Surface registration is widely used in machine vision and medical imaging, where 1-1 correspondences between surfaces are computed to study their variations. Surface maps are usually stored as the 3D coordinates each vertex is mapped to, which often requires lots of storage memory. This causes inconvenience in data transmission and data storage, especially when a large set of surfaces are analyzed. To tackle this problem, we propose a novel representation of surface diffeomorphisms using Beltrami coefficients, which are complex-valued functions defined on surfaces with supreme norm less than 1. Fixing any 3 points on a pair of surfaces, there is a 1-1 correspondence between the set of surface diffeomorphisms between them and the set of Beltrami coefficients on the source domain. Hence, every bijective surface map can be represented by a unique Beltrami coefficient. Conversely, given a Beltrami coefficient, we can reconstruct the unique surface map associated to it using the Beltrami Holomorphic flow (BHF) method introduced in this paper. Using this representation, 1/3 of the storage space is saved. We can further reduce the storage requirement by 90% by compressing the Beltrami coefficients using Fourier approximations. We test our algorithm on synthetic data, real human brain and hippocampal surfaces. Our results show high accuracy in the reconstructed data, while the amount of storage is greatly reduced. Our approach is compared with the Fourier compression of the coordinate functions using the same amount of data. The latter approach often shows jaggy results and cannot guarantee to preserve diffeomorphisms.

The analysis of the vestibular system (VS) is an important research topic in medical image analysis. VS is a sensory structure in the inner ear for the perception of spatial orientation. It is believed several diseases, such as the Adolescent Idiopathic Scoliosis (AIS), are due to the impairment of the VS function. The morphology of the VS is thus of great research significance. A major challenge is that the VS is a genus-3 surface. The high-genus topology of the VS poses great challenges to find accurate pointwise correspondences between the surfaces and whereby perform accurate shape analysis. In this paper, we present a method to obtain the landmark constrained diffeomorphic registration between the VS surfaces based on the quasi-conformal theory. Given a set of corresponding landmarks on the VS surfaces, a diffeomorphism between the VS surfaces that matches the features consistently can be obtained. The basic idea is to iteratively search for an admissible Beltrami coefficient, which is associated to our desired landmark matching registration. With the obtained surface registrations, vertex-wise morphometric analysis can be carried out. Two types of geometric features are used for shape comparison. One is the collection of homotopic loops on each canals of the VS, which can be used to measure the local thickness of the canals. From the homotopic loops, centerlines can be extracted. By examining the deviations of the centerlines from the best fit planes, bendings of the canals can be detected. The second geometric feature is the minimal surface enclosed by the homotopic loop. From the minimal surfaces of each homotopic loops, cross-sectional area of the canals can be evaluated. To study the local shape difference more comprehensively, a complete shape index, which is defined using the Beltrami coefficients and surface curvatures, is used. We test proposed registration method on 15 VS of normal control subjects and 12 VS of patients suffering from AIS. Experimental results show the efficacy and accuracy of the proposed algorithm to compute the VS surface registration. Shape analysis has also been carried out using the proposed geometric features and shape index, which reveals shape differences in the posterior canal between normal and diseased AIS groups.

This paper presents a novel algorithm to obtain landmark-based genus-1 surface registration via a special class of quasi-conformal maps called the Teichmüller maps. Registering shapes with important features is an important process in medical imaging. However, it is challenging to obtain a unique and bijective genus-1 surface matching that satisfies the prescribed landmark constraints. In addition, as suggested by [11], conformal transformation provides the most natural way to describe the deformation or growth of anatomical structures. This motivates us to look for the unique mapping between genus-1 surfaces that matches the features while minimizing the maximal conformality distortion. Existence and uniqueness of such optimal diffeomorphism is theoretically guaranteed and is called the Teichmüller extremal mapping. In this work, we propose an iterative algorithm, called the Quasi-conformal (QC) iteration, to find the Teichmüller extremal mapping between the covering spaces of genus-1 surfaces. By representing the set of diffeomorphisms using Beltrami coefficients (BCs), we look for an optimal BC which corresponds to our desired diffeomorphism that matches prescribed features and satisfies the periodic boundary condition on the covering space. Numerical experiments show that our proposed algorithm is efficient and stable for registering genus-1 surfaces even with large amount of landmarks. We have also applied the algorithm on registering vertebral bones with prescribed feature curves, which demonstrates the usefulness of the proposed algorithm.

This paper studies the Voronoi diagrams on 2-manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point-source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line-segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n-face mesh with m generators, where N = max{m,n}. Computational results on real-world models demonstrate the efficiency of our algorithm.

In this paper, we propose novel algorithms for inpainting and refinement of diffeomorphisms. We first represent a diffeomorphism by its Beltrami coefficient. Then it is possible to refine and inpaint the diffeomorphism by processing this Beltrami coefficient. With the inpainted/refined Beltrami coefficient, we construct a new diffeomorphism using the exact Beltrami holomorphic flow algorithm proposed in this paper. We apply our algorithms on several practical applications, which include the inpainting of a highly distorted diffeomorphism, the inpainting of image sequences of deforming shapes, the super-resolution of diffeomorphisms and the global parameterization of cortical surfaces by combining local parameterizations. Experiments show that our algorithm can solve these problems with natural and smooth results. We demonstrate how our proposed method can be widely applied in areas from texture mapping to video processing, and from computer graphics to medical imaging.

