Jacques Bres

Sascha Diwersy

Giancarlo Luxardo

The Competition between the Present Conditional and the Prospective Imperfect in French over the Centuries: first results

Keywords: prospective, subjective ulteriority, objective ulteriority, grammaticalization

While a significant number of works are known about the competition over the centuries between the synthetic future and the periphrastic prospective present, the parallel competition between the present conditional and the periphrastic construction with the prospective imperfect has received less attention. We focus here on the latter competition, limiting our study of the two forms to their temporal uses in discourse. We describe the uses for each form according to their order of appearance: imminence, subjective ulteriority and objective ulteriority. The two forms compete with each other in the expression of both subjective and objective ulteriority. We give an assessment of the diachronic evolution of the ratio present conditional / prospective imperfect in the expression of subjective ulteriority.

Introduction

Extensive work has been carried out in the area of French grammar about the competition over the centuries between the synthetic future (partira, 'leave-FUT-3SG') and the periphrastic construction with the prospective present (va partir, 'go-PRS-3SG leave-INF') (e.g. [START_REF] Damourette | Des mots à la pensée : essai de grammaire de la langue française[END_REF][1911-1936]; [START_REF] Fleischman | The future in thought and language[END_REF]Poplack & Turpin 1999;Poplack & Dion 2009;Vetters & Lière 2009;[START_REF] Lindschouw | L'évolution du système du futur du moyen français au français moderne : la réorganisation comme un cas de régrammation[END_REF][START_REF] Abouda | Du rapport entre formes synthétique et analytique du futur. Étude de la variable modale dans un corpus oral micro-diachronique[END_REF].

The main subjects of these analyses are (i) the diachronic evolution of the grammatical forms, i.e. the cycle of future tenses (analytical form → synthetic form → analytical form) and (ii) the illustration of the grammaticalization process of a movement verb into a temporal auxiliary.

Much less attention has been paid to the parallel competition between the present conditional (partirait, 'leave-COND-3SG') and the periphrastic construction with the prospective imperfect (allait partir, 'go-IMP-3SG leave-INF'), certainly because these forms occur less frequently. 1 Indeed, whereas different namings have been given to the construction va partir (e.g. futur proche, futur périphrastique, futur immédiat), nothing similar had occurred for allait partir 'go-IMP-3SG leave-INF'. [START_REF] Fleischman | The future in thought and language[END_REF], for instance, devoted a number of pages to the distinction between partira 'leave-FUT-3SG' and va partir 'go-PRS-3SG leave-INF', but none to the distinction between partirait 'leave-COND-3SG'and allait partir 'go-IMP-3SG leave-INF'.

The focus of this chapter is on the relationship between the two forms, the present conditional and the prospective imperfect, in their temporal uses. We first provide an explicit account of the uses in discourse of each form according to their diachronic appearance: a) subjective ulteriority (10 th century) and objective ulteriority (19 th century) for the conditional; b) imminence (15 th century), subjective ulteriority (16 th century) and objective ulteriority (late 18 th century) for the prospective imperfect. The two forms compete with each other in the expression of both subjective and objective ulteriority. Choosing to only address the question of diachronic evolution of the ratio present conditional / prospective imperfect in the expression of subjective ulteriority, we describe our corpus and the methodology we used (i.e. text retrieval and hierarchical clustering) for the experiment. Finally, we present and discuss the results of the study, including quantitative data and charts.

Preliminary comments should be made about the choice of the terms 'prospective present' (présent prospectif: va partir) and 'prospective imperfect' (imparfait prospectif: allait partir).

This choice is based on the fact that the current denomination 'periphrastic future' appears problematic for two reasons: first, it cannot be applied to allait partir as the auxiliary is in the imperfect; second, for both forms (present and imperfect), the denomination is relevant only for one meaning effect (admittedly frequent), i.e. ulteriority, while the periphrasis also produces imminence as another meaning (cf. infra 2.2). We will use the term prospective, proposed by [START_REF] Benveniste | Les relations de temps dans le verbe français[END_REF]Benveniste ( / 1966: 245) : 245) or Comrie (1976: 64), which allows us to group the various meanings produced by the periphrasis.

Uses in discourse of the present conditional and the prospective imperfect

Although both the present conditional and the prospective imperfect are likely to have either aspecto-temporal or modal uses [START_REF] Bres | Le conditionnel en français : énonciation, ultériorité dans le passé et valeurs modales[END_REF], we will only focus on the former.

The present conditional

The present conditional may have two types of temporal uses in discourse, subjective ulteriority and objective ulteriority, which are diachronically very distant: 2 Already in early texts from the 10 th century, the conditional is used to actualize an event as ulterior with respect to a past utterance. This past utterance may be explicit -indirect discourse as exemplified in (1) -or implicit -free indirect discourse as illustrated in (2).

(1) cil jurerent sus sainz lealment que il iroient ('go-COND-3PL') par les destroiz de Marroth. (Villehardouin, La Conquête de Constantinople, 1208)

'they swore on the gospel saints that they would go loyally through the straits of Morocco.'

(2) Il s'allongea, les yeux au plafond. Il remonterait ('go back up-COND-3SG') là-haut à la nuit tombante. (J. Carrière, L'Épervier de Maheux, 1972) 'He laid down, with his eyes to the ceiling. He would go back up there at dusk.'

Because ulteriority is assessed from an utterance, the process may then be realized or not: it falls within the scope of branching time [START_REF] Kripke | Semantical Considerations on Modal Logic[END_REF]Rescher et Urquhart 1971;Gardies 1975;[START_REF] Martin | Le futur linguistique : temps linéaire ou temps ramifié ? (à propos du futur et du conditionnel en français)[END_REF]). The past, as it is irrevocable, has a linear structure, whereas the future, because it falls under what is possible, has a ramified structure. The Crusaders in (1) either went through the straits of Morocco or they did not; similarly, the character in (2) either went back up or he did not.

Stage (b) -objective ulteriority

Starting from the 19 th century, due to a decline in subjective mediation, the conditional may indicate an event as being ulterior to another one in the objective unilinearity of the past [START_REF] Damourette | Des mots à la pensée : essai de grammaire de la langue française[END_REF][1911-1936], [START_REF] Nilsson-Ehle | Le conditionnel "futur du passé" et la périphrase devait + infinitif[END_REF][START_REF] Bres | Conditionnel et ultériorité dans le PASSÉ : de la subjectivité à l'objectivité[END_REF] 3 . This use of the conditional is not frequent. In this case, it may be glossed with a simple past as in ( 3) and ( 4):

(3) 'Relieved to be seen walking straight enough, Glory would prefer to return on foot rather than to take a taxi.'

In these two previous uses, the conditional is in competition with the prospective imperfect, and therefore it may be replaced by it (remonterait / allait remonter; préfèrerait / allait préférer).

The prospective imperfect

Aller is a prototypical instance of the grammaticalization of a spatial lexical unit into a grammatical unit indicating tense (e.g. [START_REF] Fleischman | The future in thought and language[END_REF][START_REF] Heine | World Lexicon of Grammaticalization[END_REF][START_REF] Mulder | Grammaticalisation, métaphore et métonymie: le cas d'aller[END_REF]Bres & Labeau 2013a) according to the "verb-to-affix cline", thus summarized by Hopper & Traugott (1993 :108): "full verb > auxiliary > clitic > affix". In the present case, it is the first step (auxiliarity). The movement verb aller, stage (a), is grammaticalized into an auxiliary of imminence, stage (b); then into an auxiliary of subjective ulteriority, stage (c);

and finally, into objective ulteriority, stage (d), according to a development path that may be represented as follows: Two other development paths of the grammaticalization for aller should be pointed out: first, the narrative use [START_REF] Gougenheim | Etude sur les périphrases verbales du français[END_REF][START_REF] Bres | La grammaticalisation de la forme itive comme prospectif dans les langues romanes[END_REF], found as early as the 13 th century as exemplified in ( 5), and second, the allure extraordinaire (since the 15 th ) [START_REF] Damourette | Des mots à la pensée : essai de grammaire de la langue française[END_REF][1911-1936], Bres & Labeau 2013b) as instantiated in ( 6):

