Jean Carrive

François Pachet

Rémi Ronfard
email: rronfard@ina.frpachet@csl.sony.fr

Clavis: a temporal reasoning system for classification of audiovisual sequences

In the context of video indexing, we present the Clavis system in which typical video sequences of television programs are represented by templates. Templates are terminological constraint networks in which video segments coming from automatic analysis tools are represented in a description logic formalism. Templates allow to express complex classes of video sequences with temporal constraints associated to a regular expression operator. Recognizing occurrences of a template in a video program is a plan recognition problem for which efficient methods have been implemented in a constraint satisfaction problem framework. The paper describes the system and illustrates its use with several experiments that were done in the context of the DiVAN european project.

Introduction

An important step towards content-based indexing television programs is the segmentation of the video into independent meaningful units, intermediate between the shot and the complete program. This is an inherently ill-posed problem in general, since even experts fail to agree on a common vocabulary of those units, and how to compare different segmentations. The problem becomes more tractable in more constrained situations, such as a collection of videos built on a common pattern or model. In that case, we can view segmentation as a plan recognition problem, where the plans to be recognized are characteristic of a collection of videos -such as a particular broadcast news or variety show. In this communication, we introduce a representation language and a computational framework for building such abstract models of television program collections, and recognizing the models from observations.

In [START_REF] Ronfard | Shot-level description and matching of video content[END_REF] it was first proposed to use a description logic to describe and index video shots with a rich set of film concepts. [START_REF] Carrive | Using Description Logics for Indexing Audiovisual Documents[END_REF] further elaborated on this idea, and extended the proposal to a general taxonomy of film events, useful in the description and the analysis of video documents in the large. In this paper, we present Clavis (Classification of Video Sequences), a system which classifies typical video sequences found in collections of television programs, using temporal compositions of film events. The classes of sequences are represented as templates which are terminological constraints networks. Recognizing occurrences of templates within the video is presented as a plan recognition problem and the solution proposed is an extension of the T-Rex system originally proposed by [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF], which combines symbolic temporal relations with a regular expression operator.

The paper is structured as follows. In section 0, we describe how classes of video segments coming from automatic analysis tools are represented in a description logic formalism, and used as building blocks of the Clavis system. In Section 3, we further explain how templates are defined as terminological constraints network and how the recognition process is designed. Finally in Section 4, we present some experiments that were done in the context of the DiVAN (Distributed Audiovisual Archives Network) project1 .

Templates: descriptions of video sequences

A lot of periodic television programs, such as newscasts, variety shows or magazines, follow a predefined scenario which presents very little variation from one edition to another. These programs are part of what is called a collection. We propose to describe typical sequences of such programs using templates and we use a plan recognition algorithm based on Weida's work on terminological constraints network [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF].

A plan recognition problem

We claim that recognising the occurrences of a template in a television program is similar to recognising which plan some active agent is following [START_REF] Kautz | A Formal Theory of Plan Recognition and its Implementation. Reasoning about Plans[END_REF] or recognising which predefined scenario best describes the evolution of a dynamic system [START_REF] Ramaux | Recognising a Scenario by Calculating a Temporal Proximity Index between Constraint Graphs[END_REF], and we present this problem as a plan recognition problem. In [START_REF] Fontaine | Une approche par graphes pour la reconnaissance de scénarios temporels[END_REF], the author distinguishes four steps in a plan recognition process: opportunity, filtering, activation and discrimination. We will concentrate in this paper on the last step, which can be formulated in our case as the problem of finding in a video program made of automatically labelled segments the occurrences of a typical sequence represented by a template 2 . This recognition process often results in attributing a modality to the plan being processed, depending on whether the observations satisfy, don't satisfy or are compatible with the plan [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF]. [START_REF] Ramaux | Recognising a Scenario by Calculating a Temporal Proximity Index between Constraint Graphs[END_REF] present a method that computes a proximity measure between the plan and the observations. We will focus in this paper on determining whether a set of observations satisfies or don't satisfies a template. It has turned out that determining whether the observations are compatible with a template is difficult and we temporarily put this task to one's side.

Following [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF], we define a template as a terminological constraint network. The vertices of the network are associated with concepts which describe classes of video segments coming from audio or video analysis tools. The edges of the network are temporal constraints which have to be respected by the observations, i.e. the video segments coming from the analysis tools. In addition to Weida's formalism, we define an iteration operator "*" which expresses a contiguous sequence of video segments. For instance, a simple template may describe a report as a sequence of consecutive shots with a logo appearing during the first shot of the sequence. This template is defined by the following expression:

Report nodes: s1 [Shot] s2 [Shot*] s3 [Logo] constraints : s1 {meets} s2 s3 {starts ∨ during ∨ finishes} s1 s1 {starts} this s3 {finishes} this

Classification of basic film events

Everything that appears on the screen, or is heard in the soundtrack constitutes an event. In this paper, we will consider that the temporal part of an event is only a time interval -for example a start point and a duration -identifying the temporal occurrence of the event within the video. Much like in grammars, we assume that a video is composed of several terminals, which we call segments. These

Logo

Shot

Report

Shot Shot Shot Shot events are terminal because they are not themselves composed of other segments. An event can be a particular shot, which is what is filmed in one shot of the camera, a segment of music, a gradual transition between two shots as a dissolve, etc.

When applied in the context of DiVAN, the complete indexing process consists of the following steps: 1) initial segmentation of the audio and video track, producing at least two separate segmentation layers (usually more); 2) feature extraction and classification of segments, based on learned statistical models; 3) symbolic classification, using DL descriptions; and 4) recognition of composite events. In this paper, we assume the results from 1) and 2) provide a set of terminal events and focus on step 3) and 4).

Description Logics Description logics (Nebel, 1990) form a family of knowledge representation languages which derive from works on semantic networks and frame languages. In a description logic, concepts represent sets of individuals, and roles represent binary relations between individuals.

Concepts can be seen as unary logical predicates, as roles are similar to binary logical predicates.

Concepts can be described by syntactic operators as intersection (AND), union (OR), restrictions on the domain of a role or on the cardinality of a role. Concepts (and sometimes roles) are organized into a taxonomy according to a generality link -a subsumption link. Computing the subsumption relation between two concepts is one of the principal task of a description logic system. Instantiation is one other important operation, which compute the set of concept an individual belongs to. Primitive concepts are defined with necessary -and not sufficient -conditions, as defined concepts are defined with necessary and sufficient conditions.

Taxonomy of film events Using the CLASSIC system [START_REF] Borgida | CLASSIC: A Structural Data Model for Objects[END_REF], we define classes of events as concepts, focusing of classes of events which can be automatically recognized by audio and/or video analysis tools, such as those which are integrated in the DiVAN prototype: segmentation into shots, face regions and text regions detection, music/speech discrimination, jingle detection in the audio track, for example.

Figure 1 shows five concepts corresponding to cases where a face region can be detected clearly. These concepts are derived from terms of a cinematographic vocabulary, called "shot values", and range from close-up (CU), where the face occupies approximately half of the screen, to the long shot (LS), where the human figure is seen entirely, and the face occupies around ten percent of the screen. Intermediate shot values are the medium shot (MS), the medium-close-up (MCU) and the mediumlong-shot (MLS) [START_REF] Thompson | Grammar of the shot[END_REF]. Shot values are usually defined in relative and imprecise terms, based on the distance of the subject to the camera. We use the fact that the apparent size of faces on screen vary inversely with their distance to the camera to provide a computable definition of shot values. The ratio of the width of the face to the width of the frame is used to classify a shot among the five concepts. For example, the CLASSIC definition of a MCU shot is the following:

(cl-define-concept 'MCU-Face `(and face (all face-ratio (and (min ,(/ 1 6)) (max ,(/ 1 2))))))

Face CU MCU MS MLS LS In may happen in some collections of documents that low-level features can directly provide highlevel information. For example, in the five editions of the "France 3" evening newscast "Soir 3" from the DiVAN corpus, when some text is displayed at the bottom left of the screen during a medium close-up shot of a character, the text always refers to the character on-screen, mentioning its name and sometimes its function or role (see Figure 3). Thus, a "named person shot" can be defined by the very simple CLASSIC expression:

(cl-define-concept 'NamedPersonShot '(and MCU BottomLeftTextShot))) When a shot is classified both as a MCUShot and as a BottomLeftTextShot, it is automatically classified as a NamedPersonShot. The definition of this concept is specific to the "Soir 3" newscast. Specific concepts are defined for each collection, starting from generally defined concepts as MCU. In other words, a general taxonomy of concepts is specialized for each collection of programs.

Constraint networks

A template is a temporal constraint network whose vertices are associated with concepts defined in a description logic formalism, or with other templates. A vertex associated with a concept is called an "elementary" vertex and a vertex associated with a template is told a "composed" vertex. An iteration operator "*" is defined which can be applied on the vertices of the network which are associated with concepts or with certain types on templates. This types of templates will be discussed later. The "*" operator can be compared to the "+" operator in regular expressions, as it indicates a contiguous sequence of at least one element. Non iterated vertices are told "simple" vertices. This iteration operator indicates a sequence of contiguous events. This leads to four different types of vertices:

• simple elementary vertices (v C ) • simple composed vertices (v T ) • iterated elementary vertices (v C* ) • iterated composed vertices (v T* )
The edges of the network are temporal constraints. In the current implementation of the system, these temporal constraints are temporal relations in the full interval algebra. A template is recognized -or satisfied -if and only if :

• each simple elementary vertex v C is matched with an observation which is an instance C;

• each simple composed vertex v T is matched with a subset of the observations which satisfies T; • each iterated elementary vertex v C* is matched with a subset of the observations forming a contiguous sequence of instances of C; • each iterated composed vertex v T* is matched with a subset of the observations forming a contiguous sequence of satisfied templates T; • the matching respect the temporal constraints defined in the template.

When a set of observations satisfies a template T, it is said to be an instance of T. Without iterated vertices, the problem of template recognition comes down to find a matching between the constraint network and the observation network. This network matching problem has been proved to be NP-hard [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF]. Recognizing templates with iterated vertices lead to matching vertices of the template with sub-networks of the observation network. In order to avoid a combinatorial explosion, we designed methods which are very efficient for the type of cases we have to deal with. An overview of these methods is presented in section 0.

Temporal constraints

Several representations of time may underlie a temporal constraint network. The two main categories are the time point algebra [START_REF] Vilain | Constraint propagation algorithms for temporal reasoning: A revised report[END_REF] and the time interval algebra [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. Complete constraint propagation in the latter representation is NP-hard and tractable subclasses of this algebra have been proposed [START_REF] Nebel | Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra[END_REF][START_REF] Drakengren | Twenty-one Large Tractable Subclasses of Allen's Algebra[END_REF]. Following [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF] we have chosen the full interval algebra with a 3-path consistency constraint propagation algorithm which is potentially non complete. The reason why we choose this formalism is that when we started this work we didn't have a precise idea on what would be the most appropriate representation of time. We thus adopted this very general and expressive formalism. In a second step, we should work on determining what are the temporal constraints we really need. For example, it appeared on the one hand that numerical constraints such as "a segment of music which starts less than 30 seconds before a shot", as in [START_REF] Aigrain | Medium Knowledge-Based Macro-Segmentation of Video into Sequences[END_REF], would enhance the powerfulness of our system. On the other hand, the full expressiveness of Allen's algebra didn't appear yet to be necessary.

The temporal extension of an instance t of a template T can be specified in the template definition by setting temporal constraints between t -or more precisely what will be t when T will be recognizedand its components. The instance of a template is designed by "this" in the template definition. For example, the template illustrated by Figure 4 defines a "musical shot" as a shot which appears during a musical segment. The temporal extension of a musical shot is naturally set as being equal to the observed shot. Note that any disjunction of Allen's relations may be set between the instance of a template and its components.

Iterated sequences

An iterated vertex v C* or v T* in a template represent a contiguous sequence of observations which are instances of C or instances of T. An iterated sequence contains at least one element, and the elements of an iterated sequence are contiguous, which means that two successive elements must be related by the Allen's meets relation. The temporal extension of an iterated sequence is defined as the temporal union of the temporal extensions of its elements. This implies that the temporal extensions of those elements are known, which lead to limit the types of templates which can be associated to an iterated vertex (see section 0). These types of templates are what we call "bounded" templates, i.e. templates whose temporal extension of instances may be computed. Roughly, a template is bounded if some of its vertices are in such a temporal relation with "this" that the temporal extension of its instances may be computed from the temporal extension of its components. This vertices have to be associated with event concepts or with other bounded templates. The temporal relations that allow to compute the starting point are starts, is-started, meets, equals, and the temporal relations that allow to compute the ending point are finishes, is-finished, is-met, equals.

The Figure 5

Other constraints

Once the general architecture of a template is designed as a temporal constraint network whose vertices are associated to concepts in a taxonomy of audiovisual events or with other templates, and whose vertices may be iterated in some cases, it is possible to define other constraints on its vertices. For example, we define a "no … between" constraint telling that for a template to be recognized, there should be no instance of some concept C or some template T between the observations matched with two of the vertices of the template. For example, the template illustrated by Figure 6 defines a report as the sequence of shots that is shown between two consecutive "jingle" shots, a jingle shot being a shot during which some instance of Jingle is heard. Other constraints could be easily defined, which would be taken into account by the constraint solver during the recognition process. It might be for cardinality constraints on the number of elements of an iterated sequence, or even numerical constraints on the temporal dimension of vertices, as "two instances of Jingle separated by at least 30 seconds". Note however that these constraints would not be taken into account during the construction of the temporal constraint network, and thus that inconsistencies would not be detected. In this case, the recognition process would scan the whole search space before answering that there are no solutions.

CSP techniques for template recognition

The problem of recognizing instances of a template T among the observations is expressed as a constraint satisfaction problem (CSP). Roughly, each vertex of T gives a variable of the CSP. Each variable takes its values from its domain, a finite set of possible values. The solutions of the problem are expressed as a set of constraints which are boolean functions whose arguments are variables.

In this section, we give an overview of the implementation of the Clavis system, focusing on the recognition of iterated sequences. The implementation deeply relies on BackJava (Roy et al., 1999), a (CSP) framework which allows to implement specific classes or variables, constraints and even domains or heuristics as subclasses of general purpose predefined classes. Thus, general mechanisms as arc-consistency can be used, as specialized filtering methods can be defined. In the system presented here, we use general unary constraints for checking that a simple elementary vertices are matched with observations that are instances of the concept associated with the vertex, general binary constraints for temporal constraints between simple vertices and specialized filtering method for temporal constraints which implies iterated vertices. These methods are sketched below. Finally, we let the default resolution mechanism of BackJava realize the recognition process, i.e. we let it choose when it should instantiate a new variable, which variable to choose, when it should backtrack, etc. The time responses we get during the experimentations we did -a few seconds for templates with iterated composed vertices with about 200 observed events -were quite encouraging and we didn't try to optimize the resolution phase.

The most complicated part of the implementation concerns iterated vertices of templates. We describe what is done with iterated elementary vertices. Iterated composed vertices associated with a template T are managed in a similar way after all instances of T have been recognized. Each iterated elementary vertex v C* gives an "iterated variable" of the CSP. The first problem is to represent the domain of the variable, i.e. the set of iterated sequences of instances of C. The number of such sequences can be very important. For example, for an observation network made of N consecutive shots, there are N(N+1) 2 distinct iterated sequences of shots. In this case, illustrated by Figure 7, all sequences of shots may be represented as sub-sequences of the biggest sequence of shots, which is called a "maximal" sequence. A maximal sequence of instances of C is an iterated sequence of instances of C where no observation is both an instance of C and is in the meets relation (respectively the is-met) relation with its first (respectively its last) element. Each sub-sequence is uniquely determined by its size and the index of Report its first element in the maximal sequence. An indexing function is used, which associates a unique integer between 0 and N(N+1) 2 -1 to all sub-sequences of a maximal sequence of size N according to their size and the index of their first element in the maximal sequence. The domain of an iterated variable is thus represented as a list of integers which is internally implemented as a list of intervals. This kind of integer variables are already implemented in BackJava which takes in charge basic operations on intervals, like union or intersection. 1234567891 0 1 1 1 2 1 3 1 4 1 5 1 6 1 In order to compute the domain of an iterated variable representing an iterated vertex v C* , one's must first compute the set of all maximal sequences of instances of C. This computation could be very expensive in the general case, but is quite acceptable for the kind of cases we have to process.

Temporal constraints which imply an iterated variable are implemented using a set of several filtering methods. Each of this method is intended to reduce the domain of the iterated variable in a given context. The general principal is the following. Let C R (v, v*) be a temporal constraint which imposes hat the values of the two variables v and v* are in the R temporal relation, v* being an iterated variable, v being either iterated or not. When v is instantiated, i.e. when the solver chooses a value for v, some filtering methods are called which suppress from the domain of v* the iterated sequences which don't respect the R relation.

Let us take as example a template which specifies that a jingle must precisely meets an iterated sequence of shots. The meets relation is expected to be frequently encountered in templates, and thus a specialized filtering method has been designed for it. The v J variable represents the jingle and the v S* variable represents the shot sequence. The observations are illustrated by Figure 8. During the recognition process, the solver may choose to affect the jingle-1 to v J . In this case, the doMeets filtering method is called, which suppresses from the domain of v s* . all the sequences which don't start with the sixth shot, as illustrated in the figure. Similar methods are designed for other cases which are expected to frequently happen, as the starts, equals or finishes temporal relations.

Another set of 13 methods are designed to cope with any temporal constraint, one for each of the Allen's basic temporal relation. For the r Allen's basic relation, the filtering method doNot-r is implemented, which takes as argument an iterated variables v* and an observed event e, and which suppresses from the domain of v* all the sequences which are in the r relation with e. In order to process a C R (v, v*) constraint in the case where R is any disjunction of Allen's basic relations, the doNot-r method is called for all the Allen's basic relation r which are not part of R.

Template subsumption

It would be appreciable if the template library was hierarchically organized according to subsumption links, as are concepts in a taxonomy. In [START_REF] Weida | Knowledge Representation for Plan Recognition[END_REF], recognizing instances of templates among the observations amounts to testing subsumption between templates, as plans and observations are roughly the same kind of temporal constraint networks. Unfortunately, the iteration operator we introduce in the template definition language results in an important complexity in the computation of subsumption between templates, as the '*' may appear in both the subsuming and the subsumee template. This implies that computing subsumption would necessitate to find a matching from sub-networks of the subsuming constraint network to sub-networks of the subsumee constraint network. Consider for example the templates T 1 and T 2 illustrated by Figure 9. T 1 subsumes T 2 , as any set of observations recognized as an instance of T 2 would also be recognized as an instance of T 1 .

Shot* Shot

Experimentation

We present in this section some experimentation we made on different broadcast news. Some of the documents come from an annotated corpus which was provided by INA and the AIM3 group, the other are part of the corpus of the DiVAN project. The results presented here rely on reference segmentations established for evaluation of analysis and classification tools of the DiVAN project [START_REF] Bouthemy | Scene segmentation and image feature extraction for video indexing and retrieval[END_REF]. The newscasts presented here fall into two main categories:

• Traditional newscasts, alternating between the anchor person in the studio, and pre-recorded stories; • Short newscasts composed of a small set of pre-recorded stories separated by jingles and/or graphics.

In order to recognize reports from this two types of newscast, two different methods are used which use different templates. It should be noted that similar classes of events -similar concepts -in two different newscast may have different definitions at the signal level. For example, the name of a character being filmed appears differently in a "Soir 3" and in a "France 2" evening newscasts, as well as the place of the logo is different (see Figure 3 above and Figure 10 below).

Reports of "France 2" newscast

In an edition of the "France 2" evening newscast, report sequences alternate with shots showing the anchorman in a studio. The anchorman can be filmed from different cameras. The logo of the channel always appear during report sequences on the bottom right of the screen, and never appears on studio shots, except once 4 . During report sequences, a text inscription on the bottom left of the screen always indicates the name of the person being filmed as a text inscription on the bottom right of a medium close-up shot always indicates the name of the location where the action takes place. Detecting these types of shots is interesting for at least two reasons. First, it may help to temporally structure the report sequence itself. Second, these shots may be used for summarize the report sequence, by for instance preferably select keyframes coming from these shots.

By exploiting the results of three analysis tools, namely a logo, a text region and a face region detection tool, four classes of shots can be defined for this newscast. These four classes are illustrated by Figure 10 In this example, we define a report as being what is shown between two shots of the anchorman. We thus extract the reports from the list of shots by defining the following template:

Report nodes: s1[StudioShot] s2[ReportShot*] s3[StudioShot] constraints:
s1 meets s2 s2 meets s3 s2 equals this This template specifies that a report is recognized when it occurs that a studio shot is followed by a sequence of report shots which is followed by another studio shot, and that the temporal extension of the report is equals to the temporal extension of the report shot sequence, i.e. it excludes the studio shots. This template is illustrated by Figure 12.

(…) Report The recognition of this template gives 7 reports, as expected. The recognized reports are shown Figure 11. We then try to establish which reports contain at least one shot of a named person. The following template is used for this purpose:

ReportWithNamedPerson nodes: s1[Report] s2[NamedPersonShot] constraints:
s1 {starts finishes during equals} s2 s1 equals this This template specifies that the reports we are looking for are reports "during" which a shot of a named person occurs, the meaning of "during" being given by the disjunction of Allen relations: {starts ∨ finishes ∨ during ∨ equals}. This relation states that the shot of the named person can be at any place in the report and can even temporally equals the report, which would be the case if the report is composed of a single shot of a named person -intervention of a foreign correspondent, for example. The temporal extension of such a report is obviously the same as the original report, as stated by the last constraint of the template definition.

The reports r 1 , r 3 , r 4 , r 5 and r 7 of Figure 11 are recognized as reports with a named person. Note that the r 4 report contains three distinct shots of a named person. Thus, there are three different ways to recognize r 4 as a report with a named person. The recognition process gives three responses for r 4 t o such a report, and a post-treatment is needed in order to keep only one answer.

Reports recognized from audio jingle occurrences

Several short newscasts share a common very simple temporal structure: reports are only separated by jingles. This is the case for example for the French channels M6 (the "6 minutes" newscast), Canal+ and Arte (the "8 ½" newscast). Most of time, the jingles of such newscasts are sequences of very similar images accompanied with very similar sound samples. We are interested here in the case where two analysis algorithms are applied, one providing a segmentation of the visual part into shots and the other detecting occurrences of jingles within the audio track. Jingles and shots are temporally independents, as shown in Figure 13. We define in this case a report as a sequence of shots which is delimitated -in a way that will be précised later -by two jingles. We consider the first jingle as being part of the report in order to be able to build sequences of reports, i.e. to recognize the Report* part of the whole newscast template.

We choose to include the first jingle as a jingle is often announcing the report and may contain visual or audio information on the report. A report is illustrated Figure 14. The first and the last reports constitute special cases, which are dealt with separately.

(…) Report We first define the whole temporal structure of the newscast, which is simpler that the definition of the report, and which is given by the following template:

Newscast nodes: s1[FirstReport] s2[Report*] s3[LastReport] constraints:
s1 meets s2 s2 meets s3 s1 starts this s3 finishes this This template indicates that the newscast is composed of its first report followed by a sequence of reports followed by its last report, and that its temporal extension is the temporal union of all the reports. The template which defines a report is a bit more complicated, in order to handle all the possible relative temporal positions of the shots which are part of the jingles with respect to the audio part of those jingles. The definition of this template is the following:

Report nodes: s1[Shot] s2[Shot*] s3[Shot] s4[Jingle] s5[Jingle] constraints:
s1 meets s2 s2 meets s3 s1 {overlaps starts is-started is-during} s4 s3 {overlaps starts is-started is-during} s5 s1 starts this s2 finishes this no Jingle between s4 s5

At least three shots are necessary to recognize a report. Shots labelled s 1 and s 3 in the template delimitate the report. The temporal relation {overlaps ∨ starts ∨ is-started ∨ is-during} which constraint s 1 and s 3 stands for "the earliest shot which temporally intersect the jingle". Roughly, a report is said to last from the beginning of one jingle to the beginning of the next jingle.

The way the temporal constraints are set in the template ensures that recognized reports form a contiguous sequence. The last constraint imposes that there is no jingle between the jingles matched with s 3 and s 4 , i.e. s 3 and s 4 are matched with consecutive jingles. Figure 15 shows an example of such a report. The matching of the template nodes are indicated on the figure, as are indicated the observed constraints between the shots which bound the report and the jingles. First and last reports are defined in a similar way, assuming that the first and the last shots have been labelled as FirstShot and LastShot. The definition of the template of the first report is given bellow:

FirstReport nodes: s1[FirstShot] s2[Shot*] s3[Shot] s4[Jingle] constraints:
s1 meets s2 s2 meets s3 s3 {overlaps starts is-started is-during} s4 s1 starts this s2 finishes this no Jingle between s1 s3

At a first glance, it may not appear necessary to explicitly refer to the shots which bound the reportshots indicated by s 1 and s 3 in the report template -and a report may seem to be more simply defined as a sequence of shots "between" two consecutive jingles, which would naturally lead to define the template:

NaiveReport nodes: s1[Shot*] s2[Jingle] s3[Jingle] constraints:
s1 {is-started is-overlapped} s2 s1 {meets overlaps} s3 s1 equals this no Jingle between s2 s3

Now consider the shots and the jingles illustrated by Figure 16. In the figure, shots which can be the first shot of a naïve report are indicated by a star and shots which can be the last shot of a naïve report are indicated by a diamond. Thus, there are 9 possible naïve reports, as there is only one report when applying the previous template. Moreover, this template doesn't take into account some special cases, as the case where the audio jingle is totally temporally contained in one single shot. We applied the newscast template to a "M6" newscast5 containing 174 shots and 10 jingles. The recognition process gives exactly 1 matching for the newscast, which is made of 1 first report, a sequence of 9 reports, and 1 last report, which means that all reports have been recognized and that each report was recognized is only one way. On the other side, the recognition of the "naïve" report template gives 485 reports.

Other types of programs follow similar structures. For instance, programs of the "Top A" variety show from the DiVAN's corpus present successive songs which can be segmented by only using the applause occurring at the end of each song. Delimitating the temporal boundaries of a song is however more difficult than those of a "M6" report, because applause can temporally overlap the music.

Reports recognized from progressive transitions

We compare in this section two different ways of recognizing reports from five editions of "Soir 3", the evening newscast of the french France 3 channel. Four of these documents are part of the DiVAN corpus and the last one comes from the AIM corpus. A report of this newscast is defined as the sequence of shots that is showed between two consecutive shots of the anchorman. This definition is taken as the reference. The first method for recognising reports uses only one concept, AnchorManShot, and one template:

Report nodes: s1[AnchorManShot] s2[AnchorManShot] constraints:
s1 before s2 s1 meets this s2 is-met this no AnchorManShot between s1 s2

Most of time, reports in a "Soir 3" newscast begins or ends with a progressive transition, as a dissolve, as illustrated by Figure 17. Shots of the anchorman and progressive transitions of a typical "Soir 3" edition is illustrated by Figure 18. As progressive transitions may appear during a report, and as reports don't always start or end with a progressive transition, recognising reports with using only progressive transitions will produce some errors. These errors may come from a shot of the anchorman or a sequence of shots of the anchorman being classified as a report if it is surrounded by progressive transitions, or from "missed" reports -or more precisely missed transitions between two consecutive reports -caused by an anchorman shot or a sequence of anchorman shots neither starting nor ending by a progressive transitions. The template used to recognize reports using the ProgressiveTransition event concept is the same as the template used with the AnchorManShot concept, by replacing AnchorManShot with ProgressiveTransition. Table 1 summarizes the number of reports recognized with the two templates, as the number of anchormans shots or sequences classified as reports and the number of missed reports.

Reports from anchorman shots

Reports from progressive transitions

Anchorman shots or sequences classified as reports This experience shows that detecting reports in this case by using only the progressive transitions entails some over-segmentation due to progressive transitions appearing during the reports and anchorman shots or sequences of shots surrounded by progressive transitions. The quasi systematic use of progressive transitions at the beginning or at the end of reports leads to a very small number of forgotten reports.

Conclusion

We have shown in this paper that a plan recognition approach, making use of complex temporal relations between video segments can be both useful and efficient for solving a variety of video segmentation and indexing tasks. This temporal framework is obviously not sufficient for solving all problems, and should be extended to deal with other relations, such as image or sound similarity between segment classes, and numerical temporal constraints. While this paper focused on the macrosegmentation task, such extensions could be even more useful in other applications, such as the automatic generation of video abstracts. More work is also needed to determine whether this temporal framework is necessary (compared to other simpler approaches using regular expressions and finite automata) for solving the task at hand. This work should be extended in two main directions. First, experimentations showed that designing a template for a collection is not a trivial task, even for television experts, and that the quality of the results depends critically on such difficult design choices as temporal constraints. Therefore, we are now turning to machine learning techniques for creating templates from annotated examples. Second, we currently assume that the initial segmentation and classifying results observed by Clavis are perfect. In the future, we would like to relax this assumption, for instance by defining preferences in the space of solution of the CSPs.

Figure 1 :

 1 Figure 1: shot valuesThe algorithm used in DiVAN to segment a video into shots also detects two different classes of progressive transitions between shots, namely dissolves and wipes. In a dissolve, the existing image is

Figure 3 :

 3 Figure 3: example of a NamedPersonShot

Figure 4 :

 4 Figure 4: temporal extension of an instance of template

Figure 5 :

 5 Figure 5: example of an iterated sequence

  Figure 7: representation of sub-sequences

Figure 8 :

 8 Figure 8: filtering iterated variables

  Figure 9: templates subsumption

Figure 10 :

 10 Figure 10: the four classes of shots from "France 2" evening newscast We present here an edition of a "France 2" newscast coming from the AIM corpus. This document contains 157 shots, including 15 studio shots, 7 shots of named persons and 11 shots of named places. The temporal order of the shots is shown Figure 11. In the figure, the missing shots are report shots which are not shots of named place or named person.

Figure 12 :

 12 Figure 12: example of a "France 2" report

Figure 13 :

 13 Figure 13: shot segmentation and jingle detection

Figure 14 :

 14 Figure 14: example of a "M6" report

Figure 15 :

 15 Figure 15: example of a report recognized from jingles

  Figure 16: multi occurrences of a naïve report

Figure 17 :

 17 Figure 17: progressive transition at the beginning of a "Soir 3" report

Figure 18 :

 18 Figure 18: anchorman shots and progressive transitions in a "Soir 3" edition

example of template with a "no … between" constraint

	Report nodes:	s1[Shot]	MusicalShot
		s2[Shot*]
		s3[Shot]	Shot
		s4[Jingle]
	constraints	s5[Jingle] s1 meets s2	Music
		s2 meets s3
		s4 during s1
		s5 during s3
		s2 equals this
		no Jingle between s4 s5
		Figure 6:

Table 1 : reports from "Soir 3" editions

 1

	Missed
	reports

DiVAN is the Esprit project N°

 2 We choose the term "template" because scenario or plan ("plan" means "shot" in French) are ambiguous in the television domain.

Action Indexation Multimedia

Still from AIM corpus


Anders Heyden

Fredrik Kahl

Long Quan

Minimal Projective Reconstruction including Missing Data

The minimal data necessary for projective reconstruction from point features is well-known when each object point is visible in all images. In this paper, we formulate and propose solutions to a new family of reconstruction problems for multiple images from minimal data, where there are missing points in some of the images. The ability to handle the minimal cases with missing data is of great theoretical and practical importance. It is unavoidable to use them to bootstrap robust estimation such as RANSAC and LMS algorithms and optimal estimation such as bundle adjustment.

First, we develop a framework to parameterize the multiple view geometry, needed to handle the missing data cases. Then we present a solution to the minimal case of 8 points in 3 images, where one point is missing in one of the three images. We prove that there are in general as many as 11 solutions for this minimal case. Furthermore, all minimal cases with missing data for 3 and 4 images are catalogued. Finally, we demonstrate the method on both simulated and real images and show that the algorithms presented in this paper can be used for practical problems.

Introduction

Obtaining a 3D reconstruction is one common goal in computer vision. Recently, reconstruction methods have been successfully extended to projective reconstruction within an uncalibrated framework [START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Hartley | Stereo from uncalibrated cameras[END_REF]. Solving minimal cases to perform 3D reconstruction is of both theoretical and practical importance, whereby a minimal case is meant that omission of one point in one image gives an infinite number of solutions. It is common to use the solutions obtained from the minimal cases to either bootstrap a robust estimation algorithms such as RANSAC or LMS schema [START_REF] Fischler | Random sample consencus, a paradigm for model fitting with application to image analysis and automated cartography[END_REF][START_REF] Torr | Robust parameterization and computation of the trifocal tensor[END_REF][START_REF] Zhang | A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry[END_REF] or an optimal estimation algorithm such as bundle adjustment. The minimal data necessary for projective reconstruction is well-known. In the two-view case, the minimum number of the points is 7, cf. Sturm's method [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF] reintroduced into computer vision in [START_REF] Faugeras | Motion from point matches: Multiplicity of solutions[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Maybank | A theory of self calibration of a moving camera[END_REF]. For three views, the minimum number of the points is 6, cf. [START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF][START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF]. The solutions to these problems rely on solving a cubic equation, and thus there are in general up to 3 solutions. However, these minimal cases do not allow the possibility of missing data. In practice, the missing data cases are frequent; the more images we have, the higher possibility that missing data occur. One typical example is illustrated in Figure 1 in which no matter how we locate the cameras, one of the 8 corners will not be visible. Even more, the missing point changes with the viewing position. Three possible camera positions are indicated in the figure that may result in three different missing corners in the images. This motivates us to formulate a new family of minimal reconstruction problems containing missing data. We will first develop a framework for efficiently parameterizing the multiple view geometry. Then, we will concentrate on the typical minimal case of 8 points in 3 images, where one point is missing in each of the three images. We will show that, not surprisingly, the algorithms for missing data cases are generally more complicated than the non-missing counterparts. The typical minimal case described above has 11 solutions. Finally, a catalogue of the different minimal cases for 3 and 4 images will be provided. Although the algebraic solutions are complicated, we demonstrate that the solutions are stable enough for dealing with real image sequences.

Previous work on reconstruction with missing data has been primarily concentrated on solely handling the redundant data cases. For example, the 'hallucination' of Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF], the closure constraints in the projective case of Triggs [START_REF] Triggs | Linear projective reconstruction from matching tensors[END_REF] and in the affine case of Kahl and Heyden [START_REF] Kahl | Affine structure and motion from points, lines and conics[END_REF]. The ability to deal with both a minimal case and missing data is, to our knowledge, new to the computer vision community.

The paper is organized as follows. In Section 2, we first formulate the minimal missing data problem for reconstruction. Then, we solve the minimal case of 8 points in 3 images with one missing point in each image in Section 3. Next, we summarize all known minimal missing data cases for 3 and 4 images in a catalogue in Section 4. After that, we evaluate the performance of the solutions on both simulated and real images in Section 5. Finally, some concluding remarks are given in Section 6.

Problem formulation

Throughout the paper, vectors are denoted in lower case boldface and matrices in upper case boldface. Scalars are any plain letters or lower case Greek.

We assume a perspective projection (uncalibrated pin-hole camera) as the camera model.

Thus the object space may be considered as embedded in ¢¡ and the image space embedded in ¡ . The camera performs a projection from ¡

to ¢ and can be represented by a £ ¡¤ ¦¥ matrix P ¡ ¨ § © of rank 3 whose kernel is the projection center. The relation between a object point x in ¡

and an image point u in can be written

P ¡ ¨ § © x (1)
It is well known that both the problem of reconstructing points from £ images (see [START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF][START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF]) as well as points from images, see [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF][START_REF] Faugeras | Motion from point matches: Multiplicity of solutions[END_REF], have in general £ different solutions. However, these minimal cases do not allow the possibility of having missing data in any of the images. For practical applications, it is important to be able to deal with the minimal cases which may contain missing data in some of the images. For two images, there are no minimal cases with missing data since a point visible in only one image does not give any constraint on the viewing geometry. So the minimum number of images in which we are interested is three.

For each point in each image, two quantities are measured ( -and ! -coordinates). Thus, given 6 points visible in 3 images, #" £ " $ £ constraints (or equations) are obtained.

The unknowns are the 3D point coordinates and the camera matrices modulo the projective coordinate frame, in total £ " &% £ " (' )' 10 2' 43 £ unknowns. This is a minimal case without missing data as 5 76 8 @9 A8 @B DC E8 @F 5 7G IH P6 RQ TS VU WB P8 @F £ A Starting with the above minimal case, i.e. points in £ images, and removing the sixth point from the third image gives, of course, less equations than unknowns. However, trying to add a seventh point visible in images ' and results in 3 X" £ " Y ¢% ` a" b a" b £ )c (3 points in £ images and points in images) equations and d" £ % £ " $' )' 70 e' D3 £ gf ( points and £ camera matrices up to the projective transformation) unknowns. This is still underdetermined as 5 76 8 @9 A8 @B DC E8 @F ih p5 7G IH P6 RQ TS VU WB P8 @F . By further adding a point in images and £ , we obtain 3 i" £ " T E% £ " T ¢" T ¥ (3 points in £ images and £ points in images) equations and c " £ % £ " q' )' i0 `' D3 ¥ ( c points and £ camera matrices) unknowns, i.e. a minimal case since 5 r6 R8 @9 A8 @B DC E8 @F 5 aG IH P6 Q TS VU sB D8 tF ¥ .

This incidence relation can be visualized by the following matrix, where u in row U and column v means that point v is missing in image U and ¤ means visible:

w x ¤ ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ y (2)
The three images of a cube indicated in Figure 1 may result in the above incidence relation. We conclude the discussion with a formal problem statement.

Problem 1. Reconstruct the object and the camera matrices (structure and motion) from c

points £ images where one point is missing in each image and determine the number of different solutions.

Problem solution

In this section we will first outline a parameterization framework for handling the geometry of multiple cameras. Then a solution to Problem 1 will be derived. As we are working within an uncalibrated projective setting, all quantities are determined only up to an unknown projective transformation, therefore we may without restriction1 introduce a projective coordinate system such that the first 3 points in space are assigned to the canonical projective coordinates

x¡ x x ¡ x © x¢ ¤£ w ¥ ¥ x ' u u u ' u ' u u ' u u ' u ' u u u ' ' y ¦ ¦
and the first ¥ image points in each image are assigned to

u¡ u u ¡ u © £ w x ' u u ' u ' u ' u u ' ' y
Using this choice of coordinates it is not hard to see that we get the following special form of camera matrices

P w x ¨ § u u © u u © u u © y
This reduced camera matrix using canonical projective coordinates has been successfully applied by many researchers [START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF][START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF][START_REF] Carlsson | Dual computation of projective shape and camera positions from multiple images[END_REF].

By further using the fact that the fifth basis point in space ' I' I' I' projects onto the fifth point in each image as

6 ¢ ¨ ¢ C ¢ ! , we obtain " # $ # % ¢ &¢ § % '© ¢ ! ¢ % (© ¢ 0) ¢ a% (©
Observe that both the left side and the right side are only determined up to an unknown scale factor. This means that we can fix the scale factors consistently by putting ¢ ' , which gives a natural scale to the camera matrix, inherited from the homogeneous coordinates 6 ¢ ¨ ¢ C ¢ 1 . We will assume that this fixation of scales already have been made in the sequel. This leads to the following reduced camera matrix:

P w x © 10 6 ¢ u u © u © E0 2 ¢ u © u u © 10 C ¢ 3© y (3)
It is important to observe that this reduced camera matrix only contains one unknown parameter © . We are now ready to state our main theorem of the section.

Theorem 1. There are in general ' )' algebraic solutions to Problem 1. The solutions may include complex and not physically feasible solutions.

Proof. Without restrictions we can make projective changes of coordinates in the object space as well as in the images. We then arrive at the reduced camera matrix parameterized by only one unknown © as in [START_REF] Faugeras | Motion from point matches: Multiplicity of solutions[END_REF]. For a set of three images, we have three unknowns © , © ¡ and © ¢ .

Consider the sub-configuration of 6 points that are visible in both the first and second image. If the first 5 points are chosen as projective basis, then the image of the sixth point in the first image is given by

¤£ w x 6 £ £ C £ y w x © E0 6 ¢ u u © u © &0 2 ¢ u © u u © E0 C ¢ 3© y w ¥ ¥ x £ ! £ ) £ S £ y ¦ ¦
and in the second image by

£ w x 6 £ ¥ £ C £ y w x © ¦ (0 6 ¢ u u © ¦ u © ¦ (0 2 ¥ ¢ u © ¦ u u © 0 C ¢ © y w ¥ ¥ x £ ! £ ) £ S £ y ¦ ¦
Note that they are both homogeneously linear in

£ , ! £ , ) £ ,

S £

, ¤£ and £ and can be rewritten together as

w ¥ ¥ ¥ ¥ ¥ ¥ x © E0 6 ¢ u u u 0 ¥ £ u u © ¦ 0 C ¢ © ¦ u 0 C £ y ¦ ¦ ¦ ¦ ¦ ¦ w ¥ ¥ ¥ ¥ ¥ ¥ x £ ! £ ) £ S £ §£ £ y ¦ ¦ ¦ ¦ ¦ ¦ 0 (4)
or more compactly denoted as

