Problems related to pickup and delivery are common with on-demand ride-sharing services. Passengers request rides through mobile apps, and drivers pick them up at designated locations and take them to their destinations. Although this process efficiently transports many passengers with a limited number of vehicles, it usually results in an NP-hard problem involving multiple travel requests from different locations. This paper presents an approach to simulating such services interactively by solving optimization problems to properly assign sets of requests to vehicles. Our approach successfully concatenates pickup and drop-off points on vehicle routes by enumerating their permutations. We randomly sample possible permutations of visit locations to approximately solve NP-hard routing problems within a specific time frame. Our interactive interface allows us to reassign additional on-demand travel requests to vehicles at any time, accommodating dynamic pickup and delivery issues.

Abstract Aggregation, as an operation of cartographic generalization, provides an effective means of abstracting the configuration of building features by combining them according to the scale reduction of the 2D map. Automating this design process effectively helps professional cartographers design both paper and digital maps, but finding the best aggregation result from the numerous combinations of building features has been a challenge. This paper presents a novel approach to assist cartographers in interactively designing the aggregation of building features in scale‐aware map visualization. Our contribution is to provide an appropriate set of candidates for the cartographer to choose from among a limited number of possible combinations of building features. This is achieved by collecting locally optimal solutions that emerge in the course of aggregation operations, formulated as a label cost optimization problem. Users can also explore better aggregation results by interactively adjusting the design parameters to update the set of possible combinations, along with an operator to force the combination of manually selected building features. Each cluster of aggregated building features is tightly enclosed by a concave hull, which is later adaptively simplified to abstract its boundary shapes. Experimental design examples and evaluations by expert cartographers demonstrate the feasibility of the proposed approach to interactive aggregation.

Understanding the degree of satisfaction for visitors has been a key factor in selecting attractive collections and designing appealing layouts in art galleries and museums. Although monitoring the actual spatiotemporal behaviors of visitors is essential for this purpose, introducing an expensive monitoring system would impose a heavy burden on the financial management and leads to unwanted restrictions on the layout design in the exhibition rooms. This paper presents an approach to visualizing the spatiotemporal changes in the maps of visitors' interest with a system of installed single-board computers such as Raspberry Pi devices. Employing single-board computers as IoT sensors facilitates monitoring systems to maximally covers the entire exhibition space while keeping the associated installation cost and power consumption sufficiently low. Our approach for this novel system organization begins by first detecting individuals from camera images using machine learning techniques and reconstructing their spatial positions from perspective views. Kernel density estimation was employed to represent the distribution of interest across the entire exhibition room as a continuous function by respecting the reconstructed positions of visitors. This allowed the use of heatmaps to visualize the changes in the map of interest reflecting the travel history of individual visitors and the accumulated distribution of interest over a specific period. Experimental results from eight months of measurement data demonstrate the capability of the proposed approach, including meaningful trends that reveal how the layout of collections attracted visitors to the exhibitions.

Color is an essential factor that influences human perception, and thus, the proper selection of color sets is crucial in creating informative and appealing visual content. Furthermore, the choice of such color palettes often reflects the underlying emotional intention of creators, especially when they want to introduce specific affective styles. This paper presents a color palette recommendation system that facilitates preferred colors and affective expressions in visual content. This is accomplished by introducing non-negative tensor factorization (NTF), which extends the conventional matrix-based collaborative filtering for recommending items through ratings of multiple users. In our approach, we composed a rating tensor that constitutes the scores for colors in terms of affective factors provided by participants in the user study. With this rating tensor, we explored the meaningful relation between affective expression and color preference. Our experiments exposed that we can successfully apply a tensor-based approach to recommending convincing sets of colors in several possible cases by predicting the underlying emotional intentions in the visual content design.

The bag-of-features (BoF) model is the standard platform for image retrieval systems and successfully extended to systems for exploring 3D models through their projected views. However, we need a large number of views for each 3D model to achieve shape retrieval systems with high accuracy, which results in increased data storage and long computation time for shape comparison. This paper presents an approach for reducing projected images in such image-based shape retrieval by aggregating views of each 3D model. Our approach begins by discovering a proper metric for evaluating dissimilarity between 3D models by referring to their high-dimensional feature vectors obtained from the BoF model. We then introduce a variant of the k-means clustering method to identify the representative views of each 3D model, given the number of such essential views. Finally, we adjust the degree of such view aggregation by assessing the number of plane symmetries for each 3D model. We test our approach with a dataset containing 200 3D models and we learn that we can reduce the number of views to less than 10% while limiting the degradation of accuracy to approximately 5%.

