Image‐Based Edge Bundles: Simplified Visualization of Large Graphs

We present a new approach aimed at understanding the structure of connections in edge‐bundling layouts. We combine the advantages of edge bundles with a bundle‐centric simplified visual representation of a graph's structure. For this, we first compute a hierarchical edge clustering of a given graph layout which groups similar edges together. Next, we render clusters at a user‐selected level of detail using a new image‐based technique that combines distance‐based splatting and shape skeletonization. The overall result displays a given graph as a small set of overlapping shaded edge bundles. Luminance, saturation, hue, and shading encode edge density, edge types, and edge similarity. Finally, we add brushing and a new type of semantic lens to help navigation where local structures overlap. We illustrate the proposed method on several real‐world graph datasets.     

Winding Roads: Routing edges into bundles

Visualizing graphs containing many nodes and edges efficiently is quite challenging. Drawings of such graphs generally suffer from visual clutter induced by the large amount of edges and their crossings. Consequently it is difficult to read the relationships between nodes and the high‐level edge patterns that may exist in standard node‐link diagram representations. Edge bundling techniques have been proposed to help solve this issue, which rely on high quality edge rerouting. In this paper, we introduce an intuitive edge bundling technique which efficiently reduces edge clutter in graphs drawings. Our method is based on the use of a grid built using the original graph to compute the edge rerouting. In comparison with previously proposed edge bundling methods, our technique improves both the level of clutter reduction and the computation performance. The second contribution of this paper is a GPU‐based rendering method which helps users perceive bundles densities while preserving edge color.     

Interactive Cover Design Considering Physical Constraints

We developed an interactive system to design a customized cover for a given three‐dimensional (3D) object such as a camera, teapot, or car. The system first computes the convex hull of the input geometry. The user segments it into several cloth patches by drawing on the 3D surface. This paper provides two technical contributions. First, it introduces a specialized flattening algorithm for cover patches. It makes each two‐dimensional edge in the flattened pattern equal to or longer than the original 3D edge; a smaller patch would fail to cover the object, and a larger patch would result in extra wrinkles. Second, it introduces a mechanism to verify that the user‐specified opening would be large enough for the object to be removed. Starting with the initial configuration, the system virtually “pulls” the object out of the cover while avoiding excessive stretching of cloth patches. We used the system to design real covers and confirmed that it functions as intended.     

Soft Folding

We introduce soft folding, a new interactive method for designing and exploring thin‐plate forms. A user specifies sharp and soft folds as two‐dimensional(2D) curves on a flat sheet, along with the fold magnitude and sharpness of each. Then, based on the soft folds, the system computes the three‐dimensional(3D) folded shape. Internally, the system first computes a fold field, which defines local folding operations on a flat sheet. A fold field is a generalization of a discrete fold graph in origami, replacing a graph with sharp folds with a continuous field with soft folds. Next, local patches are folded independently according to the fold field. Finally, a globally folded 3D shape is obtained by assembling the locally folded patches. This algorithm computes an approximation of 3D developable surfaces with user‐defined soft folds at an interactive speed. The user can later apply nonlinear physical simulation to generate more realistic results. Experimental results demonstrated that soft folding is effective for producing complex folded shapes with controllable sharpness.     

Modeling Complex Unfoliaged Trees from a Sparse Set of Images

We present a novel image‐based technique for modeling complex unfoliaged trees. Existing tree modeling tools either require capturing a large number of views for dense 3D reconstruction or rely on user inputs and botanic rules to synthesize natural‐looking tree geometry. In this paper, we focus on faithfully recovering real instead of realistically‐looking tree geometry from a sparse set of images. Our solution directly integrates 2D/3D tree topology as shape priors into the modeling process. For each input view, we first estimate a 2D skeleton graph from its matte image and then find a 2D skeleton tree from the graph by imposing tree topology. We develop a simple but effective technique for computing the optimal 3D skeleton tree most consistent with the 2D skeletons. For each edge in the 3D skeleton tree, we further apply volumetric reconstruction to recover its corresponding curved branch. Finally, we use piecewise cylinders to approximate each branch from the volumetric results. We demonstrate our framework on a variety of trees to illustrate the robustness and usefulness of our technique.     

Structural Analysis of Multivariate Point Clouds Using Simplicial Chains

Topological and geometrical methods constitute common tools for the analysis of high‐dimensional scientific data sets. Geometrical methods such as projection algorithms focus on preserving distances in the data set. Topological methods such as contour trees, by contrast, focus on preserving structural and connectivity information. By combining both types of methods, we want to benefit from their individual advantages. To this end, we describe an algorithm that uses persistent homology to analyse the topology of a data set. Persistent homology identifies high‐dimensional holes in data sets, describing them as simplicial chains. We localize these chains using geometrical information of the data set, which we obtain from geodesic distances on a neighbourhood graph. The localized chains describe the structure of point clouds. We represent them using an interactive graph, in which each node describes a single chain and its geometrical properties. This graph yields a more intuitive understanding of multivariate point clouds and simplifies comparisons of time‐varying data. Our method focuses on detecting and analysing inhomogeneous regions, i.e. holes, in a data set because these regions characterize data in a different manner, thereby leading to new insights. We demonstrate the potential of our method on data sets from particle physics, political science and meteorology.     

