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
) 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.
