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.

Ramanathan Muthuganapathy

Department of Engineering Design

Image reconstruction

Triangulation

BOUNDARY SAMPLES

Comparative studies

DELAU-NAY TRIANGULATIONS

Delaunay triangulation

DOT PATTERNS

RECONSTRUCTION PROBLEMS

Theoretical guarantees

TIME AND SPACE COMPLEXITY

geometry

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)

Complex vector drawings serve as convenient and expressive visual representations, but they remain difficult to edit or manipulate. For clean-line vector drawings of smooth organic shapes, we describe a method to automatically extract a layered structure for the drawn object from the current or nearby viewpoints. The layers correspond to salient regions of the drawing, which are often naturally associated to ‘parts’ of the underlying shape. We present a method that automatically extracts salient structure, organized as parts with relative depth orderings, from clean-line vector drawings of smooth organic shapes. Our method handles drawings that contain complex internal contours with T-junctions indicative of occlusions, as well as internal curves that may either be expressive strokes or substructures. To extract the structure, we introduce a new part-aware metric for complex 2D drawings, the radial variation metric, which is used to identify salient parts. These parts are then considered in a priority-ordered fashion, which enables us to identify and recursively process new shape parts while keeping track of their relative depth ordering. The output is represented in terms of scalable vector graphics layers, thereby enabling meaningful sketch editing and manipulation. We evaluate the method on multiple input drawings and show that the structure we compute is convenient for subsequent posing and animation from nearby viewpoints. Lastly, to further demonstrate the usefulness of our system, we develop two direct applications, namely the creation of cardboard articulated puppets and part-based 3D modeling from a single sketch. © 2019 Elsevier Ltd

Fulltext

Automatic structuring of organic shapes from a single drawing

We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece-wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non-uniformly (ε-sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non-uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm. © 2018 The Authors Computer Graphics Forum © 2018 The Eurographics Association and John Wiley & Sons Ltd.

Computer Graphics Forum

Incremental Labelling of Voronoi Vertices for Shape Reconstruction

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

Hole detection in a planar point set: An empty disk approach

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 ε-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 Author(s) Computer Graphics Forum © 2016 The Eurographics Association and John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

Crawl through Neighbors: A Simple Curve Reconstruction Algorithm

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.

CAD Computer Aided Design

A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering

ACM SIGGRAPH 2016 Courses on - SIGGRAPH '16

CGAL

ACM Transactions on Graphics

Screened poisson surface reconstruction

An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes

IET Computer Vision

Polygonal shape reconstruction in the plane

A unified approach towards reconstruction of a planar point set

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