Abstract
Preprocessing a 2D image often produces a noisy cloud of interest points. We study the problem of counting holes in noisy clouds in the plane. The holes in a given cloud are quantified by the topological persistence of their boundary contours when the cloud is analyzed at all possible scales. We design the algorithm to count holes that are most persistent in the filtration of offsets (neighborhoods) around given points. The input is a cloud of $n$ points in the plane without any user-defined parameters. The algorithm has a near linear time and a linear space $O(n)$. The output is the array (number of holes, relative persistence in the filtration). We prove theoretical guarantees when the algorithm finds the correct number of holes (components in the complement) of an unknown shape approximated by a cloud.
Introduction
In computer vision and image processing, interest point detection often results in a "noisy cloud" of points. A fundamental challenge is understanding the underlying shape of this cloud—specifically, how many holes it contains. Traditional methods usually require a "scale" parameter, such as a radius $\alpha$ around each point. If $\alpha$ is too small, the cloud appears as a collection of disconnected dots; if it is too large, the holes are filled in. Finding the optimal scale is difficult and often requires manual tuning. Furthermore, noise can create "fake" transient holes that disappear quickly as the scale changes. This paper introduces HOCTOP (Hole Counting based on Topological Persistence), a robust, automated way to count only the holes that represent true features of the underlying shape.
Methodology: The HOCTOP Algorithm
The HOCTOP algorithm leverages concepts from Topological Data Analysis (TDA) to provide a parameter-free solution for hole counting.
Filtration and $\alpha$-Complexes
The algorithm begins by constructing a Delaunay triangulation of the $n$ input points. It then considers the "offsets" (disks of radius $\alpha$) around each point. As $\alpha$ increases, these disks merge to form various shapes. The algorithm analyzes the entire "filtration," the sequence of shapes formed as $\alpha$ grows from zero to infinity.
Topological Persistence and the Elder Rule
Instead of selecting a single $\alpha$, the algorithm tracks the "birth" and "death" (filling in) of holes across all scales. The "persistence" of a hole is its lifespan within this filtration. When two holes merge, the "elder rule" is applied: the younger (less persistent) hole is considered to have died, while the older one survives. Long-lived holes are identified as true geometric features, while short-lived ones are dismissed as noise.
To ensure computational efficiency, the algorithm maps the problem of 1D persistence (holes) to 0D persistence (connected components) in a dual graph. This reduction allows the use of a Union-Find data structure, resulting in a near-linear time complexity of $O(n \log n)$ and $O(n)$ space.
Key Results and Probabilistic Output
Because noise is inherent in real-world data, HOCTOP does not merely output a single integer. Instead, it calculates the relative persistence of having $k$ holes across all scales, providing a probability distribution $P(k \text{ holes})$.
In evaluations using complex synthetic tests, the algorithm correctly identified the most likely hole configuration even under significant sampling noise. On real-world noisy contours, the algorithm demonstrated high stability, effectively ignoring "speckle" noise that typically confounds simpler topological algorithms.
Theoretical Guarantees
The paper provides a mathematical proof (Theorem 4) that if a point cloud is a sufficiently dense sample of an underlying shape, HOCTOP is guaranteed to find the correct number of holes. This theoretical foundation, combined with its $O(n \log n)$ efficiency, makes it a powerful tool for large-scale point cloud analysis.
Conclusion
HOCTOP provides a fast, robust, and parameter-free method to count persistent holes in noisy 2D point clouds. By leveraging topological persistence and Delaunay triangulations, it distinguishes true geometric features from noise with high accuracy. Future work may extend these concepts to 3D or utilize the extracted boundary contours for advanced image segmentation.
Summary updated