Texture mapping and texture synthesis are two popular methods for the decoration of surfaces with visual detail. Here, an existing challenge is to preserve, or at least balance, two competing metrics: scale and angle. In this paper we present two methods for this, both based on global conformal parameterization. First, we describe a texture synthesis algorithm for surfaces with arbitrary topology. By using the conformal parameterization, the 3D surface texture synthesis problem can be converted to a 2D image synthesis problem, which is more intuitive, easier, and conceptually simpler. While the conformality of the parameterization naturally preserves the angles of the texture, in this paper we provide a multi-scale technique to also maintain a more uniform area scaling factor. A second novel contribution is to employ the global parameterization to simultaneously preserve orthogonality and size in texture

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 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.

Registration, which aims to find an optimal one-to-one correspondence between different data, is an important problem in various fields. This problem is especially challenging when large deformations occur. In this paper, we present a novel algorithm to obtain diffeomorphic image or surface registrations with large deformations via quasi-conformal maps. The basic idea is to minimize an energy functional involving a Beltrami coefficient term, which measures the distortion of the quasi-conformal map. The Beltrami coefficient effectively controls the bijectivity and smoothness of the registration, even with very large deformations. Using the proposed algorithm, landmark-based registration between images or surfaces can be effectively computed. The obtained registration is guaranteed to be diffeomorphic (1-1 and onto), even with a large deformation or large number of landmark constraints. The proposed algorithm can also be combined with matching intensity (such as image intensity or surface curvature) to improve the accuracy of the registration. Experiments have been carried out on both synthetic and real data. Results demonstrate the efficacy of the proposed algorithm to obtain diffeomorphic registration between images or surfaces.

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.

We propose a new method to obtain landmark-matching transformations between n-dimensional Euclidean spaces with large deformations. Given a set of feature correspondences, our algorithm searches for an optimal folding-free mapping that satisfies the prescribed landmark constraints. The standard conformality distortion defined for mappings between 2-dimensional spaces is first generalized to the n-dimensional conformality distortion K(f) for a mapping f between n-dimensional Euclidean spaces (n≥3). We then propose a variational model involving K(f) to tackle the landmark-matching problem in higher dimensional spaces. The generalized conformality term K(f) enforces the bijectivity of the optimized mapping and minimizes its local geometric distortions even with large deformations. Another challenge is the high computational cost of the proposed model. To tackle this, we have also proposed a numerical method to solve the optimization problem more efficiently. Alternating direction method with multiplier (ADMM) is applied to split the optimization problem into two subproblems. Preconditioned conjugate gradient method with multi-grid preconditioner is applied to solve one of the sub-problems, while a fixed-point iteration is proposed to solve another subproblem. Experiments have been carried out on both synthetic examples and lung CT images to compute the diffeomorphic landmark-matching transformation with different landmark constraints. Results show the efficacy of our proposed model to obtain a folding-free landmark-matching transformation between n-dimensional spaces with large deformations.

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 paper proposes a novel approach for extracting two intrinsic feature curves on hippocampal (HC) surfaces. The hippocampus is a key target of study in medical imaging, as it degenerates in conditions such as epilepsy and Alzheimer's disease (AD), but its structure is complex. To facilitate HC morphometry, we generate two intrinsic feature curves that describe their global geometries. For example, the separation of them captures thickness changes in HC surfaces, which can be used to effectively measure HC atrophy found in patients with AD. They also separate HC surfaces into upper and lower surface patches where intrinsic shape analysis using conformal modules can be carried out. Based on these curves, we further propose a parameterization of HC surfaces called the eigen-harmonic parameterization (EHP). EHP maps each HC surface onto a parameter domain and imposes longitudinal and azimuthal coordinates on each surface, which follow the gradient and level sets of its first nontrivial Laplace-Beltrami eigenfunction, respectively. Each tubular domain is constructed according to the geometry of an individual HC surface. This gives a parameter domain with much less geometric distortion compared to spherical parameterization. With EHP, all HC surfaces are automatically registered with intrinsic feature curves preserved and geometric distortions minimized. This allows shape analysis on any number of HC surfaces to be performed consistently. We studied geometric changes over time in 138 HC surfaces of patients with AD and normal subjects scanned at two different times. We successfully located areas with significantly different shape changes over time between the two groups.

