Stéphane Conversy
email: stephane.conversy@enac.fr

Christophe Hurter
email: christophe.hurter@aviation-civile.gouv.fr

Stéphane Chatty
email: chatty@enac.fr

A Descriptive Model of Visual Scanning

Keywords: H.5.2 User Interfaces -Evaluation/methodology, Screen design Design, Human Factors Visualization, Infovis, Design Rationale, Visual design

When designing a representation, a designer implicitly formulates a sequence of visual tasks required to understand and use the representation effectively. This paper aims to make the sequence of visual tasks explicit, in order to help designers eliciting their design choices. In particular, we present a set of concepts to systematically analyze what a user must theoretically do to decipher representation. The analysis consists of a decomposition of the activity of scanning into elementary visualization operations. We show how the analysis applies to various existing representations, and how expected benefits can be expressed in terms of elementary operations. The set of elementary operations form the basis of a shared, common language for representation designers. The decomposition highlights the challenges encountered by a user when deciphering a representation, and helps designers to exhibit possible flaws in their design, justify their choices, and compare designs.

INTRODUCTION

Designing representation is often considered to be a craft. The design activity requires multiple iterations that mix ad-hoc testing, discussions with users, controlled experiments, and personal preferences. These ways of designing are either costly (controlled experiment), error-prone (ad-hoc testing) or lead to non-optimal results ( personal preference). Though a number of theoretical works help to explain the strengths or weaknesses of representation [START_REF] Amar | A Knowledge Task-Based Framework for Design and Evaluation of Information Visualizations[END_REF][3][4] [START_REF] Bertin | Sémiologie Graphique -Les diagrammesles réseaux -les cartes[END_REF] [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF][26] [START_REF] Wilkinson | The Grammar of Graphics[END_REF], no systematic method exists that would help designers to assess their design in an a priori manner, i.e., before user experiments. As suggested in [START_REF] Munzner | A Nested Process Model for Visualization Design and Validation[END_REF], such a method would help not only for formative purposes, but also as a summative evaluation before actual user experiments.

When designing a representation, a designer implicitly formulates a way to understand and use the representation effectively. For example, reading a city map requires scanning it, finding noteworthy locations (metro stations, connections...), devising a path to go from one point to another, etc [START_REF] Ware | Visual Thinking for Design[END_REF]. For a user, except for very specialized graphics and narrow tasks, figuring out a representation is like interacting using the eyes only: a user has to figure out a solution to his task at hand by scanning the picture, seeking graphics, memorizing things, etc. The succession of these small visualization operations induces a cost that deserves to be evaluated before acceptance of a final design.

In this paper we suggest that most design decisions can be explained by the willingness of the designer to reduce the cost of deciphering the representation. However, there is no common core of concepts that allows designers to precisely express the rationale behind a design decision. This hinders the design process because it makes it hard for designers to explain to users and stakeholders why a representation is suitable for their tasks (justification), and how a new prototype is better than a previous one (comparison). Furthermore, they cannot justify their choices in a design rationale document, which makes the decisions susceptible to disappearance in future evolutions of the system. This paper presents a set of concepts and a method for analyzing how a user deciphers a representation. It relies on and extends previous works about visual scanning and design elicitation. The goal of the paper is not to show better designs for a particular problem. Rather, the goal of the paper is to present a method that exhibits the steps required to figure out a particular representation, and helps justify design choices and compare representations.

RELATED WORK

We based our work on previous studies that can be roughly divided into three groups. The first group concerns eye gaze, representation scanning, and models of visual perception; the second concerns visual task taxonomies; and the third concerns design formulation.

Eye gaze, scanning, visual perception

Eye tracking enables researchers to analyze what users look at when solving a problem. However, a large part of the literature is devoted to how to process tracking data in order to analyze it [START_REF] Crowe | Comparing interfaces based on what users watch and do[END_REF][23] [START_REF] Salvucci | Automated eyemovement protocol analysis[END_REF]. Furthermore, the state of the art in this field still experiments with very low-level designs and abstract graphics [START_REF] Atkins | An application of eyegaze tracking for designing radiologists' workstations: Insights for comparative visual search tasks[END_REF] [27], far from the richness of today's visualizations. A number of findings are interesting and may help the design of representations, but they are hard to generalize and use in a prescriptive way [START_REF] Rayner | Eye Movements in Reading and Information Processing: 20 Years of Research[END_REF].

The ACT-R model aims at providing tools that simulate human perception and reasoning [3][4]. However, the tool is not targeted towards designers, as its purpose is to model human behavior so as to anticipate real-world usage. It does not take into account some arrangements such as ordered or quantitative layout, nor does it support a description of how a representation is supposed to be used. ACT-R has tentatively been used to carry out autonomous navigation of graphical interface, together with the SegMan perception/action substrate [START_REF] St | A perception/action substrate for cognitive modeling in HCI[END_REF]. However the interfaces used as testbeds are targeted toward WIMP applications, which do not exhibit high-level properties available in rich visualization.

The semiology of graphics is a theory of abstract graphical representation such as maps or bar charts [START_REF] Bertin | Sémiologie Graphique -Les diagrammesles réseaux -les cartes[END_REF]. It describes and explains the perceptual phenomenon and properties underlying the act of reading abstract graphics. In his book, Bertin defines three levels of reading a representation: the elementary level, which enables the reader to "unpack" visual variables of a single mark, the middle level, which enables the reader to perceive a sizelimited pattern or regularity, and the global level, which enables the reader to grasp the representation as a whole, and see at a glance emergent visual information. Bertin ([7] p148) pointed out the problem of scanning in what he terms "figuration" (i.e., bad representation). He briefly depicts how the eye scans a graphic. During scanning, the eye jumps from one mark to the next, while experiencing perturbation by other marks. The eye then focuses on particular marks to gather visual information.

Visual task taxonomies

Casner designed BOZ, a tool that automatically generates an appropriate visualization for a particular task [START_REF] Casner | Task-analytic approach to the automated design of graphic presentations[END_REF]. BOZ takes as input a description of the task to support and relies on a set of inference rules to generate a visualization that maximizes the use of the human perceptual system. In the following, we use the set of perceptual operators embedded in BOZ, such as "search (an object with a given graphical property)", "lookup (a property given an object)", and "verify (given a property and an object, that this object has the property)".

Zhou and Feiner designed IMPROVISE, another automatic tool to design representations [START_REF] Accot | Beyond Fitts' law: models for trajectory-based HCI tasks[END_REF]. Zhou and Feiner have refined the visual analysis into multiple levels: visual intents, visual tasks, and visual techniques. Visual tasks include emphasize, reveal, correlate, etc. A visual task may accomplish a set of visual intents, such as search, verify, sum or differentiate. In turn, a visual intent can be accomplished by a set of visual tasks. A visual task implies a set of visual techniques, such as spatial proximity, visual structure (tables, networks), use of color, etc.

Design formulation

The GOMS Keystroke-Level Model (KLM) helps to compute the time needed to perform an interaction [START_REF] Card | The Keystroke-Level Model for user performance time with interactive systems[END_REF]. The Complexity of Interaction Sequences (CIS) model takes into account the context in which the interaction takes place [START_REF] Appert | Context Matters: Evaluating Interaction Techniques with the CIS Model[END_REF]. Both KLM and CIS are based on descriptive models of interaction, which decompose it into elementary operations. They are also predictive models, i.e., they can help compute a measurement of expected effectiveness and enable quantitative comparisons between interaction techniques. These tools have proved to be accurate and efficient when designing new interfaces [START_REF] Appert | Context Matters: Evaluating Interaction Techniques with the CIS Model[END_REF] [START_REF] Card | The Keystroke-Level Model for user performance time with interactive systems[END_REF].

