Christophe Hurter
email: christophe.hurter@enac.fr

Benjamin R Cowan
email: b.r.cowan@cs.bham.ac.uk

Audrey Girouard
email: audrey_girouard@carleton.ca

Nathalie Henry Riche

Active Progress Bar: Aiding the switch to temporary activities

Keywords: Progress bars, participatory design, frustration, task switching, user satisfaction

Can we design an interface to help people make use of the idle time spent looking at progress bars? We propose to augment progress bars with user-controlled functionalities facilitating the switch to temporary activities. We propose a taxonomy of waiting period contexts and possible temporary tasks, then report on participatory design sessions, and a follow-up survey. Finally we describe an early prototype of active progress bar and report a small controlled experiment used to identify the impact of the tool on primary task satisfaction. The findings suggest that Active Progress Bars lead to significantly higher satisfaction when compared to a control condition.

INTRODUCTION

Encountering a progress bar and waiting for computer-based tasks to finish in order to resume our primary task is common when working with computer systems. Many designs have been proposed to improve progress bars themselves yet little has been done to help users make better use of the waiting time. We propose that progress bars can be augmented with simple functionalities to facilitate a switch to a temporary secondary activity, and a smooth return to the primary activity so that these waits can become useful. Currently users develop their own strategies for dealing with this delay. They may stretch, make coffee, rest, or stay on the computer and manually switch to a temporary activity such as checking email, Facebook, or reviewing their to-do list. This often leads users to forget to return to the primary task or alternatively they may choose not to return. The completion of a secondary temporary activity when waiting in these experiences is likely to have a positive impact on the user experience of the primary task execution. The primary activity, its context and the duration of the wait may of course determine the type of temporary activities users engage in while the primary one is on hold. Context will also dictate the benefit -or danger -of switching to another activity. Users trying to stay focused on a single task may not want to switch, while others may welcome assistance in switching between tasks. Our goal with this research is to initially investigate possible user interface designs that would facilitate task switching when users welcome it and then begin to explore how such a design would impact on primary task satisfaction. The paper focuses on three stages of work related to the design of a progress bar to facilitate the use of waiting time. We firstly describe the related work on waiting when conducting tasks on computer systems and develop a taxonomy of aspects which need to be considered in designing a system to impact on waiting time. Secondly we describe the design process of Active Progress Bar, including participatory design sessions to gather ideas for design situations where such a tool could be used and what it could be used for, as well as the development and informal evaluation of an early prototype by the authors. The paper then starts to investigate the impact of Active Progress Bar on users' primary task satisfaction in a small pilot study. It explores how aspects highlighted in previous activities such as the passiveness of the secondary task supplied by Active Progress Bar and the context of primary task affect Active Progress Bar's impact on primary task satisfaction.

Related Work

Users are impatient [START_REF] Zhang | Human-Computer Interaction and Management Information Systems: Foundations[END_REF]. While there have been improvements in hardware and software leading to much faster download and processing time in all applications, files sizes and processing complexity have also increased. Designers strive to minimize the need for progress bars (e.g. using video streaming instead of downloading, or displaying partial visual content prior to the whole file being downloaded [START_REF] Harrison | Evaluation of progressive image loading schemes[END_REF]), but waiting and progress bars are still commonly seen as we deal with network congestion or farm out processing and storage to remote locations. Early studies have shown that users prefer having progress indicators [START_REF] Myers | The importance of percent-done progress indicators for computer-human interfaces[END_REF]. Users, when given graphical dynamic progress indicators rather than static ("Please wait"), blinking, or numeric (number of seconds left) messages also report higher satisfaction and shorter perceived times to completion [START_REF] Meyer | Duration estimates and users' preferences in human-computer interaction[END_REF]. Many designs have attempted to alter users' perception of time [START_REF] Harrison | Rethinking the progress bar[END_REF], for example a progress bar with animated ribbing that moves backwards in a decelerating manner was found to reduce the perceived wait time by 11% compared to a more traditional design [START_REF] Harrison | Faster progress bars: manipulating perceived duration with visual augmentations[END_REF]. Our goal is not to make the wait time appear shorter (when in fact it is not), but to try to make better use of the waiting time, something that has not been explored.

Task switching comes at a cost [START_REF] Monsell | Task switching[END_REF]. Psychologists have studied the experience of "being in the flow" [START_REF] Csikszentmihalyi | Flow: The Psychology of Optimal Experience[END_REF] which lead to design recommendations and examples [START_REF] Bederson | Interfaces for staying in the flow[END_REF][START_REF] Shneiderman | Maintaining concentration to achieve task completion[END_REF] for the design of applications. Researchers keep trying to better understand the effects of interruptions which are typically considered a significant nuisance (e.g [START_REF] Gillie | What makes interruptions disruptive? A study of length, similarity, and complexity[END_REF][START_REF] Czerwinski | A diary study of task switching and interruptions[END_REF]) and some tools have been proposed to facilitate the return to the primary task after interruption [START_REF] Smith | GroupBar: The TaskBar Evolved[END_REF][START_REF] Dragunov | TaskTracer: a desktop environment to support multi-tasking knowledge workers[END_REF][START_REF] Matthews | Clipping lists and change borders: improving multitasking efficiency with peripheral information design[END_REF]. Interruptions are usually described as something that is not under users' control (e.g. a phone call, somebody walking in the office), while a progress bar is generally the result of users' actions and may be considered a break and not an interruption. With active progress bars users can be given control over the level of interruption they want from the primary activity by this break.

CHARACTERIZING WAITING & PROGRESS BARS

To guide our exploration of active toolbars we first defined a set of dimensions describing waiting and progress bars. From our results and previous work in the interruption literature [START_REF] Iqbal | Oasis: A framework for linking notification delivery to the perceptual structure of goal-directed tasks[END_REF][START_REF] Dabbish | Why do I keep interrupting myself?: environment, habit and self-interruption[END_REF], we present a simple taxonomy iteratively refined from analysing the data from our participatory design sessions in Section 3. We identified three main temporal components: (1) the primary activity the user is performing before the progress bar appears; (2) the waiting period; and (3) the temporary activity the user can perform while waiting. For each component, we identified multiple dimensions that are crucial to these activities.

Primary Activities

This is the activity users were performing before the waiting period.

Primary Activity-Context

We identify three types of contexts: work, entertainment, and idle. We use context as a dimension and not the software currently used, as this might vary per user. For instance, checking emails might be considered work if done by a lawyer during a weekday, but might be entertainment for a teen user. Similarly, the use of Adobe Photoshop by an amateur photographer is recreational (entertainment), but not for a graphic designer at work. The third context -idle -refers to situations when the user was not performing any specific task before the start of the progress bar (such as when booting up a computer.).

Primary Activity-Stage

When the waiting occurs, the primary activity can be in one of four stages: (1) at the start of the activity, such as when loading a program; (2) during the activity, when performing a specific action during an activity such as performing some data transformation; (3) at the end of the activity, such as when logging off a program; and finally (4) in a peripheral activity, such as when downloading a file that will be required further along in the current primary activity.

Waiting Period

We characterize the waiting period during which the user is shown a progress bar with three dimensions.

Waiting Period-Control of Initiation

The start of the waiting period can be under user control or not. Users decide when to compile their code or save large documents as PDFs, but the waiting may also be triggered automatically during the primary activity, such as when a large document is saved automatically. Users may also be able to delay the start of the waiting period (e.g. when delaying a virus scan or installation of updates).