M £ § £ x £ ¤£ £ ¨ 0 (5)
Since the vector x £ §£ £ does not vanish, the ¤ matrix M has to be singular, i.e. © M u . Expanding the vanishing determinant gives a polynomial equation ¡ © ¨© u , where

¡ Q ¡ ¨© © % Q © © % Q ¡ © % Q © © © % Q ¢ © % Q £ © % Q © and the coefficients Q are polynomial expressions in u¢ u ¢ u £ and u £ .
Exactly the same analysis can be done for the seventh point in images ' and £ , which leads to

M £ § £ x ¨ 0 (6)
and for the eighth point in images and

£ M £ § £ x ¨ 0 (7)
The vanishing of the determinants M and M gives the two polynomial equations ¡ ¡ © 0© ¦ u and ¡ © 0© u , where ¡ ¡ and ¡ are given as

¡ ¡ ! ¡ ¨© © % © © % ¡ © % © © © % ¢ © % "£ © % © (8)
and

¡ ¡ ¡ © © % © © % ¡ © % © © © % ¢ 0© % "£ © % © (9)
The coefficients are polynomial expressions in u¢ u ¢ u and u and the in u ¢ u ¢ u and u . Now, we have to solve the polynomial system of equations

" $ % ¡ © 0© ¦ u ¡ ¡ © 0© ¦ u ¡ © ¢ 0© ¦ u
for the three unknown camera parameters © , © and © ¦ . Since each equation is cubic in the unknowns, there may be as many as £ " £ " £ ) different solutions in view of Bezout's theorem. However, as the polynomials are not dense, e.g. the monomials © ¡ , © ¦ ¡ and the constant are missing in ¡ , we could expect to have much less than 27 possible solutions.

