Search

We propose a new video vectorization approach for converting videos in the raster format to vector representation with the benefits of resolution independence and compact storage. Through classifying extracted curves in each video frame into salient ones and non-salient ones, we introduce a novel bipartite diffusion curves (BDCs) representation in order to preserve both important image features such as sharp boundaries and regions with smooth color variation. This bipartite representation allows us to propagate non-salient curves across frames such that the propagation, in conjunction with geometry optimization and color optimization of salient curves, ensures the preservation of fine details within each frame and across different frames, and meanwhile, achieves good spatial-temporal coherence. Thorough experiments on a variety of videos show that our method is capable of converting videos to the vector representation with low reconstruction errors, low computational cost, and fine details, demonstrating our superior performance over the state of the art. We also show that, when used for video upsampling, our method produces results comparable to video super-resolution.

Automatic tooth alignment target prediction is vital in shortening the planning time of orthodontic treatments and aligner designs. Generally, the quality of alignment targets greatly depends on the experience and ability of dentists and has enormous subjective factors. Therefore, many knowledge-driven alignment prediction methods have been proposed to help inexperienced dentists. Unfortunately, existing methods tend to directly regress tooth motion, which lacks clinical interpretability. Tooth anatomical landmarks play a critical role in orthodontics because they are effective in aiding the assessment of whether teeth are in close arrangement and normal occlusion. Thus, we consider anatomical landmark constraints to improve tooth alignment results. In this paper, we present a novel tooth alignment neural network for alignment target predictions based on tooth landmark constraints and a hierarchical graph structure. We detect the landmarks of each tooth first and then construct a hierarchical graph of jaw-tooth-landmark to characterize the relationship between teeth and landmarks. Then, we define the landmark constraints to guide the network to learn the normal occlusion and predict the rigid transformation of each tooth during alignment. Our method achieves better results with the architecture built for tooth data and landmark constraints and has better explainability than previous methods with regard to clinical tooth alignments.

Creating 3D shapes from 2D drawings is an important problem with applications in content creation for computer animation and virtual reality. We introduce a new sketch-based system, CreatureShop, that enables amateurs to create high-quality textured 3D character models from 2D drawings with ease and efficiency. CreatureShop takes an input bitmap drawing of a character (such as an animal or other creature), depicted from an arbitrary descriptive pose and viewpoint, and creates a 3D shape with plausible geometric details and textures from a small number of user annotations on the 2D drawing. Our key contributions are a novel oblique view modeling method, a set of systematic approaches for producing plausible textures on the invisible or occluded parts of the 3D character (as viewed from the direction of the input drawing), and a user-friendly interactive system. We validate our system and methods by creating numerous 3D characters from various drawings, and compare our results with related works to show the advantages of our method. We perform a user study to evaluate the usability of our system, which demonstrates that our system is a practical and efficient approach to create fully-textured 3D character models for novice users., This is the author's version of the article published in IEEE Transactions on Visualization and Computer Graphics, 2022

Volumetric data abounds in medical imaging and other fields. With the improved imaging quality and the increased resolution, volumetric datasets are getting so large that the existing tools have become inadequate for processing and analyzing the data. Here we consider the problem of computing tetrahedral meshes to represent large volumetric datasets with labeled multiple materials, which are often encountered in medical imaging or microscopy optical slice tomography. Such tetrahedral meshes are a more compact and expressive geometric representation so are in demand for efficient visualization and simulation of the data, which are impossible if the original large volumetric data are used directly due to the large memory requirement. Existing methods for meshing volumetric data are not scalable for handling large datasets due to their sheer demand on excessively large run-time memory or failure to produce a tet-mesh that preserves the multi-material structure of the original volumetric data. In this paper we propose a novel approach, called Marching Windows, that uses a moving window and a disk-swap strategy to reduce the run-time memory footprint, devise a new scheme that guarantees to preserve the topological structure of the original dataset, and adopt an error-guided optimization technique to improve both geometric approximation error and mesh quality. Extensive experiments show that our method is capable of processing very large volumetric datasets beyond the capability of the existing methods and producing tetrahedral meshes of high quality.

