Phil Ippe M Ul L Er

Er Gos Afant Enos

Pascal Denis
email: pascal.denis@inria.fr

N Ichol As Asher
email: asher@irit.fr

Constrained decoding for text-level discourse parsing

Keywords: Discourse Structure, Discourse Parsing, Dependency Structures, Constrained Decoding, A*

This paper presents a novel approach to document-based discourse analysis by performing a global A* search over the space of possible structures while optimizing a global criterion over the set of potential coherence relations. Existing approaches to discourse analysis have so far relied on greedy search strategies or restricted themselves to sentence-level discourse parsing. Another advantage of our approach, over other global alternatives (like Maximum Spanning Tree decoding algorithms), is its flexibility in being able to integrate constraints (including linguistically motivated ones like the Right Frontier Constraint). Finally, our paper provides the first discourse parsing system for French; our evaluation is carried out on the Annodis corpus. While using a lot less training data than earlier approaches than previous work on English, our system manages to achieve state-of-the-art results, with F1-scores of 66.2 and 46.8 when compared to unlabeled and labeled reference structures.

Introduction

Discourse analysis involves the identification of coherence relations between discourse units, which can be either elementary ones-typically clauses or sentences-or complex ones, spanning larger chunks of text. These larger units play similar roles to elementary ones. Coherence relations categorize discourse units in terms of their argumentative, thematic or causal links to other units. Together these relations and the units they relate form the global structure of a discourse. This structure is important as it reflects the thematic organization at various levels of granularity, and constrains semantic interpretations, for instance with respect to anaphora resolution or temporal interpretation. Discourse processing is thus a crucial part of natural language understanding, and it has potentially many applications-opinion detection and classification, question answering, information extraction, recognizing textual entailment, evaluating text coherence, or knowledge extraction to name a few [START_REF] Stede | Discourse Processing[END_REF][START_REF] Verberne | Evaluating discoursebased answer extraction for why-question answering[END_REF][START_REF] Somasundaran | Supervised and unsupervised methods in employing discourse relations for improving opinion polarity classification[END_REF][START_REF] Lin | Automatically evaluating text coherence using discourse relations[END_REF][START_REF] Gerber | Open-domain commonsense reasoning using discourse relations from a corpus of weblog stories[END_REF] Producing a discourse structure automatically is a complex task, however. Coherence involves syntactic and lexical factors, and relies heavily on the semantic interpretation of its parts. Most existing work tends to focus on restricted aspects of the full problem.

