Composite Flow Maps

Flow maps are widely used to provide an overview of geospatial transportation data. Existing solutions lack the support for the interactive exploration of multiple flow components at once. Flow components are given by different materials being transported, different flow directions, or by the need for comparing alternative scenarios. In this paper, we combine flows as individual ribbons in one composite flow map. The presented approach can handle an arbitrary number of sources and sinks. To avoid visual clutter, we simplify our flow maps based on a force‐driven algorithm, accounting for restrictions with respect to application semantics. The goal is to preserve important characteristics of the geospatial context. This feature also enables us to highlight relevant spatial information on top of the flow map such as traffic conditions or accessibility. The flow map is computed on the basis of flows between zones. We describe a method for auto‐deriving zones from geospatial data according to application requirements. We demonstrate the method in real‐world applications, including transportation logistics, evacuation procedures, and water simulation. Our results are evaluated with experts from corresponding fields.     

一种基于空间距离的边绑定方法

边绑定方法是近年来信息可视化领域的一个研究热点,解决图可视化中由于边的 过多交叉而引起的视觉混乱问题。在现有的边绑定方法中,基于路径构建的算法通常能够在时 间和绑定效果上获得较好的结果,其中基于边聚类和骨架构建路径的方法具有良好的数据表达 能力。在此基础上,提出一种基于空间距离的边绑定的方法,结合边的空间距离和骨架生成的 特点,在实现边绑定功能的同时针对以往基于骨架路径的方法做了进一步的改进。实验结果表 明,该方法相比原方法有着更高的时间效率,对数据的细节保留更为合理,消除了原方法存在 的绑定过度的问题,简化原方法的计算过程,并避免奇异性问题,更为实用。     

Vortex visualization in ultra low Reynolds number insect flight

We present the visual analysis of a biologically inspired CFD simulation of the deformable flapping wings of a dragonfly as it takes off and begins to maneuver, using vortex detection and integration-based flow lines. The additional seed placement and perceptual challenges introduced by having multiple dynamically deforming objects in the highly unsteady 3D flow domain are addressed. A brief overview of the high speed photogrammetry setup used to capture the dragonfly takeoff, parametric surfaces used for wing reconstruction, CFD solver and underlying flapping flight theory is presented to clarify the importance of several unsteady flight mechanisms, such as the leading edge vortex, that are captured visually. A novel interactive seed placement method is used to simplify the generation of seed curves that stay in the vicinity of relevant flow phenomena as they move with the flapping wings. This method allows a user to define and evaluate the quality of a seed's trajectory over time while working with a single time step. The seed curves are then used to place particles, streamlines and generalized streak lines. The novel concept of flowing seeds is also introduced in order to add visual context about the instantaneous vector fields surrounding smoothly animate streak lines. Tests show this method to be particularly effective at visually capturing vortices that move quickly or that exist for a very brief period of time. In addition, an automatic camera animation method is used to address occlusion issues caused when animating the immersed wing boundaries alongside many geometric flow lines. Each visualization method is presented at multiple time steps during the up-stroke and down-stroke to highlight the formation, attachment and shedding of the leading edge vortices in pairs of wings. Also, the visualizations show evidence of wake capture at stroke reversal which suggests the existence of previously unknown unsteady lift generation mechanisms that are unique to quad wing insects.     

Flow charts: visualization of vector fields on arbitrary surfaces

We introduce a novel flow visualization method called Flow Charts, which uses a texture atlas approach for the visualization of flows defined over curved surfaces. In this scheme the surface and its associated flow are segmented into overlapping patches which are then parameterized and packed in the texture domain. This scheme allows accurate particle advection across multiple charts in the texture domain, providing a flexible framework that supports various flow visualization techniques. The use of surface parameterization enables flow visualization techniques requiring the global view of the surface over long time spans, such as Unsteady Flow LIC (UFLIC), particle-based Unsteady Flow Advection-Convolution (UFAC), or dye advection. It also prevents visual artifacts normally associated with view-dependent methods. Represented as textures, Flow Charts can be naturally integrated into GPU flow visualization techniques for interactive performance.     

Flow Curves: an Intuitive Interface for Coherent Scene Deformation

