Joseph Chazalon
email: joseph.chazalon@irisa.fr

Bertrand Co Üasnon
email: bertrand.couasnon@irisa.fr

Aurélie Lemaitre
email: aurelie.lemaitre@irisa.fr

A Simple and Uniform Way to Introduce Complimentary Asynchronous Interaction Models in an Existing Document Analysis System

Keywords: human interaction, asynchronous interaction, interaction models, degraded documents, historical documents

Extracting and indexing meaningful contents from degraded documents, like historical ones, is a challenging problem. Existing analysis systems usually rely on a manual correction of results during the post-processing stage, and cannot make use of external information to adapt their response. This paper presents how an existing document analysis system can be easily adapted to enable an efficient interaction during the analysis stage, and benefit from external information. We identify the minimal architecture required, and we detail the two complimentary interaction models we propose: a directed interaction model which allows to handle cases where errors can be automatically detected; and a spontaneous interaction model which permits to cope with the other cases. Both models are asynchronous to prevent the human operator or the system from waiting for each other during document processing. They are based on a common foundation which uses standard exception-like mechanisms to implement error detection, correction and recovery aspects. Our system was tested on several tasks. For instance, for the transcription of handwritten words in documents dating from the 18th century, where we were able to diminish the human workload by 28% for an overall recognition rate of 80%.

I. INTRODUCTION

Difficulties encountered during content extraction and indexing in old and degraded documents have at least two main causes. First, the media is damaged, and the content is altered. Documents are noisy channels which require error-correcting analysis methods. Second, both contents and structures in historical collection can vary a lot: printed and handwritten contents can be mixed, writers can change, vocabulary is outdated or unknown in advance (family names for instance), structures are not constrained by some modern formating system. . . Models we use tend to be unreliable as unexpected elements will very probably be encountered in the important amounts of pages we process.

These causes lead to important amounts of errors during mass processing of documents. Contextual dependencies between elements increase the final amount of manual corrections needed. It is often more efficient to let a human operator manually produce the results instead of correcting all the errors after the processing. Therefore, an analysis system should make use of external information during the processing stage to improve its response to past and future pages and globally reduce the amount of human work required. This interaction must be asynchronous to prevent the human and the system from waiting for each other.

This paper details how, using a uniform basis, complimentary interaction models can be easily implemented in an analysis system. In Sec. II, we review several existing interactive approaches for document processing and show that two interaction models are necessary. In Sec. III, we present the minimal architecture required to enable those models. In Sec. IV, we focus on how we transformed our page analyzer using a common basis for both models, easy to adapt to other systems. In Sec. V, we illustrate the capabilities of such system with two experiments we made.

II. RELATED WORK

Few document analysis systems allow human operators to interact with them during the analysis stage to guide or correct their response. Some systems among those few illustrate well the challenges we face.

The Edelweiss system [START_REF] Roussel | Web-based cooperative document understanding[END_REF] proposes a first kind of interaction. It process document pages and progressively produces an XML structure a human operator can edit at some points in the analysis process. On the one hand, it permits to influence the response of the system for the rest of the page processing by virtually transforming any element in the document structure, but on the other hand, it does not reconsider previous intermediary results, and does not validate humanprovided information against some document model.

The smartFIX system [START_REF] Klein | smartFIX: An adaptive system for document analysis and understanding[END_REF] relies heavily on human interaction. It is designed for mass processing of business documents, like medical invoices, and automatically triggers business transactions. It assigns a confidence score to elements it extracts and recognizes, and asks for a human validation for suspicious ones, or for a correction for problematic ones. While this approach permits an homogeneous integration of human knowledge in the process, it limits the modifications made by a human to final results, preventing to correct original errors and to guide the analysis.

Nagy and Veeramachaneni explore, in [START_REF] Nagy | Adaptive and interactive approaches to document analysis[END_REF], some links between document processing and interaction: they suggest that "the operator should not even have to look at data that the system had no trouble in classifying", and also that "every interaction should be utilized by the system to improve subsequent classification". There first requirement implies a "machine-initiated interaction", where the human operator reacts to problems detected. However, the detection of errors and the localization of their cause cannot always be done automatically, while it is still necessary to replace some parts of the automated analysis by human processing.

The ability to detect errors is the key here, and we propose to distinguish interaction which is "directed" (by automatic error detection) [START_REF] Chazalon | Iterative Analysis of Pages in Document Collections for Efficient User Interaction[END_REF], where error detection is possible, and where a question (which requires an answer) can be asked to a human operator; and interaction which is "spontaneous" [START_REF] Chazalon | Iterative analysis of document collections enables efficient human-initiated interaction[END_REF] for cases where error detection not possible. Spontaneous interaction is "human-initiated", as the automated system will have to react to external information, and use it to improve its response for a given page. The following sections present how an iterative analysis of pages permits to adapt the system response, and how a common foundation enables both directed and spontaneous interaction models. System improvement using machine learning will not be discussed, even if our architecture supports it.

III. ITERATIVE ANALYSIS ARCHITECTURE FOR HUMAN INTERACTION

To enable an asynchronous between a human operator and a document analysis system during the analysis stage, and permit to reconsider previous results for the pages processed, we need: i) an iterative analysis of pages; ii) a visual memory structure; iii) an architecture for collection processing. We now detail those aspects, and show that the page analyzer is the key component to make use of external information.

A. Iterative Analysis of Pages

