B Bach

P Dragicevic

D Archambault

C Hurter

S Carpendale

Keywords: (according to ACM CCS): H, 5, 0 [Information Systems]: Information Interfaces and Presentation-General

We review a range of temporal data visualization techniques through a new lens, by describing them as series of operations performed on a conceptual space-time cube. These operations include extracting subparts of a space-time cube, flattening it across space or time, or transforming the cube's geometry or content. We introduce a taxonomy of elementary space-time cube operations, and explain how they can be combined to turn a three-dimensional space-time cube into an easily-readable two-dimensional visualization. Our model captures most visualizations showing two or more data dimensions in addition to time, such as geotemporal visualizations, dynamic networks, time-evolving scatterplots, or videos. We finally review interactive systems that support a range of operations. By introducing this conceptual framework we hope to facilitate the description, criticism and comparison of existing temporal data visualizations, as well as encourage the exploration of new techniques and systems.

Introduction

Temporal datasets are ubiquitous but notoriously hard to visualize, especially rich datasets that involve more than one dimension in addition to time.

Previous work on novel visualizations for temporal data has dramatically advanced the field of information visualization (infovis). However, there are so many different techniques today that it has become hard for both researchers and designers to get a clear picture of what has been done, and how much of the design space of temporal data visualizations remains to be explored. For similar reasons, teaching this research topic to students is challenging. Therefore, there is a clear need to structure and organize previous work in the area of temporal data visualization.

Part of the problem is that information visualization researchers have mostly focused on nomenclature. Most familiar charts have an agreed-upon name, e.g., bar charts or scatter plots, and this tradition has been continued in infovis, where each newly published visualization technique is given a different name. Many textbooks and surveys list ex-isting techniques by their name, both for general visualizations [START_REF] Harris R | Information Graphics: A Comprehensive Illustrated Reference[END_REF] and for temporal visualizations [AMST11].

Although names are essential for indexing, retrieval and communication purposes, they are a poor thinking tool. Because there is no convention for naming techniques, names rarely reflect the essential concepts behind a technique. For example, names such as Value Flow Maps [START_REF] Andrienko | Interactive visual tools to explore spatio-temporal variation[END_REF] and Planning Polygons [START_REF] Shanbhag | Temporal Visualization of Planning Polygons for Efficient Partitioning of Geo-Spatial Data[END_REF] say little about the possible conceptual similarities between the two techniques (see Figure 1). Names can also be ambiguous. For example, the term small multiples is commonly used to refer to a specific type of temporal data visualization [Tuf86]. But Figure 2 shows that two visualizations can be based on small multiples despite being very different conceptually.

There has been recent effort at proposing taxonomies, conceptual models and design spaces for temporal visualizations, mainly focusing on analytical tasks and data types (e.g., object movement data [AAH11, AAB * 11, AA12], video data [BCD * 12], or datasets with different temporal and spatial structures [AMM * 07]). We propose a simple way of describing temporal visualizations based on operations on conceptual space-time cubes. Our work is specific in that it focuses on how to characterize existing techniques, independently from the data and the tasks, and without considering which technique is the most effective. Hence our framework is unique in that it is purely descriptive.

The merit of a clear and detailed descriptive framework is that it helps i) connect techniques that are similar and ii) distinguish techniques that are dissimilar. For example, the two techniques from Figure 1 are the result of a similar operation on a space-time cube and which we call sampling. The term space-time cube originates from cartography, where it refers to a geographical representation where time is treated as a third dimension [START_REF] Andrienko | Visual Data Exploration using Space-Time Cube[END_REF]. One of the earliest uses was by geographer Hägerstand in 1970, who described a "space-time model which could help us to develop a kind of socio economic web model" [Hä70, p. 10]. His intention was to analyze people's behaviour and interactions across space and time. For example, a moving person on a 2D map becomes a static 3D trajectory once visualized as a space-time cube (Figure 3). Since then, space-time cubes have been employed in a number of interactive visualization systems (e.g., [CCT * 99, FLM00, Kra03]), as well as for entertainment purposes [START_REF] Cassinelli | Khronos Projector[END_REF] (see Figure 4). However, they have never been used as a conceptual model for reflecting on temporal visualization techniques. In this article we use the term space-time cube in a similar fashion as in previous work, but with two major differences: 1. A space-time cube is a conceptual representation that helps to think about temporal data visualization techniques in general, not only 3D visualizations. The space-time cube does not necessarily have to appear explicitly in the final visualization nor does it need to be implemented in the system used to generate this visualization. For example, the visualizations in Figure 1 do not show a space-time cube. For most observers, they are purely 2D visualizations.

submitted to Eurographics Conference on Visualization (EuroVis) (2014) 2. A space-time cube does not need to involve spatial data. Many visualizations (e.g., scatterplots, bar charts or node-link diagrams) convey abstract, non-spatial data [START_REF] Munzner | Process and Pitfalls in Writing Information Visualization Research Papers[END_REF]. Nevertheless, they all occupy a 2D space. When data changes over time, such as in GapMinder's animated 2D scatterplots [START_REF] Rosling | Stats that reshape your worldview[END_REF], each animation frame can be conceptually thought of as a slice of a space-time cube. In the term space-time cube, space therefore refers to an abstract 2D substrate that is used to visualize data at a specific time.

Thus it is important to stress that this article is not about space-time cube visualizations, and that 3D space-time cube representations like the one in Figure 3 only represent a very small subset of the techniques we aim to cover.

In addition, our conceptual framework does not consider how space-time cubes are built, e.g., whether or not 2D scatterplots should be used to represent the value of country indicators at any given time. Instead, it assumes that a conceptual 3D space-time cube is already given, and focuses on how this cube can be transformed to accommodate 2D media like computer displays and paper while remaining legible. We show how such transformations are enough to capture most known techniques for visualizing rich temporal datasets. We mostly focus on datasets that involve two dimensions plus time (e.g., spatio-temporal data, dynamic graphs, scatterplots, videos, or any two-dimensional numerical data varying over time), although we later discuss how our model can be extended to other dimensionalities.

We first review common temporal data visualization techniques, and explain how they can be all seen as operations on a conceptual space-time cube. We then describe our framework in more detail by providing definitions of key concepts, as well as a taxonomy of elementary operations and how they can be combined. We then review temporal data exploration systems that show how a range of space-time cube operations can be supported on a single system through interactivity. Finally, we discuss the limitations of our framework and suggest avenues for future work.

Static Visualizations as Space-Time Cube Operations

In this section we illustrate how space-time cube operations can be used to describe a range of common static visualization techniques for temporal data, all meant for screen or paper media. We focus on a small but representative selection of examples from the literature, and describe operations informally, often using analogies from photography techniques and art.

The conceptual space-time cube we use to describe all techniques has three major axes: a time axis, and two orthogonal axes we call data axes. The 2D plane formed by the two data axes is referred to as the data plane. While in Haegerstrand's original illustration the time axis is vertical, in our illustrations time goes from left to right. A time cutting operation consists in extracting a particular temporal snapshot from the cube to be presented to the viewer. Figure 5 illustrates this operation: the left part (1) shows the initial space-time cube and the temporal snapshot that is being extracted, while the right part (2) shows the resulting image that is presented to the viewer.

Time Cutting

For example, consider a photographer who captures a particular instant of a moving scene. If the scene being viewed is represented as a space-time cube (i.e., all possible pictures are piled up to form a cube), then taking a photograph is equivalent to applying a time cutting operation on this cube.

In information visualization, an image produced by time cutting is typically called a time slice. But a temporal visualization rarely consists in a single time slice. As we will see in Section 3, time cutting is typically either performed multiple times and used in combination with other operations, or is used in combination with animation and interaction. Time flattening collapses the space-time cube along its time axis, by merging all time slices into a single 2D image (Figure 6). An analogy is long exposure photography, which collapses several seconds, minutes or even hours of a natural scene into a single image.

Time Flattening

One of the earliest uses of time flattening is Minard's illustration of Napoleon's march towards Moscow (Figure 7). The illustration shows on a single image the state of Napoleon's army (position, size, key events) at different points in time during the Russian campaign in 1812 [Tuf86]. Another early example is Dr. John Snow's map showing where deaths from cholera occurred in London in 1854 (Figure 8(a)). The map shows events from several days aggregated over time. Many maps that show temporal data can be seen as timeflattened space-time cubes. But the time flattening technique is not limited to geographical data, and has been employed in a large variety of information visualization systems as well as in static data graphics. Figure 8(b) for example, shows the evolution of inflation rate and unemployment in Spain from 1990 to 2000. This diagram can be seen as time-flattened version of a space-time cube representing a 2D scatter plot with a single data point evolving over time. Discrete time flattening is similar to time flattening, but instead of merging all time slices into an image, a selection of time slices is made before combining them (Figure 9). The colored time flattening operation is similar to the time flattening operation, but time slices are assigned a color before being combined (Figure 11). Although this operation does not map to any photography technique we know of, similar results could in principle be obtained by rapidly switching color filters during a long-exposure photography.

Discrete Time Flattening

Time Juxtaposing

Time juxtaposing consists in extracting multiple time slices then placing them side-by-side or on a grid (Figure 13).