Computing the resultant, which we denote by ¡ , of ¡ ¡ and ¡ with respect to © yields a polynomial equation in © and © of degree with coefficients that are polynomial expressions in the image coordinates. Next, taking the resultant of the polynomials ¡ and ¡ with respect to © ¢ , one obtains a polynomial equation in © of degree ' D3 .

At this stage, one might (mistakingly) conclude that there are 15 solutions. However, in the derivation we have introduced spurious solutions, which are independent of the image data. These solutions are identified by carefully inspecting the matrix M £ § £ in ( 5). If © 6

¢ and © ¦ 6

¢ , then the first column of the matrix M is a zero vector, resulting in the singularity of the matrix M. The same is true for M and M in ( 6) and [START_REF] Kahl | Affine structure and motion from points, lines and conics[END_REF], respectively. In summary, all three matrices M, M and M contain a zero column, hence singular if

© 0© 0© 6 ¢ 6 ¢ 6 ¢ 0 © 0© 0© ¢ ¤ ¢ ¤ ¢ 0 © 0© 0© C ¢ C ¢ C ¢ 0 or © ¨© ¨© Wu u u
These solutions imply, in turn, that the camera center one of the three cameras is located at

' u u u ¨ Wu ' u u 0 u u I' u or u u u I' For instance, © 6
¢ gives the first camera center at ' u u u as the 9 YG ¢ P ' u u u . This means that the camera center coincides with the first object point in the projective basis. These ¥ solutions are obviously not a general situation and can be easily singled out from the final ' D3 th degree polynomial equation. This concludes the proof that we can have at most ' )' ' 43 i0 ¥ solutions. £