The simplest iterative analysis scenario we use is the one where we first process all the pages of a collection automatically, then we let the human operator asynchronously provide necessary information about pages. Each page is then reprocessed using external information, and this scheme is repeated as many times as needed. At each iteration, new information about the page being reprocessed is provided.

To enable such approach, both the system and the human operator have to be given the same goal, and the ability to exchange information about the content of the pages, according to a previously established protocol. As interaction must be asynchronous, the system has to be able to store information associated to pages, and therefore it should be able to process them independently from the human.

Page Analyzer Human Interface

Central Storage

Strategy Module 1: process(I, M I (t))

2: M I (t + 1) 3: process(I, M I (t + 1))

4: M I (t + 2)
Figure 1. A single step (repeated as many times as needed during the iterative analysis) of a possible information exchange about a given image between a page analyzer and a human interface, showing the implied components of the architecture and the visual memory M I associated to the image I. At time t, the strategy modules first invokes the page analyzer on the image I, with the memory M I (t). The strategy module gathers M I (t+1) after the analysis, and transfers it to the human interface, which, in turn, produces M I (t + 2) and sends it back.

The human operator provides as much information as required (directed model), and may be able to provide extra elements (spontaneous model). Questions of a directed interactive session could be "Where is the recipient bloc of this mail?", or "What is the value of this number (zone)?". Answers and information provided during a spontaneous interactive session are we similar, and could be "The recipient is here (zone).", "The value of this number is 27.", or "The right place for the sum column of this bill is here (zone)."

B. Visual Memory

The visual memory is a persistent data structure associated to each page which is used for information exchange between processes, but also during document analysis in order to reintegrate external information and use it. It is an associative structure that each process can change, and which gives to each data a corresponding shape and position in its image's referential. This structure is very strongly integrated in the page analyzer, to enable the fusion between the current image content and external information during page analysis, and to guarantee that, at each moment, external data is available and that creation, deletion and modification of elements contained in the visual memory is possible.

As an example, the content associated to some image containing a table of numbers could be composed of geometric objects indicating column types, recognized numbers and their values, suspicious numbers, etc. We note M I (t) the visual memory related to some image I at time t.

C. Architecture for Collection Processing

The iterative analysis of document pages is made possible thanks to the following components, illustrated in Fig. 1.

Strategy Module: It manages the invocation of the different processes during the analysis and their communication. This is the abstraction level where the analysis scenario is played, and where collection properties can be used: for instance, in [START_REF] Guichard | Exploiting Collection Level for Improving Assisted Handwritten Words Transcription of Historical Documents[END_REF], we grouped questions about visually similar words from various pages to reduce the number of manual work required to answer and perform the transcription.

Central Database: The central database stores the visual memories associated to each page in the whole collection. It provides a collection-centric view about the knowledge about the pages which progressively grows.

Page Analyzer: The page analyzer uses a document model to try to locate and recognize contents from a given image I and its associated visual memory M I (t). The iterative analysis scheme allows it to transform M I (t) and return an updated content for M I (t + 1) to the strategy module when done. At each iteration, it reprocesses the whole image (we integrated several optimizations to keep some results and avoid wasting too much time) and makes use of external information which was asynchronously provided. This permits to produce new structured results based on new intermediary results, all validated against the document model. In a directed interaction model, the page analyzer can generate questions indicating its lack of knowledge.

Human Interface: When solicited by the strategy module, the human interface enables a human operator to change the content of the visual memory.The page analyzer and the human interface must produce similar elements in the visual memory of each image, as they have to collaborate in such a way that the human operator may sometimes substitute himself to parts of the automated analysis to produce intermediary results.

IV. UNIFORM IMPLEMENTATION FOR DIRECTED AND SPONTANEOUS INTERACTION MODELS

In previous papers, we separately demonstrated the interest of a directed (see [START_REF] Chazalon | Iterative Analysis of Pages in Document Collections for Efficient User Interaction[END_REF], [START_REF] Guichard | Exploiting Collection Level for Improving Assisted Handwritten Words Transcription of Historical Documents[END_REF], and Sec. V-A) and of a spontaneous (see [START_REF] Chazalon | Iterative analysis of document collections enables efficient human-initiated interaction[END_REF] and Sec. V-B) interaction models. When used appropriately, they permit to reduce the amount of manual corrections required, for a given quality level, when compared to manual correction during post-processing.

This section shows how we integrated those two interaction models in a same page analyzer, thanks to a versatile implementation of the the directed interaction model which addresses not only specific cases where automatic error detection is possible, but also supports cases where no error detection is required. We briefly describe the DMOS-P system for which the prototype implementation was designed, then we focus on each interaction model and show they can be implemented using the same foundations.

A. DMOS-P Framework and Language

DMOS-P [START_REF] Coüasnon | Dealing with noise in DMOS, a generic method for structured document recognition: An example on a complete grammar[END_REF] is a concept-driven grammatical document analysis method. It uses a bi-dimensional extension of Definite Clause Grammars, called Enhanced Position Formalism (EPF), to describe pages. The following example illustrates its syntax: to recognize A, we try, at the top of the image, to recognize B, and if it fails, we try, at the bottom, to recognize C. Derivation is noted "::=", concatenation is noted "&&" and alternatives are expressed with multiples derivations for a same left-hand part. The "AT" operator is used for the positioning the analyzer's "reading head": it defines a zone in the image plan, and only elements which are present in this zone will be considered in the rule which follows this operator.

Like attribute grammars, rules have input and output parameters indicated by "+" and "-" signs, as illustrated by: recognizeNumber(+NumPos, -Value) ::= callClassifier(+NumPos, -Value).

