Shape registration has a wide range of applications in geometric modeling, medical imaging, and computer vision. This paper focuses on the registration of the genus-3 vestibular systems and studies the geometric differences between the normal and Adolescent Idiopathic Scoliosis (AIS) groups. The non-trivial topology of the VS poses great technical challenges to the geometric analysis. To tackle these challenges, we present an effective and practical solution to register the vestibular systems. We first extract six geodesic landmarks for the VS, which are stable, intrinsic, and insensitive to the VS’s resolution and tessellation. Moreover, they are highly consistent regardless of the AIS and normal groups. The detected geodesic landmarks partition the VS into three patches, a topological annulus and two topological disks. For each pair of patches of the AIS subject and the control, we compute a bijective map using the holomorphic 1-form and harmonic map techniques. With a carefully designed boundary condition, the three individual maps can be glued in a seamless manner so that the resulting registration is a homeomorphism with exact landmark matching. Our method is robust, automatic and efficient. It takes only a few seconds on a low-end PC, which significantly outperforms the non-rigid ICP algorithm. We conducted a student’s t-test on the test data. Computational results show that using the mean curvature measure E_H, our method can distinguish the AIS subjects and the normal subjects.

Computing geodesic distances on triangle meshes is a fundamental problem in computational geometry and computer graphics. To date, two notable classes of algorithms, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been proposed. Although these algorithms can compute exact geodesic distances if numerical computation is exact, they are computationally expensive, which diminishes their usefulness for large-scale models and/or time-critical applications. In this paper, we propose the fast wavefront propagation (FWP) framework for improving the performance of both the MMP and CH algorithms. Unlike the original algorithms that propagate only a single window (a data structure locally encodes geodesic information) at each iteration, our method organizes windows with a bucket data structure so that it can process a large number of windows simultaneously without compromising wavefront quality. Thanks to its macro nature, the FWP method is less sensitive to mesh triangulation than the MMP and CH algorithms. We evaluate our FWP-based MMP and CH algorithms on a wide range of large-scale real-world models. Computational results show that our method can improve the speed by a factor of 3-10.

Automatic computation of surface correspondence via harmonic map is an active research field in computer vision, computer graphics and computational geometry. It may help document and understand physical and biological phenomena and also has broad applications in biometrics, medical imaging and motion capture industries. Although numerous studies have been devoted to harmonic map research, limited progress has been made to compute a diffeomorphic harmonic map on general topology surfaces with landmark constraints. This work conquers this problem by changing the Riemannian metric on the target surface to a hyperbolic metric so that the harmonic mapping is guaranteed to be a diffeomorphism under landmark constraints. The computational algorithms are based on Ricci flow and nonlinear heat diffusion methods. The approach is general and robust. We employ our algorithm to study the

Detecting deformities on objects is a typical topic in shape analysis, and has much applications such as abnormalities detection in medical imaging (e.g. growth of tumor, spread of cancer). While many algorithms are already well-established in a 2-dimensional case when the object is indeed a surface, a model that still performs well in the general n-dimensional case is still missing. It is our goal in this paper to complete this missing piece, by introducing an indicator in order to effectively distinguish between normal and abnormal deformities. The proposed framework is closely related to the classic 2-dimensional conformal geometry and quasi-conformal geometry. In this work, we model abnormal deformations by anisotropic deformations. Given any two objects of the same dimension (with landmark constraints in between), we define the Anisotropic Indicator, a locally defined real-valued function on the original object, which demonstrates the abnormalities in the deformation between them. Both global and local features about the abnormalities between the two objects can be tracked by analyzing the indicator. We tested the algorithm by detecting deformations on synthetic data and real data, and results show that our algorithm can detect deformations of different types and degrees.

Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others. The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed. The worst-case time complexity of the proposed algorithm is $O((n+m)log n)$, where $n$ is the number of input circles, and $m$ is the number of intersection points among circles. As $m$ can be $O(n^22)$, the presented algorithm is optimal with $O(n^2 log n) $ worst-case time complexity.

