A numerical method for computing the extremal Teichmüller map between multiply-connected domains is presented. Given two multiply-connected domains, there exists a unique Teichmüller map (T-Map) between them minimizing the conformality distortion. The extremal T-Map can be considered as the ‘most conformal’ map between multiply-connected domains. In this paper, we propose an iterative algorithm to compute the extremal T-Map using the Beltrami holomorphic flow (BHF). The BHF procedure iteratively adjusts the initial map based on a sequence of Beltrami coefficients, which are complex-valued functions defined on the source domain. It produces a sequence of quasi-conformal maps, which converges to the T-Map minimizing the conformality distortion. We test our method on synthetic data together with real human face data. Results show that our algorithm computes the extremal T-Map between two multiply-connected domains of the same topology accurately and efficiently.

In the past decades, many methods for computing conformal mesh parameterizations have been developed in response to demand of numerous applications in the field of geometry processing. Spectral conformal parameterization (SCP) (Mullen et al. in Proceedings of the symposium on geometry processing, SGP ’08. Eurographics Association, Aire-la-Ville, Switzerland, pp 1487–1494, 2008) is one of these methods used to compute a quality conformal parameterization based on the spectral techniques. SCP focuses on a generalized eigenvalue problem (GEP) $L_{C} \bf{f} = \lambda B \bf{f}$ whose eigenvector(s) associated with the smallest positive eigenvalue(s) provide the conformal parameterization result. This paper is devoted to studying a novel eigensolver for this GEP. Based on structures of the matrix pair $(L_{C}, B)$, we show that this GEP can be transformed into a small-scale compressed and deflated standard eigenvalue problem with a symmetric positive definite skew-Hamiltonian operator. We then propose a symmetric skew-Hamiltonian isotropic Lanczos algorithm (SHILA) to solve the reduced problem. Numerical experiments show that our compressed deflating technique can exclude the impact of convergence from the kernel of $L_{C}$ and transform the original problem to a more robust system. The novel SHILA method can effectively avoid the disturbance of duplicate eigenvalues. As a result, based on the spectral model of SCP, our numerical eigensolver can compute the conformal parameterization accurately and efficiently.

This paper is motivated by the problem of subdividing a prismatic mesh to a tetrahedral mesh (without inserting Steiner points) so as to not only match arbitrarily prescribed boundary conditions but also allow arbitrary topologies in the base mesh. We explore all possible combinations of these two factors, and propose a complete solution to this 3D problem by converting it to an equivalent 2D graph problem, called cutting flow problem. For each case, we not only prove the sufficient and necessary condition for the existence of solutions, but also provide linear and provable algorithms to compute a solution whenever there is one.

No abstract uploaded!

Surface conformal parameterizations have been widely applied to various tasks in computer graphics. In this paper, we develop a convergent conformal energy minimization (CCEM) iterative algorithm via the line-search gradient descent method with a quadratic approximation for the computation of disk-shaped conformal parameterizations of simply connected open triangular meshes. In addition, we prove the global convergence of the proposed CCEM iterative algorithm. Moreover, under some mild assumptions, we prove the existence of the nontrivial solution, which is a local minimum of the conformal energy with a bijective boundary map. Numerical experiments indicate that the efficiency of the proposed CCEM algorithm is highly improved and the accuracy is competitive with that of state-of-the-art algorithms.

Morphing is the process of changing a geometric model or an image into another. The process generally involves rigid body motions and non-rigid deformations. It is well known that there exists a unique conformal mapping from a simply connected surface into a unit disk by the Riemann mapping theorem. On the other hand, a 3D surface deformable model can be built via various approaches such as mutual parameterization from direct interpolation or surface matching using landmarks. In this paper, a numerical methods of 3D surface morphing based on deformable model and conformal mapping is demonstrated. We take the advantage of the unique representation of 3D surfaces by the mean curvatures $H$ and the conformal factors $\lambda$ associated with the Riemann mapping and build up the deformation model by consistently registering the landmarks on the conformal parametric domains. As a result, the correspondence of the $(H, \lambda)$ between two surfaces can be defined and a 3D deformation field can be reconstructed. Furthermore, by composition of the M\"obius transformation and the 3D deformation field, a smooth morphing sequence can be generated over a consistent mesh structure via the cubic spline homotopy. Several numerical experiments on the face morphing are presented to demonstrate the robustness of our approach.

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.

This paper presents a method of obtaining geometric registrations between high-genus (g≥1) surfaces. Surface registration between simple surfaces, such as simply connected open surfaces, has been well studied. However, very few works have been carried out for the registration of high-genus surfaces. The high-genus topology of the surface poses a great challenge for surface registration. A possible approach is to partition surfaces into simply connected patches and registration can be done in a patch-by-patch manner. Consistent cuts are required, which are usually difficult to obtain and prone to error. In this work, we propose an effective way to obtain geometric registration between high-genus surfaces without introducing consistent cuts. The key idea is to conformally parameterize the surface into its universal covering space, which is either the Euclidean plane or the hyperbolic disk embedded in R2. Registration can then be done on the universal covering space by iteratively minimizing a shape mismatching energy measuring the geometric dissimilarity between the two surfaces. The Beltrami coefficient of the mapping is considered and adjusted in order to control the bijectivity of the mappings in each iteration. Our proposed algorithm effectively computes a smooth registration between high-genus surfaces that matches geometric information as much as possible. The algorithm can also be applied to find a smooth registration minimizing any general energy functionals. Numerical experiments on high-genus surface data show that our proposed method is effective for registering high-genus surfaces with geometric matching. We also applied the method to register anatomical structures for medical imaging, which demonstrates the usefulness of the proposed algorithm.

Planar polynomial curves have rational offset curves, if they are either Pythagorean-hodograph (PH) or indirect Pythagorean-hodograph (iPH) curves. In this paper, we derive an algebraic and two geometric characterizations for planar quartic iPH curves. The characterizations are given in terms of quantities related to the Bézier control polygon of the curve, and naturally extend to quartic and cubic PH and quadratic iPH curves.

Shape analysis is a central problem in the field of computer vision. In 2D shape analysis, classification and recognition of objects from their observed silhouettes are extremely crucial but difficult. It usually involves an efficient representation of 2D shape space with a metric, so that its mathematical structure can be used for further analysis. Although the study of 2D simply-connected shapes has been subject to a corpus of literatures, the analysis of multiply-connected shapes is comparatively less studied. In this work, we propose a representation for general 2D multiply-connected domains with arbitrary topologies using conformal welding. A metric can be defined on the proposed representation space, which gives a metric to measure dissimilarities between objects. The main idea is to map the exterior and interior of the domain conformally to unit disks and circle domains (unit disk with several inner disks removed), using holomorphic 1-forms. A set of diffeomorphisms of the unit circle S1 can be obtained, which together with the conformal modules are used to define the shape signature. A shape distance between shape signatures can be defined to measure dissimilarities between shapes. We prove theoretically that the proposed shape signature uniquely determines the multiply-connected objects under suitable normalization. We also introduce a reconstruction algorithm to obtain shapes from their signatures. This completes our framework and allows us to move back and forth between shapes and signatures. With that, a morphing algorithm between shapes can be developed through the interpolation of the Beltrami coefficients associated with the signatures. Experiments have been carried out on shapes extracted from real images. Results demonstrate the efficacy of our proposed algorithm as a stable shape representation scheme.