John Brosz

Miguel A Nacenta

Richard Pusch

Sheelagh Carpendale
email: sheelagh@ucalgary.carapusch@alumni.ucalgary.ca

Christophe Hurter
email: christophe.hurter@enac.fr

Métamorphose : la manipulation libre et simplifiée de visualisations

Keywords: Visualization, image deformation, multi-touch. ACM Classification H.5.2 Information interfaces and presentation: User Interfaces -Graphical user interfaces

teaching and research institutions in France or abroad, or from public or private research centers.

INTRODUCTION

We live in an information world and, thanks partly to the web, this information is increasingly visual. Visual representations of data appear often at work and in our social lives; for example, in newspapers and other websites we regularly encounter graphical evolutions of economic indicators for the last few years, or maps that display the most expensive neighborhoods in the city. These data visualizations are necessarily limited to specific representations, usually constrained by the format (e.g., paper, raster images on websites), and by the representation choices of the designer.

Naturally, no representation can be perfect for all purposes, for all people, or for all data. Tversky [START_REF] Tversky | Some ways that maps and diagrams communicate[END_REF] has discussed how all maps (also a type of visual data representation) omit some information and may scale, simplify, reduce dimensionality, regularize, or even use inconsistent scale and perspective in order to better fulfill their purpose (which can be practical, aesthetic, or even political). Similar constraints apply to other types of static and dynamic visualizations. Even dynamic information visualizations cannot foresee all the needs and preferences of viewers [START_REF] Kostelnick | The visual rhetoric of data displays: The conundrum of clarity[END_REF]. Although InfoVis programming languages (e.g., [START_REF] Bostock | D3: Data-driven documents[END_REF]) and end-user software systems (e.g., Tableau1 ) are sufficiently expressive to create a great range of purpose-adapted representations, producing visualizations with these tools takes significant time and effort. Often this is not even an option since, despite the current push for open data, most often the data behind a representation is not directly available.

In this work we aim at allowing viewers to easily explore alternative representations. To do this we created the Transmogrification Canvas (TC), a tool that allows quick, realtime, flexible transformations of the representation of 2D visuals. Transmogrifiers-the core technique of the TCare novel interface elements that adapt graphical deformation techniques to enable the transformation of an arbitrary original shape into another shape.

Using Transmogrifiers people can create custom transformations of existing graphics that are adapted to the person's specific visualization purpose, preference, and cognitive abilities. The specially crafted interface works in real-time on any existing visual material, and without the need for programming. The TC is designed to allow people to sketch, transform, and compare visualizations from one or multiple sources in a way that fits real-life situations, where people discussing a graph would like to make a point through a visual representation while still keeping pace with the conversation.

The contribution of this paper is three-fold:

• The concept of transmogrification: an application of graphical deformation to enable cartographic and visualization manipulations. • A novel integrated set of interaction and animation techniques that enable quick and flexible transmogrification in real-time. • A desktop multi-touch tool that integrates these techniques and animations into a coherent interface.

AN EXAMPLE SCENARIO

Maria likes to go on long bike rides. She carries equipment that measures her position and altitude through GPS, as well as her heart rate. After processing her data, her software creates the map and graphs in Fig. 1.A. To investigate the data further, Maria starts the Transmogrifier Canvas, which captures the map and graphs from the desktop. She creates a route trace on the map with her finger and then transforms it into a rectangle. This rectification represents her ride as a straight path from start to finish and she then resizes and moves it to lie under the graphs of altitude and heart-rate (see Fig. 1.B). This shows her how the different towns and intersections correspond to the different stages of her ride. She can quickly identify the name of the town where she stopped for lunch by looking at the correspondence between the rectified map and the graphed area of low heart rate.

To get a further overview of where she put in the most effort, she applies a transformation to plot her heart rate upon the map itself. Figure 1.C represents the effort (heart rate) at each point in the route, encoded in the width and amount of orange beside the route. Now she can easily identify that she worked hardest along the inland road. Finally, she applies the same transformation of the altitude graph to the map and overlays this with the transmogrified heart rate to see how one influenced the other (Fig. 1.D).

RELATED WORK

While motivated by Casual Infovis [START_REF] Pousman | Casual information visualization: Depictions of data in everyday life[END_REF], our interaction techniques can be applied to non-casual scenarios and audiences.

In this section we review related work in four subsections: the closest related tools, visualization and cartographic techniques, graphical deformation algorithms, and animation.

Related Tools

Most closely related to our work is Savva et al.'s ReVision [START_REF] Savva | Revision: automated classification, analysis and redesign of chart images[END_REF], which uses machine learning techniques to analyze images of charts, extract chart type and infer the data, and then create alternative chart designs and styles. This approach supports one of Transmogrifiers goals (re-representation of an existing visual), but it is not real-time, it still requires significant knowledge for re-representation, and does not allow arbitrary transformations of shape. Also, while ReVision is 96% accurate classifying the infographic type, it is much less accurate in extracting the data; for instance, it was only ∼ 64% successful at extracting data from the charts. In exchange, if successful in extracting data, ReVision would usually be more accurate, and its results avoid some of the problems that we discuss in the Limitations section.