B. DMOS-P Extensions for Directed Interaction

The directed interaction model we propose was introduced in [START_REF] Chazalon | Iterative Analysis of Pages in Document Collections for Efficient User Interaction[END_REF] and its efficiency was demonstrated in [START_REF] Guichard | Exploiting Collection Level for Improving Assisted Handwritten Words Transcription of Historical Documents[END_REF]. This model relies on the introduction of 3 new operators in the page description language. The semantics associated to those operators permit to express properties about pages. Their implementation allow to change the behavior of the page analyzer to automatically handle the interaction with a human operator or other components. It is based on an asynchronous information exchange made of questions and answers and using the visual memory, throughout the various page analyzer invocations at each analysis iteration.

The visual memory carries (and locates in the image referential) questions and answers using the containers:

Q(T ext, DataT ype) A(Data)
T ext gives information about the problem and DataT ype indicates the expected type for the content of the answer, which is stored in its Data attribute.

From a technical point of view, the operators were implemented using a continuation mechanism in the logical programming language used in DMOS-P. Continuations are, in this case, constructs very similar to the standard exception mechanism commonly used in imperative languages: our approach should be easily adapted to other systems.

Our implementation enables an asynchronous error detection and correction, and also allows to recover from errors during page analysis. In order to make a clear analogy between our new operators and exception handling, we chose names reflecting the behavior they produce during the analysis. Those operators are designed to: i) detect errors and ask questions; ii) ensure that answers are used by the analyzer to make progress instead of asking the same questions forever; and iii) make as much progress as possible in independent parts of the analysis if a problem arises.

1) Asking Questions (Error Detection): This operator is used to indicate that some part of the page cannot be understood properly. It can be to indicate that no valid interpretation could be proposed (all alternatives failed); or that recognized element are inconsistent with each other (non incrementing page numbers for example); or simply that the current case should better be processed by a human (not implemented, not reliable, etc.). The syntax and the algorithm describing the behavior of the page analyzer are: raiseQuestion(+Text, +Zone, +DataType)

When called, it 1) adds a question in the visual memory M I , with shape and position defined by +Zone to locate the issue; and 2) continues the analysis just after the latest invocation of catchQuestion. The following example illustrates how to ask a question if, in some mail we try to recognize, we cannot find the recipient.

mail ::= AT(top_right) && recipient(-R) && % use recipient information mail ::= raiseQuestion("Where is the recipient?", all_page, recipient).

Answering the questions is done outside of the page analyzer, in the human-machine interface, after the automatic step of the current iteration has been completed. Answers are stored in the visual memory and will be usable in the next iteration.

2) Using Answer (Error Correction):

This operator is used to indicate the part of the document model which need to be ignored when an appropriate answer exists in the visual memory. This part of the page model is supposed to produce a result, unless an error occurs and then the automated analysis will be replaced by a human operator, or another automated process. This operator is the one which enables both interaction models, as we will see in Sec. IV-C. Syntax and implementation algorithm are:

getAnswerOrTry(+DataType, -Result, +Rule)
where +DataType indicates the type of the content of acceptable answers, and +Rule is a rule which has a unique output parameter whose type is also +DataType. The type of the element contained in the answer is the same as the type of the result produced by the automatic rule.

When called, it looks at the current search position for an answer A(Data) in M I where the type of Data is +DataType. If it exists, the value of -Result is Data. Otherwise, it invokes the rule +Rule and the value of the output parameter of +Rule is used as value for -Result.

In order to avoid asking questions indefinitely, we need to ensure that if some appropriate answer was provided, the original question will not be asked again. To do so, we control that usage of raiseQuestion is only made inside rules annotated with a getAnswerOrTry with the same DataType. The following example illustrates this usage. 3) Continuing the Analysis (Error Recovery): This operator is used to indicate the scope of some error in the page model. Outside this scope, the analysis is not impacted by such error and can be continued if it occurs. This operator is noted:

catchQuestion(+Rule)
where +Rule is a rule which may have any parameter. When called, it invokes the rule +Rule and catches any interaction request raised with raiseQuestion in that rule. If no question is raised, the output parameters of +Rule are well defined, otherwise they are left uninstantiated. If, for some table recognition task we can process rows independently, then we could write:

C. Introducing Spontaneous Interaction

Spontaneous interaction relies on a simpler protocol than directed interaction. There is no need to detect errors and ask questions, and no need to recover from error. However, the ability to replace some parts of the automated analysis by a manual edition made by a human operator is necessary. Therefore, the getAnswerOrTry operator contains all the logic we need to enable spontaneous interaction: if we allow (thanks to some modification in the protocol defined in the strategy module) the human operator to provide information with the right type, located at the right place in the image referential, then the analyzer will automatically use it and will skip specific parts of the automated analysis process. As a result, we should not call "answers" every piece of information provided by a human operator, but we should simply say "information" about image content.

This approach allows to annotate specific parts of the document model which may be manually corrected by human operators during interaction steps. This allows to correct erroneous element, or add missing results in an intermediary structure, like in the following example: number_sequence ::= getAnswerOrTry(number, -Num, find1Number(-Num)) && AT(right_of(+Num)) && % loop until no more numbers

If the system misses a number, a human operator can add it in the visual memory and during the next analysis iteration, it will be used just like if it was detected in the image.

D. Implementation Advantages