Structured light system using a digital video projector is increasingly used for a 3-D shape measurement because of its digital nature. However, the nonlinear gamma of the projector causes the projected fringe patterns to be non-sinusoidal, which results in phase error therefore shape measurement error. Previous work showed that, by using a small look-up-table (LUT), this type of phase error can be reduced significantly for a three-step phase-shifting algorithm. In this research, we prove that this type of phase error compensation method is not limited to a three-step phase-shifting algorithm. It is generic for any phase-shifting algorithm. The phase error compensation algorithm is able to theoretically eliminate the phase error caused by the gamma of the projector completely. It is based on our finding that in phase domain, the phase error due to the projector's gamma is preserved for arbitrary object's surface

We develop a new algorithm to automatically register hippocampal (HP) surfaces with complete geometric matching, avoiding the need to manually label landmark features. A good registration depends on a reasonable choice of shape energy that measures the dissimilarity between surfaces. In our work, we first propose a complete shape index using the Beltrami coefficient and curvatures, which measures subtle local differences. The proposed shape energy is zero if and only if two shapes are identical up to a rigid motion. We then seek the best surface registration by minimizing the shape energy. We propose a simple representation of surface diffeomorphisms using Beltrami coefficients, which simplifies the optimization process. We then iteratively minimize the shape energy using the proposed Beltrami Holomorphic flow (BHF) method. Experimental results on 212 HP of normal and diseased (Alzheimer's disease) subjects show our proposed algorithm is effective in registering HP surfaces with complete geometric matching. The proposed shape energy can also capture local shape differences between HP for disease analysis.

We address the problem of surface inpainting, which aims to fill in holes or missing regions on a Riemann surface based on its surface geometry. In practical situation, surfaces obtained from range scanners often have holes where the 3D models are incomplete. In order to analyze the 3D shapes effectively, restoring the incomplete shape by filling in the surface holes is necessary. In this paper, we propose a novel conformal approach to inpaint surface holes on a Riemann surface based on its surface geometry. The basic idea is to represent the Riemann surface using its conformal factor and mean curvature. According to Riemann surface theory, a Riemann surface can be uniquely determined by its conformal factor and mean curvature up to a rigid motion. Given a Riemann surface S, its mean curvature H and conformal factor λ can be computed easily through its conformal parameterization. Conversely, given λ and H, a Riemann surface can be uniquely reconstructed by solving the Gauss-Codazzi equation on the conformal parameter domain. Hence, the conformal factor and the mean curvature are two geometric quantities fully describing the surface. With this λ-H representation of the surface, the problem of surface inpainting can be reduced to the problem of image inpainting of λ and H on the conformal parameter domain. Once λ and H are inpainted, a Riemann surface can be reconstructed which effectively restores the 3D surface with missing holes. Since the inpainting model is based on the geometric quantities λ and H, the restored surface follows the surface geometric pattern. We test the proposed algorithm on synthetic data as well as real surface data. Experimental results show that our proposed method is an effective surface inpainting algorithm to fill in surface holes on an incomplete 3D models based their surface geometry.

The skeleton of a 2D shape is an important geometric structure in pattern analysis and computer vision. In this paper we study the skeleton of a 2D shape in a two-manifold M, based on a geodesic metric. We present a formal definition of the skeleton S(\Omega) for a shape V in M and show several properties that make S(\Omega) distinct from its Euclidean counterpart in R^2. We further prove that for a shape sequence {\Omega_i} that converge to a shape V in M, the mapping \Omega\rightarrow S(\Omega_i) is lower semi-continuous. A direct application of this result is that we can use a set P of sample points to approximate the boundary of a 2D shape V in M, and the Voronoi diagram of P inside \Omega\subset M gives a good approximation to the skeleton S(\Omega). Examples of skeleton computation in topography and brain morphometry are illustrated.

Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window-VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window-VTP algorithm runs 3-8 times faster than Liu et al.’s method [LCT11], 1.2 times faster than its FWP-MMP variant and more importantly uses 10-70 times less memory than both of them.