An analogy is Eadweard Muybridge's multiple camera chronophotography [Muy87]. In contrast with Marey, Muybridge used multiple cameras that recorded snapshots on different locations on the film. He used it for the scientific study of for example horse gaits, and his pictures famously settled the question as to whether horses have all four feet off the ground while trotting. Time juxtaposing is also the base for many forms of sequential art, from ancient Egyptian murals and Greek vase paintings to today's comics [START_REF] Mccloud | Understanding Comics[END_REF].

Time juxtaposing is often used in information visualization to show temporal data such as time-evolving maps, trajectories in space [START_REF] Thudt | Visits: A Spatiotemporal Visualization of Location Histories[END_REF] and dynamic graphs [LNS11, BBL12, RM13, BPF14a]. Figure 2.5 shows forest harvest data over 11 years. In information visualization time juxtaposing is usually referred to as small multiples [CKN * 03], although small multiples are not necessarily built from time slices (see Figure 2(a)). Time juxtaposing has been also widely used for video summarization [START_REF] Truong | Video Abstraction: A systematic Review and Classification[END_REF].

Space Cutting

Space cutting consists in extracting a planar cut in a direction perpendicular to the data plane (Figure 15). An analogy is slit-scan photography, a process where a plate into which a slit has been cut is inserted in front of a camera and Space cutting has also been employed for visualizing temporal data. In the 19th century, Marey created a visualization using space cutting to visualize train connections between major French cities (Figure 16). Space is cut along the rails connecting cities and diagonal lines indicate positions of trains at any time [Tuf86, Mar78]. More recently, space cutting was shown to be useful for analyzing video logs [START_REF] Tang | Exploring Video Streams using Slit-Tear Visualizations[END_REF]: Figure 17 shows a space cut (called tear in the original work) extracted from a video scene, and revealing traffic activity (car count, speed and direction) on a road. The time slice at t 1 is shown to the left, together with the position of the segment extracted. The system is also able to show multiple longitudinal slices on top of each other (i.e. space juxtaposing). Space flattening is similar to space cutting, but involves flattening the cube along a particular direction on the data plane instead of extracting a cut (see Figure 18). where the y-axis is a 1D graph layout, and the x-axis shows when connections are established. Sampling is a more complex operation that consists in extracting space cuts (samples) from a space time cube at several locations on the data plane, then rotating those samples in-place so they face the viewer (Figure 21). Two examples of sampling are mentioned in this article's introduction (Figure 1). The top one shows the evolution of crime statistics in every US state [START_REF] Andrienko | Interactive visual tools to explore spatio-temporal variation[END_REF], while the bottom one shows the evolution of high school population in several districts across three years [START_REF] Shanbhag | Temporal Visualization of Planning Polygons for Efficient Partitioning of Geo-Spatial Data[END_REF]. Although additional operations are involved (e.g., using silhouette graphs to encode values), both examples are conceptually based on a sampling operation. Sampling has also been used in dynamic network visualization, for conveying changes in edge weight [START_REF] Brandes | Asymmetric Relations in Longitudinal Social Networks[END_REF] and in attribute values [START_REF] Hadlak | Supporting the Visual Analysis of Dynamic Networks by Clustering associated Temporal Attributes[END_REF]. 3D rendering is essentially a flattening operation but in contrast with time flattening and space flattening, it is (i) typically done on a plane not orthogonal to the cube's principal axes; (ii) can involve a non-orthographic projection (e.g., perspective projection); (iii) can involve 3D shading, i.e. the addition of light reflections and shadows. In geography and geology, 3D rendering has been used to visualize events such as earthquakes (Figure 23

Space Flattening

An example of use of space flattening in infovis is the History Flow technique for visualizing document histories [VWD04], illustrated in

Sampling

3D Rendering

The Design Space of Space-Time Cube Operations

The previous section reviewed several common operations that turn a conceptual time-space cube into a final twodimensional visualization. Those were examples selected for illustration, and the list was not meant to be exhaustive. In addition, some operations were rather simple (e.g., time cutting), while others were more complex (e.g., sampling) and could be described as a composition of several lower-level operations. Therefore, we provide in this section a more systematic description of the design space of space-time cube operations.

Basic Terminology

A space-time cube operation takes a space-time object and produces another space-time object. A space-time object is a geometrical object within a space-time coordinate system (i.e. two spatial dimensions and one temporal dimension). Possible space-time objects include (i) space-time volumes (of which a complete space-time cube is an example), (ii) space-time surfaces (planar and non-planar), (iii) space-time curves, (iv) points, as well as (v) sets of disconnected volumes, surfaces, curves and points.

The ultimate goal of space-time cube operations is to transform a space-time cube into a space-time object whose shape is compatible with the shape of the media employed to convey the information. By media we mean the visualization's physical presentation, which is the physical object or apparatus that makes a visualization observable to the viewer [START_REF] Jansen | An interaction Model for Visualizations Beyond The Desktop[END_REF]. In the vast majority of cases (i.e. computer displays and paper) the media has a planar shape.

For a given media, a space-time cube operation is complete if it takes space-time volumes as input and produces space-time objects whose shape match the media's shape. Otherwise the operation is incomplete: it cannot be used to produce a valid visualization from a space-time cube. Several elementary space-time cube operations can be chained, in which case they form compound operations. A compound operation is complete if the first operation takes space-time volumes as input, and the last operation produces space-time objects whose shape is compatible with the media.

A Taxonomy of Elementary Space-time cube operations

A taxonomy of elementary space-time cube operations is shown in Figure 24 on the next page. The taxonomy breaks down space-time cube operations into five main classes:

• Extraction consists in selecting a subset of a space-time object (e.g., extracting a line or cut from a volume),

• Flattening consists in aggregating a space-time object into a lower-dimensional space-time object (e.g., projecting a volume onto a surface),

• Filling consists in turning a set of disconnected spacetime objects into a fully connected space-time object,

• Geometry transformation consists in transforming a space-time object spatially without change of content,

• Content transformation consists in changing the content of a space-time object without affecting its geometry.

The table in Figure 24 shows how general operations break down into more specific operations. On each of the two columns, general operations are on the left while more specific operations are on the right. Operations that are the most specialized (i.e. leaves on the taxonomy tree) are shown on a white background. Operations written in bold are those which produce planar surfaces, i.e. can be used as final operations on screen-based and paper-based media.

We quickly review the most specialized operations (white background), going from top to bottom on the left column, then on the right column. We also describe the parameters necessary to specify each space-time cube operation. Most of the operations have already been used in infovis, others have been added for completeness.

• Extraction:

-Point extraction consists in selecting a specific point inside a space-time volume. This operation is defined by a 2D position on the data plane and a time value. -Linear space cutting consists in extracting a planar cut from a space-time volume in a direction orthogonal to the data plane (see Section 2.6). It is also complete, and takes as parameter a line or a segment parallel to the data plane that once extruded over time defines the cutting surface. -Oblique cutting consists in extracting a planar cut from a space-time volume that is neither orthogonal to the time axis, nor orthogonal to the data plane (e.g. [START_REF] Fels | Techniques for Interactive Video Cubism[END_REF]). It takes as parameter a 3D cutting plane. -Curvilinear space cutting is similar to linear space cutting except the cutting surface is produced by extruding a curve parallel to the data plane that is neither a line nor a segment. This operation produces non-planar space-time surfaces that further need to be flattened (e.g., using 3D rendering [START_REF] Tominski | Stacking-Based Visualization of Trajectory Attribute Data[END_REF]) or unfolded (as in Figure 16). -Time chopping is similar to time cutting but slices have a thickness instead of being infinitely thin. Since it produces volumes it is not complete for 2D media, and thus needs to be complemented with additional operations. It takes as parameter a time segment that defines the two cutting slabs (a slab is the infinite region between two planes). -Linear space chopping, oblique chopping and curvilinear space chopping are similar to the previous cutting operations, with the difference that they produce volumes with a certain thickness instead of infinitely thin surfaces.

• Flattening:

-Time flattening aggregates a space-time volume into a plane orthogonal to the time axis (see Section 2.2). for more details).

• Filling:

-Time interpolation consists in filling "holes" in space-time objects (volumes, surfaces or curves) by interpolating between values along the time axis. It takes as parameter a monovariate interpolation function. For example, a piecewise linear time interpolation operation will transform a set of time slices into a full space-time cube by linearly interpolating the values (e.g., RGBA colors) between pairs of successive time slices. -Space interpolation consists in filling "holes" in space-time objects by interpolating between values on each data plane. It takes as parameter a bivariate interpolation function. For example, a bilinear space interpolation operation will transform a set of lines parallel to the time axis into a full space-time cube. -Volume interpolation consists in filling "holes" in space-time objects by interpolating across both space and time. It takes as parameter a trivariate interpolation function. One example is interpolating video frames using motion estimation techniques [START_REF] Choi B.-T | New frame rate upconversion using bi-directional motion estimation[END_REF].

• Geometry Transformation:

-Space shifting, time shifting, yaw, roll and pitch consist in moving or rotating space-time objects. They can be used, e.g., for placing multiple cuts side-by-side or for rotating an entire space time cube rendered in 3D (e.g. [KW04,CCT * 99,BPF14b]). They each take a single scalar value as parameter. -Time scaling and space scaling rescale space-time objects along their principal axes. They take as parameters one and two scalar values respectively, that define the scaling factor. -Bending deforms space-time objects. For example, a space-time volume can be bent such that the time axis follows an arc instead of a line [START_REF] Daniel | Video Visualization[END_REF]. This operation takes as parameter a deformation function that maps 3D locations to 3D locations. -Unfolding transforms a non-planar space-time surface submitted to Eurographics Conference on Visualization (EuroVis) (2014) into a planar space-time surface. An analogy is a map projection function that transforms a sphere or portion of sphere into a plane. An example of space-time unfolding is Maray's train schedule (Figure 16), which can be seen as an unfolded curvilinear space cut performed on a time-evolving 2D map.

• Content Transformation:

-Time coloring consists in altering the colors of each time slice according to time. Examples include coloring each time slice uniformly according to a linear color scale (Figure 12), changing the hue of each time slice, or dividing the time axis in different regions and applying a discrete color scale (Figure 7). -Space coloring alters the color of points in a spacetime volume depending on their 2D position on the data plane. -Difference coloring consists in altering the colors of each time slice according to the difference between time slices.

Adaptive and Semantic Operations

So far we mostly described operations that are agnostic to the data and the content of the cube. Adaptive operations take into account the shape or content of the particular space-time objects they operate on. For example, an adaptive time cutting operation can be used to cut cubes according to regions with large changes instead of cutting them into regularlyspaced slices. This technique is used, for example, in adap-tive video fast-forward [START_REF] Petrovic | Adaptive Video Fast Forward[END_REF]. Similarly, an unfolding operation that works on any surface (as opposed to, e.g., only spheres), would be an adaptive unfolding operation.

Semantic operations take into account the data semantics of the space-time objects they operate on. One example would be a semantic volume interpolation operation that connects discrete sets of moving objects with lines or tubes (see Figures 8(b) and 23(b), as well as [START_REF] Rosling | Stats that reshape your worldview[END_REF]BPF14a]). This type of operation is semantic because it needs to know the identity of the objects to be able to match them on successive time slices. Time labeling operations such as the one used in Figure 8(b) are also semantic, because they need to know the location of datapoints of interest to place the labels appropriately. Filtering operations can also be semantic, as well as recoloring operations [VWD04, RFF * 08, BPF14b]. Finally, semantic operations can also be used to cut cubes according to specific temporal cycles (days, weeks, etc.).

Compound Operations

We previously defined compound operations as several operations applied in sequence. According to our taxonomy from Figure 24, some of the operations we introduced in Section 2 are elementary, namely time cutting, time flattening, space flattening. Others are compound and can be broken down as indicated in Table 1. In our notation, the symbol + refers to a composition, the symbol * refers to operations applied multiple times and the symbols [ ] refer to optional operations. A compound operation inherits the parameters of its suboperations. For example, a discrete time flattening operation is specified by a sequence of time values, as well as a projection function and an aggregation function. But in practice, most compound operations enforce constraints between their parameters. For example, all space scalings from a time juxtaposing operation are typically the same.

Many elaborate temporal data visualization techniques can be described as compound operations. For example, the Visits technique (Figure 25) employs (time chopping + time flattening + space shifting)*.

Dynamic Operations

So far we only considered operations (both elementary and compound) that transform a space-time cube into a static visual representation. On computer displays, operations can also be applied in a dynamic manner. Dynamic operations can involve either animation or interaction.

Animation

We refer to animation as the process of applying different operations on a space-time cube over time, or similarly, varying the parameters of an operation over time.

The most common form of animation consists in changing the position of a cutting operation over time, i.e. animated time cutting. This results in the space-time cube content being "played back". For example, if the space-time cube represents a visual scene like video surveillance data, synchronizing the motion of the slice with a clock will result in a real-time playback of the original scene. When significant data is skipped during playback, the animation is closer to a discrete time juxtaposing operation, except slices are shown in sequence instead of being laid out side-by-side.

An animated time cutting operation can be preceded by a filling operation order to produce smooth animated transitions. Many examples exist in the literature, for example when animating dynamic networks [ATMS * 11, RM13, BPF14a] or scatterplots [Ros06, RFF * 08]. Most of these examples can be described as semantic volume interpolation + animated time cutting operations. Animated time cutting can also be combined with other space-time cube operations such as time flattening. For example, Gapminder can combine scatterplot animations with static trails for points of interest (a filtering + time flattening operation) [START_REF] Rosling | Stats that reshape your worldview[END_REF].

While many animation techniques can be described as animated time cutting on static space-time cubes, more elaborate techniques require operations to be applied in real-time. For example, Hurter et al.'s system [HEF * 13] uses animated time chopping to animate a network over time while preserving temporal context information. At every animation frame, a time flattening is applied that produces colored trails and a dynamic bundling operation is applied that guarantees a continuous animation without jumping bundles [START_REF] Hurter | Graph Bundling by Kernel Density Estimation[END_REF].

Although animated time cutting and its many variants are the most common forms of animation, other animated op-erations exist. For example, animated 3D rendering can explain a transition between two space-time cube operations to a user by smoothly rotating a space-time cube representation [START_REF] Bach | Visualizing Dynamic Networks with Matrix Cubes[END_REF]. This technique will be discussed in Section 4, where we review space-time cube visualization systems.

Interaction

Interaction is similar to animation except the changes in the space-time cube operations are under the user's control.

Consider animated time cutting: if the position of the cutting plane is controlled by the user (e.g., by dragging a slider) instead of being automatically moved, then the operation becomes interactive time cutting. A common implementation of interactive time cutting is the seeker bar on a video player. As with animations, any operation can be made interactive. Examples of interactive operations abound, and we will review some of them in the next section.

Space-Time Cube Systems

Choosing an appropriate space-time cube operation depends on many factors and almost always involves tradeoffs. In this section we review a representative sample of visualization systems that address this issue by supporting multiple spacetime cube operations. Such systems almost invariably use 3D rendering as an explicit representation of the space time cube, both for showing an overview and for explaining how different operations relate. We call these systems space-time cube systems. Because they work by letting people switch between different operations and tune their parameters, interaction is a key feature. GeoTime is a carefully-designed commercial system for analyzing spatio-temporal data [geo, KW04]. Events are shown as spheres on a 3D rendering view that can be freely (Figure 27(a)). This view also uses a reference plane, and a semantic volume interpolation operation is applied to indicate event ordering. Users can perform time chopping operations by dragging on a timeline widget. GeoTime also supports time flattening and space flattening. Figure 27(a) shows a space flattening view where time runs from top to bottom, and a reference plane is provided that can be rotated. Thin gray lines connect the two views. Finally, pan & zoom is supported through space chopping + space scaling. Tardis [CCT * 99, CFC * 96] is a system for visualizing environmental data using 3D rendering in combination with advanced space-time cube operations. The voxels in the cube are color-coded depending on the type of vegetation, its age, soil characteristics or the presence of bush fires (Figure 28).

CommonGIS

Tardis