Abstract The Fukushima nuclear accident of 2011 raised awareness of the importance of radioactive deposition processes, especially for proposing aerosol measures against possible air pollution. However, identifying these types of processes is often difficult due to complicated terrains. This paper presents an application study for identifying radioactive deposition processes by taking advantage of visual interaction with topographic data. The idea is to visually investigate the correspondence of the spatial positions to the air dose rate along with relevant attributes. This is accomplished by composing scatterplots of pairwise attributes, onto which we project terrain areas to interactively find specific patterns of such attributes. We applied our approach to the analysis of air dose rate distribution data around the Fukushima nuclear plant after the accident. Our visualization technique clearly distinguished contamination areas derived from different deposition processes and thus is useful for elucidation of the deposition process.

Appropriate product placement significantly influences how viewers easily find their favorites, especially when they try to select products from digital signage displays. This increases the demand for dynamic categorization and optimal placement of items according to the context in which viewers explore their preferred choices. In this paper, we present an approach for optimizing the placement of items by respecting the underlying context in the search for favorites. Our approach starts with formulating the static placement of items as a constrained optimization problem, in which we incorporate design rules that highlight the underlying categorization of the items. We then extend this idea to accommodate dynamic placement according to the context in which users explore their preferred choices. This is accomplished by adaptively adjusting the priority of each item based on the distribution of visual attention obtained by an eye-tracking device. In particular, we construct a context map for understanding the relationship between the items by taking advantage of topic-based text mining techniques. We provide several examples of gaze-based interaction to demonstrate the capability of the proposed approach, which is followed by a discussion on possible directions for future research.

Transit maps are designed to present information for using public transportation systems, such as urban railways. Creating a transit map is a time-consuming process, which requires iterative information selection, layout design, and usability validation, and thus maps cannot easily be customised or updated frequently. To improve this, scientists investigate fully- or semi-automatic techniques in order to produce high quality transit maps using computers and further examine their corresponding usability. Nonetheless, the quality gap between manually-drawn maps and machine-generated maps is still large. To elaborate the current research status, this state-of-the-art report provides an overview of the transit map generation process, primarily from Design, Machine, and Human perspectives. A systematic categorisation is introduced to describe the design pipeline, and an extensive analysis of perspectives is conducted to support the proposed taxonomy. We conclude this survey with a discussion on the current research status, open challenges, and future directions.

The consistent arrangement of map features in accordance with the map scale has recently been technically important in digital cartographic generalization. This is primarily due to the recent demand for informative mapping systems, especially for use in smartphones and tablets. However, such sophisticated generalization has usually been conducted manually by expert cartographers and thus results in a time-consuming and error-prone process. In this paper, we focus on the displacement process within cartographic generalization and formulate them as a constrained optimization problem to provide an associated algorithm implementation and its effective solution. We first identify the underlying spatial relationships among map features, such as points and lines, on each map scale as constraints and optimize the cost function that penalizes excessive displacement of the map features in terms of the map scale. Several examples are also provided to demonstrate that the proposed approach allows us to maintain consistent mapping regardless of changes to the map scale.

Abstract A set diagram represents the membership relation among data elements. It is often visualized as secondary information on top of primary information, such as the spatial positions of elements on maps and charts. Visualizing the temporal evolution of such set diagrams as well as their primary features is quite important; however, conventional approaches have only focused on the temporal behavior of the primary features and do not provide an effective means to highlight notable transitions within the set relationships. This paper presents an approach for generating a stepwise animation between set diagrams by decomposing the entire transition into atomic changes associated with individual data elements. The key idea behind our approach is to optimize the ordering of the atomic changes such that the synthesized animation minimizes unwanted set occlusions by considering their depth ordering and reduces the gaze shift between two consecutive stepwise changes. Experimental results and a user study demonstrate that the proposed approach effectively facilitates the visual identification of the detailed transitions inherent in dynamic set diagrams.

We develop a novel method printing complex self-folding geometries. We demonstrated that with a desktop fused deposition modeling (FDM) 3D printer, off-the-shelf printing filaments and a design editor, we can print flat thermoplastic composites and trigger them to self-fold into 3D with arbitrary bending angles. This is a suitable technique, called Thermorph, to prototype hollow and foldable 3D shapes without losing key features. We describe a new curved folding origami design algorithm, compiling given arbitrary 3D models to 2D unfolded models in G-Code for FDM printers. To demonstrate the Thermorph platform, we designed and printed complex self-folding geometries (up to 70 faces), including 15 self-curved geometric primitives and 4 self-curved applications, such as chairs, the simplified Stanford Bunny and flowers. Compared to the standard 3D printing, our method saves up to 60% - 87% of the printing time for all shapes chosen.

We present an approach to synthesizing tag cloud ("wordle"s) maps that produce illusionary visual depth fields based on stereoscopic imaging. By using a 3D scalar field (such as elevation or weather data) as input, the synthesized map yields a visual illusion that suitably simulates the 3D shape of the field; this is done by applying stereoscopic rendering effects to individual word tags. In the generated tag cloud maps, we employed chromastereoptic rendering as a mechanism for controlling the rendering styles of respective place names. Our technical contribution also lies in the formulation for optimizing the layout of place names in a tag cloud by using a genetic algorithm, which effectively simulates the 3D visual depth illusion of a given scalar field over the map domain. Design examples are presented to demonstrate the capability of the proposed approach followed by a discussion of the possible limitations.

