Abstract. In this paper, in light of the [Formula: see text]-dimensional Dirichlet energy, we define the [Formula: see text]-dimensional volumetric stretch energies ([Formula: see text]-VSEs) on an [Formula: see text]-dimensional manifold [Formula: see text] for both continuous and discrete cases. The discrete [Formula: see text]-VSE can be represented by a Laplacian matrix with cotangent weights, which involves the previously proposed volumetric stretch energies as special cases with [Formula: see text]. We prove that the [Formula: see text]-VSE functionals have the lower bound [Formula: see text], where [Formula: see text] is the parameterized manifold topologically equivalent to [Formula: see text], and [Formula: see text] and [Formula: see text] are associated measures on [Formula: see text] and [Formula: see text], respectively, and we show that the minimizer of the [Formula: see text]-VSE functional is volume-/mass-preserving if and only if the minimal energy attains [Formula: see text]. We propose an effective [Formula: see text]-VSE minimization ([Formula: see text]-VSEM) algorithm for the computation of volume-/mass-preserving parameterizations between [Formula: see text] and a unit [Formula: see text]-sphere [Formula: see text], as well as an [Formula: see text]-VSEM algorithm for that between [Formula: see text] and a unit [Formula: see text]-ball [Formula: see text], respectively. The [Formula: see text]-VSEM algorithm for [Formula: see text] is divided into a small-scale constrained boundary subproblem solved by the Newton iteration combined with the trust region method, and a large-scale unconstrained interior subproblem solved by fixed-point iteration. The numerical experiments demonstrate the accuracy and the robustness of the proposed algorithms. Furthermore, a modified [Formula: see text]-VSEM algorithm can be applied to manifold registrations and deformations which shows the versatility of [Formula: see text]-VSE.

Abstract. Volumetric stretch energy has been widely applied to the computation of volume-/mass-preserving parameterizations of simply connected tetrahedral mesh models [Formula: see text]. However, this approach still lacks theoretical support. In this paper, we provide a theoretical foundation for volumetric stretch energy minimization (VSEM) to show that a map is a precise volume-/mass-preserving parameterization from [Formula: see text] to a region of a specified shape if and only if its volumetric stretch energy reaches [Formula: see text], where [Formula: see text] is the total mass of [Formula: see text]. We use VSEM to compute an [Formula: see text]-volume-/mass-preserving map [Formula: see text] from [Formula: see text] to a unit ball, where [Formula: see text] is the gap between the energy of [Formula: see text] and [Formula: see text]. In addition, we prove the efficiency of the VSEM algorithm with guaranteed asymptotic R-linear convergence. Furthermore, based on the VSEM algorithm, we propose a projected gradient method for the computation of the [Formula: see text]-volume-/mass-preserving optimal mass transport map with a guaranteed convergence rate of [Formula: see text], and combined with Nesterov-based acceleration, the guaranteed convergence rate becomes [Formula: see text]. Numerical experiments are presented to justify the theoretical convergence behavior for various examples drawn from known benchmark models. Moreover, these numerical experiments show the effectiveness of the proposed algorithm, particularly in the processing of 3D medical MRI brain images.

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 a nontrivial solution, which is a local minimum of the conformal energy with a bijective boundary map. The numerical experiments indicate that the efficiency of the proposed CCEM algorithm is greatly improved and that the accuracy is competitive with that of state-of-the-art algorithms.

Spherical Harmonics (SH) have been proven as a powerful tool for rendering, especially in real-time applications such as Precomputed Radiance Transfer (PRT). Spherical harmonics are orthonormal basis functions and are efficient in computing dot products. However, computations of triple product and multiple product operations are often the bottlenecks that prevent moderately high-frequency use of spherical harmonics. Specifically state-of-the-art methods for accurate SH triple products of order n have a time complexity of O ( n 5 ), which is a heavy burden for most real-time applications. Even worse, a brute-force way to compute k -multiple products would take O ( n 2 k ) time. In this paper, we propose a fast and accurate method for spherical harmonics triple products with the time complexity of only O ( n 3 ), and further extend it for computing k -multiple products with the time complexity of O ( kn 3 + k 2 n 2 log ( kn )). Our key insight is to conduct the triple and multiple products in the Fourier space, in which the multiplications can be performed much more efficiently. To our knowledge, our method is theoretically the fastest for accurate spherical harmonics triple and multiple products. And in practice, we demonstrate the efficiency of our method in rendering applications including mid-frequency relighting and shadow fields.