The implementation we propose not only permits to introduce the two interaction model we propose in the same page analyzer, it also has two main advantages. The first advantage is to propose a clear separation between the page description and the implementation of the automated management of the interaction with some human operator (or other software components). It permits to keep the page description simple, and also to improve the interaction management without changing the page model. The second advantage is to integrate external information (humanprovided, system-provided, or both), exactly as if they were extracted from the image. As a result, we can assign a confidence score to external information, validate it against the document model, and use it to produce final results.

V. APPLICATIONS AND RESULTS

A. Directed Interaction for the Transcription of Documents from the 18 th Century

The directed interaction model was used to efficiently transcript handwritten words from sales registers of the 18 th century [START_REF] Guichard | Exploiting Collection Level for Improving Assisted Handwritten Words Transcription of Historical Documents[END_REF]. In the tests we made, 70 documents (1206 words) were processed, and extracted words were grouped by visual similarity in clusters (making use of redundancies of several words among pages), which were manually annotated if necessary. The iterative analysis permitted to reintegrate and validate external information (extracted using collection context) within a unique page model. This global approach diminished the human labeling of words from 21% (manual labeling of all suspicious elements) to 15% (-28%) for an overall recognition rate of 80%.

B. Spontaneous Interaction to Correct Number Segmentation Issues in Documents from the 18 th Century

The spontaneous interaction model was used to correct segmentation issues during the localization of numbers in an excerpt (50 pages with 1637 numbers) of a document dating from the 18 th century [START_REF] Chazalon | Iterative analysis of document collections enables efficient human-initiated interaction[END_REF]. Those numbers were separated by some special characters which where not always properly detected, and caused under-segmentation issues. In the tests we made, we allowed the human operator to review localization results, and to indicate the position of separators which were not detected. Using this approach, we were able to recover 40.6% of the missing numbers and to eliminate 30.0% of the erroneous zones. Correcting errors during the analysis stage allowed us to reduce by 29.8% the number of manual actions required to reach this quality level, when compared to a manual post-processing.

VI. CONCLUSION

Interacting with a human operator during the analysis stage is necessary to process old and degraded documents. While a directed interaction model may be the most efficient approach, as asking missing information enables to optimize human interaction, the error detection this model relies on is not always possible. Spontaneous interaction is a valuable alternative in those cases, as it also permits to reduce human workload when compared to post-processing. This paper show how we introduced both directed and spontaneous interaction models in the same page analyzer to be able to benefit from both approaches. The implementation we used enables an asynchronous error detection, correction and recovery throughout the iterations of the analysis. It is based on standard programming constructs very close to exceptions and should be easily adapted to other existing systems. Doing so, making use of external information during the analysis is very easy, and we were able to benefit from human-provided information, but also information extracted from collection context: redundancies of words among pages helped us to transcript documents from the 18 th century, with fewer manual actions than before.

A

  ::= AT(top) && B. % clause 1, tried 1st A ::= AT(bottom) && C. % tried if 1 fails

  recognizeNumber(+NumPos, -Value) ::= getAnswerOrTry(number, -Value, callClassifier(+NumPos, -Value)) callClassifier(+NumPos, -Value) ::= % inner machinery % fail if confidence is too low callClassifier(+NumPos, -Value) ::= raiseQuestion("What is this number?", +NumPos, number).

  rowlist ::= catchQuestion(one_row) && % detect other rows independently

  line_of_numbers ::= AT(left_of_line) && number_sequence.

ACKNOWLEDGMENT

This work has been done in cooperation with the Archives départementales des Yvelines in France, with the support of the Conseil Général des Yvelines.


Joseph Chazalon
email: joseph.chazalon@irisa.fr

Bertrand Coüasnon
email: bertrand.couasnon@irisa.fr

Iterative analysis of document collections enables efficient human-initiated interaction

Keywords: document analysis, degraded documents, document sets, iterative analysis, human interaction

Document analysis and recognition systems often fail to produce results with a sufficient quality level when processing old and damaged documents sets, and require manual corrections to improve results. This paper presents how, using the iterative analysis of document pages we recently proposed, we can implement a spontaneous interaction model, suitable for mass document processing. It enables human operators to detect and correct errors made by the automatic system, and reintegrates the corrections they made into subsequent analysis steps of the iterative analysis process. Thus, a page analyzer can reprocess erroneous parts and those which depend on them, avoiding the necessity to manually fix during post-processing all the consequences of errors made by the automatic system. After presenting the global system architecture and a prototype implementation of our proposal, we show that document model can be simply enriched to enable the spontaneous interaction model we propose. We present how to use it in a practical example to correct under-segmentation issues during the localization of numbers in documents from the 18th century. Evaluations we conducted on the example case show, on 50 pages containing 1637 numbers to localize, that the interaction model we propose can reduce human workload (29.8% less elements to provide) for a given target quality level when compared to a manual post-processing.

INTRODUCTION