Octilinear network layouts are commonly used as the schematic representation of railway maps due to their enhanced readability. However, it is often time-consuming to place station names on such railway maps by trial and error, especially within the limited labeling space around interchange stations. This paper presents a progressive approach to placing station names around stations in schematic railway maps for better automation of map labeling processes. The idea behind our approach is to annotate stations in dense downtown areas around the interchange stations first and then those in sparse rural areas. This is achieved by introducing the sum of geodesic distances over the railway network to identify the proper order in which to annotate stations. In the actual annotation process, we increase the labeling space around the railway network when necessary by progressively stretching railway line segments while retaining their original directions, which allows us to respect the original schematic layout as much as possible. We present several experimental results to demonstrate the effectiveness of the proposed approach, together with a discussion on parameter tuning in our formulation.

Datasets obtained through recently advanced measurement techniques tend to possess a large number of dimensions. This leads to explosively increasing computation costs for analyzing such datasets, thus making formulation and verification of scientific hypotheses very difficult. Therefore, an efficient approach to identifying feature subspaces of target datasets, that is, the subspaces of dimension variables or subsets of the data samples, is required to describe the essence hidden in the original dataset. This paper proposes a visual data mining framework for supporting semiautomatic data analysis that builds upon asymmetric biclustering to explore highly correlated feature subspaces. For this purpose, a variant of parallel coordinate plots, many-to-many parallel coordinate plots, is extended to visually assist appropriate selections of feature subspaces as well as to avoid intrinsic visual clutter. In this framework, biclustering is applied to dimension variables and data samples of the dataset simultaneously and asymmetrically. A set of variable axes are projected to a single composite axis while data samples between two consecutive variable axes are bundled using polygonal strips. This makes the visualization method scalable and enables it to play a key role in the framework. The effectiveness of the proposed framework has been empirically proven, and it is remarkably useful for many-to-many parallel coordinate plots.

Conventional force-directed algorithms are known as a common approach to aesthetically drawing networks while they still suffer from self-overlaps especially when the network nodes are annotated with text labels. Incorporating space partitioning techniques including Voronoi tessellation are often effective to spare enough space around each node while this may incur different artifacts such as unexpectedly long edges and edge overlaps. This paper presents an approach to resolving overlaps among node labels by adaptively blending multiple layout forces applied to the respective network nodes. This is accomplished by extending our previous approach for transforming the force-directed layout into that obtained through the centroidal Voronoi tessellation. Our technical contribution lies in a novel algorithm for smoothing blending ratios associated with the network nodes so that we can adaptively explore the reasonable balance between the two layouts independently for each node. Experimental results will present that our new approach can produce well-balanced distribution of node labels while maximally avoiding the aforementioned unwanted visual artifacts.

Image saliency is a biologically inspired concept for characterizing visual conspicuity of individual features in natural images, and provides us with a useful insight into the mechanism for directing instant visual attention from viewers. Nevertheless, this perceptual quality often remains to be further sophisticated especially for enhancing saliency in infographic images since they usually consist of relatively simple visual pattens that result in sharp image edges rather than smooth gradations in natural images. This paper presents a new approach to intentionally drawing visual attention for infographic images, in such a way that the corresponding important features naturally pop up in the image. The idea behind our approach is to introduce the concept of symmetry saliency for enhancing local symmetry inherent in such infographic images. This is accomplished by evaluating how much each image edge contributes to the symmetry saliency, and augmenting the corresponding image gradient in proportion to the amount of its contribution. The intensity field of the given image is then modulated with such enhanced image edges by solving the Poisson equation. Several examples together with statistics obtained through a user study demonstrate that our proposed approach successfully improves the readability of infographic images and effectively attracts visual attention to intended regions of interest.

The papers in this special section were presenteda at the 2015 IEEE Pacific Visualization Symposium (PacificVis’15) that was held in Hangzhou from April 14 to 17, 2015.

Scalar topology in the form of Morse theory has provided computational tools that analyze and visualize data from scientific and engineering tasks. Contracting isocontours to single points encapsulates variations in isocontour connectivity in the Reeb graph. For multivariate data, isocontours generalize to fibers-inverse images of points in the range, and this area is therefore known as fiber topology. However, fiber topology is less fully developed than Morse theory, and current efforts rely on manual visualizations. This paper presents how to accelerate and semi-automate this task through an interface for visualizing fiber singularities of multivariate functions R³ → R². This interface exploits existing conventions of fiber topology, but also introduces a 3D view based on the extension of Reeb graphs to Reeb spaces. Using the Joint Contour Net, a quantized approximation of the Reeb space, this accelerates topological visualization and permits online perturbation to reduce or remove degeneracies in functions under study. Validation of the interface is performed by assessing whether the interface supports the mathematical workflow both of experts and of less experienced mathematicians.