Geodesics measure the shortest distance between points on curved surfaces and are a fundamental tool in digital geometry processing. Although there are many algorithms for computing geodesic paths, most of them are designed for a single type of geometric domain (typically a triangle mesh), thus diminishing its practical usage. In this paper, we propose a general framework for computing geodesic paths for various geometric domains, including meshes, point clouds, implicit surfaces and parametric surfaces. Our key idea is to decouple geodesic computation from the type of the input surfaces. Discretizing the initial path by a sequence of points{x_i}, i=1,2,…,n that can only move on the surface, we minimize H(||x_i-x_(i+1)||), i=1,2,…,n. We show that the point sequence yielded by our approach is also a minimizer of the traditional geodesic length function, and the points are evenly spaced along the path. Our method encodes 3D geometry by signed distance functions (SDF) and can work for all types of input. We also propose a simple yet effective strategy to generate initial paths. We demonstrate the advantages of our methods over the conventional geodesic path algorithms in terms of accuracy, performance and scalability. Finally, we show that our method can be extended to solve general minimal-cost path problem.

This article presents a simple yet effective method for computing geodesic distances on triangle meshes. Unlike the popular window propagation methods that partition mesh edges into intervals of varying lengths, our method places evenly-spaced, source-independent Steiner points on edges. Given a source vertex, our method constructs a Steiner-point graph that partitions the surface into mutually exclusive tracks, called geodesic tracks. Inside each triangle, the tracks form sub-regions in which the change of distance field is approximately linear. Our method does not require any pre-computation, and can effectively balance speed and accuracy. Experimental results show that with 5 Steiner points on each edge, the mean relative error is less than 0.3 % for common 3D models used in the graphics community. We propose a set of effective filtering rules to eliminate a large amount of useless broadcast events. For a 1000K-face model, our method runs 10 times faster than the conventional Steiner point method that examines a complete graph of Steiner points in each triangle. We also observe that using more Steiner points increases the accuracy at only a small extra computational cost. Our method works well for meshes with poor triangulation and non-manifold configuration, which often poses challenges to the existing PDE methods. We show that geodesic tracks, as a new data structure that encodes rich information of discrete geodesics, support accurate geodesic path and isoline tracing, and efficient distance query. Our method can be easily extended to meshes with non-constant density functions and/or anisotropic metrics.

Synthesizing realistic videos of humans using neural networks has been a popular alternative to the conventional graphics-based rendering pipeline due to its high efficiency. Existing works typically formulate this as an image-to-image translation problem in 2D screen space, which leads to artifacts such as over-smoothing, missing body parts, and temporal instability of fine-scale detail, such as pose-dependent wrinkles in the clothing. In this article, we propose a novel human video synthesis method that approaches these limiting factors by explicitly disentangling the learning of time-coherent fine-scale details from the embedding of the human in 2D screen space. More specifically, our method relies on the combination of two convolutional neural networks (CNNs). Given the pose information, the first CNN predicts a dynamic texture map that contains time-coherent high-frequency details, and the second CNN conditions the generation of the final video on the temporally coherent output of the first CNN. We demonstrate several applications of our approach, such as human reenactment and novel view synthesis from monocular video, where we show significant improvement over the state of the art both qualitatively and quantitatively.

Retrieving salient structure from textured images is an important but difficult problem in computer vision because texture, which can be irregular, anisotropic, non-uniform and complex, shares many of the same properties as structure. Observing that salient structure in a textured image should be piece-wise smooth, we present a method to retrieve such structures using an $L_0$ minimization of a modified form of the relative total variation metric. Thanks to the characteristics shared by texture and small structures, our method is effective at retrieving structure based on scale as well. Our method outperforms state-of-art methods in texture removal as well as scale-space filtering. We also demonstrate our method's ability in other applications such as edge detection, clip art compression artifact removal, and inverse half-toning.