Remark. The special choice of coordinates made above can also be used to solve the minimal case of 6 points visible in all 3 images. Again we have the £ unknowns © , © and © ¢ , representing the unknown parameters in each reduced camera matrix (3) obtained after a projective change of coordinates. Analogously to (4), the images of the sixth point in all three images gives a matrix equation:

w ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ x © E0 6 ¢ u u u u u © u 0 6 £ u © 0 ¢ u u © u 0 £ u u © ¢ 0 C ¢ u © ¦ u 0 C £ y ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ w ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ x £ ! £ ) £ S £ ¤£ £ £ y ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 0 which is homogeneously linear in £ , ! £ , ) £ ,

S £

, ¤£ , £ and £ and can be written as M § x £ ¤£ £ £ ¨ 0 As M § must be rank deficient, all ¤ minors vanish. Consider first the condition obtained from the images of the sixth point in the first and second image, which is the same as in the proof of Theorem 1 and result in a polynomial constraint of the form

¡ © 0© Q ¡ ¨© © % Q © © % Q ¡ © % Q © © © % Q ¢ © % Q £ © % Q © u
Similarly the condition obtained from the images of the sixth point in the first and third image, gives

¡ ¡ © 0© ¡ ¨© © % © © % ¡ © % © © © % ¢ © % "£ © % © u
However, in this case we can also consider the minor obtained from the rows ' ¥ 3 c f of M § (assuming