Exploring feature subspaces is one of promising approaches to analyzing and understanding the important patterns in multivariate data. If relying too much on effective enhancements in manual interventions, the associated results depend heavily on the knowledge and skills of users performing the data analysis. This paper presents a novel approach to extracting feature subspaces from multivariate data by incorporating biclustering techniques. The approach has been maximally automated in the sense that highly-correlated dimensions are automatically grouped to form subspaces, which effectively supports further exploration of them. A key idea behind our approach lies in a new mathematical formulation of asymmetric biclustering, by combining spherical k-means clustering for grouping highly-correlated dimensions, together with ordinary k-means clustering for identifying subsets of data samples. Lower-dimensional representations of data in feature subspaces are successfully visualized by parallel coordinate plot, where we project the data samples of correlated dimensions to one composite axis through dimensionality reduction schemes. Several experimental results of our data analysis together with discussions will be provided to assess the capability of our approach.

Visual interaction with networks have been promising in the sense that we can successfully elucidate underlying relationships hidden behind complicated mutual relationships such as co-authorship networks, product co purchasing networks, and scale-free social networks. However, it is still burdensome to alleviate visual clutter arising from overlaps among node labels especially in such interactive environments as the networks become dense in terms of the topological connectivity. This paper presents a novel approach for dynamically rearranging the network layouts by incorporating centroidal Voronoi tessellation for better readability of node labels. Our idea is to smoothly transform the network layouts obtained through the conventional force-directed algorithm to that produced by the centroidal Voronoi tessellation to seek a plausible compromise between them. We also incorporated the Chebyshev distance metric into the centroidal Voronoi tessellation while adaptively adjusting the aspect ratios of the Voronoi cells so that we can place rectangular labels compactly over the network nodes. Finally, we applied the proposed approach to relatively large networks to demonstrate the feasibility of our formulation especially in interactive environments.

Schematic metro maps provide an effective means of simplifying the geographical configuration of public rapid transportation systems. Nonetheless, travelers still find it difficult to identify routes of a specific topology on the maps because it is usually hidden behind the conventional octilinear layout of the entire map. In this paper, we present an approach to designing schematic maps with loop lines, which are drawn as circles together with annotation labels for guiding different traveling purposes. Our idea here is to formulate the aesthetic criteria as mathematical constraints in the mixed-integer programming model, which allows us to either align stations on the loop line at a grid if they are interchange stations or noninterchange stations on a circle otherwise. We then distribute the annotation labels associated with stations on the loop line evenly to the four side boundary of the map domain in order to make full use of the annotation space, while maximally avoiding intersections between leader lines and the metro network by employing a flow network algorithm. Finally, we present several experimental results generated by our prototype system to demonstrate the feasibility of the proposed approach.

The papers in this special section present extended versions of four selected papers from the 2014 IEEE Pacific Visualization Symposium (PacificVis’14).

The demand for interactively designing the image feature space has been increasing due to the ongoing need for image retrieval, recognition, and labeling. Although conventional methods provide an interface for locally rearranging such a feature space, category-level global manipulation is still missing and thus manually rearranging the overall image categorization usually requires a time-consuming task. This paper presents a novel approach to exploring images in the database through the manipulation of bi-level feature space representations, where the upper-and lower-level representations characterize the global categories and local features of the images, respectively. In this approach, the upper-level space describes similarity relationship among the underlying categories extracted from the bag-of-features model, while the lower-level space encodes the closeness between a pair of images within the same category. The key idea behind this approach is to associate the relationship between the two feature spaces with a two-layered graph representation and project it onto 2D screen space using pivot MDS for user manipulation. Experimental results are provided to demonstrate that our approach allows users to understand the entire structure of the given image dataset and reorganize the layout according to their preference both locally and globally.

Parallel coordinates is well-known as a popular tool for visualizing the underlying relationships among variables in high-dimension datasets. However, this representation still suffers from visual clutter arising from intersections among poly line plots especially when the number of data samples and their associated dimension become high. This paper presents a method of alleviating such visual clutter by contracting multiple axes through the analysis of correlation between every pair of variables. In this method, we first construct a graph by connecting axis nodes with an edge weighted by data correlation between the corresponding pair of dimensions, and then reorder the multiple axes by projecting the nodes onto the primary axis obtained through the spectral graph analysis. This allows us to compose a dendrogram tree by recursively merging a pair of the closest axes one by one. Our visualization platform helps the visual interpretation of such axis contraction by plotting the principal component of each data sample along the composite axis. Smooth animation of the associated axis contraction and expansion has also been implemented to enhance the visual readability of behavior inherent in the given high-dimensional datasets.