Waiting Period-Duration Predictability

The waiting period can be either determined or undetermined.

Determined waiting periods correspond to situations where an algorithm can estimate the length of the wait. Often the duration of the waiting period cannot be determined. It is often expressed in the interface by a rotating wheel or hourglass instead of a progress bar.

Waiting Period-Duration

Duration of the waiting period can also vary significantly. To simplify, we empirically distinguish four ranges: the waiting can be instant -less than 1 second, short -less than 5 seconds, mediumbetween 5 and 20 seconds, or long -more than 20 seconds. An example of an instant wait is saving a small file. An example of a short wait can be loading a modest webpage or the automatic save of a very large document. Launching a program like Adobe Photoshop might be a medium wait, while installing new software is a long wait. In this paper, we will discuss short, medium and long waits because they are more prominent to the user and influence the decision about what to do during this period. Note that recent work on progress bars only focused on short or medium wait times (5s for [START_REF] Harrison | Rethinking the progress bar[END_REF]; [START_REF] Harrison | Faster progress bars: manipulating perceived duration with visual augmentations[END_REF] and 12s for [START_REF] Gronier | Etude des métaphores temporelles sur la perception du temps d'attente[END_REF]).

Waiting Period-Control of Initiation

Finally, we also observed four states of notification of the progress during the waiting period. It can be discrete (e.g. number of seconds, if the end of the wait time is emphasized), continuous (percentage done), binary (icon or "please wait" message) or there can be no notification at all.

Temporary Activity

Finally, we characterize the type of activity performed during the waiting period.

Temporary Activity-Context

The temporary activity has a context with the same characteristics of the primary activity (work, entertainment or idle). However, the context of the temporary activity does not need to be identical to that of the initial activity. One could watch a short fun video (entertainment) while installing a statistical package (work). The idle context of a temporary activity refers to the user stopping all computer activity to stretch, get a snack or read a printed document.

Temporary Activity-Interaction

This dimension captures the level of involvement of the user in the temporary activity. The activity can be passive: an activity that does not require the user to perform any action, e.g. watching an animation or reading pieces of information. Or, the activity can be active and require users to interact with the computer, e.g. tagging a photo, browsing the web or playing games.

Temporary Activity-Determination of completion

The temporary activity may be finite or not. Finite activities have an identifiable end. Examples include adding a tag to a photo or updating one's Facebook status. Finite activities may include activities with multiple steps achieved over multiple waits (e.g. tagging photos). Non-finite activities do not have an explicit end. They may be best accomplished during an undetermined length of time. Examples are web browsing tasks or paper reading tasks.

DESIGN STAGE: PARTICIPATORY DESIGN

We conducted five participatory design sessions [START_REF] Sannino | Past Experiences and Recent Challenges in Participatory Design Research[END_REF] to better understand the experiences of users when they wait. We selected the groups (22 users total) through an iterative process. We started with two groups of computer scientists, based on the results of the preliminary questionnaire and in these, we reworked the taxonomy and identified professional groups more likely to shed light on the design space. Specifically, we had gathered from these initial sessions that downloading and editing pictures were common activities that required waiting, therefore we also selected a group of photographers to take part in the design sessions. We also identified that time and task management were likely to be important and that our design could have high relevance in a workplace scenario so we also recruited a group of managers. In each session, users were asked to identify and describe three typical waiting situations before brainstorming on activities they may want to conduct to improve how they spend their time waiting. The brainstorming was situated in up to five predefined use cases, and their own identified situations.

Participants

As stated we selected two groups of four computer scientists (CS) that included researchers and PhDs in computer science. Those two groups came from different institutions, one in the US and one in France; the third group of five participants had no formal information technology training (non-IT) but were regular computer users; the last groups consisted of four photographers and four managers. The latter three groups were conducted in the US. Table 1 details the participants.

Procedure

We first described the goal of the project and the structure of the session. Each participant filled in a questionnaire describing three situations where they waited when using a computer and ranked both the frequency of the waiting time and their frustration level for each. Then, they each read aloud their answers and summarized the situations on a shared whiteboard. During this phase, we encouraged all participants to share both their frustrating and pleasant waiting experiences and discussed the characteristics that made them particularly enjoyable or not.

In the next phase, the facilitator picked waiting situations either from a pre-made list of five use cases or from the whiteboard and asked participants to brainstorm possible solutions to improve the wait situation. Three of the use cases described primary activities: downloading pictures from a camera, rebooting a computer, compiling software; while two use cases suggested possible temporary activities to perform: managing one's time, and playing a social game. These use cases were developed to facilitate ideas in the design sessions and act as a context for participants. All ideas were noted on a second whiteboard and participants voted for their favourites. Finally participants worked in pairs to prototype an idea of their choice using pencils and paper. The final result was recorded using pictures and video.

Results

In this section, we report the results of our participatory design sessions and preliminary questionnaire. First we present the common waiting situations reported by our participants (3.3.1). Then, we describe the ideas designed by our participants to improve their waiting experience.

We grouped the multiple ideas we collected in six categories: how to avoid the waiting situations (3.3.2), how to stay in context (3.3.3), how to stay in the flow and perform related activities (3.3.4), how to get back to frequently performed activities (3.3.5), how to improve time management (3.3.6) and finally, how to enjoy the waiting period by taking a break (3.3.7).

Common Waiting Situations

Table 2 reports on common situations reported by participants, their average occurrence per week, the average wait reported, and the associated frustration level.

Situations that received the highest frustration level from a single participant (6 or 7 on a 10 point scale) include video rendering, data backup, installing software, downloading large files, and loading software. On the other hand, the waiting situations with the lowest level of frustration (rating of 1 on the 1-10 frustration scale) include booking a flight, booting the computer, loading email.

Users also reported a great diversity of situations, such as ripping and burning CDs, connecting to Wifi, syncing a phone, streaming web content, doing a backup, booking a flight, rendering video and logging off, although those situations were each reported only once.

Common Waiting Situations

Participants in different groups mentioned the importance of avoiding waiting time as much as possible. This point was stressed by the group of managers, who emphasized their heavy schedules and their desire to organize their time effectively. The solutions proposed by this group reflected the necessity of managing their time and gaining more control over the computer's activities. For example, they proposed to schedule the booting up of their computer a few minutes before their arrival and scheduling software updates after their departure from work. They also proposed to rank the applications to be launched at startup to get working immediately.

Other participants expressed the desire to gain more control over the computer memory, processor and bandwidth resources. Five participants designed a resource allocator where they could control the amount of bandwidth for each file download, or reassess the priority of program computations.

Staying in Context

For many situations, participants suggested presenting contextual information during the wait period. Specifically, several participants suggested temporary activities that were in the same context as the primary activity. However, to avoid interfering with the primary activity, these Managers had suggestions focusing on keeping employees working. One participant who managed several architects and designers stated that waiting for large software suites such as Adobe Creative Suite or AutoCAD to load was a loss of time for his employees and distracted them from their work. In response to this observation, the group brainstormed solutions to inform, motivate and help employees focus on their work. Suggestions included seeing projects previously completed with this software, seeing other employees' projects and even a "best project of the week" selected by the manager. Other general motivation ideas were mentioned such as providing the inspirational of the day, news article or advertisement of the company's achievement. Some participants in the manager group also mentioned the possibility to have a message crafted by the managers themselves and use the loading time as a notice board. Who selects the temporary activity may be an important design choice for active progress bar.

Staying in the Flow (Performing Related Activities)

A subset goal of staying in context is to stay in the flow, where users specifically continue their current task in some way to maintain their train of thought, list and to maximize their productivity [START_REF] Csikszentmihalyi | Flow: The Psychology of Optimal Experience[END_REF]. In contrast with our previous section describing passive activities to stay in context, staying in the flow is likely accomplished by performing active temporary activities specifically related to the primary activity. A good scenario illustrating this category came from the group of photographers. They discussed how transferring photos and uploading those to online sites was a regular task that took a significant portion of their time. They commented that this transfer/upload time was low compared to the time spent modifying pictures but that they felt idle during these downloading periods. They suggested merging those activities: while downloading pictures (as primary activity), a window could appear offering them to tag the picture and open it with their favourite software to modify them (switch to temporary activity). Our predefined user case of compiling code also resulted in many suggestions of activities to stay in flow. Participants suggested static temporary activities such as reading documentation. Activities with active participation from the user included reviewing code statistics, compilation statistics (time it took to compile the previous time), to-do lists generated directly from the code and showing the difference between the to-do lists from the previous and current version. Participants discussed seeing the software architecture, or the last modified files. Finally, participants suggested showing a short movie (or replay) or the last user actions (file edition, writing text, etc.). They made it clear that the temporary activity must depend on the memory required to load/compile program and the resources available.

Back to the most frequent activities

In two different groups, several participants mentioned the fact that in many cases, they did not care about staying in context or in the flow. Indeed, they commented that these waiting periods could serve as breaks since they already used them as such when they knew the wait would be long. For example, they explained that they would use the booting up time of their machine to get a coffee and greet their colleagues. Additionally they mentioned when downloading or during large software loading times they would browse the Internet and go to their favourite shopping site. For such occasions, these participants suggested that a window should appear, showing them their top 5 most used applications. The participants envisioned that they could see their photos being downloaded as an indication of the progress and in the same window the program could suggest the four or five applications they often launch, such as Facebook or shopping websites. Several participants mocked up a prototype that contained a similar idea in the context of the computer start up. The prototype shows a window where users can order their four favourite applications. Thus, the computer will start launching them in this order to enable the user to perform an enjoyable task and limit their frustration while waiting.

Managing Time

The group of managers spent a significant amount of time discussing their time management and emphasizing their need to constantly refer to what they had to do next or check their email before their appointments with employees or customers. Many of them suggested that the waiting period could provide a reminder of what their next action item was or what appointment was coming next. One of the participants also suggested that when waiting for the computer to log off and shut down information could be displayed on the traffic or bus timetable. They mocked up a paper prototype describing a window to be displayed at log off and shut down of the computer. This window shows the fastest way home according to the preset of the user beforehand. This participant commented that they then could select multiple ways to get back home including ride sharing or buses. This application could save them precious time by indicating which transit option would be faster.

Taking a Break

One of the predetermined temporary activity facilitators brought up was the inclusion of some type of entertainment application in the progress bar. Interestingly very few participants responded favourably to this suggestion. The entertainment ideas mentioned were to show feeds from Facebook, news headlines, RSS feeds or the word of the day. However those situations were mentioned in the context of an entertainment primary activity, such as surfing the web and waiting for a page to load. This highlights the potential importance of the link between primary and secondary activity. A few suggested presenting a game, such as online poker. Amusing suggestions included betting with other "waiters" on how long the wait will be, and playing chat "roulette" (chatting with a random fellow waiter). In one group, proposing such games was unsuccessful because they thought that short progress bars, or progress bars of undetermined amount of time were not suitable for games.

SURVEY

Based on our taxonomy, the participatory design sessions and the preliminary feedback on our prototype (see next section), we designed a survey to collect broader user preferences on temporary activities in different situations. This survey was sent via e-mails and we collected the answers of 96 participants (47 female, 49 male, 33 years of age on average, all regular computer users in US, Canada and France).

Current activities when waiting

While 20% of respondents said that they didn't wait in front of their computers for more than 5 seconds, others (80%) confirmed that they did. 47% of the participants mentioned that they just stay idle for short waiting period (less than 5 seconds). 37% of the participants reported switching to a temporary activity. However, 65% answered that they switch to other activities for longer wait (from 15 sec and up). Surprisingly only 50% preferred to do something else when the waiting period was more than 1 minute.

Active Progress Bar design

65% of our participants indicated that they would be willing to use an active progress bar to help them switch to a temporary activity. They estimated that it was worth using the tool when the wait was over 36 seconds on average. To switch to a temporary activity, 36 % preferred that a menu appeared allowing them to select a temporary activity among a few choices. At the end of the waiting period, 70% of the participants answered that they would switch back to their primary activity. 36% of the participants would rather switch back to their activity on their own, by retrieving the appropriate window. However, they also answered that they wanted to be notified that the wait was over. Most of the participants preferred a visual artefact that displayed the end of the waiting period (windows, progress Bar).

Desired activities when waiting

We asked our participants which activities they would perform in situations varying in context and waiting length. In work settings, 60% of our participants answered that they would prefer to stay in context and perform a work related activity or manage their todo list and calendar during a wait of more than 1 minute. During a medium waiting period of 15sec, it appears that about 30% to 40% of the participants would rather perform a passive activity such as getting information about the program waiting or about the weather or traffic. Only 15% of our participants mentioned that they would perform similar passive activities for short waiting periods. In entertainment (home) settings, 67% of our participants favoured activities such as reading twitter or news feeds, in particular for longer waiting periods.

Figure 2:

The Configuration window of the prototype.

EARLY PROTOTYPE DEVELOPMENT

We developed an Active Progress Bar prototype to investigate some of the ideas generated by participants. This software monitors the Operating System (OS) and when it detects a waiting period proposes temporary activities that the user can customize. When a waiting period is detected the system proposes to switch to a temporary activity while waiting. Users can respond that the detection is invalid in order to adjust future detection. Different temporary activities are proposed and the user is notified when the waiting period is finished. A control panel allows users to customize Active Progress Bar. The first waiting periods can be used to customize the tool. In Figure 2, users can set their preferences about when to trigger the progress bar, what activity to trigger, and various parameters for temporary activities. At the bottom buttons give access to the black lists, and a debugging window shows an event log.

Detecting the wait

The detection of a waiting period is a complex problem. While the user is fully aware of a waiting period, in a multi-task and multi-threading OS the computer activity never stops. A common way to notify the user of a waiting period is to display a progress bar control that fills over time. Therefore the appearance of the progress bar may be the best trigger for Active Progress Bar. Thus, our tool monitors and evaluates the value of all available progress bars in the OS.

Progress bar monitoring

In order to retrieve all the progress bar information, we use a polling method. Other options do exist like pixel-based analysis that captures the current display and try, with an image recognizer, to detect the progress bar [START_REF] Dixon | Prefab: implementing advanced behaviors using pixel-based reverse engineering of interface structure[END_REF]. This process is not feasible, because when switching to a temporary activity the progress bar may not be visible anymore. Another approach is to use a hooking method that interfaces into the OS and duplicates messages sent to a progress bar. This requires a complex development process. Therefore, we preferred to use a simple method that consists of asking the OS to list all available windows. Then we ask all these windows the list of their components (with the Win32 API: EnumWindows and EnumChildWindows). If one of these components is a progress bar we retrieve its unique identifier and we record its current value. Then, with regular polling, we can (1) detect new progress bars, (2) estimate their filling speed, and (3) detect if they are full (which means that the waiting period is over).

Temporary activities

Our Active Progress Bar prototype proposes samples of secondary activity applications, combine existing applications with a normal progress bar. i. Entertainment: games such as Sudoku, Web browser with Facebook, photo viewer. ii. Work: FreeWriter that allows the user to manage a to-do list. iii. Both: RSS feeds reading. Users can also choose any other application of their choice to be launched but it would not include the integrated progress bar indicating the remaining time.

Software configuration

Users can select the value, in seconds, of the minimum estimated waiting time that should trigger the Active Progress Bar (the default value is 5 seconds). User can choose if they want the temporary activity to start automatically as soon as the wait is detected or be presented with a menu of activities. Options are available to choose a URL for the web browser or to select an RSS feed. A black list of progress bars can be updated to tailor which application should trigger Active Progress Bar or not.

Use of prototype by the authors

The early prototype was tested by two of the authors. This was to identify bugs, develop ideas for user testing and identify functionality issues. Our initial experience confirms that users will want a high level of customization of Active Progress Bar to adjust to their needs and preferences. Tuning Active Progress Bar's configuration may in fact be a good candidate of temporary activity proposed by default. Initially all applications and processes could trigger Active Progress Bar. This triggered Active Progress Bar too often so a black list was added which improved the problem. To avoid having to "opt-out" too many times before the toolbar becomes useful, the toolbar could allow users to "opt-in" by selecting the applications they want to use Active Progress Bar with. They may select only a few at the beginning such as Photoshop or Illustrator, then add more as they become familiar with the behaviour of the toolbar and find other appropriate uses. The Active Progress Bar could provide statistical information about the applications or processes that make users wait the most, and guide their selection. Our initial prototype only includes visual notification that the wait is over and that the primary activity can resume. Users have to switch back to the primary task themselves (by clicking on the right window). Our initial use of Active Progress Bar leads us to believe that finite activities with a detectable ending (i.e. a user action such as sending a tweet or saving a tab) might be appropriate to trigger automatic returns to the primary activity. This is something we aim to investigate in further research. The feedback from our limited testing about the choice of activities mostly matches the survey results but not entirely (e.g. we liked the photo browser while the survey didn't show that). This confirms the need for a rich configuration panel.