SketchVis [START_REF] Browne | Data analysis on interactive whiteboards through sketch-based interaction[END_REF] and NapkinVis [START_REF] Chao | Poster: Rapid pen-centric authoring of improvisational visualizations with napkinvis[END_REF] both create visualizations through sketches on interactive surfaces. These share with transmogrifiers the goal of quickly generating data visualizations without the need for programming. However, they are different in that they require access to the underlying data, do not operate on existing visualizations, and are focused on a few possible visualization types. Additionally, other tools exist that leverage multi-touch for drawing (e.g., [START_REF] Sun | An interactive multi-touch sketching interface for diffusion curves[END_REF]).

Related Visualization and Cartographic Techniques

The use of graphic deformation underlies many infovis techniques. A common type are local magnification techniques, which can be divided into two main categories (after Cockburn et al. [START_REF] Cockburn | A review of overview+detail, zooming, and focus+context interfaces[END_REF]): overview+detail and focus+context. With overview+detail the magnified area is presented spatially separate from the context; focus+context techniques place the magnified region within the context by compressing some amount of the context area. Alternatives exist where transparency is used instead of compression [START_REF] Pietriga | Sigma lenses: focus-context transitions combining space, time and translucence[END_REF], where context regions are hidden in folds [START_REF] Slack | Composite rectilinear deformation for stretch and squish navigation[END_REF], or where the lens automatically adapts its shape to match objects of interest [START_REF] Pindat | Content-aware adaptive lenses[END_REF].

Agrawala and Stolte [START_REF] Agrawala | Rendering effective route maps: improving usability through generalization[END_REF] deform maps to reproduce characteristics of hand-drawn route maps, such as portraying the important turns and landmarks for a route without requiring an accurate representation of space. For this same goal of automatic creation of route maps Kopf et al. [START_REF] Kopf | Automatic generation of destination maps[END_REF] make use of nonlinear optimization to non-uniformly adjust the position, scale, and orientation of an automatically determined subset of relevant roads. Bottger et al. [START_REF] Bottger | Map warping for the annotation of metro maps[END_REF] use image deformation to globally deform street-level map images to match the layout of an abstracted metro map/schematic.

Most of the techniques above can be simulated, reproduced, or approximated through the interactive use of transmogrifiers. Transmogrification provides a way of thinking about deformations as well a generalized interface to reproduce and prototype these deformations and many more.

Finally, there are related techniques based on spatial transformation and selection that are outside the scope of transmogrifiers. For example, magic lenses [START_REF] Bier | Toolglass and magic lenses: The see-through interface[END_REF][START_REF] Hurter | An attribute and structure-based semantic lens for large element-based plots[END_REF] present information from a different or processed layer of spatial data in situ, within the spatial context, and Histomages [START_REF] Chevalier | Histomages: fully synchronized views for image editing[END_REF] enable 2D selection operations in the transformed color histogram space.

Deformation Algorithms

Transmogrification is based on the ability to deform graphics.

Computer graphics research has a long tradition of research in image deformation, which is often referred to as tweening (deformation has often been used to generate in-between frames for animations). Within tweening we review morphing and image deformation algorithms. Several of the following algorithms serve as base and are adapted to work with the constraints of transmogrifiers (see also Implementation).

Morphing. Morphing algorithms provide transitions where one object changes into another. Typically a set of correspondences are used to create a series of images that smoothly transition from an image to another. Although morphing was first achieved by simply cross-dissolving images [START_REF] Wolberg | Image morphing: a survey[END_REF], current approaches [START_REF] Smythe | A two-pass mesh warping algorithm for object transformation and image interpolation[END_REF][START_REF] Lee | Fast feature-based metamorphosis and operator design[END_REF] make use of image deformation style techniques, including one-to-one morphing. Reilly & Inkpen [START_REF] Reilly | Map morphing: making sense of incongruent maps[END_REF] and Haunert and Sering [START_REF] Haunert | Drawing road networks with focus regions[END_REF] provide examples of cartographic morphing-respectively deforming Cartesian maps into schematic maps and clarifying road knots.

Image Deformation. Image deformations encompass a variety of techniques designed to allow images to be manipulated as if they were flexible objects. These are applied to alter images, interpolate between keyframes, or even animate entire sequences. Usually deformations are enabled through placing and altering the positions of handles. There are many varieties of handles utilized for this task including points [START_REF] Igarashi | As-rigid-as-possbile shape manipulation[END_REF][START_REF] Weng | 2d shape deformation using nonlinear least squares optimization[END_REF][START_REF] Jacobson | Bounded biharmonic weights for real-time deformation[END_REF], lines [START_REF] Beier | Feature-based image metamorphosis[END_REF], skeletons [START_REF] Burtnyk | Interactive skeleton techniques for enhancing motion dynamics in key frame animation[END_REF][START_REF] Hsu | Skeletal strokes[END_REF], bones [START_REF] Shen | An MLS-based cartoon deformation[END_REF], lattices [START_REF] Yang | 2d shape manipulation via topology-aware rigid grid[END_REF], sketches [START_REF] Eitz | Sketch based image deformation[END_REF][START_REF] Weng | Sketching MLS image deformations on the GPU[END_REF], and cages [START_REF] Lipman | Green coordinates[END_REF][START_REF] Weber | Controllable conformal maps for shape deformation and interpolation[END_REF][START_REF] Meng | Multicage image deformation on gpu[END_REF]. Alternative interactions exist, for instance Schiwietz et al. [START_REF] Schiwietz | Freeform image[END_REF] assign physical properties and create deformations by applying force vectors.

