Hole detection in a planar point set: An empty disk approach. (August 2017)

• Record Type: Journal Article
• Authors: Methirumangalath, Subhasree; Kannan, Shyam Sundar; Dev Parakkat, Amal; Muthuganapathy, Ramanathan
• Is Part Of: Computers & graphics. Volume 66(2017)
• Page Start: 124
• Page End: 134
• Publication Date: 2017-08
• Subjects: Hole detection -- Shape reconstruction -- Island detection -- Delaunay triangulation -- Non-parametric -- Planar point set; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2017.05.006
• Languages: English
• ISSNs: 0097-8493

Abstract

Highlights: A non-parametric Delaunay based algorithm. Can detect holes in a boundary sample or a dot pattern. Theoretical analysis has been performed. Results indicate the algorithm is independent of sampling of the input point set. Extensive comparison and evaluation of the algorithm show it is better or on par with existing algorithms. Graphical abstract: Abstract: Given a planar point set S, outer boundary detection (shape reconstruction) is an extensively studied problem whereas, inner boundary (hole) detection is not a well researched one, probably because detecting the presence of a hole itself is a difficult task. Nevertheless, hole detection has wide applications in areas such as face recognition, model retrieval and pattern recognition. We present a Delaunay triangulation based strategy to detect the presence of holes and an algorithm to reconstruct them. Our algorithm is a unified one which reconstructs holes, both for a boundary sample (points sampled only from the boundary of the object) as well as for a dot pattern (points sampled from the entire object). Our method is a non-parametric one which detects holes irrespective of its shape. Assuming a sampling model, we provide theoretical analysis of the proposed algorithm, which ensures the correctness of the reconstructed holes, for specific structures. We conduct both qualitative and quantitative comparisons with existing methods and demonstrate that our method is better or comparable with them. Experiments with varying point densities and distributions demonstrate that the algorithm is independent of sampling. We also discuss the limitations of the algorithm.