EXPLORING THE IMPACT OF ACTIVE PROGRESS BAR ON PRIMARY TASK

After developing the prototype we wished to investigate two things. Firstly whether Active Progress Bar impacted primary task satisfaction compared to a common situation of waiting. This is important so as to identify whether our Active Progress Bar significantly impacts on their primary task satisfaction compared to a control condition. If 7.94, p=0.01]. This suggests that the interaction effect is based on a significant difference in the control condition where users in the Work condition rated their primary task satisfaction as lower than those in the Non-Work condition. In experiences with the Active Progress Bar this significant difference was not apparent. From the graph in Figure 5 we can see that the satisfaction ratings in the Non Work condition seem to stay relatively consistent in comparison to the Work task where there seems to be a heightening of satisfaction from the control condition to the Active Progress Bar conditions. This would suggest that Active Progress Bar conditions had a positive impact on satisfaction in the Work condition when comparing it to the control condition.

Discussion

These results show that our prototype, with active and passive actions, have a positive impact on primary task satisfaction level and that they have more impact on satisfaction levels from control conditions in work based tasks compared to nonwork based tasks. Interestingly our findings did not show a difference between active or passive tasks. This is likely to be because users prefer to be active during the wait, even if completing a passive or active task rather than doing nothing whilst waiting. Active Progress Bar aims to facilitate active interaction during task waiting and our findings show Active Progress Bar does achieve this. We feel that the future research agenda related to such an application is varied and wide. For example there is a need for testing the interface of Active Progress Bar, the impact it has on primary task variables (as conducted here) and the satisfaction users have with the secondary task. These involve different dependent variables in analysis and need different approaches to study.