Registration Based Non‐uniform Motion Deblurring

This paper proposes an algorithm which uses image registration to estimate a non‐uniform motion blur point spread function (PSF) caused by camera shake. Our study is based on a motion blur model which models blur effects of camera shakes using a set of planar perspective projections (i.e., homographies). This representation can fully describe motions of camera shakes in 3D which cause non‐uniform motion blurs. We transform the non‐uniform PSF estimation problem into a set of image registration problems which estimate homographies of the motion blur model one‐by‐one through the Lucas‐Kanade algorithm. We demonstrate the performance of our algorithm using both synthetic and real world examples. We also discuss the effectiveness and limitations of our algorithm for non‐uniform deblurring.     

Location‐dependent generalization of road networks based on equivalent destinations

Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge‐weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear‐time algorithm to compute the minimum‐cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus‐and‐context map generalization. When contracting shortest‐path trees in a geographic network, the computed clustering additionally provides a constant‐factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.     

Visualizing the Uncertainty of Graph‐based 2D Segmentation with Min‐path Stability

This paper presents a novel approach to visualize the uncertainty in graph‐based segmentations of scalar data. Segmentation of 2D scalar data has wide application in a variety of scientific and medical domains. Typically, a segmentation is presented as a single unambiguous boundary although the solution is often uncertain due to noise or blur in the underlying data as well as imprecision in user input. Our approach provides insight into this uncertainty by computing the “min‐path stability”, a scalar measure analyzing the stability of the segmentation given a set of input constraints. Our approach is efficient, easy to compute, and can be generally applied to either graph cuts or live‐wire (even partial) segmentations. In addition to its general applicability, our new approach to graph cuts uncertainty visualization improves on the time complexity of the current state‐of‐the‐art with an additional fast approximate solution. We also introduce a novel query enabled by our approach which provides users with alternate segmentations by efficiently extracting local minima of the segmentation optimization. Finally, we evaluate our approach and demonstrate its utility on data from scientific and medical applications.     

Scalable Partitioning for Parallel Position Based Dynamics

We introduce a practical partitioning technique designed for parallelizing Position Based Dynamics, and exploiting the ubiquitous multi‐core processors present in current commodity GPUs. The input is a set of particles whose dynamics is influenced by spatial constraints. In the initialization phase, we build a graph in which each node corresponds to a constraint and two constraints are connected by an edge if they influence at least one common particle. We introduce a novel greedy algorithm for inserting additional constraints (phantoms) in the graph such that the resulting topology is ‐colourable, where is an arbitrary number. We color the graph, and the constraints with the same color are assigned to the same partition. Then, the set of constraints belonging to each partition is solved in parallel during the animation phase. We demonstrate this by using our partitioning technique; the performance hit caused by the GPU kernel calls is significantly decreased, leaving unaffected the visual quality, robustness and speed of serial position based dynamics.     

Automatic Animation for Time‐Varying Data Visualization

This paper presents a digital storytelling approach that generates automatic animations for time‐varying data visualization. Our approach simulates the composition and transition of storytelling techniques and synthesizes animations to describe various event features. Specifically, we analyze information related to a given event and abstract it as an event graph, which represents data features as nodes and event relationships as links. This graph embeds a tree‐like hierarchical structure which encodes data features at different scales. Next, narrative structures are built by exploring starting nodes and suitable search strategies in this graph. Different stages of narrative structures are considered in our automatic rendering parameter decision process to generate animations as digital stories. We integrate this animation generation approach into an interactive exploration process of time‐varying data, so that more comprehensive information can be provided in a timely fashion. We demonstrate with a storm surge application that our approach allows semantic visualization of time‐varying data and easy animation generation for users without special knowledge about the underlying visualization techniques.     

Curvature Aware Fundamental Cycles

We present a graph algorithm to find fundamental cycles aligned with the principal curvature directions of a surface. Specifically, we use the tree‐cotree decomposition of graphs embedded in manifolds, guided with edge weights, in order to produce these cycles. Our algorithm is very quick compared to existing methods, with a worst case running time of O(n log n+gn) where n is the number of faces and g is the surface genus. Further, its flexibility to accommodate different weighting functions and to handle boundaries may be used to produce cycles suitable for a variety of applications and models.     

Using a Visual Attention Model to Improve Gaze Tracking Systems in Interactive 3D Applications