Green identified cognitive dimensions of notation, which help designers share a common language when discussing design [START_REF] Green | Cognitive dimensions of notation[END_REF]. The dimensions help make explicit what a notation is supposed to improve, or fail to support. Cognitive dimensions are based on activities typical of the use of interactive systems such as incrementation or transcription. However, they are high-level descriptions and do not detail visualization tasks. Our work has the same means and goals (description and production of a shared language) as cognitive dimensions, but specialized to visualization.

IDEALIZED SCANNING OF REPRESENTATION

As previously stated, when designing a representation, a designer implicitly formulates a method required to understand and use the representation effectively. The work presented here is an analysis of this method that provides a way to make it explicit.

When trying to solve a problem using a representation, a user completes a visualization task by performing a set of visual and memory operations. A visualization task can be decomposed into a sequence of steps pertaining to the problem at hand (e.g., "find a bus line"). Each step requires that a sequence of elementary visualization operations be accomplished. Operations include entering the representation, memorizing information, seeking a subset of marks, unpacking a mark and verifying a predicate, seeking and navigating among a subset of marks, and entering and exiting from the representation. As we will see below, operations are facilitated by the use of (possibly) adequate visual cues, such as Bertin's selection with color, size or alignment [START_REF] Bertin | Sémiologie Graphique -Les diagrammesles réseaux -les cartes[END_REF].

In terms of the model proposed in [START_REF] Munzner | A Nested Process Model for Visualization Design and Validation[END_REF], we target the encoding/interaction technique design box.

In the following, we analyze idealized scanning of representations.. We use "idealized" in the sense that the user knows exactly what she is looking for, knows how to use the representation so as to step through with the minimum necessary steps, and uses only the available information in the representation otherwise stated. Thus, we do not take into account other phenomena such as learning, understanding, error, chance, or personal perceptual disabilities (like color blindness). This is similar to the approach taken with the KLM: when applying a decomposition, the designer analyzes an idealized interaction.

In fact, the model enables either comparing multiple scanning strategies for a given task and a given representation, or comparing multiple representations for a given task and the most efficient scanning. In the following, we focus on representation comparison, and we assume that we have found the most efficient scanning for each representation. The next section uses an example to illustrate how to perform an analysis of representation scanning. Based on this, we further detail the steps and operations required, and what factors affect users' efficiency at achieving them.

A FIRST GLIMPSE: A TABULAR BUS SCHEDULE REPRESENTATION