We investigated the effect of Active Progress Bar on primary task satisfaction as we wished to identify its impact on the overall task people were needing to achieve as our initial piece of investigatory work into the tools impact. We felt it was important to establish this before further development and research of the application. However further work should not only focus deeper on its effects on primary task but on the other aspects of the Active Progress Bar user experience to develop a more holistic view of this application. At the end of the authors initial stage of testing (described in Section 5.5) there were some hypotheses that through further testing we currently aim to explore. From our experiences with the system it seemed that temporary activities were not worth triggering for short waits, that passive activities seem more appropriate for medium waits (e.g. watching a slide show of photos is immediately rewarding), and that only long waits call for active temporary activities requiring user input (e.g. maintaining a to-do list). Similar interactions between waiting time and secondary activity were also highlighted in the surveys (see Section 6.3). A future avenue for testing Active Progress Bar lies in experimentally testing these hypotheses by varying the type of secondary task and the time of the wait to identify how that impacts on user experience.

It is important to highlight that although the tasks were written so as to make the dichotomy of the tasks into Work and Non-Work clear (indeed this was the reason they were conducted as betweenparticipants conditions) the task in both settings are not necessarily exclusive to those contexts. For instance categorising and naming photographs may not be seen as a solely non-work based activity if the person taking part is a photographer, who would do this in a work scenario, although in our sample it would be safe to presume that such an activity is a recreational rather than work activity. Further research could experiment with the framing of these tasks to identify whether primary task satisfaction is impacted by context or whether the effect seen here is due to the type of task completed in the conditions. Before concluding we would like to highlight the limitations of the sample homogeneity in terms of gender and profession and the size of the sample. A larger and wider array of participants with a more even gender balance is needed to make the conclusions more generalizable yet the findings here point to the promising positive influence of Active Progress Bar on primary task satisfaction.

As this work was a small-scale pilot experiment we are currently aiming to expand and refine the original experiment design to include more defined and consistent tasks and to test this with a more heterogeneous sample.

CONCLUSION

In this paper, we introduced Active Progress Bar, a new approach facilitating the switching to temporary activities when a primary activity requires users to wait. We provided a taxonomy of waiting times and explored the design space of an Active Progress Bar tool using four approaches (participatory design, survey, informal discussions, and prototype). We report numerous situations where users wait, and propose relevant secondary activities. We demonstrated the feasibility of detecting the waiting with an Active Progress Bar prototype, and finally, we assessed that our tool impacts primary satisfaction levels with a controlled experiment. Results of our controlled experiment showed that the Active Progress Bar system impacts primary task satisfaction levels compared to control conditions in a work scenario. The next phase is to allow the user to customize the Active Progress Bar tool to define relevant secondary tasks during these waiting periods and identify the effects his may have on satisfaction. We believe that with adequate user control, Active Progress Bar has the potential to help users make better use of their time while waiting.

ACKNOWLEDGEMENT

We would like to thank Catherine Plaisant for her insightful comments and her help to design our prototype.