C £ ¢¡ u ), giving ¡ ¡ © ¨© 0© ¡ ¡ ¤© % © % ¡ © % © © © % ¢ 0© © % "£ © © u
We now have to solve the system of polynomial equations:

" $ % ¡ © 0© ¦ u ¡ ¡ © 0© ¦ u ¡ ¡ © 0© 0© u Y
Taking the resultant of ¡ ¡ and ¡ ¡ with respect to © ¢ and then the resultant of this polynomial and ¡ with respect to © ¢ gives a seventh degree polynomial equation in © . Removing the same spurious solutions as above we finally obtain a third order polynomial equation, giving three solutions. Remark. The special choice of coordinates can also be used to solve the minimal case of 7 points visible in 2 images. The details are left to the reader.

A catalogue of minimal cases with missing data

Having solved one minimal case with missing data, we now systematically look for all other possible cases. First, however, we can already apply Carlsson duality [START_REF] Carlsson | Dual computation of projective shape and camera positions from multiple images[END_REF] to the problem we have solved. Recall that Carlsson and Weinshall demonstrated the following remarkable result: Theorem 2 (see [START_REF] Carlsson | Dual computation of projective shape and camera positions from multiple images[END_REF]). The projective reconstruction with 8 points and images is equivalent to that with % ¥ points and 8 0 ¥ images. The n points and m images is said to be dual to m+4 points and n-4 images.

For instance, the case of 7 points in 2 images is equivalent to 6 points in 3 images. So knowing that 6 points in 3 images has in general 3 solutions, it follows directly by the Carlsson duality that 7 points in 2 images also has 3 solutions. Now dualizing Theorem 1 for the minimal case of 8 points in 3 images with 1 point missing, we obtain another minimal case with 7 points in 4 images where one point is missing in one of the 4 images.

Corollary 1. There are in general ' )' different solutions to the projective reconstruction for points in ¥ images where one point is missing in 1 of the 4 images.

The procedure of dualizing can also be demonstrated for the incidence relationship in [START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF].

Start by removing the first ¥ columns corresponding to ¥ base points of the duality. Then transpose the remaining matrix, and add the ¥ base columns again. After that we obtain the following dualized incidence relation corresponding to Corollary 1.

w ¥ ¥ x ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ u ¤ ¤ y ¦ ¦ (10)

Three images

We can now find all other minimal cases for three images. Let 8 and 8 ¡ denote the number of points which appear simultaneously only in two and three images. Clearly, 8 ¡ ¢¡ , otherwise we have the case of (at least) points in £ images, respectively.

The number of unknowns for the three-view geometry is £ " Y' )' for the three cameras and £ " 8 % 8 ¡ g0 #' 43 for the 8 % 8 ¡ points modulo a projective transformation, while the number of equations is ¥ " 8 % " 8 ¡ . By equating the number of unknowns and the number of equations, we have necessary conditions for minimal cases,

¥ 8 % 8 ¡ £ )£ % £ 8 % 8 ¡ 0 ' D3 i.e.

% £ ¡ ' c

This is a Diophantine equation whose solution is

£ 8 £ 9 8 ¡ &0 9 9 ' I 2
for u ¥¤ 8 ¡ ¦¡ , as 8 ¡ ¦ § leads to the trivial non-missing data case.

The solution 9 ' gives 8 and 8 ¡ 3 which may result in the following two incidence relations (not symmetric over three images) in addition to the one that we have solved in Theorem 1:

w x ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ u u ¤ y (11)
or

w x ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ u u u y (12)
In general, equating the number of equations and unknowns gives only necessary conditions. It is not sufficient to guarantee a finite number of solutions. For the incidence relation [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF], the first two images have points in common, so it could be solved by Sturm's method resulting in up to £ solutions. For each of these three solutions, we need to determine the ge- ometry of the third camera. The constraint for the eighth point, visible in images 1 and 3, is given by ¡ ¡ in [START_REF] Maybank | A theory of self calibration of a moving camera[END_REF]. This is a second degree equation in the remaining unknown © ¡ . Note that © is already solved for using images 1 and 2. Hence there are up to two possibilities for the third camera. In total, there might be up to possible solutions for this case.

For the case described by the incidence relation [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF], the geometry of the first two cameras is generally uniquely determined as they have c points in common, which is overconstrained, while there are infinitely many possibilities for the third camera, since it is underconstrained.

The other values for 9 ¦h ' can be handled in a similar manner, but the resulting polynomial equations are of very high degree and therefore hard to solve. One probably needs to rely on numerical computations.

Four images Let

¡

, £ ¥ denote the number of points which appear simultaneously in images. Equating the number of unknowns and the number of constraints gives the following Diophantine equation:

¥ 8 % 8 ¡ % c 8 © ¥ g¥ % £ 8 % 8 ¡ % 8 © 0 ' D3 i.e.

% £ ¡ % 3 © f

There are quite many solutions to the above equation. The complete catalogue for four images consists of all solutions to the above equation. We discuss a few of the cases below for small k, for which the solutions are obtainable with symbolic calculations in, for example, Maple without requiring waste computer resources.

¢ 8 © 3 , 8 ¡ 8 ' . This is the dual of the incidence relations shown in [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF] and ( 12),

w ¥ ¥ x ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ u ¤ y ¦ ¦ and w ¥ ¥ x ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ ¤ u ¤ ¤ ¤ ¤ ¤ ¤ u y ¦ ¦ (13)
So in the first case, there are solutions and in the second case, the cameras and the first points are in general uniquely determined, while the seventh point is undetermined since it is only visible in one image.

¢ 8 © 3 , 8 ¡ u , 8 ¥ . If the ¥ points visible in only images are symmetrically distributed such that no subset of points is common in images, i.e.

w ¥ ¥ x ¤ ¤ ¤ ¤ ¤ ¤ ¤ u u ¤ ¤ ¤ ¤ ¤ ¤ u ¤ u ¤ ¤ ¤ ¤ ¤ u ¤ u ¤ ¤ ¤ ¤ ¤ ¤ u u ¤ ¤ y ¦ ¦
then one can show, in the same way as in the proof of Theorem 1, that there are up to ) solutions! The dual case consists of 3 images and c points. ¢ 8 © ¥ , 8 ¡ £ , 8 u . This is the dual of Theorem 1 whose solution is given in Corollary 1 with incidence relation [START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF].

The list of cases continues, but they occur less frequently in practice, and often the complexity of the involved polynomials is too high in order to solve with symbolic computations.

Experiments

The algorithm for c points in £ images described in this paper has been implemented in Maple.

We first demonstrate the algorithm on the popular sequence of images of a wooden house (cf. Figure 2), which has been previously used for different projective reconstruction algorithms by many researchers. Three views covering about a ¥ 3 rotation of the camera around the wooden house are taken. The point features are first detected as the maximum of curvatures of the B-Spline approximation of the edge chains, then automatically tracked for the three images. The location of point features is also optimized by a nonlinear subpixel corner detector. The minimal missing data is shown in Figure 3. The first 5 points are visible in all three images and the 6th point is considered missing in the third, the 7th missing in the second and the 8th missing in the first image. Note that the 7th point is indeed missing in the third image as the side face is becoming tangent to the camera view. As more points are available in this sequence, a traditional method based on bundle adjustment has first been applied using all available 3 ¥ points. This £ ¢¡ reconstruction is used as ground truth.

We start by computing the real solutions of © ¨© and © ¦ for the projection matrices with the Maple implementation of the algorithm. For each real solution of projection matrices, we compute the projective structure of the set of 8 points. The projective reconstruction is then transformed into its Euclidean representation by applying a space collineation calculated with the 5 known reference points from the ground truth. Finally, the root mean square (RMS) error is computed for the reconstructed 6th, 7th and 8th point w.r.t. their known Euclidean coordinates.

In this real image case, very interestingly, up to the maximum of 11 real solutions are obtained! The lowest RMS solution is considered as the true solution. The other 46 matched points across the three images are also reconstructed in space for this solution. The final reconstruction of all points by the minimal missing data algorithm is superimposed with the reconstruction results obtained by a bundle adjustment. The result is illustrated in Figure 4. The reconstruction is remarkably good, only in the side view, we can see the error is more pronounced for the farther points such as those on the cup. The readers can also compare with that presented in [START_REF] Quan | Invariant of a pair of non-coplanar conics in space: Definition, geometric interpretation and computation[END_REF] using 6 points in 3 images. struction. We first proposed a general framework to parameterize the geometry of the multiple cameras. Then we solved the first problem of 8 points in 3 images with one point missing in one of the 3 images, proving that this problem can have as many as 11 algebraic solutions including complex and negative depth solutions. We also showed that the minimal cases with missing data for reconstruction is generally more complicated than those without missing data. Though we have to solve very high degree polynomial equations, the actual Maple implementation of the algorithms presented in this paper demonstrated remarquable reconstruction results. The accuracy and stability of algebraic solutions with missing data are comparable with those obtained without missing data. It suggests that these algorithms can be practically used for bootstrapping robust and optimal reconstruction. A complete catalogue of the minimal missing data cases for 3 and 4 images is also provided.

