An Efficient Strategy for Bit-Quad-Based Euler Number Computing Algorithm

Bin Yao, Hua Wu, Yun Yang, Yuyan Chao, Atsushi Ohta, Haruki Kawanaka, Lifeng HeIEICE 2014 · DOI

Abstract

The Euler number of a binary image is an important topological property for pattern recognition, and can be calculated by counting certain bit-quads in the image. This paper proposes an efficient strategy for improving the bit-quad-based Euler number computing algorithm. By use of the information obtained when processing the previous bit quad, the number of times that pixels must be checked in processing a bit quad decreases from 4 to 2. Experiments demonstrate that an algorithm with our strategy significantly outperforms conventional Euler number computing algorithms.

Introduction

The Euler number is a fundamental topological feature in image processing, defined as the difference between the number of connected components and the number of holes ($E = C - H$). Its invariance under transformations like rotation and scaling makes it indispensable for applications in medical imaging, document analysis, and robotics.

Traditionally, the Euler number is computed using the GRAY algorithm, which scans an image with a $2 \times 2$ sliding window (a "bit-quad"). While effective, the GRAY algorithm is computationally inefficient because it re-examines pixels as the window slides. Specifically, when moving the window one pixel to the right, two pixels that were just processed are checked again. In memory-constrained environments, these redundant accesses create a significant bottleneck.

Methodology: The State-Machine Approach

The proposed method optimizes the bit-quad counting process by transitioning from a stateless scan to a state-machine-based strategy.

Bit-Quad Counting

The algorithm identifies specific $2 \times 2$ patterns to compute the Euler number via the formula: $E = (N_1 - N_2 - 2N_3)/4$, where $N_1, N_2,$ and $N_3$ represent the counts of specific object pixel configurations.

Information Reuse and State Transitions

The core innovation lies in defining four states ($S_1$ to $S_4$) based on the values of the two pixels on the right side of the current window. As the window slides, these "right-side" pixels become the "left-side" pixels of the next window. By maintaining the current state, the algorithm "remembers" these values, requiring only two new pixel fetches from memory instead of four.

State transition diagram for the proposed Euler number computing algorithm

This state-machine logic effectively reduces the total number of pixel accesses from $4NM$ to $2NM$ for an $N \times M$ image, representing a 50% theoretical reduction in memory overhead.

Experimental Evaluation

The algorithm was benchmarked against several standard methods, including the GRAY algorithm, the run-length-based (RUN) algorithm, and the state-of-the-art labeling-based HCS algorithm. Testing was conducted on a diverse dataset including artificial noise (0% to 100% density), natural images from the SIDBA and USC-SIPI databases, and specialized medical imagery.

Results and Discussion

The experimental results confirm the efficiency of the state-machine strategy. The proposed algorithm consistently outperformed the GRAY and RUN algorithms across all test cases.

Execution time comparison across varying image densities

As shown in the performance graph, the execution time for the proposed method is significantly lower than that of the GRAY algorithm. While the HCS algorithm performs well at extreme densities (near 0% or 100%), the proposed bit-quad method provides superior and more consistent performance across the broad middle range of image densities. On natural images, the mean execution time was reduced from 1.42ms (GRAY) to 0.86ms, a real-world improvement of approximately 39%.

Conclusion

By leveraging a finite state machine to eliminate redundant memory accesses, this research provides a highly efficient strategy for Euler number computation. The reduction of pixel accesses from four to two per window translates directly into significant speed gains on general-purpose CPUs. Furthermore, the logic is well-suited for parallel hardware implementations, such as FPGAs, offering a path toward even higher performance in real-time computer vision systems.

Summary updated

Abstract

The Euler number of a binary image is an important topological property for pattern recognition, and can be calculated by counting certain bit-quads in the image. This paper proposes an efficient strategy for improving the bit-quad-based Euler number computing algorithm. By use of the information obtained when processing the previous bit quad, the number of times that pixels must be checked in processing a bit quad decreases from 4 to 2. Experiments demonstrate that an algorithm with our strategy significantly outperforms conventional Euler number computing algorithms.
BibTeX
@inproceedings{yao2014efficient,
  author = {Bin Yao and Hua Wu and Yun Yang and Yuyan Chao and Atsushi Ohta and Haruki Kawanaka and Lifeng He},
  title = {{An Efficient Strategy for Bit-Quad-Based Euler Number Computing Algorithm}},
  booktitle = {IEICE},
  year = {2014},
  doi = {10.1587/transinf.e97.d.1374},
}
Figure