Surface parameterizations have been widely applied in the computer-aided design for the geometric processing tasks of surface registration, remeshing, texture mapping, and so on. In this paper, we present an efficient balanced energy minimization (BEM) algorithm for the computation of simply connected open surface parameterizations with balanced angle and area distortions. The existence of a nontrivial accumulation function of the BEM algorithm is guaranteed under some mild conditions and the limiting function is shown to be one-to-one. Comparisons of the BEM algorithm with the angle- and the area-preserving parameterizations show that the angular distortion is close to that of the angle-preserving parameterization while the area distortion is significantly improved. An application of the BEM on the Chinese virtual broadcasting technique is demonstrated thereafter, which is consisted of surface remeshing, registration, and morphing.

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

We propose a method to map a multiply connected bounded planar region conformally to a bounded region with circular boundaries. The norm of the derivative of such a conformal map satisfies the Laplace equation with a nonlinear Neumann type boundary condition. We analyze the singular behavior at corners of the boundary and separate the major singular part. The remaining smooth part solves a variational problem which is easy to discretize. We use a finite element method and a gradient descent method to find an approximate solution. The conformal map is then constructed from this norm function. We tested our algorithm on a polygonal region and a curvilinear smooth region.

Adolescent Idiopathic Scoliosis (AIS) characterized by the 3D spine deformity affects about 4% schoolchildren worldwide. Several studies have demonstrated the malfunctioning of postural balance, proprioception, and equilibrium control in patients with AIS. Since these functions are closely related to structures in and around the brainstem, the morphometry of the brainstem surface is of utmost importance. In this paper, we propose an effective method to accurately compute the registration between brainstem surfaces. Four consistent features, which describe the global geometry of the brainstem, are automatically extracted to guide the surface registration. Using the discrete Ricci flow method, brainstem surfaces are parameterized conformally onto the quadrilaterally-faced hexahedron, through which the brainstem registration can be obtained. Our registration algorithm can guarantee the exact landmark correspondence between brainstem surfaces. With the obtained registration, a shape energy can be defined to measure the local shape difference between different brainstem surfaces. We have tested our algorithms on 30 real brainstem surfaces extracted from MRIs of 15 normal subjects and 15 AIS patients. Experimental results show the efficacy of the proposed algorithm to register brainstem surfaces, which matches landmark features consistently. The computed registration can be used for the morphometry of brainstems.

This paper describes a high-resolution, real-time, three-dimensional shape measurement system using the modified two-plus-one phase-shifting algorithm. The data acquisition speed is as high as 60 frames/s with an image resolution of 640480 pixels per frame. Experiments demonstrated that the system was able to acquire the dynamic changing objects such as facial geometric shape changes when the subject is speaking, and the modified two-plus-one phase-shifting algorithm can further alleviate the error due to motion. Applications of this system include manufacturing, online inspection, medical imaging, compute vision, and computer graphics.

We study the combinatorial complexity of Voronoi diagram of point sites on a general triangulated 2-manifold surface, based on the geodesic metric. Given a triangulated 2- manifold T of n faces and a set of m point sites S = {s1, s2, . . . , sm} ∈ T, we prove that the complexity of Voronoi diagram VT (S) of S on T is O(mn) if the genus of T is zero. For a genus-g manifold T in which the samples in S are dense enough and the resulting Voronoi diagram satisfies the closed ball property, we prove that the complexity of Voronoi diagram VT (S) is O((m + g)n).

This paper describes a Graphics Processing Unit (GPU)-assisted real-time three-dimensional shape measurement system. Our experiments demonstrated that the absolute coordinates calculation and rendering speed of a GPU is more than four times faster than that of a dual CPU workstation with the same graphics card. By implementing the GPU into our system, we realized simultaneous absolute coordinate acquisition, reconstruction and display at 30 frames per second with a resolution of approximately 266K points per frame. Moreover, a 2+1 phase-shifting algorithm was employed to alleviate the measurement error caused by motion. Applications of the system include medical imaging, manufacturing, entertainment, and security.

Surface registration, which transforms different sets of surface data into one common reference space, is an important process which allows us to compare or integrate the surface data effectively. If a nonrigid transformation is required, surface registration is commonly done by parameterizing the surfaces onto a simple parameter domain, such as the unit square or sphere. In this work, we are interested in looking for meaningful registrations between surfaces through parameterizations, using prior features in the form of landmark curves on the surfaces. In particular, we generate optimized conformal parameterizations which match landmark curves exactly with shape-based correspondences between them. We propose a variational method to minimize a compound energy functional that measures the harmonic energy of the parameterization maps and the shape dissimilarity between mapped points on the landmark curves. The novelty is that the computed maps are guaranteed to align the landmark features consistently and give a shape-based diffeomorphism between the landmark curves. We achieve this by intrinsically modeling our search space of maps as flows of smooth vector fields that do not flow across the landmark curves. By using the local surface geometry on the curves to define a shape measure, we compute registrations that ensure consistent correspondences between anatomical features. We test our algorithm on synthetic surface data. An application of our model to medical imaging research is shown, using experiments on brain cortical surfaces, with anatomical (sulcal) landmarks delineated, which show that our computed maps give a shape-based alignment of the sulcal curves without significantly impairing conformality. This ensures correct averaging and comparison of data across subjects.