Parameterizations of manifolds are widely applied to the fields of numerical partial differential equations and computer graphics. To this end, in recent years several efficient and reliable numerical algorithms have been developed by different research groups for the computation of triangular and tetrahedral mesh parameterizations. However, it is still challenging when the topology of manifolds is nontrivial, e.g., the 3-manifold of a topological solid torus. In this paper, we propose a novel volumetric stretch energy minimization algorithm for volume-preserving parameterizations of toroidal polyhedra with a single boundary being mapped to a standard torus. In addition, the algorithm can also be used to compute the equiareal mapping between a genus-one closed surface and the standard torus. Numerical experiments indicate that the developed algorithm is effective and performs well on the bijectivity of the mapping. Applications on manifold registrations and partitions are demonstrated to show the robustness of our algorithms.

Two general challenges faced by data analysis are the existence of noise and the extraction of meaningful information from collected data. In this study, we used a multiscale framework to reduce the effects caused by noise and to extract explainable geometric properties to characterize finite metric spaces. We conducted lab experiments that integrated the use of eye‐tracking, electrodermal activity (EDA), and user logs to explore users' information‐seeking behaviors on search engine result pages (SERPs). Experimental results of 1,590 search queries showed that the proposed strategies effectively predicted query‐level user satisfaction using EDA and eye‐tracking data. The bootstrap analysis showed that combining EDA and eye‐tracking data with user behavior data extracted from user logs led to a significantly better linear model fit than using user behavior data alone. Furthermore, cross‐user and cross‐task validations showed that our methods can be generalized to different search engine users performing different preassigned tasks.

Manifold parameterizations have been applied to various fields of commercial industries. Several efficient algorithms for the computation of triangular surface mesh parameterizations have been proposed in recent years. However, the computation of tetrahedral volumetric mesh parameterizations is more challenging due to the fact that the number of mesh points would become enormously large when the higher-resolution mesh is considered and the bijectivity of parameterizations is more difficult to guarantee. In this paper, we develop a novel volumetric stretch energy minimization algorithm for volume-preserving parameterizations of simply connected $3$-manifolds with a single boundary under the restriction that the boundary is a spherical area-preserving mapping. In addition, our algorithm can also be applied to compute spherical angle- and area-preserving parameterizations of genus-zero closed surfaces, respectively. Several numerical experiments indicate that the developed algorithms are more efficient and reliable compared to other existing algorithms. Numerical results on applications of the manifold partition and the mesh processing for three-dimensional printing are demonstrated thereafter to show the robustness of the proposed algorithm.

We present Write-A-Video , a tool for the creation of video montage using mostly text-editing. Given an input themed text and a related video repository either from online websites or personal albums, the tool allows novice users to generate a video montage much more easily than current video editing tools. The resulting video illustrates the given narrative, provides diverse visual content, and follows cinematographic guidelines. The process involves three simple steps: (1) the user provides input, mostly in the form of editing the text, (2) the tool automatically searches for semantically matching candidate shots from the video repository, and (3) an optimization method assembles the video montage. Visual-semantic matching between segmented text and shots is performed by cascaded keyword matching and visual-semantic embedding, that have better accuracy than alternative solutions. The video assembly is formulated as a hybrid optimization problem over a graph of shots, considering temporal constraints, cinematography metrics such as camera movement and tone, and user-specified cinematography idioms. Using our system, users without video editing experience are able to generate appealing videos.

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 constrained surface registration problem which applies to both computer vision and medical imaging applications. Experimental results demonstrate that, by changing the Riemannian metric, the registrations are always diffeomorphic and achieve relatively high performance when evaluated with some popular surface registration evaluation standards.

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 S(1) 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.

Registration, which aims to find an optimal 1-1 correspondence between shapes, is an important process in different research areas. Landmark-based surface registration has been widely studied to obtain a mapping between shapes that matches important features. Obtaining a unique and bijective surface registration that matches features consistently is generally challenging, especially when a large number of landmark constraints are enforced. This motivates us to search for a unique landmark matching surface diffeomorphism, which minimizes the local geometric distortion. For this purpose, we propose a special class of diffeomorphisms called the Teichmüller mappings (T-Maps). Under suitable conditions on the landmark constraints, a unique T-Map between two surfaces can be obtained, which minimizes the maximal conformality distortion. The conformality distortion measures how far the mapping deviates from a conformal mapping, and hence it measures the local geometric distortion. In this paper, we propose an efficient iterative algorithm, called the quasi-conformal (QC) iteration, to compute the T-Map. The basic idea is to represent the set of diffeomorphisms using Beltrami coefficients (BCs) and look for an optimal BC associated to the desired T-Map. The associated diffeomorphism can be efficiently reconstructed from the optimal BC using the linear Beltrami solver (LBS). Using BCs to represent diffeomorphisms guarantees the diffeomorphic property of the registration, even with very large deformation. Using our proposed method, the T-Map can be accurately and efficiently computed. The obtained registration is guaranteed to be bijective. The proposed algorithm can also be extended to compute T-Map with soft landmark constraints. We applied the proposed algorithm to real applications, such as brain landmark matching registration, constrained texture mapping, and human face registration. Experimental results shows that our method is both effective and efficient in computing a nonoverlap landmark matching registration with the least amount of conformality distortion.

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. 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 conquer 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 the Ricci flow method and the method is general and robust. We apply our algorithm to study constrained human brain surface registration problem. Experimental results demonstrate that, by changing the Riemannian metric, the registrations are always diffeomorphic, and achieve relative high performance when evaluated with some popular cortical surface registration evaluation standards.