Many of these techniques, such as that of Igarashi et al. [START_REF] Igarashi | As-rigid-as-possbile shape manipulation[END_REF], break the image into small polygons and frame the problem as that of minimizing distortion. Other techniques, such as Lipman et al.'s [START_REF] Lipman | Green coordinates[END_REF], make use of different coordinate calculations with various shape preserving qualities to transform pixel coordinates. While minimization provides a physical basis for such manipulations, it also limits their scope. For transmogrification we can override these physically-plausible restrictions and instead seize the opportunity to alter imagery in a more abstract fashion.

Optimization-based deformation techniques work by moving pieces of the image to new locations and then attempting to make the rest of the image fit, providing a globally coherent reorganization of the image. These techniques are less useful for transmogrification, where the final shape is determined interactively rather than algorithmically.

In our exploration of algorithms we found that skeleton-type handles that allow for simple selection of visual elements are best suited for our purpose when combined with multi-touch interaction. Consequently transmogrifiers expand upon existing skeletal deformation techniques [START_REF] Burtnyk | Interactive skeleton techniques for enhancing motion dynamics in key frame animation[END_REF][START_REF] Hsu | Skeletal strokes[END_REF], as discussed in the Implementation section below.

Animation

We provide animations to help viewers find correspondences between transformed and untransformed images. Tversky et al. [START_REF] Tversky | Animation: can it facilitate?[END_REF] surveyed research in the cognitive value of animation and found that it can be beneficial if it helps to portray extra information. This is the case for transmogrifiers, where animation is used to depict correspondences between 2D spaces that are not explicit otherwise. Other researchers have found benefits in animation for different domains such as tree visualization [START_REF] Bederson | Does animation help users build mental maps of spatial information[END_REF], common statistical graphs [START_REF] Heer | Animated transitions in statistical data graphics[END_REF], and hierarchies [START_REF] Robertson | Animated visualization of multiple intersecting hierarchies[END_REF]. These and other uses and studies of animation in information visualization (e.g., [START_REF] Elmqvist | Rolling the dice: Multidimensional visual exploration using scatterplot matrix navigation[END_REF][START_REF] Dragicevic | Temporal distortion for animated transitions[END_REF][START_REF] Hurter | Spreading aircraft trajectories across views to support iterative queries[END_REF][START_REF] Hurter | An attribute and structure-based semantic lens for large element-based plots[END_REF]) inspire and inform the animations available in our tool.

TRANSMOGRIFICATION

Transmogrification is a technique designed for casual information exploration that allows people to easily take a personally selected part of the visual data and transform its geometry interactively. Transmogrification is instantiated by transmogrifiers, which are interface elements that implement adaptations of existing skeleton-based image deformation algorithms [START_REF] Burtnyk | Interactive skeleton techniques for enhancing motion dynamics in key frame animation[END_REF][START_REF] Hsu | Skeletal strokes[END_REF], can be animated in different ways, and are controlled with multi-touch interaction techniques.

Transmogrifiers operate on any chosen area of an imagethat is, they can start from any arbitrarily shaped region-and transform its contents to fit a chosen resulting shape. These shapes can be regular geometrical shapes or free-form shapes created interactively to fit a particular feature of the original representation. For example, a square area can be transformed into a circular area, and a curved free-form area can be transformed into a rectangular area. We call the shape that determines the area to be transformed the source, and the intended shape of the transformation the destination. Fig. 2 shows two transmogrifiers sharing the same origin.

Interface

Interaction with transmogrifiers is designed to support two basic goals: enabling a flexible set of transformations that adapt to the underlying data, and allowing people to generate a large number of different explorations in a short time.

To enable a large set of manipulations, source and destination can be chosen from a set of predefined shapes (rectangle, circle, quadrilateral, spiral, ring) available through a tool palette (see Fig. 2.B), created on the fly through single-and multi-point finger traces, or defined through bezier curves.

The multiple combinations of source and destination shapes support different usages.

A transmogrifier is created by dragging a finger from an existing shape into another. The shape under the start of the drag gesture becomes the source and the shape under the finger at touch release becomes the destination. A red transparent tapered line starts thick on the source and narrows to the destination, indicating the presence of a transmogrifier (Fig. 2.

H).