Document analysis and recognition systems often fail to produce results with a sufficient quality level when processing old and damaged document sets, and require manual corrections by human operators to improve results. While most systems tend to rely on human interaction during post-processing stage, is it clear that the ability to interact with such automatic system during the analysis, and not after, can be valuable. For instance, in Fig. 1, our goal was to localize sales numbers, and segment them using separators we detected, then recognize them, optimize recognition results using the fact that, for each line, numbers are in increasing order, and associate the resulting number list to the sale name written on the left (previously recognized) in a database entry. When a separator (a coma here) is missed, a human operator can simply indicate the position of the missing separator at the right time so as to avoid the need for manual correction of subsequent errors in the final document structure, which would require costlier edition actions: localize each number, key its value, etc. This paper presents how, using the iterative analysis of document pages we recently proposed, [START_REF] Guichard | Exploiting Collection Level for Improving Assisted Handwritten Words Transcription of Historical Documents[END_REF][START_REF] Chazalon | Iterative Analysis of Pages in Document Collections for Efficient User Interaction[END_REF] we can implement a human-initiated, or spontaneous, interaction model suitable for mass document processing: it enables human operators to detect and correct errors made by the automatic system, and reintegrates the corrections they made into following analysis steps of the iterative analysis process. It triggers a reprocessing of erroneous parts and of those which depend on them, instead of having to fix during post-processing all the consequences of each error made by the automatic system. This iterative approach, which permits to process each document page as many times as needed, exhibits interesting properties regarding the four main challenges we identified for an efficient interaction with a human operator, in the context of analysis and recognition of massive document sets. Those challenge are: Challenge 1: Use asynchronous (non-blocking) interaction As sets of documents we process are often made of tens of thousands of pages, interacting with a human must not make the human operator wait for work nor block the system each time the human of the system need to communicate information about a given page to the other. In this paper, we consider cases where errors cannot be automatically detected. When errors can be detected, delaying interaction also enables to improve error detection by considering more elements, and to group, order and filter errors to show to human operators.

Challenge 2: Give the automatic system the ability to reconsider images, results and models Instead of only local and isolated corrections, the system we aim at should be able to use external information to complete or correct content detection (like in Fig. 1 were a coma is missed); to adapt or change the results linked to corrections a human operator made (like when using a language model to improve a sentence recognition: forcing a word value may change the global optimization result); and even to use new examples to improve content models or document structure models (but machine learning issues will not be discussed in this paper).

Challenge 3: Minimize the global human interaction cost

As mentioned previously, an automatic processing without interaction will require costly post-processing corrections. However, manual processing must be used as little as possible, even if it provides valuable information. Thus, it seems necessary to optimize human interaction usage to find the right balance between automatic and manual processing. We will show in this paper that interacting at the right time can be a way to achieve this.

Challenge 4: Keep a simple and unique document model, with as little interaction-related content as possible Existing systems use sophisticated document models to extract contents from difficult documents. Then, interaction must not increase model complexity with synchronization considerations, nor duplicate document knowledge, in particular between analysis and human interface processes to model-check answers supplied by a human. This paper first describe, in Sec. 2, how existing approaches for interactive analysis comply with those requirements. Then, in Sec. 3, we present the global system architecture and the spontaneous interaction model we propose. In Sec. 4 we detail a prototype implementation of our proposal, and illustrate on a practical example how this interaction can be used to correct under-segmentation issues during the recognition of sequences of numbers in documents from the 18 th century. Finally, we evaluate, in Sec. 5, the interest of this approach by measuring, for this example, the diminution of human work we obtained compared to post-processing.

RELATED WORK

There are few document analysis system which propose an interactive analysis model, or at least communicate with a human operators at some point of the analysis. PerfectDoc 3 is a post-processing tool which enables bulk correction of document structure (zone classification, reading order) and character recognition before producing the final structure of digitized magazines. While the human operator does not wait for tasks, and can detect and correct errors by himself, the system does not validate human information nor uses it to correct previous interpretations, as it could be done in an iterative analysis process.

The ability to interact at different times during the analysis is made possible by DocMining, 4 a very general framework for document processing where document processing units are successively invoked by a scheduling module following a predefined scenario. A persistent structure is associated to each document where each processing unit consumes and produces recognition data. DocMining permits a delayed interaction between components thanks to its central storage module, and human interaction can be easily implemented as new processing units. However, this system does not allow to reprocess a page to reconsider previous results using new information, as previously. Furthermore, document model seems implicit in this system which builds a pipeline of processes, and the specification of what information human operator can provide may be complicated.

The smartFIX system 5 takes another way: it uses a central repository to enable a delayed interaction, and also proposes the iterative recognition, optimization and control of documents using explicit model definitions: when human operators correct results, they are automatically checked against those document models. However, as few details are given about how external information is reintegrated during the analysis processes, it is hard to know whether human interaction could be more elaborated than just labeling suspicious fields: manual corrections seem to be made in the final document structure, and not at intermediary steps of the analysis process.

While existing approaches may permit an asynchronous interaction with a human operator at some point, they generally do not reprocess document pages, and then they do not use external information to improve previous results. Nagy and Veeramachaneni 6 identify this issue as the need for a durable interaction, which "immediately alters some system parameters and therefore affects how the system deals with new data", as opposed to an ephemeral interaction which "merely labels new patterns or modify the results of classification." Moreover, there is generally no optimization of human interaction usage in the manual post-processing of existing system. Finally, they seldom rely on document models, or do not explain how interaction can be modeled or expressed. As a result, an iterative analysis of document pages seems necessary to face the challenges we listed.

ARCHITECTURE AND INTERACTION MODEL

The iterative analysis approach we recently proposed 2 is based on an architecture and several properties we will first present shortly, before detailing what the spontaneous interaction model is.

Iterative Analysis Framework

The iterative analysis of document pages is made possible thanks to the following elements (illustrated in Fig. 2):

Strategy Module It is responsible for the invocation of the different processes during the analysis and their communication. This is the abstraction level where the analysis scenario is played, and it could imply to reprocess many times the same page as long as new information is available.