The bag-of-features models is one of the most popular and promising approaches for extracting the underlying semantics from image databases. However, the associated image categorization based on machine learning techniques may not convince us of its validity since we cannot visually verify how the images have been classified in the high-dimensional image feature space. This paper aims at visually rearrange the images in the projected feature space by taking advantage of a set of representative features called visual words obtained using the bag-of-features model. Our main idea is to associate each image with a specific number of visual words to compose a bipartite graph, and then lay out the overall set of images using anchored map representation in which the ordering of anchor nodes is optimized through a genetic algorithm. For handling relatively large image datasets, we adaptively merge a pair of most similar images one by one to conduct the hierarchical clustering through the similarity measure based on the weighted Jaccard coefficient. Voronoi partitioning has been also incorporated into our approach so that we can visually identify the image categorization based on support vector machine. Experimental results are finally presented to demonstrate that our visualization framework can effectively elucidate the underlying relationships between images and visual words through the anchored map representation.

In composing hand-drawn 3D urban maps, the most common design problem is to avoid overlaps between geographic features such as roads and buildings by displacing them consistently over the map domain. Nonetheless, automating this map design process is still a challenging task because we have to maximally retain the 3D depth perception inherent in pairs of parallel lines embedded in the original layout of such geographic features. This paper presents a novel approach to disoccluding important geographic features when creating 3D urban maps for enhancing their visual readability. This is accomplished by formulating the design criteria as a constrained optimization problem based on the linear programming approach. Our mathematical formulation allows us to systematically eliminate occlusions of landmark roads and buildings, and further controls the degree of local 3D map deformation by devising an objective function to be minimized. Various design examples together with a user study are presented to demonstrate the robustness and feasibility of the proposed approach.

We have developed a hybrid wind tunnel, where 2D measurement-integrated (MI) simulation, which utilizes actual data acquired from real air flow behind a square cylinder, plays an important role in improving the accuracy of the numerical analysis. The wind tunnel requires an accompanying visual analysis tool with which we can effectively peer into the relationships between the actual and simulated flow fields. In this paper, we attempt to exploit an augmented reality display to that end. The basic idea is to superimpose the computationally-visualized MI simulated pressure field onto the actual flow velocity structure physically-visualized with oil misttraced streaklines instantaneously. Spatial registration of these two visual sources is rather straight-forward since the fixed cylinder of the wind tunnel is easily identified, whereas visualizing the MI simulated pressure field can be characterized with a sophisticated scheme based on differential topology. Considering the fact that vortex centers are located at local minima in the pressure field, and each minimum is surrounded by a derived topological feature called ridge cycle, we can colorize the field adaptively and keep track of Karman vortex streets robustly, regardless of drastic change in the Reynolds number of the flow field.

Metro maps with thumbnail photographs serve as common travel guides for providing sufficient information to meet the requirements of travelers in the cities. However, conventional methods attempt to minimize the total distance between stations and labels while maximizing the number of the labels rather than further taking into account the overall balance of the spatial distribution of labels. This paper presents an entropy-based approach for effectively annotating large annotation labels sufficiently close to the metro stations. Our idea is to decompose the entire labeling space intro regions bounded by the metro lines, and then further partition each region into Voronoi cells, each of which is reserved for a station to be annotated. This is accomplished by incorporating a new genetic-based optimization, while the fitness of the decomposition is evaluated by the entropy of the relative coverage ratios of such Voronoi cells. We also include several design examples to demonstrate that the proposed approach successfully distributes large labels around the metro network with minimal user intervention.

Abstract Annotating metro maps with thumbnail photographs is a commonly used technique for guiding travelers. However, conventional methods usually suffer from small labeling space around the metro stations especially when they are interchange stations served by two or more metro lines. This paper presents an approach for aesthetically designing schematic metro maps while ensuring effective placement of large annotation labels that are sufficiently close to their corresponding stations. Our idea is to distribute such labels in a well‐balanced manner to labeling regions around the metro network first and then adjust the lengths of metro line and leader line segments, which allows us to fully maximize the space coverage of the entire annotated map. This is accomplished by incorporating additional constraints into the conventional mixed‐integer programming formulation, while we devised a three‐step algorithm for accelerating the overall optimization process. We include several design examples to demonstrate the spatial efficiency of the map layout generated using the proposed approach through minimal user intervention.

Abstract When providing travel guides for a specific route in a metro network, we often place the route around the center of the map and annotate stations on the route with thumbnail photographs. Nonetheless, existing methods do not offer an effective means of customizing the network layout in order to accommodate such large annotation labels while preserving its planar embedding. This paper presents a new approach for designing the metro map layout in order to annotate stations on a specific travel route with large annotation labels. Our idea is to elongate the travel route to be straight along the centerline of the map so that we can systematically annotate such stations with external labels. This is accomplished by extending the conventional mixed‐integer programming technique for computing octilinear layouts where orientations inherent to the metro line segments are plausibly rearranged. The stations are then connected with external labels through leaders while minimizing intersections with metro lines for enhancing visual clarity. We present several design examples of metro maps and user studies to demonstrate that the proposed aesthetic criteria successfully direct viewers’ attention to specific travel routes.