Shapes can be translated, scaled and rotated with multi-touch interaction techniques (e.g., [START_REF] Nacenta | Separability of spatial manipulations in multi-touch interfaces[END_REF]). Most shapes have control points that enable further modifications, such as the quadrilateral, where corners can be adjusted, or the ring, where the size of the interior circumference can be enlarged.

One of the main features of transmogrifiers that enables datacentric flexible analysis are trace-shapes. A trace-shape is created by touch-tracing a line on any region of the image space. This allows generation of arbitrary source and destination shapes that can follow the shape of the original graphical data on the screen. For example, with this multi-touch technique it is easy to create a source shape that follows the contour of elements in the image such as coastlines in a map. There are two types of trace-shape: single-and double-point.

In single-point trace-shapes, the analyst generates a line around which a shape is grown with constant width (Fig. 3). We call this central line the spine, which is related to Hsu et al.'s reference backbone [START_REF] Hsu | Skeletal strokes[END_REF]. The width of the shape is constant, but it can be modified through a control that appears at the start side of the shape (Fig. 3.B). Trace-shapes also provide handles along the trace to modify the local sampling densities, which allow compression or expansion of parts of the image longitudinally along the spine.

The double-point trace-shape is more flexible than the singlepoint because it enables dynamic variation of thickness along the trace, which allows a larger range of possible shapes. In exchange, it is harder to control because the additional degrees of freedom may make difficult to attain accurate traces [START_REF] Nacenta | Separability of spatial manipulations in multi-touch interfaces[END_REF]. However, while tracing with double-points one's fingers do not occlude the middle content being traced (Fig. 4).

For traces that require more precision, we implemented a bezier curve drawing technique that works similarly to the single-point trace-shape. Bezier-generated shapes can also be translated, scaled or rotated with the usual gestures. Alternatively, the TC provides a "magnet" mode where traces are algorithmically aligned with nearby edges using our variant of Snakes [START_REF] Kass | Snakes: Active contour models[END_REF], with the input points being aligned with the first-order gradient of a blurred internal image copy.

Animations

Transmogrifications are usually non-linear transformations which can be potentially hard to understand. To facilitate seeing the relationship between the original and transmogrified space we incorporate animation, which has previously been shown to be successful in supporting comprehension during transformation in infovis (e.g., [START_REF] Robertson | Animated visualization of multiple intersecting hierarchies[END_REF][START_REF] Dragicevic | Temporal distortion for animated transitions[END_REF][START_REF] Heer | Animated transitions in statistical data graphics[END_REF][START_REF] Bederson | Does animation help users build mental maps of spatial information[END_REF]).

When a transmogrifier is created, a default animated transformation from origin to destination is shown. The viewer can replay this animation at her desired speed by dragging a slider that appears at the bottom of the interface (Fig. 2

.K).

A virtually infinite variety of combinations of origin and destination shapes implies that animations that are good for one transformation might not be good for another. To address this we implemented three different animation types, selectable through a menu in the TC interface. We chose these according to two criteria derived from previous work and our own experimentation: we try to maximize the number of pixels moving in the same direction (consistency), and we try to avoid twists and folds during the animation (clarity).

The animations are: ring quadrature, path distance delay, and ribbon (Fig. 5). Ring quadrature provides transitions from shapes in Cartesian coordinates to shapes in polar coordinates; path distance delay interpolates between shapes progressively from one end of the shape to the other; ribbon unwinds long, curving shapes. Future work should address the feasibility of automatic animation selection.

The Transmogrification Canvas

Transmogrifiers exist within the Transmogrification Canvas.

Although the general interface is designed to take advantage of the multi-touch paradigm, during the design of the application we decided that-for some functions-menus, buttons, and sliders are preferable to invocation gestures that are sometimes difficult to discover and remember [START_REF] Nacenta | Memorability of pre-designed and user-defined gesture sets[END_REF]. The following subsections describe the functionality of TC that goes beyond the individual transmogrifiers, and how it interacts with the wider computing context.

General Interface

TC has a basic menu/palette that appears on the top left corner of the window (2.A). Large elements enable touch interaction, although indirect input is also possible for systems with mouse input. The shapes sub-menu in TC offers the standard shapes; however it can also save custom-made transmogrifiers, which become part of the palette (Fig. 2.B). Transmogrifications can be turned into source raster images. The menu also contains options to select the animation type.

Multi-transmogrifier Functionality

Beyond pure transmogrification functionality, the TC provides a workspace to combine and compose different transmogrifiers for more power. For example, transmogrifiers can not only share the same canvas space, but TC allows transmogrifiers to share the same origin shape, which is useful to compare alternative transformations of the same data.

Because a transmogrifier can be turned into a source image with the press of a button, we can chain multiple transmogrification operations, creating a 'transmogrification pipeline' reminiscent of Lark [START_REF] Tobiasz | Coordinating co-located collaboration with information visualization[END_REF]. This operation, combined with the ability of a transmogrifier to operate on adjacent images enables a powerful image transformation algebra that we will return to in the Examples and Discussion sections.

