An Efficient Two-Scan Labeling Algorithm for Binary Hexagonal Images

Lifeng He, Xiao Zhao, Bin Yao, Yun Yang, Yuyan ChaoIEICE 2014 · DOI

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.

Hexagonal grid coordinate system used for image representation.

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.

  1. 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."
  2. 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.

The two distinct neighborhood masks required for hexagonal grids due to grid staggering.

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

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.
BibTeX
@inproceedings{he2014efficient,
  author = {Lifeng He and Xiao Zhao and Bin Yao and Yun Yang and Yuyan Chao},
  title = {{An Efficient Two-Scan Labeling Algorithm for Binary Hexagonal Images}},
  booktitle = {IEICE},
  year = {2014},
  doi = {10.1587/transinf.2014edl8119},
}
Figure