Abstract 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.

Abstract 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.

Crowd simulation has been an important research field due to its diverse range of applications that include film production, military simulation, and urban planning. A challenging problem is to provide simple yet effective control over captured and simulated crowds to synthesize intended group motions. We present a new method that blends existing crowd data to generate a new crowd animation. The new animation can include an arbitrary number of agents, extends for an arbitrary duration, and yields a natural-looking mixture of the input crowd data. The main benefit of this approach is to create new spatio-temporal crowd behavior in an intuitive and predictable manner. It is accomplished by introducing a morphable crowd model that allows us to encode the formations and individual trajectories in crowd data. Then, its original spatio-temporal behavior can be reconstructed and interpolated at an arbitrary scale using our morphable model.

We present an intuitive and straightforward method for synthesizing videos by manipulating objects without 3D models. Video synthesis is still costly when generating the realistic motion of 3D models directly. The motion graph [Kovar et al. 2002] is a novel method that creates realistic and controllable motion from examples, while its associated motion data must be obtained beforehand using capture devices that are still expensive. On the other hand, Schödl et al. [2002] defined a video object segmented from a video frame as a "video sprite", and created controllable animations using 2D motion graphs, where the nodes correspond to the extracted video sprites and the edges represent temporal transitions between similar sprites. While their approach can create animations without 3D models, users can only control positions or animation paths of objects. Our primary contribution lies in a novel 2D motion graph search algorithm by feature points tracking, which enables us to control detailed motions of a video object through the screen space directly.

Abstract Given a pair of keyframe formations for a group consisting of multiple individuals, we present a spectral‐based approach to smoothly transforming a source group formation into a target formation while respecting the clusters of the involved individuals. The proposed method provides an effective means for controlling the macroscopic spatiotemporal arrangement of individuals for applications such as expressive formations in mass performances and tactical formations in team sports. Our main idea is to formulate this problem as rotation interpolation of the eigenbases for the Laplacian matrices, each of which represents how the individuals are clustered in a given keyframe formation. A stream of time‐varying formations is controlled by editing the underlying adjacency relationships among individuals as well as their spatial positions at each keyframe, and interpolating the keyframe formations while producing plausible collective behaviors over a period of time. An interactive system of editing existing group behaviors in a hierarchical fashion has been implemented to provide flexible formation control of large crowds.

Abstract A method for automatically generating a picture maze from two different images is introduced throughout this paper. The process begins with the extraction of salient contours and edge tangent flow information from the primary image in order to build the overall maze. Thus, mazes with passages flowing in the main edge directions and walls that effectively represent an abstract version of the primary image can be successfully created. Furthermore, our proposed approach makes possible the use of their solution path as a means of illustrating the main features of the secondary image, while attempting to keep its image motif concealed until the maze has been finally solved. The contour features and intensity of the secondary image are also incorporated into our method in order to determine the areas of the maze to be shaded by allowing the solution path to go through them. Moreover, an experiment has been conducted to confirm that solution paths can be successfully hidden from the participants in the mazes generated using our method.

A contour tree is a powerful tool for delineating the topological evolution of isosurfaces of a single-valued function, and thus has been frequently used as a means of extracting features from volumes and their time-varying behaviors. Several sophisticated algorithms have been proposed for constructing contour trees while they often complicate the software implementation especially for higher-dimensional cases such as time-varying volumes. This paper presents a simple yet effective approach to plotting in 3D space, approximate contour trees from a set of scattered samples embedded in the high-dimensional space. Our main idea is to take advantage of manifold learning so that we can elongate the distribution of high-dimensional data samples to embed it into a low-dimensional space while respecting its local proximity of sample points. The contribution of this paper lies in the introduction of new distance metrics to manifold learning, which allows us to reformulate existing algorithms as a variant of currently available dimensionality reduction scheme. Efficient reduction of data sizes together with segmentation capability is also developed to equip our approach with a coarse-to-fine analysis even for large-scale datasets. Examples are provided to demonstrate that our proposed scheme can successfully traverse the features of volumes and their temporal behaviors through the constructed contour trees.

Animating a crowd of characters is an important problem in computer graphics. The latest techniques enable highly realistic group motions to be produced in feature animation films and video games. However, interactive methods have not emerged yet for editing the existing group motion of multiple characters. We present an approach to editing group motion as a whole while maintaining its neighborhood formation and individual moving trajectories in the original animation as much as possible. The user can deform a group motion by pinning or dragging individuals. Multiple group motions can be stitched or merged to form a longer or larger group motion while avoiding collisions. These editing operations rely on a novel graph structure, in which vertices represent positions of individuals at specific frames and edges encode neighborhood formations and moving trajectories. We employ a shape-manipulation technique to minimize the distortion of relative arrangements among adjacent vertices while editing the graph structure. The usefulness and flexibility of our approach is demonstrated through examples in which the user creates and edits complex crowd animations interactively using a collection of group motion clips.

