This work introduces a rigorous and practical approach for automatic N-RoSy field design on arbitrary surfaces with user defined field topologies. The user has full control of the number, positions and indices of the singularities, the turning numbers of the loops, and is able to edit the field interactively. We formulate N-RoSy field construction as designing a Riemannian metric, such that the holonomy along any loop is compatible with the local symmetry of N-RoSy fields. We prove the compatibility condition using discrete parallel transport. The complexity of N-RoSy field design is caused by curvatures. In our work, we propose to simplify the Riemannian metric to make it flat almost everywhere. This approach greatly simplifies the process and improves the flexibility, such that, it can design N-RoSy fields with single singularity, and mixed-RoSy fields. To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sketching and geometry remeshing.

In this paper, we introduce a novel method that can generate a sequence of physical transformations between 3D models with different shape and topology. Feasible transformations are realized on a chain structure with connected components that are 3D printed. Collision-free motions are computed to transform between different configurations of the 3D printed chain structure. To realize the transformation between different 3D models, we first voxelize these input models into similar number of voxels. The challenging part of our approach is to generate a simple path --- as a chain configuration to connect most voxels. A layer-based algorithm is developed with theoretical guarantee of the existence and the path length. We find that collision-free motion sequence can always be generated when using a straight line as the intermediate configuration of transformation. The effectiveness of our method is demonstrated by both the simulation and the experimental tests taken on 3D printed chains.

Delaunay meshes (DM) are a special type of triangle mesh where the local Delaunay condition holds everywhere. We present an efficient algorithm to convert an arbitrary manifold triangle mesh M into a Delaunay mesh. We show that the constructed DM has O(Kn) vertices, where n is the number of vertices in M and K is a model-dependent constant. We also develop a novel algorithm to simplify Delaunay meshes, allowing a smooth choice of detail levels. Our methods are conceptually simple, theoretically sound and easy to implement. The DM construction algorithm also scales well due to its O(nK logK) time complexity. Delaunay meshes have many favorable geometric and numerical properties. For example, a DM has exactly the same geometry as the input mesh, and it can be encoded by any mesh data structure. Moreover, the empty geodesic circumcircle property implies that the commonly used cotangent Laplace-Beltrami operator has non-negative weights. Therefore, the existing digital geometry processing algorithms can benefit the numerical stability of DM without changing any codes. We observe that DMs can improve the accuracy of the heat method for computing geodesic distances. Also, popular parameterization techniques, such as discrete harmonic mapping, produce more stable results on the DMs than on the input meshes.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

A time domain blind source separation algorithm of convolutive sound mixtures is studied based on a compact partial inversion formula in closed form. An L1-constrained minimization problem is formulated to find demixing filter coefficients for source separation while capturing scaling invariance and sparseness of solutions. The minimization aims to reduce (lagged) cross correlations of the mixture signals, which are modeled stochastically. The problem is non-convex, however it is put in a nonlinear least squares form where the robust and convergent Levenberg-Marquardt iterative method is applicable to compute local minimizers. Efficiency is achieved in recovering lower dimensional demixing filter solutions than the physical ones. Computations on recorded and synthetic mixtures show satisfactory performance, and are compared with other iterative methods.

Mesh parameterization is a fundamental technique in computer graphics. The major goals during mesh parameterization are to minimize both the angle distortion and the area distortion. Angle distortion can be eliminated by the use of conformal mapping, in principle. Our paper focuses on solving the problem of finding the best discrete conformal mapping that also minimizes area distortion. First, we deduce an exact analytical differential formula to represent area distortion by curvature change in the discrete conformal mapping, giving a dynamic Poisson equation. On a mesh, the vertex curvature is related to edge lengths by the curvature map. Our result shows the map is invertible, i.e., the edge lengths can be computed from the curvature (by integration). Furthermore, we give the explicit Jacobi matrix of the inverse curvature map. Second, we formulate the task of computing conformal parameterizations with least area distortions as a constrained nonlinear optimization problem in curvature space. We deduce explicit conditions for the optima. Third, we give an energy form to measure the area distortions, and show that it has a unique global minimum. We use this to design an efficient algorithm, called free boundary curvature diffusion, which is guaranteed to converge to the global minimum; it has a natural physical interpretation. This result proves the common belief that optimal parameterization with least area distortion has a unique solution and can be achieved by free boundary conformal mapping. Major theoretical results and practical algorithms are presented for optimal parameterization based on the inverse curvature map. Comparisons are conducted with existing methods and using different energies. Novel parameterization applications are also introduced. The theoretical framework of the inverse curvature map can be applied to further study discrete conformal mappings.