This paper introduces the use of a visual attention model to improve the accuracy of gaze tracking systems. Visual attention models simulate the selective attention part of the human visual system. For instance, in a bottom‐up approach, a saliency map is defined for the image and gives an attention weight to every pixel of the image as a function of its colour, edge or intensity. Our algorithm uses an uncertainty window, defined by the gaze tracker accuracy, and located around the gaze point given by the tracker. Then, using a visual attention model, it searches for the most salient points, or objects, located inside this uncertainty window, and determines a novel, and hopefully, better gaze point. This combination of a gaze tracker together with a visual attention model is considered as the main contribution of the paper. We demonstrate the promising results of our method by presenting two experiments conducted in two different contexts: (1) a free exploration of a visually rich 3D virtual environment without a specific task, and (2) a video game based on gaze tracking involving a selection task. Our approach can be used to improve real‐time gaze tracking systems in many interactive 3D applications such as video games or virtual reality applications. The use of a visual attention model can be adapted to any gaze tracker and the visual attention model can also be adapted to the application in which it is used.     

Semi‐isometric Registration of Line Features for Flexible Fitting of Protein Structures

In this paper, we study a registration problem that is motivated by a practical biology problem – fitting protein structures to low‐re solution density maps. We consider registration between two sets of lines features (e.g., helices in the proteins) that have undergone not a single, but multiple isometric transformations (e.g., hinge‐motions). The problem is further complicated by the presence of symmetry in each set. We formulate the problem as a clique‐finding problem in a product graph, and propose a heuristic solution that includes a fast clique‐finding algorithm unique to the structure of this graph. When tested on a suite of real protein structures, the algorithm achieved high accuracy even for very large inputs containing hundreds of helices.     

Visualizing a Sequence of a Thousand Graphs (or Even More)

The visualization of dynamic graphs demands visually encoding at least three major data dimensions: vertices, edges, and time steps. Many of the state‐of‐the‐art techniques can show an overview of vertices and edges but lack a data‐scalable visual representation of the time aspect. In this paper, we address the problem of displaying dynamic graphs with a thousand or more time steps. Our proposed interleaved parallel edge splatting technique uses a time‐to‐space mapping and shows the complete dynamic graph in a static visualization. It provides an overview of all data dimensions, allowing for visually detecting time‐varying data patterns; hence, it serves as a starting point for further data exploration. By applying clustering and ordering techniques on the vertices, edge splatting on the links, and a dense time‐to‐space mapping, our approach becomes visually scalable in all three dynamic graph data dimensions. We illustrate the usefulness of our technique by applying it to call graphs and US domestic flight data with several hundred vertices, several thousand edges, and more than a thousand time steps.     

Efficient Computation of Blue Noise Point Sets through Importance Sampling

Dart‐throwing can generate ideal Poisson‐disk distributions with excellent blue noise properties, but is very computationally expensive if a maximal point set is desired. In this paper, we observe that the Poisson‐disk sampling problem can be posed in terms of importance sampling by representing the available space to be sampled as a probability density function (pdf). This allows us to develop an efficient algorithm for the generation of maximal Poisson‐disk distributions with quality similar to naïve dart‐throwing but without rejection of samples. In our algorithm, we first position samples in one dimension based on its marginal cumulative distribution function (cdf). We then throw samples in the other dimension only in the regions which are available for sampling. After each 2D sample is placed, we update the cdf and data structures to keep track of the available regions. In addition to uniform sampling, our method is able to perform variable‐density sampling with small modifications. Finally, we also propose a new min‐conflict metric for variable‐density sampling which results in better adaptation of samples to the underlying importance field.     

Force-Directed Edge Bundling for Graph Visualization

Graphs depicted as node-link diagrams are widely used to show relationships between entities. However, node-link diagrams comprised of a large number of nodes and edges often suffer from visual clutter. The use of edge bundling remedies this and reveals high-level edge patterns. Previous methods require the graph to contain a hierarchy for this, or they construct a control mesh to guide the edge bundling process, which often results in bundles that show considerable variation in curvature along the overall bundle direction. We present a new edge bundling method that uses a self-organizing approach to bundling in which edges are modeled as flexible springs that can attract each other. In contrast to previous methods, no hierarchy is used and no control mesh. The resulting bundled graphs show significant clutter reduction and clearly visible high-level edge patterns. Curvature variation is furthermore minimized, resulting in smooth bundles that are easy to follow. Finally, we present a rendering technique that can be used to emphasize the bundling.     

Automatic Cinemagraph Portraits

Cinemagraphs are a popular new type of visual media that lie in‐between photos and video; some parts of the frame are animated and loop seamlessly, while other parts of the frame remain completely still. Cinemagraphs are especially effective for portraits because they capture the nuances of our dynamic facial expressions. We present a completely automatic algorithm for generating portrait cinemagraphs from a short video captured with a hand‐held camera. Our algorithm uses a combination of face tracking and point tracking to segment face motions into two classes: gross, large‐scale motions that should be removed from the video, and dynamic facial expressions that should be preserved. This segmentation informs a spatially‐varying warp that removes the large‐scale motion, and a graph‐cut segmentation of the frame into dynamic and still regions that preserves the finer‐scale facial expression motions. We demonstrate the success of our method with a variety of results and a comparison to previous work.