Figure 1 :

 1 Figure 1: Paper prototype for booking a flight.

  the difference in the Work and Non Work tasks in the Active Condition [F (2,44)= 0.08, p=0.78]. However the differences in primary task satisfaction between the Non Work and Work tasks in the Idle (Control) condition and the Active Progress Bar condition were significantly different [F (2,44)=

Figure 3 :

 3 Figure 3: Graphical representation of the interaction between task and Active Progress Bar condition.

Table 1 :

 1 Description of participator design samples

	Group	Age (stdev) Distribution
	Computer scientists	27 (4.2)	1M 3F
	Computer scientists	27 (5.2)	3M 1F
	Non-IT	36 (15.6)	4M 1F
	Photographers	29 (6.1)	2M 2F
	Managers	36 (8.6)	5M 0F

Table 2 :

 2 Most common progress bar situations. (N=number of subjects that noted the situation) One participant proposed the situation of booking a flight ticket, which lead to a large number of ideas. Most consisted of providing contextual information about the travel destination during the wait time, such as top tourists activities, weather, local headlines and events in the area.

	Progress Bar Situations	N	Freq/ week	Wait (min)	Frustration (S.D.)
	Loading software	10	21.2	1.7	4.4 (1.9)
	Installing/
	updating a	10	2.9	8.4	4.7 (1.9)
	program
	Loading webpage	8	51.5	0.7	3.6 (1.7)
	Downloading
	files, photos,	8	12.4	11.8 4.1 (1.9)
	etc.
	Booting a computer	6	4.6	3.2	3.5 (1.5)

we find that Active Progress Bar brings more satisfaction then we can conclude that this tool has a positive impact on the user experience of these situations and warrants further exploration. Secondly we wanted to test some of the observations from the participatory design sessions in a more controlled way to gather causal insight into these observations. We wished to observe the impact of Active Progress Bar on different types of primary task contexts (more work related compared to more non work related) and how different types of activities (either active or passive) have an impact on primary task satisfaction. We did this by running a small-scale controlled experiment with 24 participants (23 Male and 1 Female), all regular computer users in France.

Tasks

We defined two tasks (between-user conditions) and three conditions in which users will have to wait (within-user conditions). In both tasks, Active Progress Bar notified the user when the waiting period was over. The order of the conditions was fully counterbalanced to reduce the impact of order and practice effects on completion satisfaction across the experiment. Each participant completed only one of the tasks, but did so for each waiting condition. After each condition, they completed a satisfaction questionnaire.

Task 1-Sending an email

Participants were asked to start their email software and send an email to a colleague. Since the email software takes one minute to start, the user needed to wait before they were able to send their email. The participant was provided the content for the email. Participants completed this task under three conditions: i. No Active Progress Bar (Idle-Control).

Participants waited 1 minute without doing anything before sending the email. ii. Active Progress Bar + passive action (Passive).

Participants read an RSS feed while waiting for the software to load. They then completed and sent the email. iii. Active Progress Bar + active action (Active).

The user immediately started writing the email, facilitated by Active Progress Bar, but they were not able to send it until the email software started.

Task 2-Copying camera images (Non-work)

Participants were asked to copy a set of images from a camera to their desktop. The copying process took one minute to complete. i. No active Progress Bar (Idle-Control).

Participants waited 1 minute without doing anything.

ii. Active Progress Bar + passive action (Passive).

Participants saw a slideshow of the copying pictures while waiting for the pictures to transfer. iii. Active Progress Bar + active action (Active).

Participants could rotate, delete, and rename pictures during the copying process before the task was complete.

Questionnaire

We designed a Task Satisfaction Inventory (TSI) for the experiment, using concepts from satisfaction measures such as the QUIS [START_REF] Chin | Development of an instrument measuring user satisfaction of the human-computer interface[END_REF] and the MINERVA [START_REF] Love | Identifying salient usability attributes for automated telephone services[END_REF]. The measure is made up of 16 items (9 positively worded items, 7 negatively worded items), focusing on aspects of ease of task completion ("I thought completing the task was complicated"), affect ("Completing the task was fun"), efficiency ("Completing the task took too long") and control ("when competing the task I always knew what to do next"). When completing the questionnaire participants were asked to think about the primary task they completed in the experiment. The questionnaire used a 5-point Likert scale ranging from Strongly Disagree to Strongly Agree. Negative items were reverse scored and the scores were summed to create a task satisfaction score. The scale range was from a minimum of 16 to a maximum of 80. The questionnaire items were randomly ordered into 3 order sets so as to reduce the opportunity of participants remembering their previous responses. Each order was used consecutively in each session.

Results

A reliability analysis was conducted to identify the TSI's internal consistency. ). We found no significant difference between the passive and active conditions (p=0.056). We also found a significant interaction between active Progress Bar and Task variables on user task satisfaction (F (2,44)= 7.25, p=0.002) (Figure 3). Simple contrasts highlight that the difference between the Work and Non Work tasks in the Passive condition was not significantly different to


Maxime Cordeil
email: cordeil@cena.fr

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

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

Experimenting and Improving Perception of 3D Rotation-based Transitions between 2D Visualizations

Keywords: Information Visualization, Visual exploration, Navigation, Transition, 3D Rotation

Exploring a multidimensional dataset with visualization requires to transition between points of view. In order to enable users to understand transitions, visualization can employ progressive 3D rotations. However, existing implementations of progressive 3D rotation exhibit some perception problems with visualization of cluttered scene. In this paper, we present a first experiment showing how existing 3D rotation is effective for tracking marks, and that cluttered scenes actually hinder perception of rotation. Then, we propose to set the axis of rotation on the graphical marks of interest, and ran a second experiment showing that focus-centered rotation improves perception of relative arrangement.

Introduction

Air Traffic Control analysts have to analyze how a particular Air Traffic Controller proceeded to resolve a past conflict involving two aircraft. For these incidents analysis, they use two 2D-views presenting aircraft trajectories from top and vertical views. Thereby, they switch between these views in order to understand the resolution of the conflict, i.e. which aircraft has changed its flight level or heading.

The switch between views can use 3D rotation, a transition that supposedly helps track moving marks and their relative arrangement during the time of the transition. This type of animated transition consists of displaying a temporary 3D view that rotates like a transparent dice. It is used for example for exploration of scatterplots (ScatterDice [START_REF] Elmqvist | Rolling the dice: Multidimensional Visual Exploration using Scatterplot Matrix Navigation Visualization[END_REF]) or aircraft trajectories (FromDaDy [START_REF] Hurter | FromDaDy: Spreading Aircraft Trajectories Across Views to Support Iterative Queries[END_REF]). The scatterdice-like transition implemented in visualization tools used by ATC analysts is slightly different; to explore data, users are free to pan and zoom 2D-views of trajectories. Since the rotation axis is always set at the X,Y,Z center of the data set, the scatterdicelike transition can provoke a loss of focus on these trajectories. Furthermore, in the original usage of scatterdice users deal with a small amount of data, whereas ATC analysts have to deal with a large amount of trajectories (up to 20,000), resulting in cluttered scenes. Previous studied benefits of animated transitions showed that rotation can help track objects [START_REF] Robertson | Animated visualization of multiple intersecting hierarchies[END_REF] but the studies did not aim at assessing the perception of relative arrangement.

In this paper, we first present an experiment showing that 3D rotation can help users tracking objects and that cluttered scenes hinder perception of rotation. Then we propose an improvement of 3D rotation regarding problems we identified, and ran experiments showing that focus-centred rotation improves perception of relative spatial arrangement.

Experiment 1: Tracking Objects

The goal of this experiment is to validate that animated rotation helps users tracking graphical objects, and that density influences the effectiveness at this task. The underlying hypothesis is: (H1) higher density levels will negatively affect tracking objects.

The screen is a standard 21" LCD screen. A trajectory is depicted with a 1 pixelwidth line. There were nine subjects, all regular computer users (researchers and PhDs in computer science, ergonomics, air traffic controllers), with an age ranging from 22 to 55 (average of age 40). Half of them are familiar with 3D environments. None are Infovis experts. Though the task is related to the specific activity, it does not require Air Traffic Control skills.

In this experiment, the system first presented a top view of green trajectories, with a particular red trajectory (the focus trajectory). After four seconds, the red trajectory turned to green and the system played a 3D-rotation from the top to the vertical view. In this last view, the same trajectory or another one was re-highlighted in red. Then, participants were asked to answer "Yes" or "No" to the question: "Is the red trajectory the same as the red one at the beginning of the animation?" During this first experiment, there were four levels of density (i.e. number of displayed trajectories): Empty (only the two trajectories of interest), Low (10 trajectories), Medium (20 trajectories) and Heavy (40 trajectories). The starting location of the trajectories is at the edge of the screen. We excluded the centre location since we assume that it helps the subject to track a mark. One of our concerns was that subjects would recognize trajectory configurations, and base their answers on previous trials. To avoid this effect, we varied the profiles of the trajectories, and the exact starting location. In summary, we tested 4 levels of density, with 4 trajectory profiles, at 4 locations. Thus, each subject performed 64 trials. The order of conditions was counter-balanced.

We merged the results according to density level and performed a measure-repeated ANOVA on the data. We only consider findings significant if the P value is less than .05. We first found that the level of density influences the correctness of the users' answers (p=,000). In the "empty" condition, users answered 88% correctly, but only 40% when the view is cluttered. Wrong answers vary with density accordingly, but the analysis is not significant (p=,055). The amount of undecided answers is correlated to density levels (p=,000). Users were undecided for only 1% of the trials with no density, as opposed to 40% with the cluttered one.

The experiment shows that H1 was confirmed: the level of density negatively impacts the effectiveness at tracking marks. In the next section, we propose a new rotation design that counters the effect of density.

Experiment 2: Improving 3D Rotation Perception and Perception of Relative Arrangement

If designers of visualization software want to make rotation effective at tracking marks in dense scenes, they have to provide specific features that counter the density effect. Our proposal is to set the rotation axis on the graphical mark of interest. We called this 3D-rotation a focus-centred rotation.

The experiments we show in this section are not about testing if focus-centred rotation is better than screen-centred rotation at tracking marks. However, perceiving arrangement of marks (i.e. understanding spatial relationship between marks) relies on correct tracking; considering experiment 1 results, we already know that density hinders perceiving arrangement. Thus, these experiments aim to show that a focuscentred 3D rotation helps better the perception of relative arrangement than a screencentred 3D rotation. To summarize, the assumptions we make are: (H1) Focus-centred rotation provides a better accuracy than screen-centred rotation (H2) Density levels have a negative impact on accuracy; (H3) Density levels have less of a negative impact on accuracy with focus-centred rotation compared to screen-centred rotation.

The experimental apparatus and participants are the same as in the first experiment. In this experiment, two trajectories are displayed as lines. When seen in the top view, lines cross. However, one trajectory stays at the same altitude, whereas the other one changes its altitude. The user has to figure out if the stationary trajectory goes under or above the other one. This task requires the user to focus on the trajectories of interest, and to perceive the relative arrangement of the lines. Participants first see a top view with two highlighted crossing trajectories in red (the surrounding trajectories are green). After 4 seconds, the colour of the specific trajectories turns back to green, and the 3D rotation from the top to the vertical view is played. At the end of the transition, participants were asked to answer the question: "does the stationary trajectory go under the trajectory that changes altitude?" with "yes", "no", or "I don't know" We used three different density levels (empty, medium with 20 trajectories, high with 40 trajectories), 4 profiles of trajectories, 4 trajectory locations (lop-left, top-right, bottom-left, bottom-right), and 2 types of transition (screen-centred, focused-centred rotation). Since we did not repeat measures, users performed 96 trials each.

We first analyzed the global effect of rotation types without taking into account the context. The rotation types have a significant effect on correct answers: F(1, 10)=12,224, p=,00576 and on undecided answers: F(1, 10)=7,8955, p=,01848. Since the number of bad answers is very low, the analysis does not show a significant effect on the wrong answers: F(1, 10)=1,5432, p=,24248. This analysis shows that without taking into account the context density, the Focus-centered rotation improves the rotation efficiency to understand the data structure (H1).

We also assessed the impact of the context with repeated measures ANOVA using contexts (Empty, Medium, and Heavy) and the type of rotation (Screen-centered, Focus-centered) factors. For the participant's correct answers, we have found that there is a main effect of rotation type: F(2,20) = 12,224 p=,005762, and a main effect of context : F(2,20)=26,395 p=,000. We also found an interaction between density and rotation type (F(2,20)=6,754 p=,005740). These results show that density has less of an impact on correctness of answers with focus-centered rotation (from 99% to 90% vs from 99% to 66% for screen-centered rotation).

For wrong answers, we have found that there is no main effect. Results were not found significant for the rotation type effect (F(2,20)= 1,53918 p=,243058) and the density effect(F(2,20)= 1,51103 p=,244827). We did not found an interaction between density and rotation type (F(2,20)=0,61053 p=,0552848). These results are not significant because participants gave very few wrong answers. This suggests that both transitions are not misleading. For the participants' undecided answers, we have found that there is a main effect of rotation type (F(2,20)=7,89552 p=,018478) and a main effect of context (F(2,20) = 13,60981 p=,000186). We also found an interaction between density and rotation type (F(2,20) = 9,25000 p=,001431).

We can conclude that Focus-centered rotation minimizes the indecision of participants when density increases (for heavy density, 8% vs 28% undecided answers). Our analysis shows that the type of rotation has a significant effect on the user's ability to understand the data structure (H2) and that the impact of the context density is reduced with the Focus-centered rotation (H3). Hence the Focus-centered rotation is more efficient than the Screen-centered rotation.

Conclusion and Design Perspective

We proposed that rotation-based transition help in tracking marks, and perceiving their relative arrangement. We showed that users can track marks with a rotation, but that density hinders it. We also showed that rotation enables users to perceive relative arrangement, and that focus-centred rotation improves perception of relative arrangement compared to a screen-centred rotation. As stated before, this paper is about perception of rotation for visualization, and not about the interaction with the rotation. Now that we know that perception is better with a focus-centred rotation, we need to enable the user to rotate around this axis instead of the centre of the screen. Of course, in contrast to experiment 2, the system does not know which marks the user currently analyses. Hence, we are currently working on the design of an interaction to set the location of the axis. Solutions based on selecting an object are not suitable, since our scenes are very dense and cluttered, which makes pointing a difficult task.


Kata Gábor
email: kata.gabor@inria.fr

Benoît Sagot
email: benoit.sagot@inria.fr

Automated Error Detection in Digitized Cultural Heritage Documents

The work reported in this paper aims at performance optimization in the digitization of documents pertaining to the cultural heritage domain. A hybrid method is proposed, combining statistical classification algorithms and linguistic knowledge to automatize post-OCR error detection and correction. The current paper deals with the integration of linguistic modules and their impact on error detection.

Introduction

Providing wider access to national cultural heritage by massive digitization confronts the actors of the field with a set of new challenges. State of the art optical character recognition (OCR) software currently achieve an error rate of around 1 to 10% depending on the age and the layout of the text. While this quality may be adequate for indexing, documents intended for reading need to meet higher standards. A reduction of the error rate by a factor of 10 to 100 becomes necessary for the diffusion of digitized books and journals through emerging technologies such as e-books. Our paper deals with the automatic post-processing of digitized documents with the aim of reducing the OCR error rate by using contextual information and linguistic processing, by and large absent from current OCR engines. In the current stage of the project, we are focusing on French texts from the archives of the French National Library (Bibliothèque Nationale de France) covering the period from 1646 to 1990. We adopted a hybrid approach, making use of both statistical classification techniques and linguistically motivated modules to detect OCR errors and generate correction candidates. The technology is based on a symbolic linguistic preprocessing, followed by a statistical module which adpots the noisy channel model [START_REF] Shannon | A Mathematical Theory of Communication[END_REF]. Symbolic methods for error correction allow to target specific phenomena with a high precision, but they typically strongly rely on presumptions about the nature of errors encountered. This drawback can be overcome by using the noisy channel model [START_REF] Kernighan | A spelling correction program based on a noisy channel model[END_REF][START_REF] Brill | An Improved Error Model for Noisy Channel Spelling Correction[END_REF][START_REF] Kolak | OCR error correction using a noisy channel model[END_REF][START_REF] Mays | Context based spelling correction[END_REF][START_REF] Tong | A statistical approach to automatic OCR error correction in context[END_REF]. However, error models in such systems work best if they are created from manually corrected training data, which are not always available. Other alternatives to OCR error correction include (weighted) FSTs [START_REF] Beaufort | A weighted finite-state framework for correcting errors in natural scene OCR[END_REF], voting systems using the output of different OCR engines [START_REF] Klein | A voting system for automatic OCR correction[END_REF], textual alignment combined with dictionary lookup [START_REF] Lund | Improving optical character recognition through efficient multiple system alignment[END_REF], or heuristic correction methods [START_REF] Alex | Digitised historical text: Does it have to be mediOCRe?[END_REF]. While correction systems rely less and less on pre-existing external dictionaries, a shift can be observed towards methods that dinamically create lexicons either by exploiting the Web [START_REF] Cucerzan | Spelling correction as an iterative process that exploits the collective knowledge of web users[END_REF][START_REF] Strohmaier | Lexical postcorrection of OCR-results: the web as a dynamic secondary dictionary[END_REF] or from the corpus [START_REF] Reynaert | Multilingual text induced spelling correction[END_REF].

As to linguistically enhanced models, POS tagging was succesfully applied to spelling correction [START_REF] Golding | Combining trigram-based and feature-based methods for context-sensitive spelling correction[END_REF][START_REF] Schaback | Multi-level feature extraction for spelling correction[END_REF]. However, to our knowledge, very little work has been done to exploit linguistic analysis for post-OCR correction [START_REF] Francom | Diacritic error detection and restoration via part-of-speech tags[END_REF]. We propose to apply a shallow processing module to detect certain types of named entities (NEs), and a POS tagger trained specifically to deal with NE-tagged input. Our studies aim to demonstrate that linguistic preprocessing can efficiently contribute to reduce the error rate by 1) detecting false corrections proposed by the statistical correction module, 2) detecting OCR errors which are unlikely to be detected by the statistical correction module. We argue that named entity grammars can be adapted to the correction task at a low cost and they allow to target specific types of errors with a very high precision.