This paper presents a method for occlusion-free animation of geographical landmarks, and its application to a new type of car navigation system in which driving routes of interest are always visible. This is achieved by animating a nonperspective image where geographical landmarks such as mountain tops and roads are rendered as if they are seen from different viewpoints. The technical contribution of this paper lies in formulating the nonperspective terrain navigation as an inverse problem of continuously deforming a 3D terrain surface from the 2D screen arrangement of its associated geographical landmarks. The present approach provides a perceptually reasonable compromise between the navigation clarity and visual realism where the corresponding nonperspective view is fully augmented by assigning appropriate textures and shading effects to the terrain surface according to its geometry. An eye tracking experiment is conducted to prove that the present approach actually exhibits visually-pleasing navigation frames while users can clearly recognize the shape of the driving route without occlusion, together with the spatial configuration of geographical landmarks in its neighborhood.

Optimal viewpoint selection is an important task because it considerably influences the amount of information contained in the 2D projected images of 3D objects, and thus dominates their first impressions from a psychological point of view. Although several methods have been proposed that calculate the optimal positions of viewpoints especially for 3D surface meshes, none has been done for solid objects such as volumes. This paper presents a new method of locating such optimal viewpoints when visualizing volumes using direct volume rendering. The major idea behind our method is to decompose an entire volume into a set of feature components, and then find a globally optimal viewpoint by finding a compromise between locally optimal viewpoints for the components. As the feature components, the method employs interval volumes and their combinations that characterize the topological transitions of isosurfaces according to the scalar field. Furthermore, opacity transfer functions are also utilized to assign different weights to the decomposed components so that users can emphasize features of specific interest in the volumes. Several examples of volume datasets together with their optimal positions of viewpoints are exhibited in order to demonstrate that the method can effectively guide naive users to find optimal projections of volumes.

This paper discusses a method to watermark a 3D shape model defined as a set of unoriented points. Our approach is to perform frequency domain analysis of the shape of the 3D point set for watermarking. Our method applies the mesh-spectral analysis technique proposed by Zachi Karni, et al. to the point set model for frequency domain shape analysis. As the technique requires connectivity of vertices for the analysis, our method generates a nonmanifold mesh from the point set and uses its connectivity for the analysis. The watermarks embedded by using the method can be detected, to some extent, after such attacks as cropping, (simulated) simplification, similarity transformation, and additive random noise applied on the watermarked point set model.

Topological volume skeletons represent level-set graphs of 3D scalar fields, and have recently become crucial to visualizing the global isosurface transitions in the volume. However, it is still a time-consuming task to extract them, especially when input volumes are large-scale data and/or prone to small-amplitude noise. The paper presents an efficient method for accelerating the computation of such skeletons using adaptive tetrahedralization. The tetrahedralization is a top-down approach to linear interpolation of the scalar fields in that it selects tetrahedra to be subdivided adaptively using several criteria. As the criteria, the method employs a topological criterion as well as a geometric one in order to pursue all the topological isosurface transitions that may contribute to the global skeleton of the volume. The tetrahedralization also allows us to avoid unnecessary tracking of minor degenerate features that hide the global skeleton. Experimental results are included to demonstrate that the present method smoothes out the original scalar fields effectively without missing any significant topological features.

Direct volume rendering is a standard technique for projecting all the optically-encoded samples onto the screen at once to allow us to peer into the inner structures involved in a volume data. Datacentric approaches to the design of transfer functions (TFs) have recently been well-established, which perform mathematical analysis of the data prior to pertinent rendering. The advent of multidimensional TFs is one of the latest major achievements in the volume visualization research. As opposed to the traditional onedimensional TFs that only consider a voxel’s scalar field value, the multi-dimensional TFs assign auxiliary attributes to the voxels to construct their sophisticated parametric domains. For example, when visualizing volumes obtained by scientific simulations, the observers can utilize their own knowledge about the simulation settings to extract the global characteristics of the volumes and to locate regions of particular interest. If they are allowed to design multi-dimensional TFs using staff attributes so as to encapsulate such advance knowledge, they can readily yield visualization results to fulfill their purposes. Nevertheless, nearly all attributes for the conventional multi-dimensional TFs are based on local features, such as differentials and curvatures, and are difficult to capture the global structure of the volume contrary to the observer’s purposes. This paper therefore introduces a new set of topological attributes to establish a new framework that is intended to realize objective-based assistance. Topological attributes proposed herein are derived from the level-set graph, which delineates the topological evolution of an isosurface with respect to the scalar field.