A new method is presented for producing photo collages that preserve content correlation of photos. We use deep learning techniques to find correlation among given photos to facilitate their embedding on the canvas, and develop an efficient combinatorial optimization technique to make correlated photos stay close to each other. To make efficient use of canvas space, our method first extracts salient regions of photos and packs only these salient regions. We allow the salient regions to have arbitrary shapes, therefore yielding informative, yet more compact collages than by other similar collage methods based on salient regions. We present extensive experimental results, user study results, and comparisons against the state-of-the-art methods to show the superiority of our method.

We present a novel solution to enable portrait relief modeling from a single image. The main challenges are geometry reconstruction, facial details recovery and depth structure preservation. Previous image-based methods are developed for portrait bas-relief modeling in 2.5D form, but not adequate for 3D-like high relief modeling with undercut features. In this paper, we propose a template-based framework to generate portrait reliefs of various forms. Our method benefits from Shape-from-Shading (SFS). Specifically, we use bi-Laplacian mesh deformation to guide the relief modeling. Given a portrait image, we first use a template face to fit the portrait. We then apply bi-Laplacian mesh deformation to align the facial features. Afterwards, SFS-based reconstruction with a few user interactions is used to optimize the face depth, and create a relief with similar appearance to the input. Both depth structures and geometric details can be well constructed in the final relief. Experiments and comparisons to other methods demonstrate the effectiveness of the proposed method.

Mosaics are widely used for surface decoration to produce appealing visual effects. We present a method for synthesizing digital surface mosaics with irregularly shaped tiles, which are a type of tiles often used for mosaics design. Our method employs both continuous optimization and combinatorial optimization to improve tile arrangement. In the continuous optimization step, we iteratively partition the base surface into approximate Voronoi regions of the tiles and optimize the positions and orientations of the tiles to achieve a tight fit. Combination optimization performs tile permutation and replacement to further increase surface coverage and diversify tile selection. The alternative applications of these two optimization steps lead to rich combination of tiles and high surface coverage. We demonstrate the effectiveness of our solution with extensive experiments and comparisons.

Three-dimensional symmetric tensor fields have a wide range of applications in solid and fluid mechanics. Recent advances in the (topological) analysis of 3D symmetric tensor fields focus on degenerate tensors which form curves. In this paper, we introduce a number of feature surfaces, such as neutral surfaces and traceless surfaces , into tensor field analysis, based on the notion of eigenvalue manifold . Neutral surfaces are the boundary between linear tensors and planar tensors, and the traceless surfaces are the boundary between tensors of positive traces and those of negative traces. Degenerate curves, neutral surfaces, and traceless surfaces together form a partition of the eigenvalue manifold, which provides a more complete tensor field analysis than degenerate curves alone. We also extract and visualize the isosurfaces of tensor modes, tensor isotropy, and tensor magnitude, which we have found useful for domain applications in fluid and solid mechanics. Extracting neutral and traceless surfaces using the Marching Tetrahedra method can cause the loss of geometric and topological details, which can lead to false physical interpretation. To robustly extract neutral surfaces and traceless surfaces, we develop a polynomial description of them which enables us to borrow techniques from algebraic surface extraction, a topic well-researched by the computer-aided design (CAD) community as well as the algebraic geometry community. In addition, we adapt the surface extraction technique, called A-patches , to improve the speed of finding degenerate curves. Finally, we apply our analysis to data from solid and fluid mechanics as well as scalar field analysis.

The medial axis transform has long been known as an intrinsic shape representation supporting a variety of shape analysis and synthesis tasks. However, for a given shape, it is hard to obtain its faithful, concise and stable medial axis, which hinders the application of the medial axis. In this paper, we introduce the medial mesh , a new discrete representation of the medial axis. A medial mesh is a 2D simplicial complex coupled with a radius function that provides a piecewise linear approximation to the medial axis. We further present an effective algorithm for computing a concise and stable medial mesh for a given shape. Our algorithm is quantitatively driven by a shape approximation error metric, and progressively simplifies an initial medial mesh by iteratively contracting edges until the approximation error reaches a predefined threshold. We further demonstrate the superior efficiency and accuracy of our method over existing methods for medial axis simplification.

