next up previous
Next: Finite State Machine Up: Hoshen-Kopelman Algorithm Previous: Neighborhood Rule

1.4 Implementing the Hoshen-Kopelman Algorithm

As each row of the map is traversed, the value of the current pixel is compared to the value of the previous pixel in that row (west neighbor) and the pixel value in the same column of the previous row (north neighbor). Abiding by the NEWS neighborhood rule, if all pixels are in the same cluster, the smallest cluster label is assigned to all three pixels and any changes in the status of the west and north neighbors are recorded in the working arrays. The smallest of the two values is chosen to reduce the memory requirements of the csize array where the maximum size is a function of the density of the map and the pixel clustering patterns. For the best use of memory by the csize array, the best case scenario is a map entirely of 1's or 0's which would contain only 1 cluster of size . The csize array size would be 1. Conversely, the worst case scenario is a checkerboard pattern, alternating 1's and 0's throughout the map, resulting in clusters each containing only 1 pixel. The csize array size would be . When the algorithm completes, each index in the csize array holds one of three values: a zero, the number of pixels in the cluster identified by the csize index value, or a pointer to another csize index. The last two values are differentiated by the arithmetic sign of the value---positive represents the pixel count in the indexed cluster whereas negative represents a pointer to another csize array index. De-referencing the pointer, which could follow a non-circular, multi-step path, is accomplished by indexing into the csize array using the absolute value of the pointer. The HK algorithm does not guarantee a properly labeled map; however, relabeling, or adjusting pixel values to accurately reflect cluster membership can be accomplished in linear time using the working array produced by the HK algorithm. Figure 6 illustrates the results of the working array csize after merging the temporary cluster labeled 2 from the top row into the temporary cluster labeled 1.

 


Figure 6:  Example of working arrays csize and matrix manipulation during the implementation of the Hoshen-Kopelman algorithm. The After image of the csize array illustrates the results of merging the temporary cluster labeled 2 ( matrix array) into the temporary cluster labeled 1.

Before the merge, temporary cluster 1 contained 9 pixels, and temporary cluster 2 contained 2 pixels. After the addition of the current pixel (1 pixel) and the pixels from temporary cluster 2 (2 pixels), temporary cluster 1 now contains 12 pixels (9 + 2 + 1), and temporary cluster 2 shows a pointer to temporary cluster 1 in the csize working array. It is possible to process extremely large maps in linear time using a divide-and-conquer approach to cluster identification because at a point in time, the algorithm only requires access to the working array csize, the current pixel, the north neighboring pixel, and the pixel value of the west neighbor. In this work, both an improved sequential implementation of the HK algorithm and a parallel implementation on the Thinking Machines CM-5 are presented.



next up previous
Next: Finite State Machine Up: Hoshen-Kopelman Algorithm Previous: Neighborhood Rule



Michael W. Berry (berry@cs.utk.edu)
Sat Mar 30 23:40:13 EST 1996