The TC and its Computing Context

TC is designed to integrate in people's workflow through multiple features. First, images to transmogrify can be imported into the canvas through a load option that accesses the user's operating system image files. Additionally, transmogrified images can be saved back to the hard-drive or copied into the system clipboard for use in other applications.

The TC can also be a sophisticated visualization and exploration tool when accessing web or other program's visualizations. By assigning a system-wide keystroke (e.g., Shift+PrtScr) TC can take a snapshopt of the current state of the desktop and import it into a screen-sized TC window.

Lastly, TC has a multi-display mode in which the canvas can operate, in real-time, on objects that are present in other screens. This is a powerful feature, since it enables real-time interaction with transmogrified visualizations or even videos, which are updated in real time. This is possible without the need for interfacing our software with each specific visualization. Additionally, this feature allows viewers to configure personalized transmogrified information dashboards of information from other screens, a powerful generalization of the WinCuts concept [START_REF] Tan | Wincuts: manipulating arbitrary window regions for more effective use of screen space[END_REF]. To better understand the real-time desktop features, please refer to the Video Figure.

IMPLEMENTATION

This section describes our implementation to enable other researchers to reproduce our work; additionally, we report on how we adapted existing techniques, highlighting our contributions and providing a rationale for our choices.

Spines and Parameterization

The key element of the implementation of transmogrifiers is the deformation algorithm that maps the source shape into the destination shape. For this we extend the skeleton-based approach of Hsu et al. [START_REF] Hsu | Skeletal strokes[END_REF]. Our algorithm requires that we define each shape through three curves: two boundary curves at the edges of the shape, and a spine somewhere between them (see Fig. 6). Based on those curves, the algorithm creates a parameterization of the source space that it uses to render it onto the destination. The destination space is a shape defined by a different set of spline and boundary lines (see Fig. 7).

With an equivalent parameterization in the source and the destination, we can then map the source area between the source's spine and boundaries to the shape defined by the destination's spine and boundaries. The parameterization of the shape's area is based on a linear interpolation between the spine, f s (u), and the boundary curves, f b (u) and f b (u), where u is the parameter that expresses the distance of a point along the curves, and v the parameter that describes the relative position of a point between the curves:

f (u, v) = (1 -2v)f b (u) + 2vf s (u) v ≤ 1 2 ; (2 -2v)f s (u) + (2v -1)f b (u) else where v ∈ [0, 1].
Parameterization of standard shapes is easy to achieve (e.g., we parameterize the circle using polar coordinates); for traceshapes we use piecewise linear parameterization of the touch traces. Once this is established, the rest of the process uses the texture coordinates to reshape the source area to fit the destination area. This is done by calculating the image's texture coordinates along the source's spine and boundary curves. These coordinates are used on the destination shape curves' positions, rendering textured quad strips between the spine and each boundary (Figure 7). We adopted this algorithm for four reasons: a) it is sufficiently flexible to provide a wide variety of transformations; b) it preserves the continuity of the source and destination shapes; c) the visual presence of spines and borders facilitates the understanding of transformations (as opposed to, e.g., formulae); and d) it lends itself to trace-based interaction and, specifically, multitouch input (see next subsection).

Our implementation described thus far differs from Hsu et al.'s Skeletal Strokes [START_REF] Hsu | Skeletal strokes[END_REF] because the latter are constrained to rectangles as source shapes and only introduce arbitrary shapes as destination shape. We can use arbitrary shapes for both source and destination; in the following sections we show multiple examples that need this flexibility. Additionally, Hsu et al. do not offer an interface for the flexible manipulation of their parameters. In contrast, transmogrification is an interactive technique at heart. The following sections describe adaptations of our algorithm that derive directly from the interactive nature of transmogrifiers.

Defining the Spine and Boundary Curves

As seen above, the main input for the algorithm is the curves that define the source and destination shapes. These are defined in different ways depending on the type of shape. For example, in a quadrilateral we choose two opposite sides as boundaries, and the median line as spine; in a circle the boundary lines are the circumference and the circle's center, and the spine is a circle at half the radius. For trace-shapes the definition of the curves is built into the interaction and requires some extra considerations.

Single-point trace shapes. In these shapes the touch-trace generated by the analyst determines the spine, but the raw input has to be processed before it can be used due to the noisy touch input and irregular sampling provided by the input device. We interpolate the input linearly to subpixel resolution and then filter and decimate this signal [START_REF] Cherlin | Sketch-based modeling with few strokes[END_REF]. The sampling of the spine curve is regularized according to arc-length along the spine. The viewer can alter the sampling by manipulating the handles described in the Interaction section.

