Last updated: 11 April 2000 &beetung <Tue> 1:40am
 

Track Identification Algorithm

Since we are only utilizing a single CCD camera as our environment feedback, all navigation related algorithms and procedures must be based on sequence of images received. There are various disadvantages associated with performing navigation this way[XXX,XX]. For example, the speed-scale ambiguity where .... The CPU intensive information processing time,...

In order to reduce the processing time required, we assumed specific track conditions and introduced visual clues which enables us to satisify the needs of our navigation system.
 

I would attempt to implement a track folding algorithm. Obviously, it is for track extraction based on the image sequence received. In addition, a basic short-term position mapping would also be implemented. If time permits, a collusion avoidance technique based on B-spline would also be attempted. All these algorithms would be implemented in C++. At this stage(april 2000), only the basic algorithm structure have been tested.

Work done so far:

1. Testing XSHM extension for Linux

XShm allows direct X image mapping from memory to screen without utilising several slower X interface. I managed to achieve 44fps on a P-III. From several newsgroup article, it seems quite possible that frame rate above 100 can be achieved.
2. Basic Algorithm object structure

I have implemented the basic structure of my algorithm design. Track folding seems to work quite well but there are lots of different issues to be addressed still! Ie: where should the folding window be, how does this interact with short-term history mapping,etc.

3. P-Thread package

A multi-threaded library(p-thread) has been tested under Linux to perform some concurrent calculations. We might utilise this library later on for various purposes.
4. Reading Tim’s 1999 C code

I have thoroughly read Tim’s navigation system code. His navigation system is quite logical and simple to understand.

Implementation Details

The follow Diagrams illustrate sequencially the steps in achieving track extraction. There is a resultant estimated value that indicates the current relative location of our RF car about the track after each frame analysis.

Image received

Mirroring the RHS of our image and XOR-ing with the LHS.

 
 
 
 
 

We will also prioritize our folding algorithm. A track is divided into two or more regions horizontally. Initially, all processing would only be done on the top part of the track. Since the upper region represent what is further down the track. Prioritizing enables us to response more quickly in changing track condition and eliminate the needs for reduntent track ID. After processing the upper region, control is passed back to our navigation kernal where other task with higher priority can be processed. Eventually, if our processing power is sufficient, the navigation kernal would signal track ID on the lower part of the track.
For example, from the following image, we can see that we are not on center of track(COT). In folding the upper region, a resultant XOR map would be produced. This map essentially tells us how we should adjust our left/right control in an attempt to follow the shape of the track.
 

Collusion Avoidance technique via B-Spline.

When we are approaching an object from a distance, the closer we are towards the object, the bigger the size of the object would be. By measuring the rate of change of a object or its divergence, we can effective estimate the its closeness in relation to our location. Collusion avoidance can be achieved this way. Our goal, however, is to find a computational efficient object tracking algorithm which enables us to estimate the divergence in a simple manner. Utilizing B-Spline for collusion avoidance was propose
by Cipoola[XXXX].