( 'About this subject, in agreement, and while searching for an appropriate place to do this beautiful work, she told him that she didn't know a better or further one from suspicion, than a small house in the park where there was a suitable room and bed.'

In this example of narrative use, vat dire (go-PRS-3SG say-INF) competes with the passé simple (preterit). This construction, attested between the 13 th and 17 th centuries, is grammaticalized as a periphrastic preterit only in Catalan and a few Occitan dialects. 'She forgot her honor and conscience to such an extent that she loved a young man.'

The allure extraordinaire, which is constructed with all tenses, has spanned over the centuries and is today quite alive.

Stage (a) -movement

Aller, as a verb, means the displacement of an animated agent towards a destination, which will be reached at the end of this movement, therefore at a later stage than this very movement (Corinne allait, 'go-IMP-3SG') à Sète, 'Corinne was going to Sète'). This destination may be a process in the infinitive, which is realized at the end of this displacement, as in (7). This use, which is found in Vulgar Latin, is realized at all times. 'He left suddenly as soon as he knew that you loved him, he promised me that he was going to find a happy exit, and that around midnight you would be ready to leave silently.'

In (11), the prospective imperfect is in a complement clause and the ulteriority is thus assessed from the utterance (promettre) of an agent set in the past. The process will then be achieved or it will not: it falls into the scope of branching time.

Stage (d) -objective ulteriority

Starting from the end of the 18 th century, the prospective imperfect in an independent clause may, as a sign of the fading of the utterance of an agent, inscribe an event as subsequent in the linearity of the past. 'I had never thought to be so close to death; alas! It was going to happen to me under an even more real appearance. Roland comes back, he gets me out of the coffin.'

In this case, the prospective imperfect may be glossed by a simple past (passé simple) or by a present perfect (passé composé):

(12a) Je ne m'étais jamais crue si près de la mort ; hélas ! Elle s'offrit / s'est offerte ('happen-PRET-3SG' / 'be-PRS-3SG happen-PTCP-PST') pourtant à moi sous un aspect encore plus réel.

'I'd never thought to be so close to death; alas! It happened to me under an even more real appearance.'

The prospective imperfect actualizes an event which has taken place. It is fully inscribed in the objective unilinearity of the past.

With regard to this development path, it is worth mentioning that:

(i) the new meanings do not eliminate the former meanings, but add up with them;

(ii) the transition may be seamless: for instance, some occurrences may perfectly be relevant both to imminence and subjective ulteriority.

The competition between the prospective imperfect and the present conditional occurs in examples in stages (c) and (d): cases that do not represent the process in its pre-processual phase, as in stage (b), but in a processual phase referenced as ulterior, either subjectively (stage (c)) as in (11) or objectively (stage (d)) as in ( 12).

In order to follow diachronically the competition of the two forms, we now focus on subjective ulteriority, previously illustrated for the present conditional by examples (1) and

(2), and for the prospective imperfect by ( 11). As a consequence, since its use for both forms lies within the context of finite complement clauses and is introduced by the conjunction que (propositions complétives), these clauses can easily be retrieved in large amounts in a text corpus (with respect to other uses).

An experiment with a multi-genre diachronic corpus of annotated texts

