Automatic Centroid Algorithm

The algorithm has three phases: finding all the regions in the image, determining which regions are centroids, and putting the centroids in the correct order.

To find the black regions in the image, an iterative algorithm is used to assign a different color to each different region. An L-shaped "window" iteratively scans the image from left to right, top to bottom. The window can be visualized as follows:

	 U
	LC

Each letter corresponds to a pixel. If "C" is ontop of a pixel that is black, the algorithm checks the values of the pixels under "L" and "U": If "U" is black or already colored and "L" is white then "C" is of the same region as "U" so the pixel under "C" is assigned to the same color as "U". A similar assignment is made if "L" is already colored and "U" is white. If both "L" and "U" have already been colored, then all three pixels under the window are assigned the same color as the pixel under "U". If both "L" and "U" are white, then the pixel under "C" (remember: we already know it is black) is assigned to an unused color, thus beginning a new region. The window is then moved one pixel to the right, or if it has reached the end of a row, down a row and over to the first pixel on the left, and the algorithm continues until the window has gone over the entire image.

The program performs various tests on the regions to determine if a region is a centroid or not. It first checks to see if the number of pixels in the region is within a preset range of values. This test eliminates noise specks and large blobs. Then the ratio of the height of the region to its width. Proper centroids have ratios close to 1. This also eliminates regions that are 1 pixel wide or long. The second to last test compares the midpoint of the region to the average "x" and "y" values of the region. In a centroid, thes values would be very close. The final test makes sure that the region is not on the edge of the image. If it passes all the tests, it is a centroid.

Ordering the centroids begins by finding the hollow centroids. Once these are found, the line between the two centroids is calculated. The algorithm determines which side of the line all the solid centroids are on and their distance from it. With this information, ordering is easy (more explanation necessary).

Up to "Camera Calibration"

Back to "Identifying the calibration points"