This paper proposes a novel algorithm to extract feature landmarks on the vestibular system (VS), for the analysis of Adolescent Idiopathic Scoliosis (AIS) disease. AIS is a 3-D spinal deformity commonly occurred in adolescent girls with unclear etiology. One popular hypothesis was suggested to be the structural changes in the VS that induce the disturbed balance perception, and further cause the spinal deformity. The morphometry of VS to study the geometric differences between the healthy and AIS groups is of utmost importance. However, the VS is a genus-3 structure situated in the inner ear. The high-genus topology of the surface poses great challenge for shape analysis. In this work, we present a new method to compute exact geodesic loops on the VS. The resultant geodesic loops are in Euclidean metric, thus characterizing the intrinsic geometric properties of the VS based on the real background geometry. This leads to more accurate results than existing methods, such as the hyperbolic Ricci flow method. Furthermore, our method is fully automatic and highly efficient, e.g., one order of magnitude faster than. We applied our algorithm to the VS of normal and AIS subjects. The promising experimental results demonstrate the efficacy of our method and reveal more statistically significant shape difference in the VS between right-thoracic AIS and normal subjects.

Surface parameterizations have been widely used in computer graphics and geometry processing. In particular, as simply-connected open surfaces are conformally equivalent to the unit disk, it is desirable to compute the disk conformal parameterizations of the surfaces. In this paper, we propose a novel algorithm for the conformal parameterization of a simply-connected open surface onto the unit disk, which significantly speeds up the computation, enhances the conformality and stability, and guarantees the bijectivity. The conformality distortions at the inner region and on the boundary are corrected by two steps, with the aid of an iterative scheme using quasi-conformal theories. Experimental results demonstrate the effectiveness of our proposed method.

In this paper, we investigate how to topologically and geometrically characterize the intersection relations between a movable convex polygon and a set  of possibly overlapping polygons fixed in the plane. More specifically, a subset   is called an intersection relation if there exists a placement of that intersects, and only intersects, . The objective of this paper is to design an efficient algorithm that finds a finite and discrete representation of all of the intersection relations between and . Past related research only focuses on the complexity of the free space of the configuration space between and  and how to move or place an object in this free space. However, there are many applications that require the knowledge of not only the free space, but also the intersection relations. Examples are presented to demonstrate the rich applications of the formulated problem on intersection relations.

Point cloud is the most fundamental representation of 3D geometric objects as it provides the most exact information of them. Analyzing and processing point cloud surfaces is important in computer graphics and computer vision. However, most of the existing algorithms for surface analysis require connectivity information. Therefore, it is desirable to develop a mesh structure on point clouds. This task can be simplified with the aid of a parameterization. In particular, conformal parameterizations are advantageous in preserving the geometric information of the point cloud data. In this paper, we extend a state-of-the-art spherical conformal parameterization algorithm for genus-0 closed meshes to the case of point clouds, using an improved approximation of the Laplace-Beltrami operator on data points. Then, we propose an iterative scheme called the North-South reiteration for achieving a spherical conformal parameterization. A balancing scheme is introduced to enhance the distribution of the spherical parameterization. High quality triangulations and quadrangulations can then be built on the point clouds with the aid of the parameterizations. Also, the meshes generated are guaranteed to be genus-0 closed meshes. Moreover, using our proposed spherical conformal parameterization, multilevel representations of point clouds can be easily constructed. Experimental results demonstrate the effectiveness of our proposed framework.

