next up previous
Next: The Finite State Up: Finite State Machine Previous: Temporary Label Determination

1.5.2 Search Path Compression

The HK algorithm traverses the map assigning temporary cluster labels to non-zero pixels in the order in which the pixels are encountered. Once it has been determined that two temporary clusters are actually the same cluster, a merge operation is performed. Figure 7 illustrates the effects of merging


Figure 7:  Example of search path compression in the csize array before (left) and after (right) a merge operation. The operation merged the temporary cluster labeled 2 into the temporary cluster labeled 1. This operation followed a 5-step pointer path () to determine that temporary cluster labeled 2 was actually temporary cluster labeled 3 and contains 22 pixels.

temporary cluster 2 into temporary cluster 1 and path compression on the working array csize. The resulting temporary cluster 1 then contains 34 pixels. Temporary cluster 1 contributed 12 pixels and temporary cluster 3 contributed 22 pixels. Temporary cluster 2 contains a pointer to cluster 4 which is differentiated by the negative arithmetic sign. During the merge operation, the algorithm followed a 5-step pointer path () to determine that temporary cluster 2 had previously been merged into temporary cluster 3. Pointer paths are non-circular and contain a finite number of steps. Path compression reduces the number of steps in any given path by replacing each pointer along the path with a pointer to the destination of the path. After path compression, the next time the algorithm encounters a merge involving cluster 2 the algorithm will only have to follow a 1-step path. This approach will always reduce the steps of a given path to only 1, which decreases the number of integer comparisons and overall cluster identification time.

Michael W. Berry (
Sat Mar 30 23:40:13 EST 1996