Visual Memory It is a persistent data structure associated to each page which is used for information exchange between processes, but also during document analysis in order to reintegrate external information and use it. It is an associative structure that each process can change, and which gives to each data a corresponding shape and position in its image's referential. We note M I (t) the visual memory related to the image I at time t.

Central Database

The central database stores the associated visual memories for each page in the whole collection. It provides a collection-centric view of information stored which can progressively grow.

Page Analyzer

The page analyzer uses a document model to try to extract relevant information from an image. In an iterative analysis scheme, it is invoked with an image reference I and the associated visual memory M I (t), and returns M I (t + 1) to the strategy module when done. At each iteration step, it reprocesses the whole image (we integrated several optimizations to keep some results) and makes use of external information. This key feature permits to produce new structured results, which are valid according to the document model.

Human Interface When solicited by the strategy module, the human interface enables a human operator to change the content of the visual memory of some image, like any other process. In this paper, we consider this interface from a theoretical point of view, as we will focus on the implementation of the page analyzer. Fig. 2 shows a single step, repeated as many times as needed, of information exchange (for a given page) between a page analyzer and a user interface in a simple strategy which triggers each component one after another for each page. The communication with the central database is omitted for brevity. At time t, the strategy modules first invokes the page analyzer on the image I, with the memory M I (t). The strategy module gathers M I (t + 1) after the analysis, and transfers it to the human interface, which, in turn, produces M I (t + 2) and sends it back. Page reprocessing may be seen as costly, but it is necessary to be able to change the behavior of the page analyzer on a given page. Moreover, keeping intermediary results, like recognition results, can be easily implemented.

Human Interface Central Storage

Strategy Module 1: process(I, M I (t))

2: M I (t + 1) 3: process(I, M I (t + 1))

4: M I (t + 2)
Figure 2. A single step (repeated as many times as needed during the iterative analysis) of a simple dialogue strategy between a page analyzer and a human interface, showing the implied components of the architecture and the visual memory MI associated to the image I.

Spontaneous Interaction Model

Using the iterative analysis we can build many information flows between the human interface and the page analyzer to propose several forms of asynchronous interaction. In a previous paper, 2 we presented a directed interaction model. This approach allowed a page analyzer to ask question the human operator when it detected a problem. The human operator answers back, and model constraints embedded in the question structure ensure that his answer will be valid and properly reintegrated according to the document model.

The current paper focuses on a spontaneous interaction model. This new approach deals with cases where the directed interaction cannot be used, in particular when errors cannot be automatically detected and localized during the page analysis. At some point in the analysis process, the human operator is allowed to view and change some parts of the content of the visual memory of images. Those changes are used in later automatic page processing, and will hopefully help the page analyzer to improve its response.

While it provides more flexibility, the main drawback of this approach is to make the reintegration of external information to the analysis process and the final structure more difficult. The reason is that human operators have few constraints on information they provide, and new elements may not comply with the document model: they could be at unexpected positions, or have unexpected values. We will see in the next sections that this spontaneous interaction model still permits an early correction of errors, which is valuable.

IMPLEMENTATION AND EXAMPLE

This section presents how a spontaneous interaction model can be implemented and used in a rule-based page analyzer based on the DMOS-P approach, [START_REF] Coüasnon | Dealing with noise in DMOS, a generic method for structured document recognition: An example on a complete grammar[END_REF] then it shows on an example how this mechanism can be used.

DMOS-P Framework and Language

DMOS-P 7 is a concept-driven grammatical document analysis method. It uses a bi-dimensional extension of Definite Clause Grammars, called Enhanced Position Formalism (EPF), to describe pages. The following example illustrates its syntax: to recognize A, we try, from the top of the image, to recognize B, and if it fails, we try, inside the bottomPart, to recognize C. Derivation is noted "::=", concatenation is noted "&&" and alternatives are expressed with multiples derivations for a same left-hand part. Operators are: "AT" for the positioning; and "IN..DO" for spacial restriction (to limit the part of the image where a rule can be applied).

Information Representation

Information stored in the visual memory associated to an image is made of elements which can be represented by the following construct, where: Zone represents the localization of the element in the current image's coordinate system; M arker is a tag, like m separator or m number, which enables to distinguish different information types; and Data is the useful content according to the information tag, like coma for separators, or [15, 115, 16] for numbers (hypothesis list). In the spontaneous interaction model, those contents are provided by the human operators to guide or correct the behavior of the automatic system on a given image.

MI (t) = {Zone1 → (M arker1, Data1); Zone2 → (M arker2, Data2)}

DMOS-P Extension for Spontaneous Interaction

Spontaneous interaction is made possible by adding the following operator to the document model language, and providing an implementation for this operator which automatically manages the way external information is used to adapt the page analyzer's behavior.

SPONTANEOUS(+Marker, +Rule)

This construct automatically checks for some data in the visual memory of the current image before choosing whether the rule Rule should be applied or not. The content of the memorized element will be used instead of applying the rule in the parts of the image indicated by the Zone component of the memorized construct, if the Marker tag of the element in the visual memory corresponds to the one expected.

This approach allows to annotate specific parts of the document model to identify those which can produce erroneous results that may be manually corrected by human operators during interaction steps. As a result, an interactive detection and correction of errors through several analysis steps (automatic analysis, asynchronous interaction, then automatic analysis again) is made possible. The key advantage is that it enables to substitute human processing to automatic processing for some parts of the document model in a systematic and simple way: as soon as a rule is "decorated" with the previous extension, this behavior is available with not extra cost, as all information fusion and decision issues are handled automatically. Some improvement of the human interface may be needed to handle new data types.