Tardis implements interactive semantic filtering: users can, e.g., select a particular type of vegetation or a range of vegetation ages. In addition, Tardis supports interactive orthogonal cutting, but in contrast with our previous examples, cutting is always used in combination with 3D rendering. Users can define and manipulate multiple orthogonal cutting planes (Figure 28 VISUAL-TimePAcTS is a system for analyzing activity diaries [VFC10]. It uses non-geographical space-time cubes. The cube's two data axes can be mapped to data dimensions such as individuals, locations, or activities. We focus on the case where one axis maps to individuals while the other axis maps to activities. Activities are also encoded using color.

VISUAL-TimePAcTS

VISUAL-TimePAcTS supports linear space flattening on both data axes. Figure 29(a) shows 6 individuals (horizontal axis) and their activities (colors) across time (vertical axis). Figure 29(c) shows the evolution of activities aggregated across all people over time. VISUAL-TimePAcTS supports a seamless transition between the two operations through interactive 3D rendering (Figure 29(c)). Since 3D rendering employs orthographic projection and no shading, it is essentially an oblique flattening operation.

VISUAL-TimePAcTS supports a more elaborate spacetime cube operation that prevents visual marks from overlapping due to flattening. In Figure 29(c), for example, individuals are horizontally offset when several of them do the same submitted to Eurographics Conference on Visualization (EuroVis) (2014) activity at the same time. This technique is called shearing by the authors, and is further explained in Figures 29(d), 29(e). This technique is essentially a (linear space cutting + space offset)* + space flattening operation, and is a hybrid between space juxtaposing and space flattening.

Cubix

Figure 30: Different operations applied to a time-evolving adjacency matrix in Cubix [START_REF] Bach | Visualizing Dynamic Networks with Matrix Cubes[END_REF] Cubix is a system for analyzing dynamic weighted networks through adjacency matrix representations [START_REF] Bach | Visualizing Dynamic Networks with Matrix Cubes[END_REF]. A 3D rendering provides an overview of the data (Figure 30(a)). Time goes from left to right. Each cell of the cube represents a connection between two nodes at a given time, with size depending on connection weight. Cells can be color-coded according to time, weight, or direction.

Cubix supports a range of space-time cube operations, including time juxtaposing (Figure 30(b)), space juxtaposing (detail in Figure 30(d)), animated time cutting , animated space cutting, time flattening and space flattening. For flattening operations, cells can be made translucent to visually aggregate the history of connections. Cubix also supports semantic filtering on connections based on their weight.

Cubix provides a control widget in the form of a stylized cube, and whose different parts can be clicked or dragged to switch between operations. All operation switches are explained using animated transitions through rotations of the 3D rendering representation, or through staged animations of extraction and rigid transformation operations.

Video Cube Systems

Several space-time cube systems have been proposed to support video analysis [MB98,FLM00,DC03,CI05]. Video Cubism [START_REF] Fels | Techniques for Interactive Video Cubism[END_REF] uses a 3D rendering representation together with an interactive volume extraction operation that is defined by manipulating a planar cutting plane (Figure 31(a)). Similary, Khronos projector [START_REF] Cassinelli | Khronos Projector[END_REF] supports manipulation of a non-planar cutting plane using touch or mid-air gestures (Figure 4). V 3 [DC03] (Volume Visualization for Videos) supports different operations, including time juxtaposing and a 3D rendering view that can be combined with a bending operation (Figure 31(b)). V 3 also supports filtering operations that allow removal of pixels of a certain color, or pixels that do not change across a given time period.

Besides the space-time cube systems reviewed in this section, there is a wealth of general 3D visualization systems. Commercial and research tools exist in domains such as geovisualization (e.g., Voxler [Vox], ArcGIS [arc]), scientific visualization (e.g., VTK [SAH00], Matlab [mat] and R [r]), and medical visualization [START_REF] Mcguffin | Using Deformations for Browsing Volumetric Data[END_REF]. Although these tools do not treat time as a specific dimension, they can be used to inspire the design of interactive space-time cube systems.

General Discussion

We now discuss the limitations of our descriptive framework and consider areas for future research, including: unifying our framework with the infovis pipeline model, extending it to other dimensionalities, considering non-planar media such as physical visualizations, characterizing the inner structure of time space cubes, and considering the strengths and weaknesses of different space-time cube operations.

Comparison with the Infovis Pipeline Model

Since our framework builds on the notion of composition of operations, it shares similarities with another common model: the infovis reference model, also called the infovis pipeline [CMS99, Chi00, JD13]. The infovis pipeline sees visualization as a data-flow process, i.e., a sequence of stages and transformations that turn raw data into a final image. These transformations commonly include data transformation, visual mapping, presentation mapping and rendering [START_REF] Jansen | An interaction Model for Visualizations Beyond The Desktop[END_REF]. Interactivity is implemented by having data analysts alter these transformations at different stages.

There is clearly an analogy between transformations and operations. However, the infovis pipeline and our framework differ in several important respects. The infovis pipeline is a submitted to Eurographics Conference on Visualization (EuroVis) (2014) general model for visualizations, where the sequence of operations is fixed, but the operations themselves are rather abstract. For example, the pipeline model provides no specific details about what happens in the visual mapping transformation. In contrast, our model only captures a specific family of visualizations (temporal visualizations), its sequence of operations is not fixed, and the operations are more concrete. The infovis pipeline is more general but too high-level to capture the similarities and differences between the visualizations we presented. On the other hand, our model is incomplete in that it does not define how the space-time cube is built. The two models are therefore complementary.

Since the infovis pipeline has inspired the software architecture of several infovis tools [Fek04], it is worth considering to what extent the two models can be unified. Several space-time cube operations could in principle be implemented at different stages of the infovis pipeline. For example, time flattening can be performed at the data transformation stage, by aggregating raw data over time. Alternatively, time flattening could be emulated by explicitly rendering a 3D space-time cube on the screen and using a proper camera placement and projection transformation. In that case, it would be implemented at the rendering level.

However, these approaches would only provide a very partial support for space-time cube operations. For a full support, our space-time cube needs to be reified as a first-class object. Since it is both abstract and visual, our space-time cube best aligns with the abstract visual form stage of the pipeline [START_REF] Jansen | An interaction Model for Visualizations Beyond The Desktop[END_REF]. Thus space-time cube operations are best seen as presentation mapping transformations, i.e., transformations that turn the abstract visual form into a fullyspecified 2D image or 3D model [START_REF] Jansen | An interaction Model for Visualizations Beyond The Desktop[END_REF]. In other terms, our space-time cube operations can be used to decompose and refine the presentation mapping transformation of the infovis pipeline. We believe that implementing our framework in this way could dramatically facilitate the exploration of a wide range of temporal visualization techniques.

Other Dimensionalities

This review focused on temporal visualizations that involve two spatial dimensions plus time. These two dimensions can be inherently spatial or can result from 2D spatial encodings of abstract data. However, temporal visualizations with other dimensionalities are possible.

Most notably, a rich variety of temporal visualizations exist that involve a single spatial dimension plus time, e.g., timelines and time-series visualizations [AMST11]. In principle, our framework still applies if the 3D space-time cube is turned into a 2D space-time plane. Operations analogous to our geometry transformation operations would capture techniques such as spiral visualizations, calendar visualizations or cycle plots [AMST11]. However, since a 2D spacetime plane already naturally maps to a 2D planar display, and since the richness of time-series visualizations and timelines mostly stem from the visual encodings used, the usefulness of our framework would be less clear in this case.

Other temporal visualization techniques, although less common, show three spatial dimensions plus time. We believe most of them can be captured with operations on 4dimensional space-time hypercubes. For example, Tufte explains how small multiples can be used to show the evolution of a three-dimensional storm [START_REF] Baker | After the storm: Considerations for information visualization[END_REF]. This approach amounts to applying a time juxtaposition operation on a space-time hypercube, where each time cutting operation yields a 3D image. Similarly, FromDady [HTC09] uses 3D trails to show the trajectories of airplanes in space. This technique amounts to performing a time flattening on a spacetime hypercube. Extending our framework to higher data dimensionalities is an exciting topic for future research. However, it is less easy to imagine a hypercube than a cube, so the merits of such a conceptual model still remain to be seen.

Non-Planar Media

Throughout this review we assumed the presentation medium to be planar. Although these are by far the most common, other display shapes are being explored in HCI, some of which are even deformable [START_REF] Rasmussen | Shape-changing interfaces: a review of the design space and open research questions[END_REF]HV08]. In these cases, the conditions for an operation to be complete are not the same. This opens up a wide range of possibilities for new visualization designs. For example, one implementation of the Khronos projector (Figure 4) employs back projection on a freely deformable cloth, allowing the use of non-planar cutting operations that are complete. In addition, physical visualizations make it possible to faithfully display 3D space-time cubes without any additional operations Cuts can be taken apart and manipulated freely, allowing for time juxtaposing and space juxtaposing as well as time flattening and space flattening, if viewed from a proper orthogonal angle and distance. For another example see [STB].

The Inner Structure of Space-Time Cubes

In this review we considered space-time cubes as monolithic entities. Two space-time cubes can however look quite different, depending on what data is visualized: migration of animals, earthquakes, changes in vegetation and ecosystems, networks with changing connections, surveillance videos, or scatterplots evolving over time. We can refer to this lowerlevel decomposition as the cube's inner structure.

Inner structure is likely to be an important factor when choosing between space-time cube operations. For example, videos produce maximally dense inner structures and therefore are not well-suited to 3D rendering, unless complementary operations such as filtering are used (Figure 31(b)). Structures that present large variations over time may not be well-suited to time juxtaposing because objects could be difficult to relate across time slices. We plan to extend our descriptive framework by characterizing different types of inner structures for space-time cubes.

Which Operation to Choose?

Again, our contribution is a descriptive conceptual framework, and we chose not consider the relative merits and limitations of different techniques. We believe that a detailed descriptive model is a necessary first step, before considering performance issues. The question however remains as of which operation works best under which context. Several studies comparing space-time cube operations have been reported in the past. Many of them compared animation (usually animated time cutting) against static visualizations (usually time juxtaposing) [TMB02, GMH * 06, RFF * 08, APP11, FQ11, AP12b], finding benefits and drawbacks for both approaches. Other studies evaluated space time-cube representations (i.e., 3D rendering) against a range of baseline conditions, including time flattening [KDA * 09, WvdWvW09, KK12, AABW12], time cutting [WvdWvW09, BCH07], and space cutting [AABW12]. Although such empirical investigations are crucial for the advancement of science, only a subset of all possible operations have been covered, and many of the existing findings are hard to generalize beyond the domain, type of data, and operation parameters used in the stimuli. For example, animation can mean either animated time cutting or interactive time cutting, and space-time cube visualizations can be implemented in a multitude of ways, including in the content A clear and descriptive framework would allow us to better structure this body of evidence and tease apart the effects of different subtle design features and to better control for confounds. We showed how many temporal visualization techniques can be decomposed into elementary operations. These operations can be combined in many ways or made dynamic at different levels (either through animation or interaction). The characterization of the inner structure of space-time cubes, may already provide many elements to discuss the practical strengths and weaknesses of space-time cube operations, mostly based on well-established knowledge on perception and HCI, and on common sense.

