30-Issue 7

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/167

Browse

Now showing 1 - 20 of 28

Authoring Hierarchical Road Networks
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Galin, Eric; Peytavie, Adrien; Guérin, Eric; Benes, Bedrich; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We present a procedural method for generating hierarchical road networks connecting cities, towns and villages over large terrains. Our approach relies on an original geometric graph generation algorithm based on a non- Euclidean metric combined with a path merging algorithm that creates junctions between the different types of roads. Unlike previous work, our method allows high level user control by manipulating the density and the pattern of the network. The geometry of the highways, primary and secondary roads as well as the interchanges and intersections are automatically created from the graph structure by instantiating generic parameterized models.
Real Time Edit Propagation by Efficient Sampling
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bie, Xiaohui; Huang, Haoda; Wang, Wencheng; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
It is popular to edit the appearance of images using strokes, owing to their ease of use and convenience of conveying the user's intention. However, propagating the user inputs to the rest of the images requires solving an enormous optimization problem, which is very time consuming, thus preventing its practical use. In this paper, a two-step edit propagation scheme is proposed, first to solve edits on clusters of similar pixels and then to interpolate individual pixel edits from cluster edits. The key in our scheme is that we use efficient stroke sampling to compute the affinity between image pixels and strokes. Based on this, our clustering does not need to be strokeadaptive and thus the number of clusters is greatly reduced, resulting in a significant speedup. The proposed method has been tested on various images, and the results show that it is more than one order of magnitude faster than existing methods, while still achieving precise results compared with the ground truth. Moreover, its efficiency is not sensitive to the number of strokes, making it suitable for performing dense edits in practice.
Flexible Splicing of Upper-Body Motion Spaces on Locomotion
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Basten, Ben J. H. van; Egges, Arjan; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper presents an efficient technique for synthesizing motions by stitching, or splicing, an upper-body motion retrieved from a motion space on top of an existing lower-body locomotion of another motion. Compared to the standard motion splicing problem, motion space splicing imposes new challenges as both the upper and lower body motions might not be known in advance. Our technique is the first motion (space) splicing technique that propagates temporal and spatial properties of the lower-body locomotion to the newly generated upper-body motion and vice versa. Whereas existing techniques only adapt the upper-body motion to fit the lower-body motion, our technique also adapts the lower-body locomotion based on the upper body task for a more coherent full-body motion. In this paper, we will show that our decoupled approach is able to generate high-fidelity full-body motion for interactive applications such as games.
Efficient Opacity Specification Based on Feature Visibilities in Direct Volume Rendering
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Wang, Yunhai; Zhang, Jian; Chen, Wei; Zhang, Huai; Chi, Xuebin; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Due to 3D occlusion, the specification of proper opacities in direct volume rendering is a time-consuming and unintuitive process. The visibility histograms introduced by Correa and Ma reflect the effect of occlusion by measuring the influence of each sample in the histogram to the rendered image. However, the visibility is defined on individual samples, while volume exploration focuses on conveying the spatial relationships between features. Moreover, the high computational cost and large memory requirement limits its application in multi-dimensional transfer function design. In this paper, we extend visibility histograms to feature visibility, which measures the contribution of each feature in the rendered image. Compared to visibility histograms, it has two distinctive advantages for opacity specification. First, the user can directly specify the visibilities for features and the opacities are automatically generated using an optimization algorithm. Second, its calculation requires only one rendering pass with no additional memory requirement. This feature visibility based opacity specification is fast and compatible with all types of transfer function design. Furthermore, we introduce a two-step volume exploration scheme, in which an automatic optimization is first performed to provide a clear illustration of the spatial relationship and then the user adjusts the visibilities directly to achieve the desired feature enhancement. The effectiveness of this scheme is demonstrated by experimental results on several volumetric datasets.
Improving Performance and Accuracy of Local PCA
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Gassenbauer, Václav; Krivánek, Jaroslav; Bouatouch, Kadi; Bouville, Christian; Ribardière, Mickaël; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Local Principal Component Analysis (LPCA) is one of the popular techniques for dimensionality reduction and data compression of large data sets encountered in computer graphics. The LPCA algorithm is a variant of kmeans clustering where the repetitive classification of high dimensional data points to their nearest cluster leads to long execution times. The focus of this paper is on improving the efficiency and accuracy of LPCA. We propose a novel SortCluster LPCA algorithm that significantly reduces the cost of the point-cluster classification stage, achieving a speed-up of up to 20. To improve the approximation accuracy, we investigate different initialization schemes for LPCA and find that the k-means++ algorithm [AV07] yields best results, however at a high computation cost. We show that similar ideas that lead to the efficiency of our SortCluster LPCA algorithm can be used to accelerate k-means++. The resulting initialization algorithm is faster than purely random seeding while producing substantially more accurate data approximation.
Exposure Fusion for Time-Of-Flight Imaging
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Hahne, Uwe; Alexa, Marc; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This work deals with the problem of automatically choosing the correct exposure (or integration) time for timeof- flight depth image capturing. We apply methods known from high dynamic range imaging to combine depth images taken with differing integration times in order to produce high quality depth maps. We evaluate the quality of these depth maps by comparing the performance in reconstruction of planar textured patches and in the 3D reconstruction of an indoor scene. Our solution is fast enough to capture the images at interactive frame rates and also flexible to deal with any amount of exposures.
Creating Fluid Animation from a Single Image using Video Database
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Okabe, Makoto; Anjyo, Ken; Onai, Rikio; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We present a method for synthesizing fluid animation from a single image, using a fluid video database. The user inputs a target painting or photograph of a fluid scene along with its alpha matte that extracts the fluid region of interest in the scene. Our approach allows the user to generate a fluid animation from the input image and to enter a few additional commands about fluid orientation or speed. Employing the database of fluid examples, the core algorithm in our method then automatically assigns fluid videos for each part of the target image. Our method can therefore deal with various paintings and photographs of a river, waterfall, fire, and smoke. The resulting animations demonstrate that our method is more powerful and efficient than our prior work.
Edge-Optimized À-Trous Wavelets for Local Contrast Enhancement with Robust Denoising
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Hanika, Johannes; Dammertz, Holger; Lensch, Hendrik; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
In this paper we extend the edge-avoiding à-trous wavelet transform for local contrast enhancement while avoiding common artifacts such as halos and gradient reversals. We show that this algorithm is a highly efficient and robust tool for image manipulation based on multi-scale decompositions. It can achieve comparable results to previous high-quality methods while being orders of magnitude faster and simpler to implement. Our method is much more robust than previously known fast methods by avoiding aliasing and ringing which is achieved by introducing a data-adaptive edge weight. Operating on multi-scale, our algorithm can directly include the BayesShrink method for denoising. For moderate noise levels our edge-optimized technique consistently improves separation of signal and noise.
Motion Deblurring from a Single Image using Circular Sensor Motion
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bando, Yosuke; Chen, Bing-Yu; Nishita, Tomoyuki; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Image blur caused by object motion attenuates high frequency content of images, making post-capture deblurring an ill-posed problem. The recoverable frequency band quickly becomes narrower for faster object motion as high frequencies are severely attenuated and virtually lost. This paper proposes to translate a camera sensor circularly about the optical axis during exposure, so that high frequencies can be preserved for a wide range of in-plane linear object motion in any direction within some predetermined speed. That is, although no object may be photographed sharply at capture time, differently moving objects captured in a single image can be deconvolved with similar quality. In addition, circular sensor motion is shown to facilitate blur estimation thanks to distinct frequency zero patterns of the resulting motion blur point-spread functions. An analysis of the frequency characteristics of circular sensor motion in relation to linear object motion is presented, along with deconvolution results for photographs captured with a prototype camera.
Video Brush: A Novel Interface for Efficient Video Cutout
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Tong, Ruo-Feng; Zhang, Yun; Ding, Meng; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We present Video Brush, a novel interface for interactive video cutout. Inspired by the progressive selection scheme in images, our interface is designed to select video objects by painting on successive frames as the video plays. The video objects are progressively selected by solving the graph-cut based local optimization according to the strokes drawn by the brush on each painted frame. In order to provide users interactive feedback, we accelerate 3D graph-cut by efficient graph building and multi-level banded graph-cut. Experimental results show that our novel interface is both intuitive and efficient for video cutout.
SSD: Smooth Signed Distance Surface Reconstruction
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Calakli, Fatih; Taubin, Gabriel; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We introduce a new variational formulation for the problem of reconstructing a watertight surface defined by an implicit equation, from a finite set of oriented points; a problem which has attracted a lot of attention for more than two decades. As in the Poisson Surface Reconstruction approach, discretizations of the continuous formulation reduce to the solution of sparse linear systems of equations. But rather than forcing the implicit function to approximate the indicator function of the volume bounded by the implicit surface, in our formulation the implicit function is forced to be a smooth approximation of the signed distance function to the surface. Since an indicator function is discontinuous, its gradient does not exist exactly where it needs to be compared with the normal vector data. The smooth signed distance has approximate unit slope in the neighborhood of the data points. As a result, the normal vector data can be incorporated directly into the energy function without implicit function smoothing. In addition, rather than first extending the oriented points to a vector field within the bounding volume, and then approximating the vector field by a gradient field in the least squares sense, here the vector field is constrained to be the gradient of the implicit function, and a single variational problem is solved directly in one step. The formulation allows for a number of different efficient discretizations, reduces to a finite least squares problem for all linearly parameterized families of functions, and does not require boundary conditions. The resulting algorithms are significantly simpler and easier to implement, and produce results of quality comparable with state-of-the-art algorithms. An efficient implementation based on a primal-graph octree-based hybrid finite element-finite difference discretization, and the Dual Marching Cubes isosurface extraction algorithm, is shown to produce high quality crack-free adaptive manifold polygon meshes.
Rephotography Using Image Collections
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Lee, Kun-Ting; Luo, Sheng-Jie; Chen, Bing-Yu; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper proposes a novel system that 'rephotographs' a historical photograph with a collection of images. Rather than finding the accurate viewpoint of the historical photo, users only need to take a number of photographs around the target scene. We adopt the structure from motion technique to estimate the spatial relationship among these photographs, and construct a set of 3D point cloud. Based on the user-specified correspondences between the projected 3D point cloud and historical photograph, the camera parameters of the historical photograph are estimated. We then combine forward and backward warping images to render the result. Finally, inpainting and content-preserving warping are used to refine it, and the photograph at the same viewpoint of the historical one is produced by this photo collection.
Asynchronous Evolution for Fully-Implicit and Semi-Implicit Time Integration
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Schroeder, Craig; Kwatra, Nipun; Zheng, Wen; Fedkiw, Ron; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We propose a series of techniques for hybridizing implicit and semi-implicit time integration methods in a manner that retains much of the speed of the implicit method without sacrificing all of the higher quality vibrations one obtains with methods that handle elastic forces explicitly. We propose our scheme in the context of asynchronous methods, where different parts of the mesh are evolved at different time steps. Whereas traditional asynchronous methods evolve each element independently, we partition all of our elements into two groups: one group evolved at the frame rate using a fully implicit scheme, and another group which takes a number of substeps per frame using a scheme that is implicit on damping forces and explicit on the elastic forces. This allows for a straightforward coupling between the implicit and semi-implicit methods at frame boundaries for added stability. As has been stressed by various authors, asynchronous schemes take some of the pressure off of mesh generation, allowing time evolution to remain efficient even in the face of sliver elements. Finally, we propose a force distributing projection method which allows one to redistribute the forces felt on boundaries between implicit and semi-implicit regions of the mesh in a manner that yields improved visual quality.
River Networks for Instant Procedural Planets
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Derzapf, Evgenij; Ganster, Björn; Guthe, Michael; Klein, Reinhard; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view-dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly-through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly-throughs.
Optimized Topological Surgery for Unfolding 3D Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Takahashi, Shigeo; Wu, Hsiang-Yun; Saw, Seow Hui; Lin, Chun-Cheng; Yen, Hsu-Chun; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Constructing a 3D papercraft model from its unfolding has been fun for both children and adults since we can reproduce virtual 3D models in the real world. However, facilitating the papercraft construction process is still a challenging problem, especially when the shape of the input model is complex in the sense that it has large variation in its surface curvature. This paper presents a new heuristic approach to unfolding 3D triangular meshes without any shape distortions, so that we can construct the 3D papercraft models through simple atomic operations for gluing boundary edges around the 2D unfoldings. Our approach is inspired by the concept of topological surgery, where the appearance of boundary edges of the unfolded closed surface can be encoded using a symbolic representation. To fully simplify the papercraft construction process, we developed a genetic-based algorithm for unfolding the 3D mesh into a single connected patch in general, while optimizing the usage of the paper sheet and balance in the shape of that patch. Several examples together with user studies are included to demonstrate that the proposed approach works well for a broad range of 3D triangular meshes.
Heat Walk: Robust Salient Segmentation of Non-rigid Shapes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Benjamin, William; Polk, Andrew Wood; Vishwanathan, S. V. N.; Ramani, Karthik; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Segmenting three dimensional objects using properties of heat diffusion on meshes aim to produce salient results. The few existing algorithms based on heat diffusion do not use the full knowledge that can be gained from heat diffusion and are sensitive to varying kinds of perturbations. Our simple algorithm, Heat Walk, converts the implicit information in the heat kernel to explicit knowledge about the pathways for maximum heat flow capacity. We develop a two stage strategy for segmentation. In the first stage we quickly identify regions which are dominated by heat accumulators by employing a greedy algorithm. The second stage partitions out dissipative regions from the previously discovered accumulative regions by using a KL-divergence based criterion. The resulting algorithm is both independent of human intervention and fast because of the globally aware directed walk along the maximal heat flow capacity. Extensive experimental evidence shows the method is robust to a variety of noise factors including topological short circuits, surface holes, pose variations, variations in tessellation, missing features, scaling, as well as normal and shot noise. Comparison with the Princeton Segmentation Benchmark (PSB) shows that our method is comparable with state of the art segmentation methods and has additional advantages of being robust and self contained. Based upon theoretical insight the convergence and stability of the Heat Walk is shown.
Discriminative Sketch-based 3D Model Retrieval via Robust Shape Matching
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Shao, Tianjia; Xu, Weiwei; Yin, Kangkang; Wang, Jingdong; Zhou, Kun; Guo, Baining; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We propose a sketch-based 3D shape retrieval system that is substantially more discriminative and robust than existing systems, especially for complex models. The power of our system comes from a combination of a contourbased 2D shape representation and a robust sampling-based shape matching scheme. They are defined over discriminative local features and applicable for partial sketches; robust to noise and distortions in hand drawings; and consistent when strokes are added progressively. Our robust shape matching, however, requires dense sampling and registration and incurs a high computational cost. We thus devise critical acceleration methods to achieve interactive performance: precomputing kNN graphs that record transformations between neighboring contour images and enable fast online shape alignment; pruning sampling and shape registration strategically and hierarchically; and parallelizing shape matching on multi-core platforms or GPUs. We demonstrate the effectiveness of our system through various experiments, comparisons, and user studies.
Motion Retrieval Using Low-Rank Subspace Decomposition of Motion Volume
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Sun, Chuan; Junejo, Imran; Foroosh, Hassan; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper proposes a novel framework that allows for a flexible and an efficient retrieval of motion capture data in huge databases. The method first converts an action sequence into a novel representation, i.e. the Self-Similarity Matrix (SSM), which is based on the notion of self-similarity. This conversion of the motion sequences into compact and low-rank subspace representations greatly reduces the spatiotemporal dimensionality of the sequences. The SSMs are then used to construct order-3 tensors, and we propose a low-rank decomposition scheme that allows for converting the motion sequence volumes into compact lower dimensional representations, without losing the nonlinear dynamics of the motion manifold. Thus, unlike existing linear dimensionality reduction methods that distort the motion manifold and lose very critical and discriminative components, the proposed method performs well even when inter-class differences are small or intra-class differences are large. In addition, the method allows for an efficient retrieval and does not require the time-alignment of the motion sequences. We evaluate the performance of our retrieval framework on the CMU mocap dataset under two experimental settings, both demonstrating promising retrieval rates.
Bipartite Polar Classification for Surface Reconstruction
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Chen, Yi-Ling; Lee, Tung-Ying; Chen, Bing-Yu; Lai, Shang-Hong; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
In this paper, we propose bipartite polar classification to augment an input unorganized point set P with two disjoint groups of points distributed around the ambient space of P to assist the task of surface reconstruction. The goal of bipartite polar classification is to obtain a space partitioning of P by assigning pairs of Voronoi poles into two mutually invisible sets lying in the opposite sides of P through direct point set visibility examination. Based on the observation that a pair of Voronoi poles are mutually invisible, spatial classification is accomplished by carving away visible exterior poles with their counterparts simultaneously determined as interior ones. By examining the conflicts of mutual invisibility, holes or boundaries can also be effectively detected, resulting in a hole-aware space carving technique. With the classified poles, the task of surface reconstruction can be facilitated by more robust surface normal estimation with global consistent orientation and off-surface point specification for variational implicit surface reconstruction. We demonstrate the ability of the bipartite polar classification to achieve robust and efficient space carving on unorganized point clouds with holes and complex topology and show its application to surface reconstruction.
A Graph-based Approach to Continuous Line Illustrations with Variable Levels of Detail
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Wong, Fernando J.; Takahashi, Shigeo; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper introduces a method for automatically generating continuous line illustrations, drawings consisting of a single line, from a given input image. Our approach begins by inferring a graph from a set of edges extracted from the image in question and obtaining a path that traverses through all edges of the said graph. The resulting path is then subjected to a series of post-processing operations to transform it into a continuous line drawing. Moreover, our approach allows us to manipulate the amount of detail portrayed in our line illustrations, which is particularly useful for simplifying the overall illustration while still retaining its most significant features. We also present several experimental results to demonstrate that our approach can automatically synthesize continuous line illustrations comparable to those of some contemporary artists.

Browse

Browsing 30-Issue 7 by Issue Date

Results Per Page

Sort Options