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.

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.

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.

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.

A fresh framework for mesh optimization, the Filtered Hooke's Optimization, is proposed. With the notion of the elasticity theory, the Hooke's Optimization is developed by modifying the Hooke's law, in which an elastic force is simulated on the edges of a mesh so that adjacent vertices are either attracted to each other or repelled from each other, so as to regularize the mesh in terms of triangulation. A normal torque force is acted on vertices to guarantee smoothness of the surface. In addition, a filtering scheme, called the Newtonian Filtering, is proposed as a supplementary tool for the proposed Hooke's Optimization to preserve the geometry of the mesh. Numerical simulations on meshes with different geometry indicate an impressive performance of our proposed framework to significantly improve the mesh triangulation without noteworthy distortions of the mesh geometry.

This work proposes a novel framework for optimization in the constrained diffeomorphism space for deformable surface registration. First the diffeomorphism space is modeled as a special complex functional space on the source surface, the Beltrami coefficient space. The physically plausible constraints, in terms of feature landmarks and deformation types, define subspaces in the Beltrami coefficient space. Then the harmonic energy of the registration is minimized in the constrained subspaces. The minimization is achieved by alternating two steps: 1) optimization - diffuse the Beltrami coefficient, and 2) projection - first deform the conformal structure by the current Beltrami coefficient and then compose with a harmonic map from the deformed conformal structure to the target. The registration result is diffeomorphic, satisfies the physical landmark and deformation constraints, and minimizes the conformality distortion. Experiments on human facial surfaces demonstrate the efficiency and efficacy of the proposed registration framework.

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.

We develop a general approach that uses holomorphic 1-forms to parameterize anatomical surfaces with complex (possibly branching) topology. Rather than evolve the surface geometry to a plane or sphere, we instead use the fact that all orientable surfaces are Riemann surfaces and admit conformal structures, which induce special curvilinear coordinate systems on the surfaces. Based on Riemann surface structure, we can then canonically partition the surface into patches. Each of these patches can be conformally mapped to a parallelogram. The resulting surface subdivision and the parameterizations of the components are intrinsic and stable. To illustrate the technique, we computed conformal structures for several types of anatomical surfaces in MRI scans of the brain, including the cortex, hippocampus, and lateral ventricles. We found that the resulting parameterizations were consistent across