This paper introduces an efficient approach to integrating non-local statistics into the higher-order Markov Random Fields (MRFs) framework. Motivated by the observation that many non-local statistics (e.g., shape priors, color distributions) can usually be represented by a small number of parameters, we reformulate the higher-order MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higher-order cliques. The resulting new model, called NC-MRF, not only provides the flexibility in representing the configurations of higher-order cliques, but also automatically decomposes the energy function into less coupled terms, allowing us to design an efficient algorithmic framework for maximum a posteriori (MAP) inference. Based on this novel modeling/ inference framework, we achieve state-of-the-art solutions to the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking, which demonstrate the potential of our approach.

In brain mapping research, parameterized 3-D surface models are of great interest for statistical comparisons of anatomy, surface-based registration, and signal processing. Here, we introduce the theories of continuous and discrete surface Ricci flow, which can create Riemannian metrics on surfaces with arbitrary topologies with user-defined Gaussian curvatures. The resulting conformal parameterizations have no singularities and they are intrinsic and stable. First, we convert a cortical surface model into a multiple boundary surface by cutting along selected anatomical landmark curves. Secondly, we conformally parameterize each cortical surface to a parameter domain with a user-designed Gaussian curvature arrangement. In the parameter domain, a shape index based on conformal invariants is computed, and inter-subject cortical surface matching is performed by solving a constrained harmonic map. We illustrate various target curvature arrangements and demonstrate the stability of the method using longitudinal data. To map statistical differences in cortical morphometry, we studied brain asymmetry in 14 healthy control subjects. We used a manifold version of Hotelling's T(2) test, applied to the Jacobian matrices of the surface parameterizations. A permutation test, along with the cumulative distribution of p-values, were used to estimate the overall statistical significance of differences. The results show our algorithm's power to detect subtle group differences in cortical surfaces.

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 Bel-trami 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 develops a novel computational technique to define and construct powerful manifold splines with only one singular point by employing the rigorous mathematical theory of Ricci flow. The central idea and new computational paradigm of manifold splines are to systematically extend the algorithmic pipeline of spline surface construction from any planar domain to arbitrary topology. As a result, manifold splines can unify planar spline representations as their special cases. Despite their earlier success, the existing manifold spline framework is plagued by the topology-dependent, large number of singular points (i.e., |2g -- 2| for any genus-g surface), where the analysis of surface behaviors such as continuity remains extremely difficult. The unique theoretical contribution of this paper is that we devise new mathematical tools so that manifold splines can now be constructed with only one singular point, reaching their theoretic lower bound of singularity for real-world applications. Our new algorithm is founded upon the concept of discrete Ricci flow and associated techniques. First, Ricci flow is employed to compute a special metric of any manifold domain (serving as a parametric domain for manifold splines), such that the metric becomes flat everywhere except at one point. Then, the metric naturally induces an affine atlas covering the entire manifold except this singular point. Finally, manifold splines are defined over this affine atlas. The Ricci flow method is theoretically sound, and practically simple and efficient. We conduct various shape experiments and our new theoretical and algorithmic results alleviate the modeling difficulty of manifold splines, and hence, promising to promote the widespread use of manifold splines in surface and solid modeling, geometric design, and reverse engineering.

Surface classification is one of the most fundamental problems in geometric modeling. Surfaces can be classified according to their conformal structures. In general, each topological equivalent class has infinite conformally equivalent classes.

No abstract available.