In shape analysis, finding an optimal 1-1 correspondence between 3D surfaces within a large class of admissible bijective mappings is of great importance. Such a process is called surface registration. The difficulty lies in the fact that the space of all surface diffeomorphisms is a complicated functional space, making it challenging to exhaustively search for the best mapping. To tackle this problem, we propose a simple representation of bijective surface maps using Beltrami coefficients (BCs)—complex-valued functions defined on surfaces with supremum 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 BCs. Hence, every bijective surface map may be represented by a unique BC. Conversely, given a BC, we can reconstruct the unique surface map associated with it using the Beltrami Holomorphic flow (BHF) method. Using BCs to represent surface maps is advantageous because it is a much simpler functional space, which captures many essential features of a surface map. By adjusting BCs, we equivalently adjust surface diffeomorphisms to obtain the optimal map with desired properties. More specifically, BHF gives us the variation of the associated map under the variation of BC. Using this, a variational problem over the space of surface diffeomorphisms can be easily reformulated into a variational problem over the space of BCs. This makes the minimization procedure much easier. More importantly, the diffeomorphic property is always preserved. We test our method on synthetic examples and real medical applications. Experimental results demonstrate the effectiveness of our proposed algorithm for surface registration.

In this paper we show that stability for holomorphic vector bundles are equivalent to the existence of solutions to certain system of Monge Ampere equations parametrized by a parameter k. We solve this fully nonlinear elliptic system by singular perturbation technique and show that the vanishing of obstructions for the perturbation is given precisely by the stability condition. This can be interpreted as an infinite dimensional analog of the equivalencybetween Geometric Invariant Theory and Symplectic Reduction for moduli space of vector bundles.

There is an unmet medical need to identify neuroimaging biomarkers that allow us to accurately diagnose and monitor Alzheimer's disease (AD) at its very early stages and to assess the response to AD-modifying therapies. To a certain extent, volumetric and functional magnetic resonance imaging (fMRI) studies can detect changes in structure, cerebral blood flow, and blood oxygenation that distinguish AD and mild cognitive impairment (MCI) subjects from healthy control (HC) subjects. However, it has been challenging to use fully automated MRI analytic methods to identify potential AD neuroimaging biomarkers. We have thus proposed a method based on independent component analysis (ICA) for studying potential AD-related MR image features that can be coupled with the use of support vector machine (SVM) for classifying scans into categories of AD, MCI, and HC subjects. The MRI data were selected from

Superpixels are perceptually meaningful atomic regions that can effectively capture image features. Among various methods for computing uniform superpixels, simple linear iterative clustering (SLIC) is popular due to its simplicity and high performance. In this paper, we extend SLIC to compute content-sensitive superpixels, i.e., small superpixels in content-dense regions with high intensity or colour variation and large superpixels in content-sparse regions. Rather than using the conventional SLIC method that clusters pixels in R^5, we map the input image I to a 2-dimensional manifoldMR5, whose area elements are a good measure of the content density in I. We propose a simple method, called intrinsic manifold SLIC (IMSLIC), for computing a geodesic centroidal Voronoi tessellation (GCVT)—a uniform tessellation—onM, which induces the content-sensitive superpixels in I. In contrast to the existing algorithms, IMSLIC characterizes the content sensitivity by measuring areas of Voronoi cells onM. Using a simple and fast approximation to a closed-form solution, the method can compute the GCVT at a very low cost and guarantees that all Voronoi cells are simply connected. We thoroughly evaluate IMSLIC and compare it with eleven representative methods on the BSDS500 dataset and seven representative methods on the NYUV2 dataset. Computational results show that IMSLIC outperforms existing methods in terms of commonly used quality measures pertaining to superpixels such as compactness, adherence to boundaries, and achievable segmentation accuracy. We also evaluate IMSLIC and seven representative methods in an image contour closure application, and the results on two datasets, WHD and WSD, show that IMSLIC achieves the best foreground segmentation performance.

Delaunay meshes (DM) are a special type of manifold triangle meshes --- where the local Delaunay condition holds everywhere --- and find important applications in digital geometry processing. This paper addresses the \yongjin{general} DM simplification problem: given an arbitrary manifold triangle mesh M with n vertices and the user-specified resolution m(< n), compute a Delaunay mesh M* with m vertices that has the least Hausdorff distance to M. To solve the problem, we abstract the simplification process using a 2D Cartesian grid model, in which each grid point corresponds to triangle meshes with a certain number of vertices and a simplification process is a monotonic path on the grid. We develop a novel differential-evolution-based method to compute a low-cost path, which leads to a high quality Delaunay mesh. Extensive evaluation shows that our method consistently outperforms the existing methods in terms of approximation error. In particular, our method is highly effective for small-scale CAD models and man-made objects with sharp features but less details. Moreover, our method is fully automatic and can preserve sharp features well and deal with models with multiple components, whereas the existing methods often fail.