Technical Reports Archive

Efficient Synthesis of Gradient Solid Textures
Technical Report TR-110818, GGC Group, Tsinghua University, Beijing, China  
Guo-Xin Zhang, Yu-Kun Lai and Shi-Min Hu
Online 2011.08.18

Solid textures require large storage and are computationally expensive to synthesize. In this paper, we propose a novel solid representation called gradient solids to compactly represent solid textures, including a tricubic interpolation scheme of colors and gradients for smooth variation and a region-based approach for representing sharp boundaries. We further propose a novel approach based on this to directly synthesize gradient solid textures from exemplars. Compared to existing methods, our approach avoids the expensive step of synthesizing the complete solid textures at voxel level and produces optimized solid textures using our representation. This avoids significant amount of unnecessary computation and storage involved in the voxel-level synthesis while producing solid textures with comparable quality to the state of the art. The algorithm is much faster than existing approaches for solid texture synthesis and makes it feasible to synthesize high-resolution solid textures in full. Our compact representation also supports efficient novel applications such as instant editing propagation on full solids.

PoseShop: A Human Image Database and Personalized Content Synthesis
Technical Report TR-100906, GGC Group, Tsinghua University, Beijing, China  
Tao Chen, Ping Tan, Li-Qian Ma, Ming-Ming Cheng, Ariel Shamir and Shi-Min Hu

We present a human image database collected from online images where human figures are segmented out of their background. The images are organized based on action semantic, clothes attributes and indexed by the shape of their poses. The database is built by downloading, analyzing, and filtering over 3 million human images from the Internet and can be queried using either silhouette sketch or a skeleton to find a given pose. We demonstrate the application of this database for multi-frame personalized content synthesis in the form of comic-strips, where the main character is the user or his/her friends. We address the two challenges of such synthesis, namely personalization and consistency over a set of frames, by introducing head swapping and clothes swapping techniques. We also demonstrate an action correlation analysis application to show the usefulness of the database for vision application.

Online Video Stream Stylization
Technical Report TR-090801. Tsinghua University, Beijing, China  
Song-Hai Zhang, Xian-Ying Li, Shi-Min Hu, Ralph R. Martin

This paper gives an automatic method for online video stream stylization, producing a temporally coherent output video stream. Our system transforms video into an abstract style with large regions of constant color and highlighted bold edges. Our system includes two novel components. Firstly, to provide coherent and simplified output, we segment frames, and use optical flow to propagate segmen tation information from frame to frame; an error control strategy is used to help ensure that the propagated information is reliable. Secondly, to achieve coherent and attractive coloring of the output, we use a color scheme replacement algorithm specifically designed for an online video stream. We demonstrate real-time performance, allowing our approach to be used for live communication, video games, and related applications.

Video Presentation Board : A Semantic Visualization of Video Sequence
Technical Report TR-081202. Tsinghua University, Beijing, China  
Tao Chen, Ai-Dong Lu, Shi-Min Hu

This paper presents a video summarization method to visualizing video sequences in a static image for the purposes of efficient representation and quick overview. It can assist viewers to understand important video contents by revealing essential information of video story units and their relations. We have designed a new method called Video Presentation Board to extract, organize, and synthesize important video information in a succinct and meaningful visual format, which also preserves the elegance of original videos.

Some properties of exact geodesics on triangular mesh surfaces
Technical Report TR-090620. Tsinghua University, Beijing, China   
Yong-Jin Liu, Wen-Qi Zhang, Kai Tang
Supplement Material

Computing exact geodesic paths on triangular mesh surfaces is an important operation in many geometric algorithms. In this paper we show several particular examples that reveal four interesting properties and three observations of exact geodesic computations on triangular mesh surfaces. The properties are proved and observations are drawn from experimental results using practical models. With these properties and observations, we present a new perspective of the classical MMP algorithm and the readers may find a clearer picture of how to code the MMP algorithm.

Curve Structure Extraction for Cartoon Images
Technical Report TR-081201. Tsinghua University, Beijing, China  
Ming-Ming Cheng, Shi-Min Hu

This paper presents an algorithm for extracting curve structure in cartoon images. We focus on getting smoothly and continue curve structure for both decorative curve and boundary curve simultaneously. Experimental results show that the continuity, measured by the number of curves presenting similar curve quality, enhanced a lot compared to traditional curve structure extraction algorithm. The small number of smooth curves means lead to a lot of convenient for further processing such as vectorizing and editing.

Video-Based Running Water Animation in Chinese Painting Style
Technical Report TR-080801. Tsinghua University, Beijing, China  
Song-hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, Ralph R. Martin

This paper presents a novel algorithm for synthesizing animations of running water, such as waterfalls and rivers, in the style of Chinese paintings, for applications such as cartoon making. All video frames are first registered in a common coordinate system, simultaneously segmenting the water from background and computing optical flow of the water. Taking artists’ advice into account, we produce a painting structure to guide painting of brush strokes. Flow lines are placed in the water following an analysis of variance of optical flow, to cause strokes to be drawn where the water is flowing smoothly, rather than in turbulent areas: this allows a few moving strokes to depict the trends of the water flows. A variety of brush strokes is then drawn using a template determined from real Chinese paintings. The novel contributions of this paper are: a method for painting structure generation for flows in videos, and a method for stroke placement, with the necessary temporal coherence.