It is still challenging to generate hand-drawn pictures because they differ from ordinary photographs in that they are often drawn as seen from multiple viewpoints. This paper presents a new approach for modeling such surperspective projection based on shape deformation techniques. Specifically, surperspective landscape images for guide-maps are generated from 3D geographical elevation data. Our method first partitions a target geographical surface into feature areas to provide designers with landmarks suitable for editing. The system takes as input 2D visual effects, which are converted to 3D geometric constraints for geographical surface deformation. Using ordinary perspective projection, the deformed shape is then transformed into a target guide-map image where each landmark enjoys its own vista points. An algorithm for calculating such 2D visual effects semi-automatically from the geographical shape features is also considered.

This paper presents a robust watermarking algorithm with informed detection for 3D polygonal meshes. The algorithm is based on our previous algorithm [22] that employs mesh-spectral analysis to modify mesh shapes in their transformed domain. This paper presents extensions to our previous algorithm so that (1) much larger meshes can be watermarked within a reasonable time, and that (2) the watermark is robust against connectivity alteration (e.g., mesh simplification), and that (3) the watermark is robust against attacks that combine similarity transformation with such other attacks as cropping, mesh simplification, and smoothing. Experiment showed that our new watermarks are resistant against mesh simplification and remeshing combined with resection, similarity transformation, and other operations..

Existing methods of morphing 3D meshes are often limited to cases in which 3D input meshes to be morphed are topologically equivalent. The paper presents a new method for morphing 3D meshes having different surface topological types. The most significant feature of the method is that it allows explicit control of topological transitions that occur during the morph. Transitions of topological types are specified by means of a compact formalism that resulted from a rigorous examination of singularities of 4D hypersurfaces and embeddings of meshes in 3D space. Using the formalism, every plausible path of topological transitions can be classified into a small set of cases. In order to guide a topological transition during the morph, our method employs a key frame that binds two distinct surface topological types. The key frame consists of a pair of "faces", each of which is homeomorphic to one of the source (input) 3D meshes. Interpolating the source meshes and the key frame by using a tetrahedral 4D mesh and then intersecting the interpolating mesh with another 4D hypersurface creates a morphed 3D mesh. We demonstrate the power of our methodology by using several examples of topology transcending morphing.

Subdivision surfaces provide an efficient means of representing surfaces of arbitrary topological type. In recent years, multiresolution modeling with variational smoothing has played an important role in controlling such surfaces. This paper presents a new model of multiresolution constraints that can be applied to subdivision surfaces. The advantage of this model is that different geometric constraints can be imposed on the surfaces at different resolution levels. The model employs the wavelet-based framework of Lounsbery, et al. (1997), to represent the subdivision surfaces in a hierarchical fashion. In the proposed framework, local smooth filtering is used to obtain the optimal surface shape at each resolution level. Controlling the number of iterations for the local smoothing operations allows us to modify the smoothness of the subdivision surfaces even when the same set of constraints is given. Several design examples are included to demonstrate the capability of this model.

The paper introduces constraints termed tolerance constraints, which specify several types of variations, in the design of smooth curves and surfaces at multiresolution levels. The mathematical model for such tolerance constraints is implemented by extending Welch and Witkin's (1992) work on linear constraints in variational shape sculpting. The tolerance constraints presented in this paper are classified into two types: geometric-tolerance and parametric-tolerance constraints. The geometric-tolerance constraints serve as constraints that allow variations in geometric size, while the parametric ones introduce variations in the parametric domain where the shape is defined. These two types are employed as not only finite-dimensional constraints, such as points and tangents, but also transfinite constraints, such as curves and areas. In order to find a smooth shape of a curve or a surface, the multiplier method is used that seeks to minimize the function subject the shape deformation, along with the penalty terms derived from the tolerance constraints. An optimal solution is then found easily because the derivatives of the penalty terms can be evaluated using vector and matrix calculations. Several design, examples are presented to show that the tolerance constraints are powerful tools for finding optimal shapes of multiresolution curves and surfaces.

The paper presents a method of designing curves and surfaces by solving the constraints imposed on the shapes at multiresolution levels. In this method, the curves and surfaces are represented by endpoint interpolating B splines and their corresponding wavelets. At each resolution level, the shape is determined by minimizing the energy function subject to the deformation of the shape while preserving the given constraints. Constraints at a low resolution level are converted to those at a high resolution level using wavelet transforms in order to associate all the constraints with the common basis functions. The constraints at multiresolution levels are then solved recursively from low to high resolution levels. Design examples are also presented.

Abstract Researchers in the fields of computer graphics and geographical information systems (GISs) have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition.

We introduce a new concept of ridges, ravines and related structures (skeletons) associated with surfaces in three-dimensional space that generalizes the medial axis transformation approach. The concept is based on singularity theory and involves both local and global geometric properties of the surface; it is invariant with respect to translations and rotations of the surface. It leads to a method of hierarchic description of surfaces that yields new approaches to shape coding, rendering and design. The extraction of the features is based on differential geometry of surfaces with consequent segregation via multiscale analysis. Terrain feature recognition, dental shape reconstruction and medical imagery are a partial list of applications.>