In medical imaging, parameterized 3-D surface models are useful for anatomical modeling and visualization, statistical comparisons of anatomy, and surface-based registration and signal processing. Here we introduce a parameterization method based on Riemann surface structure, which uses a special curvilinear net structure (conformal net) to partition the surface into a set of patches that can each be conformally mapped to a parallelogram. The resulting surface subdivision and the parameterizations of the components are intrinsic and stable (their solutions tend to be smooth functions and the boundary conditions of the Dirichlet problem can be enforced). Conformal parameterization also helps transform partial differential equations (PDEs) that may be defined on 3-D brain surface manifolds to modified PDEs on a two-dimensional parameter domain. Since the Jacobian matrix of a conformal parameterization is diagonal, the modified PDE on the parameter domain is readily solved. To illustrate our techniques, we computed parameterizations for several types of anatomical surfaces in 3-D magnetic resonance imaging scans of the brain, including the cerebral cortex, hippocampi, and lateral ventricles. For surfaces that are topologically homeomorphic to each other and have similar geometrical structures, we show that the parameterization results are consistent and the subdivided surfaces can be matched to each other. Finally, we present an automatic sulcal landmark location algorithm by solving PDEs on cortical surfaces. The landmark detection results are used as constraints for building conformal maps between surfaces that also match explicitly defined landmarks.

We propose a general method that parameterizes general surfaces with complex (possible branching) topology using Riemann surface structure. 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. We can then automatically partition the surface using a critical graph that connects zero points in the global conformal structure on the surface. The trajectories of iso-parametric curves canonically partition a surface into patches. Each of these patches is either a topological disk or a cylinder and can be conformally mapped to a parallelogram by integrating a holomorphic I-form defined on the surface. The resulting surface subdivision and the parameterizations of the components are intrinsic and stable. For surfaces with similar topology and geometry, we show that the parameterization results are consistent and the subdivided surfaces can be matched to each other using constrained harmonic maps. The surface similarity can be measured by direct computation of distance between each pair of corresponding points on two surfaces. To illustrate the technique, we computed conformal structures for anatomical surfaces in MRI scans of the brain and human face surfaces. We found that the resulting parameterizations were consistent across subjects, even for branching structures such as the ventricles, which are otherwise difficult to parameterize. Our method provides a surface-based framework for statistical comparison of surfaces and for generating grids on surfaces for PDE-based signal processing.

All orientable metric surfaces are Riemann surfaces and admit global conformal parameterizations. Riemann surface structure is a fundamental structure and governs many natural physical phenomena, such as heat diffusion and electro-magnetic fields on the surface. A good parameterization is crucial for simulation and visualization. This paper provides an explicit method for finding optimal global conformal parameterizations of arbitrary surfaces. It relies on certain holomorphic differential forms and conformal mappings from differential geometry and Riemann surface theories. Algorithms are developed to modify topology, locate zero points, and determine cohomology types of differential forms. The implementation is based on a finite dimensional optimization method. The optimal parameterization is intrinsic to the geometry, preserves angular structure, and can play an important role in various applications including texture mapping, remeshing, morphing and simulation. The method is demonstrated by visualizing the Riemann surface structure of real surfaces represented as triangle meshes.

We developed a general method for global conformal parameterizations based on the structure of the cohomology group of holomorphic one-forms for surfaces with or without boundaries (Gu and Yau, 2002), (Gu and Yau, 2003). For genus zero surfaces, our algorithm can find a unique mapping between any two genus zero manifolds by minimizing the harmonic energy of the map. In this paper, we apply the algorithm to the cortical surface matching problem. We use a mesh structure to represent the brain surface. Further constraints are added to ensure that the conformal map is unique. Empirical tests on magnetic resonance imaging (MRI) data show that the mappings preserve angular relationships, are stable in MRIs acquired at different times, and are robust to differences in data triangulation, and resolution. Compared with other brain surface conformal mapping algorithms, our algorithm is more stable and has good extensibility.

3D surface classification is a fundamental problem in computer vision and computational geometry. Surfaces can be classified by different transformation groups. Traditional classification methods mainly use topological transformation groups and Euclidean transformation groups. We introduce a novel method to classify surfaces by conformal transformation groups. Conformal equivalent class is refiner than topological equivalent class and coarser than isometric equivalent class, making it suitable for practical classification purposes. For general surfaces, the gradient fields of conformal maps form a vector space, which has a natural structure invariant under conformal transformations. We present an algorithm to compute this conformal structure, which can be represented as matrices, and use it to classify surfaces. The result is intrinsic to the geometry, invariant to triangulation and insensitive to resolution. To the best of our knowledge, this is the first paper to classify surfaces with arbitrary topologies by global conformal invariants. The method introduced here can also be used for surface matching problems.

No abstract available.