Figure 1 :

 1 Figure 1: A frequent practical example of missing data. A cube with 8 corners where (in general) only 7 corners will be visible in each image. Three possible camera positions resulting in three different missing points are indicated by arrows.

Figure 4 :

 4 Figure 4: A general, front and side view of two superimposed reconstructions: the points reconstructed from the minimal missing data are marked as diamonds, and the points from bundle adjustment solution are marked as crosses.

Figure 5 :

 5 Figure 5: RMS errors of 3D reconstruction vs. standard deviation of image noise, for the best and second best solutions of the 8-point algorithm, and the best solution for the 6-point algorithm.

Figure 6 :

 6 Figure 6: The number of real solutions and solutions with all points having positive depths vs. standard deviation of image noise, for the 8-point algorithm.

We are implicitly assuming that the first 4 object points are projectively independent as well as the first 5 points in each image.

Acknowledgments

This work has been done with support from the ESPRIT LTR project CUMULI.

We also check the stability of the algorithm by running on simulated data with the following set-up. We use three real camera matrices similar to the previous real image case, typically obtained from a bundle adjustment algorithm. A set of 8 known points are selected and projected by these projection matrices onto the synthesized images. Then, the projected positions of the points in the images are perturbed by varying levels of noise of a Gaussian distribution. The realism of the simulation is preserved in this way, and the image noise can be quantatively controlled as well in order to observe its influence. From the perturbed image points, the same computation procedure as for the previous real image case is performed. In addition, with the same data, the 8 points were reconstructed using the 6-point algorithm (where all points are visible), resulting in 3 solutions. For each of these solutions, the 7th and 8th point were reconstructed using the obtained camera matrices. The reconstruction errors are graphed in Figure 5, for both algorithms. In Figure 6, the number of real solutions and the number of solutions with all points having positive depths are illustrated.

We note that the solutions degrade very smoothly with increasing noise level. The behaviour of the 8 point algorithm is similar to the performance of the 6-point algorithm. Even if there are several real solutions, we see that there are at most one solution with all points in front of the camera. This suggests that the algorithm presented in this paper is of very practical importance even a very high degree polynomial equation has to be solved.

Conclusions

A new family of projective reconstruction problems using the minimal data from multiple uncalibrated images has been formulated and solved. Instead of the minimal data available in all images, we allow that the minimal data could be partly missing in some of the images. These minimal cases are undoubtedly of theoretical importance in order to understand the geometry of multiple views. But also they are of practical importance for both robust and optimal recon-


M Lhuillier

L Quan

¡ H Shum

¢ H T Tsui

Relief Mosaics by Joint View Triangulation