Running studies for answering specific research questions will naturally remain important, and we hope our descriptive framework will facilitate the design of such studies and the discussion of findings in a more informative manner.

Other Limitations

Our framework is designed as a thinking tool. Like any model, it is necessarily incomplete. First, our taxonomy of elementary operations in Figure 24 is not meant to cover all possible operations. Second, our framework does not provide much guidance for interaction design: the design space for interactive operations has only been partially explored. Finally, not all techniques for visualizing temporal data can be captured with space-time cubes. For example, temporal data can be visualized using two time axes instead of a single data axis (see Figure 33). Our framework is not meant to restrict creativity but rather to help visualization designers find new solutions, extend or generalize existing ones, and think out of the box. Again, our framework assumes that the space-time cube already exists. It does not provide guidance for producing the space-time cube itself. For abstract data, many visual mappings can be used to produce individual slices. For example, locations on a map can yield values for altitude, temperature, rain, vegetation and soil type. How to visualize all these attributes at any particular point in time is a general problem of information visualization, but the choice may also affect the efficiency of later space-time cube operations.

Conclusion

We reviewed various techniques to visualize temporal data, by describing them as sequences of parametric operations applied to a conceptual space-time cube. Our operations are independent from the underlying data and can be applied across a range of application domains, be they cartography, dynamic network analysis, geopolitics, or video analytics.

By introducing domain-agnostic concepts and a clear terminology, this article aims at facilitating the comparison of different approaches for visualizing temporal data. Existing visualizations from one data domain can be analyzed in terms of elementary operations and then be adapted to other domains and problems.

By giving a better vision of the richness of the design space, we hope our model will also motivate the exploration of new approaches. It also stresses the importance of developing fully-integrated interactive systems and toolkits that can support a range of techniques in a consistent manner.

Our model also aims at facilitating the design of studies and discussing their results in a more informative manner. We hope the presented terminology and low-level concepts will help design better experiments that tease out important factors in dynamic data visualization. Many more controlled studies are needed to understand the trade-offs between different space-time cube operations and how they perform depending on the task, the data, and the people that use them. This work mostly arose out of the need to teach temporal information visualization to undergrad students. We therefore hope that it will help other people teach this field effectively, by providing a clear structure and a clear terminology on which to base higher-level discussions and analyses.

Biography

Benjamin Bach is a PhD student in the Aviz group at IN-RIA, France, since 2011. He received his Masters Degree in 2010 from the Department of Computer Science at the University of Technology, Dresden, Germany. His research focuses on network visualization, visualization of temporal data, interaction for information visualization.

Pierre Dragicevic is a permanent researcher in the Aviz group at INRIA, France, since 2007. He is doing research on human-computer interaction and information visualization, with a focus on animation, direct manipulation, physical visualization, visual perception and decision making.

Daniel Archambault is a lecturer at Swansea University (since 2013). His research interests include information visualization, graph drawing, and perceptual issues in visualization. Daniel has worked in the area of dynamic graph drawing and has conducted human-centered experiments involving presentation methods for dynamic graphs such as animation and small multiples as well as drawing stability (or the "mental map").

Christophe Hurter is an associate professor at the Interactive computing laboratory (LII) at the French Civil Aviation University (ENAC) in Toulouse, France, since 2011.

His research interests lie in the areas of information visualization and human-computer interaction, with a focus on visualization of multivariate data in space and time, the design of scalable visual interfaces and the development of pixelbased algorithms such as bundling rendering techniques.

Sheelagh

  (a) Value flow diagram [AA04b] (b) Planning Polygons [SRdJ05]

Figure 1 :

 1 Figure 1: Two conceptually similar temporal visualization techniques showing: (a) the evolution of crime statistics in every US state; (b) the evolution of high school population in several districts across 3 years.

Figure 2 :

 2 Figure 2: Two visualizations using small multiples to show the same indicator data for 4 countries over 6 years, but which are conceptually very different.

  Figure 2(a) involves operations such as filtering, time flattening and space shifting, while Figure 2(b) is the result of a compound operation we call time juxtaposing.

Figure 3 :

 3 Figure 3: A space-time cube based on an illustration by Hägerstrand [Hä70] in 1970, showing social interactions across space and time.

Figure 4 :

 4 Figure 4: Khronos projector [CI05] lets users dig into video cubes: here, a scene transitioning from day to night.

Figure 5 :

 5 Figure 5: The time cutting operation.

Figure 6 :

 6 Figure 6: The time flattening operation.

Figure 7 :

 7 Figure 7: A famous example of time flattening: Napoleon's march to Moscow by Joseph Minard [Tuf86].

Figure 8 :

 8 Figure 8: Other examples of time flattening: (a) Detail of the map of the cholera outbreak in London 1854, by Dr. John Snow. Piled bars mark the number of death per house. (b) Connected scatterplot showing the relationship between inflation rate and unemployment in Spain from 1990 to 2000.

Figure 9 :

 9 Figure 9: The discrete time flattening operation.

  An analogy for discrete time flatting is multiple exposure photography, where several photos are taken at different times and blended into a single image. Etienne-Jules Marey pioneered this technique in 1882 with an instrument (the chronophotographic gun) that records 12 photos per second on the same film, and used it to visualize human and animal motion [Mar78]. Modern art has also employed a similar technique to convey movement, e.g., Marcel Duchamp's "Nude Descending a Staircase, No. 2".

Figure 10 :Figure 11 :

 1011 Figure 10: An example of discrete time flattening. For a better infographic by Megan Jaegerman, see [Tuf].

Figure 12 :Figure 13 :

 1213 Figure 12: Two visualizations using colored time flattening. (a) Illustration of a dynamic graph visualization as used in GEVOL [CKN * 03]. (b) Stroke order in Chinese characters [Wik13]; the color legends have been added.

Figure 14 :

 14 Figure 14: Time juxtaposing showing approved forest harvest applications across 10 years [Gre11].

Figure 15 :

 15 Figure 15: The space cutting operation.

Figure 16 :

 16 Figure 16: Example of space cutting: horizontal lines indicate train stops, vertical lines indicate times, and diagonal lines indicate moving trains [Mar78].

Figure 17 :

 17 Figure 17: Space cutting used to show road traffic [TGF08].

Figure 18 :

 18 Figure 18: The space flattening operation.

  Figure 19: the right panel shows the last revision of a Wikipedia article, each color corresponding to a specific contributor. The left visualization shows the history of the article, built by collapsing each article revision into a one-pixel column, and then displaying all columns side-by-side. These operations are equivalent to flattening the article's space-time cube along the x data axis.

Figure 19 :

 19 Figure 19: An example of space flattening showing the edit history of a Wikipedia article [VWD04].

Figure 20 :

 20 Figure 20: An example of space flattening for showing article citations over time [SA06, AS].

Figure 21 :

 21 Figure 21: The sampling operation.

Figure 22 :

 22 Figure 22: The 3D rendering operation.3D rendering consists in showing a space-time cube the way three-dimensional objects are typically displayed on 2D media, i.e. by projecting it onto a 2D plane (Figure22).

  submitted to Eurographics Conference on Visualization (EuroVis)(2014)

Figure 23 :

 23 Figure 23: Two examples of 3D rendering. (a) Occurrence of earthquakes (authors' illustration after [GAA04]), and (b) a dynamic Network [DG04]

  (a)) or the movement of objects [Kra03, GAA04]. 3D rendering is also common in temporal information visualization. For example, in networks whose connectivity change over time, nodes can be represented as columns and links as bridges [DG04, BC03] (Figure 23(b)). When the layout of the dynamic network also changes, nodes become worms [DE02, GHW09].

Figure 24 :

 24 Figure24: Taxonomy of elementary space-time cube operations with schematic illustrations. Gray shading indicates nonleaves, bold indicates complete operations. The Time column regroups operations that are applied according to the time axis, while the Space column regroups operations that are applied according to the data plane.

  submitted to Eurographics Conference on Visualization (EuroVis)(2014)

Figure 25 :

 25 Figure 25: Compound operation in Visits [TBC13].

Figure 26 :Figure 27 :

 2627 Figure 26: CommonGIS [AA99] (picture from [AA04a]) CommonGIS [AA99] is a feature-rich analytical system for spatio-temporal data. It supports several space-time cube operations, including time flattening and 3D rendering (Figure26). The 3D rendering view is combined with a semantic filtering operation to make the space-time cube transparent: geographical context is only shown on a single time slice, as a reference plane. Two widgets provide control of the projection function (arrow in Figure26). One controls the camera position around the cube, the other one controls its height.

  (a) 3D rendering with multiple time and space cutting (b) 3D rendering with multiple volume extraction+translation

Figure 28 :

 28 Figure 28: Tardis [CCT * 99] and visual access [CFC * 96]

  (a)). Further operations include opening the cube like a book (interactive (volume extraction + rotation)*) or apply a 3D fisheye effect (interactive (volume extraction + translation)*). This fisheye effect, called "Visual Access Distortion", pushes away voxels from the cursor (Figure 28(b)).

