Basically, we wanted a fast algorithm that can run per each frame with the least cost, so our choice was the Component-Labeling Algorithm Using Contour Tracing Technique. That algorithm runs in linear time & was reported faster than other ones (see the table bellow)
#CC : Number of connected componentsAs a polygon can be determined by set of vertices, a component can be determined with the set of points lying on its contour.. Mainly, the Algorithm scans a binary image & the process is divided into four steps (as illustrated in the figure):
1- when an external contour point, say A, is encountered the first time, we make a complete trace of the contour until we return to A. We assign a label to A and to all points of that contour.3- when an internal counter point, say B, is encountered the first time, we assign B the same label as the external contour of the same component. We then trace the internal contour containing B & also assign to all contour points the same label as B.
4- when a labeled internal contour point, say B’, is encountered, we follow the scan line to find all subsequent black pixels & assign them the same label as B’.
When implementing the above procedures first we add a dummy row of black pixels at the top & associate the image with an array carrying the labels per each pixel (initially all pixels are unlabeled).
We start initially with label C (where C = 1). Following the 4 steps described above, we will be able to assign a label for each pixel, The value of C is incremented when a new unlabeled external contour is encountered.
Each time the value of C is incremented, this indicates that a new blob is found, a new blob is then created, given a new id & added to the list of blobs (which is later on handled by the tracker)
Regarding the contour tracing Algorithm, its a flood fill algorithm that works by checking the 8 neighbors of a pixel searching for white pixels, The searching procedure is also done in an optimized way that makes searching faster and also guarantee that each pixel is checked only once during the whole procedure.
Now, The Algorithm is implemented & tested successfully with other modules of the project.
Updates:
For further processing requirements, some additions were added to the algorithm including: calculating the center of mass of each blob by calculating the total mass. In addition to that, Blobs are inserted in a sorted order. (refer to the Tracking post)
Further work:
Investigation about making the thresholding value that determines the blobs a more dynamic one depending on the illumination of the frames received.
References
Component-Labeling Algorithm Using Contour Tracing Technique Paper
