Implementation Environment

Programming Environment: Visual C++
Computer: Dual processor Pentium III
Camera: MEGA-D Digital Stereo Camera (IEEE-1394 Connection)

The camera input, as well as the disparity calculations were obtained using SRI's Small Vision System. We linked these libraries into our code, courtesy of Dr. Kurt Konolige at SRI.

Implementation Details

Normalization: As discussed in the theory section, in order for the points to minimize the area of the object they surround, they must maintain equal spacing. Our method for normalization was very simple, yet fast and effective. We calculate the polygonal perimiter of the region within the contour as we are calculating the new locations for the points. Once the new points are assigned, we cycle again through the points, placing point i at distance i*perimeter/n from point 0. (Where n is the number of points). These distances are calculated along the perimeter of the region.

Contour Loops: During the developmentof our system, we found that there was another issue that needed to be resolved. SVS performs a texture check when calculating disparities, so objects without texture are left out of the disparity image. Hence it is often the case that the object we are tracking has gaps between its blobs. When the contour enters these gaps, it is possible for points to cross leading to a loop in the contour. By the algorithm given in the theory the loops then continue to expand.(Since the direction vectors become inverted).

In the case of loops on the outside of the contour, we were able to solve the problem by a sensible modification of the algorithm. After the normal vectors are calculated, the actual direction vectors of the points are recalculated based on the following formula:

Effectively, this implies that when distant points (along the contour) come physically close to a point, then the point will be pushed away from them. Since distance(i,j) will be small the other points' normal vector will contribute to the vector of the point. This was very successful in dealing with outer loops as they would actually unwind.

We were not as successful at dealing with inner loops since this method is no longer applicable. (This can be proved). In our current implementation of the program, in addition to the new vector calculation, we prevent points from moving too close to other points by a threshold.


Implementing a working handler for occlusion involved many trials and ideas.

Detecting Occlusion: In order to handle cases of occlusion, it is first necessary to detect them. We considered using a method of closest points to detect whether a point in one snake was inside another snake. This involved finding the closest point in each other existing snake and then checking within a certain angle of the inside normal vector of the point. Since this would be computationally expensive for many snakes, we restricted the algorithm to bounded boxes. A point is considered occluded if it is within the bounded box of another snake.

We attempted to use disparity information to judge which object was in the foreground, however we were unable to get solid distinctions in disparity when objects were close. Our implementation currently disregards which object is in the foreground, thus all points inside a bounding box of another snake are considered occluded.

Handling Occlusion: If a point (on a snake) is detected to be occluded, we assume that that point can no longer gather valid information to change its position. Keeping it stationary is not reasonable since the object tracked by the snake moves. Hence, we move it based on the unoccluded points. For each frame we first calculate the unoccluded points. Then, if there are occluded points, we find the translation of the contour from the previous frame to the current frame which maximizes the similarity in position and shape. We do this by testing translations of two magnitudes in eight directions. In order to calculate the quality of the approximation, for each point in the translated snake, we find the closest point in the new snake and sum these distances.

Finding the closest point in this case is not expensive, due to the relatively small motion of the snake. The closest point in the new snake to an approximation obtained by translating the old snake is extremely likely to either be the same point, or one of its two neighbors. Once the translation that produces the best fit is found, it is applied to the occluded points and all the points are normalized.