Figure 29 :

 29 Figure 29: VISUAL TimePAcTS [VFC10]. (a) Space Flattening on activities, (b) Oblique flattening, (c) Space flattening on individuals.

Figure 31 :

 31 Figure 31: (a) Video Cubism [FLM00]; (b) V 3 [DC03].

Figure 32 :

 32 Figure 32: Two physical implementations of the Matrix Cube visualization [BPF14b] for dynamic networks, made by this article's first author.

  [JDF13, JD13]. Many such visualizations have been already crafted by scientists, artists and designers [DJ13]. Physical temporal visualizations can even be made modular to support interactive space-time cube operations. Figure 32 shows two physical representations of a dynamic netsubmitted to Eurographics Conference on Visualization (EuroVis) (2014) work [BPF14b] made of laser-cut and laser-engraved acrylic. The left version supports interactive time cutting while the right version supports interactive space cutting.

Figure 33 :

 33 Figure33: Visualization of energy consumption over time[START_REF] Van Wijk | Cluster and Calendar Based Visualization of Time Series Data[END_REF]. One horizontal axis is mapped to days while the other one is mapped to hours. transformations they use (e.g., aggregation [BCH07] or filtering [AABW12]), and in the interactions they implement. Overall, findings are very hard to compare for a lack of a consistent descriptive terminology.

  Time drilling consists in extracting a line parallel with the time axis. It is uniquely specified by a 2D position on the data plane. For example, sampling (Section 2.8) uses several drilling operations. -Space drilling extracts a line perpendicular with the time axis. It is specified by a 2D line and a time value. -Oblique drilling consists in extracting an arbitrarily oriented straight line from within a space-time volume. -Planar curvilinear drilling consists in extracting a planar 3D curve from a space-time volume. This operation, as well as all operations above, is complete for 2D media. -Non-planar curvilinear drilling consists in extracting an arbitrary 3D curve from a space-time volume. It is incomplete, and hence needs to be combined with other operations like flattening or unfolding. This operation can be used to extract object trajectories [KW04, RFF * 08]. -Time cutting consists in extracting a planar cut from a space-time volume in a direction orthogonal to the time axis (see Section 2.1). It takes as parameter a time value that defines the cut position on the time axis. It is a complete operation for 2D media.

