Muthuganapathy Ramanathan

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.

In this paper, we propose a Delaunay triangulation based algorithmic framework for the 2D point set type discernment and its reconstruction. The point set discernment deals with determining whether the given point set S consists of only the points sampled along the boundary of an object (referred to as boundary sample) or S is distributed across the object (referred to as dot-pattern). In general, the existing approaches deal with the reconstruction of an a priori known input type - boundary sample or dot-pattern. Our approach works on both sets of input data type by first identifying the input type that a given point set belongs to. To distinguish the point set type, we introduce the notion of Petal-Ratio(PR) which captures the ratio of the longest edge to the smallest edge emanating from a vertex in Delaunay triangulation. Further, we employ the Petal-Ratio as the essence to design simple reconstruction algorithms pertaining to each input type that unveil the shape of the object hidden in the given point set. The reconstruction algorithms start with computing the Delaunay triangulation of the given point set and for each vertex, the Petal-Ratio is calculated. Following this, the edges are removed based on the value of the PR for every vertex to arrive at the boundaries. Theoretical analysis of determining appropriate values of PRs under ϵ- sampling and minimal reach sampling models have been presented. Unlike many other algorithms, our approach is non-parametric and non-feature specific that can capture features like disconnected components, multiple holes even with the presence of outliers, self-intersection (only for boundary sample) and open curves (only for boundary sample). Moreover, our algorithms take only one pass to reconstruct the hole boundaries as well as outer boundary irrespective of the object features like the number of holes and the number of components. The comparative analysis shows that our algorithms perform equally well or better than their counterparts for the objects with contrasting features. We also demonstrate that the proposed idea can be easily extended to surface reconstruction.

We present a drawing assistant for sketching and for assisting users in shading a hand drawn sketch. The augmented reality based system uses a sketch made by a professional and uses it to help inexperienced users to do sketching and shading. The input image is converted to a set of points based on simple heuristics for providing a "connect the dots" interface for a user to aid sketching. With the help of a 2.5D mesh generated by our algorithm, the system assists the user by providing information about the colors that can be given in different parts of the sketch. The system was tested with users of different age groups and skill levels, indicating its usefulness.

We present a mixed reality-based assistive system for shading paper sketches. Given a paper sketch made by an artist, our interface helps inexperienced users to shade it appropriately. Initially, using a simple Delaunay-triangulation based inflation algorithm, an approximate depth map is computed. The system then highlights areas (to assist shading) based on a rendering of the 2.5-dimensional inflated model of the input contour. With the help of a mixed reality system, we project the highlighted areas back to aid users. The hints given by the system are used for shading and are smudged appropriately to apply an artistic shading to the sketch. The user is given flexibility at various levels to simulate conditions such as height and light position. Experiments show that the proposed system aids novice users in creating sketches with impressive shading.

Given a set of rough strokes drawn by an artist (either in pen-paper medium or in digital medium) in raster format, the objective is to group them meaningfully and represent the group with simple most appropriate curves. In this paper, a Delaunay triangulation based algorithm is proposed for grouping strokes. The grouping procedure is capable of identifying open curves and reconstructing broken strokes. The proposed algorithm is capable of helping the user in masking misinterpreted regions. We also introduce a shape aware skeleton smoothing procedure which best approximates the shape by taking input raster sketch as a reference to create final vector output. The user can also control the final output. The proposed algorithm combines the techniques in computational geometry as well as in image processing to utilize the power of both.

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.

We present a drawing assistant for sketching and for assisting users in shading a hand drawn sketch. The augmented reality based system uses a sketch made by a professional and uses it to help inexperienced users to do sketching and shading. The input image is converted to a set of points based on simple heuristics for providing a "connect the dots" interface for a user to aid sketching. With the help of a 2.5D mesh generated by our algorithm, the system assists the user by providing information about the colors that can be given in different parts of the sketch. The system was tested with users of different age groups and skill levels, indicating its usefulness.

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.

Given a finite set of points P ? R3, sampled from a surface S, surface reconstruction problem computes a model of S from P, typically in the form of a triangle mesh. The problem is ill-posed as various models can be reconstructed from a given point set. In this paper, curve reconstruction in R2, is initially looked at using the Delaunay triangulation (DT) of a point set. The key idea is that the edges in the DT are prioritized and the interior or exterior edges of the DT are removed as long as it has at least one adjacent triangle. Theoretically, it is shown that the reconstruction is homeomorphic to a simple closed curve. Extending this to 3D, an approach based on ‘retaining solitary triangles’ and ‘removing triangles anywhere’ has been proposed. An additional constraint based on the circumradius of a triangle has been employed. Results on public and real-world scanned data, and qualitative/quantitative comparisons with existing methods show that our approach handles diverse features, outliers and noise better or comparable with other methods.

Given a set of points S∈R2, reconstruction is a process of identifying the boundary edges that best approximates the set of points. In general, the set of points can either be derived from only the boundaries of the curves (called as boundary sample) or can be derived from both boundary and interior of the curves (called as dot pattern). Most of the existing algorithms focus towards reconstruction from only boundary samples, termed as curve reconstruction. Unfortunately many of them don't reconstruct when the input is of dot pattern type (called as shape reconstruction). In this paper, we propose an input-independent non-parametric algorithm for reconstruction that works for both dot patterns as well as boundary samples. The algorithm starts with computing the Delaunay triangulation of the given point set. An edge between a pair of triangles is marked for removal when the circumcenters lie on the same side of the edge. Further, we also propose additional criterion for removing edges based on characterizing a triangle by the distance between its circumcenter and incenter. To maintain a manifold output, a degree constraint is employed. The proposed approach requires only a single pass to capture both inner and outer boundaries irrespective of the number of objects/holes. Moreover, the same criterion has been employed for both inner and outer boundary detection. The experiments show that our approach works well for a variety of inputs such as multiple components, multiple holes etc. Extensive comparisons with state-of-the-art methods for various kinds of point sets including varying the sampling density and distribution show that our algorithm is either better or on par with them. Theoretical discussions on the algorithm have also been presented using ϵ-sampling and r-sampling. Limitations of the algorithm are also discussed.