In what follows, we present the global architecture of the post-OCR correction system (2), the named entity recognition module (3), as well as our experiments in named entity-aware POS tagging (4). The predicted impact of the linguistic modules is illustrated in section 5. Finally, we present ongoing work and the conclusion (6).

System Architecture

Our OCR error detection and correction system uses a hybrid methodology with a symbolic module for linguistic preprocessing, a POS tagger, followed by statistical decoding correction modules. The SxPipe toolchain [START_REF] Sagot | SxPipe 2: architecture pour le traitement pré-syntaxique de corpus bruts[END_REF] is used for shallow processing tasks (tokenisation, sentence segmentation, named entity recognition). The NE-tagged text is input to POS tagging with MElt-h, a hybrid version of the MElt tagger [START_REF] Denis | Exploitation d'une ressource lexicale pour la construction d'un étiqueteur morphosyntaxique état-de-l'art du franc ¸ais[END_REF][START_REF] Denis | Coupling an annotated corpus and a lexicon for state-of-the-art POS tagging[END_REF]. MELT-h can take both NE tagged texts and raw text as input. The decoding phase is based on the noisy channel model [START_REF] Shannon | A Mathematical Theory of Communication[END_REF] adapted to spell checking [START_REF] Kernighan | A spelling correction program based on a noisy channel model[END_REF]. In a noisy channel model, given an input string s, we want to find the word w which maximizes P (w|s). Using Bayes theorem, this can be written as:

argmax(w)P (s|w) * P (w) (1)
where P(w) is given by the language model obtained from clean corpora. Both sentence-level [START_REF] Tong | A statistical approach to automatic OCR error correction in context[END_REF][START_REF] Boswell | Language models for spelling correction[END_REF]) and wordlevel [START_REF] Mays | Context based spelling correction[END_REF] language models can be used. P (s|w) is given by the error model, represented as a confusion matrix calculated from our training corpus in which OCR output is aligned with its manually corrected, noiseless equivalent. The post-correction process is summarized in 1. The integration of a symbolic module for NE recognition and the use of part of speech and named entity tags constitute a novel aspect in our method. Moreover, linguistic preprocessing allows us to challenge tokenisation decisions prior [START_REF] Kolak | OCR postprocessing for low density languages[END_REF]) ; this constitutes a significant feature as OCR errors often boil down to a fusion or split of tokens.

The corpus we use comes from the archives of the French National Library and contains 1 500 documents (50 000 000 tokens). This corpus is available both as a "reference corpus", i.e., in a manually corrected, clean version, and as a "contrast corpus", i.e., a noisy OCR output version. These variants are aligned at the sentence level.

3 Named entity tagging

NE recognition methodology

As a first step in error detection, the OCR output is analysed in search of "irregular" character sequences such as named entities. This process is implemented with SxPipe [START_REF] Sagot | SxPipe 2: architecture pour le traitement pré-syntaxique de corpus bruts[END_REF], a freely available1 , robust and modular multilingual processing chain for unrestricted text. SxPipe contains modules for named entity recognition, tokenization, sentence segmentation, non-deterministic multi-word expression detection, spelling correction and lexicon-based patterns detection. The SxPipe chain is fully customizable with respect to input language, domain, text type and the modules to be used. Users are also free to add their own modules to the chain.