Example

This example shows a very simple grammar (inspired by a one we use) which processes images like the one in Fig 1 : starting at the top of the page, it locates a text line and uses its position to extract sales numbers in this restricted area, and goes on until no more text line is found. Number extraction is done by first detecting all the separators of the line (coma, "à", etc.) and second locating the numbers using the position of those separators. The detectAllSeparators rule is a while-like construct which build a list of all the results got from the separator rule. In order to enable a spontaneous interaction for the localization of separators, the only thing to to is to "decorate" the separator(-Sep) line in the detectAllSeparators rule definition. Let us now suppose that the image we want to process contains only 3 numbers; "11", "22" and "33", and that those number are separated by comas. If, for any reason, the last coma was not detected, the two last number may not be properly segmented and later recognition will fail. In the case of a collection with a single page, with a simple analysis strategy which ask successively the page analyzer and the human interface to modify the memory content, the following table illustrates a possible behavior. We consider here that the content of the visual memory is the observable system's behavior, and that extracted numbers and separators are stored for human analysis (the way it was done is omitted in the grammar description for simplicity).

Grammar without interaction capability

Time t i Description

Visual memory content M I (t i )

t 0
The analysis starts. ∅

t 1
The page analyzer tried to locate the and the numbers, but it missed one. The memory contains 2 numbers and 1 separator elements. The first number ("11") at zone Z N 1 is correct, and the second ("2233") at zone Z E is a fusion of the 2 last numbers.

{Z N 1 → (m number, "11");

Z S1 → (m separator, coma); Z E → (m number, "2233")} t 2
The human operator has controlled the content localization and adds the missed separator at position Z S2 , while removing the erroneous number ("2233").

{Z N 1 → (m number, "11");

Z S1 → (m separator, coma); Z S2 → (m separator, coma)} t 3
The system reprocessed the image and used new information to properly segment the two numbers ("22" and "33"). As the number "11" was already in memory, the system did not reprocess this number, saving CPU time. This simple optimization is used for real analysis tasks.

{Z N 1 → (m number, "11");

Z S1 → (m separator, coma); Z S2 → (m separator, coma); Z N 2 → (m number, "22"); Z N 3 → (m number, "33")}
As we can see, the spontaneous interaction model can be very easily used to enrich the document model and specify which parts of the analysis may be altered by human operators. To integrate this approach in an existing document analysis system, the only required elements are: the simple architecture we presented, which allows an iterative analysis of document pages; a visual memory to exchange and reuse information; and a page analyzer based on a document model language containing an operator similar to the one we presented.

EVALUATION ON A PRACTICAL CASE

The goal of this last section is to show that spontaneous interaction during the analysis of documents permits to reduce human workload while being easy to integrate in some page analyzer. We isolated a very narrow part (number zones localization) of a real document analysis we performed on French documents dating from the 18 th century, in order to be able to evaluate the influence of the interaction model we propose, and to avoid mixing human actions with different costs. Real strategies mix various interaction schemes but are hard to evaluate.

Dataset

We used 50 images of old documents dating from the French Revolution (18 th century), which contain text lines indicating a sale category followed by a sequence of numbers indicating sales references. Those numbers (1637 in the 50 pages) are separated by a symbol (coma or "à" which indicates a range) or, sometimes, a blank space. Fig. 1 shows an excerpt of a page, and contains 8 numbers: 6 for the first sale type (or line), and 2 for the second. For each page, we know the real position of each number (its bounding box) thanks to a manual annotation.

Protocol

We used a page analyzer similar to the one presented in the example in Sec. 4.4: using the image and its associated memory, it tries to localize the separators and the numbers the image contains, and stores them in the visual memory. It permits a spontaneous interaction, as presented in the previous example in Sec. 4.4. We used the following analysis strategy. First, all images are processed with the page analyzer (first iterative step, first automatic analysis). We kept a snapshot S 1 of the content of all the visual memory structures before human interaction for later analysis. Then, a human operator was able to change visual memory contents of all images (second iterative step, interaction). Finally, all images are reprocessed with the same page analyzer (third iterative step, second automatic analysis). We kept another snapshot S 2 after the second automatic analysis.

As explained in introduction, we limited the actions performed by the human operator to avoid mixing different actions costs. He was only allowed to correct under-segmented numbers in the following way: he reviewed analysis results and located under-segmented numbers (as in Fig. 1), then he removed erroneous elements (separator and numbers) in this area and added one (or more) separators (of fixed size) at the right positions. He did not locate nor recognize numbers, at it should be done automatically during the reprocessing of the page.

Analysis

Our goal was to measure the improvement with spontaneous interaction for the number localization task while evaluating the human work cost it implied, and compare it with the human work cost which would have been necessary to reach the same quality by localizing the numbers directly (post-processing ephemeral interaction).

Localization quality was estimated by counting the zones matching the ground truth as follows:

if surface(I) surface(E) > T and surface(I) surface(R) > T then R matches E else R does not match E
where surface(Zone) is the number of pixels in Zone; E is the expected sale number zone (ground truth); R is the zone actually localized (by the automatic system); I = E ∩ R is the intersection of expected and real zones; and T ∈ [0; 1] is a threshold. A threshold of 0.99 (perfect match) allowed us to know how many sale number zones were removed and added between S 1 and S 2 , and we used a threshold of 0.80 (acceptable match) when comparing S 1 and S 2 to the ground truth. This value was not finely tuned but presented a good compromise between too permissive and too restrictive: as the old-fashioned writing style in the document we processed tend to produce very long figures for the numbers "9" and "7" (as in Fig. 1), and missing the very lower part of them has little impact on number recognition.