To generate the shape, we expand from the spine outwards, perpendicular to the spine's tangent until boundary curves at the desired width are created. As noted by Hsu et al., this can result in wrinkling or folding on the inside of boundary curves (Figure 8). Figure 9 shows the solution proposed by Hsu et al. [START_REF] Hsu | Skeletal strokes[END_REF], which only works for small loops, and our solution, which avoids the area becoming unnaturally stretched by distributing points along the path to the loop's centroid (for larger loops). While this was not a concern in their scenario, we need to consider it because we use trace shapes as source shapes. For larger loops with more than three points in the loop we distribute points along a path to the loop's centroid. Double-Point Trace. In a double-point trace-shape the touchtraces determine the boundary curves, and the spine is interpolated midway between them. Both boundaries are captured simultaneously, but care must be taken to match the sampling of both curves.

The piecewise curves resulting from each trace are linearly resampled based on input time so that each curve has the same number of points. Once both curves have an equal number of sample points the same interpolation and filtering process described for the single-point trace is applied. The parameterization for all three curves is based on the spine distance (as opposed to one of the boundaries).

Note that it is possible to use touch timestamps instead of distance to generate alternative sampling patterns. This opens a number of interesting possibilities that have not been considered in previous work. Moreover, our algorithmic modifications also support non one-to-one mappings, where source areas can appear more than once in the destination shape. In other words, transmogrifier shapes can fold upon or loop over themselves, making the same source pixels appear multiple times in the transmogrified image.

EXAMPLES

This section illustrates usage of transmogrification to achieve alternative visualizations in a range of scenarios.

Path Rectification and Deformation

Maps are typically represented as projections onto Cartesian planes. Distances and areas as measured in these representations usually revert to approximately Euclidean distances, which can be perceived reasonably accurately through direct sight. However, there are instances where we need to see distances beyond "straight line" distance. A straightforward example of this is J. H. Colton's visualization of river's length, recently analyzed by Tufte [START_REF] Tufte | Envisioning Information[END_REF], p. 77. Because it can be difficult to compare the lengths of rivers as displayed in their own locations, with different bends and orientations, Colton decided to "hang rivers to dry" in a visualization that, (a) is straightforward to understand, (b) provides a quick, visual answer to the question of distance, and (c) preserves local context and much of the graphical information of the rivers contained in their original graphical representation. What was a compelling but likely a painstakingly difficult visualization to produce for Colton is interactively trivial with a single-point trace transmogrifier (see Figure 10). All that is needed is to simply trace one's finger along the path of the river. This technique can enable quick visual calculations of distance to other elements such as roads, paths, and coastlines. Precision will depend on multiple factors such as the accuracy of the initial representation, whether the 'magnet' mode is on, the accuracy of the tracing, and the sampling algorithm.

When transmogrification is used to straighten roads, as in the opening scenario of the paper (Fig. 1.B), the resulting imagery is close in spirit to Matthew Paris's medieval pilgrimage maps [START_REF] Gaudio | Matthew paris and the cartography of the margins[END_REF]. Essentially, the resulting maps abstract away turns and provide a representation where the reader sees to the left or to the right what the travelers would see as their trip progresses.

The example in Fig. 11 uses spatial adjustments achieved through spine scaling for the route from Los Angeles to Las Vegas. The left part of the figure is an undistorted cutout of the map; the right part shows a transmogrification of the route where sampling is intentionally varied. It has been manipulated to provide more detail in the areas that contain more important information (the details such as curves and turns within each city), and less detail in the long straight roads crossing the Mojave Desert. This manipulation is reminiscent of the route maps that people draw when sketching directions, and of those generated by Agrawala and Stolte [START_REF] Agrawala | Rendering effective route maps: improving usability through generalization[END_REF] and Kopf et al. [START_REF] Kopf | Automatic generation of destination maps[END_REF]. However, here we only adjust scale along the spine of the transmogrifier; adjusting scale in the dimension perpendicular to the spine can be achieved through a two-finger trace. Adding semantic zoom capabilities requires further work.

Straightening trajectories can offer additional benefits beyond the above length comparisons or traveler-centric maps. For example, transmogrifiers can help represent spatial data that encodes other visual variables. Fig. 12 (left) is an actual route visualization of aircraft taking off from Lyon airport; it shows how the aircraft take different routes that reach high altitudes (in red to blue) at different stages. Optimizing altitude profiles is important because it affects fuel consumption. However, the layout and the turns in the trajectories make colorcoded altitude profiles difficult to compare. Fig. 12 (right) shows an alternative representation that rectifies the routes. We discussed this visualization with an air traffic controller, who was able to confirm insights from the graph that are otherwise difficult to perceive in the original layout (e.g., current routes going to the East have less steep profiles, despite heading towards the Alps).

Changing Visualization Layouts

There are multiple instances of visualizations that can benefit from dynamically adjusting their layout geometries; for example, circular or square layouts of trees might be preferable depending on whether the visualization is meant for a single person or a group of people on a tabletop [START_REF] Tobiasz | Coordinating co-located collaboration with information visualization[END_REF]. Fig. 13 shows how an icicle plot is transmogrified into a sunburst tree, and the transmogrifier in Fig. 14 turns a circular chord visualization [START_REF] Meyer | Mizbee: A multiscale synteny browser[END_REF] into a rectangular layout. A different example of visualization re-representation is the reverse of path rectification shown in the opening scenario (Fig. 1.C), where a variable is shown in its spatial context by warping to a path. More complicated geometry transformations can take advantage of the free-form shapes to, for example, adjust a stacked graph [START_REF] Wattenberg | Baby names, visualization, and social data analysis[END_REF] by straightening the base line of a data region (Fig. 15).