There is no such thing as an absolutely effective representation; to be effective, a representation must minimize the amount of work required to fulfill a task [START_REF] Casner | Task-analytic approach to the automated design of graphic presentations[END_REF]. In the following example, the problem to be solved by a user is to answer the following question: "I am at the IUT Rangueil station and it is 14:18. How long will I have to wait for the next bus to the Université Paul Sabatier station?" The user knows that two bus lines go to the destination (#68 and #108). Figure 1 is an excerpt of a typical representation of a bus schedule. The display is a physical panel at the station booth, on which lay paper sheets, each with a table for one bus line that displays the time of departure from each station.

The drawings overlaid on the representation show the idealized visualization tasks a user must perform when trying to answer the question. A circle depicts an eye reading, an arrow an eye movement. Memory operations are depicted with a blue "M". The step numbers are in the form x.y.z, which means that step y is the y th sub-step of step x, and step z, the z th sub-step of step y. A check mark depicts the last operation of a substep, together with a green circle. Figure 1 also shows two different scanning strategies to answer two instances of an intermediate question ("when is the next bus for line 68 (resp. 108)?").

Figure 1. A bus schedule representation with the required steps to find particular information

Step 0: the user should memorize the two compatible bus line numbers and the current time.

Step 1.x: the user should find an appropriate bus line. The number of the line is represented in large, boldface text at the top-right corner of each paper sheet.

Step 1.2.1: the user should find his current location ( "IUT Rangueil") among the list of stations. The list is a subset of marks of kind "text", aligned vertically, with no marks in-between. The stations are ordered according to their location along the bus line.

Step 1.2.1.x: the user must find the next departure time. He has to navigate through a row of texts that displays hour and minute for each bus departure. As the X dimension is multiplexed (or "folded on") Y, the user may not find a compatible time in the first row examined: in this case he has to start Step 1.2 over by moving to the next row (Step 1.2.2). Finally, the user finds the next departure when he identifies the first departure that is later than the current time.

Step 1.3.3.2: the user finds that this row does not contain relevant information, so he performs a back step to the previous row. This requires memorization of a previous mark position.

Step 1.2.2.x, 1.3.2.x, green circle: the user finds a compatible bus in each line and thus has to perform mental computation (a difference between two times) to find the duration before the next bus, and memorize it to compare with previous or following findings.

ELEMENTARY OPERATIONS

This section details the various elementary operations required to implement the steps. In defining the operations, we based our analysis on existing literature when available, supplemented by interviews with visualization designers. For each operation, we detail it, and give elements that aid or hinder operation achievement. We also compare our operations to the BOZ and IMPROVISE taxonomies, and explain the differences, mainly in terms of elements that may aid or hinder the operation.

Memorizing information

To solve problems, users have to know what information to seek.

They have to memorize this information, so as to compare it to the information that arises from the representation. As we will see in the examples, different representations require different numbers of memory "cells". For example, in the tabular bus scheduling view, users need three cells of information at the beginning (current time, 68 and 108), two cells for intermediary results, and one cell for a previous location. Memory requirements are often overlooked when comparing visualizations: the more cells required, the harder it becomes to solve a problem. Memory fades with time, so for long scanning tasks users may have forgotten important information before the end of the scanning. Forgotten information that is available on the representation can be compensated for by additional seeking operations, or by adding the equivalent of a selectable visual property (e.g., a hand-written mark, or a pointing finger).

Entering and exiting representation

A representation is rarely used in isolation. Users are surrounded by different representation from various systems. For example, Air Traffic controllers employ radar views, various lists of flights, paper strips, etc. When they solve a problem, users may have to switch representations. This may require translating the input of a representation into the visual language of another representation and translating the information found back into the problem.

In the bus schedule example, users may have to translate the representation of a time seen on a watch into numbers in the form hh:mm so as to comply with the ordered-by-time menu-like vertical representation ( entering). They also have to get the correct bus line somewhere (i.e. a map representing the public transportation network), and translate the information (a textual number or a color) into the visual language of the representation (entering). The information to find is the waiting time for the next bus. The tabular representation does not give this information directly, and thus requires a mental computation (exiting). In the city map example, translating map direction to real-world direction and recognizing street layout is easier if the map is oriented to the terrain (i.e., north of map matching the actual north direction). Taking into account this step is important when a switch of representation does not require translation, since this makes the second representation easier to understand.

Seeking a subset of marks

When users search for bus line information, they have to search for a subset of the marks in the representation. In order to find the correct line, the user has to navigate from line number to line number.

Perceiving a subset is made easier with selective (in the sense of the semiology of graphics [START_REF] Bertin | Sémiologie Graphique -Les diagrammesles réseaux -les cartes[END_REF]) visual variables: marks can be extracted from the soup of all marks at one glance, which narrows down the number of marks to consider. For example, the number of the bus line is represented in text, with a large font size and boldface, placed at the top-right corner of the sheet. The size and position of bus line number make the marks selectable. Furthermore, when elements in a subset are close enough together, no other in-between element perturbs the navigation from mark to mark. The list is even easier to navigate in, since the marks are aligned horizontally and vertically (or in other words, marks differ by only one dimension (X or Y)).

Conversely, perceiving a subset can be harder in presence of similar marks that do not belong to the considered subset. In the tabular schedule example, all time information has similar visual properties except for the start time of each bus, which is set in bold. If the start time were set in regular, it would be harder to find at a glance. Seeking a subset corresponds to the searchobject-* perceptual operator in BOZ [START_REF] Casner | Task-analytic approach to the automated design of graphic presentations[END_REF].

Unpacking a mark and verifying a predicate

When the user sees a candidate mark, she has to assess it against a predicate. In the tabular bus schedule example, the user has to find a line number that matches one of the correct buses. Assessing a predicate may require extracting (or unpacking [START_REF] Accot | Beyond Fitts' law: models for trajectory-based HCI tasks[END_REF]) visual dimensions from a mark. This is what Bertin calls "elementary reading" [START_REF] Bertin | Sémiologie Graphique -Les diagrammesles réseaux -les cartes[END_REF]. This operation also corresponds to the lookup-* and computation perceptual operator class in BOZ [START_REF] Casner | Task-analytic approach to the automated design of graphic presentations[END_REF]. However, assessing a predicate may also require cognitive comparison to memorized information (is the bus number I'm looking at one of the memorized ones?), or visual comparison with another mark (example in the following). In BOZ the difficulty of accomplishing the operation depends on the visual variable used, but not on other considerations such as memory or visual comparison.

Seeking and navigating among a subset of marks

Within an identified subset, a user may search for a particular mark. If marks are displayed in random positions, finding a mark requires a linear, one-by-one scanning of marks, with a predicate verification for each. The time needed is O(n). If marks are ordered (as in the ordered-by-time schedule), a user can benefit from this regularity to speed up navigation, for example by using a binary search approach, which leads to a time needed of O(log(n)). If marks are displayed at quantitative positions, we can hope to achieve O(1). However, this may require secondary marks such as a scale ticks and legends. In this case, scanning is split into two phases: navigating into the scale first, then into primary marks.

Navigating inside a list of texts is equivalent to reading a menu, for which performance may be predicted quite accurately [START_REF] Accot | Beyond Fitts' law: models for trajectory-based HCI tasks[END_REF]. However, some graphical elements may hinder navigation. For example, navigating in a row surrounded by other rows, as in a table, is difficult. This is the equivalent of a visual steering task [START_REF] Accot | Beyond Fitts' law: models for trajectory-based HCI tasks[END_REF]: it requires that the eye be able to stay in a tunnel. Some representations are supposed to aid this (e.g., think of an Excel sheet where every other row is colored). Performance depends on the width and the length of the tunnel. Navigating inside a vertical list of text is easier than navigating in a horizontal one, since a horizontal row is as narrow as the height of a glyph. Furthermore, in particular cases, navigating may require a step back to a previous mark, which in turn requires memorizing a previous location (see step 1.3.2.x in Figure 1).

No BOZ perceptual operator corresponds to this operation. IMPROVISE generates scales for quantitative data, but no mechanism facilitates ordered data. None of the taxonomies in BOZ and IMPROVISE handle navigation or take visual steering into consideration.

FORMULATING DESIGN RATIONALE

We argue that a designer implicitly designs a required sequence of elementary operations when inventing a new representation. We also suggest that most explanations given by designers can be expressed in terms of elementary operations, and in particular in how a particular design improves operation performance. In the following, we present various designs for bus schedules and ATC paper strips. We explain the expected gains of each design using the concepts presented above. We balance the claims by our own analysis, and possible loss of performance due to a lack of support for overlooked operations.

Bus schedule

Ordered-by-time linear representation

Figure 2. An ordered-by-time bus schedule

One bus company proposes the representation in Figure 2 on its web site. This displays an ordered list of time of departure at the chosen station along the X dimension, with the corresponding bus line indicated by a cell containing a background color and white text. The required steps are:

Step 0: memorize the current time and appropriate bus lines (entering and memorizing), possibly translating time from an 'analog' watch to a text in the form hh:mm (entering).

Step 1: find the ordered list of time (seeking), and the first time later than the current time (navigating and predicate).

Step 2: find the next appropriate bus (predicate, or seeking a mark if using bus color).

Step 3: find the associated time (seeking a mark).

Step 4: compute the waiting time before the departure (exiting).

Compared to the tabular representation, the following operations may be aided…:

seeking and navigating among a subset of marks: times of departure are displayed in a ordered manner which may ease navigation.

seeking a subset of marks: the user can easily select elements to the right of the element found in step 2 (later times, using selection based on location).

memorizing: there are less information to memorize (2 vs 6 chunks).

…and there are no apparent drawback.

Spiral representation

SpiraClock is an interactive tool that displays nearby events inside a spiral (instead of a circle like with a regular clock) [START_REF] Dragicevic | SpiraClock: a continuous and non-intrusive display for upcoming events[END_REF]. Time of event is mapped to angle, and thanks to the multiplexing of the angle over the radius, other information emerge (periodicity, closeness through radius) (Figure 3). The clock also displays the current time, and adapts the event occurrences accordingly. The occurrence of an event is actually depicted by the "most recent" limit of a "slice". Duration is a relative angle, or a curvilinear distance, which is quantitative representation, more precise on the exterior of the spiral (i.e. for close events) than in the interior.

There is also a scale depicted with black squares along the circle. SpiraClock's designers argued that adding textual information about hours would be useless, since the design uses a well-known reference (a watch) and since the visualization is focused on current time. If we represent the bus timetable on SpiraClock (as in Figure 3), the steps required to answer the question are:

Step 0: memorize two bus colors (entering and memorizing)

Step 1: find the end of minute hand (seeking a mark)

Step 2: find the next matching colored mark (i.e. corresponding to line 68 or 108) (seeking a mark)

Step 3: evaluate the distance between the matching mark and the minute hand, and estimate the waiting time (unpack and exiting)

Compared to the ordered linear representation, the following operations may be aided…:

entering: the current time is directly visible thanks to the hands.

navigating: since the time is visible, navigating to the next correct bus is shorter exiting: with SpiraClock, a rough idea of the waiting time is directly visible (no computation needed), since it is proportional to distance and the design uses a culturally-known scale.

… and there are no apparent drawback.

Quantitative linear representation

Figure 4 shows a representation based on a linear quantitative scale. Each colored rectangle represents the departure of a bus at the chosen station. The horizontal position of a rectangle corresponds to the time of departure and is multiplexed along the vertical dimension. To aid navigation, a linear scale is provided, with textual information about hours, and small ticks to mark quarters between hours.

Step 0: memorize two bus colors (memorizing), possibly translate time from a watch to a text for hour, and then to a position among ticks for minutes (entering)

Step 1: find the hour (seeking a mark).

Step 2: find the correct quarter-hour among the ticks (seeking a mark).

Step 3: find the next compatible bus (i.e., corresponding to line 68 or 108) (seeking a mark).

Step 4: evaluate the distance between the matching mark and the minute hand, and estimate the waiting time (no computation is needed) (unpack and exiting).

Compared to SpiraClock, the following operation may be aided…:

navigating: thanks to the linear layout and the supplemental space between rows, the steering task is easier to perform (especially compared the narrow tunnel configuration of Figure 3, left).

… at the expense of the entering operation (there is no current time visible, since the representation is not dynamic).

ATC strips

The activity of Air Traffic Controllers (ATCos) includes maintaining a safe distance between aircraft by giving clearances to pilots-heading, speed, and level (altitude) orders. ATCos must detect potential conflicts in advance. To do this they use various tools, including a radar view and flight strips [START_REF] Green | Cognitive dimensions of notation[END_REF]. A flight strip is a paper strip that shows the route followed by an airplane when flying in a sector (Figure 5).

Figure 5. An ATC paper strip

The route is presented as an ordered sequence of cells, each cell corresponding to a beacon, with its name, and its time of passage. Controllers lay paper strips on a strip board, usually by organizing them in columns. The layout of strips on a board, though physical, can be considered as a representation. Some planned systems aim to replace paper strips with entirely digital systems, so as to capture clearances in the database (currently the system is not aware of clearances from the controllers to the pilots). These systems partly replicate the existing representation, and we show in subsequent sections how they compare with respect to representation scanning.

Regular strip board

One of the activities of a controller is to integrate the arrival of a flight into the current traffic. To do this safely, the controller must check that for each beacon crossed by the new flight, no other flights cross that beacon at the same time at the same level. Figure 6 shows the required idealized scanning, with typical paper strips organized in a column. The steps are:

Step 1: find the flight level and memorize it (seeking and memorizing).

Step 2.1: find the beacon text on the arrival strip (seeking), and for each beacon (horizontal text list scanning, with no perturbation), do the following steps (navigating).

Step 2.2: memorize the beacon text, find the minute information (hour is usually not important) ( seeking), and memorize it (memorizing).

Step 2.3: for each other strip (vertical rectangular shape list scanning), do the following steps (seeking and navigating).

Step 2.4.1: find the beacon text, and for each beacon (horizontal text list scanning, with no perturbation), do the following steps (seeking and navigating).

Step 2.4.2: compare the beacon text to the one memorized in step 2.2 (predicate).

Step 2.4.3.1: if it is the same, find the minute text, and compare it to the one memorized in step 1.2 (+-5 min) (predicate).

Step 2.4.3.2: if the number is about the same, find flight level, check it and compare it with the memorized level (predicate).

Step 2.5.1.2: if it is the same, do something to avoid a conflict (predicate and exiting).

Strips in colored holders

The strip look and layout in the previous section is specific to the En-Route Control Centre at Bordeaux, France. In other En-Route Control Centers, people use rigid, colored holders for each paper strip. The look of strips is different, since the colored frame of the holder surrounds each strip. Figure 7 shows an idealized scanning with colored strip holders: here red is for north-south flights (odd flight level), while green is for south-north flights (even flight level). Because of the different level assignments, controllers can be sure that red and green flights will never enter into conflict.

Red holders can quickly be extracted from green ones (selection based on color). Hence, colored strip holders enable controllers to narrow the set of flights to compare with a new one, and reduce the number of required steps accordingly (step 2.x, with x>=3, seeking and navigating). Holder colors can also ease predicate verification: holder color of the arriving strip can be matched easily to holder color of other strips, without requiring the controller to determine if the strip is a north-south or a south-north flight.

Pen-based digital stripping system

Figure 8 shows a digital, pen-based system that adds an interaction allowing the controller to press a beacon cell, so as to highlight in red the time of passage over that beacon on other strips (the system cannot automatically detect conflict because the data on the strips is not always current). This facilitates seeking and navigating in step 2.x, as it reduces the subset of marks to consider when comparing times, and memorizing (1 vs 3 cells).

Dynastrip

Dynastrip displays beacons in a quantitative way, mapping time to the horizontal dimension (Figure 9) [START_REF] Grau | Dynastrip": a time-line approach for improving the air traffic picture of ATCOS[END_REF]. All time scales are aligned across strips. The main goal of Dynastrip is to display position relative to planned route in the strip, which adds information. Dynastrip designers also hoped that this representation would assist controllers to identify conflicts: if beacons with the same text are vertically aligned, it means that multiple flights pass over the same beacon at the same time.

Figure 9. Dynastrip, overlaid with the steering tunnel

Step 1: find the flight level (seeking), and memorize it (memorizing).

Step 2.1: find the beacon texts on the arrival strip, and for each beacon (horizontal text list scanning (seeking and navigating), do the following steps.

Step 2.2: memorize the beacon (memorizing), steer visually through a tunnel (+-5min) (symbolized in gray on Figure 9 but not shown on the actual interface) (seeking and navigating), and compare each beacon found with the memorized one (predicate).

Step 2.2.1: find the flight level, check it and compare it with the memorized level (predicate).

Compared to the regular strip boards, this design may aid…:

Seeking and navigating: thanks to a steering task, beacon search is facilitated.

Verifying a predicate: the time limit is directly visible.

… at the expense of a supplemental interaction to reach beacons not yet visible on the time scale.

VALIDITY AND LIMITATIONS

Idealized scanning is only theoretical. We have not verified experimentally the degree to which actual scanning corresponds to our model, which raises questions about the validity of the work presented here. However, we suggest that designers implicitly rely on theoretical scanning, though their expectations do not always stand against reality [START_REF] Grau | Dynastrip": a time-line approach for improving the air traffic picture of ATCOS[END_REF]. A deeper understanding of the phenomena is thus necessary, to make explicit design choices and expected benefits, and to get a reasonable confidence in the design.

Bertin's semiology of graphics and Furnas' Effective View Navigation [START_REF] Furnas | Effective view navigation[END_REF] have not been fully validated experimentally. Nevertheless, their concepts permeate a large number of visualization designs. These approaches allow identification of relevant concepts and dimensions when analyzing or designing new visualizations. We think that the elementary operations we identify in this paper will serve as a similar framework for representation rationale. In the same way, we have not verified experimentally whether navigation in an ordered set is easier than in a random set, and whether navigation in a quantitative set is easier than in an ordered set. Again, a number of visualizations rely on these assumptions: making the assumptions explicit helps designers think about the effectiveness of their designs.

The absence of a distinction between "beginners" and "experts" in our analysis seems problematic as well. This is clearly the case in the ATC example: we know from previous observation that ATC controllers do not scan the strips the way we described the process above. Instead, they rely heavily on their knowledge of the sector, recurrent problems and recurrent aircraft to detect conflicts. Again, our description aimed at eliciting what the visualization enables for a reader that only uses information extracted from the representation. However, during normal operations, ATC controllers regularly do what they call a "tour of the radar image" or a "tour of the strip board", in order to check "everything". In this case, they are supposed to heavily scan both representations and may exhibit some of the theorized behavior. Furthermore, we observed that ATC controllers make more errors when training on a new sector, at least partly because of representation flaws. These flaws are compensated for by expertise, which is somewhat related to knowledge in the head and memory (in some cases, an ATC controller is considered as expert on a sector only after 2 years of training). However, in high-load situations, with lots of aircraft, or with particular problematic conditions such as unexpected storms, the representation becomes more important and controllers seem more likely to exhibit the theorized behavior.

CONCLUSION

In this paper, we presented a method to analyze theoretical scanning of graphical representations. The method relies on a set of elementary operations, which includes operations from previous taxonomies and new ones (entering, exiting, memorizing) together with new considerations (back steps, visual steering, and the use of ordered or quantitative arrangement). We argue that rationale for design can be expressed in terms of these elementary operations. We showed in various examples how such an analysis can be achieved and how gains and losses can be explained with elementary operations. The set of elementary operations forms the basis of a shared, common language that helps designers justify and compare their choices.

In its current form, the method is descriptive, not predictive. We believe that we are still far from a fully predictive model of human performance in representation use. In the meantime, we argue that a descriptive method is useful for designers, since the decomposition highlights the challenges encountered by a user when deciphering a representation. The benefit is equivalent to one of the two benefits of KML: in addition to predicting completion times, KLM helps designers to understand what a user must do to accomplish an interaction task.

In addition to the examples presented here, we have successfully applied our analysis method presented to other representations, such as calendars (month, week and day view), item rating by customers in online stores, widgets, and radar images. Work is certainly needed to expand the set of operations and the elements that aid or affect their realization. For example, we do not yet take into account the fact that tasks can be aided when externalizing constraints into the real world [START_REF] Zhang | The Nature of External Representations in Problem Solving[END_REF], nor did we take into account representations that ease mental computation [START_REF] Zhang | A Representational Analysis of Numeration Systems[END_REF]. Furthermore, different acts of mental computation and memorization may exhibit very different costs. In addition, while we tackled the "what to do" question in this paper, we did not tackle the question of "how to do it". Eventually, we need to propose a systematic method that will help designers find for themselves the steps and considerations to take into account when evaluating the effectiveness of a particular representation.

Figure 3 .

 3 Figure 3. SpiraClock. Left: visual scanning. Right: a configuration that displays more information

Figure 4 .

 4 Figure 4. A linear, quantitative bus schedule representation

Figure 6 .

 6 Figure 6. Scanning on regular ATC paper strip

Figure 7 .Figure 8 .

 78 Figure 7. Scanning with paper strips in colored holders

ACKNOWLEDGEMENTS

The authors wish to thank the reviewers for their very relevant suggestions. We also thank N. Roussel and W.G. Philips for their helpful comments.


Christophe Hurter
email: christophe.hurter@aviation-civile.gouv.fr

Benjamin Tissoires
email: tissoire@cena.fr.

Stéphane Conversy
email: stephane.conversy@enac.fr.

FromDaDy: Spreading Aircraft Trajectories Across Views to Support Iterative Queries

Keywords: spreading aircraft trajectories across views to support iterative queries visualization, iterative exploration, direct manipulation, trajectories

published or not. The documents may come

INTRODUCTION

In the Air Traffic Control (ATC) field, analyzing traffic or devising new ways of managing airspace requires trajectories analysis. An aircraft trajectory is a record of positions of an aircraft in a given airspace (3D+time plus other information such as identifier, speed etc). As such, trajectories are multidimensional data. Air Traffic stake-holders regularly analyze traffic to:

• understand past conflicts and then improve safety with adequate evolutions, • assess new onboard and ground safety systems and the resulting aircraft trails, • devise new air space organization and procedures to handle traffic increase, • compare trails with environmental considerations (fuel consumption, noise pollution, vertical profile comparison), • study profitability from a business trajectory point of view (number of aircraft on a specific Flight Route per day, number of aircraft that actually landed at a specific airport…), • filter and extract trajectories in order to re-use them (this task will be later illustrated in this paper in the section on trajectory extraction for Air Traffic Controllers' training).

Formulating queries over trajectories in a declarative, textuallanguage based manner, such as a SQL, is hard. Even if it is possible to select trajectories that flow over specific locations, it is very difficult to specify features like "select trajectories where this part of the trajectory is straight" or "where this part has a constant climbing rate"… Thus, visual analysis remains the only way to detect relevant trajectory features efficiently.

Trajectories are numerous and tangle: one-day's traffic over France for example, represents some 20000 trajectories ( Fig. 1). When dealing with trajectories, users must perform dynamic requests (response time < 100 ms [START_REF] Shneiderman | Direct manipulation: A step beyond programming languages[END_REF]) on a huge multi-dimensional dataset (>1 million data). In addition to the data size problem, users have to deal with a dataset that contains many errors and uncertainties: recording is done in a periodic manner (in our database: a radar plot per aircraft every 4 minutes), but a plot can be missed, or have erroneous values because of physical problems that occurred at the time of recording. The problem we address in this paper is to find a way to express these queries, simply and accurately, given the constraints of size and uncertainty of the datasets.

We have developed FromDaDy (which stands for "FROM DAta to DisplaY"), a visualization tool that tackles the challenge of representing, and interacting with, numerous trajectories involving uncertainties. FromDaDy employs a simple paradigm to explore multidimensional data based on scatterplots, brushing, pick and drop, juxtaposed views and rapid visual configuration. The fundamental new aspect of FromDaDy compared to existing visualization systems, is to enable users to spread data across views. Together with a finely tuned mix between design customization and simple interaction, users can filter, remove and add trajectories in an iterated manner until they extract a set of relevant data, thus formulating complex queries. The remainder of this paper is organized as follows. First, we present relevant related work. Then we list the design requirements to fulfill the trajectory analysis task. Next, we describe FromDaDy features and justify our implementation choices. Finally, we outline the strengths of FromDaDy with two specific data extraction scenarios.

2.1

The dataflow model

Card, Mackinlay and Shneiderman [START_REF] Card | Readings in Information Visualization: Using Vision to Think[END_REF] proposed a model that describes visualizations as a data flow sequence from the raw data to the views. This data flow model is still widely used in a lot of visualization software (SpotFire [START_REF] Ahlberg | Spotfire: an information exploration environment[END_REF], VQE [START_REF] Derthick | An interactive visual query environment for exploring data[END_REF] , InfoVis Toolkit [START_REF] Fekete | The InfoVis Toolkit[END_REF], ILOG Discovery [START_REF] Baudel | Browsing through an information visualization design space[END_REF], nVizN [START_REF] Wilkinson | The grammar of Graphics[END_REF]…).

Fig. 1 : One-day's record of traffic over France. The color gradient from green to blue represents the ascending altitude of aircraft (green being the lowest and blue the highest altitude). The French coastline is apparent here in terms of sightseeing by light aircraft and the straight blue lines represent high altitude Flight Routes.

Simple filtering and selection

Though originally designed for data exploration, Dynamic Queries [START_REF] Ahlberg | Dynamic queries for information exploration: an implementation and evaluation[END_REF] represents the seminal work in query design. The associated "range-slider" widget, allows for fast, incremental manipulation of ranges, with immediate effect [START_REF] Shneiderman | Direct manipulation: A step beyond programming languages[END_REF] . As such, a range-slider reifies a simple query, which filters out data outside the range. Some systems allow data to be selected by defining an area over graphical entities, which changes their appearance (for example, they are reddened). In a multiple view system, such as a scatterplot matrix, selected data appear highlighted both in the view manipulated by the user, and in the other views, making it possible to understand the relationships between selected data. Interactions for selecting data include one-by-one designation [START_REF] Livny | DEVise: integrated querying and visual exploration of large datasets[END_REF], rubber-band rectangle [START_REF] Livny | DEVise: integrated querying and visual exploration of large datasets[END_REF][8], lassoing [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF] or brushing [START_REF] Becker | Brushing scatterplots[END_REF]. Various systems propose enhanced brushing techniques, such as XmdvTool [START_REF] Ward | XmdvTool: integrating multiple methods for visualizing multivariate data[END_REF]. However, they require a complex interface to tune parameters, which hinders rapid iteration. For example, an "erase-data" mode in XmdvTool is accessible, but only through a dialog box.

Defining filtering and selection

All tools enable the user to define a selection, but again in various degrees. With Dynamic Queries, users can point to a range-slider previously manipulated to adjust the range. "Rolling the Dice" [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF] makes it possible to "sculpt" queries, but only by defining a new selection to be combined with existing ones. Though not fully explained, it seems that redefining a selection requires defining a completely new one: it does not seem possible to resize a rubber rectangle or modify a lasso shape. XmdvTools allows the user to add a new brush over an existing one, but does not allow removal of parts of the stroke [START_REF] Ward | XmdvTool: integrating multiple methods for visualizing multivariate data[END_REF]. TimeSearcher allows the user to select time series with movable boxes [START_REF] Hochheiser | Dynamic query tools for time series data sets: timebox widgets for interactive exploration[END_REF].

Multiple filtering and selections, Boolean operations

Multiple range-sliders implicitly combine their queries into a single one, implementing a Boolean "and" operation. Some systems allow multiple selections (sometimes called "layers"), differentiated by colors. This enables the user to find patterns between the different groups of selected data. The combination of selections is done by the visualisation of a mix of differently colored shapes. Thus users visually apply a "xor" operation when seeking groups of isolated shapes, while they apply an "and" operation when they try to group differently-colored shapes.

In some systems, users can explicitly define how selections are combined by choosing a Boolean operation: the resulting selection is then highlighted with yet another color. The interaction uses either a specific tool [START_REF] Ward | XmdvTool: integrating multiple methods for visualizing multivariate data[END_REF], or a specific button of the interface at the start of the interaction [START_REF] Martin | High Dimensional Brushing for Interactive Exploration of Multivariate Data[END_REF]. "Rolling the Dice" [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF] reifies selections into stacked rectangles that enable the user to combine selections by dragging and dropping one rectangle onto another. The choice of which Boolean operation to apply is made by dragging either with the right button (and) or the left button (or). Once executed, the two selections are merged into one, and they cannot be manipulated any further.

Views organization and navigation

Matrix scatterplots are scatterplots arranged in a matrix, so that every scatterplot on a row (or column) shares the same dimension on the X (or Y) axis. As each dimension is spatially matched to the others, users can detect spatial patterns at a glance. In addition, there is no need to navigate between views, as all of them are displayed at once. This enables users to switch rapidly between views, so as to interact with the view that is the most adapted to the problem at hand. By contrast, a traditional visualization system offers few ways to display multiple views, and forces the user to switch between views with standard window manipulation. However, the size of scatterplots matrix scales quadratically with the number of dimensions, and results in thumbnail views that are difficult to visualize and interact with. Furthermore, even if interaction-free navigation requires finding a particular scatterplot in the matrix, this sometimes takes time; the user has to find the row and the column of the two dimensions to explore, and then find the scatterplot at the intersection between the row and the column. Designed to overcome this problem, "Rolling the Dice" [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF] offers a number of interactions to navigate from one scatterplot to another, and displays a rolling dice-like animation when switching between views. However, "Rolling the Dice" displays only one scatterplot at a time (with geometrically transformed selections already made in other views). This makes interaction with previous selections longer, as it requires the user to look back and switch to a more appropriate view.

DESIGN REQUIREMENTS

This section presents the design requirements required to achieve trajectory exploration. The majority of our tasks consist in finding real world trajectories with a specific set of features. This contrasts with the traditional InfoVis tasks, where the goal is to discover trends or outliers. Trajectory features are difficult to specify for two reasons. First, they are often only specifiable with visual features (straight lines, or general shape). Furthermore, users often explore the queries as much as they explore the data: in the course of exploration, users discover that the set of features they thought relevant has to be adapted, either because they were false, or because they cannot figure out how to query them efficiently. Hence, the system must permit the customization of views so as to offer multiple means of understanding and querying the data visually. It should allow for a quick change of mapping between data and visual dimensions. Often, the set of interesting trajectories for a particular task can only be described by extension: hence, the system must also support iterative selection design, i.e. the ability to store a temporal state of a selection and to be able to improve it later. Trajectory databases are huge and multidimensional (more than 500000 records with more than 10 fields: aircraft's name, speed, location…). The system should be able to handle this amount of data, and display graphical entities with a frame rate compatible with smooth interaction. As said earlier, our database contains many errors and uncertainties; thus the user must be able to figure out if the displayed trajectory is reliable or not. If not, users must understand why.

Fig. 2 : The brushing interaction allows the user to select trajectories by brushing them with a size configurable tool.

RADAR DATASET

Our radar dataset contains recording of aircraft parameters at a given time (Table 1). This dataset may contain many other fields, but we present here the most important ones. Records are linked through the aircraft identifier (provided by radar tracking). Points are gathered to form trajectories.

Field name details Latitude

Latitude of the aircraft at a given time Longitude Longitude of the aircraft at a given time Flight Level

Altitude of the aircraft Time

The time of the record Speed

The aircraft speed Track ID

The unique identifier of the aircraft The trajectories dataset contains many errors:

• The radar tracking system is faulty when an aircraft has a very low altitude, •

The onboard system may emit temporally wrong information (aircraft ID and altitude) ,

•
The flight route used by aircraft may not correspond to the current aircraft heading (due to metrological considerations, traffic optimization or safety reasons).

These errors are very important since they can highlight a radar loss detection area, or onboard technical problems. Errors can easily be detected visually when they create outliers or discontinuities in visualization: e.g. the aircraft altitude suddenly jumps to zero then back to high. The dataset also contains uncertainties, which are due to the sampling rate of the aircraft position. Our available dataset contains aircraft positions every four minutes. Therefore the actual aircraft position between two consecutive positions is unknown. For exemple, aircraft having landed may stop at a high altitude (the last detected position lasting four minutes).

SYSTEM DESCRIPTION

This section details FromDaDy basic features for trajectory exploration tasks.

Visual configuration

FromDaDy uses the data flow model, through a tool that enables a user to draw connections between data dimensions and visual variables [START_REF] Bertin | Graphics and Graphic Information Processing de[END_REF], thus specifying a visual configuration. For instance, in the left hand image of Fig. 3, the user connected the longitude with the X axis of the view and the latitude with the Y axis of the view. The user also connected the altitude field of the database to the color of the lines. The resulting connections produce a vertical representation of a one-day traffic record over France (see right Fig. 3). The user can also double-click on axis X or Y of a view to make the field selection menu appear, and change the mapping for that axis.

FromDaDy uses an automatic scaling process to make data visible on the screen. This process is based on scaling with the min/max value of each field of the dataset and the configuration of the view. For instance, the user connected longitude with the X screen and latitude with the Y screen: FromDaDy scales the view so that all latitude and longitude values fit into the view.

Brushing interaction and incremental selection

The user selects a subset by means of a brushing technique. Brushing is an interaction that allows the user to "brush" graphical entities, using a size-configurable or shape-configurable area controlled by the mouse pointer [START_REF] Becker | Brushing scatterplots[END_REF]. Each trajectory touched by the area during the mouse movement is selected, and becomes gray. The selection can be modified by further brush strokes ("Ctrl key" pressed), or by removing parts of it with brush strokes in the "erase" mode ("Shift key" pressed). Our implementation leaves a brush trail, so that the user can see and remember more easily how the selection was made. All trajectories that cross the trail are selected: hence, modifying the selection is like painting or erasing the trail (Fig. 2). While the ctrl and shift key are pressed, the size of the stroke can be adjusted with the mouse wheel. If neither of them is pressed, the mouse wheel allows zooming of the view in and out. The combination of fast switching between the add or erase mode, trail visualization, rapid size-setting, and cursor-centered zooming with the mouse wheel provides for fast, incremental selection.

"Pick and drop" paradigm

Thanks to the brushing technique, the user can select and highlight parts of the displayed data. By hitting the space bar, the user can extract previously selected data and attach them to the mouse cursor (beginning of Fig. 5). By default, the selected data are picked: they are removed from the view, and appear in a "fly-over" view (transparent background). When the user hits the space bar for the second time, a drop occurs in another view under the cursor. If there is an empty view under the cursor (gray views as shown in Fig. 5), the software creates a new view with the selected data. If the user presses the space bar while moving over an existing view, FromDaDy adds the selected data to this view.

Although it resembles to a regular drag'n'drop operation, we prefer to use the term "pick'n'drop" [START_REF] Rekimoto | Pick-and-drop: a direct manipulation technique for multiple computer environments[END_REF], in the sense that data is removed from the previous view and is attached to the mouse even if the space bar is released.

The organization of Views

A session starts with a view displaying all the data. The visualization employs a default visual configuration, i.e. the mapping between data dimensions and visual variables. The view is inside a window, and occupies a cell in a virtual infinite grid that extends from the four sides of the cell. With the brushing and the Pick/Drop paradigm, the user creates new views and changes their visual configurations. The user can select the other cells to display another representation of the data. The user can also destroy a view if the brush selects all the trajectories and if the user picks them.

Rolling dice animation

Sudden changes in the axis of the view are disruptive since they prevent the user from tracking changes over time. Therefore FromDaDy uses an animation similar to "Rolling the Dice" [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF]. In other words, one dimension in the focused view is preserved while the other changes. The change is visualized using an animated transition. As in [START_REF] Elmqvist | Rolling the Dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF], instead of simply interpolating the position of each point for the transition, FromDaDy performs the transition as a 3D rotation. This gives some semantic meaning to the movement of the points, allowing the human mind to interpret the motion as a rotating shape, and to keep the focus on visual entities during the transition. The user can also control the transition with a click and drag along an axis (Fig. 4). Rolling dice animation is also used when dragging the picked data over a view. During this qualitative evaluation we observe how they took advantage of FromDaDy's assets: the spreading of trajectories across views, the extended features of the pick/drop paradigm, the visual configuration choices, and the implicit Boolean operations.

Spreading data across views

Within FromDaDy, there is a single line per trajectory instance: trajectories are not duplicated, but spread across views. The advantage of this technique is twofold. Firstly, it enables the user to remove data from a view (and drop them on to the destination view). The fly-over view enables the user to decide rapidly if the revealed data (previously hidden by the picked one) are interesting. Secondly, it makes it possible to build a data subset incrementally. In this case, the user can immediately assess the quality of the selection, by seeing it in the "fly-over" view. Furthermore, by removing data from first view, the user makes it less cluttered, and makes it easier for him to pick data again from the first view and drop them on to the second view.

Picking, transition, and visual configuration picker

The rolling dice animation is also used when the user moves a picked set of trajectories around. When moving over an existing view, the visual configuration of the view may be different from the picked view. In order to prevent sudden changes, FromDaDy animates the transition: the colors, size, pan and zoom change until they reach the parameter of the view under the mouse pointer. This animation is easy to understand and helps the user to figure out the selection layout in the new view before dropping. This enables users to reassess the quality of the selection, as it allows them to forecast the result of the drop. Furthermore, this interaction acts as a visual configuration picker. The user may want to pick trajectories and apply the visual configuration of another view. To do so, the user brushes and picks trajectories, moves the picked trajectories over the view with the desired visual configuration, sees FromDaDy apply the configuration to the picked trajectories, and drops the trajectories into an empty cell.

Line and brush combination for efficient selection

Trajectories are displayed as dots connected by a line. Other design choices may have been envisaged: one color, shape or size per trajectory. Because trajectories are too numerous, lines remain the only suitable design to separate them visually.

As said above, brushing selects entire trajectory instead of single plots. Line brushing has significant advantages: in a very dense area the brushing of a specific trajectory is difficult, whereas the user can select the same trajectory in a less dense area (for example, the surroundings). The zoom is not always a suitable solution to address the problem of selection in a dense area, since the user often needs a complete view on the trajectories. This design choice may lead to false interpretation as the system connects two non-consecutive plots: the line may hide radar detection loss. This kind of data error can be visually detected when trajectories are straight over a long distance.

Trajectory exploration requires more complex selection shapes than a simple rectangle box, and a configurable selection shape, as supported by FromDaDy is more important than, i.e. a movable one. Unlike many visualization systems, FromDaDy employs a simple brushing tool: the user is able to add brush strokes, and remove parts of them. There is no "erase-data" mode, as pick and drop into a trash cell does the same thing. Though simple to master, FromDaDy allows for complex geometrical queries that other visualization software cannot easily perform.

Implicit specification of Boolean operations

Boolean operations are cumbersome to produce, even with an astute interface, as results are difficult to foresee [START_REF] Young | A graphical filter/flow representation of Boolean queries: a prototype implementation and evaluation[END_REF]. FromDady reduces this drawback, since any operation of the interaction paradigm (brushing, picking and dropping) implicitly performs Boolean operations. The following two examples illustrate the union, intersection and negation Boolean operations. With these three basic operations the user can perform any kind of Boolean operation: AND, OR, NOT, XOR… Fig. 7, the user wants to select trajectories that pass through region A or through region B. He or she just has to brush the two desired regions and Pick/Drop the selected tracks into a new view. The resulting view contains his or her query, and the previous one contains the negation of the query. In Fig. 8 the same process is used to find the tracks that pass through A and B. By sequencing two "pick and drop" operations, the user formulates his or her request.

Seamless view navigation

FromDaDy gives the user partial control over the organization of the workspace. There are no windows to create and manipulate, and there is only a single layout available (juxtaposed views). This enables quick back and forth pick and drop operations between two views, with rough brushing to unveil hidden trajectories followed by precise brushing to restore some of them. The visual configuration tool is always available and allows for rapid representation change.

Hence the user never has to interrupt the exploration process to cope with secondary manipulation. Furthermore, when exploring a query, the user can arrange the workspace, so as to lay out successive steps. This results in a kind of a storyboard that helps visualize the procedure (and not only the data). Thus, in the middle of an unsuccessful exploration, the user can quickly check intermediate views to figure out why the procedure is incorrect.

SCENARIOS

This section presents two scenarios that underline FromDaDy's assets. This first scenario illustrates how users can explore a dataset and interactively refine their visual queries. The second scenario is a real case, where FromDaDy was used to extract trajectories for a training simulator for Air Traffic Controllers.

Iterative exploration

The visualization in Fig. 9 displays air traffic over France during one day. The user wants to display transatlantic aircraft that landed or took off at Roissy airport during one day (Roissy is at the main intersection of the lines). To answer this query, the user first devises a procedure composed of two ordered steps. He or She initially decides to filter aircraft that flew over the Atlantic Ocean.

To do so, the user brushes the left hand area of the visualization which selects aircraft that flew over the ocean (Fig. 9, right). For the second step, the user changes the view configuration to a vertical view (altitude, latitude) and selects aircraft that have a very low altitude at the latitude of the airport (Fig. 10). The user then changes back the view configuration to a top view (X:latitude, Y:longitude). He or She picks the selected data and starts dragging it.

Then the user discovers that trajectories from a second airport, close to Roissy, is part of the selection, and that trajectories landing at Roissy still exist in the view with unpicked data. Furthermore, an intruder aircraft stands out (on the bottom right of Fig. 11). This aircraft performed an unexpected transit flight through Lyon airport, which was not requested. The result of the visual selection is effectively inaccurate: the selection misses trajectories that did not end at a low altitude (erroneous data due to radar detection loss or to the 4 minute sampling rate). Furthermore, the vertical view forces the user to select all trajectories with a low altitude at the same longitude of the selected airport (the two main airports in France have the same longitude but not the same latitude).

Hence, the user has to revise the formulation of the query. He or she performs many tentative explorations and finally finds an additional statement: "aircraft that land at this airport do not overshoot it". The user selects aircraft that flew over the ocean, and deletes the ones that overshoot the airport, by using a filter-out brushing operation. He or she thus obtains the required result. This example illustrates how iterative exploration allows the user to find out the correct procedure to use and how the user modified the query to find the correct result. It also illustrates how unexpected data can be easily removed.

Specific trajectory extraction for ATC controller training purposes

In this section, we detail in an actual scenario, in which FromDaDy was used to carry out a data exploration task. The user is a specialist in the Air Traffic Control field. His task was to extract specific aircraft fulfilling the following criteria. Aircraft must pass exactly over specific beacons (corresponding to referenced Flight Routes).

Their vertical profile must correspond to a constant climbing trajectory: there should be no continuous horizontal flight. Finally, aircraft must be sorted by their main departure direction. Aircraft do not always follow standard Flight Routes. Air Traffic Controllers can shorten a trajectory for optimization reasons. Furthermore, an aircraft can deviate from its trajectory if it overshoots beacons. The user has to filter out this kind of data, even though the criteria that specify them are fuzzy. Step by step actions

The system first displayed a specific view (longitude->X, latitude->Y) (Fig. 13). As explained above, the data are linked by the "Track ID name", the user can group and join them with a line on the screen, in order to display the different trajectories. Thus, each trajectory concerns a single aircraft.

The user has a rough idea of the position of the standard trajectories and immediately detects them: as they are superposed, they merge into darker lines. The trajectories that surround them are either trajectories shortened by the controller or trajectories that deviated from the initial plan. The user eliminates these trajectories by brushing them and dragging them into a trash cell. FromDaDy also displays two numbers that correspond to the cursor position in the data dimension of the visualization. This enables the user to position the brush precisely at the longitude of the last beacon, and brushes all trajectories that overshoot it, in order to drag them into the trash cell. At this stage, the user creates as many views as identified aircraft procedures (two North, one East, and one South departure). To do so, he selects, picks and drops each trajectory into their corresponding view (sorting stage: Fig. 14). The final step is the selection of the correct vertical profile (Fig. 15). The user changed the visual configuration to a "vertical view" (latitude->X, altitude->Y). The user wanted a constant vertical profile: no aircraft with a continuous flat altitude. Thus the user began to dismiss more aircraft in one view. However, he noticed that he would have been obliged to do so with the three other views. He thus retracted to the previous step by recreating the cell with unsorted trajectories. He applied the vertical profile filtering, and did the sorting step again, thus optimizing his procedure. By organizing the layout of temporary views, the user has been able to target rapidly which steps to retract to. During the vertical profile filtering, the user noticed that the animated transition could have helped him if the views had been correctly arranged. He copied the vertical view under the top view, so that the animation between the top view (longitude, latitude) and the vertical view (longitude, altitude) helped to filter the requested flights: the longitude is common to the two views, therefore the user could focus on the longitude of the last beacon of the Flight Plan and, during the view transition, he could pick out aircraft that had a constant climbing rate up to this longitude (the user can keep the focus on a specific longitude). Again, the ability to organize the workspace rapidly allowed him or her to emphasize the animation feature.

TECHNOLOGICAL CONSIDERATIONS

FromDaDy is built in C# with the .Net framework 3.0 for interface implementation and DirectX 10 for GPU programming. The brushing technique with 5 millions points is technologically challenging. Therefore we had to take full advantage of modern graphic card features. FromDaDy uses a fragment shader and the render-to-texture technique [START_REF] Harris | Mapping computational concepts to GPUs[END_REF]. Each trajectory has a unique identifier. A texture (stored in the graphic card) contains the Boolean selection value of each trajectory, false by default. When the trajectory is brushed its value is set to true. The graphic card uses parallel rendering which prevents reading and writing in the same texture in a single pass. Therefore we used a two-step rendering process (Fig. 16) : firstly we test the intersection of the brushing shape and the point to be rendered to update the selected identifier texture, and, secondly, we draw all the points with their corresponding selected attribute (gray color if selected, visual configuration color otherwise) (Fig. 16). We also implemented the rendering of points and lines with geometry shaders. Thanks to these techniques, FromDaDy can display up to 5 million points in real time (frame rates of over 20 FPS) with 2009 computer generation and a 2009 graphic card (8800GTX).

Fig. 3 .

 3 Fig. 3. The connection tool for visual design (left), menu axis (right)

Fig. 5 .

 5 Fig. 5. Pick and Drop interaction

Fig. 4 :

 4 Fig. 4 : Users control the transition between top (Latitude, Longitude) view and vertical (Altitude, Longitude) view by dragging the mouse along the vertical axis.

Fig. 6 .

 6 Fig. 6. FromDaDy interface with cells, design tools and one picked selection

Fig. 7 .Fig. 8 .

 78 Fig. 7. Union Boolean operation

Fig. 9 .

 9 Fig. 9. One day traffic (left), transatlantic selection (right). The thicker polygon is the outline of France.

Fig. 10 .

 10 Fig. 10. One day traffic vertical view (left), bottom selection (right).

Fig. 11 .

 11 Fig. 11. Resulting selection with one intruder (left), zoomed (right)

Fig. 12 .

 12 Fig. 12. Selection of non overshooting items (left), Zoom out (right).

Fig. 13 .

 13 Fig. 13. Original aircraft trajectories (left), landing aircraft trajectories (right) and standard procedures (right hand figure, outlined trajectories are the published Flight Routes by the air transportation authority) 7.2.1Step by step actions

Fig. 14 .

 14 Fig. 14. Trajectories that follows the standard procedures (center), sorted trajectories (corners)

Fig. 15 .

 15 Fig. 15. Trajectories with flat level vertical profile (left), trajectories without flat level (right).

Table 1 :

 1 Record field names and semantics.

ACKNOWLEDGEMENTS

The authors thank Stéphane Chatty, Jean-Luc Vinot, Jean-Daniel Fekete and Pierre Dragicevic for their invaluable discussions and suggestions. The authors add a special thank you to Jean-Paul Imbert, the very first user of FromDaDy.

CONCLUSION

FromDaDy is a multidimensional visualization tool making it possible to explore large sets of aircraft trajectories. FromDaDy uses a minimalist interface: a desktop with a matrix of cells, and a dimension-to-visual variables connection tool. Its interactions are also minimalist: brushing, picking, and dropping. Nevertheless the combination of these interactions permits numerous functions: the creation and destruction of working views, the initiation and refinement of selections, the filtering of sub-datasets, the application of Boolean operations, the creation of relevant steps during the exploration process, and the organization of the desktop layout to create a storyboard and visualize the query building procedure.

Through two scenarios, we showed how FromDaDy supports iterative queries and the extraction of trajectories in a dataset that contains up to 5 million data points with errors and uncertainties. As such, FromDaDy, meets the need for a rapid, flexible and accurate exploration of numerous trajectories in the ATC field. Our contribution is not a new interaction technique but rather a carefully reasoned justification of how existing techniques can be usefully combined to perform trajectory extraction. The cornerstone of FromDaDy is the trajectory spreading across views with a simple brush/pick/drop paradigm. We plan to assess FromDaDy with practitioners in traffic analysis. This will enable us to provide longitudinal studies of other tasks.

FromDaDy is not limited to displaying aircraft trajectories. It can use different types of data; we plan to perform further experiments with other datasets, such as GPS tracking.


A

  Dual-band High Impedance Surface mounted with a spiral antenna for GNSS applications Mélusine Pigeon, Christophe Morlaas, Hervé Aubert To cite this version: Mélusine Pigeon, Christophe Morlaas, Hervé Aubert. A Dual-band High Impedance Surface mounted with a spiral antenna for GNSS applications. APWC 2011 IEEE-APS Topical Conference on Antennas and Propagation in Wireless Communications, Sep 2011, Torino, Italy. pp 994 -997, 10.1109/APWC.2011.6046821. hal-01022277 978-1-4577-0048-4/11/$26.00 ©2011 IEEE