Effective composition in visual arts relies on the principle of movement, where the viewer's eye is directed along subjective curves to a center of interest. We call these curves subjective because they may span the edges and/or center‐lines of multiple objects, as well as contain missing portions which are automatically filled by our visual system. By carefully coordinating the shape of objects in a scene, skilled artists direct the viewer's attention via strong subjective curves. While traditional 2D sketching is a natural fit for this task, current 3D tools are object‐centric and do not accommodate coherent deformation of multiple shapes into smooth flows. We address this shortcoming with a new sketch‐based interface called Flow Curves which allows coordinating deformation across multiple objects. Core components of our method include an understanding of the principle of flow, algorithms to automatically identify subjective curve elements that may span multiple disconnected objects, and a deformation representation tailored to the view‐dependent nature of scene movement. As demonstrated in our video, sketching flow curves requires significantly less time than using traditional 3D editing workflows.     

Openflow Based Dynamic Flow Scheduling with Multipath for Data Center Networks

The routing mechanism in Data Center networks can affect network performance and latency significantly. Hash-based method, such as ECMP (Equal-Cost Multi-Path), has been widely used in Data Center networks to fulfill the requirement of load balance. However, ECMP statically maps one flow to a path by a hash method, which results in some paths overloaded while others remain underutilized. Some dynamic flow scheduling schemes choose the most underutilized link as the next hop to better utilize the network bandwidth, while these schemes lacks of utilizing the global state of the network. To achieve high bandwidth utilization and low latency, we present a dynamic flow scheduling mechanism based on OpenFlow protocol which enables monitoring the global network information by a centralized controller. Depending on the network statistics obtained by the OpenFlow controller, the routing algorithm chooses the best path for the flow. Because there are two kinds of flows in a Data Center, short-lived flows and long-lived flows, we proposed two different algorithms for them. The implementation uses pox as OpenFlow controller and mininet as the network emulator. The evaluation results demonstrate that our dynamic flow scheduling algorithm is effective and can achieve high link utilization.     

Towards computational discourse analysis: A methodology for mining Twitter backchanneling conversations

In this paper we present a methodology to analyze and visualize streams of Social Media messages and apply it to a case in which Twitter is used as a backchannel, i.e. as a communication medium through which participants follow an event in the real world as it unfolds. Unlike other methods based on social networks or theories of information diffusion, we do not assume proximity or a pre-existing social structure to model content generation and diffusion by distributed users; instead we refer to concepts and theories from discourse psychology and conversational analysis to track online interaction and discover how people collectively make sense of novel events through micro-blogging. In particular, the proposed methodology extracts concept maps from twitter streams and uses a mix of sentiment and topological metrics computed over the extracted concept maps to build visual devices and display the conversational flow represented as a trajectory through time of automatically extracted topics. We evaluated the proposed method through data collected from the analysis of Twitter users’ reactions to the March 2015 Apple Keynote during which the company announced the official launch of several new products.     

New Visual Invariants for Terrain Navigation Without 3D Reconstruction

For autonomous vehicles to achieve terrain navigation, obstacles must be discriminated from terrain before any path planning and obstacle avoidance activity is undertaken. In this paper, a novel approach to obstacle detection has been developed. The method finds obstacles in the 2D image space, as opposed to 3D reconstructed space, using optical flow. Our method assumes that both nonobstacle terrain regions, as well as regions with obstacles, will be visible in the imagery. Therefore, our goal is to discriminate between terrain regions with obstacles and terrain regions without obstacles. Our method uses new visual linear invariants based on optical flow. Employing the linear invariance property, obstacles can be directly detected by using reference flow lines obtained from measured optical flow. The main features of this approach are: (1) 2D visual information (i.e., optical flow) is directly used to detect obstacles; no range, 3D motion, or 3D scene geometry is recovered; (2) knowledge about the camera-to-ground coordinate transformation is not required; (3) knowledge about vehicle (or camera) motion is not required; (4) the method is valid for the vehicle (or camera) undergoing general six-degree-of-freedom motion; (5) the error sources involved are reduced to a minimum, because the only information required is one component of optical flow. Numerous experiments using both synthetic and real image data are presented. Our methods are demonstrated in both ground and air vehicle scenarios.     