A natural metric in 2-manifold surfaces is to use geodesic distance. If a 2-manifold surface is represented by a triangle mesh T , the geodesic metric on T can be computed exactly using computational geometry methods. Previous work for establishing the geodesic metric on T only supports using half-edge data structures; i.e., each edge e in T is split into two halves (he1, he2) and each half-edge corresponds to one of two faces incident to e. In this paper, we prove that the exact-geodesic structures on two halfedges of e can be merged into one structure associated with e. Four merits are achieved based on the properties which are studied in this paper: (1) Existing CAD systems that use edge-based data structures can directly add the geodesic distance function without changing the kernel to a half-edge data structure; (2) To find the geodesic path from inquiry points to the source, the MMP algorithm can be run in an onthe- fly fashion such that the inquiry points are covered by correct wedges; (3) The MMP algorithm is sped up by pruning unnecessary wedges during the wedge propagation process; (4) The storage of the MMP algorithm is reduced since fewer wedges need to be stored in an edge-based data structure. Experimental results show that when compared to the classic half-edge data structure, the edge-based implementation of the MMP algorithm reduces running time by 44% and storage by 29% on average.

Alzheimer's disease (AD) is a no-cure disease that has been frustrating the scientists for many years. Analyzing the disease has become an important but challenging research topic. The shape analysis of the sub-cortical structure of AD patients has been commonly used to understand this disease. In this paper, we assess the feasibility of using shape information on the hippocampal (HP) surfaces to detect some sub-structural changes in AD patients. We propose a quasi-conformal statistical shape analysis model, which allows us to study local regional geometric changes in the HPs amongst normal control (NC) and AD groups. A shape index defined by the quasi-conformality and surface curvatures is used to characterize region-specific shape variations of the HP surfaces. Feature vectors can be extracted for each HPs, with which a classification model can be built using machine learning methods to classify HPs into NC and AD subjects. Experiments have been carried out on 99 normal controls and 41 patients with AD. Results demonstrate that the proposed quasi-conformal based model is effective for classifying HPs into NC and AD groups with high classification accuracy (with highest overall classification accuracy reaching 87.86% in a leave-one-out experiment using the whole dataset).

We propose a novel framework for reconstructing lightweight polygonal surfaces from point clouds. Unlike traditional methods that focus on either extracting good geometric primitives or obtaining proper arrangements of primitives, the emphasis of this work lies in intersecting the primitives (planes only) and seeking for an appropriate combination of them to obtain a manifold polygonal surface model without boundary. We show that reconstruction from point clouds can be cast as a binary labeling problem. Our method is based on a hypothesizing and selection strategy. We first generate a reasonably large set of face candidates by intersecting the extracted planar primitives. Then an optimal subset of the candidate faces is selected through optimization. Our optimization is based on a binary linear programming formulation under hard constraints that enforce the final polygonal surface model to be manifold and watertight. Experiments on point clouds from various sources demonstrate that our method can generate lightweight polygonal surface models of arbitrary piecewise planar objects. Besides, our method is capable of recovering sharp features and is robust to noise, outliers, and missing data.

We address the problem of detecting deformities on elastic surfaces. This is of great importance for shape analysis, with applications such as detecting abnormalities in biological shapes (e.g., brain structures). We propose an effective algorithm to detect abnormal deformations by generating quasi-conformal maps between the original and deformed surfaces. We firstly flatten the 3D surfaces conformally onto 2D rectangles using the discrete Yamabe flow and use them to compute a quasi-conformal map that matches internal features lying within the surfaces. The deformities on the elastic surface are formulated as non-conformal deformations, whereas normal deformations that preserve local geometry are formulated as conformal deformations. We then detect abnormalities by computing the Beltrami coefficient associated uniquely with the quasi-conformal map. The Beltrami coefficient is a complex-valued function defined on the surface. It describes the deviation of the deformation from conformality at each point. By considering the norm of the Beltrami coefficient, we can effectively segment the regions of abnormal changes, which are invariant under normal (non-rigid) deformations that preserve local geometry. Furthermore, by considering the argument of the Beltrami coefficient, we can capture abnormalities induced by local rotational changes. We tested the algorithm by detecting abnormalities on synthetic surfaces, 3D human face data and MRI-derived brain surfaces. Experimental results show that our algorithm can effectively detect abnormalities and capture local rotational alterations. Our method is also more effective than other existing methods, such as the isometric indicator, for locating abnormalities.

In this work, we introduce two sets of algorithms inspired by the ideas from modern geometry. One is computational conformal geometry method, including harmonic maps, holomorphic 1-forms and Ricci flow. The other one is optimization method using affine normals.