In accordance with our purposes, we defined named entities as sequences of characters which cannot be analysed morphologically or syntactically, yet follow productive patterns. Such entities do not adhere to regular tokenization patterns since they often include punctuation marks, usually considered as separators. As compared to the consensual use of the term [START_REF] Maynard | Named entity recognition from diverse text types[END_REF][START_REF] Chinchor | Muc-7 named entity task definition[END_REF][START_REF] Tjong | Introduction to the conll-2003 shared task: Languageindependent named entity recognition[END_REF], our definition covers a wider range of entities, e.g., numerals, currency units, dimensions. 2 The correct annotation of these entities has a double relevance for our project:

• NE tagging prior to POS tagging helps to improve the accuracy of the latter.

• NE tagging allows to detect and, eventually, correct OCR errors which occur inside NEs. Conversely, it can also contribute to detect false correction candidates when the sequence of characters forming the NE would otherwise be assigned a low probability by the language model.

The named entity recognition module is implemented in Perl as a series of local grammars. Local grammars constitute a simple and powerful tool to recognize open classes of entities [START_REF] Friburger | Finitestate transducer cascades to extract named entities in texts[END_REF][START_REF] Maynard | Architectural elements of language engineering robustness[END_REF][START_REF] Bontcheva | Shallow methods for named entity coreference resolution[END_REF]; we are concerned with time expressions, addresses, currency units, dimensions, chemical formulae and legal IDs. Named entity grammars are applied to the raw corpus before tokenization and segmentation. Our grammars are robust in the sense that they inherently recognize and correct some types of frequent OCR errors in the input. 3 SxPipe's architecture allows to define an OCR-specific correction mode as an input parameter and hence apply robust recognition and correction to noisy output, while requiring exact matching for clean texts. However, maximizing precision remains our primary target, as a false correction is more costly than the non-correction of an eventual error at this stage. Therefore, our grammars are built around unambiguous markers.

Evaluation of NE tagging

A manual, application-independent evaluation was carried out, concentrating primarily on precision for the reasons mentioned in 3. For four types of NEs, we collected a sample of 200 sentences expected to contain one or more instances of the given entity category, based on the presence of category-specific markers (lexical units, acronyms etc.)4 . However, chemical formulae were evaluated directly on sentences extracted from the archives of the European Patent Office; no filtering was needed due to the density of formulae in these documents. Legal IDs were evaluated on a legal corpus from the Publications Office of the European Union, while the rest of the grammars were evaluated using the BNF corpus. The following step in the chain is POS tagging using a named entity-aware version of the MElt tagger. MElt [START_REF] Denis | Exploitation d'une ressource lexicale pour la construction d'un étiqueteur morphosyntaxique état-de-l'art du franc ¸ais[END_REF][START_REF] Denis | Coupling an annotated corpus and a lexicon for state-of-the-art POS tagging[END_REF]) is a maximum entropy POS tagger which differs from other systems in that it uses both corpus-based features and a large-coverage lexicon as an external source of information. Its French version, MElt-FR was trained on the Lefff lexicon [START_REF] Sagot | The lefff, a freely available and large-coverage morphological and syntactic lexicon for french[END_REF] and on the French TreeBank (FTB) [START_REF] Abeillé | Building a treebank for French[END_REF]. The training corpus uses a tagset consisting of 29 tags. MElt FR yields state of the art results for French, namely 97.8% accuracy on the test set.

Entity Type Precision

In order to integrate MElt into our toolchain, the tagger needed to be trained to read NE-tagged texts as output by SxPipe. We thus extended the FTB with 332 manually annotated sentences (15 500 tokens) containing real examples for each type of NE covered by our version of SxPipe. Sx-Pipe's output format was slightly modified to facilitate learning: entities covered by the grammars were replaced by pseudo-words corresponding to their category. The training corpus is the union of the FTB and the small NE corpus annotated with 35 categories (29 POS and 6 named entity categories). We used this corpus to train MElt-h, a hybrid tagger compatible with our OCR postprocessing toolchain. MElt-h can tag both raw corpora (using the 29 POS categories learnt from the FTB), and NE-annotated texts (preprocessed with SxPipe or any other tool, as long as the format is consistent with the output of SxPipe). Training a tagger on a heterogeneous corpus like the one we used is theoretically challengeable. Therefore, careful attention was paid to evaluating it on both NE-annotated data and on the FTB test corpus. The latter result is meant to indicate whether there is a decrease in performance compared to the "original" MElt FR tagger, trained solely on FTB data.

Evaluation of POS and NE tagging

A set of experiments were performed using different sections of the NE-annotated training data. First, we cut out 100 sentences at random and used them as a test corpus. From the rest of the sentences, we created diverse random partitionings using 50, 100, 150 and all the 232 sentences as training data. We trained MElt-h on each training corpus and evaluated it on the test section of the FTB as well as on the 100 NE-annotated sentences. The results confirm that adding NE-annotated sentences to the training corpus does not decrease precision on the FTB itself. Furthermore, we note that the results on the NE corpus are slightly inferior to the results on the FTB, but the figures suggest that the learning curve did not reach a limit for NE-annotated data: adding more NE-annotated sentences will probably increase precision.

#sentences

Expected impact on OCR error reduction

While the major impact of named entity tagging and NE-enriched POS tagging is expected to result from their integration into the language model, series of experiments are currently being carried out to estimate the efficiency of the symbolic correction module and the quantity of the remaining OCR errors inside named entities. A sample of 500.000 sentences (15.500.000 tokens) was extracted from the BNF corpus to be used for a comparison and case studies, both in the noisy OCR output version and in the editorial quality version. Both types of texts were tagged for NEs with Sx-Pipe, using the "clean input" mode (without tolerance for errors and correction candidates). Only 65% of the recognized NEs are identical, implying that 35% of the named entities are very likely to contain an OCR error. 5 To investigate further, we applied the grammars one by one in "noisy input" mode. This setting allows to detect certain types of typical OCR errors, with an efficiency ranging from 0 (no tolerance) to 10% i.e., up to this quantity of erroneous input can be detected and correctly tagged with certain named entity grammars. Detailed case studies are currently being carried out to determine the exact precision of the correction module.

Conclusion and Future Work

We described an architecture for post-OCR error detection in documents pertaining to the cultural heritage domain. Among other characteristics, the specificity of our model consists in a combination of linguistic analysis and statistical modules, which interact at different stages in the error detection and correction process. The first experiments carried out within the project suggest that linguistically informed modules can efficiently complement statistical methods for post-OCR error detection. Our principal future direction is towards the integration of NE-enriched POS tagging information into the language models, in order to provide a finer grained categorization and account for these phenomena. A series of experiences are planned to be undertaken, using different combinations of token-level information.

Figure 1 :

 1 Figure 1: Architecture

Table 1 :

 1 Evaluation of NE grammars

	Recall

4.1 MElt FR and MElt-h

Table 2 :

 2 Evaluation of MElt-h on the FTB and on the NE-annotated corpus

		Prec on FTB Prec on PACTE-NE
	0	97.83	-
	50	97.82	95.61
	100	97.80	95.71
	150	97.78	95.76
	200	97.78	95.84
	232	97.75	96.20

https://gforge.inria.fr/projects/lingwb/

Our current experiments do not cover single-word proper names.

E.g., A numerical 0 inside a chemical formula is presumed in most cases to be an erroneous hypothesis for alphabetical O.

Although this sampling is biased towards entities with a certain type of marker, it gives an approximation on the recall, as opposed to simply extracting hits of our grammars and evaluating only their precision.

In the less frequent case, divergences can also be due to errors in the editorial quality text.