submitted to Eurographics Conference on Visualization (EuroVis) (2014) -

  This operation takes as parameters a time value, a projection function and an aggregation function. The projection function maps 3D points to points on the plane. Examples include orthographic projection and perspective projection. The aggregation function describes how point values are combined. If values are defined in an RGBA color space, the function maps vectors of RGBA colors to a single RGBA color. Examples of such functions include alpha-blending (e.g., averaging all colors) and overplotting (i.e. only keeping the last color).-Space flattening, oblique flattening and non-planar flattening are similar operations, but the surface on which the volume is projected is different (see previous cutting operations as well as Sections 2.7 and 2.9

Table 1 :

 1 Compound operations decomposed.

	Compound Operation	Elementary Operations
	Discrete time flattening	time cutting* + time flattening
	Colored time flattening	time coloring + time flattening
	Time juxtaposing	(time cutting + space scaling + space
		shifting)* + time flattening
	Marey's schedule	curvilinear space cutting + yaw + un-
		folding
	Slit tears	(linear/curvilinear space cutting +
		yaw + [unfolding] + space shifting)*
	Sampling	(time drilling + time scaling + yaw)*
	3D rendering	[shading] + oblique flattening

  Carpendale is a professor at University of Calgary, where she also holds a Canada Research Chair in Information Visualization. She leads the Innovations in Visualization (InnoVis) Research Group. Her research on information visualization, large interactive displays, and new media draws on her interdisciplinary background in art, design and computer science. She has contributed a number of novel techniques for temporal data visualization.

submitted to Eurographics Conference on Visualization (EuroVis)

(2014)

submitted to Eurographics Conference on Visualization (EuroVis)(2014)

Acknowledgements

Collaboration on this work was initiated by Dagstuhl Seminar "Putting Data on the Map 12261", June 2012, and supported in part by NSERC, SMART Technologies, AITF, Surfnet and GRAND NCE, as well as by Clique Strategic Research Cluster funded by Science Foundation Ireland (SFI) Grant No. 08/SRC/I1407.


Emmanuel Vincent
email: emmanuel.vincent@inria.fr

Aggelos Gkiokas
email: agkiokas@ilsp.gr

Dominik Schnitzer

Arthur Flexer
email: arthur.flexer@ofai.at

An investigation of likelihood normalization for robust ASR

Keywords: noise-robust speech recognition, concentration of distances, hubness

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

While automatic speech recognition (ASR) is now very effective in clean conditions, reverberant and noisy conditions still pose a great challenge [START_REF] Baker | Research developments and directions in speech recognition and understanding, part 1[END_REF]. Robust ASR techniques operate by compensating for the impact of reverberation and noise in the features, in the acoustic models, or both [START_REF] Droppo | Environmental robustness[END_REF][START_REF] Wölfel | Distant Speech Recognition[END_REF][START_REF] Deng | Front-end, back-end, and hybrid techniques for noiserobust speech recognition[END_REF][START_REF] Virtanen | Techniques for Noise Robustness in Automatic Speech Recognition[END_REF].

Among the earliest feature transforms, cepstral mean and variance normalization [START_REF] Viikki | Cepstral domain segmental feature vector normalization for noise robust speech recognition[END_REF] reduce the variability of the features by equalizing their moments across all environments. Featurespace maximum likelihood linear regression (fMLLR) [START_REF] Gales | Maximum likelihood linear transformations for HMM-based speech recognition[END_REF] and linear discriminant analysis (LDA) [START_REF] Häb-Umbach | Linear discriminant analysis for improved large vocabulary continuous speech recognition[END_REF] provide more flexibility by generatively or discriminatively adapting the transform to the environment. Such linear transforms greatly increase robustness to channel mismatch, but less so to reverberation and noise which result in nonlinear distortion of the features. Reverberation and noise can be reduced prior to feature extraction by means of signal-space speech enhancement or source separation techniques [START_REF] Loizou | Speech Enhancement: Theory and Practice[END_REF][START_REF]Blind speech separation[END_REF]. Feature-space nonlinear transforms such as vector Taylor series [START_REF] Moreno | A vector Taylor series approach for environment-independent speech recognition[END_REF], stereo-based piecewise linear compensation for environments (SPLICE) [START_REF] Deng | Large vocabulary speech recognition under adverse acoustic environments[END_REF] and featurespace minimum phone error (fMPE) [START_REF] Povey | fMPE: Discriminatively trained features for speech recognition[END_REF] have also showed to be effective [START_REF] Tachioka | Discriminative methods for noise robust speech recognition: A CHiME Challenge benchmark[END_REF].

As for the transformation of the acoustic models, maximum a posteriori (MAP) [START_REF] Gauvain | Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains[END_REF] and maximum likelihood linear regression (MLLR) [START_REF] Gales | Maximum likelihood linear transformations for HMM-based speech recognition[END_REF][START_REF] Leggetter | Maximum likelihood linear regression for speaker adaptation of continuous density hidden Markov models[END_REF] have been widely used to adapt the mean and/or the covariance of Gaussian mixture model (GMM) observation densities to the environment. Multicondition training, i.e., directly training GMMs on reverberant and noisy data, can work even better when sufficient training data are available. The best results are often achieved by hybrid approaches applying model compensation after feature compensation on the training and the test data [START_REF] Deng | Large vocabulary speech recognition under adverse acoustic environments[END_REF][START_REF] Astudillo | Uncertainty propagation[END_REF][START_REF] Tran | Extension of uncertainty propagation to dynamic MFCCs for noise-robust ASR[END_REF].

A common trait of the above techniques is that they operate on the features or on the GMM parameters themselves. By contrast, a number of normalization techniques have been defined in the field of speaker verification that operate on the set of acoustic scores, i.e., on the likelihoods of the acoustic models given the feature vectors [START_REF] Bimbot | A tutorial on text-independent speaker verification[END_REF]. These techniques are fundamentally different from the above in that the normalized scores are not restricted to be proper likelihoods anymore, i.e., they may each integrate to a different value other than 1. This extra flexibility increases the discriminativity of the decision thresholds.

In this paper, we provide a theoretical motivation for likelihood normalization due to the so-called "hubness" phenomenon [START_REF] Radovanović | Hubs in space: Popular nearest neighbors in high-dimensional data[END_REF] and we evaluate the benefit of several normalization techniques on ASR accuracy. Compared to speaker verification, this raises the challenge of balancing the normalized GMM scores and the HMM state transition scores. The resulting gain in noise robustness is evaluated on Track 1 of the 2nd CHiME Speech Separation and Recognition Challenge [START_REF] Vincent | The second 'CHiME' speech separation and recognition challenge: An overview of challenge systems and outcomes[END_REF]. The paper is organized as follows. We provide more background information about hubness and speaker verification in Section 2. We generalize existing score normalization techniques and hubness measures to the context of ASR in Section 3. We report experimental results in Section 4 and we conclude in Section 5.

Motivation

Hubness has been described and explored as a fundamental issue for machine learning in high dimensional spaces [START_REF] Radovanović | Hubs in space: Popular nearest neighbors in high-dimensional data[END_REF]. Most machine learning problems involve computing the "distance"1 between points in feature and/or model spaces. Hubness is the phenomenon by which certain points called "hubs" have a small distance to an exceptionally large number of points while certain points called "anti-hubs" are far from all other points. It is related to the concentration of distances [START_REF] Franc ¸ois | The concentration of fractional distances[END_REF], which impairs the contrast of distances in high dimensional spaces. As dimensionality increases, pairwise distances become almost identical to each other thus making it difficult to distinguish between the farthest and the closest point. This phenomenon has been mathematically studied for Euclidean spaces and other l p norms [START_REF] Franc ¸ois | The concentration of fractional distances[END_REF][START_REF] Aggarwal | On the surprising behavior of distance metrics in high dimensional space[END_REF] and empirically observed for many other forms of "distances" including negative log-likelihoods between feature and model spaces [START_REF] Schnitzer | The relation of hubs to the Doddington zoo in speaker verification[END_REF].

Proofs concerning concentration of distances have been formulated for dimensionality approaching infinity. However, the dimension does not need to be very large for hubness to occur. In the finite case, some points are expected to be closer to the center of the space and at the same time closer, on average, to all other points [START_REF] Radovanović | Hubs in space: Popular nearest neighbors in high-dimensional data[END_REF]. Such points closer to the center have a high probability of being hubs, i.e., of appearing in nearest neighbor lists of many other points. Points which are further away from the center have a high probability of being anti-hubs, i.e., points that never appear in any nearest neighbor list. Hubness has been reported for dimensions as low as on the order of 10 in practice [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF].

This phenomenon is exacerbated by distortions of the features and/or the models, which further reduce the contrast of distances. Nevertheless, it is essential to understand that it is a separate issue and that it may still occur beyond a certain dimension even after feature and model compensation.

This behavior has a negative impact on many machine learning tasks including classification [START_REF] Radovanović | Hubs in space: Popular nearest neighbors in high-dimensional data[END_REF], nearest neighbor based recommendation [START_REF] Flexer | A MIREX meta-analysis of hubness in audio music similarity[END_REF], outlier detection [START_REF] Radovanović | Hubs in space: Popular nearest neighbors in high-dimensional data[END_REF][START_REF] Flexer | Using mutual proximity for novelty detection in audio music similarity[END_REF] and clustering [START_REF] Tomašev | The role of hubness in clustering high-dimensional data[END_REF]. Closer to ASR, it has been shown that the "Doddington zoo" effect [START_REF] Doddington | Sheep, goats, lambs and wolves: A statistical analysis of speaker performance in the NIST 1998 speaker recognition evaluation[END_REF] in speaker verification is connected to the hubness phenomenon [START_REF] Schnitzer | The relation of hubs to the Doddington zoo in speaker verification[END_REF]. In this context, audio samples from "wolves" easily impersonate other speakers (are close to many speaker models), while persons which are difficult to recognize are referred to as "goats" (because they appear far from all other speaker models). "Wolves" and "goats" are therefore essentially hubs and anti-hubs.

A general solution to reduce hubness lies in the normalization of the distances [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF]. Several normalization techniques have been proposed in the field of speaker verification that aim to equalize the mean and the variance of the acoustic loglikelihood scores (see [START_REF] Bimbot | A tutorial on text-independent speaker verification[END_REF] for a review). The mean is normalized in such a way that the decision threshold between target and impostor speakers is always fixed to the same score while the variance is normalized to unity. The two fundamental operations are zero normalization (Z-Norm) [START_REF] Li | Normalizations and selection of speech segments for speaker recognition scoring[END_REF][START_REF] Reynolds | Speaker verification using adapted gaussian mixture models[END_REF], which reduces the score variability across the target models, and test normalization (T-norm) [START_REF] Auckenthaler | Score normalization for text-independent speaker verification systems[END_REF], which reduces the score variability across the test utterances. Combinations of these two operations have also been proposed, including test-dependent zero-score normalization (TZ-norm) and zero-dependent test-score normalization (ZT-norm) [START_REF] Vogt | Modeling session variability in text-independent speaker verification[END_REF][START_REF] Zheng | A comparative study of feature and score normalization for speaker verification[END_REF], which consist of applying them one after the other, and symmetric normalization (S-norm) [START_REF] Shum | Unsupervised speaker adaptation based on the cosine similarity for textindependent speaker verification[END_REF], which consists of summing the two normalized scores together. These normalization techniques as well as the ones developed in the machine learning community [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF] have been shown to reduce hubness and to improve speaker verification accuracy [START_REF] Schnitzer | The relation of hubs to the Doddington zoo in speaker verification[END_REF].

Likelihood normalization

We propose to generalize to ASR the score normalization techniques introduced in speaker verification. While speaker verification outputs a single score per utterance, ASR outputs a sequence of words, each of which is a sequence of acoustic units, e.g., phones. Each unit is modeled by a context-dependent hidden Markov model (HMM) with GMM observation densities. This raises the challenge of balancing the normalized GMM scores and the HMM state transition scores.

Formulation of ASR

We formulate ASR as the following weighted maximum a posteriori (MAP) decoding problem:

arg max w,s t Q(xt|st) + α log P (s|w) + αβ log P (w) (1)
with xt the observed feature vector at time t, s the sequence of HMM states (st), and w the word sequence. We call Q(xt|st) the observation scores and log P (s|w) the state transition score and log P (w) is the language score. We introduce the weight α to balance the observation scores and the other scores, while β is the language model weight as classically used in ASR [START_REF] Bahl | Languagemodel/acoustic channel balance mechanism[END_REF]. Conventional decoding is achieved by setting α = 1 and Q(xt|st) = log P (xt|st) where P (xt|st) is the GMM density associated with state st.

Normalizing the observation scores

As we shall see, the features and the acoustic models used for robust ASR exhibit a certain amount of hubness. This translates into two separate issues. Firstly, certain HMM states have systematically high (resp. low) observation scores even when they do not (resp. do) correspond to the true states behind the feature vectors, which is a major problem for ASR. The balance between the observation scores for different states can be restored via the Z-norm

Q Z (xt|st = i) = log P (xt|st = i) -µi σi (2)
where µi and σi denote the mean and the standard deviation of log P (xt|st = i) over "impostor" feature vectors xt, respectively. These quantities are estimated on the full development set and we define impostors in this context as all feature vectors whose corresponding state (according to forced alignment with the true word sequence) is not i. This normalization equalizes the decision threshold for all states. Secondly, certain feature vectors result in more (resp. less) contrasted observation scores for all states. Although this is less of a problem than above, this may still affect the estimated word sequence to some extent by giving more (resp. less) importance to the observation scores in the MAP decoding rule [START_REF] Baker | Research developments and directions in speech recognition and understanding, part 1[END_REF]. The balance between the observation scores and the other scores may be restored by the T-norm

Q T (xt|st = i) = log P (xt|st = i) -µit σit (3)
where µit and σit denote the mean and the standard deviation of log P (xt|st = i) over "impostor" states i, respectively. These quantities are computed on each time frame in the test data and we define impostors in this context as all states except i, that is I -1 states where I is the total number of states of all HMMs. Finally, both normalization techniques may be combined into the S-norm:

Q S (xt|st = i) = Q Z (xt|st = i) + Q T (xt|st = i). (4)
The normalized observation scores are used in place of the original scores Q(xt|st) and MAP decoding is achieved as in [START_REF] Baker | Research developments and directions in speech recognition and understanding, part 1[END_REF].

We tried several variants of the above normalization techniques, such as computing the T-norm over all states instead of impostors only and computing the Z-norm over each test utterance or over all feature vectors in the development set instead of impostors only. We also tried the TZ-norm and the ZT-norm as alternatives to the S-norm. All these variants resulted in slightly lower ASR performance than the corresponding original norms above and they are not explored hereafter.

Hubness measures

In the following, we assess the impact of likelihood normalization not only on ASR accuracy but also on hubness. A measure was defined in [START_REF] Radovanović | Hubs in space: Popular nearest neighbors in high-dimensional data[END_REF] to quantify the strength of the hubness phenomenon in a given space. Since ASR involves two different spaces for features and models, we adapt this definition into two complementary measures drawn from the scores Q(xt|st = i) of all feature vectors and all states. We fix k = 5 as in [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF].

For each feature vector xt, we first determine the k most likely states. For each state i, we then define the k-occurrence Mi as the number of feature vectors for which it is among the k most likely. Model-space hubness Smodel is computed as the skewness of the distribution of Mi:

Smodel = E[(Mi -µM ) 3 ] σ 3 M (5)
with µM its mean and σM its standard deviation. Values close to zero indicate low hubness, while large (positive or negative) values indicate high hubness.

Similarly, we find the k most likely feature vectors for each state i and we count the k-occurrence Nt as the number of states for which xt occurs among the k most likely feature vectors. Feature-space hubness Sfeature is obtained as:

Sfeature = E[(Nt -µN ) 3 ] σ 3 N . (6)

Experimental evaluation

We assess the impact of likelihood normalization on noise robustness. Evaluation is conducted on Track 1 of the 2nd CHiME Speech Separation and Recognition Challenge [START_REF] Vincent | The second 'CHiME' speech separation and recognition challenge: An overview of challenge systems and outcomes[END_REF].

Data and task

The Challenge aims to recognize distant speech in a real home with reverberation and multisource background noise. The target utterances are 6-word commands of the form <command> <color> <preposition> <letter> <digit> <adverb> read by 34 speakers at 6 different signal-to-noise ratios (SNRs) from -6 to +9 dB. The speaker is assumed to be known and the task is to report the letter and digit keywords, which are the most easily confusable words. Accuracy is measured as the percentage of correctly recognized keywords.

Feature and model compensation

The proposed normalization techniques are evaluated alone and in combination with feature and model compensation. To evaluate the effect on feature compensation, we consider both the original noisy data and enhanced data. Speech enhancement is applied to the development and test datasets and to the noisy training set using the Flexible Audio Source Separation Toolbox (FASST) [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF] with the same settings as in [START_REF] Tran | Extension of uncertainty propagation to dynamic MFCCs for noise-robust ASR[END_REF]. Uncertainty propagation is employed to robustly extract feature vectors from the separated signals as detailed in [START_REF] Tran | Extension of uncertainty propagation to dynamic MFCCs for noise-robust ASR[END_REF]. Three sets of acoustic models are considered: clean models trained on the clean training set, reverberated models (abbreviated "reverb") trained on the reverberated training set, and multicondition models ("multi") trained on the original/enhanced noisy training set (all SNRs included). Multicondition training was indeed found to perform better than model adaptation techniques for this Track, due to the large amount of training data [START_REF] Vincent | The second 'CHiME' speech separation and recognition challenge: An overview of challenge systems and outcomes[END_REF]. All models are speaker-dependent and SNR-independent.

Algorithm settings

The normalization factors for the Z-norm (and consequently for the S-norm) are assumed to be speaker-dependent. In order to evaluate the impact of data mismatch on the estimation of these factors, they are trained either in an SNR-dependent fashion on the development data for the same speaker and SNR as the test utterance or in an SNR-independent fashion on all development data of the same speaker.

Decoding is performed using the baseline HTK setup provided by the Challenge organizers [START_REF] Vincent | The second 'CHiME' speech separation and recognition challenge: An overview of challenge systems and outcomes[END_REF]. The features are 39dimensional vectors consisting of 12 Mel-frequency cepstral coefficients (MFCCs), log-energy, delta and acceleration coefficients. The acoustic models are word-level left-to-right HMMs with 2 states per phoneme. Each state is modeled by a GMM with 7 Gaussians with diagonal covariance.

Due to the constrained syntax, the language model weight has no impact and it is fixed to β = 1. The weight α is assumed to be SNR-independent and it is optimized on development data in the range of [0,50] with a step of 1 for the original scores and in the range of [0,4] with a step of 0.2 for the normalized likelihoods 2 . The optimal weight is found to vary between 0 and 11 in the former case and between 0 and 1.6 in the latter case depending on the data (noisy or enhanced), on the model, and on the normalization technique. The weight found on development data is subsequently applied to the test data.

ASR results

The average ASR performance achieved for different data, models, and normalization techniques is shown in Table 1, with the best (statistically significant) results in each column highlighted in bold. The baseline test set accuracy ranges from 17.64% without compensation (noisy data, clean model) to 85.85% with feature and model compensation (enhanced data, multicondition model).

SNR-dependent and SNR-independent normalization are seen to perform very similarly. We hence focus on SNRindependent results hereafter.

Applied alone, the change of the value of α and the T-norm have no significant effect on accuracy. The Z-norm improves performance on all data in combination with clean or reverberated models, but not with multicondition models.

The S-norm is the only norm that improves results on all data and for all models. Compared to the baseline, it achieves a test set accuracy of 52.74% without compensation and 87.25% with feature and model compensation, that is a relative error rate reduction of 43% and 10%, respectively. This is in agreement with previous work in the field of machine learning which has shown that it is decisive to normalize distances with respect to both arguments [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF].

The latter result is analyzed as a function of the SNR in Table 2, with the best (statistically significant) results in each column highlighted in bold. Likelihood normalization has no significant effect at high SNRs but it increases performance up to 19% relative at low SNRs, that is twice as much as on average over all SNRs.

Analysis of hubness

The measured hubness is reported in Table 3. The original values are on the order of 2 to 4, which is moderate to large [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF]. For a given dataset and model, the lower the model hubness The smallest model hubness Smodel = 1.39 is achieved when jointly using these three techniques. This is confirmed in Figure 1 (horizontal axis) which depicts the measured hubness before and after normalization for each utterance in the enhanced test set. Feature hubness, on the other hand, appears to be unrelated to ASR performance. This confirms that biases in the observation scores are more crucial to address than imbalance with the other scores.

Conclusion

We explored the use of likelihood normalization techniques for speaker verification in the context of robust ASR. We adapted these techniques to the observation scores in ASR and we balanced the other terms in the MAP decoding rule via a weight α. We showed that joint normalization of the scores across both the models and the features significantly improves performance even after feature and model compensation. ASR performance appears to be well correlated with model hubness, with lower values of model hubness resulting in greater ASR accuracy. Future work will focus on computing the S-norm from a subset of states for greater computational efficiency [START_REF] Schnitzer | Local and global scaling reduce hubs in space[END_REF], on evaluating it on larger-vocabulary tasks, and on finding improved normalization techniques to further reduce model hubness.

Acknowledgment

This work was supported by FWF grant P24095 and by the LangTERRA project (FP7-REGPOT-2011-1). We thank D. T. Tran for the enhanced features and D. Jouvet for his advice.

Figure 1 :

 1 Figure 1: Model and feature hubness measured on the enhanced test set with multicondition acoustic models. Each dot corresponds to one utterance.

Table 1 :

 1 Keyword accuracy (in %) for all data and models averaged over all SNRs. .17 84.[START_REF] Vogt | Modeling session variability in text-independent speaker verification[END_REF] 89.58 91.12 93.33 75.75 77.75 85.33 90.50 92.50 93.08 S-norm (SNR-ind.) 78.33 81.25 86.33 89.25 91.50 92.92 79.58 82.08 87.17 90.42 91.67 92.58

	Dataset		Noisy development set	Noisy test set	Enhanced development set	Enhanced test set
	Acoustic model	Clean Reverb Multi Clean Reverb Multi Clean Reverb	Multi	Clean Reverb Multi
	No norm	α = 1 α opt.	17.72 57.42 69.19 17.64 58.53 69.47 26.10 77.15 18.53 57.97 69.28 18.72 58.33 69.42 26.51 77.51	85.17 85.24	25.93 79.21 85.85 27.03 79.14 85.82
	Z-norm	SNR-dep. 58.92 70.15 66.76 57.67 68.76 65.94 66.49 78.38 SNR-ind. 58.06 69.63 66.22 57.67 68.57 66.07 66.31 78.38	81.25 81.00	66.44 78.11 81.26 66.31 78.25 81.46
	T-norm		18.54 56.86 69.01 18.74 57.74 69.24 26.15 76.68	84.47	26.32 78.68 85.26
	S-norm	SNR-dep. 54.39 71.39 73.72 53.04 71.14 73.46 64.61 83.08 SNR-ind. 53.67 71.35 73.64 52.74 71.13 73.28 64.75 83.18	86.65 86.60	64.35 83.78 87.26 64.71 83.68 87.25
	Multicondition	Enhanced development set	Enhanced test set
	acoustic model	-6 dB -3 dB 0 dB 3 dB 6 dB 9 dB -6 dB -3 dB 0 dB 3 dB 6 dB 9 dB
	No norm	73.92 79

Table 2 :

 2 Keyword accuracy (in %) for the enhanced data and the multicondition acoustic models as a function of the SNR.

	Measure		Model hubness Smodel				Feature hubness Sfeature
	Dataset	Noisy test set		Enhanced test set	Noisy test set		Enhanced test set
	Acoustic model	Clean Reverb Multi Clean Reverb Multi Clean Reverb Multi Clean Reverb Multi
	No norm	4.31	2.69	1.67	3.95	2.06	1.53	2.03	2.65	4.00	1.93	2.27	2.67
	Z-norm (SNR-ind.)	1.67	1.79	1.85	1.59	1.67	1.68	2.03	2.65	4.00	1.93	2.27	2.67
	T-norm (SNR-ind.)	4.31	2.69	1.67	3.95	2.06	1.53	1.10	0.90	0.61	1.06	0.75	0.60
	S-norm (SNR-ind.)	1.81	1.67	1.53	1.73	1.49	1.39	1.54	1.22	1.81	1.46	1.05	1.02

Table 3 :

 3 Test set hubness for all data and models.

the better the ASR performance. Feature compensation, model compensation, and S-normalization all reduce model hubness.

This term refers here to a pairwise dissimilarity score, which does not necessarily satisfy the mathematical definition of a distance.

α = 0 means that the left-to-right state order and the word order are enforced, but state durations are not constrained anymore.