Implementation |
Our final stage of development was to supply the region-growing program with an array of starting points, rather than just one. The program starts the algorithm sequentially over each of these starting points, and maintains a linked list of regions. We chose not to spend the time developing an automatic starting-point finder, although we had discussed several methods.
The method that we felt would work best is the following: Low-pass filter the image very heavily, perform a gradient operation, take the absolute value, and use local minima as starting points. Assuming (as we did above) that the intensity values were equal to or greater in the middle of the object than towards the edges, this method should give starting points close to the middle of regions.
We used a median filter for low-pass filtering the image before finding the gradient of the image. We decided to use a 7x7 median filter (the size was chosen through experimentation). We then found the gradient of the smoothed image, and then normalized and histogram-equalized it, simply for convenience. Then we found the places where the gradient was in the top 5% (only the edges of the objects) and averaged the intensity values at these points. This gave us an approximate lower bound on intensity for membership in the region.
We wrote a C program that takes as inputs an image, and a set of points from which to start the region-growing process. The algorithm begins at each starting pixel and scans the neighboring 8 pixels in a circular fashion, to determine membership of the region around the central pixel. As pixels are added, the process repeats with the newly added pixels as the center pixel. A list of tested pixels is maintained, to avoid unnecessary duplication of tests. In this way, the region is constructed, using the membership criteria already discussed.
Because of the short-term nature of this project, we did not have the time to implement a region-merging technique. However, we did think about ways to do this. When we pick several points around which to start growing regions, there is a chance that two of these regions will eventually meet. If they do meet, we may not necessarily want to join them - there could be two objects very close to one another, even touching each other.
To decide whether or not to merge two regions, we could compare their histograms to see if they are similar (in mean gray level and texture). If the histograms were similar (meaning the regions are either in the same object or two different objects of the same type), and we had a priori information about the shape of an object, we could check to see if the merger would produce a shape closer to, or farther away from what we are looking for. A good measure of shape is the ratio of the perimeter squared to the area of the region (p2/a).