The task of building a discourse structure involves three subtasks: (1) identifying discourse units (DUs), ( 2) "attaching" DUs to one another, and (3) labeling their link with a coherence relation. Of these, the first one is usually considered easiest (see for instance [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF], the second is arguably the hardest; and as a consequence, researchers have focussed attention on the third one, labelling discourse relations [START_REF] Lin | Recognizing implicit discourse relations in the Penn Discourse Treebank[END_REF][START_REF] Feng | Text-level discourse parsing with rich linguistic features[END_REF][START_REF] Sporleder | Using automatically labelled examples to classify rhetorical relations: An assessment[END_REF][START_REF] Wellner | Classification of discourse coherence relations: an exploratory study using multiple knowledge sources[END_REF][START_REF] Louis | Using entity features to classify implicit discourse relations[END_REF]. Research on discourse structure also divides into two orthogonal categories: some researchers limit themselves to intra-sentential discourse structure [START_REF] Wellner | Classification of discourse coherence relations: an exploratory study using multiple knowledge sources[END_REF][START_REF] Sagae | Analysis of discourse structure with syntactic dependencies and datadriven shift-reduce parsing[END_REF][START_REF] Joty | A novel discriminative framework for sentencelevel discourse analysis[END_REF]; others tackle the problem of identifying the full discourse structure of a text [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF][START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF]. The latter rely on "local" models to predict potential coherence relations, assuming independence between the decisions, and build the structure guided by greedy heuristics. The exception is [START_REF] Baldridge | Probabilistic head-driven parsing for discourse structure[END_REF], who use a generative model, in the case of specific task-oriented dialogues.

In this paper, we propose a more general approach to discourse structure prediction at the document level: (i) it performs a global search over the space of possible structures and optimizes a global criterion over the set of potential coherence relations; (ii) it can also take into account linguistically motivated constraints on the predicted structure. Specifically, our approach relies on the A* search algorithm, which is particularly well suited in allowing to capture constraints such as the so-called Right Frontier Constraint (or RFC), various versions of which have been a staple of theoretical linguistic approaches to discourse [START_REF] Polanyi | A formal model of the structure of discourse[END_REF].

Another contribution of our paper is to provide a simple formalism that captures many of the commonalities across particular representation models for full discourse structure by considering a more general graph-based model, which can nevertheless integrate framework specific constraints. Previous work relies on several different discourse representation theories and corpora-e.g., the Penn Discourse Tree Bank (PDTB) of [START_REF] Prasad | The Penn Discourse TreeBank 2.0[END_REF], which assumes a light-weight linear structure; Rhetorical Structure Theory (RST) and the RST treebank [START_REF] Carlson | Building a discourse-tagged corpus in the framework of rhetorical structure theory[END_REF], which assumes a constituent tree structure; Segmented Discourse Representation Theory (SDRT) from which derive the Discor and Annodis corpora [START_REF] Baldridge | Annotation for and Robust Parsing of Discourse Structure on Unrestricted Texts[END_REF][START_REF] Afantenos | An empirical resource for discovering cognitive principles of discourse organisation: the annodis corpus[END_REF], with directed acyclic graphs; or GraphBank [START_REF] Wolf | Coherence in Natural Language: Data Stuctures and Applications[END_REF], with little if any constraints on a graph-based structure.

Incidentally, we also deliver the first discourse parsing system for French. Our evaluation is performed on the ANNODIS corpus [START_REF] Afantenos | An empirical resource for discovering cognitive principles of discourse organisation: the annodis corpus[END_REF].

The paper is structured as follows. Section 2 positions in more detail our work with respect to the existing literature on discourse parsing. Section 3 describes our approach to discourse structure "decoding". Section 4 introduces the data we use from the Annodis corpus, and sections 5-6 present our experiment design. Finally section 7 reports our results and an analysis, especially with respect to comparable work.

Related work

Apart from a few exceptions, research on automatic discourse analysis has focused on specific aspects of the general problem. Most work concerns the task of discourse relation labeling between pairs of DUs. Examples of this line of work are: [START_REF] Marcu | An unsupervised approach to recognizing discourse relations[END_REF], [START_REF] Sporleder | Exploiting linguistic cues to classify rhetorical relations[END_REF] and [START_REF] Lin | Recognizing implicit discourse relations in the Penn Discourse Treebank[END_REF]. This setting makes an unwarranted assumption, as it assumes one decision concerning labeling is independent from another. Alternatively, researchers have considered the task of predicting full discourse structures, but only at the sentence level. An example of sentence-level discourse parsing is [START_REF] Soricut | Sentence level discourse parsing using syntactic and lexical information[END_REF], which makes use of dynamic programming along with a standard bottom-up chart parsing. In this case, probabilities for each sentence level discourse tree are calculated as the product of the probabilities for the structure and the relation. More recently, [START_REF] Sagae | Analysis of discourse structure with syntactic dependencies and datadriven shift-reduce parsing[END_REF] has developed a shift-reduce algorithm for intra-sentential discourse analysis. Their stack contains the current discourse subtree and it consumes a sequence of EDUs. Like [START_REF] Soricut | Sentence level discourse parsing using syntactic and lexical information[END_REF], [START_REF] Sagae | Analysis of discourse structure with syntactic dependencies and datadriven shift-reduce parsing[END_REF] use the RST Discourse Treebank. RST trees are "lexicalized" through head percolation using the so-called nucleus/satellite distinction. The shift operation removes the next EDU from the sequence and pushes a subtree containing only that EDU onto the stack. The reduce operation is either unary or binary: unary reduce just pops the stack and pushes a subtree with the popped item as the only child and it's lexicalized head as its mother, while the left and right binary reduce operations pop two nodes, attach them and push them back-left and right being used to judge nuclearity.

There are two main reasons why the full task of discourse parsing has eluded NLP researchers. The first is that annotating discourse structures is a very expensive procedure. There are but modest amounts of data that have been annotated, and structured prediction views each document as a single instance. Consequently, training is not very reliable. The second reason is that the two largest discourse-annotated corpora (the PDTB and the RST corpus) enforce strong constraints on the structure (namely attachment to adjacent DUs) and are thus naturally biased toward local approaches where only attachment to the left or right DU should be considered, ignoring the interdependence of local decisions. This problem can be tackled more easily at the sentence-level, where structures are simpler with only a few discourse units. Sentences can be considered independently of one another, and provide more training instances and more reliable predictions.

Among the few attempts to build document-level discourse parsers are [START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF] and duVerle and [START_REF] Prendinger | A novel discourse parser based on support vector machine classification[END_REF]. Like [START_REF] Sagae | Analysis of discourse structure with syntactic dependencies and datadriven shift-reduce parsing[END_REF], Subba and Di Eugenio (2009) use a transition-based approach. As in the intra-sentential work cited above, the shift operation places the next segment on top of the stack, but there is only a binary reduce operation which may result in the triggering of more reduce operations. In case no reduce operation is triggered then a shift is automatically performed. Consequently, only the reduce operations need to be learned. In case that the input string is empty but the stack is not, a reduce with the relation LIST is (continuously) performed. [START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF] use rich linguistic features and Inductive Logic Programming for training. All results are reported on an in-house corpus, and they barely surpass the baseline that consists in always attaching to the last DU. duVerle and [START_REF] Prendinger | A novel discourse parser based on support vector machine classification[END_REF], and its sequel [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF] both rely on locally greedy methods, and in line with all previous works, treat attachment prediction and relation label prediction as independent problems. Specifically, they start by computing probabilities of attachments for adjacent pairs of EDUs and greedily select the highest scoring. A second classifier, applied in cascade, determines the relation for the two DUs. The pair is replaced by the created "span" and the procedure continues in a bottom up way. The recent work of [START_REF] Feng | Text-level discourse parsing with rich linguistic features[END_REF] extend this approach by additional feature engineering but is restricted to sentence-level parsing. These three papers all use the RST-DT. [START_REF] Joty | A novel discriminative framework for sentencelevel discourse analysis[END_REF] deserve special mention because they consider inter-dependence of local decisions, but nonetheless limit themselves on the level of intra-sentential parsing. As a first step, they compute the joint probabilities for structure plus relation for all possible combinations of structures and relations within a single sentence. For the computation of those joint probabilities they use a Dynamic CRF. Once all the possible joint probabilities have been computed, they perform a classic CKY chart parsing using dynamic programming. They use features representing text organization, dominance sets, contextual information and hierarchical dependencies. This is a very interesting approach but it does not easily scale up for the whole text, at least using a CRF-like approach. This is where we distinguish ourselves by adopting a local model and then a constraint-based decoding mechanism for identifying the optimal global structure.

Another relevant paper [START_REF] Baldridge | Probabilistic head-driven parsing for discourse structure[END_REF] presents a comparable problem, namely predicting the rhetorical structure of dialogues, from the Verbmobil corpus. Dialogues are considered as documents with relations between utterances, and the authors train a PCFG to produce tree representations of the dialogue structure. It is unclear how this approach, which works on very specific task-oriented dialogues, would perform in a more general framework, especially since they require some semantic features that were annotated manually.

Discourse decoding under constraints

In order to recover the rhetorical structure of a document, we take as our starting point two locally-trained classifiers predicting the attachment of discourse units and the labelling of their relations, much in the same way as [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF][START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF]. Our models are also "local" in the sense that the training criterion that they optimize is still local and the features they use are defined over pairs of DUs. But we differ from previous approaches in the way we use the outputs of the local classifiers to predict the overall discourse structure, as well as in the use of constraints (such as the Right Frontier Constraint) during this "decoding" phase. Yet another difference is that we predict attachment decisions and relation labeling decisions in a joint fashion, rather than in pipeline as it is done in previous work.

Before getting into the details of the decoding, let's first consider the type of structure we intend to produce. An important challenge with discourse analysis is the lack of consensus among discourse theorists as to the relevant type of representations that one should use to encode discourse structure. These theoretical differences are directly reflected in the various existing discourse annotation corpora, as most of them are based on one particular theoretical framework. As a result, the different existing systems being trained on a specific resource are framework-specific. One of our goals in this paper is to abstract away from these differences and provide a more generic approach to the problem of discourse parsing.

Consider RST-DTs. RST representations are similar to constituent-based syntactic trees, since relational structures are recursively built bottom-up from elementary discourse units to form complex discourse units and adjacency is enforced at each level. Users of RST also often assume the so-called "nuclearity principle", by which complex RST segments have a distinguished EDU as a sort of head, a procedure similar to head percolation in syntax, when converting to a constituent-based to a dependency based representation. Other frameworks like SDRT or GraphBank assume more general structures (respectively directed acyclic graphs and graphs). One uniform way to capture commonalities between these different types of representation is to convert them into a dependency graph between EDUs. Many of the differences between frameworks can be encoded with different, additional structural constraints. To capture RST up to complex segments, one translates an RST tree recursively taking the nuclearity principle into account. SDRT also has complex segments, and we address how they can be dealt with in section 4. In SDRT, discourse interpretation is supposed to be an incremental process that respects a "right frontier constraint" (RFC) [START_REF] Polanyi | A formal model of the structure of discourse[END_REF]: discourse units are supposed to be processed one by one, and the current unit can only be attached to a node on the "right frontier" formed by the last introduced node and nodes "above" it (assuming a hierarchical structure). These theories distinguish between relations that are "coordinating" (additive relations, also called multinuclear in RST) or "subordinating" (expanding relations, or nuclear-satellite in RST). In that case subordinating relations add a level to the discourse hierarchy while coordinating stay at a given level of granularity.

Dependency structures have become very prominent for syntactic parsing, and a number of approaches have been applied successfully to the problem. So, a natural question is whether techniques developed therein could be directly used for discourse analysis. As noted, there have been some initial attempts at adapting shift-reduce parsers to discourse. An alternative to transition-based parsing is the graph-based parsing proposed e.g. by [START_REF] Mcdonald | Non-projective dependency parsing using spanning tree algorithms[END_REF]. This approach is particularly appealing since it builds upon an exact search procedure for finding the best possible dependency tree: it is the Maximal Spanning Tree (or MST) on the fully connected graph defined on the sentence words. One could in principle use this approach for discourse parsing, but as with transition-based parsing, there is no obvious way to easily integrate global constraints as the RFC.

Our solution is to express the problem of discourse parsing as a state-space search with different state-space definitions and constraints, and apply a general A* exploration strategy. A* search is shortest-path search through the state of possible results (dependency graphs in our case), which orders the search considering an estimated cost of a partial solution as the sum of the cost of the part of the solution already built and the estimated cost of the remaining part to be built. Transitions between states should be here the choice of an edge between two DUs, to be added to the desired solution. Since transition costs must be additive, the cost of an edge will be -log its probability, as given by the models for attachment and relations. The general form of such a search is shown as algorithm 1. The estimation, or "heuristics", guarantees an optimal solution under certain conditions, the most common being that the heuristics is "admissible", i.e. it always underestimates the cost of the remaining exploration.

Algorithm 1 General A* decoding. S 0 is an initial state, problem dependent. Functions g and h are the cost of 'current' so far, and the estimated cost. In contrast to the greedy approaches of [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF][START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF], we have more control on the solution yielded by the procedure. With an admissible heuristics, A* guarantees an optimal solution with respect to the cost function on state transitions (here, the probability of a given relation between two discourse units). Limited search can further be implemented as a special case if the state-space proves to be combinatorial, by restricting A* with a beam (a pending queue of fixed size, but then losing completeness). A* has also been used in syntactic parsing because of these advantages [START_REF] Pauls | K-best a* parsing[END_REF]. Another advantage offered by A* search and used in the previous paper, lies in its ordering of hypotheses, that easily yields the n best solutions by continuing the exploration of the state space. This is useful for instance to apply reordering or ranking techniques.

The most delicate aspect of using A* is in the heuristics chosen to guide the search. We will discuss possible heuristics in section 6, as they are rather orthogonal to the current discussion.

The state-space exploration works as an incremental building of a solution and must specify mainly: (1) a starting state for building a solution and (2) allowed states from a given state. For instance an MST approach could be implemented (inefficiently, though) with a starting state consisting of just one discourse unit, or as a fake node related to the others depending on the probability of a segment to be the head of the discourse (as is done in syntactic parsing). Following states could then only add a relation between a new node and one and only one of the already chosen nodes, until all nodes are attached.

To implement the RFC, we only need to restrict the previous procedure so that new nodes can only be attached to the set of accessible nodes assuming the RFC, see for details algorithm 2.

In case one wants to stay within the RST framework, the starting state would be empty, and new states should be built by adding a relation between two adjacent active units. Active units are all elementary units at the beginning, each EDU being replaced by a complex one as they are attached during the decoding procedure.

Algorithm 2 Example state generation for building a tree incrementally under the RFC constraint, taking the first segment as the root. For simplicity, (1) relations are ignored since the best for each edge are incorporated in the cost evaluations, and (2) no difference is made between additive or expanding relation for updating the right frontier RF. The treatment below correspond to expanding relations only. For additive relations, the new attached unit replaces the attachment point in the RF, so the RF update should be new.RF = new.RF[:k-1] + [next]. Let I = [u 1 , ..., u n ] the list of elementary discourse units, in text order. And let a general state S = 〈V, E, RF 〉 where V is the list of DU to be attached, E is a set of edges making up a tree, and RF is a list of accessible nodes according to the right frontier constraint. We will note the state parts as S.V, S.E and S.RF. Initially, S = 〈I[2 :], , [u 1 ]〉, as we take the first segment as the root. The following will generate a tree structure respecting the RFC, approximating a SDRT DAG:

The corpus used

A number of different corpora have been annotated with discourse structures. These differ in the discourse formalism they are grounded in, and from our perspective in the type of constraint they impose on the attachment of DUs. The one with the heaviest constraints on discourse attachment, and consequently the simplest structures, is PDTB [START_REF] Prasad | The Penn Discourse TreeBank 2.0[END_REF], as most attachment are between adjacent EDUs, creating no further complex structures. To be fair, the main focus of PDTB is not discourse structure per se, but instead the study of explicit and implicit discourse relations-as signaled by discourse markers or absence thereof. Based on Rhetorical Structure Theory (RST) [START_REF] Mann | Rhetorical Structure Theory: A Framework for the Analysis of Texts[END_REF][START_REF] Marcu | The Theory and Practice of Discourse Parsing and Summarization[END_REF], the RST Discourse Treebank (RST-DT) does have recursive structures, but it imposes heavy constraints by still enforcing adjacency [START_REF] Marcu | The Theory and Practice of Discourse Parsing and Summarization[END_REF]. More specifically, in RST an EDU can be attached either to its adjacent EDUs (forming what is called a span) or to any other adjacent span, recursively thus creating a tree.1 Less constrained structures are found in two other approaches, first from [START_REF] Wolf | Coherence in Natural Language: Data Stuctures and Applications[END_REF] (the GraphBank corpus) which creates graph structures with apparently no constraints whatsoever, second from SDRT [START_REF] Asher | Logics of Conversation[END_REF] which creates directed acyclic graphs imposing only the RFC. Two different annotations campaigns have used the SDRT framework: DISCOR [START_REF] Baldridge | Annotation for and Robust Parsing of Discourse Structure on Unrestricted Texts[END_REF] for English and ANNODIS [START_REF] Afantenos | An empirical resource for discovering cognitive principles of discourse organisation: the annodis corpus[END_REF] for French.

We have used the ANNODIS corpus: it is a collection of French discourse annotated newspaper and Wikipedia articles; specifically, we used the so-called "expert" annotations from the sub-corpus that deals with rhetorical relations. The chief reason for choosing a corpus based on SDRT is that it provides a compromise between simplistic approaches to discourse (attachment on adjacent DUs) and completely unrestricted approaches (such as the GraphBank corpus). SDRT manages to capture fine grained discourse phenomena, such as for example long distance attachments and pop-ups, while at the same time imposing a few constraints through the distinction between hierarchical and additive relations, such as the right frontier constraint.

The relation set used in the ANNODIS annotation campaign is a strict subset of the set of relations described in [START_REF] Asher | Logics of Conversation[END_REF] (for example, there are no metarelations); their semantics was also simplified in order to be accessible to naive subjects. In order to be able to apply techniques from syntactic dependency parsing, we transformed SDRT Annodis annotations into dependency graphs by replacing complex discourse units with their recursive heads. Annotations indeed mix EDU (elementary DU) and sets of EDUs, which are comparable to large spans in RST, with less constraints on their members, and this procedure is then another kind of head percolation. The head of a CDU is the highest DU in its subgraph (in terms of hierarchical/subordinate relations) and leftmost or older DU in the discourse with respect to additive/coordinate relations if there is more than one. In case that the DU is a complex one, the procedure is recursively applied until an EDU is reached, in which case that is the recursive head of the CDU. This transformation is graphically depicted in figure 1 which also contains the corresponding text and segmentation in the original French language.

Local models

Our discourse parsing is based on two locally-trained classifiers, one that predicts the attachment site of each DU, the other that predicts a discourse relation for attached pairs of DUs. In both cases, we trained probabilistic classifiers, using two different types of model: Naive Bayes (NB) and logistic regression (aka maximum entropy, or MaxEnt for short). The use of probabilistic models is guided by the way we combine the two models during decoding, and will be explained in Section 6.

We used two different, partially overlapping, feature sets for attachment and labeling.

Overlapping features reflect an inclusion in the same sentence or paragraph, an EDU being the first of the paragraph, the number of tokens in an EDU, the number of intervening EDUs between source and target EDUs, whether the source is embedded in the target and conversely. Features specific to attachment include the presence of a discourse marker, whether the target is embedded in an EDU other than the source and a boolean feature triggered by a set of syntactic rules determining whether source (or target) is an apposition or relative clause embedded in its main clause. Features specific to labeling include: the presence of a verb, boolean features indicating which discourse relations are triggered from all discourse markers in the EDU, the syntactic category of the head token, the presence of a negation, tense agreement between head verbs of both source and target (the last three make use of syntactic dependency parses3 ) and features inspired from coreference resolution (based on pronouns and NPs).

Evaluation for the two tasks, based on 10-fold cross validation on the document level, is shown in table 2. For the relation labeling task, we use the whole set of 18 relations annotated in the Annodis corpus, but since this is a relatively small corpus, we also considered a smaller sets of relations. Following other hierarchies of relations (RST and PDTB), we grouped SDRT-inspired relations into four main groups: "structural" (parallel, contrast, alternation, conditional); "sequence" (result, narration, continuation); "expansion" (frame, elaboration, e-elaboration, attribution, comment, explanation); and "temporal" (temploc, goal, flashback, background). This corresponds roughly to the PDTB upper-level 4-way distinction, namely temporal, causal ("contingency"), comparison and expansion, with comparison being almost the same as structural without the logical relations, but the sets of fine-grain relations are somewhat different. Our 4-way coarse grain classification is also more evenly distributed between relations (and instances, as it turns out).

For both tasks, we perform our experiments using a set that contains all possible pairs of EDUs, and a set that considers only pairs of EDUs whose distance is between 1 and 5 (noted "w5" for window of 5 in the table). This window was decided upon using a small development test, whose analysis revealed that around 92% of the attachment decisions fell within a window of 5 DUs. The class imbalance inherent to the attachment problem was thus reduced: the ratio of positive instances (i.e., attachments) went up roughly from 2% to 20%. These results show that Maxent is the best model in isolation, for both tasks (it is better in both precision and recall). As expected, we also notice that the resampling increases performance in both cases; although it isn't reported here, it does however produce a small decrease in recall for the attachment task. On this task, Maxent appears to be more robust to class imbalance than NB, as shown by the relative differences between attachment F1-scores with and without resampling.

MaxEnt

Parsing experiments

We divided the ANNODIS corpus in two parts: a main part and a small development set on which we had a look on the impact of some features, and most importantly on the distribution of distances between discourse units actually attached. As explained in Section 5, this leads to different sampling strategies for training the local classifiers. This will also impact decoding in pre-pruning the hypothesis space.4

Our various experiments are based on different combinations of classifier models (as detailed in the previous section) and decoding strategies. For attachment, we consider as instances either every pair of DUs in the same text or every pair in a distance equal to five or less. For labeling, the training is made only on attached discourse units in the training set and predictions are made on every pair tested for attachment. Features for each training procedures were detailed in section 5. As decoders, we tested a few baselines as well as MST and A*, all detailed further in this section. The last two algorithms take as input G, the complete graph over discourse units, where each edge (u, v) is labelled with the relation R having the best probability according to the relation labeling model, and the cost or weight of an edge is given by:

cost((u, v)) = -log(P r(at t ach(u, v) = True) × ma x R P r(R|at t ach(u, v) = True))
This way of computing each arc cost means that we are in effect taking attachment and labeling decisions jointly, and not in a cascade as is done in the baselines.

Baselines We use two baseline decoders. The first one always selects the previous unit for attachment to the current one (noted "last"). We have also implemented a locally greedy approach similar to that of [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF]. DUs are ordered based on their left boundary (embedded segments are considered to be at distance 1 from their containers).

Then for all pair of adjacent units5 (e i , e j ) we greedily select the one that has the highest attachment probability. We remove e i from the ordered list and continue the process until there is only one unit left in the list.

Using the Chu-Liu Edmonds algorithm

The structures that result from the replacement of CDUs with their recursive heads in Annodis annotations are directed acyclic graphs, with few edges reaching a given node; they are thus very close to non-projective trees with directed arcs. Naturally then, we can apply a Maximum Spanning Tree (MST) approach, as applied by [START_REF] Mcdonald | Non-projective dependency parsing using spanning tree algorithms[END_REF] in the context of syntactic dependency parsing for directed non-projective dependency trees. MST can consider an almost complete graph with a "root" as the only node with no incoming edges. In our case this node will be the first (leftmost) EDU. Using either NB or MaxEnt, we calculate the probabilities of attachment between each pair of EDUs, except for the first (root) EDU for which we calculate only the outgoing edges. We can then apply the Chu-Liu Edmonds algorithm [START_REF] Chu | On the shortest arborescence of a directed graph[END_REF][START_REF] Edmonds | Optimum branchings[END_REF], whose complexity is O(n 3 ). MST is expected to perform well in the case that there are no additional constraints to be respected. Nonetheless, adding additional constraints is not a trivial matter.

Using the A* algorithm The general schema for A* search has been shown in section 3.

Here we detail the heuristics that we have used to guide the search. In A* search, the pending queue is ordered by the estimated cost of a solution whose intermediary state is the current state s. The estimated cost is f (S) = g(S) + h(S) where g is the cost of what decisions have already been taken, here the sum of the cost of selected relations so far (see above). When we build a tree under the right-frontier constraint, we have a set of discourse units yet to be attached. A heuristic yields an optimal solution if it underestimates the remaining cost (it is then an "admissible heuristic"), so that a usual way of estimating this cost is to solve the remaining problem while leaving out some constraints. To be useful the heuristics must also discriminate between comparable states, and be as close as possible to the real cost, so for instance the trivial h(s) = 0, while admissible, is useless. A more classical approach is to consider what would be the best possible decision at a given stage, if no constraint was present. For instance here, we could take, for the estimated cost of attaching a given unit, the best cost of attaching this unit to any other DU already chosen.

The remaining cost of the solution is then the sum over the set of remaining DUs. Let's call this h_best. As there can be a lot of variance in the costs, another practical solution is to consider the average of attachments to every remaining nodes. This is potentially not admissible any more, as it can overestimate the real cost, but can yield good solutions faster. We will call this heuristics h_average. When tested on the development set, the predictions made using h_best and h_average were almost the same so we used h_average in the real experiments because it made decoding faster. Then:

f (S) = g(S) + h aver a g e (S) = (u,v)∈S.E cost(u, v) + u∈S.V ( (v∈I/{u} cost(v, u) ||I|| )
For each experimental setup, we perform a document-based ten-fold cross-validation6 on the main part of the corpus.

Results

This section reports on the performance obtained for our different systems. Recall that our overall goal is to evaluate labeled discourse structures, encoded here as labeled dependency graphs, produced by the different combinations of local models and decoding strategies.

We also have two different training algorithms (NB vs. Maxent) and two settings based on pre-pruning possible attachment points or not. Finally, we are also interested in comparing the joint decoding of the attachments and the relation labels compared to the pipe-lining of the two procedures.

For evaluation, we take the most natural metric for dependency graphs: we compare the set of edges predicted to the reference edges, with precision, recall and F1-measure. We average on the set of all edges on all tested documents (as mentioned in the previous section, we did a cross-validation using 10 document-based folds). We see that A* and MST decoding perform at the same level without significant differences, but largely outperform all other methods. The type of learner used does not seem to make a difference in the pruned version, while Maxent is clearly better when given the whole decision space. This is clearly in line with the extra robustness noted in the classification results in the previous section.

We can observe that the best overall scores are close the F1 score for the pure attachment classification task. This seems to indicate that the impact of our global decoding strategy is not directly captured in the (edge-based) evaluation metric, and is therefore mostly a matter of exhibiting structures with desirable properties, like obeying the RFC. These might in turn be potentially useful for latter processings, such as anaphora resolution. We now turn to the results on labeled discourse structures. The main thing to observe here is that the best decoding methods are still MST and A*, but the (expected) drop induced by relation labeling has confused the attachment results in the case of joint decoding: pipe-lining relation prediction after unlabeled attachment performs significantly better than joint decoding, at least for the best systems. It is also noticeable that pruning the attachment space is not worth it in this configuration (apart from efficiency considerations, of course). The main consequence is that we should refine our relation prediction model before drawing definite conclusions, and extend the approach to larger corpora. In hindsight, fully separating predictions within sentences or between sentences, as done in comparable work, is also something that should have been tried (we only provided features to that effect).

How can we compare these results to similar work? Taking directly [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF] published scores is not easy, since they produce RST constituent trees, and use dedicated measures, namely the Parseval measures, which compares common subtrees. That is why we tried to reproduced their overall method of decoding on our data (the greedy procedure).

We can still have a look at their classification scores for attachments, and the range of their evaluation for the whole structure. In their framework, it is equivalent to the tasks they call "structure" and "nuclearity", the first being finding a pair to link, the second one being the choice of direction of the attachment, choosing the "head" of the result. When using perfect segmentation, as we do, [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF] have a F1 score of 68.4%. In [START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF], structure is predicted as relation argument spans with a F1 score of 70%, but this is similar to the attach-to-last baseline, and nuclearity is at 50% (the same baseline is at 48). It is also interesting to consider simple attachment predictions as made in [START_REF] Feng | Text-level discourse parsing with rich linguistic features[END_REF]. Without knowledge of the rest of the structure, they have a F1 score of 69.84% on attachment decisions.

Again, it is hard to compare, since we don't have information about baselines comparable to ours, but we can observe the scores are in the same close ranges, while we have a simpler model with less features, trained on much less instances. [START_REF] Hernault | HILDA: A Discourse Parser Using Support Vector Machine Classification[END_REF] have 17k positively attached pairs, 77k overall, for a ratio of 23%, while we have, in the pruned version, 2.5k positive instances out of 13k (ratio ≤20%), and 2.7k out of 125k for the full version ( 2%).

For labelled structured, [START_REF] Subba | An effective discourse parser that uses rich linguistic information[END_REF] report a F1 score of 35%, with 15 relations and a baseline of 22%, slightly less than our 18-relation model, while the accuracy of their relation labeler reaches 60% (a much better score than ours).

Finally, [START_REF] Baldridge | Probabilistic head-driven parsing for discourse structure[END_REF], who use 30 relations on the very specialized corpus of Verbmobil dialogues, report F1 scores of 68% for unlabeled structures (very close to dependency graphs), and 43% for labelled structures. The task is arguably easier since dialogues are more constrained, and since they manually annotated some features used by their probabilistic model (e.g. semantic tags, utterance mood).

Conclusions

We have proposed a general approach to discourse structure prediction at the document level, performing a global search over the space of possible structures while optimizing a global criterion over the set of potential coherence relations, in order to take into account linguistically motivated constraints on the predicted structure (e.g. the RFC). We tested this approach on a corpus of French texts which assumes theoretical aspects from SDRT, but it could and will be adapted to other type of discourse annotations, such as RST corpora, using a simple algorithm alluded to above for translating RST into dependency graphs. The results for our general approach are at least comparable to similar approaches which are arguably more specific to a given corpus and have significantly more data to train. Our relation prediction model is slightly less accurate, being induced from a smaller dataset and poorer features than the best models, but the global decoding improvements are significant over other decoding approaches, while the predictions respect the desired properties on discourse structures. Besides improving our relation model, we intend to separate completely the predictions of links for intra-sentential discourse units from other relations, as many approaches have shown that sub-problem to be much easier. We also intend to have a more structured approach to learning the structures, first by integrating decoding within the learning phase, as is done in the syntactic analysis literature we took inspiration from, and secondly by studying the usefulness of k-best parsing on the overall result.

Figure 1 :

 1 Figure 1: An example of discourse annotation. The nodes correspond to discourse units; the EDUs are represented by their numbering; the CDUs start with π. Dotted edges represent inclusion to a CDU while edges with arrows represent rhetorical relations. Elab. = Elaboration, e-elab = Entity Elaboration, C. = Continuation. The second graph is the result of the transformation.

  An example of state generation is shown in algorithm 2

	procedure astarSearch(S 0 )
	queue ← {S 0 }
	while not(queue.isEmpty()) do
	current ← removeBest(queue)	⊲ best according to g+h(current)
	if isSolution(current) then return current
	else
	newStates ← generate(current)	⊲ well formed wrt desired constraints
	queue = queue ∪ newStates
	end if
	end while
	end procedure

  Next is removed from the nodes to attach.new.E = E ∪ (next,S.RF[k])⊲ The attachment is added to the current structure.

	procedure generate(S)
	result =
	next = head(S.V)
	for k in 1 to len(S.RF) do	⊲ This loop generate hypotheses attaching 'next' to every u ∈ RF.
	new = newState()
	new.V = pop(copy(S.V)) ⊲ result.add(new)
	end for
	return result
	end procedure

new.RF = new.RF[:k] + [next]

⊲ Next is appended to the RF after its parent, everything else below the parent is thrown out.

Table 1 :

 1 Relation distribution is shown in table 1. Corpus statistics from the ANNODIS corpus

	relation name	#	%	relation name	#	%
	alternation	18	0.5	explanation	130	3.9
	attribution	75	2.2	flashback	27	0.8
	background	155	4.6	frame	211	6.3
	comment	78	2.3	goal	95	2.8
	continuation	681	20.3	narration	349	10.4
	contrast	144	4.3	parralel	59	1.8
	Eelab	527	15.7	result	163	4.9
	elaboration	625	18.6	temploc	18	0.5
	total # relations		3355	total # EDUs		3188
	total # CDUs		1395	total # texts		86

Table 2 :

 2 Relation classification accuracy (left) and F1 score for positive attachment (right), in %. For both classifications tasks the difference between Maxent and Naive Bayes is significant at p<0.01, using McNemar's test. The upper limit recall for the latter task in w5 configuration is 92%.

			NB	Majority
	w5 (18 relations)	44.8	34.7	19.1		MaxEnt	NB
	full (18 relations)	43.3	32.9	19.7	w5	67.4	61.1
	w5 (4 relations)	65.5	62.1	51.2	full	63.5	51.3
	full (4 relations)	63.6	60.1	50.1

Table 3

 3 presents the results only for attachment of DUs. Besides pruning of the hypothesis space, we tested prediction of attachment alone, and prediction of attachment taking into account the probabilities of the best relations predicted to weight possible attachment (noted "joint unlabeled" evaluation in table3). Statistical significance was tested by comparing set of scores on documents using Wilcoxon sign-ranked test for paired samples.

	Training model	Naive Bayes		Maxent
	Decoding method	greedy MST	A * greedy MST	A * Last
	attachment alone (w5)	61.2 65.7 66.2	62.1 65.7 65.7 62.4
	attachment alone	58.5 62.0 62.1	62.2 65.7 65.7 62.4
	joint/unlabelled (w5)	59.7 61.7 64.8	62.2 65.1 65.3 62.4
	joint/unlabelled	57.9 57.0 59.6	62.3 65.1 65.4 62.4

Table 3 :

 3 Results for unlabeled structures i.e. attachment of DUs (F1 scores, %). Windowed attachment is marked with (w5). Bold scores are the best overall while italicized scores are

the best on a given setup (line). Joint unlabeled evaluation are evaluation of attachments when relations are also used to evaluate the probability of a link between DUs. A* and MST decoding do not differ significantly, but differ from all other methods. Confidence intervals at 95% are all about ± 0.9-1.2% wrt to given scores. Predicting relations does not seem to make a difference for attachment prediction.

Table 4 :

 4 Results of for full, labelled structures (F1 scores, %). Windowed attachment is marked with (w5). The 'last' baseline now uses a maxent model for prediction of relations. Bold scores are the best overall while italicized scores are the best on a given setup (line). Confidence intervals at 95% are all about ± 2% wrt to given scores. Best scores on each line are significantly better than the next one at p<0.01, except for ties. The best joint and pipe-lined scores are not significantly different from each other.

	Training model	Naive Bayes			Maxent
	Decoding method	greedy MST	A * greedy	last MST	A *
	joint(w5)	4 rels	38.9 29.3 41.7	42.2 42.2 31.6 44.1
	joint	4 rels	38.7 26.7 39.6	44.6 44.5 30.0 46.8
	pipe-line(w5) 4 rels	39.5 42.1 42.5	42.1 42.2 44.3 44.3
	pipe-line	4 rels	38.7 40.8 40.8	44.5 44.5 46.8 46.8
	joint(w5)	18 rels	22.0	8.2 23.7	28.7 28.6	4.8 30.1
	joint	18 rels	23.4	4.1 24.0	34.2 34.1	5.4 36.1
	pipe-line(w5)18 rels	22.5 24.0 24.5	28.7 28.6 30.2 30.2
	pipe-line	18 rels	23.9 24.7 24.8	34.0 34.1 36.1 36.1

It can be the case that more than two DUs (always adjacent) could be attached together for relations such as LIST.

Pamameter estimation for the latter was performed using[START_REF] Daumé | Notes on CG and LM-BFGS optimization of logistic regression[END_REF], http://www.cs.utah.edu/ ~hal/megam/. We also used utilities provided by the Orange library of[START_REF] Curk | Microarray data mining with visual programming[END_REF].

We have used Malt as a syntactic parser, trained on the french treebank http://alpage.inria.fr/ statgram/frdep/fr_stat_dep_malt.html

Note that DUs are always ordered based on their left boundary. This will be important for A* decoding, which needs an ordered set of DUs in order to respect the right-frontier constraint. Practically, it means that embedded segments are attached only once their containing segment has been processed. An embedded segment is considered to be at distance one to its container.

Two units are adjacent if their distance equals 1.

Each fold contains instances from a tenth of all documents, every document appearing in only one fold.

Acknowledgments

We wish to thank our colleagues M. Serrurier and J. Mengin.


Jérôme Ardouin
email: ardouin@esiea-ouest.fr

Anatole Lécuyer
email: alecuyer@irisa.fr

Maud Marchal
email: mmarchal@irisa.fr

Clément Riant
email: riant@et.esiea-ouest.fr

Eric Esiea

Marchand
email: marchand@irisa.fr

"FlyVIZ": A Novel Display Device to Provide Humans with 360° Vision by Coupling Catadioptric Camera with HMD

Keywords: B.4.2 [Input/Output and Data Communications]: Input/Output Devices. -Image display: I.4.1 [Image Processing and Computer Vision]: Digitization and Image Capture. -Imaging geometry Display device, 360° vision, catadioptric camera, panoramic images, Head Mounted Display

Have you ever dreamed of having eyes in the back of your head? In this paper we present a novel display device called FlyVIZ which enables humans to experience a real-time 360° vision of their surroundings for the first time. To do so, we combine a panoramic image acquisition system (positioned on top of the user's head) with a Head-Mounted Display (HMD). The omnidirectional images are transformed to fit the characteristics of HMD screens. As a result, the user can see his/her surroundings, in real-time, with 360° images mapped into the HMD field-ofview. We foresee potential applications in different fields where augmented human capacity (an extended field-of-view) could benefit, such as surveillance, security, or entertainment. FlyVIZ could also be used in novel perception and neuroscience studies.

INTRODUCTION

People are familiar with sophisticated optical devices and can use them to adapt their vision to various uses. For instance, microscopes and telescopes are classical optical devices that can magnify small or distant objects. These devices map a small part of the Field of View (FoV) to a larger one. Such mapping process decreases the effective FoV of the user.

The human field of view is limited to 180 degrees horizontally and 110 degrees vertically. Increasing the natural FoV is actually very difficult to achieve with traditional optical devices. In this paper, we introduce a display device which can enhance the human FoV, and enable a 360° horizontal FoV (80° vertically with our system). This novel device (see Figure 1), called FlyVIZ, is based on three components: (1) an acquisition system (e.g., a catadioptric sensor, on top of the user's head, for capturing 360° images), (2) a Head-Mounted Display (HMD) to display the processed image to the end-user in real-time, and (3) a computer vision algorithm to map the captured 360° images to the shape and dimensions of HMD screen).

In the remainder of this paper we first review related work. Second, we describe the global concept of FlyVIZ and its main components. Then, we present a proof-of-concept prototype and detail the proposed hardware and the real-time image processing algorithm. Finally, we discuss the performances and potential uses of our novel approach.

RELATED WORK

A HMD is a display device, worn on the head or as part of a helmet, which has a small display in front of one (monocular HMD) or both eyes (binocular HMD). The typical horizontal FoV of research or commercial HMDs ranges from 24° to 187°. Efforts are regularly made to extend the FoV of HMDs. As an example, Sensic company notably proposed an approach based on a mosaic of small screens [START_REF]Sensic piSight technical specifications[END_REF], that are able to extend the FoV while maintaining good resolution at the same time. The field of view of an HMD is also a critical parameter from a human perception perspective. When a 1:1 scale is used with a limited FoV, HMD users tend to complain, and often feel like they are looking through a keyhole.

The combination of HMDs with panoramic cameras has been scarcely studied up to now. Few examples exist in the teleoperation field. In [START_REF] Nagahara | Wide Field of View Head Mounted Display for Tele-presence with An Omnidirectional Image Sensor[END_REF], Nagahara et al. coupled a panoramic imaging sensor with a wide-FoV HMD for the purpose of remote exploration/visualization. The HMD was coupled with a head tracker, so that the user could explore the remote 360° FoV by turning his/her head. The image displayed in the HMD was not a panoramic image and the remote 360° FoV was sequentially explored. A similar system can be found in [START_REF] Onoe | Visual surveillance and monitoring system using an omnidirectional video camera[END_REF] for visual surveillance and remote monitoring. In Virtual Reality applications, a similar process of exploration of the virtual world is adopted [START_REF] Bowman | 3D User Interfaces: Theory and Practice[END_REF]. The virtual 360° FoV is explored sequentially thanks to a head tracker (ie. a device able to capture the user head orientation) and turning head movements. Interestingly enough, Fiala and Roth demonstrated the benefit of using a remote panoramic imaging system for tele-operation [START_REF] Fiala | Automatic Alignment and Graph Map Building of Panoramas[END_REF]. In particular, it removes the need for a closed-loop feedback for the remote low-FoV camera, and then reduces the overall latency.

The distortion or extension of human vision has been investigated in several scientific fields such as Neuroscience (e.g., for studying visual perception and brain adaptation using prisms [START_REF] Harris | Perceptual adaptation to inverted, reversed, and displaced vision[END_REF]), or Augmented Reality (e.g. by superimposing artificial information onto the naturally perceived images [START_REF] Barfield | Fundamentals of Wearable Computers and Augmented Reality[END_REF]). In the artistic domain, some performers have also developed systems that can extend human vision. In his 3RDI project, the artist Wafaa Bilal, was equipped with a camera on the back of his head giving a reversed point of view of his everyday life and displaying images to the audience [START_REF]3RDI project[END_REF]. The Crew Company coupled a panoramic sensor with an HMD and a head tracker. They could set up different performances in which the user could explore part of remote or recorded panoramic videos (similarly to the tele-operation systems aforementioned). Finally a similar artistic experience was built to play with the feeling of "presence" of the users [START_REF] Vanhoutte | Pending presence: negotiating the space in-between[END_REF].

To the best of the authors' knowledge, no previous work proposed a display to experience full 360° vision of one's surroundings in real-time.

THE "FlyVIZ" CONCEPT

With FlyVIZ, our objective is to enhance the natural human field of view. We intend to reach a full 360° FoV of the user's surroundings, in real-time. This would fulfill a dream of humans: to be able to "see behind their back" or see like some animals, such as flies, with a wider FoV, even reaching a fully panoramic vision. This objective is obviously difficult to achieve using simple and traditional optical devices. However, an image processing approach connecting an image acquisition system with a head-mounted display could suit our purpose. As illustrated in Figure 2, three main functions should drive the design of such a system. First it has to capture omnidirectional information/images from the user's environment (image acquisition). Second, it has to transform this view into a meaningful representation (image transformation). Finally, it has to display this view to the user (image presentation). The Image acquisition can be done with a catadioptric sensor, i.e., the combination of a camera with a mirror. Various shapes of mirrors could be used such as parabolic, hyperbolic, or spherical mirrors. Composite sensors could also be used, i.e., a set of multiple cameras assembled in a circle or sphere to cover the 360° FoV. The Image transformation requires a processing unit to carry out the necessary computations. This can be a laptop, a netbook, a wearable computer or dedicated hardware (ASIC). Smartphones with enough processing power could also fit. The Image presentation can be made using a Head-Mounted Display, but specific video glasses could also be suitable. As a complementary requirement, the whole system must preferably be wearable and compatible with the user's locomotion.

Proof of concept:

In this paper, we describe a first prototype of the FlyVIZ concept that is displayed in Figure 1. The image acquisition step is achieved with a catadioptric sensor [START_REF] Baker | A theory of catadioptric image formation[END_REF] made up of a hyperbolic mirror and a traditional 6mm-lens mounted on a CCD camera (IDS µEye 2210). The image acquisition system is mechanically attached on a helmet. Figure 3 displays a typical image acquired by this system. The panoramic images are acquired in the head reference frame (and so, it does not require head tracking). The image transformation is done on a laptop computer worn by the user in a backpack. The image presentation is done by means of a HMD (SONY HMZ-T1).

PROCESSING OF 360° IMAGES

In this section we further detail the image transformation process that is a key component of our system. The purpose of the image transformation algorithm is to transform the acquired image (Figure 3) into an image that can be displayed in the HMD. A comprehensible representation of the environment is targeted, i.e., a projection which can be effectively perceived by the user. With our approach, each pixel displayed in the HMD has to be mapped to its corresponding location in the acquired image. The image transformation is achieved in two successive steps, which correspond to two different projections:

1. Projection between a location on the final displayed image and a direction of the space ;

2. Projection between a direction of the space and its respective location in the acquired image.

For the first projection, the mathematical formulation of the problem consists in mapping all the space directions onto a plane. Mapping one direction of the 3D space is equivalent to map a point from a unit sphere onto a plane [START_REF] Baker | A theory of catadioptric image formation[END_REF]. This mapping problem (and its inverse problem) has been widely studied by mathematicians and cartographers [START_REF] Snyder | Map Projections: A Working Manual[END_REF]. We use the plate carrée cylindrical projection [START_REF] Snyder | Map Projections: A Working Manual[END_REF] (aka. the equirectangular projection) that is widely used both in cartography and panoramic imaging.

Although the plate carrée projection generates some distortions at poles, it preserves the shapes along the 0° parallel. This is known The second projection corresponds to the calibration of our optical system. The equations map a 3D space vector to its corresponding location in the acquired image. Details on the modeling and the calibration of catadioptric sensors can be found in [START_REF] Baker | A theory of catadioptric image formation[END_REF] and [START_REF] Scaramuzza | A Flexible Technique for Accurate Omnidirectional Camera Calibration and Structure from Motion[END_REF]. A practical implementation can also be found in [START_REF] Scaramuzza | A Flexible Technique for Accurate Omnidirectional Camera Calibration and Structure from Motion[END_REF]. In our setup we use a dedicated sensor calibration algorithm available in the OCamCalib toolbox [START_REF] Scaramuzza | A Flexible Technique for Accurate Omnidirectional Camera Calibration and Structure from Motion[END_REF]. The procedure takes about 15 minutes, and does not require to be fulfilled again, as soon as the optical alignment of the camera lens and the mirror is preserved. The calibration parameters are then stored and can be used later, at runtime. Mathematically, the whole process can be described as follows:

        →            →          →          ' ' y x Z Y X y x M S P ϕ λ
Thus, in the first step of our image transformation algorithm, a pixel with coordinates (x,y) is transformed to (λ,φ) with the plate carrée inverse projection (P) which is a simple affine transformation that remaps the x coordinates to [-π,π] and y to [π/2,π/2]. Then, the 3D space vector (X,Y,Z) is deduced from the parameterized form of the sphere equation (S).

          =           ) sin( ) sin( ) cos( ) cos( ) cos( ϕ λ ϕ λ ϕ Z Y X
Finally, the associated coordinates in the input image (X',Y'), are computed from (X,Y,Z), using the camera model (M) [START_REF] Scaramuzza | A Flexible Technique for Accurate Omnidirectional Camera Calibration and Structure from Motion[END_REF].

At runtime, each raw image is acquired from the catadioptric sensor and uploaded into the video memory as a texture buffer. A full-screen quad is then rasterized by using a dedicated fragment program on GPU. To transform the raw image into the final unwrapped image, the fragment program has to handle the two mappings described earlier: the plate carrée projection and the catadioptric camera model. For each processed pixel in the final image, (λ,φ) coordinates are deduced from UV coordinates of the full screen quad. The corresponding 3D vector is computed using the inverse mapping of the plate carrée projection. This vector is then used to address the input image according the catadioptric camera model [START_REF] Scaramuzza | A Flexible Technique for Accurate Omnidirectional Camera Calibration and Structure from Motion[END_REF]. This texture look up is done using hardware texture linear filtering to maintain smoothness over the final image. Both the raw panoramic image addressing and the plate carrée cylindrical projection are implemented at a fragment level. Such an implementation thus benefits from the parallel processing power available in modern GPUs and optimizes computation performances.

SYSTEM PERFORMANCES

Our prototype is based on an HMD with a FoV of 45° and a 16:9 aspect ratio (ref. SONY HMZ-T1). This aspect ratio fits relatively well with the properties of the plate carrée projection that constrains the displayed image to an aspect ratio of 2:1. Taking our optical setup into account, the final image is displayed in the HMD with 360° horizontal FoV and 80° vertical FoV (Figure 4). Our image transformation algorithm is implemented in C++ using OpenGL API and the GLSL shading language. We have benchmarked our algorithm on two different platforms with both a high (laptop) and low computational performances (netbook). The resulting frame rates obtained in HMD are given in Table 1. With a high-end laptop, the frame rate is far above the refresh rate of the camera (60Hz). But even with a low-cost netbook, the refresh rate meets a real-time constraint (24Hz). The overall latency of the system (end to end from acquisition to display) has been measured by taking pictures of a precision clock and its image processed by the system and displayed in the HMD. The value seen through the HMD was then subtracted to the directly observed value. With this procedure, we found an average latency of 83 ms.

SYSTEM IN USE

The FlyViz system is fully operational and has been tested by multiple users and in different conditions (e.g., indoor or outdoor). We can use different illustrative scenarios as illustrated in Figures 5 and6.

During these tests, users get used within the first 15 minutes of practice, letting them to smoothly move in their environment. Users also get used to the new visual feedback loop of their arms and hands, letting them open doors or grasp objects. In these cases, depth perception is altered since binocular vision is not available, but as suggested by Cutting [START_REF] Cutting | How the eye measures reality and virtual reality[END_REF], users seem to be able to base depth evaluation on the other depth cues (motion parallaxes, etc.). For the main user, a first scenario consists in grasping an object (a stick) held out by another person. Without moving his/her head, the user instantly perceives the position of the stick and can grab it, even when it is located out of his/her natural field of view. In a second scenario, the user is walking and must avoid some balls thrown at him/her, with balls sometimes being thrown from behind. A third scenario consists in driving a car on a parking lot, being able to see both the external environment and the car interior at the same time (Figure 5). During several tests, the device has been worn for more than an hour, without motion sickness or particular visual fatigue.

(

The main discomfort came from the unbalanced weight of the headset (helmet, camera, optics and HMD: 1650g). Future work is of course necessary now to evaluate the learning process, user perception, and the potential exploitation of 360° vision in various tasks, which is not the focus of this paper.

CONCLUSION AND PERSPECTIVES

This paper has introduced FLyVIZ: a novel display device to augment humans with 360° vision. FlyVIZ astutely connects a panoramic camera and a head-mounted display to present images with 360° horizontal field-of-view in real-time. A proof-ofconcept system was developed based on a catadioptric system with a standard camera and a commercial HMD. An image processing algorithm based on a plate carrée projection was developed to transform the acquired images into images compatible with HMD screens and aspect ratio. Our software implementation benefits from parallel processing power provided by modern GPUs. On a standard laptop, the system reaches a frame rate of 480Hz and 83ms latency. The operability of the FlyVIZ prototype has been illustrated in different indoor or outdoor scenarios. For example users have been able to enjoy grasping an object held out behind their back without turning their head. The FlyVIZ concept and prototype are patent pending.

There are different application fields that could benefit from an enhanced FoV. In safety and security applications, soldiers, policemen or firemen could benefit from omnidirectional vision to avoid potential dangers or locate targets more rapidly. In less critical situations, some surveillance applications with a high visual workload, in all directions of space for instance, could also be concerned, such as for traffic regulation. Considering the novel perceptual experience proposed, FlyViz could also be transformed into entertaining applications and devices, as well as experimental materials for new perception and neuroscience studies.

Future work:

We foresee different paths for extensions and improvements. First, other projections and mapping methods could be tested with other geometric properties (conformal (preserving angles), equidistant, equal area, etc). These properties could influence the usability of the presented view according to a specific usage scenario. Moreover, instead of directly providing a 360° horizontal FoV, we could use a "split-screen" approach and different viewports on the image, such as using "driving mirrors" (rear and/or lateral mirrors). Other hardware components (camera and HMD) could also be tested with different aspect ratio or resolution characteristics. High dynamic range image sensors could also dramatically improve the final image quality. Then, augmented reality applications based on FlyVIZ could be proposed, for instance for improving perception of 360° vision with superimposed virtual cues.

Figure 1 :

 1 Figure 1: FlyVIZ prototype and proof-of-concept.

Figure 3 :

 3 Figure 3: image provided by the Catadioptric system.

Figure 2 :

 2 Figure 2: FlyVIZ components

Figure 4 :

 4 Figure 4: Image displayed in the HMD corresponding to the transformation of the raw image of Figure 3.

Figure 5 :Figure 6 :

 56 Figure 5: Third illustrative scenario: driving a car on a parking lot (HMD view).

Table 1 : Computation performance (frame rates)

 1

	Hardware	CPU	GPU	Frame Rate (Hz)
	15' laptop	i7-2820QM 2.30GHz	Quadro 2000M	480
	12' netbook	ATOM D525 1.8GHz	ION2	24


João Paulo Lima

Phd Candidate

Veronica Teichrieb

Hideaki Uchiyama
email: hideaki.uchiyama@inria.fr

Eric Marchand
email: eric.marchand@inria.fr

Object Detection and Pose Estimation from Natural Features Using Consumer RGB-D Sensors: Applications in Augmented Reality

Keywords: Augmented reality, natural features, computer vision, RGB-D I.4.8 [Image Processing and Computer Vision]: Scene Analysis-Depth Cues, Range Data, Tracking; H.5.1 [Information Interfaces and Presentation]: Multimedia Information Systems-Artificial, Augmented, and Virtual Realities

The work proposed in this document aims to investigate the use of consumer RGB-D sensors for object detection and pose estimation from natural features, with the purpose of using such techniques for developing augmented reality applications. Two methods based on depth-assisted rectification are proposed, which transform features extracted from the color image to a canonical view using depth data in order to obtain a representation invariant to rotation, scale and perspective distortions. While one method is suitable for textured objects, either planar or non-planar, the other method focuses on texture-less planar objects. Qualitative and quantitative evaluations of the proposed methods are performed, comparing it to existing methods for object detection and pose estimation.

INTRODUCTION

In the last years, AR applications have been benefited with the advent of low cost RGB-D consumer devices. These devices are commonly used in human body detection and tracking for user interaction purposes. RGB-D sensors are able to provide in realtime, besides a color image (RGB channels) of the scene, another image in which each pixel value corresponds to the distance from the scene objects to the camera. Such image is named depth image (D channel). The use of RGB-D consumer devices for object detection and pose estimation has grown significantly over the last years [START_REF] Hinterstoisser | Gradient response maps for real-time detection of textureless objects[END_REF] [START_REF] Lee | Depth-assisted real-time 3D object detection for augmented reality[END_REF]. The color and depth images from RGB-D cameras can be employed to obtain 3D models of the objects to be detected and also provide useful information at runtime for accomplishing better results when compared to techniques that use only RGB data.

The main question related to the topics approached in this paper is: -How to improve object detection and pose estimation from natural features for AR using consumer RGB-D sensors?‖. In order to address this problem, existing object tracking and detection methods based on natural features should be investigated in order to identify how depth information can be exploited to obtain better results than when only RGB data is used. A special attention should also be devoted to methods that already use RGB-D information for object tracking and detection.

In this context, the work presented in this document aims to develop novel object detection and pose estimation methods for AR using natural features and consumer RGB-D sensors. The developed solutions are evaluated taking into account performance, robustness and accuracy metrics.

The specific goals to be achieved in this work are:

• Study the natural feature tracking and detection field, with emphasis on object tracking and detection methods, including techniques that make use of RGB-D data, for identifying points of improvement in the state of the art;

• Define and develop object detection and pose estimation methods that use consumer RGB-D sensors for solving some of the identified points of improvement;

• Perform case studies and evaluations of AR applications that make use of the developed methods, in order to verify how the methods contribute to improving user experience.

This paper is organized as follows. Section 2 presents one of the methods developed in this work, which makes use of depth information for rectifying patches around interest points in the color image. Section 3 presents the other method developed in this work, which rectifies contours extracted from the color image using depth data. Section 4 discusses the preliminary results obtained with the techniques described in Sections 2 and 3. The results obtained are compared with other existing object detection and pose estimation methods. Section 5 presents final considerations and future work for the remainder of the PhD course.

DEPTH-ASSISTED RECTIFICATION OF PATCHES

This section presents a method developed in this work named Depth-Assisted Rectification of Patches (DARP), which exploits depth information available in RGB-D consumer devices to improve keypoint matching of perspectively distorted images. This is achieved by generating a projective rectification of a patch around the keypoint, which is normalized with respect to perspective distortions and scale.

In DARP, keypoints are extracted using FAST-9 [START_REF] Rosten | Machine learning for highspeed corner detection[END_REF] and their normal vectors on the scene surface are estimated using the depth image with the average 3D gradient method [START_REF] Holzer | Real-time surface normal estimation from organized point cloud data using integral images[END_REF]. Then, using depth and normal information, patches around the keypoints are rectified to a canonical view in order to remove perspective and scale distortions. Given as the unit normal vector in camera coordinates at , which is the corresponding 3D point of a keypoint, two unit vectors and that define a plane with normal can be obtained by:

‖ ‖ , .
This is valid because it is assumed that and are not equal to zero at the same time, since in this case the normal would be perpendicular to the viewing direction and the patch would be not visible.

From , and , it is possible to find the corners , …, of the patch in the camera coordinate system. The patch size in camera coordinates should be fixed in order to allow scale invariance. The corners , …, of the patch to be rectified in image coordinates are the projection of the 3D points , …, . Then,

, where is the intrinsic parameters matrix. If the patch size in image coordinates is too small, the rectified patch will suffer degradation in image resolution, harming its description. This size is influenced by the location of the 3D point (e.g., if is too far from the camera, the patch size will be small). It is also directly proportional to the patch size in camera coordinates, which is determined by a constant factor applied to and as follows: and . The factor should be large enough to allow good scale invariance while being small enough to give distinctiveness to the patch. In the performed experiments, it was computed by , where is the size of the rectified patch (set to in the experiments).

The corners , …, of the patch are given by: , , , . The corresponding corners , …, of the patch in the canonical view are: , , , .

From , …, and , …, , it can be computed an homography that takes points of the input image to points of the rectified patch.

For rotation invariance, the rectified patch orientation is calculated using the intensity centroid [START_REF] Rublee | ORB: an efficient alternative to SIFT or SURF[END_REF]. Finally, a descriptor for the rectified patch is calculated using the assigned orientation with the Rotation-Aware BRIEF (rBRIEF) method [START_REF] Rublee | ORB: an efficient alternative to SIFT or SURF[END_REF].

DARP can be used with any local feature detector and descriptor and is suitable for planar and non-planar textured scenes.

DEPTH-ASSISTED RECTIFICATION OF CONTOURS

This section presents a method developed in this work named Depth-Assisted Rectification of Contours (DARC) for detection and pose estimation of texture-less planar objects using RGB-D cameras. It consists in matching contours extracted from the current image to previously acquired template contours. In order to achieve invariance to rotation, scale and perspective distortions, a rectified representation of the contours is obtained using the available depth information. DARC requires only a single RGB-D image of the planar objects in order to estimate their pose, opposed to some existing approaches that need to capture a number of views of the target object. It also does not generate warped versions of the templates, which is commonly required by existing object detection techniques.

First, contours are extracted from the query RGB image using the Canny edge detector [START_REF] Canny | A computational approach to edge detection[END_REF]. Then, for each extracted contour, the 3D points that correspond to the 2D points of the contour and its inner contours are selected. In the remainder of this paper, the set of points that belong to a contour or its inner contours is named contour group. Then, for each contour group, the corresponding 3D points of the 2D contour points are used to estimate the normal and orientation of the contour group via Principal Component Analysis (PCA). The centroid ̅ of the 3D contour points is calculated, which is invariant to affine transforms. A covariance matrix is computed using and ̅ , and its eigenvectors and corresponding eigenvalues are computed and ordered in ascending order. The normal vector to the contour group plane is [START_REF] Berkmann | Computation of surface geometry and segmentation using covariance techniques[END_REF]. If needed, is flipped to point towards the viewing direction. Contour group orientation is given by and , which can be seen as the and axis, respectively, of a local coordinate system with origin at ̅ [START_REF] Berkmann | Computation of surface geometry and segmentation using covariance techniques[END_REF]. There are four possible orientations given by combinations of the and axis with different signs. It only makes sense to consider all four orientations if mirrored or transparent objects might be detected. Otherwise, only two orientations are enough, which are given by using both flipped and non-flipped as the axis and computing the axis as the cross product of and . In order to allow matching instances of the same contour group observed from different viewpoints, they are normalized to a common representation. Translation invariance is achieved by writing the coordinates of the 3D contour points relative to the centroid ̅ . Rotation invariance is obtained by aligning and with the and global axes, respectively. Since the 3D contour points are in camera coordinates, they are scale invariant. Perspective invariance is obtained by aligning the inverse of the normal vector to the global axis. This way, the rectified contour points can be computed as follows:

[ ] ̅ .
The rectified points should lie on the plane ( ). Since two or four orientations given by and are considered, each one is used to generate a different rectification of a contour group. All these rectifications are taken into account in the matching phase. In some cases the estimated orientation is not accurate. However, this is still sufficient for matching and pose estimation purposes.

After being rectified, query contour groups can be matched to a previously rectified template contour group. This is done by comparing each rectified query contour group with the rectified template contour group, considering the different orientations computed. First, a match is rejected if the upright bounding rectangles of the rectified contour groups do not have a similar size. Then, it is calculated a rough pose that maps the 3D unrectified template contour group to the 3D unrectified query contour group. Given the rotation and translation that rectify the template contour group and the rotation and translation that rectify the query contour group, the rough pose is obtained by:

[ ] [ ].
The 3D unrectified template contour group is transformed using the rough pose [ | ] and then projected onto the query image. After that, the upright bounding rectangle of the projected points is calculated and compared with the upright bounding rectangle of the 2D query contour group. If they are not close to each other or their sizes are not similar, the match is discarded.

The similarity between template contour group projection and 2D query contour group is given by their chamfer distance [START_REF] Barrow | Parametric correspondence and chamfer matching: two new techniques for image matching[END_REF]:

∑ ,
where is the number of points in the template contour group, is the -th template contour point and is the query distance transform truncated to a value . For each query contour group, the template contour group orientation with smallest chamfer distance is marked as a candidate match.

If there is a candidate match for a given query contour group, then a refined pose of the contour group is estimated from the previously computed rough pose using the Levenberg-Marquardt algorithm. The query distance transform is used to compute the residuals. Finally, the chamfer distance between the template contour group and query contour group is calculated using the refined pose. If it is below a threshold, then the match is considered as correct.

In the current implementation, a single contour group is used for defining the pose of a given object. If the object contains several disjoint contour groups, one of these has to be selected for being used as template. This section describes some results obtained with the DARP and DARC methods. The techniques were also evaluated regarding performance and pose estimation quality. All the experiments were performed with 640x480 images using a laptop with Intel Core i7 720QM @ 1.60GHz processor and 6GB RAM.

DARP Results

In order to evaluate DARP, some image sequences from the publicly available University of Washington's RGB-D Object Dataset [START_REF] Lai | A large-scale hierarchical multiview RGB-D object dataset[END_REF] were used. The results obtained with DARP were compared with ORB [START_REF] Rublee | ORB: an efficient alternative to SIFT or SURF[END_REF], since the current implementation of DARP performs keypoint detection, orientation assignment and patch description in a way similar to ORB. Two images of the same object with different poses were matched using both techniques.

Initially the tests were done with planar objects, as can be seen in Figure 1. It is shown in the top images the results obtained with ORB and in the bottom images the results obtained with DARP. It can be seen in the left images the matches between the two instances of the object. The projection of a 3D point cloud of the object using the pose calculated from the matches is shown in the right images. It can be noted that the DARP method provides better results than ORB when the object has an oblique pose with respect to the viewing direction. The matches obtained with ORB led to a wrong 3D pose, while it was possible to estimate a reasonable pose using DARP, as evidenced by the projection of the 3D model. After, some tests were done with non-planar objects, as shown in Figure 2. DARP also obtained better results than ORB in the oblique pose scenario, since the 3D pose computed from the matches (right images) was closer to the correct pose when the DARP method was used.

DARC Results

In order to evaluate DARC, some image sequences were captured using the Microsoft Kinect for Xbox 360 RGB-D camera and synthetic RGB-D images were also generated. Figure 3 shows some results obtained with DARC for detection and pose estimation of different planar objects. A video with the results can be found at http://goo.gl/PmXzQ. It can be seen that DARC can deal with significant changes in rotation and scale as well as with perspective distortions. The contour group used as template is the octagon of the stop sign. DARC was compared to some existing techniques regarding pose estimation quality and performance. The methods selected for the evaluation were ORB [START_REF] Rublee | ORB: an efficient alternative to SIFT or SURF[END_REF], which is a texture based technique, and PTM [START_REF] Hofhauser | Edge-based template matching and tracking for perspectively distorted planar objects[END_REF], which exploits edge information. Pose estimation quality was evaluated with a database of 280 synthetic RGB-D images of a stop sign under different viewpoints on a cluttered background. The poses were under a degree change range of [ ] with a step and a scale range of [ ] with a step. The percentage of correct poses estimated by each method was calculated. The pose was considered as correct only if the root-mean-square (RMS) reprojection error was below pixels. Figure 4 shows that DARC outperformed ORB and PTM in all viewpoint changes.

FINAL CONSIDERATIONS

It was shown that the use of RGB-D sensors allows improving object tracking and detection from natural features. The DARP method has been proposed, which exploits depth information to improve keypoint matching. This is done by rectifying the patches using the 3D information in order to remove perspective effects.

The depth information is also used to obtain a scale invariant representation of the patches. It was shown that DARP can be used together with existing keypoint matching methods in order to help them to handle situations such as oblique poses with respect to the viewing direction. It supports both planar and non-planar objects and is able to run at interactive rates. The DARC technique has also been presented, which performs detection and pose estimation of texture-less planar objects by making use of depth information available in RGB-D consumer devices. In order to achieve this, contours extracted from a query image are rectified for removing distortions caused by rotation, scale and perspective transforms. The normalized representation is matched to templates acquired a priori using chamfer distance and a rough pose is calculated. This pose is later refined using a Levenberg-Marquardt optimization. DARC showed to be robust to in-plane and out-of-plane rotations, scale and perspective deformations, providing a pose with reasonable accuracy for AR applications.

The DARC technique works in real-time, being able to run at ~20 fps while detecting a single template.

Regarding DARP, a quantitative evaluation of pose estimation quality will be performed. Future work will also focus in evaluating how normal estimation can be speeded up, maybe using faster approaches such as the one described in [START_REF] Hinterstoisser | Gradient response maps for real-time detection of textureless objects[END_REF]. A refinement step for patch pose estimation using a template tracking method such as [START_REF] Benhimane | Real-time image-based tracking of planes using efficient second-order minimization[END_REF] will be considered. Another issue that should be investigated is that when the object suffers from severe perspective or scale distortion, the rectified patch loses resolution, which impacts on its description. One alternative to be studied for solving this would be to generate distorted versions of the reference images prior to keypoint matching [START_REF] Calonder | BRIEF: Binary Robust Independent Elementary Features[END_REF]. Then, the available depth and normal information could be used to select a set of most probable matching keypoints for each patch. Finally, tests with other detectors and descriptors will be done.

With respect to DARC, it will be evaluated the possibility of extending the technique for working with non-planar objects. It could also be noted that computational performance drops linearly with the number of detected templates. As future work, DARC scalability should be improved. Optimizations are planned in order to allow better frame rates while estimating the pose of a higher number of contour groups. Special attention should be devoted to the pose refinement step, which showed to be a bottleneck and its performance depends on the number of detected templates. The use of a template tracking method such as [START_REF] Benhimane | Real-time image-based tracking of planes using efficient second-order minimization[END_REF] should be considered. The current approach is also not robust to partial occlusions, since it uses only a single contour group to estimate object pose. If any contour that belongs to the contour group is occluded, detection tends to fail. Occlusion handling is a direct consequence of estimating the pose of more contour groups, which is a future work mentioned in the previous paragraph. If the object is composed by several contour groups and the pose of the visible contour groups can be calculated, the object pose can then be inferred even if some of its contour groups are occluded. In addition, a verification method using neighboring contours such as the one described in [START_REF] Holzer | Distance transform templates for object detection and pose estimation[END_REF] could also be used. Contour detection showed to be not robust to illumination changes, noise and blur caused by very fast movements. The use of more robust region detectors such as MSERs [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF] will be investigated. Finally, confusions can occur when the template contour groups do not have enough discriminative power. It will be studied if the discriminative power of contour matching can be improved by making use of oriented chamfer matching [START_REF] Shotton | Multiscale categorical object recognition using contour fragments[END_REF] or directional chamfer matching [START_REF] Liu | Fast directional chamfer matching[END_REF].

An investigation of other ways of improving object detection and pose estimation using RGB-D sensors will also be performed. Then, AR case studies using the developed methods will be done.

Figure 1 :

 1 Figure 1: Planar object matching using ORB (top) and DARP (bottom): matches (left) and pose estimation (right).

Figure 2 :

 2 Figure 2: Non-planar object matching using ORB (top) and DARP (bottom): matches (left) and pose estimation (right).

Figure 3 :

 3 Figure 3: Augmentation of planar objects using DARC.

Figure 4 :

 4 Figure 4: Percentage of correct poses of different methods with respect to viewpoint change.