30-Issue 7

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 28

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.
Toward Optimal Space Partitioning for Unbiased, Adaptive Free Path Sampling of Inhomogeneous Participating Media
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Yue, Yonghao; Iwasaki, Kei; Chen, Bing-Yu; Dobashi, Yoshinori; Nishita, Tomoyuki; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Photo-realistic rendering of inhomogeneous participating media with light scattering in consideration is impor- tant in computer graphics, and is typically computed using Monte Carlo based methods. The key technique in such methods is the free path sampling, which is used for determining the distance (free path) between successive scattering events. Recently, it has been shown that efficient and unbiased free path sampling methods can be con- structed based on Woodcock tracking. The key concept for improving the efficiency is to utilize space partitioning (e.g., kd-tree or uniform grid), and a better space partitioning scheme is important for better sampling efficiency. Thus, an estimation framework for investigating the gain in sampling efficiency is important for determining how to partition the space. However, currently, there is no estimation framework that works in 3D space. In this paper, we propose a new estimation framework to overcome this problem. Using our framework, we can analytically estimate the sampling efficiency for any typical partitioned space. Conversely, we can also use this estimation framework for determining the optimal space partitioning. As an application, we show that new space partition- ing schemes can be constructed using our estimation framework. Moreover, we show that the differences in the performances using different schemes can be predicted fairly well using our estimation framework.
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.
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.
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.
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.
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.
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.
Intelligent GPGPU Classification in Volume Visualization: A framework based on Error-Correcting Output Codes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Escalera, Sergio; Puig, Anna; Amoros, Oscar; Salamó, Maria; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
In volume visualization, the definition of the regions of interest is inherently an iterative trial-and-error process finding out the best parameters to classify and render the final image. Generally, the user requires a lot of expertise to analyze and edit these parameters through multi-dimensional transfer functions. In this paper, we present a framework of intelligent methods to label on-demand multiple regions of interest. These methods can be split into a two-level GPU-based labelling algorithm that computes in time of rendering a set of labelled structures using the Machine Learning Error-Correcting Output Codes (ECOC) framework. In a pre-processing step, ECOC trains a set of Adaboost binary classifiers from a reduced pre-labelled data set. Then, at the testing stage, each classifier is independently applied on the features of a set of unlabelled samples and combined to perform multi-class labelling. We also propose an alternative representation of these classifiers that allows to highly parallelize the testing stage. To exploit that parallelism we implemented the testing stage in GPU-OpenCL. The empirical results on different data sets for several volume structures shows high computational performance and classification accuracy.
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.
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.
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.
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.
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.
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.
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.
A Single Image Representation Model for Efficient Stereoscopic Image Creation
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Kim, Younghui; Jung, Hwi-ryong; Choi, Sungwoo; Lee, Jungjin; Noh, Junyong; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Computer graphics is one of the most efficient ways to create a stereoscopic image. The process of stereoscopic CG generation is, however, still very inefficient compared to that of monoscopic CG generation. Despite that stereo images are very similar to each other, they are rendered and manipulated independently. Additional requirements for disparity control specific to stereo images lead to even greater inefficiency. This paper proposes a method to reduce the inefficiency accompanied in the creation of a stereoscopic image. The system automatically generates an optimized single image representation of the entire visible area from both cameras. The single image can be easily manipulated with conventional techniques, as it is spatially smooth and maintains the original shapes of scene objects. In addition, a stereo image pair can be easily generated with an arbitrary disparity setting. These convenient and efficient features are achieved by the automatic generation of a stereo camera pair, robust occlusion detection with a pair of Z-buffers, an optimization method for spatial smoothness, and stereo image pair generation with a non-linear disparity adjustment. Experiments show that our technique dramatically improves the efficiency of stereoscopic image creation while preserving the quality of the results.
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.
Interactive Indirect Illumination Using Voxel Cone Tracing
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Crassin, Cyril; Neyret, Fabrice; Sainz, Miguel; Green, Simon; Eisemann, Elmar; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Indirect illumination is an important element for realistic image synthesis, but its computation is expensive and highly dependent on the complexity of the scene and of the BRDF of the involved surfaces. While off-line computation and pre-baking can be acceptable for some cases, many applications (games, simulators, etc.) require real-time or interactive approaches to evaluate indirect illumination. We present a novel algorithm to compute indirect lighting in real-time that avoids costly precomputation steps and is not restricted to low-frequency illumination. It is based on a hierarchical voxel octree representation generated and updated on the fly from a regular scene mesh coupled with an approximate voxel cone tracing that allows for a fast estimation of the visibility and incoming energy. Our approach can manage two light bounces for both Lambertian and glossy materials at interactive framerates (25-70FPS). It exhibits an almost scene-independent performance and can handle complex scenes with dynamic content thanks to an interactive octree-voxelization scheme. In addition, we demonstrate that our voxel cone tracing can be used to efficiently estimate Ambient Occlusion.
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.

Browse

Browsing 30-Issue 7 by Issue Date

Results Per Page

Sort Options