基于区间分类的螺旋图可视化边绑定方法

在时序数据可视化领域,螺旋图是一种常用的可视化方法,它既能将多个阶段的数据同时展示在一个平面空间内,又能在有限的空间内展示任意时长的数据。针对现有的螺旋图可视化方法在展示大量的时间序列数据时会出现因螺旋线交叉而导致视觉杂乱的问题,研究螺旋图可视化方法意义非凡。首先将状态圆环上的数据点进行分类;然后在相邻的状态圆环之间设置虚拟绑定圆环,通过边绑定的函数将状态圆环上的数据点映射到其对应的虚拟绑定圆环上;最后在状态圆环与其对应的虚拟绑定圆环之间绘制Bézier曲线,在虚拟绑定圆环与虚拟绑定圆环之间绘制螺旋线,从而实现边绑定的效果。实验结果表明,该边绑定算法能够有效地对大规模数据进行可视化,并能有效地缓解视觉杂乱的问题。     

On the Parameterized Complexity of Layered Graph Drawing

We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for fixed h) have bounded pathwidth. We then use a path decomposition as the basis for a linear-time algorithm to decide if a graph has a crossing-free h-layer drawing (for fixed h). This algorithm is extended to solve related problems, including allowing at most k crossings, or removing at most r edges to leave a crossing-free drawing (for fixed k or r). If the number of crossings or deleted edges is a non-fixed parameter then these problems are NP-complete. For each setting, we can also permit downward drawings of directed graphs and drawings in which edges may span multiple layers, in which case either the total span or the maximum span of edges can be minimized. In contrast to the Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers. Research initiated at the International Workshop on Fixed Parameter Tractability in Graph Drawing, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 9–16, 2001, organized by S. Whitesides. Research of Canada-based authors is supported by NSERC; research of Quebec-based authors is also supported by a grant from FCAR. Research of D.R. Wood completed while visiting McGill University. Research of G. Liotta supported by CNR and MURST.     

Topology optimization of channel flow problems

This paper describes a topology design method for simple two-dimensional flow problems. We consider steady, incompressible laminar viscous flows at low-to-moderate Reynolds numbers. This makes the flow problem nonlinear and hence a nontrivial extension of the work of Borrvall and Petersson (2003).Further, the inclusion of inertia effects significantly alters the physics, enabling solutions of new classes of optimization problems, such as velocity-driven switches, that are not addressed by the earlier method. Specifically, we determine optimal layouts of channel flows that extremize a cost function which measures either some local aspect of the velocity field or a global quantity, such as the rate of energy dissipation. We use the finite element method to model the flow, and we solve the optimization problem with a gradient-based math-programming algorithm that is driven by analytical sensitivities. Our target application is optimal layout design of channels in fluid network systems. Using concepts borrowed from topology optimization of compliant mechanisms in solid mechanics, we introduce a method for the synthesis of fluidic components, such as switches, diodes, etc.     

Autonomic load balancing of flow monitors

In monitoring flows at routers for flow analysis or deep packet inspection, the monitor calculates hash values from the flow ID of each packet arriving at the input port of the router. Therefore, the monitors must update the flow table at the transmission line rate, so high-speed and high-cost memory, such as SRAM, is used for the flow table. This requires the monitors to limit the monitoring target to just some of the flows. However, if the monitors randomly select the monitoring targets, multiple routers on the route will sometimes monitor the same flow, or no monitors will monitor a flow. To maximize the number of monitored flows in the entire network, the monitors must select the monitoring targets while maintaining a balanced load among them. We propose an autonomous load-balancing method where monitors exchange information on monitor load only with adjacent monitors. Numerical evaluations using the actual traffic matrix of Internet2 show that the proposed method improves the total monitored flow count by about 50% compared with that of independent sampling. Moreover, we evaluate the load-balancing effect on 36 backbone networks of commercial ISPs.     

Visual SLAM for Flying Vehicles