The recursive features of the TC also enable composite manipulations, such as the elimination of part of the data in a circular graph by first transforming to a square geometry, clipping, and then transforming back to circular (Fig. 16). Note that similarly to removing data, we can add or merge data from multiple sources into a single graph.

DISCUSSION

Just as we often find solutions to problems by testing different alternatives in our minds, generating visual alternatives of visual data sets may be the key to new insights. Conversely, the ability to reverse distortions in representations should also facilitate analyzing data that would otherwise be partially obscured. Many existing techniques are currently being used by analysts and artists precisely for these purposes; for example, With Transmogrification we extend existing knowledge and algorithms from computer graphics to serve the purpose of information assessment and exploration, particularly in initial stages where a quick look at an alternate view could confirm or refute an idea. We have found that multi-touch manipulation and tracing input lends itself particularly well to the control of graphical distortion techniques, where the large parametric space would be tedious and difficult to control through a single point (e.g., a mouse). Moreover, from our own experience with the system and during demonstrations, we speculate that the directness of touch interaction is particularly suited for deformation techniques because most of our experiences of deformation come from the physical world (e.g., stretching, folding of papers, cloth or other pliable or plastic materials [START_REF] Mikulecky | Exploring physical information cloth on a multitouch table[END_REF]).

From the point of view of information visualization, we see transmogrification as the natural evolution of existing distortion-based techniques such as lenses [START_REF] Carpendale | A framework for unifying presentation space[END_REF], Melange [START_REF] Elmqvist | space folding for multi-focus interaction[END_REF], or Perspective Wall [START_REF] Mackinlay | The perspective wall: Detail and context smoothly integrated[END_REF]. Recreations of a TableLens and a Perspective Wall with transmogrifiers are shown in Figures 17 and18. In fact, it is possible to think about transmogrifiers as a generalization of lenses and portal techniques. However, its flexibility and the possibility to transform visuals in arbitrary ways enables a qualitatively different way to use them; instead of applying a technique to an image, we create an ad-hoc interaction technique where visual results are based on direct interaction with the image. This information-centric perspective represents an inversion of most current techniques in visual data exploration.

We have found that transmogrifiers can be also useful to prototype and replicate many existing visualizations. In particular, the ability of the canvas to work as a transmogrification overlay on top of existing interactive visualizations makes it a powerful tool to explore questions about visualizations and about the data itself; for example, would a graph show the same effect if straightened out? How would this look on a perspective-wall? Is there a clear relationship between house prices and distance to the coast?

Although it is too early to say, we think that the composability and bidirectionality of transmogrifications will enable a large set of unexplored avenues. A common problem-solving strategy in physics, math, and engineering is to transform the data into another domain or geometry (e.g., the frequency domain, complex vector space), solve an easier problem in the transformed domain, and transform the solution back to the original domain. Transmogrification enables a similar process for spatial representations.

Finally, this paper is focused on the application of transmogrification to information visualization. During the development of transmogrifiers and the TC we have found many potential applications for collaborative environments (e.g., reproducing Cut-outs [START_REF] Pinelle | Cutouts: A flexible interaction infrastructure for tabletop groupware[END_REF]), image editing (e.g., correcting perspective or drawing in perspective), and art and entertainment (e.g., creating caricatures and fabric patterns).

LIMITATIONS AND FUTURE WORK

Visualization tasks are sometimes focused on representation accuracy. The interactive nature of transmogrifiers and their reliance on touch traces might make it difficult to achieve shape-accuracy, even with the 'magnet' mode. For example, in the hanging rivers example above, the length of a river will be affected by the person's tracing accuracy which, in turn, is affected by the fat-finger problem. Although we see this more as a consequence of the sketch-like and approximate nature of transmogrification than as a problem, there are additional input techniques (e.g., input offset) that could enable better precision when needed.

Our implementation has been refined to avoid deformation artifacts when possible, but deformation of raster images always implies the risk of making text and other symbols less readable. We built a parallel version of transmogrifiers that addresses this problem through vector rendering. Given an initial point within the source shape we calculate its position in the destination shape. In this way, text or other primitives such as lines or glyphs can simply be drawn at their transformed position as shown in Figure 19. Future work is to automatically extract labels from source raster images (similarly to Savva et al. [START_REF] Savva | Revision: automated classification, analysis and redesign of chart images[END_REF]) and alter transmogrifications to preserve text, or recognize and vectorize text and symbols to present in dual vector-raster transmogrifications.

CONCLUSION

