Abstract
This paper proposes a graph-theory-based Euler number computing algorithm. According to the graph theory and the analysis of a mask's configuration, the Euler number of a binary image in our algorithm is calculated by counting four patterns of the mask. Unlike most conventional Euler number computing algorithms, we do not need to do any processing of the background pixels. Experimental results demonstrated that our algorithm is much more efficient than conventional Euler number computing algorithms.
Introduction
In the field of computer vision and image analysis, the Euler number is a fundamental topological property. Defined as the number of connected components minus the number of holes, it remains invariant under transformations like stretching or twisting. This stability makes it an essential feature for pattern recognition, medical imaging, and robot vision.
Calculating the Euler number efficiently remains a challenge. Traditional methods, such as the "GRAY" algorithm used in MATLAB’s bweuler function, typically scan $2\times2$ pixel blocks (bit-quads). While improvements like the "I-GRAY" algorithm have reduced computational overhead, they still require checking numerous pixel patterns and often process background pixels unnecessarily. As image resolutions increase, these inefficiencies become more pronounced.
Methodology: A Graph-Theory Perspective
The proposed algorithm shifts the perspective from traditional image processing to graph theory. A binary image is represented as a square graph where each foreground pixel serves as a vertex, and edges are drawn between 8-connected neighboring pixels (ensuring no edges cross).
By applying Euler’s Theorem for planar graphs ($v - e + f = c + 1$, where $v$ is vertices, $e$ is edges, $f$ is faces, and $c$ is connected components), the Euler number can be derived by tracking the increments of vertices, edges, and faces during a raster scan. The core innovation lies in the algorithm's efficiency: it ignores background pixels entirely, as they contribute zero to the graph's topological counts.
Mask Optimization and Pattern Reduction
As the algorithm performs a raster scan, it utilizes a mask of four previously processed neighbors. While there are 16 possible configurations for this mask, the researchers proved that only four specific patterns actually result in a change to the Euler number ($\Delta E \neq 0$).
By focusing only on these four patterns ($P1, P10, P11, P12$), the algorithm drastically reduces the logical branching required by the CPU. Using Karnaugh maps for logic simplification, the algorithm needs to check an average of only 1.875 pixels in the mask for every foreground pixel encountered—a lower requirement than any previous conventional algorithm.
Experimental Results
The algorithm was benchmarked against I-GRAY, the previous state-of-the-art conventional method, using a variety of datasets including noise-heavy images, artificial patterns (spirals, honeycombs), and natural/medical images from the SIDBA and USC databases.
- Speed: The graph-theory algorithm outperformed I-GRAY in every test case. For natural images, mean execution time dropped from 0.86ms to 0.71ms.
- Density Performance: Unlike traditional methods with static costs, this algorithm's execution time is directly proportional to the number of foreground pixels, making it exceptionally fast for sparse images.
Conclusion
By treating pixels as graph vertices and optimizing mask logic to just four critical patterns, this algorithm provides a significant speedup for topological feature extraction. Its reliance on a standard raster-scan pattern also makes it an ideal candidate for future parallelization on GPUs or multi-core systems to handle ultra-high-resolution imagery in real-time.
Summary updated