Vectorizing Cartoon Animations
Technical Report TR-080701. Tsinghua University, Beijing, China  
Song-hai Zhang, Tao Chen, Yi-Fei Zhang,Shi-Min Hu, Ralph R. Martin

We present a system for vectorizing 2D raster format carton animations. The output animations are visually flicker free, smaller in file size, and easy to edit. We identify decorative lines separately from coloured regions. We use an accurate and semantically meaningful image decomposition algorithm which supports an arbitrary color model for each region. To ensure temporal coherence in the output cartoon, we reconstruct a universal background for all frames, and separately extract foreground regions. Simple user-assistance is required to complete the background. Each region and decorative line is vectorized and stored together with their motions from frame to frame.

A new watermarking method for 3D model based on integral invariant
Technical Report TR-080301. Tsinghua University, Beijing, China  
Yu-Ping Wang and Shi-Min Hu

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.

Metric-Driven RoSy Fields Design
Technical Report TR-080201. Tsinghua University, Beijing, China  
Yu-Kun Lai, Miao Jin, Xuexiang Xie, Ying He, Jonathan Palacios, Eugene Zhang, Shi-Min Hu and Xianfeng David Gu

Designing rotational symmetries on surfaces is an important task for a wide range of graphics applications. This work introduces a rigorous and practical algorithm for automatic N-RoSy 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.

Optimal Surface Parameterization Using Inverse Curvature Map
Technical Report 2007-TR-01. Tsinghua University, Beijing, China  
Yongliang Yang, Junho Kim, Feng Luo, Shimin Hu, and Xianfeng Gu

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 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. Major theoretical results are deduced using symbolic computation, for which proofs are given as Maple source code. 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.

All-Frequency Environment Light Rendering using Rotatable Square Light and Multiple Product Approximation
Technical Report 2006-TR-03. Tsinghua University, Beijing, China  
Kun Xu, Yun-Tao Jia, Shi-Min Hu, Chiew-Lan Tai

This paper presents a novel approximation technique that handles object rotation and translation in all-frequency rendering of dynamic scenes. The method can also handle arbitrary isotropic/anisotropic BRDFs, allowing on-the-fly BRDF swapping or editing. The main challenge is in the efficient approximation of the costly rendering integral between light, BRDF and visibility. We decompose the environment map, which is the integral domain, into several subregions (20-40 is sufficient for producing compelling results) so that the rendering integral over the environment map equals the sum of integrals over individual subregions. We introduce a multi-product approximation that approximates the rendering integral in each subregion by the product of separate integrals of light, BRDF and visibility. To fast compute the BRDF integral and visibility integral, we propose a new representation, rotatable square light (RSL), to represent each subregion. Based on the RSL representation, the BRDF and visibility integrals can be approximated quickly using Summed-Area Table (SAT) and Visibility Distance Table (VDT), respectively. Our algorithm can be implemented on current GPU and interactive frame rates can be achieved.

Video: Download video here (13.0MB).

Skeleton-Based Shape Deformation Using Simplex Transformations
Technical Report 2006-TR-02. Tsinghua University, Beijing, China  
Han-Bing Yan, Shi-Min Hu and Ralph R Martin

This paper presents a novel skeleton-based method for deforming meshes, based on an approximate skeleton. The major difference from previous skeleton-based methods is that they used the skeleton to control movement of vertices, whereas we use it to control the simplices defining the model. This allows errors, that occur near joints in other methods, to be spread over the whole mesh, giving smooth transitions near joints. Our method also needs no vertex weights defined on the bones, which can be tedious to choose in previous methods.

A Fast Algorithm for Computing Reeb Graph of 2-Manifold
Technical Report 2006-TR-01. Tsinghua University, Beijing, China  
Jean-Baptiste Debard and Shi-Min Hu

This paper presents an algorithm to compute the Reeb graph of a given Morse function over a compact connected oriented 2-manifold without boundary. After introducing the motivations for such a new algorithm, we will give the details of the algorithm for simplicial complex, prove its correctness and discuss its complexity and its running time.

Automatic Conversion of Meshes to T-spline Surfaces
Technical Report TR-2005. Tsinghua University, Beijing, China
Qi-Xing Huang, Yu-Kun Lai, Shi-Min Hu, Xianfeng Gu
This paper was submitted to siggraph 2005, but got rejected, and was no longer submitted. However, as we think it has its own significant contributions, and T-spline has got more attention recent years, we have decided to release it as a technical report. (online date 2010.5.15)

We give an automatic method for fitting T-spline surfaces to triangle meshes of arbitrary topology. Previous surface fitting methods required tedious human interaction to accurately capture the geometry and features. There are two main steps in our method. The first computes a curvilinear coordinate system - a conformal net on the surface, induced by global conformal parameterization. This global net is then automatically partitioned to give several rectangular patches which locally have tensor product structure suitable for defining splines. In the second step, each rectangular patch is approximated to a desired positional and normal accuracy by a T-spline surface, with appropriate continuity between patch boundaries. Use of T-splines enables us to use a low number of control points while guaranteeing L error behaviour. The only user inputs required in the whole process are these two fitting tolerances.