In this paper we have presented transmogrification, a visual exploration technique based on arbitrary transformations of 2D shapes. The technique is based on the transformation of arbitrarily-shaped source areas of the image into equally arbitrary destination regions. Through the adaptation of graphic transformations based on a spine, and using novel interaction techniques for the specification of shapes based on multi-touch traces, we enable people to design transformations based on the existing image and create real-time alternative visualizations quickly. We also presented examples that explore the application of transmogrifiers to visual map exploration, distortion compensation, and layout transformation.

Figure 1 .

 1 Figure 1. A) Cycling data: a map with a route and area graphs with average altitude (purple) and heart-rate (orange) at each kilometer. B) The rectified route map aligned under the linear graphs enables comparison of the measured variables to the map features. C) The heart-rate graph wrapped around the route in the map shows effort in spatial context. D) Same as C, but with multiple variables. Map used contains Ordnance Survey data c Crown copyright and database right 2013.

Figure 2 .

 2 Figure 2. The basic interface of the Transmogrifier Canvas, containing two transmogrifiers. A) menu, B) shapes palette, C) imported image, D) control point, E) source shape (single-touch trace), F) imported image edge, G) destination shape (ring), H) transmogrifier lines, I) destination shape (rectangle), J) transmogrified image, K) animation control.

Figure 3 .

 3 Figure 3. A single-point trace shape is created by dragging on free space. A) Spine, B) thickness control, C) sampling handles (red points).

Figure 4 .

 4 Figure 4. A double-point trace shape is created by dragging two fingers on free space. A) Spine, B) borders, C) sampling handles (red points).

Figure 5 .

 5 Figure 5. Implemented animations shown with coloured texture with the source shape (left), the destination (right), and tweened shapes (middle). A) Ring quadrature, B) path distance delay, and C) ribbon.

Figure 6 .

 6 Figure 6. Transmogrification parameterizes a variety of source shapes (left) into parameter space (middle) and then re-maps it to any destination shape (right). Spine curves are shown as dark blue. From top to bottom the shapes are single-trace, double-trace, circle, and rectangle.

Figure 7 .

 7 Figure 7. To render a transmogrifier, we calculate the image's texture coordinates along the source's spine, s, and boundary curves, b & b (left). These coordinates are used to render the transmogrifier shape with texture coordinates placed along the equivalent destination curve.

Figure 8 .

 8 Figure 8. If only the tangent is used, growing the spine into the traceshape produces overlaps (white triangle at bottom). Dark blue: trace (spine); red: path tangent; light blue: constructed bounding curves.

Figure 9 .

 9 Figure 9. Repairing a self-intersection in a boundary curve (left). Center: moving sample points formerly within the loop onto the intersecting line segment. Right: To reduce stretching, we distribute loop points between the intersection and the loop's centroid instead.

Figure 10 .

 10 Figure 10. Straightening rivers. Top: rivers are traced on a map (in green), and transmogrified into a straight shape to present the river's length for visual comparison while retaining local context. River imagery is screen capture of National Geographic's World Rivers Water Map (http://bit.ly/bVOMkq). From top to bottom: the Colorado, St. Lawrence, Volga, MacKenzie, Yellow, Mississippi, Amazon and Nile. Mid section of the rivers omitted for space.

Figure 11 .

 11 Figure 11. Compressing the highway between Las Vegas and Los Angeles. Left: original route cut from surroundings. Right: route transmogrified to show more details around cities and less across the desert.

Figure 12 .

 12 Figure 12. Left) One day of recorded aircraft positions taking off from Lyon airport. The color corresponds to the aircraft altitude (blue for low altitudes, red for high altitudes). Right) The rectified routes. Grey arrows added for clarity.

Figure 13 .

 13 Figure 13. Transmogrification of an icicle plot to a sunburst tree.

Figure 14 .

 14 Figure 14. Transmogrification of a circular chord visualization (left) to a rectangular layout (right). Technique from [33].

Figure 15 .

 15 Figure 15. Transmogrification of a stackedbar graph can be used to straighten the base of one of the regions. Left: stacked graph; right: transmogrification. Technique from [55].

Figure 16 .

 16 Figure 16. Transmogrification of a Nightingale chart into a bar chart, and then back to Nightingale with a subset of the data.

Figure 17 .

 17 Figure 17. Use of several transmogrifiers to create a Table Lens[START_REF] Rao | The table lens: merging graphical and symbolic representations in an interactive focus+context visualization for tabular information[END_REF].

Figure 18 .

 18 Figure 18. Use of three transmogrifiers to create a Perspective Wall [31].collages and sketches (digital and paper) are often useful to reorganize data representations of images or data sets. However, it is difficult to find examples of techniques that allow us to quickly use non-linear and arbitrary transformations, especially in a casual setting.

Figure 19 .

 19 Figure 19. Transmogrification of a rectangular tree source (top) to circular destinations. Left: raster-based result. Right: vector-based result.

http://www.tableausoftware.com/

ACKNOWLEDGEMENTS

We thank the reviewers and the InnoVis group. Research support was provided by the Natural Sciences and Engineering Research Council of Canada, SurfNet, GRAND NCE, AITF, Smart Technologies Inc., and the School of Computer Science at the University of St Andrews.