Harmonic functions are the critical points of a Dirichlet energy functional, the linear projections of conformal maps. They play an important role in computer graphics, particularly for gradient-domain image processing and shape-preserving geometric computation. We propose Poisson coordinates, a novel transfinite interpolation scheme based on the Poisson integral formula, as a rapid way to estimate a harmonic function on a certain domain with desired boundary values. Poisson coordinates are an extension of the Mean Value coordinates (MVCs) which inherit their linear precision, smoothness, and kernel positivity. We give explicit formulae for Poisson coordinates in both continuous and 2D discrete forms. Superior to MVCs, Poisson coordinates are proved to be pseudoharmonic (i.e., they reproduce harmonic functions on n-dimensional balls). Our experimental results show that Poisson coordinates have lower Dirichlet energies than MVCs on a number of typical 2D domains (particularly convex domains). As well as presenting a formula, our approach provides useful insights for further studies on coordinates-based interpolation and fast estimation of harmonic functions.

The medial axis transform (MAT) is an important shape representation for shape approximation, shape recognition, and shape retrieval. Despite years of research, there is still a lack of effective methods for efficient, robust and accurate computation of the MAT. We present an efficient method, called {\em Q-MAT}, that uses quadratic error minimization to compute a structurally simple, geometrically accurate, and compact representation of the MAT. We introduce a new error metric for approximation and a new quantitative characterization of unstable branches of the MAT, and integrate them in an extension of the well-known quadric error metric (QEM) framework for mesh decimation. Q-MAT is fast, removes insignificant unstable branches effectively, and produces a simple and accurate piecewise linear approximation of the MAT. The method is thoroughly validated and compared with existing methods for MAT computation.

Finding correspondences between two surfaces is a fundamental operation in various applications in computer graphics and related fields. Candidate correspondences can be found by matching local signatures, but as they only consider local geometry, many are globally inconsistent. We provide a novel algorithm to prune a set of candidate correspondences to those most likely to be globally consistent. Our approach can handle articulated surfaces, and ones related by a deformation which is globally non-isometric, provided that the deformation is locally approximately isometric. Our approach uses an efficient diffusion framework, and only requires geodesic distance calculations in small neighbourhoods, unlike many existing techniques which require computation of global geodesic distances. We demonstrate that, for typical examples, our approach provides significant improvements in accuracy, yet also reduces time and memory costs by a factor of several hundred compared to existing pruning techniques. Our method is furthermore insensitive to holes, unlike many other methods.

This paper presents a skeleton-based method for deforming meshes (the skeleton need not be the medial axis). The significant difference from previous skeleton-based methods is that the latter use the skeleton to control movement of vertices, whereas we use it to control the simplices defining the model. By doing so, errors that occur near joints in other methods can be spread over the whole mesh, via an optimization process, resulting in smooth transitions near joints of the skeleton. By controlling simplices, our method has the additional advantage that no vertex weights need be defined on the bones, which is a tedious requirement in previous skeleton-based methods. Furthermore, by incorporating the translation vector in our optimization, unlike other methods, we do not need to fix an arbitrary vertex, and the deformed mesh moves with the deformed skeleton. Our method can also easily be used to control deformation by moving a few chosen line segments, rather than a skeleton.

In this report, we propose a new semi-fragile watermarking algorithm for the authentication of 3D models based on integral invariants. To do so, we embed a watermark image by modifying the integral invariants of some of the vertices. Basically, we shift a vertex and its neighbors in order to change the integral invariants. To extract the watermark, test all the vertices for the embedded information, and combine them to recover the watermark image. How many parts can the watermark image be recovered would help us to make the authentication decision. Experimental test shows that this method is robust against rigid transform and noise attack, and useful to test purposely attack besides transferring noise and geometrical transforming noise. An additional contribution of this paper is a new algorithm for computing two kinds of integral invariants.

Remeshing aims to produce a more regular mesh from a given input mesh, while representing the original geometry as accurately as possible. Many existing remeshing methods focus on where to place new mesh vertices; these samples are placed exactly on the input mesh. However, considering the output mesh as a piecewise linear approximation of some geometry, this simple scheme leads to significant systematic error in non-planar regions. Here, we use parameterised meshes and the recent mathematical development of orthogonal approximation using Sobolev-type inner products to develop a novel sampling scheme which allows vertices to lie in space near the input surface, rather than exactly on it. The algorithm requires little extra computational effort and can be readily incorporated into many remeshing approaches. Experimental results show that on average, approximation error can be reduced by 40% with the same number of vertices.

No abstract uploaded!

Image matching is a fundamental problem in computer vision. One of the well-known techniques is SIFT (scale-invariant feature transform). SIFT searches for and extracts robust features in hierarchical image scale spaces for object identification. However it often lacks efficiency as it identifies many insignificant features such as tree leaves and grass tips in a natural building image. We introduce a content adaptive image matching approach by preprocessing the image with a color-entropy based segmentation and harmonic inpainting. Natural structures such as tree leaves have both high entropy and distinguished color, and so such a combined measure can be both discriminative and robust. The harmonic inpainting smoothly interpolates the image functions over the tree regions and so blurrs and reduces the features and their unnecessary matching there. Numerical experiments on building images show

