Abstract: This paper proposes an efficient two-scan labeling algorithm for binary hexagonal images. Unlike conventional labeling algorithms, which process pixels one by one in the first scan, our algorithm processes pixels two by two. We show that using our algorithm, we can check a smaller number of pixels. Experimental results demonstrated that our method is more efficient than the algorithm extended straightly from the corresponding labeling algorithm for rectangle binary images.
Introduction
Connected component labeling (CCL) is a fundamental step in computer vision, used to identify distinct "objects" in a binary image by grouping adjacent foreground pixels. While most image processing occurs on rectangular grids, hexagonal grids offer unique advantages: they provide consistent connectivity (every neighbor is equidistant) and more closely resemble the arrangement of photoreceptors in the human eye.
However, labeling algorithms for hexagonal grids have historically been "straight extensions" of rectangular ones. These extensions are inefficient because hexagonal tiling results in different neighbor "masks" depending on a pixel's position. This paper addresses the lack of a specialized, high-performance labeling algorithm that leverages the unique geometry of hexagonal lattices.
Methods
The proposed algorithm is an optimized two-scan labeling algorithm.
- The First Scan: The algorithm traverses the image to assign provisional labels. If a foreground pixel is adjacent to already-labeled pixels, it takes their label; if it connects two different labels, it records them as "equivalent."
- The Second Scan: It replaces all provisional labels with a single representative label for each connected component.
Innovation: 2x2 Block Processing
Standard algorithms process pixels one by one. In a hexagonal grid, adjacent pixels share many of the same neighbors. The authors propose processing pixels in pairs (referred to as 2x2 blocks in the context of grid traversal) simultaneously to avoid redundant checks. For instance, if the first pixel in the pair is already identified as foreground and assigned a label, the second pixel can often inherit that label immediately without re-scanning its entire neighborhood. This reduces the total number of memory lookups and logical comparisons.
As shown in the neighborhood masks above, hexagonal grids require two different masks depending on whether the pixel is in an "even" or "odd" position relative to the grid's stagger. By moving to a block-based strategy, the algorithm "remembers" the state of shared neighbors, minimizing computational overhead.
Experimental Evaluation
Since native hexagonal image datasets are rare, standard rectangular datasets were converted into hexagonal formats for evaluation. These included noise images with varying foreground densities (0.1 to 0.9), natural images from the SIDBA and USC-SIPI databases, medical images, and artificial patterns like spirals.
Key Results
The proposed algorithm was compared against the "SF algorithm," a straight extension of the state-of-the-art HCS rectangular algorithm.
- Speedup: The 2x2 method outperformed the SF algorithm across all test cases.
- Noise Performance: On noise images, the algorithm achieved a maximum speedup of 10.91% at a density of 0.6.
- General Performance: In natural images, the mean execution time dropped from 0.97ms (SF) to 0.91ms (Ours).
- Efficiency: The results confirm that checking fewer pixels per scan directly translates to faster processing times without sacrificing accuracy.
Conclusion
This work introduces the first optimized CCL algorithm specifically designed for hexagonal images. By exploiting the shared neighborhood properties of hexagonal grids, the algorithm achieves significant performance gains over traditional methods. Future work includes extending this block-processing logic to 3D hexagonal (rhombic dodecahedron) lattices and exploring hardware-specific optimizations like SIMD instructions.
Summary updated