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. © 2017 Elsevier Ltd

Ramanathan Muthuganapathy

Department of Engineering Design

geometry

Triangulation

DELAU-NAY TRIANGULATIONS

HOLE DETECTION

Non-parametric

Planar point sets

SHAPE RECONSTRUCTION

Face recognition

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Computers and Graphics (Pergamon)

Given a planar point set sampled from a curve, the curve reconstruction problem computes a polygonal approximation of the curve. In this paper, we propose a Delaunay triangulation-based algorithm for curve reconstruction, which removes the longest edge of each triangle to result in a graph. Further, each vertex of the graph is checked for a degree constraint to compute simple closed/open curves. Assuming ϵ-sampling, we provide theoretical guarantee which ensures that a simple closed/open curve is a piecewise linear approximation of the original curve. Input point sets with outliers are handled as part of the algorithm, without pre-processing. We also propose strategies to identify the presence of noise and simplify a noisy point set, identify self-intersections and enhance our algorithm to reconstruct such point sets. Perhaps, this is the first algorithm to identify the presence of noise in a point set. Our algorithm is able to detect closed/open curves, disconnected components, multiple holes and sharp corners. The algorithm is simple to implement, independent of the type of input, non-feature specific and hence it is a generalized one. We have performed extensive comparative studies to demonstrate that our method is comparable or better than other existing methods. Limitations of our approach have also been discussed. © 2018 Elsevier Ltd

Peeling the longest: A simple generalized curve reconstruction algorithm

Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non-parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under e-sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces. © 2016 The Eurographics Association and John Wiley & Sons Ltd.

Eurographics Symposium on Geometry Processing

Crawl through neighbors: A simple curve reconstruction algorithm

Reconstruction problem in R2 computes a polygon which best approximates the geometric shape induced by a given point set, S. In R2, the input point set can either be a boundary sample or a dot pattern. We present a Delaunay-based, unified method for reconstruction irrespective of the type of the input point set. From the Delaunay Triangulation (DT) of S, exterior edges are successively removed subject to circle and regularity constraints to compute a resultant boundary which is termed as ec-shape and has been shown to be homeomorphic to a simple closed curve. Theoretical guarantee of the reconstruction has been provided using r-sampling. In practice, our algorithm has been shown to perform well independent of sampling models and this has been illustrated through an extensive comparative study with existing methods for inputs having varying point densities and distributions. The time and space complexities of the algorithm have been shown to be O(nlogn) and O(n) respectively, where n is the number of points in S. © 2015 Elsevier Ltd. All rights reserved.

A unified approach towards reconstruction of a planar point set

In this paper, we present a fully automatic Delaunay based sculpting algorithm for approximating the shape of a finite set of points S in R2. The algorithm generates a relaxed Gabriel graph (RGG) that consists of most of the Gabriel edges and a few non-Gabriel edges induced by the Delaunay triangulation. Holes are characterized through a structural pattern called as body-arm formed by the Delaunay triangles in the void regions. RGG is constructed through an iterative removal of Delaunay triangles subjected to circumcenter (of triangle) and topological regularity constraints in O(nlogn) time using O(n) space. We introduce the notion of directed boundary samples which characterizes the two dimensional objects based on the alignment of their boundaries in the cavities. Theoretically, we justify our algorithm by showing that under given sampling conditions, the boundary of RGG captures the topological properties of objects having directed boundary samples. Unlike many other approaches, our algorithm does not require tuning of any external parameter to approximate the geometric shape of point set and hence human intervention is completely eliminated. Experimental evaluations of the proposed technique are done using L2 error norm measure, which is the symmetric difference between the boundaries of reconstructed shape and the original shape. We demonstrate the efficacy of our automatic shape reconstruction technique by showing several examples and experiments with varying point set densities and distributions. © 2014 Elsevier Ltd.

Journal	Data powered by TypesetComputers and Graphics (Pergamon)
Publisher	Data powered by TypesetElsevier Ltd
ISSN	00978493
Open Access	No