Relief mosaics are collections of registered images that extend traditional mosaics by supporting motion parallax. A simple parallax interpolation algorithm based on computed correspondence information allows high quality blurfree and ghost-free mosaics to be created using images from moving hand-held cameras that would not be suitable for traditional mosaicing. The renderer can also display local parallax changes, giving a local but visually convincing illusion of depth. Moreover, relief mosaics can be used for approximate plenoptic modeling from hand-held cameras at lower spatial sampling rates than existing light-field methods. We present a fully automatic correspondence based construction system for relief mosaics, and show how they can be used in applications. © x A ( and © x A w d ( and finally merged in the whole composite images. Suppose that the x -th and © x w d ( -th relief mosaics have dimensions h and a6 h a6 , and the viewing win- dow h . Let m G m7 be corresponding vertices in the two static relief mosaics and © @x A Dy ( be the barycentric coor- dinates of the viewer's position between the two. The position of the vertices in the synthesized view are determined by linear interpolation m7 7 © @y ( 8 © d " y ( m w y m7 " c

Introduction

Image mosaicing has been one of the most effective image-based rendering techniques. The main limitation of previous mosaicing methods [START_REF] Chen | Quicktime VR -an image-based approach to virtual environment navigation[END_REF][START_REF] Szeliski | Creating full view panoramic image mosaics and environment maps[END_REF][START_REF] Irani | Mosaic based representations of video sequences and their applications[END_REF][START_REF] Sawhney | Model-based 2D & 3D dominant motion estimation for mosaicing and video representation[END_REF][START_REF] Peleg | Panoramic mosaics by manifold projection[END_REF][START_REF] Rousso | Universal mosaicing using pipe projection[END_REF] is that the registration algorithms assume that the images are free from motion parallax. This implies either that the camera translation is small (fixed viewing position) or that the scene is shallow (near planar). Otherwise, the resulting mosaic has registration errors of order ¤ ¦¥ ¨ § © ! #" %$ '& )( pixels where ¤

is the focal length in pixels, § the magnitude of the sideways translation, and ! and $ & are the near and far scene- camera distances. For deep scenes, special equipment and calibration may be required to fix the viewing position to sufficient accuracy.

In this paper, we propose 'relief mosaics' that extend classical mosaics to allow images with motion parallax. Relief mosaics may viewed simply as collections of registered images with parallax, just as classical ones are collections of images without parallax. The registration of images with parallax is based on view interpolation or view morphing methods [START_REF] Chen | View interpolation for image synthesis[END_REF][START_REF] Seitz | View morphing[END_REF][START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF]. The inclusion of parallax has two important benefits. It allows the creation of high-quality traditional mosaics from parallax containing images taken with freely moving hand-held cameras, and it allows the renderer to produce a local but visually convincing impression of 'relief' or scene depth at very little extra cost.

There have been several previous attempts to deal with the inevitable parallax effects in image mosaicing. Deghosting technique uses local flows of small image patches computed to compensate for the parallax [START_REF] Shum | Construction and refinement of panoramic mosaics with global and local alignment[END_REF]. For dense video sequences, it is also possible to construct 'manifold mosaics' by pasting image stripes from different viewpoints along the camera path [START_REF] Peleg | Panoramic mosaics by manifold projection[END_REF][START_REF] Rousso | Universal mosaicing using pipe projection[END_REF].

A relief mosaic can be viewed as a '2.5D' plenoptic function [START_REF] Mcmillan | Plenoptic modeling: An image-based rendering system[END_REF], intermediate between 2D mosaics, and 3D concentric mosaics [START_REF] Shum | Rendering with concentric mosaics[END_REF] and 4D light-fields/lumigraphs [START_REF] Levoy | Light field rendering[END_REF][START_REF] Gortler | The lumigraph[END_REF]. However all of these plenoptic methods use pre-calibrated dense sampling without on-line correspondence, so depth interpolation is still a challenge for finite sampling rates. The static aspect of a relief mosaic is a multi-perspective panorama [START_REF] Wood | Multiperspective panoramas for cel animation[END_REF], or a rebinned concentric mosaic [START_REF] Shum | Rendering with concentric mosaics[END_REF]. They are also closely related to manifold mosaics [START_REF] Peleg | Panoramic mosaics by manifold projection[END_REF][START_REF] Rousso | Universal mosaicing using pipe projection[END_REF], however these are constructed from narrow vertical stripes from continuously registered video streams, therefore only limited parallax could be handled and the parallax information is not registered. Relief mosaics are made from fewer images, explicitly register and handle parallax information. We solve the technical challenge of correspondence-based view interpolation for relief mosaic construction using work [START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF][START_REF] Lhuillier | Edge-constrained joint view triangulation for image interpolation[END_REF] on the joint view triangulation representation for (real) image interpolation.

More generally, relief mosaics can be used as a building block for more complicated plenoptic modeling to give a kind of generalized light-fields. Such an application is demonstrated in this paper.

The paper is organized as follows. Section 2 describes the relief mosaic representation and its construction from a linear sequence of real images. Rendering with relief mosaics is presented in Section 3. Applications and results are presented in Section 4 and discussions are given in Section 5.

Relief mosaic representation by joint view triangulation

The basic idea of 'relief mosaics' is to assemble images into a composite image using view morphing to cancel their relative motion parallax on the registered overlapping sections, and a heuristic default mapping on the nonoverlapping sections to provide visual continuity with the registered ones.

The major technical challenges to using view interpolation or morphing principles [START_REF] Chen | View interpolation for image synthesis[END_REF][START_REF] Seitz | View morphing[END_REF] for images with parallax are computing dense pixel correspondences and properly handling parallax. Our approach is based on the Joint View Triangulation (JVT) registration and representation method [START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF][START_REF] Lhuillier | Edge-constrained joint view triangulation for image interpolation[END_REF]. Globally dense correspondence is seldom achievable in practice, so instead a set of corresponding patches from a 'quasi-dense' correspondence is used as described in [START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF]. Each patch is a small square in the first image and a quadrangle deformed by a plane homography in the second. A consistent joint view triangulation of the two image planes is constructed based on the corners of the corresponding patches [START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF][START_REF] Lhuillier | Edge-constrained joint view triangulation for image interpolation[END_REF]. Consistency for the JVT is defined as follows:

0 There is one-to-one correspondence between the matched corner points; 0 There is one-to-one constrained Delaunay edge corre- spondence in the two images. There are two types of Delaunay edge constraints: 1. the external boundary edges of connected and matched patches, and 2. corresponding line segments of polygonal approximations of linked image contour points.

An example of JVT for a pair of video images is illustrated in Figure 1.

A relief mosaic is represented by a collection of images with associated JVT for adjacent pairs of images. Relief mosaics represented this way may be viewed as 1 2 D plenoptic functions containing a 2D manifold mosaic and a ' 2 43 ' local parallax signal. Moreover, relief mosaics can be used as building blocks for more complicated plenoptic modeling, as illustrated in Section 4.

The main advantages of the JVT representation of real images are that it can be computed reliably and that it properly handles occlusions for composition/rendering so long as the occluding objects are sufficiently textured, as it keeps the explicit correspondence information for each triangular patch. It is related to the image impostors used in rendering synthetic large-scale environments [START_REF] Maciel | Visual navigation of large environments using textured clusters[END_REF][START_REF] Sillion | Efficient impostor manipulation for real-time visualization of urban scnenery[END_REF], however impostors are computed from a single (synthetic) depth image whereas the JVT is a mutually consistent triangulation of two (real) images without depth. It may also be viewed as an image based primitive intermediate between sprites and layered depth images [START_REF] Shade | Layered depth images[END_REF].

Compositing and rendering with relief mosaics

To compose a global static view of a relief mosaic, we warp the non-overlapping sections onto the mosaic coordinates, then locally interpolate the overlapping sections by properly handling the parallax to provide visual continuity with the warped ones. This step is in fact a traditional mosaicing using a global registration method [START_REF] Szeliski | Creating full view panoramic image mosaics and environment maps[END_REF].

Two-view compositing

2. Define an interpolation parameter that varies continuously across the composite image. To maintain visual continuity between different sections, the coefficients for linear interpolation are chosen like this: For a matched triangle v G v7 A 8 U A d A 1 , the rendering order is determined as that of the maximum norm of disparity of its vertices:

Q © u A u7 ( 8 R S T VU A u W X5 © u( `Y A © 5 a6 © u7 ( F( A b © u A u7 ( A u A A © u7 ( W X5 © u( c A © 5 a6 © u7 ( F( A d A A © u7 ( W A © 5 a6 © u7 ( F( #Y 5 © u( A Figure
! v " v7 ! A 8 U A d A 1 d ,

( 'y

The weight e © u7 7 ( is given by g h i g uj uk !l @l @m g uk k nl g ' i g uj u k l @l @m g u k k l 6 i g uj u k l @m k g u k k l y Although it is based on heuristic ordering, this two-view compositing algorithm correctly handles disocclusions so long as the occluding objects are textured enough and the depth decreases when the disparity increases. The second part of the algorithm is closely related to [START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF], but the interpolation parameter is different. It is constant in [START_REF] Lhuillier | Image interpolation by joint view triangulation[END_REF] for a physically valid single perspective view, but variable here for a continuous multi-perspective view. It is also related to McMillan's ordering algorithm [START_REF] Mcmillan | Plenoptic modeling: An image-based rendering system[END_REF] using the disparity as a heuristic in place of the true order computed from the camera geometry, which is unknown in our case.

Composing a global static relief mosaic A global static relief mosaic can easily be composed from linear sequences of discrete images taken by a hand-held camera, using the pairwise compositing algorithm described above between adjacent images. We concentrate in this paper on relief mosaics from linear sequences, although more general arrangements are certainly possible. Figure 2 shows an example of a static relief mosaic composed from 6 images.

The static compositing method can be applied directly to create traditional mosaics from images taken with handheld cameras. Motion parallax not handled by global transformation based alignment methods [START_REF] Szeliski | Creating full view panoramic image mosaics and environment maps[END_REF], and lens distortion which needs to be calibrated off-line, are very naturally absorbed by the correspondence based local interpolation of the relief mosaic. The result is a visually high quality mosaic without most of the ghosting (double images) and blurring artifacts due to imperfect global alignment and calibration as showed in Figure 3.

Rendering local parallax changes using a single relief mosaic

The static compositing method depends on the choice of the variable interpolation parameter function Q © u A u7 ( . Varying the parameter function produces compos- ite images with different parallax. Locally, the renderer creates an illusion of 'relief', except in the neighborhood of image borders. To keep the global mosaic visually continuous, we may simply replace, among other possibilities, the interpolation parameter Plenoptic modeling using relief mosaics Only local parallax changes can be rendered with a single relief mosaic. However relief mosaics can be used as building blocks for more general plenoptic modeling of larger environments. This gives a more powerful representation than plenoptic modeling [START_REF] Mcmillan | Plenoptic modeling: An image-based rendering system[END_REF] and a more space/construction efficient one than Lightfield/Lumigraph [START_REF] Levoy | Light field rendering[END_REF][START_REF] Gortler | The lumigraph[END_REF] and concentric mosaics [START_REF] Shum | Rendering with concentric mosaics[END_REF]. We have implemented a sparse horizontal Lightfield system for outward looking scenes.

Q © u A u7 ( by Q © u A u7 (
The viewing field consists of a roughly regular u h wv grid of images. It can be viewed as v relief mosaics each made from M images. Conceptually we may regard each static relief mosaic as a regular image as illustrated in Figure 5. The correspondence and JVT operations are then performed between composite images. However the correspondence information can not be computed directly from the composite images as they are not single perspective images. Instead, correspondence information is computed separately for each vertical pair

Results

The office scene was taken by a single camera moving off-line along a circle. The panorama can not be composed using traditional mosaic registration techniques due to its strong motion parallax. The relief mosaic at e 4u )f gf h 1 p gp resolution shown in Figure 7 was created from 36 video images at e g U h 1 p gp resolution. The significant parallax between adjacent images shown in Figure 1 (the maximum disparity can reach d dd U of the image size) makes composi- tion impossible with traditional mosaicing methods. Local parallax changes rendered with this relief mosaic are shown in Figure 6. A grid of h images at d U gU sr h f su )1 resolution of the wall containing the fresco and statues of Dunhuang cave #285 was captured with a hand-held camera. The grid contains 6 translating fronto-parallel views of the wall taken at 6 different depths. A relief mosaic was generated for each depth as shown in Figure 5. Figure 2 shows one of the static relief mosaics and Figure 4 shows local parallax changes of the central statue by varying p . Traditional mosaicing methods are impossible for these images as the statue has significant depth variation w.r.t. the moving camera. This grid of h images is used to create a horizontal lightfield described above. Some synthesized views are shown in Figure 8. A synthesized MPEG sequence with a circular viewer path in the horizontal field of the cameras is given in the conference CDROM (the image size is reduced due to storage limitations). The results are globally good, although there are occasional artifacts at abrupt disparity changes.

Conclusion

In this paper, we have presented relief mosaics which extend traditional mosaics by supporting motion parallax.

They can be viewed as 1 y u 3 plenoptic functions. They are composed of collections of images with parallax, for example captured using a moving hand-held camera. Motion parallax is allowed and no camera geometry information is necessary. Relief mosaics can be used to create highquality traditional mosaics, and also to render local parallax changes. Moreover, relief mosaics can be combined to form more complicated plenoptic-like models, giving a lightfield We may notice that a triangular patch is mis-placed in the front arm in the third view.

captured with a hand-held camera. This has been demonstrated with our system on an example with only h images. We are currently extending it to produce a more general (real) image based modeling and rendering system.

Figure 1 .

 1 Figure 1. The JVT of the two images. The corresponding patches are inside the black boundaries.

4 .

 4 Figure 2. A static relief mosaic at e 4f U gU ih qp sr )U composed from six images at d U gU gr th f gu g1 . The function b © u A u7 ( should guarantee a smooth tran- sition for the whole composite image, one possible choice might be b © u A u7 ( 8

  Do , with p rq U . For a given viewing window, when p rs d , the parameter Q o produces a synthetic view closer to the second camera position with p closer to 0. When p tq d it produces a syn- thetic view closer to the first camera position with increasing p . Figure 4 shows the local parallax changes rendered from the relief mosaic in Figure 2.

Figure 3 .

 3 Figure 3. A close-up zoom of a typical traditional mosaic from a hand-held camera. (top) a cylindrical mosaic by a global alignment method; (bottom) a mosaic by relief compositing method. The mosaic on the top is often ghosted due to the parallax of the foreground tree from non-negligible camera motion. The ghosting artifacts are removed using local warping for registration in the relief mosaic.

Figure 4 .

 4 Figure 4. Local parallax changes rendered at u U gU th u r u resolution from the relief mosaic in

Figure 2 .

 2 Figure 2.

Figure 5 .

 5 Figure 5. Each row of images are first composited into a relief mosaic for a horizontal lightfield.

Figure 6 .

 6 Figure 6. Local parallax changes rendered at 1 d U th 1 g1 U resolution from the relief mosaic in

Figure 7 .

 7 Figure 7.

Figure 7 .

 7 Figure 7. A static relief mosaic at e )u )f )f h 1 p gp from 36 video images. Note in Figure 1 that significant parallax exists in two adjacent images.

Figure 8 .

 8 Figure 8. Synthesized images at f U gU h u U )U resolution from the field of 36 images at d U gU gr ¦h f gu g1 resolution.

Acknoledgements

We greatly acknowledge Duanhuang Museum and Duanhuang Foundation for the help of acquiring images used in this paper. We would also like to thank Bill Triggs for many fruitful discussions.