The ability to learn a map of the environment is important for numerous types of robotic vehicles. In this paper, we address the problem of learning a visual map of the ground using flying vehicles. We assume that the vehicles are equipped with one or two low-cost downlooking cameras in combination with an attitude sensor. Our approach is able to construct a visual map that can later on be used for navigation. Key advantages of our approach are that it is comparably easy to implement, can robustly deal with noisy camera images, and can operate either with a monocular camera or a stereo camera system. Our technique uses visual features and estimates the correspondences between features using a variant of the progressive sample consensus (PROSAC) algorithm. This allows our approach to extract spatial constraints between camera poses that can then be used to address the simultaneous localization and mapping (SLAM) problem by applying graph methods. Furthermore, we address the problem of efficiently identifying loop closures. We performed several experiments with flying vehicles that demonstrate that our method is able to construct maps of large outdoor and indoor environments.      

Video-based running water animation in Chinese painting style

This paper presents a novel algorithm for synthesizing animations of running water,such as water-falls 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.     

基于流的P2P网络特性模型

利用从实际网络获得的数据,提出基于流的P2P网络特性模型。采用图形方法和概述统计识别样本所服从的分布族,使用可视化图形方法和假设检验方法对统计分布模型进行拟合优度检验。分析结果表明,流持续时间的分布模型可以用对数正态分布精确表示,混合对数正态分布可以有效拟合流长和流传输速率分布的分布模型,且P2P应用的流长和流持续时间没有高度相关的关系。     

Visualizing particle/flow structure interactions in the small bronchial tubes

Particle deposition in the small bronchial tubes (generations six through twelve) is strongly influenced by the vortex-dominated secondary flows that are induced by axial curvature of the tubes. In this paper, we employ particle destination maps in conjunction with two-dimensional, finite-time Lyapunov exponent maps to illustrate how the trajectories of finite-mass particles are influenced by the presence of vortices. We consider two three-generation bronchial tube models: a planar, asymmetric geometry and a non-planar, asymmetric geometry. Our visualizations demonstrate that these techniques, coupled with judiciously seeded particle trajectories, are effective tools for studying particle/flow structure interactions.     

Taking an object-centric view on dynamic information with object flow analysis

A large body of research analyzes the runtime execution of a system to extract abstract behavioral views. Those approaches primarily analyze control flow by tracing method execution events or they analyze object graphs of heap memory snapshots. However, they do not capture how objects are passed through the system at runtime. We refer to the exchange of objects as the object flow, and we claim that it is necessary to analyze object flows if we are to understand the runtime of an object-oriented application. We propose and detail object flow analysis, a novel dynamic analysis technique that takes this new information into account. To evaluate its usefulness, we present a visual approach that allows a developer to study classes and components in terms of how they exchange objects at runtime. We illustrate our approach on three case studies.     

Harvesting maps on the web

Maps are one of the most valuable documents for gathering geospatial information about a region. Yet, finding a collection of diverse, high-quality maps is a significant challenge because there is a dearth of content-specific metadata available to identify them from among other images on the Web. For this reason, it is desirous to analyze the content of each image. The problem is further complicated by the variations between different types of maps, such as street maps and contour maps, and also by the fact that many high-quality maps are embedded within other documents such as PDF reports. In this paper, we present an automatic method to find high-quality maps for a given geographic region. Not only does our method find documents that are maps, but also those that are embedded within other documents. We have developed a Content-Based Image Retrieval (CBIR) approach that uses a new set of features for classification in order to capture the defining characteristics of a map. This approach is able to identify all types of maps irrespective of their subject, scale, and color in a highly scalable and accurate way. Our classifier achieves an F1-measure of 74%, which is an 18% improvement over the previous work in the area.     

Dynamic Insets for Context‐Aware Graph Navigation

Maintaining both overview and detail while navigating in graphs, such as road networks, airline route maps, or social networks, is difficult, especially when targets of interest are located far apart. We present a navigation technique called Dynamic Insets that provides context awareness for graph navigation. Dynamic insets utilize the topological structure of the network to draw a visual inset for off‐screen nodes that shows a portion of the surrounding area for links leaving the edge of the screen. We implement dynamic insets for general graph navigation as well as geographical maps. We also present results from a set of user studies that show that our technique is more efficient than most of the existing techniques for graph navigation in different networks.