Our study is based on the large body of texts gathered within the framework of the PRESTO project (ANR-DFG program). This project produced a corpus of 545 text samples (monographs, collections, etc.) from the 16 th to the 20 th centuries, belonging to various discursive genres (narrative, poetry, theatre, treatise, correspondence, etc.) -a part of these samples having been selected from well-known archives: Frantext, Épistémon, ARTFL, CÉPM (Corpus Électronique de la Première Modernité) and Gallica -(for details on the processing of the PRESTO corpus, cf. [START_REF] Diwersy | Traitements pour l'analyse du français préclassique[END_REF].

The whole corpus is categorized and lemmatized by means of a part-of-speech tagger (TreeTagger), which applies a linguistic annotation model designed and developed as part of the PRESTO Project. Table 3 gives an outline of the corpus we used. targeting sequences composed of the conjunction que followed by a verbal form in the present conditional or prospective imperfect. We then randomly selected 50% of the sequences matching the query, keeping the relative proportions per century. Then, the selected sequences were searched for instances meeting the requirement of subjective ulteriority in a finite complement clause. As a result, we were able to build a concordance comprising 3,067 lines, which was submitted to statistical processing and is presented in the following section.

Evolution of the competition between conditional and prospective

Table 4 shows the relative proportions per century of the present conditional and the prospective imperfect with respect to the occurrences observed in our concordance. In the following paragraphs, we focus our observations on the prospective imperfect form, since it is the one that starts to compete with the conditional and since the calculations related to the two forms are complementary. The previous figures reveal a steady increase of its proportion from the 16 th up to the 20 th century.

In order to examine more finely the changes occurring in each century, we reprocessed the results shown in Table 4 and analyzed them as a series of observations based on 25-year intervals. Such chronological series may be analyzed according to a procedure called Variability-based Neighbor Clustering (VNC), introduced by [START_REF] Gries | The identification of stages in diachronic data: variability-based neighbour clustering[END_REF][START_REF] Bres | Conditionnel et ultériorité dans le PASSÉ : de la subjectivité à l'objectivité[END_REF] and already implemented for the study of diachronic corpora. Figure 1 shows the VNC dendrogram for our data on the prospective imperfect, overlaid with a line plot representing the chronological evolution of its observed proportion in each of the 25-year intervals. 6 5). The dendrogram has to be analyzed from the top:

• a first split appears on the year 1950, indicating the main tipping point (isolating stage P04 on the right),

• in the cluster on the left, the year 1775 marks a second split (revealing stage P03),

• the last split is around the year 1650 (between P01 and P02).

If Figure 1 is read following the line of chronological evolution, two additional observations may be drawn from this figure:

throughout period P03 (and in particular between 1850 and 1950), the increase of the proportion of the prospective imperfect is characterized by some fluctuation;

the transition from P03 to P04 (second half of the 20 th century) marks a neat quantitative shift in the progression of the prospective imperfect. 'after having a discussion, they separated without agreement: on this, it was ordered that the conference proceedings be erased and that silent be kept on the contested materials.'

Testing the association between these two classes and the prospective imperfect in each of the diachronic stages, which we have identified, yields the following results if the loglikelihood ratio is chosen as statistical test 7 (in In other words, there is evidence that in the earlier stages of its evolution, the prospective imperfect is co-textually more dependent on the semantic category of the words that govern the complement clause in which it appears; whereas in the most recent stage (which corresponds more or less to contemporary French), it tends toward more autonomy, which might indicate a certain kind of generalization of its subjective use. The questions remain then as to (a) why the prospective imperfect is more likely to be found in complement clauses that represent reported perception and thought than in clauses that represent reported communication, and (b) whether a more fine-grained classification would reveal particular associations between the prospective imperfect and some subclasses (such as terms denoting perception in contrast to terms denoting cognition or emotion).

Besides testing the effects of a more fine-grained semantic classification, this analysis should be pursued with the inclusion of additional variables, but also with the observation of more than one variable at a time (multivariate analysis), which may provide new findings on the uses of these competitive forms. For now, we simply make note of the fact that, since the beginning, the ratio of the prospective imperfect has been constantly growing with respect to the present conditional, and that this evolution goes hand in hand with the balancing of the distribution that holds between the two major semantic classes of the words governing the complement clause in which the prospective imperfect appears.

Conclusion

In this chapter, we elucidated the temporal uses in discourse of the present conditional and the prospective imperfect according to their diachronic appearance and their competition in the expression of ulteriority. Firstly, we have outlined in detail the specific configurations underpinning this competition, and in a second step, we have chosen to primarily address the question of the diachronic evolution of the relationship between the present conditional and the prospective imperfect, in the expression of subjective ulteriority within the scope of finite complement clauses introduced by the conjunction que (propositions complétives). The data we extracted in this regard from a large corpus of text samples ranging from the 16 th to the 20 th century suggest that the proportion of prospective imperfect forms is steadily increasing over time and that this upward trend involves four successive stages. With respect to these four diachronic periods (ranging from 1500 to 1649, from 1650 to 1774, from 1775 to 1949 and from 1950 to 1999 respectively), we have then finally considered the influence of another variable, the semantic category of the introductory term, likely to impact the competition between present conditional and prospective imperfect, and we have shown that this variable had some significance, at least in the early stages of the competition.

It is our intention to test possible correlations with other variables, such as the discursive genre or the sociolinguistic dimension. So far, we have not been able to find evidence to support these hypotheses (the distribution of discursive genres found in the corpus studied here is related to the period of time).

Future steps of investigation may include the following questions:

Whereas both forms mean ulteriority, they are morphologically different: a synthetic form for the present conditional (which stems from the grammaticalization as an affix of avoir in the imperfect) and a periphrastic form for the prospective imperfect (which stems from a less advanced grammaticalization of the verb aller as an auxiliary). Does this morphological difference translate into a semantic difference when it comes to uses in discourse? In the corpus, is there a distribution of occurrences between the two that would be explained by a difference of temporal or enunciative representation of the process? Because of its derivation from the meaning of imminence, is the prospective imperfect initially (i.e. 16 th and 17 th centuries) used to signify imminent ulteriority? If so, has it loosened the instruction of imminence over the centuries, in order to more widely signify the ulteriority in the past and clearly compete with the conditional present? Is the difference at the enunciative level, as the prospective imperfect means the ulteriority of a process originating at the moment of a reported enunciation act, based on the analysis by Fleischman (1983: 190), of the present prospective as "express[ing] the speaker's subjective view at the moment of utterance"?

Is the competition in the expression of objective ulteriority similar to the competition in the expression of subjective ulteriority? Does the competition affecting the temporal uses of the conditional also affect some of its modal uses?

Is the competition present conditional / prospective imperfect similar to the competition synthetic future / prospective present? Are both competitions based on the same semantic difference between the synthetic form and the periphrasis?

To what extent does a new narrative construction, developed in the 20 th century (Bres & Labeau 2013c) and exemplified by ( 15) and ( 16), revive the old construction (5) or rather derive from the construction of ulteriority, both in the present and in the imperfect?

(

  5) Sur ces propos, feirent leur accord, et, en regardant le lieu le plus propre pour faire ceste belle oeuvre, elle vat dire ('go-PRS-3SG dire-INF') qu'elle n'en sçavoit poinct de meilleure ne plus loing de tout soupson, que une petite maison qui estoit dedans le parc, où il y avoit chambre et lict tout à propos. (M. de Navarre, L'Heptaméron 1550)

( 6 )

 6 elle oblya tellement son honneur et conscience, qu'elle alla aymer ('go-PRET-3SG love-INF') un jeune homme. (M. de Navarre, L'Heptaméron, 1511)

( 12 )

 12 Je ne m'étais jamais crue si près de la mort ; hélas ! Elle allait pourtant s'offrir ('go-IMP-3SG happen-INF') à moi sous un aspect encore plus réel. Roland revient, il me sort du cercueil. (Sade, Justine ou les Malheurs de la vertu, 1791)

Figure 1 :

 1 Figure 1: Variability-based Neighbor Clustering

  trends of periodization, let us now turn to the linguistic features that might be involved in the selection of the prospective imperfect or the present conditional when used to express subjective ulteriority. We choose as a starting point for further investigation the semantic category of the word (verb, noun or adjective) that takes the subordinate clause as its complement. Close inspection of the retrieved concordance shows that we are dealing with two major classes: (a) words expressing the mediation of perception and thought (class P, as illustrated in (13)) and (b) words expressing the mediation of communication (class C, as illustrated in (14)).(13) À l'angle de la petite allée qui conduit à la maison, il s'arrêta. On parlait dans la cuisine. Il sentit ('feel-PRET-3SG') que le souffle allait lui manquer. Ses jambes s'étaient remises à trembler. Il avança pourtant, l'oreille tendue.(B. Clavel, Les Fruits de l'hiver, 1968) 'In the angle of the small alley that leads to the house, he stopped. Somebody talked in the kitchen. He felt like the breath was going to leave him. His legs had started to tremble again. Yet he moved, listening carefully.' (14) après avoir bien disputé, on se sépara sans convention & sans accommodement : sur cela on ordonna ('order-PRET-3SG') que les actes de la conférence seroient supprimés, & qu'on garderoit le silence sur les matieres contestées. (D. Diderot & J. d'Alembert (s.l.d.), Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers, Tome 7, 1757)

Table 1 : conditional

 1

	Conditional	subjective	→ objective
		ULTERIORITY	ULTERIORITY
	Stages	(a) (10 th )	(b) (19 th )
	2.1.1 Stage (a) -subjective ulteriority

Table 2

 2

			: Prospective imperfect
	Aller	MOVEMENT → IMMINENCE →	subjective ULTERIORITY	→	objective ULTERIORITY
	Stages (a)	(b) (15 th )	(c) (16 th )		(d) (late 18 th )

  The movement creates a spatial gap -the process is reached at the end of this gap -which implies a temporal gap. By metonymy, one gets from the spatial gap to the temporal gap, to indicate the stage immediately preceding a process, namely, its imminence (as early as the From the representation of the pre-processual phase, one gets into the representation of ulteriority of the processual phase. And this is realized with an important enunciative modification: in order to produce the meaning of subjective ulteriority, the process must be in

	indirect speech, as shown in (11):
	(11) Il est parti soudain après votre amour sue, /A trouvé tout aisé, m'en a promis l'issue, /
	Qu'il allait y pourvoir ('go-IMP-3SG provide-INF') et que vers la minuit /Vous fussiez
	toute prête à déloger sans bruit. (P. Corneille, L'Illusion comique, 1639)
	15 th century), as in (8) and (9): 5

4 (7) Et Tronc lez mist en prison, et lez alloit ('go-IMP-3SG') visiter moult songneusement (anonyme, Ysaÿe le Triste, 1400) 'Tronc put them in prison and went to visit them with care.' 2.2.2 Stage (b) -imminence (8) Je m'en voys à la ville ; car je sçay bien que je trouveray tout prest à monter à cheval et mes gens aussi ; car le cappitaine de Crathor les alloit tous faire habiller ('go-IMP-3SG dress-INF'), quant je suis sailly icy avec vous. (Jean de Bueil, Le Jouvencel, 1461) 'I'm leaving for the city; for I know that I would find my men ready to mount their horses. The captain Crator was about to dress them when I left with you.' (9) -Il a des qualitez qui me le font vanter. -Il ne les auroit pas s'il n'alloit heriter ('go-IMP-3SG inherit-INF'). (P. du Ryer, Les Vendanges de Suresne, 1636)

'-He has qualities that make me praise him.

-He wouldn't have them if he wasn't about to inherit.' Allait + inf. represents the pre-processual phase, and may be glossed by « était sur le point de ». Therefore « s'il n'alloit hériter » ≈ « s'il n'était sur le point d'hériter », 'he wasn't about to inherit'.

The imminence may be avertive

[START_REF] Henry | Du subjonctif d'imminence contrecarrée à un passage du Tristan de Béroul[END_REF][START_REF] Kuteva | On Identifying an Evasive Gram: Action Narrowly Averted[END_REF]

, in that the right co-text means that the process is not realized, as in (

10

): (10) Elle m'allait traiter ('go-IMP-3SG treat-INF') en auteur du forfait,/ Mais ma fuite a rendu sa fureur sans effet. (P. Corneille, La Veuve ou le Traître trahi, 1634) 'She was about to treat me as the perpetrator of the crime. But my escape rendered her fury useless.' 2.2.3 Stage (c) -subjective ulteriority

Table 3 :

 3 Text samples comprising the PRESTO corpus

	Sample	Period	Genres	Texts	Words
	PRESTO_16s 16 th century narrative, poetry, theatre, treatise	50 3,048,984
	PRESTO_17s 17 th century narrative, poetry, theatre, treatise,	106 7,042,386
			correspondence
	PRESTO_18s 18 th century narrative, poetry, theatre, treatise,	128 7,762,787
			correspondence, encyclopedia
	PRESTO_19s 19 th century narrative, poetry, theatre, treatise,	150 8,592,846
			correspondence, press
	PRESTO_20s 20 th century narrative, poetry, theatre, treatise, press	111 8,692,270
	Total			545 35,139,273

In order to retrieve the clauses relevant to our study, we first ran a set of automated queries against the corpus (based on CQP -Corpus Query Processor, cf. Evert & Hardie 2011),

Table 4 :

 4 Distribution of the two forms per century

	Verbal form	16 th	17 th	18 th	19 th	20 th	Total
	ALLAIT + INF	3	22	58	54	158	295
	Conditional	210	727	819	438	578	2772
	Total occurrences	213	749	877	492	736	3067
	ALLAIT + INF	1,41 %	2,94 %	6,61 % 10,98 % 21,47 %	9,62 %
	(ratio)
	Conditional	98,59 % 97,06 % 93,34 % 89,02 % 78,53 % 90,38 %
	(ratio)

Table 5 :

 5 Four stages in the evolution of the prospective imperfect

	Period		Cumulative proportion (by period)
	P01	1500 -1649	1,49 %
	P02	1650 -1774	5,56 %
	P03	1775 -1949	11,00 %

Table 6

 6

	, the number of asterisks indicates

  15) Teddy Pendergrass est remarqué par Harold Melvin, leader du quintette vocal The Blue Notes. Il rejoint alors la formation, qui va enchaîner ('go-PRS-3SG go on-INF') une succession de tubes. En 1976, Teddy Pendergrass décide de mener une carrière solo et quitte les Blue Notes . Il va régulièrement occuper ('go-PRS-3SG occupy-INF') les premières places des meilleures ventes de disques aux USA. (Le Monde, Obituaire de T. Pendergrass, 27 .1. 2010) 'Teddy Pendergrass is noticed by Harold Melvin, leader of the vocal quintet The Blue Notes. He joins the group, who would go on to have a series of hits. In 1976, Teddy Pendergrass decides to start a solo career and leaves the Blue Notes. He would go on to regularly occupy the top of the best-selling discs in the USA.' (16) Le ballon frisait le montant d'un Buffon qui paraissait battu (9e). Le défenseur de l'Inter, peu à la fête jusqu'à présent, allait néanmoins se racheter ('go-IMP-3SG redeem-INF'). (Le Figaro, 09/07/2006) The ball grazed the goalpost of Buffon who appeared beat (9th). The defender of Inter, not really at the party up until now, would go on to nevertheless redeem himself. (Le Figaro, 09/07/2006) What happens to the competition present conditional / prospective imperfect in other Romance languages, which have grammaticalized "go" as a temporal auxiliary (e.g. Spanish or Portuguese)?

The log-likelihood ratio is used here as a statistical test to estimate the correlation between the two variables (semantic category and time): since the logarithm of the

As we are dealing with a configuration of two variables with two levels each, the calculated scores are exactly the opposite in terms of attraction and repulsion.

1 To the best of our knowledge, only Sarrazin & Azzopardi (2012) have so far addressed this issue (contrastively in French and Spanish), on oral contemporary corpora. 2 We borrow the adjectives subjective (≈ non-factive) and objective (≈ factive) from Nilsson-Ehle, 1943. 3 From subjective constructions to objective constructions, the variation is modal, but it is limited to the scope of the aspecto-temporal value of ulteriority. 4 E.g. in the Vulgate by Jerome (382): Veniunt adorare eum, "ils viennent l'adorer". 5 According to [START_REF] Detges | Wie entsteht Grammatik ? Kognitive und pragmatische Determinanten der Grammatikalisierung von Tempus Markern[END_REF], followed by De [START_REF] Mulder | Grammaticalisation, métonymie et pertinence[END_REF] (and in agreement with Bybee et al. 1994, according to whom the grammaticalization of a form as future goes through a development step, in which an intention is expressed), an intentionality step appears as soon as the 13 th century, therefore before the imminence step, by inference starting from the displacement meaning: the agent moves with the aim of doing this or that. We must recognize not being convinced by the examples proposed by Detges and De Mulder to validate the hypothesis of an autonomous intentionality step: the intentionality is assumed as soon as the first step, and we have not found any occurrence for which the intentionality does not go along with displacement.

6 Figure 1 includes in its main title the value yielded by Kendall's Tau rank correlation coefficient, which indicates a significant upward trend throughout the whole period of investigation. The use of Kendall's Tau for analyzing global trends in diachronic data has been suggested by Hilpert & Gries (2009:389-390).


Keywords: tracking, segmentation, graph cuts Suivi suivi, segmentation, coupe dans un graphe

This paper presents a new method to both track and segment multiple objects in videos using min-cut/max-flow optimizations. We introduce objective functions that combine low-level pixelwise measures (color, motion), high-level observations obtained via an independent detection module, motion prediction and contrast-sensitive contextual regularization. One novelty is that external observations are used without adding any association step. The observations are image regions (pixel sets) that can be output by any kind of detector. The minimization of these cost functions simultaneously allows "detection-before-track" tracking (track-to-observation assignment and automatic initialization of new tracks) and segmentation of tracked objects. When several tracked objects get mixed up by the detection module (e.g., single foreground detection mask for objects close to each other), a second stage of minimization allows the proper tracking and segmentation of these individual entities despite the observation confusion. Experiments on different type of sequences demonstrate the ability of the method to detect, track and precisely segment persons as they enter and traverse the field of view, even in cases of partial occlusions, temporary grouping and frame dropping.

Introduction

Visual tracking is an important and challenging problem in computer vision. Depending on applicative context under concern, it comes into various forms (automatic or manual initialization, single or multiple objects, still or moving camera, etc.), each of which being associated with an abundant literature.

Existing methods

In a recent review on visual tracking [START_REF] Yilmaz | Object tracking: A survey[END_REF], tracking methods are divided into three categories: point tracking, silhouette tracking and kernel tracking. These three categories can be recast as "detectbefore-track" tracking, dynamic segmentation and tracking based on distributions (color in particular).

"Detect-before-track" methods

The principle of "detect-before-track" methods is to match the tracked objects with observations provided by an independent detection module. Such a tracking can be performed with either deterministic or probabilistic methods.

Deterministic methods amount to matching by minimizing a distance between the object and the observations based on certain descriptors (position and/or appearance) of the object. The appearance (which can be for example the shape, the photometry or the motion of the object) is usually taken into account with histograms : the histograms of the object and an observation are compared using a distance measure, such as correlation, Bhattacharya coefficient or Kullback-Leibler divergence.

The observations provided by a detection algorithm are often corrupted by noise. Moreover, the appearance (motion, photometry, shape) of an object can vary a little between two consecutive frames. Probabilistic methods provide means to take measurement uncertainties into account. The are often based on a state space model of the object properties and the tracking of one object is performed using a filtering method (Kalman filtering [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF], particle filtering [START_REF] Gordon | Novel approach to nonlinear/non-gaussian bayesian state estimation[END_REF]). Multiple objects tracking can also be done with a filtering technique but a step of association between the objects and the observations must be added. The most popular methods for multiple objects tracking, in a "detect-before-track" framework, are the MHT (Multiple Hypotheses Tracking) [START_REF] Reid | An algorithm for tracking multiple targets[END_REF][START_REF] Cox | A review of statistical data association for motion correspondence[END_REF] and the JPDAF (Joint Probability Data Association Filtering) [START_REF] Bar-Shalom | Estimation and Tracking: Principles, Techniques, and Software[END_REF][START_REF] Bar-Shalom | Multisensor-multitarget tracking: Principles and Techniques[END_REF].

Dynamic segmentation

Dynamic segmentation aims at extracting successive segmentations over time. A detailed silhouette of the target object is thus sought in each frame. This is often done by making evolve the silhouette obtained in the previous frame towards a new configuration in current frame. The silhouette can either be represented by a set of parameters or by an energy function. In the first case, the set of parameters represents a state space model that permits to track the contour with a filtering method. For example, in [START_REF] Terzopoulos | Tracking with kalman snakes[END_REF], some control points are positioned all along the contour and their dynamics define the state model. The correction of the points position is obtained using the image gradients. In [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF], the authors proposed to model the state with a set of splines and some motion parameters. The tracking is then achieved with a particle filter. This technique was extended to multiple objects tracking in [START_REF] Maccormick | A probabilistic exclusion principle for tracking multiple objects[END_REF].

Previous methods do not deal with the topology changes of an object (fusion and/or split). By minimizing an energy function, the changes can be handled. The object is defined as a mask of pixels [START_REF] Paragios | Geodesic active regions for motion estimation and tracking[END_REF][START_REF] Criminisi | Bilayer segmentation of live video[END_REF] or by the zero level set of a continuous function [START_REF] Paragios | Adaptive detection and localization of moving objects in image sequences[END_REF][START_REF] Shi | Real-time tracking using level sets[END_REF]. In both cases, the contour energy includes some temporal information in the form of either temporal gradients (optical flow) [START_REF] Bertalmio | Morphing active contours[END_REF][START_REF] Cremers | Statistical shape knowledge in variational motion segmentation[END_REF][START_REF] Mansouri | Region tracking via level set pdes without motion computation[END_REF] or appearance statistics originated from the object and its surroundings in previous images [START_REF] Ronfard | Region-based strategies for active contour models[END_REF][START_REF] Yilmaz | Contour-based object tracking with occlusion handling in video acquired using mobile cameras[END_REF]. In [START_REF] Xu | Object contour tracking using graph cuts based active contours[END_REF] the authors use graph cuts to minimize such an energy functional. The advantages of min-cut/max-flow optimization are its low computational cost, the fact that it converges to the global minimum without getting stuck in local minima and that no a priori on the global shape model is needed. They have also been used in [START_REF] Criminisi | Bilayer segmentation of live video[END_REF] in order to successively segment an object through time using a motion information.

"Kernel tracking"

This last group of methods aims at tracking a small and simple portion of the image (often a rectangle or an ellipse) based on the appearance. The best location of the region in the current frame is the one for which some feature distributions (e.g., color) are the closest to the reference one for the tracked object. Two approaches can be distinguished : the ones that assume a local conservation of the appearance of the object and the ones that assume this conservation to be global. The most popular INRIA method for local conservation is probably the KLT approach [START_REF] Shi | Good features to track[END_REF]. For the global conservation, the most often used technique is the one of Comaniciu et al. [START_REF] Comaniciu | Real-time tracking of non-rigid objects using meanshift[END_REF][START_REF] Comaniciu | Kernel-based optical tracking[END_REF], where approximate "mean shift" iterations are used to conduct the iterative search. Graph cuts have also been used for illumination invariant kernel tracking in [START_REF] Freedman | Illumination-invariant tracking via graph cuts[END_REF].

Advantages and limits of previous approaches

These three types of tracking techniques have different advantages and limitations, and can serve different purposes. The "detect-before-track" approaches can deal with the entrance of new objects in the scene or the exits of existing ones. They use external observations that, if they are of good quality, might allow robust tracking. On the contrary if they are of low quality the tracking can be deteriorated. Therefore, "detect-before-track" methods highly depend on the quality of the observations. Furthermore the restricted assumption that one object can only be associated to one observation is often made. Finally, this kind of tracking usually outputs bounding boxes only.

By contrast, silhouette tracking has the advantage of directly providing the segmentation of the tracked object. Representing the contour by a set of parameters allows the tracking of an object with a relatively small computational time. On the other hand these approaches do not deal with topology changes. Tracking by minimizing an energy functional allows the handling of topology changes but not always of occlusions (it depends on the dynamics used). It can also be computationally inefficient and the minimization can converge to local minima of the energy. With the use of recent graph cuts techniques, convergence to the global minima is obtained for modest computational cost. However, a limit of most silhouette tracking approaches is that they do not deal with the entrance of new objects in the scene or the exits of existing ones.

Finally kernel tracking methods, by capturing global color distribution of a tracked object, allow robust tracking at low cost in a wide range of color videos. They also do not deal with the entrance of new objects in the scene or the exits of existing ones, and the do not give the complete segmentation of the objects. Furthermore they are not well adapted to the tracking of small objects.

Overview of the paper

In this paper, we address the problem of multiple objects tracking and segmentation by combining the advantages of the three classes of approaches. We suppose that, at each instant, the moving objects are approximately known thanks to some preprocessing algorithm. These moving objects form the observations (as explained in section 2). Here, we will first use a simple background subtraction (the connected components of the detected foreground mask serve as high-level observations) and then a more complex approach [START_REF] Bugeau | Detection and segmentation of moving objects in highly dynamic scenes[END_REF] dedicated to moving objects detection in complex scenes. An important novelty of our method is that the use of external observations does not require the addition of a preliminary association step. The association between the tracked objects and the observations is jointly conducted with the segmentation and the tracking within the proposed minimization method.

At each time instant, tracked object masks are propagated using their associated optical flow, which provides predictions. Color and motion distributions are computed on the objects in previous frame and used to evaluate individual pixel likelihood in the current frame. We introduce for each object a binary labeling objective function that combines all these ingredients (low-level pixel-wise features, high-level observations obtained via an independent detection module and motion predictions) with a contrast-sensitive contextual regularization. The minimization of each of these energy functions with min-cut/max-flow provides the segmentation of one of the tracked objects in the new frame. Our algorithm also deals with the introduction of new objects and their associated tracker.

When multiple objects trigger a single detection due to their spatial vicinity, the proposed method, as most detect-before-track approaches, can get confused. To circumvent this problem, we propose to minimize a secondary multi-label energy function which allows the individual segmentation of concerned objects.

The paper is organized as follows. First, in section 2, the notations are introduced and the objects and the observations are described. In section 3, an overview of the method is given. The primary energy function associated to each tracked object is introduced in section 4. The introduction of new objects is also explained in this section. The secondary energy function permitting the separation of objects wrongly merged in the first stage is introduced in section 5. Experimental results are reported in section 6, where we demonstrate the ability of the method to detect, track and precisely segment objects, possibly with partial occlusions and missing observations. The experiments also demonstrate that the second stage of minimization allows the segmentation of individual objects when spatial proximity makes them merge at the foreground detection level.

Description of the objects and of the observations

For the clarity of the paper, we start by explaining what are the objects and the observations we are manipulating and how they are obtained.

Description of the objects

In all this paper, P will denote the set of N pixels of a frame from an input image sequence. To each pixel s of the image at time t is associated a feature vector

z t (s) = (z (C) t (s), z (M) t (s)),
where z (C) t (s) is a 3-dimensional vector in the color space and z (M ) t (s) is a 2-dimensional vector of optical flow values. We consider a chrominance color space (here we use the YUV space, where Y is luminance and U and V the chrominances) because the objects that we will track often contain skin, which is better characterized in such a space [START_REF] Kjeldsen | Finding skin in color images[END_REF][START_REF] Singh | Regression based bandwidth selection for segmentation using parzen windows[END_REF]. Furthermore, a chrominance space has the advantage of having the three channels, Y, U and V, uncorrelated. The optical flow vectors are computed using an incremental multiscale implementation of Lucas and Kanade algorithm [START_REF] Lucas | An iterative technique of image registration and its application to stereo[END_REF]. This method does not hold for pixels with insufficiently contrasted surroundings. For these pixels, the motion is not computed and color constitutes the only low-level feature. Therefore, although not always explicit in the notation for the sake of conciseness, one should bear in mind that we only consider a sparse motion field. We assume that, at time t, kt objects are tracked. The i th object at time t is denoted as

O (i)
t and is defined as a mask of pixels, O (i) t ⊂ P. The pixels of a frame not belonging to the object O (i) t belong to the "background" of this object. Both the objects and the backgrounds will be represented by a distribution that combines motion and color information. Each distribution is a mixture of Gaussians1 . For object i at instant t, this distribution, denoted as p (i) t , is fitted to the set of values {zt(s)} s∈O (i)

t

. We consider that motion and color information are independent. Hence, the distribution p (i) t is the product of a motion distribution

p (i,M ) t (fitted to the set of values {z (M ) t (s)} s∈O (i) t
) and a color distribution,

p (i,C) t (fitted to the set of values {z (C) t (s)} s∈O (i) t
). Under this independency assumption for color and motion, the likelihood of individual pixel feature z t (s) according to previous joint model is:

p (i) t (z t (s)) = p (i,C) t (z (C) t (s)) p (i,M) t (z (M) t (s)). (1)
As we consider only a sparse motion field, only the color distribution is taken into account for the pixels not having an associated motion vector:

p (i) t (zt(s)) = p (i,C) t (z (C) t (s)).
The background distributions are computed in the same way. The distribution of the background of object i at time t, denoted as q (i) t , is a mixture of Gaussians fitted to the set of values

{zt(s)} s∈P\O (i) t
. It also combines motion and color information:

q (i) t (z t (s)) = q (i,C) t (z (C) t (s)) q (i,M) t (z (M) t (s)). (2)

Description of the observations

The goal of this paper is to perform both segmentation and tracking to get the object

O (i) t correspond- ing to the object O (i)
t-1 of previous frame. Contrary to sequential segmentation techniques [START_REF] Juan | Active graph cuts[END_REF][START_REF] Kohli | Effciently solving dynamic markov random fields using graph cuts[END_REF][START_REF] Paragios | Geodesic active regions for motion estimation and tracking[END_REF], we bring in object-level "observations". We assume that, at each time t, there are mt observations. The j th observation at time t is denoted as M (j) t and is defined as a mask of pixels, M (j) t ⊂ P.

As objects and backgrounds, an observation j at time t is represented by a distribution, denoted as ρ (j) t , which is a mixture of Gaussians combining color and motion informations. The mixture is fitted to the set {zt(s)} s∈M (j) t and is defined as:

ρ (j) t (z t (s)) = ρ (j,C) t (z (C) t (s)) ρ (j,M) t (z (M) t (s)). (3)
The observations may be of various kinds (e.g., obtained by a class-specific object detector, or motion/color detectors). Here we will consider two different types of observations.

Background subtraction

The first type of observations comes from a preprocessing step of background subtraction. Each observation amounts to a connected component of the foreground map after subtracting a reference frame from the current frame (figure 1). The connected components are obtained using the "gap/mountain" method described in [START_REF] Wang | Moving object tracking in video[END_REF] and ignoring small objects.

For the first frame, the tracked objects will be initialized as the observations themselves.

Moving objects detection in complex scenes

In order to be able to track objects in more complex sequences, we will use a second type of objects detector. The method considered is the one from [START_REF] Bugeau | Detection and segmentation of moving objects in highly dynamic scenes[END_REF] that can be decomposed in three main steps.

First, a grid of moving pixels having valid flow vectors is selected. Each point is described by its position, its color and its motion. Then these points are partitioned based on a mean shift algorithm [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], leading to several moving clusters, and finally segmentation of the objects are obtained from the moving clusters by performing a graph cuts based segmentation. This last step can be avoided here. Indeed, since in this paper we will propose a method that simultaneously track and segment objects, the observations do not need to be a segmented object. Therefore, the observations will directly be the detected moving clusters (figure 2). The last step of the detection method will only be used when initializing new objects to track. When our algorithm outputs that a new tracker should be created from a given observation, the tracker is initialized with the corresponding segmented detected object.

In the detection method, flow vectors are only computed on the points of the grid. Therefore, in our tracking algorithm, when using this type of observations, we will keep considering that only the points of the grid are characterized by a motion and a color vector. All the other points will only be characterized by their color. The motion field is then really sparse here.

Principle of the method

Before presenting our approach into detail, we start by presenting its main principle. In particular, we explain why it is decomposed into two steps (first a segmentation/tracking method and then, when necessary, a further segmentation step) and why each object is tracked independently.

Tracking each object independently

We propose in this paper a tracking method based on energy minimizations. Minimizing an energy with min-cut/max-flow [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] (also known as Graph Cuts) permits to assign a label to each pixel of an image. As in [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images[END_REF], the labeling of one pixel will here depend on the closeness between the appearance at a pixel and the objects appearances and also on the similarity between this pixel and its neighbor. Indeed, a smoothness binary term that encourages two neighboring having close appearance to get the same label is added to the energy function.

In our tracking scheme, we wish to assign a label corresponding to one of the tracked objects to each pixel of the image. By using a multi-label energy function (each label corresponding to one object), all objects would be directly tracked simultaneously by minimizing a single energy function. However, in our algorithm, we do not use such an energy and each object will be tracked independently. Such a choice comes from the will to distinguish the merging of several objects from the INRIA occlusions of some objects by another one, which can not be done using a multi-label energy function. Let us illustrate this problem on an example. Assume that two objects having similar appearance are tracked. We are going to analyze and compare the two following scenarios (described on figure 3). On the one hand, we suppose that the two objects become connected in the image plane at time t First, suppose that these two objects are tracked using a multi-label energy function. Since the appearance of the objects is similar, when they get side by side (first case), the minimization will tend to label all the pixels in the same way (due to the smoothness term). Hence, each pixel will probably be assigned the same label, corresponding to only one of the tracked objects. In the second case, when one object occludes the other one, the energy minimization leads to the same result: all the pixels have the same label. Therefore, it is possible for these two scenarios to be mixed up.

Assume now that each object is tracked independently by defining one energy function per object (each object is then associated to k t-1 labels). For each object the final label is either "object" or "background". For the first case, each pixel of the two objects will be, at the end of the two minimizations, labeled as "object". For the second case, the pixels will be labeled as "object" when the minimization is done for the occluding object and as "background" for the occluded one. Therefore, by defining one energy function per object, we are able to differentiate the two cases. Of course, for the first case, the obtained result is not the wanted one: the pixels get the same label which means that the two objects have merged. In order to keep differentiating the two objects, we will add to our tracking method a step of separation of the merged objects.

The principles of the tracking and the separation of merged objects are explained in next subsections.

Principle of the tracking method

The principle of our algorithm is as follows. A prediction O (i) t|t-1 ⊂ P is made for each object i of time t -1. We denote as d (i) t-1 the mean, over all pixels of the object at time t -1, of optical flow values:

d (i) t-1 = s∈O (i) t-1 z (M) t-1 (s) |O (i) t-1 | . ( 4
)
The prediction is obtained by translating each pixel belonging to O (i) t-1 by this average optical flow:

O (i) t|t-1 = {s + d (i) t-1 , s ∈ O (i) t-1 } . (5)
Using this prediction, the new observations, as well as the distribution p (i)

t of O (i) t-1
, an energy function is built. The energy is minimized using min-cut/max-flow algorithm [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF], which gives the new segmented object at time t, O (i) t . The minimization also provides the correspondences of the object with all the available observations, which directly leads to the creation of new objects to track. Our tracking algorithm is summed up in figure 4.

(i) t-1 O (i) t-1 O (i) t|t-1

Creation of new objects

Observations

O (i) t

Principle of the segmentation of merged objects

At the end of the tracking step, several objects can have merged, i.e. the results of the segmentations for different objects overlap, that is ∩ i=1...kt O (i) t = ∅. In order to keep tracking each object separately, the merged objects must be separated. This will be done by adding a multi-label energy minimization.

Energy functions

We define one tracker for each object. To each tracker corresponds, for each frame, one graph and one energy function that is minimized using the min-cut/max-flow algorithm [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Nodes and edges of the graph can be seen in figure 5. In all this paper, we consider a 8-neighborhood system. However, for clarity, on all the figures representing a graph, only a 4-neighborhood is represented.

Graph

The undirected graph Gt = (Vt, Et) is defined as a set of nodes Vt and a set of edges Et. The set of nodes is composed of two subsets. The first subset is the set of N pixels of the image grid P. The second subset corresponds to the observations: to each observation mask M (j) t is associated a node n (j) t . We call these nodes "observation nodes". The set of nodes thus reads Vt = P {n

O (i) t|t-1
Graph for object i at time t assigning a binary label l (i) j,t ("bg" or "fg") to each observation node n (j)

t . The set of all the node labels forms L (i) t .

Energy

An energy function is defined for each object i at each instant t. It is composed of unary data terms

R (i)
s,t and smoothness binary terms B (i) s,r,t :

E (i) t (L (i) t ) = s∈Vt R (i) s,t (l (i) s,t ) + {s,r}∈Et B (i) {s,r},t (1 -δ(l (i) s,t , l (i) r,t )). (6)
In order to simplify the notations, we omit in the rest of this section the index i. Previous equation is then rewritten as:

E t (L t ) = s∈Vt R s,t (l s,t ) + {s,r}∈Et
B {s,r},t (1δ(l s,t , l r,t )).

(7)

Data term

The data term only concerns the pixel nodes lying in the predicted regions and the observation nodes. For all the other pixel nodes, labeling will only be controlled by the neighbors via binary terms. More precisely, the first part of energy in [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] reads

: s∈Vt R s,t (l s,t ) = s∈O t|t-1 -ln(p 1 (s, l s,t )) + α mt j=1 d 2 (j, l j,t ). ( 8
)
Segmented object at time t should be similar, in terms of motion and color, to the preceding instance of this object at time t -1. To exploit this consistency assumption, the distribution of the object, p (i) t-1 (equation 1), and of the background, q (i) t-1 (equation 2), from previous image, are used. Remember that we chose to omit the index of the object. Previous distributions are then denoted as pt-1 and qt-1. The likelihood p1, within predicted region, is finally defined as:

p 1 (s, l) = p t-1 (z t (s)) if l = "fg", q t-1 (z t (s)) if l = "bg" . (9)
In the same way, an observation should be used only if it is likely to correspond to the tracked object. To evaluate the similarity of observation j at time t and object i at previous time, a comparison between the distributions p (i)

t-1 and ρ (j) t (equation 3) and between q (i) t-1 and ρ (j) t must be performed through the computation of a distance measure. A classical distance to compare two mixtures of Gaussians, G1 and G2, is the Kullback-leibler distance [START_REF] Kullback | On information and sufficiency[END_REF], defined as:

KL(G 1 , G 2 ) = G 1 (x)log G 1 (x) G 2 (x) dx. ( 10
)
The likelihood p1, is finally:

d 2 (s, l) = KL(ρ (j) t , p t-1 ) if l = "fg", KL(ρ (j) t , q t-1 ) if l = "bg" . (11)
A constant α is included in the data term in equation ( 8) to give more or less influence to the observations. As only one node is used to represent the whole mask of pixels of an observation, we have chosen to fix α equal to the number of pixels belonging to the observation, that is α = |M (j) t |.

Binary term

Following [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images[END_REF], the binary term between neighboring pairs of pixels {s, r} of P is based on color gradients and has the form

B {s,r},t = λ 1 1 dist(s, r) e - z (C) t (s)-z (C) t (r) 2 σ 2 T
.

As in [START_REF] Blake | Interactive image segmentation using an adaptive gmmrf model[END_REF], the parameter σT is set to σT = 4

• (z (C) t (s) -z (C) t (r)) 2
, where . denotes expectation over a box surrounding the object.

For edges between one pixel node and one observation node, the binary term depends on the distance between the color of the observation and the pixel color. More precisely, it is computed as

B {s,n (j) t },t = λ 2 ρ (j) t (z (C) t (s)). (13)
Parameters λ1 and λ2 are discussed in the experiments.

Energy minimization

The final labeling of pixels is obtained by minimizing, with 'the "Expansion Move" algorithm [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF], the energy defined above:

L(i) t = arg min L (i) t E (i) t (L (i) t ). (14)
This labeling gives the segmentation of the i-th object at time t as:

O (i) t = {s ∈ P : l(i) s,t = "fg"}. ( 15
)

Creation of new objects

One advantage of our approach lies in its ability to jointly manipulate pixel labels and track-todetection assignment labels. This allows the system to track and segment the objects at time t while establishing the correspondence between an object currently tracked and all the approximative object candidates obtained by detection in current frame. If, after the energy minimization for an object i, an observation node n (j) t is labeled as "fg" ( l(i) t,j = "fg") it means that there is a correspondence between INRIA the i-th object and the j-th observation. Conversely, if the node is labeled as "bg", the object and the observation are not associated.

If for all the objects (i = 1, . . . , kt-1), an observation node is labeled as "bg" (∀i, l(i) t,j = "bg"), then the corresponding observation does not match any object. In this case, a new object is created and initialized with this observation. The number of tracked objects becomes kt = kt-1 + 1, and the new object is initialized as:

O (kt) t = M (j)
t . In practice, the creation of a new object will only be validated if the new object is associated to at least one observation at time t + 1, i.e., if ∃ j ∈ {1 . . . m t+1 } such that l(i) j,t+1 = "fg".

Segmenting merged objects

Assume now that the results of the segmentations for different objects overlap, that is

∩ i∈F O (i) t = ∅,
where F denotes the current set of object indices. In this case, we propose an additional step to determine whether these objects truly correspond to the same one or if they should be separated. At the end of this step, each pixel of ∩i∈F O (i) t must belong to only one object. For this purpose, a new graph Gt = ( Ṽt, Ẽt) is created, where Ṽt = ∪i∈F O (i) t and Ẽt is composed of all unordered pairs of neighboring pixel nodes of Ṽt. An exemple of such a graph is presented on figure 6. (1δ(ψ s , ψ r )).

The parameter σ3 is here set as σ3 = 4 • (zt(s) (i,C)zt(r) (i,C) ) 2 with the averaging being over i ∈ F and {s, r} ∈ Ẽ. The fact that several objects have been merged shows that their respective feature distributions at previous instant did not permit to distinguish them. A way to separate them is then to increase the role of the prediction. This is achieved by choosing function p3 as:

p 3 (s, ψ) = p (ψ) t-1 (z t (s)) if s / ∈ O (ψ) t|t-1 , 1 otherwise . ( 17
)
This multi-label energy function is minimized using the swap algorithms [START_REF] Boykov | Markov random fields with efficient approximations[END_REF][START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. After this minimization, the objects O (i) t , i ∈ F are updated.

Experimental Results

This section presents various results of the tracking and the separation of merged objects. First, we will consider a relatively simple sequence, with static background, in which the observations are obtained by background subtraction (subsection 2.2.1). Next the tracking method will be combined to the moving objects detector of [START_REF] Bugeau | Detection and segmentation of moving objects in highly dynamic scenes[END_REF] (subsection 2.2.2). For all results, a color is associated to each tracked object. This color only depends on the arbitrary order in which the objects are created.

Tracking objects detected with background subtraction

We start by demonstrating, on a sequence from the PETS 2006 data corpus (sequence 1 camera 4), the validity of the tracking method as well as the robustness to partial occlusions and the individual segmentation of objects that were initially merged. Following [START_REF] Blake | Interactive image segmentation using an adaptive gmmrf model[END_REF], the parameter λ3 was set to 20. However parameters λ1 and λ2 had to be tuned by hand to get better results. Indeed, λ1 was set to 10 while λ2 to 2. Also, the number of classes for the Gaussian mixture models was set to 10.

First results (figure 7) demonstrate the good behavior of our algorithm even in the presence of partial occlusions and of object fusion. Observations, obtained by subtracting reference frame (frame 10 shown on figure 1(a)) to the current one, are visible in the second column of figure 7. The third column contains the segmentation of the objects with the use of the second energy function. In frame 81, two objects are initialized using the observations. Note that the connected component extracted with the "gap/mountain" method misses the legs for the person in the upper right corner. While this impacts the initial segmentation, the legs are included in the segmentation as soon as the subsequent frame.

The proposed methods deals easily with the entrance of new objects in the scene. This result also shows the robustness of our method to partial occlusions. Partial occlusions occur when the person at the top passes behind the three other ones (frames 176 and 206). Despite the similar color of all the objects, this is well handled by the method, as the person is still tracked when the occlusion stops (frame 248).

Finally note that, even if from the 102 nd frame the two persons at the bottom of the frames correspond to only one observation and have a similar appearance (color and motion), our algorithm tracks each person separately (frames 116, 146). In figure 8, we show in more details the influence of the second energy function by comparing the results obtained with and without it. Before frame 102, the three persons at the bottom generate three distinct observations while, passed this instant, they correspond to only one or two observations. Even if the motions and colors of the three persons are very close, the use of the secondary multi-label energy function allows their separation.

Tracking objects in complex scenes

We are now going to show the behaviour of our tracking algorithm when the sequences are more complex (dynamic background, moving camera ...). For each sequence, the observations are the moving clusters detected with the method of [START_REF] Bugeau | Detection and segmentation of moving objects in highly dynamic scenes[END_REF]. In all this subsection, the parameter λ3 was set to 20, λ1 to 10, and λ2 to 1.

The first result is on a water skier sequence (figure 9). For each image, the moving clusters and the masks of the tracked objects are superimposed on the original image. The proposed tracking method permits to track correctly the water skier (or more precisely his wet suit) all along the sequence, despite the trajectory changes. As can be seen on the figure (for example at time 58), the detector sometimes fails to detect the skier. No observations are then available. However, thanks to the use of the prediction of the object, our method handles well this kind of situations and keeps tracking and segmenting correctly the skier. This shows the robustness of the algorithm to missing observations. However if some observations are missing for several consecutive frames, the segmentation can be a bit deteriorated. Conversely, this means that the incorporation of observations from the detection module enables to get better segmentations than when using only predictions. On several frames, some moving clusters are detected in the water. Nevertheless, no objects are created in this area. The reason is that the creation of a new object is only validated if the new object is associated to at least one observation in the following frame. This never happened in the sequence.

We end by showing results on a driver sequence (figure 10). The first object detected and tracked is the face. Once again, tracking this object shows the robustness of our method to missing observations. Indeed, even if from frame 19, the face does not move and therefore is not detected, the algorithm keeps tracking and segmenting it correctly until the driver starts turning it. The most important result on this sequence is the hands tracking. In image 39, the masks of the two hands are merged: they have a few pixels in common. The step of segmentation of merged objects is then applied which allows the correct separation of the two masks and permits to keep tracking these two objects separately. Finally, as can been seen on frame 57, our method deals well with the exit of an object from the scene.

Conclusion

In this paper we have presented a new method to simultaneously segment and track objects. Predictions and observations, composed of detected objects, are introduced in an energy function which is minimized using graph cuts. The use of graph cuts permits the segmentation of the objects at a modest computational cost (of course the computational time depends on the objects detection and the distributions computation). A novelty is the use of observation nodes in the graph which gives better segmentations but also enables the direct association of the tracked objects to the observations (without adding any association procedure). The algorithm is robust to partial occlusions, progressive illumination changes and to missing observations. Thanks to the use of a secondary multi-label energy function, our method allows individual tracking and segmentation of objects which where not distinguished from each other in the first stage. The observations used in this paper are obtained firstly by a simple background subtraction based on a single reference frame and secondly by a more complicated moving object detector. Note however that any object detection method could be used as well with no change to the approach, as soon as the observations can be represented by a mask of pixels.

As we use feature distributions of objects at previous time to define current energy functions, our method breaks down in extreme cases of abrupt illumination changes. However, by adding an external detector of such changes, we could circumvent this problem by keeping only the prediction and by updating the reference frame when the abrupt change occurs. Also, other cues, such as shapes, could probably be added to improve the results.

Apart from this rather specific problem, several research directions are open. One of them concerns the design of an unifying energy framework that would allow segmentation and tracking of

Figure 1 :

 1 Figure 1: Observations obtained with background subtraction. (a) Reference frame. (b) Current frame. (c) Result of background subtraction (pixels in black are labeled as foreground) and derived object detections (indicated with red bounding boxes).

Figure 2 :

 2 Figure 2: Observations obtained with [8] on a water skier sequence shot by a moving camera. (a) Detected moving clusters superposed on the current frame. (b) Mask of pixels characterizing the observation.

Figure 3 :

 3 Figure 3: Merge of several objects or occlusion?and, on the other hand, that one of the objects occludes the second one at time t.First, suppose that these two objects are tracked using a multi-label energy function. Since the appearance of the objects is similar, when they get side by side (first case), the minimization will tend to label all the pixels in the same way (due to the smoothness term). Hence, each pixel will probably be assigned the same label, corresponding to only one of the tracked objects. In the second case, when one object occludes the other one, the energy minimization leads to the same result: all the pixels have the same label. Therefore, it is possible for these two scenarios to be mixed up.Assume now that each object is tracked independently by defining one energy function per object (each object is then associated to k t-1 labels). For each object the final label is either "object" or "background". For the first case, each pixel of the two objects will be, at the end of the two minimizations, labeled as "object". For the second case, the pixels will be labeled as "object" when the minimization is done for the occluding object and as "background" for the occluded one. Therefore, by defining one energy function per object, we are able to differentiate the two cases. Of course, for the first case, the obtained result is not the wanted one: the pixels get the same label which means that the two objects have merged. In order to keep differentiating the two objects, we will add to our tracking method a step of separation of the merged objects.

Figure 4 :

 4 Figure 4: Principle of the algorithm

Figure 5 :

 5 Figure 5: Description of the graph. The left figure is the result of the energy minimization at time t -1. White nodes are labeled as object and black nodes as background. The optical flow vectors for the object are shown in blue. The right figure shows the graph at time t. Two observations are available, each of which giving rise to a special "observation" node. The pixel nodes circled in red correspond to the masks of these two observations. Dashed box indicates predicted mask.

Figure 6 : 3 {s

 63 Figure 6: Graph example for the segmentation of merged objects.

Figure 7 :Figure 8 :

 78 Figure 7: Results on sequence from PETS 2006 (frames 81, 116, 146, 176, 206 and 248). (a) Original frames. (b) Result of simple background subtraction and extracted observations. (c) Tracked objects on current frame using the secondary energy function.

INRIA

Figure 9 :

 9 Figure 9: Results on a water skier sequence. The observations are moving clusters detected with the method in [8]. At each time, the observations are shown on the left image while the masks of the tracked objects are shown on the right image.

Figure 10 :

 10 Figure 10: Results on a driver sequence. The observations are moving clusters detected with the method in [8]. At each time, the observations are shown on the left image while the masks of the tracked objects are shown on the right image.

RR n°6337

All mixtures of Gaussians evoked in this paper are fitted using the Expectation-Maximization (EM) algorithm.INRIA