We present a visualization approach for the analysis of CO2 bubble-induced attenuation in porous rock formations. As a basis for this, we introduce customized techniques to extract CO2 bubbles and their surrounding porous structure from X-ray computed tomography data (XCT) measurements. To understand how the structure of porous media influences the occurrence and the shape of formed bubbles, we automatically classify and relate them in terms of morphology and geometric features, and further directly support searching for promising porous structures. To allow for the meaningful direct visual comparison of bubbles and their structures, we propose a customized registration technique considering the bubble shape as well as its points of contact with the porous media surface. With our quantitative extraction of geometric bubble features, we further support the analysis as well as the creation of a physical model. We demonstrate that our approach was successfully used to answer several research questions in the domain, and discuss its high practical relevance to identify critical seismic characteristics of fluid-saturated rock that govern its capability to store CO2.

Line drawings and digital arts appear everywhere, from simple icons and logos to cartoons, maps, and illustrations. We define art patterns as the subset of line drawings and digital arts that are comprised of repeated elements. There exist textures that share characteristics with art patterns. Examples of such textures include piled discrete elements with curved contours. Inspired by recent success of exemplar-based texture synthesis, in this paper, we focus on synthesizing art patterns and textures with curvilinear features from exemplars, which we cast as a global optimization problem. Our energy function for this problem measures both the appearance similarity of color patterns and shape similarity of curvilinear features between an input exemplar and a synthesized image. We develop an overall expectation-maximization-style algorithm for minimizing this energy function. The shape similarity part of the energy is minimized through an innovative application of the level set method. We further generalize our energy function and optimization algorithm to multilayer pattern and texture synthesis. Our generalized optimization can effectively handle multiple layers and synthesize valid instances of interaction.

In this paper, we present a novel approach for automatically creating the photo collage that assembles the interest regions of a given group of images naturally. Previous methods on photo collage are generally built upon a well-defined optimization framework, which computes all the geometric parameters and layer indices for input photos on the given canvas by optimizing a unified objective function. The complex nonlinear form of optimization function limits their scalability and efficiency. From the geometric point of view, we recast the generation of collage as a region partition problem such that each image is displayed in its corresponding region partitioned from the canvas. The core of this is an efficient power-diagram-based circle packing algorithm that arranges a series of circles assigned to input photos compactly in the given canvas. To favor important photos, the circles are associated with image importances determined by an image ranking process. A heuristic search process is developed to ensure that salient information of each photo is displayed in the polygonal area resulting from circle packing. With our new formulation, each factor influencing the state of a photo is optimized in an independent stage, and computation of the optimal states for neighboring photos are completely decoupled. This improves the scalability of collage results and ensures their diversity. We also devise a saliency-based image fusion scheme to generate seamless compositive collage. Our approach can generate the collages on nonrectangular canvases and supports interactive collage that allows the user to refine collage results according to his/her personal preferences. We conduct extensive experiments and show the superiority of our algorithm by comparing against previous methods.

Centroidal Voronoi Tessellation (CVT) is a widely used geometric structure in applications including mesh generation, vector quantization and image processing. Global optimization of the CVT function is important in these applications. With numerical evidences, we show that the CVT function is highly nonconvex and has many local minima and therefore the global optimization of the CVT function is nontrivial. We apply the method of Monte Carlo with Minimization (MCM) to optimizing the CVT function globally and demonstrate its efficacy in producing much improved results compared with two other global optimization methods.

Blue noise point sampling is one of the core algorithms in computer graphics. In this paper, we present a new and versatile variational framework for generating point distributions with high-quality blue noise characteristics while precisely adapting to given density functions. Different from previous approaches based on discrete settings of capacity-constrained Voronoi tessellation, we cast the blue noise sampling generation as a variational problem with continuous settings. Based on an accurate evaluation of the gradient of an energy function, an efficient optimization is developed which delivers significantly faster performance than the previous optimization-based methods. Our framework can easily be extended to generating blue noise point samples on manifold surfaces and for multi-class sampling. The optimization formulation also allows us to naturally deal with dynamic domains, such as deformable surfaces, and to yield blue noise samplings with temporal coherence. We present experimental results to validate the efficacy of our variational framework. Finally, we show a variety of applications of the proposed methods, including nonphotorealistic image stippling, color stippling, and blue noise sampling on deformable surfaces.

