-Connected Components

The image processing problem of determining the connected components of images is a fundamental task of imaging systems (e.g. [1], [12], [13], [18], [20], [23], [24]). The task of connected component labeling is cited as a fundamental computer vision problem in the DARPA Image Understanding benchmarks ([33], [39]), and also can be applied to several computational physics problems such as percolation ([8], [35]) and various cluster Monte Carlo algorithms for computing the spin models of magnets such as the two-dimensional Ising spin model ([3], [6], [34]). All pixels with grey level (or `color') 0 are assumed to be background, while pixels with color > 0 are foreground objects. A connected component in the image is a maximal collection of uniformly colored pixels such that a path exists between any pair of pixels in the component. Note that we are using the notion of 8-connectivity, meaning that two pixels are adjacent if and only if one pixel lies in any of the eight positions surrounding the other pixel. Each pixel in the image will receive a label; pixels will have the same label if and only if they belong to the same connected component. Also, all background pixels will receive a label of 0.

It is interesting to note that, in the previous paragraph, we defined connected components as a maximal collection of uniform color pixels such that a path existed between any pair of pixels. The conventional algorithm assumes that there is a connection between two adjacent pixels if and only if their grey level values are identical. We now relax this connectivity rule and present it as a more general algorithm called -Connected Components . In this approach, we assume that two adjacent pixels with values x and y are connected if their absolute difference |x - y| is no greater than the threshold . Note that setting the parameter to 0 reduces the algorithm to the classic connected components approach. This algorithm is identical in analysis and complexity to the conventional connected components algorithm, as we are merely changing the criterion for checking the equivalence of two pixels.

For the final phase in the segmentation process, -Connected Components is applied to the enhanced image, using , where the values of and are the same as those input to the enhancement filters. The analysis for the -Connected Components algorithm is given in Section 6, equation (7). Thus, we have an efficient algorithm for image segmentation on parallel computers.