Muthuganapathy Ramanathan

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 propose an algorithm to compute and maintain the spatial proximities of planar points continuously moving along predefined linear trajectories. The proximity information of moving points is captured and maintained via the well known Gabriel graph adapted for the kinetic setting, called kinetic Gabriel graph (KGG). Kinetic Gabriel Graph is built on top of the kinetic framework of Delaunay graph. Leveraging the positioning of the Delaunay circumcenters relative to the corresponding Delaunay triangles, we formulate `Gabriel certificates' that determine whether or not an edge of a Delaunay triangle is Gabriel. Then we employ an edge tagging algorithm to maintain the set of all Gabriel edges from the Delaunay graph as the points move. The proposed algorithm has been evaluated using numerous test data, and various computational implications with respect to the topological events occurring in the data structure during the points' movement have been discussed. We also provide a conceptual demonstration of the practical potentials of the proposed algorithm in video based monitoring systems.

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.

In this chapter, we present a new hierarchical deep learning-based approach for semantic segmentation of 3D point cloud. Our method involves nearest neighbor search for local feature extraction followed by an auxiliary pretrained network for classification. The proposed method constructs an octree representation of given point cloud and then performs a box search for finding neighborhood points, which are used in local feature extraction. The problem of segmentation is redefined to a per point classification task, and segmentation labels of every point is evaluated independently. This architecture can be fed with any number of points in input point cloud as opposed to state-of-the-art existing architectures, which demands fixed size input. Usefulness of the proposed approach is substantiated by supportive qualitative and quantitative results on shapenet dataset. Our method can produce effective segmentation even for shapes different from the ones used while training.

Search and retrieval remains a major research topic in several domains, including computer graphics, computer vision, engineering design, etc. A search engine requires primarily an input search query and a database of items to search from. In engineering, which is the primary context of this paper, the database consists of 3D CAD models, such as washers, pistons, connecting rods, etc. A query from a user is typically in the form of a sketch, which attempts to capture the details of a 3D model. However, sketches have certain typical defects such as gaps, over-drawn portions (multi-strokes), etc. Since the retrieved results are only as good as the input query, sketches need cleaning-up and enhancement for better retrieval results. In this paper, a deep learning approach is proposed to improve or clean the query sketches. Initially, sketches from various categories are analysed in order to understand the many possible defects that may occur. A dataset of cleaned-up or enhanced query sketches is then created based on an understanding of these defects. Consequently, an end-to-end training of a deep neural network is carried out in order to provide a mapping between the defective and the clean sketches. This network takes the defective query sketch as the input and generates a clean or an enhanced query sketch. Qualitative and quantitative comparisons of the proposed approach with other state-of-the-art techniques show that the proposed approach is effective. The results of the search engine are reported using both the defective and enhanced query sketches, and it is shown that using the enhanced query sketches from the developed approach yields improved search results.

We present a parallel algorithm for computing the Voronoi diagram of a set of circles, C. The algorithm starts with a parallel computation of the Voronoi cell of each circle ci∈C, using a subset of circles, Ci⊂C, and a reduced touching disc method. Unlike the actual touching disc method, a reduced touching disc method does not compute antipodal discs (ADs) between all pairs of circles. We employ the Delaunay graph, D, of the center points of circles in C to set an initial Ci. For computing an initial Voronoi cell for ci∈C, it is enough to compute ADs between ci and each of the circles cj∈Ci. Computation of Voronoi cells updates initially assumed Ci, and the algorithm iteratively computes those Voronoi cells until no further updating of Ci occurs. A parallel procedure corrects the Voronoi cells, iteratively, using a topology matching approach. A reduced touching disc method and a cell-wise computation of the Voronoi diagram allow input in non-general position. Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of circles.

Discretizing the input curves into points or lines is a way of constructing an approximate Voronoi diagram. Sampling the input curves into points requires a fine sample density to obtain a reasonable topological and geometrical accuracy of the Voronoi diagram. In this work, it is shown that an accurate computation of the Voronoi diagram for a set of circles employing a very coarse sample set is possible. The approach proposes the selection of varying number of sample points on each circle dynamically, using the Delaunay graph of center points of circles. We then show that this approach can be used to identify neighborhood information of the circles. The touching disc method is then used to construct the Voronoi diagram with an algorithmic complexity of O(nlogn). The work also demonstrates the robustness and theoretical correctness of the proposed algorithm by considering inputs in non-general position and for a large number of circles of the order of 105.

The success of deep learning methods led to significant breakthroughs in 3-D point cloud processing tasks with applications in remote sensing. Existing methods utilize convolutions that have some limitations, as they assume a uniform input distribution and cannot learn long-range dependences. Recent works have shown that adding attention in conjunction with these methods improves performance. This raises a question: can attention layers completely replace convolutions? This letter proposes a fully attentional model - Point Transformer (PT) for deriving a rich point cloud representation. The model's shape classification and retrieval performance are evaluated on a large-scale urban data set - RoofN3D and a standard benchmark data set ModelNet40. Extensive experiments are conducted to test the model's robustness to unseen point corruptions for analyzing its effectiveness on real data sets. The proposed method outperforms other state-of-the-art models in the RoofN3D data set, gives competitive results in the ModelNet40 benchmark, and shows high robustness to various unseen point corruptions. Furthermore, the model is highly memory and space-efficient when compared to other methods.

We present a parallel algorithm for computing the Voronoi diagram of a set of spheres, S in R3. The spheres have varying radii and do not intersect. We compute each Voronoi cell independently using a two-stage iterative procedure, assuming the input spheres are in general position. In the first stage, an initial Voronoi cell for a sphere si is computed using an iterative lower envelope approach restricted to a subset of spheres Li⊂S. This helps to avoid defining the bisectors between all pairs of input spheres and develop a distributed memory parallel algorithm. We use the Delaunay graph of sample points from the input spheres to select the subset Li for computing each Voronoi cell. In the second stage, Voronoi cells obtained from the first stage are matched for updating the subsets. If additional spheres are added to a subset Li, the correctness of the computed vertices is verified with the bisectors of spheres newly added to Li. Results and performance of the algorithm show robustness and speed of the algorithm in handling a large set of spheres.

Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non-manifold outlines, run-time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open-sourced benchmark for the experimental study. Our unprecedented evaluation of a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results and easy integration of new algorithms.