We present a novel artistic-verisimilitude driven system for watercolor rendering of images and photos. Our system achieves realistic simulation of a set of important characteristics of watercolor paintings that have not been well implemented before. Specifically, we designed several image filters to achieve: 1) watercolor-specified color transferring; 2) saliency-based level-of-detail drawing; 3) hand tremor effect due to human neural noise; and 4) an artistically controlled wet-in-wet effect in the border regions of different wet pigments. A user study indicates that our method can produce watercolor results of artistic verisimilitude better than previous filter-based or physical-based methods. Furthermore, our algorithm is efficient and can easily be parallelized, making it suitable for interactive image watercolorization.

We present a new method for converting a photo or image to a synthesized painting following the painting style of an example painting. Treating painting styles of brush strokes as sample textures, we reduce the problem of learning an example painting to a texture synthesis problem. The proposed method uses a hierarchical patch-based approach to the synthesis of directional textures. The key features of our method are: 1) Painting styles are represented as one or more blocks of sample textures selected by the user from the example painting; 2) image segmentation and brush stroke directions defined by the medial axis are used to better represent and communicate shapes and objects present in the synthesized painting; 3) image masks and a hierarchy of texture patches are used to efficiently synthesize high-quality directional textures. The synthesis process is further accelerated through texture direction quantization and the use of Gaussian pyramids. Our method has the following advantages: First, the synthesized stroke textures can follow a direction field determined by the shapes of regions to be painted. Second, the method is very efficient; the generation time of a synthesized painting ranges from a few seconds to about one minute, rather than hours, as required by other existing methods, on a commodity PC. Furthermore, the technique presented here provides a new and efficient solution to the problem of synthesizing a 2D directional texture. We use a number of test examples to demonstrate the efficiency of the proposed method and the high quality of results produced by the method.

We present an accurate and efficient algorithm for continuous collision detection between two moving ellipsoids under rational Euclidean or affine motion. We start with a highly optimized implementation of interference testing between two stationary ellipsoids based on an algebraic condition described in terms of the signs of roots of the characteristic equation of two ellipsoids. Then we derive a time-dependent characteristic equation for two moving ellipsoids, which enables us to develop an efficient algorithm for computing the time intervals in which two moving ellipsoids collide. The effectiveness of our approach is demonstrated with several practical examples.

Coarse piecewise linear approximation of surfaces causes the undesirable polygonal appearance of silhouettes. We present an efficient method for smoothing the silhouettes of coarse triangle meshes using efficient 3D curve reconstruction and simple local remeshing. It does not assume the availability of a fine mesh and generates only a moderate amount of additional data at runtime. Furthermore, polygonal feature edges are also smoothed in a unified framework. Our method is based on a novel interpolation scheme over silhouette triangles, and this ensures that smooth silhouettes are faithfully reconstructed and always change continuously with respect to the continuous movement of the viewpoint or objects. We speed up computation with GPU assistance to achieve real-time rendering of coarse meshes with the smoothed silhouettes. Experiments show that this method outperforms previous methods for silhouette smoothing.

We present a complete framework for computing a subdivision surface to approximate unorganized point sample data, which is a separable nonlinear least squares problem. We study the convergence and stability of three geometrically-motivated optimization schemes and reveal their intrinsic relations with standard methods for constrained nonlinear optimization. A commonly-used method in graphics, called point distance minimization, is shown to use a variant of the gradient descent step and thus has only linear convergence. The second method, called tangent distance minimization, which is well-known in computer vision, is shown to use the Gauss-Newton step, and thus demonstrates near quadratic convergence for zero residual problems but may not converge otherwise. Finally, we show that an optimization scheme called squared distance minimization, recently proposed by Pottmann et al., can be derived from the Newton method. Hence, with proper regularization, tangent distance minimization and squared distance minimization are more efficient than point distance minimization. We also investigate the effects of two step size control methods -- Levenberg-Marquardt regularization and the Armijo rule -- on the convergence stability and efficiency of the above optimization schemes.