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