This paper deals with the merging problem, i.e. to approximate two adjacent Bézier curves by a single Bézier curve. A novel approach for approximate merging is introduced in the paper by using the constrained optimization method. The basic idea of this method is to find conditions for the precise merging of Bézier curves first, and then compute the constrained optimization solution by moving the control points. “Discrete” coefficient norm in L2 sense and “squared difference integral” norm are used in our method. Continuity at the endpoints of curves are considered in the merging process, and approximate merging with points constraints are also discussed. Further, it is shown that the degree elevation of original Bézier curves will reduce the merging error.

Sharp edges are important shape features and their extraction has been extensively studied both on point clouds and surfaces. We consider the problem of extracting sharp edges from a sparse set of colour-and-depth (RGB-D) images. The noise-ridden depth measurements are challenging for existing feature extraction methods that work solely in the geometric domain (e.g. points or meshes). By utilizing both colour and depth information, we propose a novel feature extraction method that produces much cleaner and more coherent feature lines. We make two technical contributions. First, we show that intensity edges can augment the depth map to improve normal estimation and feature localization from a single RGB-D image. Second, we designed a novel algorithm for consolidating feature points obtained from multiple RGB-D images. By utilizing normals and ridge/valley types associated with the feature points, our algorithm is effective in suppressing noise without smearing nearby features.

Automatic reconstruction of 3D objects from 2D orthographic views has been a major research issue in CAD/CAM. In this paper, two accelerating techniques to improve the eÆciency of reconstruction are presented. First, some pseudo elements are removed by depth and topology information as soon as the wire-frame is constructed, which reduces the searching space. Second, the proposed algorithm does not establish all possible surfaces in the process of generating 3D faces. The surfaces and edge loops are generated by using the relationship between the boundaries of 3D faces and their projections. This avoids the growth in combinational complexity of previous methods that have to check all possible pairs of 3D candidate edges.

We present a method for modifying the topology of a 3D model with user control. The heart of our method is a guided topology editing algorithm. Given a source model and a user-provided target shape, the algorithm modifies the source so that the resulting model is topologically consistent with the target. Our algorithm permits removing or adding various topological features (e.g., handles, cavities and islands) in a common framework and ensures that each topological change is made by minimal modification to the source model. To create the target shape, we have also designed a convenient 2D sketching interface for drawing 3D line skeletons. As demonstrated in a suite of examples, the use of sketching allows more accurate removal of topological artifacts than previous methods, and enables creative designs with specific topological goals.

Shape registration is fundamental to 3D object acquisition; it is used to fuse scans from multiple views. Existing algorithms mainly utilize geometric information to determine alignment, but this typically results in noticeable misalignment of textures (i.e. surface colors) when using RGB-depth cameras. We address this problem using a novel approach to color-aware registration, which takes both color and geometry into consideration simultaneously. Color information is exploited throughout the pipeline to provide more effective sampling, correspondence and alignment, in particular for surfaces with detailed textures. Our method can furthermore tackle both rigid and non-rigid registration problems (arising, for example, due to small changes in the object during scanning, or camera distortions). We demonstrate that our approach produces significantly better results than previous methods.

A nonlocally weighted soft-constrained natural gradient iterative method is introduced for robust blind separation in reverberant environment. The nonlocal weighting of the iterations promotes stability and convergence of the algorithm for long demixing filters. The scaling degree of freedom is controlled by soft-constraints built into the auxiliary difference equations. The small divisor problem of iterations in silence durations of speech is resolved. Computations on synthetic speech mixtures based on measured binaural room impulse responses show that the algorithm achieves higher signal-to-inteference ratio improvement than existing method (natural gradient time domain algorithm) in an office size room with reverberation time over 0.5 second.

No abstract uploaded!

Face tracking is an important computer vision technology that has been widely adopted in many areas, from cell phone applications to industry robots. In this paper, we introduce a novel way to parallelize a face contour detecting application based on the color-entropy preprocessed ChanVese model utilizing a total variation G-norm. This particular application is a complicated and unsupervised computational method requiring a large amount of calculations. Several core parts therein are difficult to parallelize due to heavily correlated data processing among iterations and pixels.

A convex speech enhancement (CSE) method is presented based on convex optimization and pause detection of the speech sources. Channel spatial difference is identified for enhancing each speech source individually while suppressing other interfering sources. Sparse unmixing filters indicating channel spatial differences are sought by <i>l</i> ₁ norm regularization and the split Bregman method. A subdivided split Bregman method is developed for efficiently solving the problem in severely reverberant environments. The speech pause detection is based on a binary mask source separation method. The CSE method is evaluated objectively and subjectively, and found to outperform a list of existing blind speech separation approaches on both synthetic and room recorded speech mixtures in terms of the overall computational speed and separation quality.