Micheline Elias
email: micheline.elias@ecp.fr

Anastasia Bezerianos
email: anastasia.bezerianos@lri.fr

Annotating BI Visualization Dashboards: Needs & Challenges

Keywords: Annotation, visualization dashboards and Business Intelligence, ACM Classification H, 5, m, Information Interfaces and Presentation (e, g, HCI): Miscellaneous

Annotations have been identified as an important aid in analysis record-keeping and recently data discovery. In this paper we discuss the use of annotations on visualization dashboards, with a special focus on business intelligence (BI) analysis. In-depth interviews with experts lead to new annotation needs for multi-chart visualization systems, on which we based the design of a dashboard prototype that supports data and context aware annotations. We focus particularly on novel annotation aspects, such as multi-target annotations, annotation transparency across charts and data dimension levels, as well as annotation properties such as lifetime and validity. Moreover, our prototype is built on a data layer shared among different data-sources and BI applications, allowing cross application annotations. We discuss challenges in supporting context aware annotations in dashboards and other visualizations, such as dealing with changing annotated data, and provide design solutions. Finally we report reactions and recommendations from a different set of expert users.

INTRODUCTION

Well-designed interactive visualizations help users gain insights into their data, identify patterns, and make decisions. During visual analysis, a single analyst or a group, access information from multiple sources to combine insights. These analysis sessions may last from a few hours to many weeks. Given the limits of human memory [START_REF] Cowan | Attention and Memory: An Integrated Framework[END_REF] remembering all reasoning details and milestones in the analysis process becomes challenging. Thus the importance of "externalizing" memory, knowledge, and insights [START_REF] Hutchins | Cognition in the Wild[END_REF] has been identified early on. Analysts achieve this by making sense of their visualizations, annotating them with their findings [START_REF] Heer | Design considerations for collaborative visual analytics[END_REF], organizing their findings, and presenting them to others [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative visualization[END_REF] [START_REF] Shrinivasan | Supporting the analytical reasoning process in information visualization[END_REF]. Annotations are thus an integral part of complex visual analyses, aiding analysts in revisiting and reusing past analysis sessions [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF]. Recent work has started to explore the potential of utilizing the context surrounding annotations to better support users in data discovery and analysis (e.g. [START_REF] Chen | Click2annotate: Automated insight externalization with rich semantics[END_REF] [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF]).

In the domain of Business Intelligence (BI) analysis , the most popular visualization tools are dashboards [START_REF] Cutroni | Google Analytics[END_REF], collections of multiple visual components (such as charts) on a single view [START_REF] Few | Show Me the Numbers: Designing Tables and Graphs to Enlighten[END_REF]. Despite the growing use and research work on annotations for visual data analysis in general, related research on the domain of BI dashboards and other complex multi-chart visualization environments (coordinated views [START_REF] Roberts | State of the art: Coordinated & multiple views in exploratory visualization[END_REF]), has not equally progressed. Our work attempts to rectify that.

Based on interviews with expert BI analysts, we derive new requirements for dashboard annotations that current dashboard tools fail to support. Following these requirements and using a user-centered design approach, we develop and evaluate an annotation-enabled dashboard, addressing several challenges.

Our contributions are: (1) A new set of requirements for annotations, targeting dashboards and other coordinated view visualization systems. (2) The design and evaluation of a prototype dashboard that supports context-aware annotations. Using this system, we explain how annotations support advanced analysis functionality such as: "annotate once, see everywhere" annotations for multi-chart visualizations (as was done for text [START_REF] Cheng | Context-based page unit recommendation for web-based sensemaking tasks[END_REF]), annotation recommendations to promote knowledge discovery, and the use of the common data model layer present in BI systems (e.g. [2] [START_REF]SAP businessobjects semantic layer[END_REF]) to link annotations with external data sources and enable cross application annotations and information foraging. (3) We identify and provide solutions to challenges when using context aware annotations, such as issues arising when the "context" changes (e.g. annotated data are deleted or changed at the data source).

RELATED WORK

To help analysts track their analysis process and findings, researchers have suggested the use of history tools (e.g. [START_REF] Shrinivasan | Supporting the analytical reasoning process in information visualization[END_REF] [22] [START_REF] Kadivar | Capturing and supporting the analysis process[END_REF] [START_REF] Derthick | Data exploration across temporal contexts[END_REF]) to review, re-visit and retrieve previous analysis steps [START_REF] Shneiderman | The eyes have it: A task by data type taxonomy for information visualizations[END_REF]. Augmenting visual representations with annotations to record analysis details and findings has also been recommended [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative visualization[END_REF] and implemented in information visual- ization systems (e.g. [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative visualization[END_REF][34] [START_REF] Kapler | Geo time information visualization[END_REF]), allowing analysts to revisit their analysis and re-use previous findings [START_REF] Marshall | Work practice study: Analysts and notetaking[END_REF].

Marshall [START_REF] Marshall | Work practice study: Analysts and notetaking[END_REF] identified three main processing activities during analysis: searching, interpreting, and presenting. Pirolli and Card [START_REF] Pirolli | The sensemaking process and leverage points for analyst technology as identified through cognitive task analysis[END_REF] refer to the first two activities as the information foraging and sense making loops. Annotations are traditionally used to support interpretation (sense making). Visual Analytics (VA) systems like ManyEyes [START_REF] Viegas | Manyeyes: a site for visualization at internet scale[END_REF], and sense.us [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative visualization[END_REF] allow multiple users to annotate their insights on a single visualization, and search through them, encouraging peer learning and social sense making [START_REF] Nelson | With a little help from my friends: examining the impact of social annotations in sensemaking tasks[END_REF]. Others, like Sandbox [START_REF] Wright | The sandbox for analysis: concepts and methods[END_REF] and VisualLinks [8], aid users to collect and group multiple discoveries and insights on a single visualization, and record them in the form of annotations. These support the sense making process of framing relevant information together, clarifying connections and information importance [START_REF] Klein | A data-frame theory of sensemaking[END_REF].

During analysis, fragmented information pieced together often reveals connections and further opportunities for investigation [START_REF] Attfield | Sense-making in visual analytics: processes and challenges[END_REF], contributing to the searching (foraging) aspect of sense making. Recent VA systems have moved beyond this simple information grouping. Annotations are no longer simply attached to visualizations or chart graphics, but to the data, moving towards more context aware annotations. These annotations can then be used explicitly to search (forage) for related visualizations or annotations. The sense.us [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative visualization[END_REF] system provides doubly linked discussions, allowing users to move from visualizations to annotations and vice versa. Aruvi [START_REF] Shrinivasan | Supporting the analytical reasoning process in information visualization[END_REF] allows users to arrange their annotations in a "mind map", a diagram linking related visualization views and their annotations. Users can access past analysis views using keyword searches and text similarity metrics. Shrinivasan et al. [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF] recommend related annotations based on the context of the current analysis. Finally, Chen et al. [START_REF] Chen | Click2annotate: Automated insight externalization with rich semantics[END_REF] use annotation context as a way to semi-automatically annotate facts belonging to the same analysis categories across visualizations.

Most existing VA work supports context aware annotations on a single visualization view. Traditionally BI analysts conduct their analysis using complex visualization dashboards. Dashboards visualize multi-dimensional datasets through a combination of linked charts [START_REF] Cutroni | Google Analytics[END_REF], and are very widespread in BI (e.g. [START_REF]Dundas dashboard[END_REF][3][4] [START_REF] Bezerianos | [END_REF][7]). Annotations are supported in all these dashboards, and are usually attached to data points (not the chart graphic). Nevertheless, these systems do not adequately support several needs identified by BI experts (detailed later), such as annotations spanning multiple charts, or annotation transparency across data dimensions and visualizations (annotate once, see everywhere, as is done in text [START_REF] Cheng | Context-based page unit recommendation for web-based sensemaking tasks[END_REF]).

This body of research uses context aware annotations for different purposes. Our work extends it in two ways: based on expert users' comments we identify desired behavior and possible uses of context aware annotations on visualization dashboards; and we explore challenges in their design and use, for example due to the dynamic nature of "context".

APPROACH

In our work we followed a user-centered design approach. Based on in-depth interviews with expert BI analysts, we derive requirements and needs for annotations on visualization dashboards: this lead to the choice of context aware annotations. Following these requirements and scenarios of use provided from our experts, we developed a dashboard prototype with annotation functionality that supports different analysis tasks. While building our prototype, we identified challenges in using context aware annotations with dynamic data and evolving annotation context. Based on a second interview with experts, we refined our system to address these challenges, following user recommendations. Finally, we evaluated our prototype with different experts and report results and reactions on the benefits and drawbacks of our designs.

INTERVIEW 1: ANNOTATION REQUIREMENTS & NEEDS

To better understand BI expert annotation needs, we conducted a set of in depth interviews with 8 BI experts. Our goal was to investigate their annotation activities when performing analysis using dashboards, as well as their hopes for future annotation enabled dashboards. Experts' experience in the BI domain ranged from 3-11 years. Three used dashboards daily while 5 several times a week.

Interviews were recorded and transcribed, and the emerging themes identified using a card sorting analysis approach. Bellow we summarize our major findings:

BI Dashboards Annotation Practices

All experts confirmed the importance of annotations in their analysis and the need of having annotations directly embedded in their BI dashboard tools. This way analysts can share their analysis with tactical and operational decision-makers simply by using their dashboards and relevant annotation indicators [START_REF] Golfarelli | Beyond data warehousing: what's next in business intelligence?[END_REF]. An expert explained: "The data has no meaning without our analysis and contribution we add to it, so charts and dashboards would be useless without explanations".

When asked about their actual analysis annotation practices, all experts mentioned taking static snapshots of dashboards (Figure 2) and including them in emails or power point presentations, with text comments accompanying them. Their annotated comments are either for dissemination purposes to a larger audience, or serve as personal reminders and analysis findings records. Experts explained that for each annotation they also copy a data query, as a reference to the exact data the annotation refers to.

BI Dashboards Annotation Needs

We further prompted experts to elaborate on their ideal vision of annotation-enabled dashboards. Experts brought to the interviews annotated examples made by them or other BI experts in their groups. These examples indeed consisted of either screenshots of dashboards on paper with hand-written comments, snapshots attached to emails with annotated explanations, or presentation slides with annotated text (Figure 2). By examining this material with them, we extracted annotation functionality they would like to have embedded in their dashboards systems. Seven major needs emerged from the interview and expert's examples:

Multiple Target Annotations

Experts need to attach their annotations to multiple targets (multiple charts on the dashboard). Seven out of eight experts annotated multiple charts on a single dashboard. An expert commented, "The aim of a dashboard is to tell a story, that's why we need a way to link all the dashboard's charts that bold a connection and give the story we need". Another expert said "two different dimensions that cannot be gathered in one chart could answer a specific question, so we need to link them by one annotation to explain and show the result or solution".

Chart Transparent Annotations

Six experts mentioned they need to attach annotations to the actual data points, rather than static visualizations "because usually I change the chart view and then have to rewrite or re-comment for the new representation of data". Another explained that this is useful "not only for having the comment for both chart representations, but when seeing the comment on a different chart, it may show that the interpretation of this point was not right, or maybe a different chart would give a better interpretable view of your data". One expert mentioned that it "would be useful to find other visualizations or annotations for a specific event in that data", i.e. use the annotated data as a focus point from which to find related annotations and visualizations. Here experts highlighted the importance of being able to go from an annotation, or a list of annotations, to the referenced real data on the dashboard.

Visible Annotation Representation on the Dashboard

Five experts preferred to see visual indicators (icons, flags or special visual highlights) of annotations attached to the actual data "like small indicators on the dashboard and clicking them to see the content". They also wanted to have the option to expand and collapse all annotations' text: expand them "to see all dashboard related annotations at a glance and their story", and collapse them "because having them all on the dashboard would be not clear". Moreover they commented that a list of all dashboard annotations should be available, with visual links to their data targets.

Granularity Transparent Annotations

Four experts mentioned they would like to have annotations "transparent" through different data dimension granularities (e.g. country/city, year/quarter/month), and mentioned there are business use cases where they want to mark a specific event of importance in all visualized levels (e.g. mark a market trend). They would like this feature as an option in special business cases, and deactivate it when not relevant.

Annotation Validity & Lifetime

The lifetime of dashboard annotations was an important issue raised, since there are cases where the data referred to by an annotation can change. All experts confirmed the need to archive annotations "we would like to have them archived to be used in future analysis and to access them for comparisons". They would also like to archive with the annotation a snapshot of the visualization on which it was made. Seven experts preferred to have the option to explicitly define the lifetime of annotations either in time periods (sessions, days, weeks, months, etc), or based on validity rules (e.g. valid while the value of sales ranges between 3000 and 5000).

Sharing BI Dashboard Annotations

Experts expressed the need to share annotations, and in particular being able to define user groups to share annotations with. They also requested to be alerted when a specific user or group of users edits or shares an annotation. Nevertheless, all experts expressed the need for private annotations to use as reminders or analysis record keeping.

Formal Annotation Representation on Dashboards

When prompted, all experts stated a preference for a more formal annotation design (e.g. use a toolbar with predefined annotation categories, shapes, arrows and text boxes), rather than hand-drawing shapes or notes [START_REF] Denisovich | Software support for annotation of visualized data using hand-drawn marks[END_REF]. They explained that they very often share annotated dashboards with peers and embed them in presentations, thus they see a "first priority for structured, clean annotations" that look more professional.

Summary

To summarize, we identified the following annotation needs expressed by BI experts, grouped in two categories: a. Functional F1. Multiple Target Annotations Annotations should have multiple data and chart targets. Navigation to the different targets should be possible from the annotation. With few exceptions (e.g. [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF]), most visualization systems annotate single visualization charts.

F2. Chart Transparent Annotations

Annotations need to be attached to data-points, rather than charts. Few systems (e.g. [7]) actually allow data, rather than visualization annotations, and generally they do not show a data point's annotation in different charts.

F3. Granularity Transparent Annotations

Annotation transparency should be optionally preserved across dimension granularities. We are aware of no system that supports this.

F4. Annotation Validity & Lifetime

Annotations should be archived even if the context of the annotation (e.g. annotated data) changes, together with a visual snapshot of the data at the time of the annotation. Moreover, users should also be able to define the annotation lifetime, based on a time period or data related rules. We are aware of no system that supports both these aspects.

F5. Sharing Annotations

Users should have the option to share annotations with specific users groups, or kept them private for personal use. Systems supporting sharing (e.g. [START_REF] Viegas | Manyeyes: a site for visualization at internet scale[END_REF]), do so for single charts.

b. Design D1. Visible Annotation Representation on the Dashboard

Annotations should be attached to the annotated data using small visual indicators that won't clutter the overall view, but with an option to expand them in place.

D2. Formal Annotation Representation on Dashboards BI experts prefer structured and professional looking annotations to hand drawn ones, for presentation purposes.

CONTEXT AWARE ANNOTATIONS PROTOTYPE

Based on these findings we implemented a dashboard prototype which supports annotations that keep a record of their surrounding context (i.e. the multiple data points and charts they are attached to), as well as special annotation properties, such as their validity and lifetime. Using annotation context also allows us to provide annotation recommendations [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF].

In this section, we provide an overview of our prototype. Apart from the described interview, experts were engaged throughout the design of our system. Architecture BI dashboards provide users with a multi-chart interface, connecting one or more data sources and data sets that are represented as charts. Based on our user interviews, we want seamless annotations that work across data sources and charts. To that end we allow annotations to refer to one or many "data targets" on a common data layer.

A common data layer is present in most BI systems (e.g. Oracle, SAP, Microsoft) and provides a layer of data abstraction that unifies different data sources. Thus data queries are performed directly on this layer and retrieve relevant results from multiple sources. Our annotations work on top of this layer: each annotation is stored in a database, together with a reference to its data targets on the common data layer. Although the common data layer is not present in all coordinated views system, there is usually a common querying layer (e.g. a database with SQL queries) that works across charts and controls chart coordination. In such systems our annotations can be connected to the querying layer.

Given this approach, our system permits context aware annotations that can be shared among different applications with a common data layer. Once an annotation is made on data points in one application, it is attached to this data irrespective of application, allowing cross-application annotation and annotation re-use.

The context of an annotation includes the following entities, similar to the model proposed by [START_REF] Chen | Toward effective insight management in visual analytics systems[END_REF]:

• Content: the text provided by the user.

• Authoring metadata: automatically captured information, such as the author and creation date of the annotation. • User defined properties: these include annotation ranking and categorization of annotations (derived from previous research [START_REF] Mahyar | A closer look at note taking in the co-located collaborative visual analytics process[END_REF][13] [START_REF] Marshall | Work practice study: Analysts and notetaking[END_REF]). As well as new concepts such as annotation "validity rule" or "lifetime" (F4 discussed in great detail in the Annotation Challenges section). Defining these properties is optional. • Data targets: these are one or more entities that the annotation refers to (or is attached to). Each target includes: an Overview data context that defines the larger data context of the annotation, for example the chart or data table on which is was made; and more importantly, a Detailed The right hand side of the screen (Figure 1.c) is the list of all annotations that users can navigate. For each annotation in this list we provide a snippet of its content and some authoring meta-data to help user recall. When users click on a specific annotation in the annotations list, they are provided with an overview of related and recommended annotations (Figure 1.d). We discuss this recommendation feature in the Section "How to Use Context".

Annotations in the list are searchable and can be double clicked to pop-up a detailed view of the annotation content (Figure 3). The detailed view includes content and metadata, as well as a list of all target data contexts the annotation is attached to (overview context charts and tables with the detailed data context highlighted, Figure 3.a). A textual description of the context (dimensions, measures, values) is also provided.

For example the annotation seen in Figure 3 is attached to 2 data contexts, part of a doughnut chart from one dataset, and part of a bar chart from another. When seen in a different application sharing the same data layer, this annotation will still show this exact snapshot, including the two original charts and the highlighted points, regardless of how the data is visually presented in the different applications.

Annotations are created in the following way: When a user selects one or multiple regions on different charts (representing different data contexts), she can right click to annotate them. A new detailed annotation window appears showing all charts in the dashboard containing the target data context (even if not selected when creating the annotation), with the specific context highlighted.

User can share their annotations (F5) with others through a private, public option, and can respond to other user's annotations in the form of an annotation thread (Figure 3.e), supporting social sense-making [START_REF] Nelson | With a little help from my friends: examining the impact of social annotations in sensemaking tasks[END_REF].

HOW TO USE CONTEXT

In this section we discuss in detail how our annotation prototype follows the experts' requirements and aids analysts in their tasks on dashboards. The tasks and scenarios described here come either from the interview or from intermediate feedback sessions with experts.

Transparency

Our annotations are transparent through applications, dashboards, charts, and datasets following a common data layer. Moreover, they can be transparent through different hierarchical data granularities, discussed later on.

Our annotations store detailed data context, so whenever this data context appears, so does the annotation (annotate once, see everywhere as it is done for text in [START_REF] Cheng | Context-based page unit recommendation for web-based sensemaking tasks[END_REF]). During the analysis phase this can help in 4 different ways:

(i) Analysts can switch visualizations (chart types) without loosing their annotations (F2), experimenting with alternative representations that may be better suited to their data.

(ii) Our annotations provide a list of all other charts containing the same detailed annotated context. This allows analysts to find new charts that may present these data in different analysis scenarios, e.g. in combination with different measures or data categories. Thus analysts may gain new insights from their data by seeing them in different analysis situations.

(iii) Through annotations, analysts can reach different material (other applications or data-sources) that incorporate the same data context, aiding in knowledge discovery.

(iv) Finally, users have the option to see annotations from lower or higher data dimension granularity (F3). For example when viewing sales data for France they can make an annotation transparent for the hierarchical dimension 'location' and see it appearing in sales in Paris. Noticing such annotations that are explicitly visible across dimension granularities can lead to new exploration paths and insights. We elaborate on this last point and discuss challenges with annotations across granularities in the next interview section.

Chart linking

Our system provides an easy way to add/remove data contexts to/from the annotation, either at the detailed annotation window, or by selecting interactively a data context (e.g. a bar in a bar-chart) and choose the option to link/unlink it to an existing annotation. Annotations can target multiple detailed data contexts from multiple charts, as well as multiple data sets (Figure 3.a). This was a specific requirement from our interviews (F1), made possible through the use of the common data layer across charts and data-sources. Analysts can thus use annotations as a means to chunk or group diverse material together for insight externalization and organization (an important task in sense-making [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF], [START_REF] Klein | A data-frame theory of sensemaking[END_REF]).

Moreover, annotations can be seen as a way to navigate through the linked charts: by expanding the annotation of a data context in one chart, analysts can see all related contexts in other charts, select them and load them in the dashboard. This cross-linking and navigation has been identified as important in reading sense-making tasks (e.g. [START_REF] Tashman | Liquidtext: a flexible, multitouch environment to support active reading[END_REF]) and visualizations representing one chart at a time (e.g. [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative visualization[END_REF]).

Recommendations

We use annotation context [START_REF] Shrinivasan | Connecting the dots in visual analysis[END_REF] to recommend annotations or charts of similar data contexts, promoting knowledge discovery and peer learning from annotations of others.

To identify similar contexts we compute a simple similarity measure. Similarity between two data contexts is the arithmetic average of all common dimension IDs across contexts, all common measures IDs and their values.

Recommended annotations are presented in a list by order of similarity (Figure 1.d). A set of two visual similarity bars was included initially in our prototype, the 1st to show the overall similarity of all dimensions and measures between two annotations, and the 2nd to show the similarity of dimensions only. The goal of this was to help analysts understand the ranking and, if they choose so, to focus the recommendations to dimensions only. Nevertheless experts indicated that the overall similarity was enough for their purposes and we adjusted our prototype (see "User Study").

External search

To aid knowledge foraging and discovery, our system allows users to use their annotation context as a search term outside applications with the same data model. For example we use it to perform system wide searches for documents, as well as to construct a set of well formatted search terms to use in web search engines, like Google.

Automatic annotation

We do not perform automated or semi-automated annotation [START_REF] Chen | Click2annotate: Automated insight externalization with rich semantics[END_REF]. Although we do have all the required components, this previous work targets single chart visualizations to define annotation templates, and requires further work to extend to multiple charts. Nevertheless, in our system there is an implicit automated annotation taking place through the transparency of annotations across applications and data sources.

INTERVIEW 2: DESIGN CHALLENGES & SOLUTIONS

Early on in our interviews, we came across two major design challenges for annotations not addressed in previous work:

(1) how should annotations behave when their underlying data has changed? (2) When are annotations applicable across granularities? We conducted a follow-up interview with the same 8 experts, where we discussed alternatives and collected their reactions and suggestions.

Dynamic context vs. dynamic annotations

Often annotations in BI target dynamic data points (e.g. the averages of sales records that are being updated every month).

There are two design alternatives for how annotations could behave during such data changes.

The first is to make annotations dynamic: when the context of the annotation changes in a small way, then the annotation can be attached to this new context. The challenge is to clearly define what is "a small change".

Based on all our input from participants this "depends on the situation". Some mentioned that changes in data value only could be considered as a small change in some scenarios (while measure and dimension IDs remain the same). For example a participant attaches an annotation regarding sales peak on the data point with dimension ID= month, value = December, and measure ID = sold-quantity, value= 3000. They want to keep this annotation valid even if the value of the measure changes, e.g. becomes 3500. Others mentioned that sometimes if the dimensions or measures go through small changes, the annotation can remain attached to the data points.

Clearly the nature of "small change" is unique to each analysis scenario and requires users to define "change" thresholds. On the flip side, this requirement essentially turns annotations into data monitoring mechanisms: when the annotation is deleted a specific data threshold has been reached.

The second alternative is to acknowledge dynamic context, and assume that the annotation is no longer attached to the data. When the data context changes the system assumes the annotation is no longer valid, and keeps a snapshot of the context under which the annotation was made (dimensions, measures, values), as well as the visual chart it was made on. Nevertheless, all participants stressed that this should not mean the annotation gets lost, but archived.

This last approach is the default approach we chose in our system. The unattached annotation obviously has a context very similar to that of the changed data. Thus if the user revisits the changed data, the old annotation will appear as a highly ranked recommendation, easily accessible. The visual representation of such "archived" annotations should be clearly distinguishable from "active" ones: following the inactive metaphor of UI interfaces, archived annotations are grayed out. We chose this way of addressing dynamic data context, as it is simple to define, and provides a way to archive data changes (see Sec. User Study).

An orthogonal treatment comes as a direct suggestion from our experts. They stated that their analysis is often affected by events through time, or is valid for short time periods. This prompted the notion of a user-defined "validity period" of an annotation. If she so chooses, the user can explicitly define an expiration date or a validity period for annotations, after which annotations get archived or deleted from the system. At this point experts requested the option to be sent a notifica- tion inquiring if the annotation should be archived or deleted. This lifetime functionality is also implemented.

Granularity

In hierarchical datasets, as is the case in many BI data sources (e.g. OLAP databases), users can drill down or up in dimensions. For example for the dimension time we can have 3 hierarchical levels: year, quarter and month, where a year has 4 quarters, and a quarter 3 months. The question that arises is: if an annotation is made at a lower/higher hierarchy level, when should it appear on the dashboard?

In our system, users can reach annotations from different dimension levels through annotation recommendations (as their contexts are similar). Nevertheless, experts asked to have some annotations of other hierarchical levels visible as icons on the dashboard all the time. When asked to identify under which conditions this makes sense, they commented that this also depends on the nature of the analysis. They underlined the importance of viewing such important cross-level annotations for 2 reasons: First, to use annotations as a "bookmark" to an important point in the analysis, while the analyst explores new paths (e.g. annotate 2008 to mark the economic recession, while exploring stock market values per month). Second, to highlight important findings that could influence future analysis.

Through our discussions with the experts, we could not conceive an automated way of detecting such important annotated points, and thus provided an option to explicitly make some annotations visible across hierarchical levels. We also provided users with an option to toggle on/off the visibility of all annotations from different levels.

The visual representation of such annotations was deemed very important by our experts: it should be different from annotations on the same level, but not too complex. After a few design iterations, most agreed on using the same icon used for navigation across dimensions in the dashboard (up/down icon for annotations, drill-up/down in the hierarchy) Figure 4.

USER STUDY

After several iterations of the prototype with the original group of experts, we evaluated it with a different group of experts, to explore if they can use it and benefit from the different aspects of context aware annotations for their analysis. We requested that participants conduct a set of tasks similar to the ones identified in our interviews and user-centered design process. We report our observations and experts' comments and suggestions.

Participants

Seven participants took part in our study. They were BI experts, and only one was previously involved in the design of the system. They all had experience using dashboards. All were familiar with the concept of annotation, mostly in annotating text documents while conducting analysis tasks.

Procedure and Apparatus

Participants performed the study on a 15.6" HD screen laptop. One observer was present to give instructions, explain tasks and observe participants. Sessions lasted from 45 to 90 minutes, were recorded and later analyzed. They started with a survey of participants' annotation practices and ended with an exit interview. During the study we followed a think-aloud protocol, requesting users to vocalize their thoughts and actions while performing tasks.

Tasks and datasets

We used 4 different datasets, each presented on a different chart on the dashboard: (i) Forbes 50 Richest Americans in 2006 (50 records, 4 dimensions); (ii) Population per age group (110 records, 5 dimensions); (iii) World internet users (220 records, 3 dimensions); and (iv) US historical auto sales (25 records, 2 dimensions). Datasets were new to users, but their type was familiar (e.g. the measure sales and dimension year).

As indicated in our interviews, real analysis contains different data sources. Thus using 4 datasets allows us to examine if users could easily use annotations to link different contexts from different datasets.

Participants were told they are analysts exploring different datasets to find trends, and record their findings. We instructed them to think loud, and if they failed to do so, the observer prompted them to vocalize their insights and expectations. Participants were given a brief explanation of the prototype functionalities (e.g. adding new and explore existing annotations). They performed tasks in 3 main groups, focusing on different functionalities of context aware annotations:

T1: Usability and understandability. Participants were requested to analyze part of a dataset and create a new annotation with their insights, attached to specific data. Then they explained their understanding of characteristics of that annotation, such as lifetime, privacy, category, and transparency across dimension granularity levels. Finally they were asked to experiment with other visualizations for the same data found through their annotations.

T2: Retrieval of annotations of the same context. Participants were asked to create an annotation on a specific data context and look for other annotations on the same exact context, or ones linking multiple contexts, including the current. When they detected these annotations, they were asked to determine if they were related to their analysis and explain why (based on the creator, context, datasets, characteristics, etc).

T3: Knowledge discovery. Participants were asked to search for possible similar annotations, and retrieve external search results related to the annotated data (through search in the databases sharing a data layer, or external searches on the hard disk and Google). Participants were asked to collect relevant material and add them to their analysis annotations.

Tasks began by loading a dashboard containing 4 charts, each representing a data set. Participants could change the chart visualizations and were given time to interact and familiarize themselves with the datasets and dashboard before starting the tasks. At the end of the tasks a short interview was conducted to understand how context aware annotations impacted participants' analysis, to clarify observations made during the study, to prompt users to identify difficulties/barriers they faced, and to suggest improvements.

RESULTS

We present here feedback from participants on how the system supported their analysis, and on its visual design.

Supporting Analysis

Participants completed all tasks successfully without any help from the experimenter. We present here observations made regarding the use of context aware annotations in our tasks.

T1: Usability and understandability.

• All participants understood the detailed data context(s) of the annotations, and explained that understanding the context was easy when "having the annotated data visually highlighted in a chart", and having a "detailed textual description of the data context" (dimensions' and measures' names and values) on the annotation body.

• The transparency of annotations between charts allows users to understand new chart types, using the annotated data as reference points across the two visualizations. A participant mentioned "the radar chart was unfamiliar for me, so I switched it to a scatter plot and I was able to still see the annotated data points. The annotation helped me to understand the radar by reviewing the scatter plot and see that I am looking at the same data point".

• Annotating data points vs. charts helps users see changes of important data points. Our system takes snapshots of annotated data points whose context changes. A participant commented that "annotating important data points acts as a way to see their changes through time".

T2: Retrieval of annotations of the same context.

• All participants found attaching annotations to data points (vs. entire charts) very important for verifying annotation relevance to their task, both for searched and recommended annotations (relevant to T3). As one participant mentioned, this "maximizes the analyst's focus on targeted data and not all the chart, and prevents loosing time trying to verify the context for each searched or recommended annotation".

• All participants appreciated the use of annotations as reminders of past work, and as highlights of the important data in charts ("at a glance I can determine the important data points, no matter where I am").

• Finally they all appreciated the use of annotation transparency for all users across all visualizations, as a way to avoid work replication (for example prevent duplication of annotations among multiple analysts).

T3: Knowledge discovery.

• All participants were able to navigate the list of recommended annotations, and interpret their similarity. They mentioned they understood why each recommended annotation had the presented similarity, by comparing the context of the targeted data points and that of the ranked recommendations. Five found that the global similarity measure that combines dimensions and measures is enough, while two would have also liked a text similarity metric.

• All noted the usefulness of recommending annotations for re-use or peer learning ("from notes of others"). They commented that it is especially useful because the reason for the recommendation is clear, due to clear data contexts.

• All participants found retrieving external data related to the annotation context very useful. They all commented that searching for supporting material during analysis will be easier if they can retrieve data from their company's portal using the data context to search other BI applications with the same data layer, or search for files containing the context keywords on their machine or on Google.

Visual Design

Participants provided us with design suggestions to improve the visual interpretation of annotated targets. Their feedback was used to reach the final design presented in this paper.

Here we present some of their comments that influenced the look and feel of our prototype. The first point raised was the use of icons on the main dashboard to indicate annotation on specific data points. Although they found this useful, they suggested that if a data point has many annotations we should use a different icon, that when clicked shows a drop down list of all annotations. This would introduce another annotation icon (apart from that of simple annotations and annotations at different granularities). So we chose an icon containing the number of annotations attached to the data point. The two annotation icons are seen in Figure 1 and Figure 3.

The other recommendation was to visually link annotations targeting multiple charts with lines across the dashboard. One participant had at first some trouble understanding that the charts in the detailed annotation window showed the multiple targets of an annotation. She explained that this could become more intuitive if annotations with many targets on the dashboard were connected with lines to the targeting charts. Thus at the end of the study we provided three design suggestions to our participants: the first (Figure 5.a) highlights targets in red, the second (Figure 5.b) draws arrows to the targets, and the third (Figure 5.c) fades out all related targets. All participants preferred fading out. As one explained 'this shows only points I should focus on while still seeing the whole context; moreover I can print this representation and share it because it has less clutter and more interpretable".

DISCUSSION

The set of requirements and design decisions in this work are highly influenced by the domain of focus (BI). Thus some may not apply to other domains (e.g. the need for formal annotation presentation). Nevertheless, some of the more general requirements on annotation transparency across charts and dimensions, as well as ways of addressing changing data context can be applied to other visualization domains. For example: annotation transparency and re-use saves user effort in any visualization system with many possible data views (e.g. multidimensional visualization systems); granularity transparent annotations that highlight important data across data levels can benefit any system with a hierarchical or layered data representation (e.g. systems supporting semantic zooming); whereas issues related to annotation validity and lifetime affect any dynamic data visualization system (e.g. stock market visual analysis tools). Nevertheless, further work is needed in this regard to clarify the importance of the identified needs and to validate the proposed designs with domain expert users of these visualization systems.

More generally, our work highlights a deeper need for dataaware and transparent note taking: for example in today's spreadsheet applications users can comment specific cells, but when cells are turned into charts the comments are not visible on them. Our system takes advantage of a common data model to annotate specific data contexts and have them available in all data representations and views (even across applications). But the idea of annotating directly data or queries for annotation re-use and recommendation, can be modified to work with any data archiving system that has a querying mechanism for the annotation to be attached to, and a notion of "distance" of the archived objects for recommendations. Thus it can be applicable to interactive applications ranging from spreadsheets to medical imaging archives or large document collections.

CONCLUSION AND FUTURE WORK

Recent years have seen an increase of use of context aware annotations to support VA tasks. We extend this work by defining a new set of requirements for annotations, targeting visualization dashboards and other coordinated view systems, based on in-depth interviews with expert Business Intelligence analysts. With these requirements and a user centered design approach, we developed a dashboard prototype that supports context aware annotations. We discuss how such annotations support new functionality, like "annotate once, see everywhere" for visualizations (not just text [START_REF] Cheng | Context-based page unit recommendation for web-based sensemaking tasks[END_REF]), multichart annotations, and annotations that are transparent across hierarchical data dimensions. They also support knowledge discovery through annotation recommendations, as well as the use of the common data model layer present in most BI systems (e.g. [2] [START_REF]SAP businessobjects semantic layer[END_REF]) to perform cross-application annotation, and information foraging outside the visualization system.

While building our prototype, we identified and provided solutions to challenges in using context aware annotations, notably issues arising when the annotation's "context" changes (e.g. annotated data are deleted). Based on feedback from experts, such annotations should be achieved with a snapshot of their context, as long there is an easy way to retrieve them (e.g. through recommendations). Users should also be able to define the lifetime of annotations.

Our prototype was evaluated with a different set of BI experts that were able to easily perform several tasks that they deemed important in their work: use annotations to discover other visualizations with the same data context and look at data in a new perspective; use annotations to link and organize multiple charts related to their analysis; discover charts and annotations through annotation recommendation and understand the reasons behind it; and use annotation context to find information outside the system.

Although initial reactions to our system are very positive, a long-term study is needed to determine how context aware annotations can impact analysis behavior in the long run.

Figure 1 .

 1 Figure 1. Our dashboard prototype with context aware annotations. (a) The main dashboard contains icons with the number of annotations for each data-point (b). Bellow the list of all dashboard annotations in (c), is a set of recommended annotations (d) emphasizing their similarity.

Figure 2 .

 2 Figure 2. Two annotation examples from participants.

Figure 3 .InterfaceFigure 1

 31 Figure 3. Detailed annotation view, including (a) all related data contexts & detailed data context in text form, (b) content, (c) metadata, (e) discussion thread, and (d) annotation properties (lifetime, privacy, etc).data context, the specific data points that the user is annotating. Both Overview and Detailed data context are stored as data dimension IDs (e.g. year, country) and their values, and measure IDs (e.g. sales prices, population) and values.• Threads: other annotations connected to this annotation (e.g. a discussion thread in collaborative annotating).InterfaceFigure1shows a screenshot of our prototype's main user interface. The left portion of the dashboard screen is the main canvas where the retrieved data is visualized (Figure1.a). Users explore and analyze data by interacting with each visualization chart on the dashboard. We provide functionality such as data filtering, sorting, as well as advanced OLAP functionality[START_REF]OLAP and OLAP server definitions[END_REF] (e.g. drill-down/up). On the main canvas (Figure1.b), annotations are shown as icons (D1) containing the number of attached annotations to the specific data.

Figure 4 .

 4 Figure 4. Annotation transparency through dimension levels.

Figure 5 .

 5 Figure 5. Three designs linking annotations in the annotation list with their data targets. Experts preferred design (c).

ACKNOWLEDGMENTS

This work was supported by Business Intelligence Practice in SAP Research France.


Tristan Porgès
email: porges@i3s.unice.fr

Gérard Favier
email: favier@i3s.unice.fr

AUTOMATIC TARGET CLASSIFICATION IN SAR IMAGES USING MPCA

Multilinear analysis provides a powerful mathematical framework for analyzing synthetic aperture radar (SAR) images resulting from the interaction of multiple factors like sky luminosity and viewing angles, while preserving their original shape. In this paper, we propose a multilinear principal component analysis (MPCA) algorithm for target recognition in SAR images. First, we form a high order tensor with the training image set and we apply the higher-order singular value decomposition (HOSVD) to reveal patterns and dependencies between images. The HOSVD of this training image tensor is also used for compressing the data and removing background noise. Then, a multilinear projection algorithm exploiting the calculated HOSVD is used to classify an unknown target in a SAR image. This multilinear projection that leads to a nonlinear optimization problem is carried out in an iterative way by applying the alternate least squares (ALS) algorithm which solves a linear projection subproblem at each iteration. The estimated feature vector associated with the mode-class is then used for recognition. Tests with a true SAR image database illustrate very good classification performance of the proposed MPCA-based method while providing a very high compression rate.

INTRODUCTION

Supervised subspace-based classification is a classical approach for pattern recognition. Traditional linear subspace methods like principal component analysis (PCA) or linear discriminant analysis (LDA) require to reshape images into high-dimensional vectors. Then, vectorized images belonging to the same class of objects to classify are ranged into a matrix, and PCA or LDA are applied to determine the basis vectors that span each class. This vectorization breaks the natural structure and correlation in the original image set. Moreover, with linear approaches only single-factor variations are permitted in the image database. During the last decade, several multilinear subspace methods have been proposed for generalizing linear methods, as it is the case of multilinear principal component analysis (MPCA), multilinear independent component analysis (MICA) and multilinear discriminant analysis (MDA) used for face recognition ( [START_REF] Vasilescu | Terzopulos : Multilinear projection for appearance-based recognition in the tensor framework[END_REF], [START_REF] Vasilescu | Multilinear independent component analysis[END_REF], [START_REF] Yan | Multilinear discriminant analysis for face recognition[END_REF]), handwritten digit classification ( [START_REF] Savas | Handwritten digit classification using higher order singular value decomposition[END_REF]), or gait recognition ( [START_REF] Lu | Venetsanopoulos : MPCA -Multilinear principal component analysis of tensor objects[END_REF], [START_REF] Tao | General tensor discriminant analysis and Gabor features for gait recognition[END_REF]). These multilinear methods take all the variation factors of the training image database into account by considering it as a high order tensor and determining multiple interrelated subspaces by means of the higher order singular value decomposition (HOSVD) ( [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF]).

In this paper, we consider the problem of target classification in synthetic aperture radar (SAR) images. Such images are very noisy due to speckle noise. Moreover, unlike optical images, SAR images of a same target observed from different viewing angles are characterized by great variations in appearance, which makes the target classification problem non trivial. Usually, in supervised classification, the test images are expected to belong to predefined training classes. In practical situations, especially for military applications, some test images do not contain objects belonging to learned classes. In this case, two additional classes must be considered : the rejection class and the confusion class. Unlearned targets are labelled into the rejection class while the confusion class is used when the classifier is not able to decide between several classes. The rest of the paper is organized as follows. In Section II, we recall some definitions relative to tensors. Section III presents the MPCA-based algorithm including training and testing phases of the classification process. A link with two existing MPCA-based classifiers is also established. In Section IV, we show how a SAR image database can be encoded as a fourth-order tensor, and we present some experimental results obtained with true SAR images. In Section V, the data compression ability of our approach is illustrated. Finally, the paper is concluded with some perspective for future work. Notations : vectors and matrices are represented by boldface lower case (x) and boldface capital (X) letters, respectively, whereas tensors are denoted by blackboard capital letters (X). Rows and columns of matrices are denoted using the matlab notation ; for example, the i-th row of X is denoted X(i, :).

TENSOR ANALYSIS

In this section, we recall some definitions relative to tensors and the HOSVD. More details can be found in [START_REF] Favier | Tensor-based methods for system identification[END_REF].

Definitions

A tensor X of order N can be viewed as an N-way array, of dimensions I1×I2×. . .×IN , each entry xi 1 i 2 ...i N being indexed by means of N indices with 1 ≤ in ≤ In. Each index is associated with a way, also called a mode. The mode-n vectors of X ∈ ℜ I 1 ×I 2 ×...×I N are the In-dimensional vectors obtained by varying the index in while keeping the other indices fixed. The mode-n matricization of X gives the unfolded matrix X (n) ∈ ℜ In×I N ...I n+1 I n-1 ...I 1 whose columns are the mode-n vectors. The Frobenius norm of a real tensor X is given by :

X 2 F = I 1 i 1 =1 I 2 i 2 =1
. . .

I N i N =1 x 2 i 1 ...i N (1)
.

The mode-n product of a tensor X ∈ ℜ I 1 ×...×In×...×I N with a matrix A ∈ ℜ Jn×In gives a tensor Y ∈ ℜ I 1 ×...×Jn×...×I N whose entries are computed by :

yi 1 ...i n-1 jni n+1 ...i N = In in=1 xi 1 ...i N aj nin (2)
The mode-n product, written in tensor notation as Y = X ×n A, can be expressed in terms of unfolded matrices as

Y (n) = AX (n) .

Higher order singular value decomposition (HOSVD)

The HOSVD can be viewed as a high order generalization of the matrix SVD which orthogonalizes the column spaces of the N unfolded matrices X (n) , n = 1, . . . , N . Such an HOSVD allows to write the tensor X as ( [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF]) :

X = S ×1 U1 ×2 U2 . . . ×N UN (3)
where the matrices Un ∈ ℜ In×In , n = 1, . . . , N , are orthogonal. The core tensor S ∈ ℜ I 1 ×...×I N defines the interactions between the mode-n matrices Un whose columns are orthonormal vectors spanning the column space of X (n) . Frobenius norm obtained in fixing one mode of the core tensor S are the singular values of the tensor X : σ (in,i) = Si n=i F .

MPCA-BASED TARGET RECOGNITION

We use MPCA as a supervised algorithm for classification. The training phase consists in forming an (N + 3) th -order tensor with all images of the database and computing its HOSVD in order to reveal interesting pattern dependencies in the database images. Then, a test image to be classified is projected onto the (N+1) subspaces associated with the first (N+1) modes. HOSVD of this tensor can be written as :

Training phase

A
D = S ×1 U1 × . . . ×N UN ×N+1 U k ×N+2 Ux ×N+3 Uy (4)
Each image Di 1 ,...,in,i k ∈ ℜ Y ×X belonging to the training database can be written using the HOSVD as follows :

Di 1 ,...,in,i k = S ×1 U1(i1, :) . . . ×N UN (iN , :) ×N+1 U k (i k , :) ×N+2 Ux ×N+3 Uy (5)
Columns of U k are singular vectors characterizing energy in the class space. Each row of U k is related to one specific class and generates, through the core tensor S, all the images of the i th k class.

Testing phase

Let us consider a test image Dtest. This image can be decomposed using the HOSVD of the training tensor D as :

Dtest = S ×1 v1 . . . ×N vN ×N+1 v k ×N+2 Ux ×N+3 Uy (6)
where v1, . . . , vN and v k are unknown row vectors of respective lengths I1, . . . , IN , I k , to be optimized. The optimization problem consists in minimizing the following Frobenius norm under an unit norm constraint on each optimized vector :

v1, . . . , vN , vk = argmin v 1 ,...,v N ,v k ||Dtest -S ×1 v1 . . . × N v N × N +1 v k × N +2 Ux × N +3 Uy|| 2 F (7)
This simultaneous minimization with respect to v1, . . . , vN and v k leads to a nonlinear optimization problem that can be solved in a suboptimal way by applying the alternate least squares (ALS) algorithm, which amounts to solve a linear projection subproblem at each iteration. Each subproblem is linked to the minimization of a conditional LS cost function associated with a different vectorization of Eq. ( 6) that can be rewritten in the equivalent element-wise form :

dyx = I 1 i 1 =1 . . . I N i N =1 I k i k =1 Ix ix=1 Iy iy =1 si 1 ...i N i k ixiy v1(i1) . . . v N (i N )v k (i k )ux(x, ix)uy(y, iy) (8)
Stacking the rows of the image Dtest ∈ ℜ Y ×X to form the row vector dtest ∈ ℜ 1×Y X , we get the N+1 following vectorized forms of Eq. ( 6) :

dtest = v1S (1) (Uy ⊗ Ux ⊗ v k ⊗ vN ⊗ . . . ⊗ v2) T = . . . = vN S (N ) (Uy ⊗ Ux ⊗ v k ⊗ vN-1 ⊗ . . . ⊗ v1) T = v k S (N +1) (Uy ⊗ Ux ⊗ vN ⊗ . . . ⊗ v1) T
where ⊗ denotes the Kronecker product and S (n) , for n = 1, . . . , N + 1, is the mode-n matrix representation of the core tensor S. Each one of these equations can be solved in the LS sense, with respect to one vector factor, conditionally to the knowledge of the N other vector factors, this knowledge being provided first by the initialization and then by estimates obtained at previous iterations. This ALS-based algorithm for computing the multilinear projection is summarized in Table 1 where it and (.) † denote, respectively, the iteration number and the Moore-Penrose matrix pseudo-inverse.

1. Initialization v(0) 2 , . . . , v(0) N , v(0) k , it = 0 2. Alternate computation v(it+1) 1 = d test (S (1) (Uy ⊗ Ux ⊗ v(it) k ⊗ v(it) N . . . ⊗ v(it) 2 ) T ) † v(it+1) 1 ← v(it+1) 1 / v(it+1) 1 . . . v(it+1) N = d test (S (N ) (Uy ⊗ Ux ⊗ v(it) k ⊗ v(it+1) N -1 ⊗ . . . ⊗ v(it+1) 1 ) T ) † v(it+1) N ← v(it+1) N / v(it+1) N v(it+1) k = d test (S (N +1) (Uy ⊗ Ux ⊗ v(it+1) N ⊗ . . . ⊗ v(it+1) 1 ) T ) † v(it+1) k ← v(it+1) k / v(it+1) k

Return to step 2 until convergence

Table 1. ALS-based multilinear projection

The computation loop is repeated until the difference between Dtest and the test image reconstructed using ( 6) with (v1, . . . , vN , v k ) replaced by their estimated values, becomes smaller than a predefined threshold. The main advantage of this algorithm is its simplicity. However, its convergence is strongly dependent on the initialization. To improve convergence, we propose to use as initial values v(0) k the row vectors U k (i k , :), with i k = 1, . . . , I k , of the mode-N+1 matrix factor of the HOSVD defined in [START_REF] Savas | Handwritten digit classification using higher order singular value decomposition[END_REF]. The image Dtest is labelled as class i test k such as :

i test k = argmin i k vk -U k (i k , :) 2 F (9)
Once recognition carried out, all other factors of Dtest can be estimated as :

i test n = argmin in vn -Un(in, :) 2 F , n = 1, . . . , N (10)

Comparison with two other MPCA-based recognition methods

Our approach can be viewed as a generalization of two existing MPCA-based recognition methods. In the case of fourth-order tensors (N = 1), the I k LS solutions of ( 7) obtained for v k = U k (i k , :

), i k = 1, . . . , I k , can be interpreted as the projections of the test image Dtest onto I k sets of basis matrices {A

(i k )
i 1 , i1 = 1, . . . , I1} characterizing the I k classes. The classification criterion can then be rewritten as :

i test k = argmin i k min v 1 Dtest -S ×1 v1 ×2 U k (i k , :) ×3 Ux ×4 Uy 2 F = argmin i k min v 1 Dtest - I 1 i 1 =1 v1(i1)A (i k ) i 1 2 F with A (i k ) i 1 = S(i1, :, :, :) ×2 U k (i k , :) ×3 Ux ×4 Uy. The basis ma- trices A (i k ) i 1
are the same as the ones defined in [START_REF] Savas | Handwritten digit classification using higher order singular value decomposition[END_REF]. Our approach can also be viewed as an unfolded matrix formulation of the algorithm proposed in [START_REF] Vasilescu | Terzopulos : Multilinear projection for appearance-based recognition in the tensor framework[END_REF] that consists in solving Eq.( 6) as follows :

R = v1 • . . . • vN • v k = T † × Dtest (11)
with T = S ×N+2 Ux ×N+3 Uy. Instead of computing the vectors v1, . . . , vN and v k by means of the ALS algorithm, the multiliner projection problem is solved in computing the best-rank(1,. . . ,1) approximation of the tensor R. However, this approach needs to compute the inverse tensor T † which is not clearly defined.

Confusion and rejection classes

When recognition is carried out using (9), we use the distance

R(i k ) = vk -U k (i k , :) 2 F .
Confusion and rejection classes can be incorporated by introducing two thresholds : the confusion threshold ∆c and the rejection threshold

Sr. If R(i k ) -R(i test k ) < ∆c for all i k ∈ {1, . . . , I k } with i k = i test k
, the decision between different classes can be considered as confused. If R(i k ) > Sr for all i k ∈ {1, . . . , I k }, it can be concluded that the unknown target does not belong to any class of the training set. Confusion and rejection thresholds are free parameters, chosen by the operator according to the robustness needed for the classification. Increased values of ∆c and Sr imply a decrease of the classification error rate but also of the recognition rate.

APPLICATION TO TARGET RECOGNITION IN SAR IMAGES

SAR image database tensor

A SAR image database is composed of a set of images of targets with different aspect angles and grazing angles. Generally, images at one grazing angle are chosen for the training set while images at another grazing angle are chosen for the testing set. The aspect angle is considered as a variation factor. In this case, MPCA is applied to a fourth-order tensor characterized by two pixel modes, one aspect angle mode and one target class mode. Fig. 2 presents a fourth-order tensor of a SAR database. The HOSVD of this SAR image tensor can be written as :

D = S ×1 Uaspect angle ×2 Utarget ×3 Ux ×4 Uy (12)
Fig. Rejection performance were evaluated using a target which was not included in the training database. Images of the target 2S1 available in the MSTAR database were considered in the testing phase. With the same thresholds as before, we obtained a rejection rate of 61% for this unlabelled target.

DATA COMPRESSION

A tensor-based approach provides a better compression rate than a matrix SVD-based approach. In the matrix case, a low rank approximation is obtained in truncating the SVD. In the same way, a low rank approximation of a tensor can be obtained as a truncated HOSVD, i.e. by discarding the least significant singular values of each unfolded matrix representation of the tensor. Preserving the shape of the data enables a better compression than with a linear approach. For example, after background masking processing, SAR images are sparse because the detection algorithm has removed most of pixels belonging to the clutter. Truncated HOSVD can remove all those null pixels from the data. Fig. 3 shows the recognition rate for different compression rates obtained with the MPCA approach and the PCA approach using matrix SVD with vectorisation of database images. In this figure, a 80% compression rate means that we used only 20% of the data volume of the training set to achieve the recognition. As we can see, the MPCA approach allows to improve the recognition rate, comparatively with the PCA approach, from a compression rate of 60%.

CONCLUSION

In this paper, a MPCA-based approach has been proposed for automatic target recognition in SAR images. This approach allows to solve a multimodal target recognition problem by considering an image database as a fourth-order tensor. Some simulation results obtained with the MSTAR database illustrate the good performance of the proposed MPCA-based classification method, in terms of both classification and compression rates.

Fig. 1 .

 1 Fig. 1. SAR image of a target in the MSTAR database

  training set is composed of I k classes of images characterized by N different variation factors. These factors correspond to the first N modes of the training tensor. Let us consider a database composed of images of size Y × X belonging to I k classes characterized by N modes of respective dimensions I1, . . . , IN (we assume that there is the same number of images per class in the training database). Each image of the database is defined by the coordinate set (i1, . . . , iN , i k ) with in = 1, . . . , In, n = 1, . . . , N and i k = 1, . . . , I k . The total number of images in the database is given by ( N n=1 In)I k . All the images are ranged into a (N + 3) th -order tensor D of dimension I1 . . . × IN × I k × X × Y where the last two modes are pixel modes and the (N + 1) th -mode is the mode-class.

Fig. 3 .

 3 Fig. 3. Recognition rate at different compression rates obtained with MPCA and PCA

Table 2 .

 2 2. Fourth-order tensor of MSTAR database images 4.2. Experimental results Confusion threshold ∆c and rejection threshold Sr were chosen empirically to get an apriori fixed recognition rate .

	Some experiments were carried out using the MSTAR (Moving Sta-
	tionary Target Acquisition and Recognition) database composed of
	various images of ten types of targets, with the aspect angle varying
	between 0˚and 360˚. Each image corresponds to a target at two
	different grazing angles : 15˚and 17˚. In this work, we used a subset
	composed of five types of targets : BMP2, BRDM2, D7, T62 and
	T72. Images at 15˚grazing angle were chosen for the training set
	while images at 17˚grazing angle were chosen for the testing set. For
	both training and testing, we selected a set of 180 images for each
	target, with an approximative 2˚aspect angle step. After background
	masking preprocessing ([9]), images are of dimension 30 × 50. So
	MPCA was applied to the fourth-order training tensor of dimension
	5 × 180 × 30 × 50. Recognition (Rc), confusion (Cf) and rejection
	(Rj) rates obtained after five iterations of the ALS algorithm are
	given in Target	Rc (in %) Cf (in %) Rj (in %)
	BMP2	83,0	5,4	6,1
	BRDM2	89,6	4,3	4,5
	D7	95,0	1,6	2,4
	T62	81,9	6,2	8,1
	T72	81,4	5,6	7,9
	Average	86,1	4,6	5,8

Table 2 .

 2 Recognition, confusion and rejection rates


Ferdaouss Mattoussi

Vincent Roca
email: vincent.roca@inria.fr

Bessem Sayadi
email: bessem.sayadi@alcatel-lucent.com

Complexity Comparison of the Use

Keywords: AL-FEC, Reed-Solomon, Vandermonde matrix, Hankel matrix

published or not. The documents may come

INTRODUCTION

Computer communications heavily rely on FEC codes to cope with data losses (e.g. IP datagram losses caused by congested routers in the Internet) and/or errors (e.g. during frame transmissions on a physical link). In particular systematic and Maximum Distance Separable (MDS) codes are rather attractive [START_REF] Mcwilliams | The theory of error correcting codes[END_REF] for two reasons: first of all, because they achieve the maximum possible minimum distance for given length and dimension, which means that they feature optimal correction capabilities; but also because they are systematic, i.e. the information data is a part of the encoded data. In this work we focus on the erasure channel (rather than on the error channel). These FEC codes, that deal with data losses, are traditionally called Application-Level FEC (AL-FEC) codes since This work was supported by the ANR-09-VERS-019-02 grant (ARSSO project) and by the Inria -Alcatel Lucent Bell Labs joint laboratory. they are found in the upper transmission layers, often within the transport protocol or the application. However our code construction results could be applied in a similar way to codes for an error channel.

Reed Solomon (RS) codes are MDS erasure codes that can be put into a systematic form. Therefore their systematic generator matrix, G, can be written as:

G = [I k |A k,n-k ],
where I k is the identity matrix of order k, and A k,n-k represents the repair matrix of order k × (n -k). The code will be MDS if and only if every square sub-matrix of A is nonsingular [START_REF] Mcwilliams | The theory of error correcting codes[END_REF] [START_REF] Lacan | A construction of matrices with no singular square submatrices[END_REF].

In order to build this A matrix, it is of common practice to use Vandermonde matrices. However this approach is relatively costly as we will demonstrate. This is not an issue if the code is fixed, i.e. if its code dimension (k) and length (n) parameters are fixed and known in advance, since A can be pre-calculated in that case. For instance, when dealing with codes for the physical layer, the code is fixed and the codec implemented in hardware. But this assumption of a fixed code is no longer valid, in general, when dealing with the AL-FEC codes where the codec is usually a software component. In that case the {n, k} parameters are dynamically determined, when there is a need to instantiate an AL-FEC encoder or decoder. This is also the case with GLDPC-Staircase codes [START_REF] Mattoussi | Design of small rate, close to ideal, GLDPC-Staircase AL-FEC codes for the erasure channel[END_REF], a class of Generalized LDPC codes that use a special form of systematic Reed-Solomon codes as component codes (i.e. the codes based on Hankel matrices introduced in this work). For such applications that generate Reed-Solomon codes on demand, dynamically, there is a clear interest in reducing the generator (G) matrix creation complexity.

[5] introduces a construction method for systematic MDS erasure codes, based on two Vandermonde matrices, which is the usual approach. In this work we focus on an alternative way of constructing the generator matrix, using Hankel matrices [START_REF] Roth | On generator matrices of MDS codes[END_REF]. To the best of our knowledge, this is the first reference to this alternative way of designing systematic Reed-Solomon codes since their introduction in 1985 in [START_REF] Roth | On generator matrices of MDS codes[END_REF]. We detail in this work how this is possible, we explain what complexity gains are expected during the systematic generator matrix creation stage, and finally we give an account of experiments carried out, using a C language software codec, in order to assess the practical gains.

The paper is organized as follows. Section 2 details the construction methods for the Vandermonde and Hankel matrix variants. Then we compare their complexity in section 3. Finally, we conclude.

CONSTRUCTION METHODS OF SYSTEMATIC

REED-SOLOMON CODES OVER GF (Q)

Let us first introduce the construction method for systematic MDS erasure codes.

Generalities

Systematic RS codes feature a generator matrix, G, of the form:

G = [I k |A k,n-k ]
where A is a k × (n -k) matrix that does not contain any singular sub-matrix. Said differently, any square sub-matrix of A, formed from any i rows and any i columns of A, with i ∈ {1, • • • , min{k, n -k}}, is non singular. Therefore the construction of a systematic RS generator matrix with the MDS property is equivalent to finding an appropriate A matrix. In this section we first detail how Vandermonde matrices are used to that purpose, then we detail an alternative solution based on Hankel matrices.

Codes based on Vandermonde matrices

A Vandermonde matrix V (q, q) is defined by one vector of q distinct elements (a 1 , • • • , a q ) over GF (q), i.e. such that each a i , 1 ≤ i ≤ q, is an element of GF (q). A representation of the Vandermonde matrix, V = (a j-1 i ) i,j is:

V (q, q) =      1 a 1 • • • a q-1 1 1 a 2 • • • a q-1 2 . . . . . . . . . 1 a q • • • a q-1 q     
Vandermonde matrices defined over GF (q) can contain singular square sub-matrices [3][5], and an upper bound of the number of singular sub-matrices is given in [START_REF] Fimes | Estimation of the number of singular square submatrices of Vandermonde matrices defined over a finite field[END_REF] [START_REF] Shparlinski | On singularity of generalized Vandermonde matrices over finite fields[END_REF]. Consequently these matrices cannot be directly used to design MDS systematic codes over GF (q). However [START_REF] Lacan | A construction of matrices with no singular square submatrices[END_REF][5] introduce methods to use these matrices in order to build a systematic MDS RS generator matrix. Therefore, to obtain a systematic generator matrix G(k, n) (and therefore a code C(k, n)), the simplest solution consists in considering two matrices: the first one is the V (k, k) matrix formed by the first k columns of the second matrix V (k, n), defined as previously. Then we invert the first matrix and multiply this inverse by V (k, n). Clearly, the product V (k, k) -1 * V (k, n) contains the identity matrix I k on its first k columns, meaning that the first k encoding elements are equal to source elements. Besides, the resulting code features the MDS property. Therefore, the resulting systematic RS generator matrix based on Vandermonde matrix is equal to,

G = V (k, k) -1 * V (k, n) (1) = [I k |V (k, k) -1 * V (k, n -k)] (2) = [I k |A(k, n -k)] (3)
This construction can be optimized by taking the representative vector of Vandermonde matrix (a 1 , • • • , a k ) equal to (1, a, a 2 , ..., a k-1 ) where a is an element of GF (q) with order k. Since the Vandermonde matrix is now defined by one element only (instead of q distinct elements), this matrix is denoted by V (a) and has the following form:

V (a) =          1 1 1 • • • 1 1 (a 1 ) 1 (a 1 ) 2 • • • (a 1 ) n-1 1 (a 2 ) 1 (a 2 ) 2 • • • (a 2 ) n-1 1 (a 3 ) 1 (a 3 ) 2 • • • (a 3 ) n-1 . . . . . . . . . . . . 1 (a k-1 ) 1 (a k-1 ) 2 • • • (a k-1 ) n-1         
This choice has two objectives: first, the inversion of [START_REF] Lacan | A construction of matrices with no singular square submatrices[END_REF]; secondly the matrix-vector multiplication between V (a) and V (a -1 ) can be performed very efficiently [START_REF] Gohberg | Fast algorithms with preprocessing for matrix-vector multiplication problems[END_REF].

V (a) is easier since (V (a)) -1 = 1 k × V (a -1 )

Codes based on Hankel matrices

Let us now focus on an alternative way of building systematic MDS generator matrix using Hankel matrix, a solution that has never been studied (as far as we can tell) since their introduction in [START_REF] Roth | On generator matrices of MDS codes[END_REF]. Hankel matrices are square matrices whose values are constant along the ascending diagonals. The construction method is based on the creation of the maximal triangular array, B q , defined over GF (q), whose coefficients are constant along diagonals in a Hankel matrix fashion:

B q = b 1 b 2 b 3 • • • b q-2 b q-1 b 2 b 3 . • • • b q-1 b 3 . . • • • . . . . . b q-1 b q-2 b q-1 b q-1
This triangular array has a "pure" Hankel matrix. The coefficients of the triangular array are equal to: b i = 1 1-y i , where 1 ≤ i ≤ q -1, y is an arbitrary primitive element of GF (q) and y i is computed over GF (q). By using these coefficients, B q has the property that every square sub-matrix is non-singular [START_REF] Roth | On generator matrices of MDS codes[END_REF].

Next step consists in extracting from the upper triangle of B q a rectangular sub-matrix A of size k × (n -k) (this is always feasible since k ≤ n < q). This matrix has of course the desired property that any square sub-matrix is nonsingular. Therefore A(k, n -k) can then be used to construct a generator matrix of a systematic RS code.

The following triangular array, T q , is a particular case:

T q = 1 1 1 1 • • • 1 1 1 1 b 1 b 2 b 3 • • • b q-3 b q-2 1 b 2 b 3 . • • • b q-2 1 . . • • • . . . • • • . . b q-2 1 b q-2 1
T q has a "quasi" Hankel matrix form (instead of "pure" form as with B q ). It is built by removing b q-1 to B q and adding an additional first row and column full of 1 entries. One can check that T q does not contain any singular square submatrix as well [START_REF] Roth | On generator matrices of MDS codes[END_REF]. Therefore one can extract an appropriate A(k, n -k) matrix from the upper triangle of T q as well in order to build the generator matrix of a systematic RS code. This second version has the nice property that the first repair symbol is also equal to the direct XOR sum of the source symbols (this is a key point of our GLDPC-Staircase codes, as detailed in [START_REF] Mattoussi | Design of small rate, close to ideal, GLDPC-Staircase AL-FEC codes for the erasure channel[END_REF]).

We therefore have two methods to build a generator matrix G = [I k |A k,n-k ] of a systematic MDS RS code: by extracting A(k, n -k) from B q ("pure" Hankel matrix form) or from T q ("quasi" Hankel matrix form). With these techniques, the systematic generator matrix is directly obtained by a trivial concatenating operation, instead of having to invert a matrix and then perform matrix-vector multiplications as is the case with the Vandermonde solution. This is a major benefit when the code needs to be produced on-the-fly.

CODE CONSTRUCTION METHOD COMPLEXITY ANALYSIS

Performance evaluation environment

Let us now evaluate the generator matrix creation complexity, both in terms of the creation time and the number of elementary XOR operations. To that purpose, we are using a C language Reed-Solomon software codec for Vandermonde matrices, derived from L. Rizzo's well known codec [START_REF] Rizzo | Effective erasure codes for reliable computer communication protocols[END_REF]. This codec has been optimized and is freely distributed at: http://openfec.org/ We also derived a codec for Reed-Solomon based on Hankel matrices that only differs during the generator matrix creation stage. The remaining of the two codecs, as well as the testing application, are strictly identical which warrants fair comparisons. In both cases we focus on GF (2 8 ) codes since this is the most practical solution for software codecs: finite field elements are aligned on byte boundaries for easy transfers to/from memory buffers, and the finite field operations pre-computed tables have a small size that fits well in CPU caches and/or RAM.

Note that we only consider the "pure" Hankel matrix variant, B q . Using the "quasi" Hankel matrix variant, T q , would slightly simplify the encoding (and perhaps decoding) steps, the first repair symbol being equal to a simple XOR sum of the source symbols.

Finally, all the initialization, encoding and decoding speeds are evaluated on a MacBookPro laptop, featuring a 2.4 GHz Intel Core i5 CPU, and running MacOS 10.6.7.

Generator matrix creation time

As explained in section 2.2, with the Vandermonde approach, the complexity of building G corresponds to the complexity of inverting V k,k and multiplying V -1 k,k by V k,n-k . On the opposite, with the Hankel approach, once the B q (or T q with "quasi" Hankel variant) coefficients are computed, a simple concatenation is sufficient. In order to appreciate the practical consequences, we have measured these times. Figure 1 illustrates the major gains permitted by the use of Hankel matrices, in terms of creation times. If the systematic generator matrix creation times increase exponentially with RS(3k, k) codes based on Vandermonde matrices as k increases, the progression is linear with their Hankel equivalent. This is confirmed in Table 1 that evaluates the processing time gains made possible by the use of the Hankel approach: the gains vary between 3.0 and 51.87.

Generator matrix creation complexity

Let us now consider the number of operations required to build a systematic generator matrix of RS codes. With Vandermonde matrices, the creation of the systematic generator matrix requires finite field additions and multiplications over GF (q) in order to perform matrix inversion and multiplication. Finite field additions consist in XORing the two values. Finite field multiplications are more complex, requiring in general a log table lookup, an addition operation and an exponentiation table lookup to determine the result. However, with GF (2 8 ), multiplications can be pre-calculated and the result stored in a table of size 255 × 255. This is a common optimization with software codecs and this is how the initial Reed-Solomon codec was implemented. With this optimization, multiplying two elements of GF (2 8 ) consists in accessing the right element of this pre-calculated table. Since this is a simple operation, the complexity evaluation only considers the number of XOR operations and ignores the number of multiplications.

As a result, for an RS(n, k) code with a Vandermonde base matrix, the systematic generator matrix creation consists of :

• the initialization of V (a) which requires k(n -1) read accesses to pre-calculated tables;

• a (k × k) matrix inversion, which requires 2k(k -1) + (k -1) + (k-1)(k-2)

2

XOR operations, and 0.5(k -1)(k -2) + 2k(k -1) + 2k 2 read accesses to precalculated tables;

• a (k × k) -(k × n -k) matrix multiplication, which requires k(n-k)(k-1)
XOR operations, and k 2 (n-k) read accesses to pre-calculated tables;

With Hankel matrices, the creation of the systematic generator matrix essentially consists in calculating the b i = 1 1-y i coefficients, with 1 ≤ i ≤ n -1. Since the same values are used along the diagonals, we only calculate the n coefficients of the first line, which requires n XOR operations. In addition, the processing requires 2n + k(n -k) read accesses to pre-calculated tables.

We see that the Hankel approach outperforms the Vandermonde approach both in terms of the number of XOR operations and read accesses to tables. Table 2 shows the statistics obtained, counting the actual number of operations in the two codecs. The results confirm the benefit of the Hankel matrix approach, with speedups similar to that achieved in Table 1 when measuring time. The small difference is due to the simplification performed when counting operations: we do not include write operations, loop control operations, function call overheads, modulo calculations, and we assign the same cost factor to XOR and table access operations. A more detailed complexity analysis is feasible, but we consider that the accuracy achieved is sufficient to give an account of the behavior observed.

Impacts on the global encoding and decoding times

Let us now try to answer to another question: what are the impacts of G creation on the total encoding or decoding times? Due to our assumptions, the systematic generator matrix creation time is included in the encoding (resp. decoding) times. Figures 2 show the relative gains made possible by the use of Hankel matrices on the encoding and decoding times, for several Reed-Solomon codes. These tests have been carried out with symbols of size 4 bytes each, i.e. the same operations are performed on each byte of the symbol (since erasures take place at the symbol level in case of Reed-Solomon codes for the erasure channel, see [START_REF] Lacan | Reed-Solomon error correction scheme[END_REF]). We see there is a clear gain in using Hankel matrices, even if this gain depends on the actual code dimension and length being used.

However it should be noted that a symbol size of 4 bytes is rather small in case of AL-FEC codes. Symbols, that form the payload of UDP/IP datagrams, are more often on the order of a few hundreds of bytes. In that case, the relative benefit of reducing the matrix creation time would be reduced since the relative importance of data manipulations on symbols increases. The results of Figures 2 should therefore be regarded as upper bounds of the gains made possible by the use of Hankel matrices during encoding and decoding with many (but not necessarily all) AL-FEC codes.

CONCLUSIONS

Building a systematic MDS generator matrix for RS codes over GF(q) is equivalent to determining the A matrix of G = [I k |A k,n-k ], with the property that any square sub-matrix of A must be non-singular. In this paper, in addition to the traditional method for building A, based on Vandermonde matrices, we have introduced another approach, based on Hankel matrices. To the best of our knowledge, this is the first mention to this alternative way of designing systematic Reed-Solomon codes since their introduction in 1985, in [START_REF] Roth | On generator matrices of MDS codes[END_REF]. We proved, both theoretically and experimentally, that this alternative solution is an order of magnitude simpler than the Vandermonde approach. The A sub-matrix of the generator matrix is produced immediately, instead of having to invert a matrix and multiplying this inverted matrix with another one. Major speedups, for instance up to 157, can be achieved thanks to the Hankel approach with our software C language Hankel Reed-Solomon codec, derived from a wellknown Vandermonde Reed-Solomon codec for the erasure channel. This result is of high importance for all situations where a software RS(n, k) codec needs to generate on the fly an RS code with appropriate dimension and length values.

  k) Hankel RS codes (3k, k) Vandermonde RS codes (a) RS(3k,k) codes.

Fig. 1 .

 1 Fig. 1. Systematic generator matrix creation times.

  k) Hankel RS codes (3k, k) Vandermonde RS codes (b) Decoding time

Fig. 2 .

 2 Fig. 2. Comparison between (3k,k) Vandermonde and Hankel Reed-Solomon codes during encoding and decoding.

Table 1 .

 1 Generator matrix creation times and performance gains made possible by the Hankel approach.

		(30,10)	(250,50)	(250,100)	(250,125)
	Vandermonde	0.007 ms	0.620 ms	2.577 ms	3.143 ms
	Hankel	0.002 ms	0.011 ms	0.020 ms	0.020 ms
	Ratio	3.5	56.36	128.85	157.15

Table 2 .

 2 Generator matrix creation complexity (number of XOR and table access (TA) operations) and performance gains made possible by the Hankel approach).

		(30,10)	(250,50)	(250,100)	(250,125)
	Vandermonde	2,225 XOR	506,125 XOR	1,524,750 XOR	1,991,875 XOR
		2,706 TA	523,526 TA	1,569,551 TA	2,054,126 TA
	Total # oper.	4,931 op.	1,029,651 op.	3,094,301 op.	4,046,001 op.
	Hankel	30 XOR	250 XOR	250 XOR	250 XOR
		260 TA	10,500 TA	15,500 TA	16,125 TA
	Total # oper.	290 op.	10,750 op.	15,750 op.	16,375 op.
	Ratio	17.0	95.8	196.5	247.1