Spontaneous interaction cost was estimated by counting the number of separators added, as it represents the worst case estimation of the count of edition actions (locate an under-segmentation zone + clear it + add a separator). The post-processing interaction cost was estimated using the count of zone numbers it would have been necessary to add to reach the same quality level. Quality improvement Our ground truth reference contains 1637 number zones. Before the spontaneous interaction stage (in S 1 ), 1339 numbers zones are properly localized, 233 (14.8% of detected zones) are erroneous (under-segmented, noise, etc.) and 298 are missing (not detected). In S 2 , after the spontaneous interaction stage, which corrects only under-segmentation, and the reprocessing of pages, 1460 number zones are well localized, 169 (10.4% of detected zones) are erroneous and 177 are still missing. The proposed approach permits an improvement of 7.5% (+121 zones) of the localization rate (-40.6% of missing zones) while also permitting to reduce the relative amount of erroneous zones (-30.0% of erroneous zones). Fig. 3 illustrates this gain.

Results

Cost reduction Between S 1 and S 2 , the human operator created 85 new separators, which means that 85 edition actions were performed. Manual post-processing would have required to perform the deletion of the elements detected in 85 erroneous zones, and the careful creation of 121 numbers (and their manually annotation, as the recognition stage is finished). If we neglect the preliminary deletion of erroneous element which could be implicit in both scenarios, we can conclude that, to reach the same upper quality level for this task, the spontaneous interaction scenario permits to reduce human workload by 29.8%, without even considering that manual number localization is costlier than separator localization.

Discussion

To build the ground truth, we actually used the results of the automatic analysis after spontaneous interaction and manually corrected the remaining errors. The spontaneous interaction stage roughly lasted 45 minutes (121 corrections, ∼22.3 sec/err), and the post-processing was more than 1 hour 30 minutes long (177 corrections, ∼30.5 sec/err). This estimation depends on lot on the human interface, but illustrates that detecting and correcting analysis errors at the right time can reduce the human workload (cost and number of corrections required).

CONCLUSION

We presented how to enable asynchronous interactions with human operators during the analysis stage of document processing, using an iterative analysis approach we recently proposed: information associated to an image can be stored and reused later, allowing a non-blocking interaction over sets of pages suitable for mass document processing (it addresses the challenge 1 of the introduction).

We introduced a spontaneous interaction model, explained how it can be implemented in a rule-based page analyzer, and showed that this model permits to make use of external information provided by a human operator to guide or to correct the system behavior (or response) for a given image. This contribution permits to detect and correct errors asynchronously with a human, and leads to a reconsideration of image content or of previous results during later reprocessing: it becomes possible, for example, to add a separator which does not exist in the image to improve the segmentation of numbers (a step toward challenge 2). We showed on an example, which was simple enough to permit an easy evaluation, that an appropriate use of spontaneous interaction could reduce human interaction cost for a given task: we asked a human operator to correct cases where number zones were under-segmented by providing the missing separators. It permitted to avoid the precise localization of number zones, but also their manual annotation as their automatic recognition remains possible during later reprocessing (a contribution to challenge 3).

Finally, we illustrated how a document model can be kept simple by annotating the parts of the automatic analysis where the human may interfere, or substitute himself to the automatic process, with only one new language operator. A document model can therefore include many annotations enabling a spontaneous interaction for various information types, while the approach we proposed hides all the communication issues using a visual memory and a systematic approach to interact with a human operator (an answer to challenge 4).

Figure 1 .

 1 Figure 1. Number and separator detection automatically produced for an excerpt from a page of a document dating from the 18 th century. On the first line, a separator was missed and caused the under-segmentation of the two last numbers.

A

  ::= AT(top) && B. % clause 1, tried first A ::= IN(bottomPart) DO(C). % tried if clause 1 failsLike attribute grammars, rules have input and output parameters indicated by "+" and "-" signs: recognizeNumber(+NumPos, -Value) ::= callClassifier(+NumPos, -Value).

  start() ::= AT(topPage) && detectTextLinePosition(-Line) && IN(lineArea +Line) DO(extractSalesNumbers()) && AT(under +Line) && % read other lines... extractSalesNumbers() ::= detectAllSeparators(-SepLst) && extractNumberBetweenSep(+SepLst). detectAllSeparators(-[Sep|OtherSep]) ::= separator(-Sep) && detectAllSeparators(-OtherSep). detectAllSeparators(-[]). Grammar allowing spontaneous interaction start() ::= AT(topPage) && detectTextLinePosition(-Line) && IN(lineArea +Line) DO(extractSalesNumbers()) && AT(under +Line) && % read other lines... extractSalesNumbers() ::= detectAllSeparators(-SepLst) && extractNumberBetweenSep(+SepLst). detectAllSeparators(-[Sep|OtherSep]) ::= SPONTANEOUS(+m separator, % Only change separator(-Sep) ) && detectAllSeparators(-OtherSep). detectAllSeparators(-[]).

Figure 3 .

 3 Figure 3. Comparison of the localization of number zones before interaction (S1) and after interaction and reprocessing (S2), showing a reduction of both missing and erroneous (noise) zones.

ACKNOWLEDGMENTS

This work has been done in cooperation with the Archives départementales des Yvelines in France, with the support of the Conseil Général des Yvelines.