From "the Doors of the Seas" to a Watery Debacle

Keywords: long XVIIIe siècle, Darien, Écosse et colonisation, Compagnie écossaise de long 18th century, Darien, Scotland and colonization

Sophie Jorrand

Sept. 10. -This morning wee passed the Tropick of Cancer with a fresh and fair gale, the ships performed the usual ceremony of ducking several of the Ships Crew, who had not passed before; they were hoisted to the main yard arm, and let down 3 several times with a soss into the sea out over head and ears, their legs being tyed somewhat closs, which was pretty good sport. (Rose, "Journal", p. 192) 1 We weighed and were under the sign of Cancer by the 10th of the month, at which time the usual ceremony of ducking from the Yards arm was performed on those that could not pay their tropick bottle. ("A Journal Kept from Scotland by One of the Company", 28 September 1698, p. 72)

The men who wrote these journals were embarking on an exciting venture, leaving from Scotland to found the first-ever Scottish colony in Central America, right under the nose of the Spaniards, in a place they believed the best one for world commerce. This they were doing in spite of the joint opposition of the East India Company, which feared a challenge to its monopoly, the London Parliament, which shared their anxieties, and King William III, who was afraid of a quarrel with Spain and concentrated on European wars. They were sailing in ships which they had had to buy in Europe for want of a suitable shipyard in Scotland itself. They also hoped for the help of the Darien Indians, and especially their non-existent emperor. And they flew the Company of Scotland's flag: a sun rising over a wide expanse of sea-blue calm water. The tone in their journals was optimistic, even cheerful. Much was expected from the Darien Venture.

The Darien Scheme appears as Scotland's greatest attempt at colonial expansion in its own right, as a still relatively independent country and nation. This project, one of several by the Company of Scotland Trading to Africa and the Indies, raised the highest of patriotic and economic hopes, only to end in cataclysmic failure. At the instigation of its promoter, William Paterson, this venture was intended to link the Atlantic and the Pacific spaces and concentrated on the Isthmus of Darien, seen as the key to these wide oceanic expanses. William Paterson's conception of what the colony of Caledonia should have been will be looked into, and we shall also, mostly but not exclusively, draw upon journals by the first expedition's eye-witnesses, such as those by Hugh Rose or Captain Pennicook, as well as another, anonymous diarist. Captain Pennicook, sometimes spelt Pennycook or Pennicuik, was captain of the Saint Andrew and commodore of the Company's fleet, and Rose was the secretary of the Council of the Colony. Their journals sometimes replicate each other, being sometimes identical, and may show interpolations, especially in the passages about the Darien Indians-though they are different enough at times to be judged of joint interest-for instance, Pennicook mentions desertions, unlike Rose.

After a brief outline of the context, we shall try and assess what the Company of Scotland's project meant, or could have meant, in geostrategic terms of maritime space and world trade. We shall then study the close interrelation of sea and land in the colonial project of Caledonia, in both its positive and negative manifestations, ranging from the choice of a good harbour as a future base and the establishment of the seedling colony on a peninsula, in close proximity to the sea, to the in-between ("entre-deux"), whether it be made manifest through mangroves, rainy weather, or even amphibious attacks. The ambivalence of the sea, symbolically linked to both life and death, is a wellknown theme, but it seems particularly relevant in the case of the Darien Scheme, and the last part of this paper shall therefore study the conflicting presentations of the sea that appear, often simultaneously or nearly so, in contemporary accounts of the Darien experience.

A study in context: a strong tradition of emigration, and a late start at colonization Portugal and Spain had launched themselves into colonial expansion in and then across the Atlantic space towards the Americas by the end of the 15th century, soon followed by France, England and the Low Countries in what Chaunu has termed an un-partitioning of the worlds ("décloisonnement des mondes"; translation ours). This led Sir William Alexander to declare, in 1624, in his Encouragement to Colonies in relation to the Nova Scotia attempt: "my countriemen would never adventure in such an Enterprise, unlesse it were as there was a New France, a New Spaine, and a New England, that they might likewise have a New Scotland" (1624, p. 32). Scotland was handicapped by several factors: its comparative small size, its poverty, and its minority status in the Union of Crowns (an "anomalous position" analysed by Devine, 2003, p. 3).

A long tradition of maritime connection and immigration, whether scholarly, mercantile, or soldierly, with Northern Europe especially, had been well-established from the Middle Ages. This included the Hanseatic cities, Poland, Denmark, Scandinavia, and France, not forgetting the Ulster of the 17th century (Devine, 2003, pp. 8-17, and pp. 20-4). Thriving

From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...

Études écossaises, 19 | 2017

Scottish communities existed all over Northern Europe (Devine, 2003, pp. 9-12). Scotsmen also played a part in colonizing Northern America, sometimes in the English colonies established there, despite a strong preference for the more ancient European connections (Landsman, 1999, pp. 463, 465). However, there had also been several attempts at Scottish settlements: Nova Scotia, sacrificed by London on the altar of good diplomatic relationships with France; Cape Breton, attacked by the French; East New Jersey, before its absorption in the royal colony of New Jersey; and Stuart's Town in Carolina, attacked by the Spaniards in 1686 [START_REF] Insh | Scottish Colonial Schemes[END_REF]Devine, 2003, pp. 38-9). The Americas were a place to emigrate for those freely seeking a better life, but also a place to transport political opponents during the Commonwealth (Armitage, 1997, p. 46).

Traditional European markets were shrinking in the second half of the 17th century, for example France, following Colbert's protectionist measures, and these deteriorating trading conditions could not counterbalance agricultural problems at home: poor lands and cold, wet climate accounted for poor crops in some decades and made not starvation but dearth loom large (Devine, 2003, p. 15). By the 1680s and 1690s, neither the existing sea connections nor the land seemed to provide satisfactory opportunities; the time had come to try and go further, and embark on transatlantic ventures. It seemed vital to resort once more to the sea, and exploit the country's peninsular situation, relocating the centres of decision-making, and looking to an Atlantic seaboard. Several English Navigation Acts had repeatedly stood in the way of Scottish maritime development (Devine, 2003, pp. 31-2), and as a direct result, pre-Union Scotland did not enjoy free trade with either England or its colonies, and neither did it enjoy independence at sea. By the 1690s, Scotland had but few ships at its disposal and even fewer maritime opportunities. But it also had this deeply ingrained tradition of emigration, and an Atlantic seaboard. Included within the sovereign powers of the Company of Scotland was, revealingly, the power "to Equipp, Fit, Set out, Fraught and Navigat their own, or hired Ships, in such manner as they shall think fit […]" in the "Act of Parliament Constituting the Company of Scotland, Trading to Africa and the Indies" of 26 June 1695 (Hart, 1929, p. 185).

The said ships, on which the hopes of a nation rested, were not Scottish-built, but bought elsewhere, from Amsterdam or Hamburg. In other words, commerce gave rise to the Company's first fleet, and not the reverse. After loading the cargoes and victualling the ships, they set sail from Leith in a climate of high expectation, exhilaration and enthusiasm.

The Scottish Indies and the "Door of the Seas": an ambitious rewriting of late 17th century-Geostrategy in Darien There were in fact not one but two Darien Schemes. The first, joint-stock project funded by English and Scottish capital planned to follow the model prescribed in "Trading to Africa and the Indies". It contained no direct mention of the Americas, though the Indies could be understood as the West Indies as well as the East Indies. Its intended scope was as ambitious as that of other commercial companies, and it aimed more specifically towards Africa and the East Indies, and consequently the Indianoceanic space-which triggered the fears and reaction of the East India Company, as "Some Considerations upon

From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...

Études écossaises, 19 | 2017

the Late Act of the Parliament of Scotland" or "Some Remedies to Prevent the Mischiefs from the Late Act of Parliament Made in Scotland, in Relation to the East-India Trade" tend to show, as well as the reaction of the English Parliament forbidding the jointventure. Revealingly, no mention of America is made in these pamphlets, and they are still classified in the Indian and African Studies Section of the British Library of London, category "East India Tracts" (former India Office Library).

In contrast, the second Darien Scheme was an exclusively Scottish project, solely funded by Scottish capital. Investors thronged at Mrs Purdie's coffee-house to enter their names in the subscription book, wishing as much to defend national pride as to invest in a promisingly prosperous venture. William Paterson, a Scottish merchant who had lived in the Caribbean and London-he was one of the founders of the Bank of England-played a crucial part in reorienting the new Darien Scheme towards Central America. He well knew from personal experience of the opportunities the West Indies had to offer; not only in relation to the Atlantic space, but also the "South Sea", the Pacific. Yet Paterson had never set foot on the isthmus itself, which may account, at least partly, for his genuinely undaunted but purely theoretical enthusiasm about it. The scope of this second, independent project was, in itself, enormous, since it aimed at no less than bringing together the Atlantic and Pacific together, clearly breaking the Spanish monopoly in the matter and challenging their long-established rights to the area, by taking possession for Scotland of "these doors of what the Spaniards used to proudly call their king's summer chambers, or, more properly speaking, the keys of the Indies and doors of the world" (Paterson, 1701, p. 147). It was more ambitious and novel than other chartered companies' projects, as it meant substitute itself, peacefully or otherwise, for the main and most ancient colonial power in this part of the world.

The isthmus was, for Spain, the crucial point of the Carrera de Indias, not an easy pathway due to climate, vegetation and terrain, but the narrowest connecting "neck of land" as it is often described, between South and North Sea. It was the shortest route, though always difficult and even perilous to cross. Yet, the alternative was enough to frighten even the most hardened sailors: the passage round Cape Horn, or through the risky Straits of Magellan. Across this trans-isthmian trail, from Panama towards the Atlantic seaboard, trains of mules would carry overland the riches from Philippines and the Far East, together with silver mined from the Potosi, in today's Bolivia. Here, they would assemble at Portobello-Nombre de Dios having been twice attacked by Drake, and then abandoned by the Spaniards-and sail from there or Cartagena, in modern-day Colombia (Tavernier, 1970, p. 102;Ward, 1993, pp. 29-66, 188-9). Paterson thought very highly of Darien and took in, in one wide rhetorical sweep, the part played by sea routes and the world interconnectedness which Scotland could now play its part in: "[T]hese doors of the seas and the keys of the universe would of course be capable of enabling their possessors to give laws to both oceans, and to become the arbitrators of the commercial world." (Paterson, 1701, p. 159) His objective was commerce, as, for him, "the isthmus of America [was] not only the natural centre of the west, but easily to be put in a state of being that of at least twothirds of the trade and treasure of both Indies" (ibid., p. 127). Accordingly, he wished to create a world entrepot, in keeping with a venture focused upon trade rather than military conquest with its concomitant atrocities, which he did not condone and wished to avoid: in his own words, "without being liable to the fatigues, expenses, and dangers, or of contracting such guilt and blood, as Alexander and Caesar" (ibid., p. 159). The

From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat... Études écossaises, 19 | 2017 merchant or tradesman was the new hero of the age, far from the bloodthirsty conquerors of the past, far from conquistadores themselves, implicitly. This outpost of future trade, a "Scottish Amsterdam of the Indies" [START_REF] Callagher | L'Amsterdam écossaise des Indes[END_REF]: "Amsterdam écossaise des Indes"; translation ours), was to welcome strangers and foreigners provided they intended to settle, thus making the settlement stronger and richer, and religious toleration was to be its hallmark ("a general naturalization, liberty of conscience, and a permission trade", Paterson, 1701, p. 154). It was an enterprise set apart from the leyenda negra, therefore, with its massacres of Indians and the cruel Inquisition, not to mention the territorial monopoly jealously enforced by Spain, which regarded trespassers into their Darien and South Sea provinces, especially Protestant, English-speaking ones, as downright pirates (Botella-Ordinas, 2010, p. 146;Schurz, 1922, p. 185).

However, it would seem a stumbling-block was already present in Paterson's noble, somewhat idealistic ambitions. To settle a colony in the teeth of colonial Spain, especially in a place of such geostrategic significance, meant that it needed the capacity to resist attack. Here appears the sharpest of contrasts between theory, "an international emporium without the costs of territorial empire" (Devine, 2003, p. 46), and practice. In order to endure long enough to trade, the colony of Caledonia would have to defend itself, and the recruitment of colonists accordingly took on a strong military imperative, although the official language resorted to double meaning, and demurely mentioned "Overseers" and "Planters" when "officers" and "soldiers" were actually meant (Prebble, 1968, p. 99). Of course, it may be argued, Ancient Rome itself had its peasant soldiers, but the conquered remembered the soldiers in them rather than the peasants, and the viceroys of the Spanish New World did not underestimate the threat. The terms "overseers" and "planters" apparently indicate landsmen rather than seamen, which means that the Councillors had survival in mind. However, the primary objective, once the settlement was effective, remained trade, and therefore sea ventures.

Places in-between sea and land

The meeting of land and sea might in fortunate circumstances provide the colonists with natural harbours, though it could just as easily present them with salt shallows and hazards such as mangroves. While the former are, clearly enough, in favour of human activities, the latter can be seen as obstacles to them.

In Modern, 16th to 18th-century Europe, a trading or colonizing venture started from one land, and sought to reach another one, thanks to the sea as connector, and bond: the supremacy of the maritime element in exotic ventures cannot be in doubt. In most cases, traders or colonists from Europe aimed for another continent, whether America, Africa or Asia, where they would establish themselves close to the sea, either as permanent settlers (Plymouth) or occupants in trading-posts (the Moluccas), on or near the coast, or up a river (the Hooghly), in the hinterland. Unsurprisingly, the first areas to have been colonized by Europeans in the Americas were the Caribbean Isles, the first commodious landfalls they had met on their way. 2 A harbour, whether already existing or to be created, as Caledonia was, brings into contact both sea and land and allows commerce and interaction between colonizing nation, colonists, and colonized, hence its central importance. Consequently, the search for the best possible harbour was the Scottish settlers' starting point, bearing in mind not only the necessary connection to be kept and developed with the outside world-the From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...

Études écossaises, 19 | 2017

whole point of their enterprise, after all-but also the defensive matters, too. It had to be spacious enough to accommodate a flourishing traffic of boats and ships, quite safe and sheltered from both natural elements and enemies, easy to access and easy to defend. They needed solid ground rather than marshland, unsilted waterways with fresh water in the vicinity, and not brackish water. In other terms, one had to be assured of land before venturing at sea.

The site of the future, but short-lived, Caledonia Harbour, seemed to win general approval. It was judged "most excellent" by the anonymous writer of "A Journal" (4 November 1698, p. 74), which is echoed by Rose: "[wee went] in our boats to sound a bay about 4 miles to the eastward of Golden Island, and found it a most excellent harbour", and, perhaps counting his chickens before they were hatched, he calculated it would easily shelter "1000 of the best ships" (3 November 1698, pp. 197-8). The natural protection it afforded was good, Pennicook thought: "here you ly Landlockt every way, that noe wind can possibly hurt you" (Pennicook, 3 November 1698, p. 82, echoed in Rose, 3 November 1698, p. 198). And the anonymous diarist saw in all this the hand of God, writing in a dutifully thankful tone: "We are certainly much bound to Providence in this affair; for as we were searching for the place we were directed to, we found this", and he carries on, "and though the Privateers had been so often at Golden Island, and though English, Dutch, and French had been all over this Coast, from Portobelo to Cartagena, yet never one of them made the discovery; even the Spaniards themselves never knew of this place" ("A Journal", 4 November 1698, p. 76). Apart from sounding over-optimistic, this is tantamount to denying Balboa knowledge of the area of the very town he founded, Acla.

Another example of place where this "entre-deux" is manifest and offers shelter to humans would be Captain Ambrosio's dwelling, protected as it is from a surprise attack: "It stands upon the banks of this river with about 10 or a dozen lesser houses about it. Their houses are on the sea hand inaccessible in a manner, being so advantageously situate that no stranger can come at them that way by reason of the numerous unseen shoalds, small rocks, and banks." (Rose, 21 November 1698, p. 207) This seems not unlike modern-day Kuna dwellings, as a majority of Kuna communities-the descendants of the Indians Wafer and the Scottish settlers met in Darien-now live on small coralline islands away from fevers while going every day on the mainland to till their fields (Severin, 2002, pp. 216-7;McKendrick, 2016, p. 99).

At first, a kind of balance appeared between the sea (dynamic) and the land (static), and the would-be colonists laboured at both: "The people ashoare are imployed in making of huts, clearing way, & c. and those on board in ordering their holds, overhauling their rigging, blocksails, & c." (Rose, 11 November 1698, p. 205) The settlement had to be made first, but could only hope to endure thanks to communications with the outside world, through the coming of news, supplies, and at a later stage the development of commerce. However, a fundamental imbalance was soon to be observed, with the liquid element gradually taking over, preventing human activities or at least slowing them down considerably, and making men and women sick from mosquito-induced fevers.

Mangroves, where sea and land meet in a tangled vegetation of entwined aerial roots, were hostile to European activities, and the time had not yet come when they would be considered as shrines of biodiversity to be protected. Marshlands were justly feared, as they brought fevers, although the part played by mosquitoes as vectors was not yet known. Mr Rose described an unsuitable place in the following terms: "On the main and all the bay round full of mangrow and swampy ground, which is very unwholesome." (Rose, 1 Nov. 1698, p. 196) 21 Wafer, trudging across Darien with an open wound in his knee, found the conditions truly appalling in the rainy season, and left an apocalyptic account of his experience in which water and earth seem no longer to exist as distinct entities: " 22 Another potentially lethal admixture of sea and land is to be noticed in the Isthmus's long-favoured military strategy, that of amphibious operations. Given the absence of roads or even permanent paths wide and clear enough for Europeans to circulate unhampered, and the difficulty of travelling overland combined with the necessity of attacking settlements on land, troops had to be shipped to a landing-point and disembarked close to the place they wanted to attack. This was exactly what privateers and pirates had done against the Spanish cities of the Isthmus: Henry Morgan organized a whole fleet before attacking Panama (Exquemelin, 1684, Part III, p. 3). Ironically, this was also the strategy the Spaniards resorted to in order to drive the Scots from Caledonia: their land forces-Campmaster Luis Carrisoli's men, or the garrison at Toubacanti-were insufficient, and expeditionary reinforcements, from Colonial America and from Spain itself, under the command of Don Juan Diaz de Pimienta and Don Pedro Fernandez de Navarrete respectively, were shipped to the nearby Golden Island, then disembarked, to drive the Darien colonists away. When the Spanish troops arrived in the Spring of 1699, the settlement was already abandoned; but, on the second occasion, in April 1700, New Edinburgh capitulated, and so ended the "Scottish dream of empire" [START_REF] Prebble | The Darien Disaster[END_REF]Storrs, 1999).

The ambivalences of the sea: life and death, dearth and plenty

Eaux en mouvement, la mer symbolise un état transitoire entre les possibles encore informels et les réalités formelles, une situation d'ambivalence, qui est celle de l'incertitude, du doute, de l'indécision et qui peut se conclure bien ou mal. De là vient que la mer est à la fois l'image de la vie et celle de la mort. (Chevalier & Gheerbrant, 1982, p. 623) From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...

Études écossaises, 19 | 2017

The sea is a traditional mythological and literary theme, and, as a metaphor of human experience, the whole drama of human experience from beginning to end, it seems to sum up and illustrate the contradictions of the Darien project. Apart from the divide and difference between seamen and landsmen in the Council of the Colony (Prebble, 1968, p. 129, for example), the two Darien expeditions seem to have been characterised by high levels of hope-the first accounts sent home were almost lyrical in their praise-while the failure brought despair to not only the colonists but to the nation itself.

The sea was not only what made the colonization possible: it also meant the arrival of potential Indian allies, supplies, news, and reinforcements from the mother-country. As such, it concentrated the hopes in the seedling establishment's survival. The former's repeated visits occurred soon enough-Rose and Pennicook report them in similar terms. The latter, in contrast, had to be long awaited: even to send Edinburgh news of the safe arrival meant finding a ship bound for the Caribbean or, even better, Europe. In this respect, the shipwreck of the French vessel which had agreed to carry dispatches, just before Christmas 1698, was a sore blow.

Kuna chiefs appear to have been well-pleased with their new neighbours, and Captains Ambrosio, Pedro and Diego took turns to visit the settlers. The colonists saw them as potential allies, inspired in this by Wafer's account and the Kunas' own declarations of friendship for privateering and pirate captains (Rose, 2 November 1698, p. 197). However, as Gallup-Diaz has emphasised, the diplomacy at stake here was not one-sided, whatever the settlers might have thought; the chiefs had for long been negotiating alliances, with or against each other, and with or more frequently against the Spaniards, or with buccaneers and freebooters whom they sometimes helped to cross the isthmus. Kunas, Pocorosas, Urabaes, Spanish-supporting Chocos, all had agendas of their own, whereas the new arrivals failed to understand the advanced state and complex nature of "rainforest diplomacy" (Gallup-Diaz, 2005, chapter 4).

Supplies were greatly needed, but few arrived. Soon after leaving Leith, Paterson was appalled at the lack of some and the poor quality of others ("Report by William Paterson", 19 December 1699, Burton, 1849, p. 179); in Madeira, the Darien fleet bought wine, but their autonomy in the matter of food was from the start less good than it should have been (Prebble, 1968, pp. 118, 144). Far from trading in spices or silk, sugar or tobacco, the settlers needed basic provisions. On 23 December 1698, a delighted Mr Rose noted that a sloop brought "flower, beefe, & c. from Jamaica", but it was rather small, he noted (23 December 1698, p. 215), and, the readers may observe, quite alone.

Rather engagingly, echoing Wafer's remark about a land of plenty, the secretary of the Council reported good catches, in keeping with the motif of the nurturing sea: "Sometimes most excellent fish taken here, as also Tortoises (but very few yet, not having time nor nets fit for them,) some of them above 2, others above 300 weight: they are the best of meat. One of them will serve 100 men of reasonable appetites." (Rose,p. 210,9 December 1698) A Short Account from, and Description of the Isthmus of Darien, Where the Scots Collony are Settled described the many resources of the place, drawing heavily from Wafer's account: vegetation, both useful and exotic, land animals, with a strong emphasis on edible ones, birds, unknown, beautiful, and delicious, and fish, of course, such as "Paracoods" (barracudas), the "Sea-Cow" (the manatee) and the best way to catch it, for it, too, was exquisite, and turtles (1699, pp. 5-9). Yet, reading Rose's journal, the last impression is not quite so favourable, as the catching of fish and turtles already seems in

From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...

Études écossaises, 19 | 2017

jeopardy due to lack of time. This may be understood as a reference to the harsh and slow process of land clearing and building, and, implicitly perhaps, to the high number of sick men too, making the progress harder and slower. The lack of adequate fishing tools (Rose, 9 December 1698, p. 210) added to the difficulties of their adaptation to their new environment, which might have been remedied had they had time enough to observe Indian ways and knowledge. As for the expected reinforcements, the first Darien settlers never saw them: when they arrived, they found a deserted colony, and what should have been a strengthening of the settlement proved to be, in fact, a second attempt and a second expedition.

Knowing that not only allies and friends, but also spies, rivals, or enemies could come from the sea, Rose explains their defensive effort: "The Council have ordered their ships in a line of battle in the mouth of the harbour." (14 December 1698, p. 213) The need to have a clear view and anticipate an attack is evident when he adds: "There is a look out made from which ships or vessels within 10 leagues can be descried." (Ibid.) Point Look-Out was indicated on contemporary maps of Darien.

Spies and rivals were feared, and the arrival of the English Captain Richard Long on board his Rupert Prize, officially commissioned to sail the area in search of sunken treasures from wrecked ships, was interpreted as a potential threat from London, the English capital interfering in Scottish affairs. Long was invited to dine several times and reciprocated the invitation (Rose, 13-23 November 1698, pp. 205-8;Pennicook, 13-26 November 1698, pp. 88-90) and the atmosphere remained courteous throughout his visit, but as soon as he had surreptitiously left, the alarm was sounded: "The Counsell mett, where Captn Long's sudden departure being consider'd, it was resolv'd the Pink should be sent home to Scotland with all possible speed" (Pennicook, 26 November 1698, p. 90), and the anonymous diarist tartly writes that Capt. Long came in eight days after, and I believe we were a great eyesore to him, tho he said nothing.

[…] Hearing by the Natives that we were here, he came in with his Long-boat, as he said to see us, but I believe it was only to know the certainty of what he feared was too true. ("A Journal", 4 November 1698, p. 77)

As they well knew, Captain Long was not there as a free-lance treasure-seeker, but had been sent on some official mission: "He commanded the Rupert Prize, a small English Man of War, fitted out by the King, upon what Design we know not, but he pretends it was to search for a Silver Wrack […]." (Ibid.)

Other rivals at this time took the modest shape of a group of French privateers at the San Blas Islands, who also benefitted from good relationships with local Indians and their chief, Captain Corbet ("Captain Long's Letter", 1699, Burton, 1849, p. 81). They were not necessarily hostile, but uncomfortably close. And, centuries after the Auld Alliance, France was known to mistrust the Scottish endeavour, fearing at first that they would aim for their own colonial possessions instead of Darien, thus verging from centuries of mutual support, friendliness and goodwill, following perhaps the well-acknowledged principle "no peace beyond the line". Furthermore, Scotland was now included in the Union of Crowns, which made it part and parcel of William III's kingdom, Louis XIV's Protestant enemy.

The enemies the New Edinburgh settlers feared were, of course, the Spaniards, and they waited for sometimes contradictory news about their movements from the visiting Indian chiefs. The Spaniards could not admit of the Scottish intrusion in the geographical centre of their empire-"the fulcrum of [their] imperial economy" (Watt, 2007, p. 5)-, which

From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...

Études écossaises, 19 | 2017

would have split the viceroyalties of New Spain and Peru into two separate entities, and created a regrettable precedent, possibly paving the way for other Protestant settlers-" Luteranos" and heretics in the eyes of Carlos II's subjects. Protestants or subjects of William III meant only one thing to colonial Spain, as it had endured repeated attacks from Sir Francis Drake to Sir Henry Morgan to Captain Bartholomew Sharp: piratesalthough some of them had actually been privateers-, that is, arch-enemies to be eradicated as soon as possible. The Council of Caledonia took every step to reassure them on this point ("Letter by the Council of Caledonia", Burton, 1849, p. 91), 3 but fair words were not judged sufficient. The possibility of Spanish reaction had been underestimated, as was their enduring strength (Storrs, 1999, pp. 6-7, 27), by those who saw colonial Spain as an empire on the wane, inhabited by slothful, cowardly, and degenerate individuals, and Spain itself as the very image of Carlos II, its perpetually ailing monarch whose death was expected any minute and whose succession agitated Europe. But the counterattack had to be reckoned with, as Caledonians themselves judged when they tried to take protective measures such as the digging of a ditch and the construction of Fort Saint Andrew, overlooking the sea. "[I]f Darien was, ultimately, a disaster for Scotland-a minor, peripheral European power-it was a triumph for a Spanish Monarchy which remained a Great Power and was by no means the desperate figure of legend on the eve of the advent of the Bourbons and the War of the Spanish Succession." (Storrs, 1999, p. 27) The Company's Directors judged, somewhat harshly, that their fellow countrymen had under-utilised their ships in the first expedition, and thus not taken enough advantage of the sea element:

And whereas we understand that the ships sent upon the first expedition for settling of the said Colony were after their arrival there all along kept wholly idle and useless, and not employed as they ought to have been in making reprisals upon the persons and goods of the Spaniards after that they broke out in acts of hostility against the said Colony; you are therefore hereby ordered to take care not to fall in the like errour and neglect […]. ("Instructions to Mr Daniel Mackay, Captain William Vetch, Captain Alexander Campbell of Fonab, and Mr Alexander Hamilton", 1699, Insh, 1924, p. 189) But, of course, it was easier said than done, and the second expedition did not, in the end, fare any better than the first. Paterson saw ships as a lifeline, an indispensible link with the outside world, and found that the Darien ships were far from meeting such requirements: "When we arrived first, we were, as it was, in a Prisone for want of sloops, briganteens, or other good, stiff, windwardly vessels." ("Report by William Paterson", 19 December 1699, Burton, 1849, p. 181) Of these ships, the Saint Andrew managed with extreme difficulty to make its way to Port-Royal, Jamaica, after narrowly escaping wreckage off the coast of Cartagena, the Dolphin was taken by the Spaniards, the Endeavour sank, and the Unicorn had to be abandoned after reaching the Hudson River estuary; the Caledonia made it back to Scotland, after staying in New York, but only just made it there from Darien (Insh, 2004, p. 119;Prebble, 1968, pp. 305, 178, 202, and 215). As for the second expedition, the Rising Sun and the Hope of Bo'ness were wrecked, the Duke of Hamilton, sunk by a storm, and the Olive Branch, a supply ship which went with the Hopeful Binning, burnt accidentally. Despite the liquid element, wooden ships' greatest enemy was fire (Prebble, 1968, pp. 306, 307, and 237). The aptly-named Speedy Return reached Scotland, but was to disappear on another, Eastern expedition with her consort the Content (Prebble, 1968, p. 312). To describe this as a hecatomb does not seem far-fetched, and this is also meant in human terms: "In our Burton, 1849, p. 196).

Given the bedraggled survivors' sorry condition, and despite the royal proclamation forbidding help to the Darien colonists, the numerous New Yorkers of Scottish descent, as well as John Nanfan, then acting as Deputy Governor for Lord Bellomont, tried to help them, at least to some extent (Insh, 2004, pp. 119-20). Some, however, never took to the sea again and chose to stay and prosper in the English colonies of America instead of returning to Scotland. For them, the sea experience was definitely over, and they had escaped a watery grave. 4

36 Whilst the means to defend Darien had been chronically insufficient before the Scottish attempt (Schurz, 1922, p. 185;Elliot, 2007, p. 59), they were increased after 1700 (Storrs, 1999). Paterson appears to have stuck to his views of Darien when he wrote his "Proposal" in 1701, and in his 1704 edition of A New Description, Wafer still urged an English colonization of the area: the geostrategic charms of the place still had not faded, and were thought enticing enough to justify these publications.

NOTES

1. The late 17th-century spelling has been left unaltered, random capitalization included.

2.

One notable exception to this supremacy of the sea element would seem to be Russia, then an essentially continental, Eurasian power in the making, where colonies came into direct geographical contact with the colonial power, quite unlike the overseas territories claimed by Western European nations. Yet, even then, the sea was not absent from the ambitions of Peter the Great, who founded the national navy, or of Catherine II, during whose reign the search for an ice-free coastline in winter accounted for the Russian territorial extension towards the Crimea.

3. "Wee doe therefore, by these, signifie to you that wee are the subjects of the King of Great Brittain, by virtue of whose power and authority granted to us, with advice and consent of his Parliament of Scotland, wee have settled here, for the encouraging, advancing, and carying of trade and commerce." At this point, in Spring 1699, the Council was trying to have the men of the Dolphin freed from Spanish gaols, where they were detained under an accusation of piracy.

4. Among those who chose to stay was Reverend Alexander Stobo, an ancestor of President Theodore Roosevelt.

ABSTRACTS

The Darien Scheme (1696-1700) appears as Scotland's greatest attempt at colonial expansion in its own right, before the 1707 Union of Parliaments. Due to its peninsular situation and overall poverty, the nation had a long tradition of emigration, and by the end of the 17th century, it also wished to take part in the trans-Atlantic venture. Far from being perceived as an obstacle, the sea

From " the

 the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat... Études écossaises, 19 | 2017 had a crucial part to play, both as a means of reaching the Americas and as a way of furthering overseas trade. But enemies too could come from the sea, and for many of the survivors of Spanish retaliation and tropical fevers, the Caribbean and the Atlantic were not only a way of escape, but also a watery grave, in an ambivalent reversal of what had first appeared as a dazzling opportunity.Le projet du Darien (1696-1700) apparaît comme la tentative coloniale majeure de l'Écosse en tant que nation indépendante, avant l'Union des Parlements de 1707. Du fait de sa situation géographique et économique, elle avait une longue tradition d'émigration, et souhaita également, à la fin du XVII e siècle, participer à l'aventure transatlantique. Loin d'être perçue comme un obstacle, la mer avait donc au contraire un rôle crucial à jouer, permettant à la fois le passage vers les Amériques et la promotion du commerce extérieur. Mais de la mer pouvait aussi venir l'ennemi, et pour nombre de survivants de la riposte espagnole et des fièvres tropicales, la mer ne fut pas seulement une échappatoire, mais aussi un tombeau liquide, en un renversement non dénué d'ambivalence.

  But not long after Sun-set, it fell a Raining, as if Heaven and Earth would meet; which Storm was accompanied with horrid Claps of Thunder, and such flashes of Lightning, of a Sulpherous smell, that we were almost stifled in the open Air."(Wafer, 1704, p. 13; emphasis ours) The New Edinburgh colonists did not arrive in the rainiest months, unlike Wafer, yet references to rain and poor weather conditions are recurrent in the testimonies of Caledonia's early days(Rose, 12-15 November 1698, pp. 205-6; 19 November, p. 206; 1 and 2 December, p. 210): "24. Much wind and rain. 25. Wind and rain as above. 27. Very much rain and wind. 28. These 24 houres ther has fallen a prodigious quantity of rain. 29. Much rain with fresh gales." (24-29 November, p. 208) Rain, thunder, and downpours again, in an endless litany: in what Kricher terms the "neo-tropical" climate (1997), rivers overflow their banks, swamps encroach, and, as in Wafer's narrative, earth and water appear to merge. This other "in-between" was of course prejudicial to human activities, both in preventing regular work ("which hinders the work much", Rose, 2 December 1698, p. 209) and in augmenting the number of the sick. Those still lodging onboard the ships suffered less from the fevers. It seems William Paterson and the Company's Directors had overlooked this part of Wafer's experience. After all, the Spaniards themselves had never actually settled the area around New Edinburgh, at least not for long.

  From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...Études écossaises, 19 | 2017voyage from the Collony to New York we lost neare 150 of about 250 persons putt on boord, most of them for want of looking after and meanes to recover them"-amounting to 60%, therefore ("Report by William Paterson", 19 December 1699,

  37 The Company of Scotland had lost much, and so had the Scottish nation; but it courageously returned to its first, Eastern interests and managed to man a few more ships. It did not prosper there, either. Prosperity took much longer to achieve, and happened only after the Union (see McGilvary, 2011), which enabled Scotland to gain access to English colonies on equal terms, although this was far from being immediate (Clive & Bailyn, 1954, p. 201). Journal Kept from Scotland by One of the Company Who Sailed on Board the Endeavour Pink; With a Short Account of Darien, in Papers Relating to the Ships and Voyages of the Company of Scotland Trading to Africa and the Indies", in G. P. Insh (ed.), 1924, Papers Relating to the Ships and Voyages of the Company of Scotland Trading to Africa and the Indies, Edinburgh, The University Press / T. & A. Constable, pp. 69-77. From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat... Some Considerations upon the Late Act of the Parliament of Scotland, for Constituting an India Company. In a Letter to a Friend", London, 1695. "Some Remedies to Prevent the Mischiefs from the Late Act of Parliament Made in Scotland, in Relation to the East-India Trade", London [?], 1695. La route de l'or et de l'argent. Séville, Panama, Manille. XV e -XVII e siècles", in Les Grandes routes maritimes, Paris, Laffont. WAFER Lionel, 1704, A New Voyage and Description of the Isthmus of America [1699], London, James Knapton. WARD Christopher, 1993, Imperial Panama: Commerce and Conflict in Isthmian America, 1500-1800, Albuquerque, University of New Mexico Press. WATT Douglas, 2007, The Price of Scotland. Darien, Union and the Wealth of Nations, Edinburgh, Luath

	STORRS Christopher, 1999, "Disaster at Darien (1698-1700)? The Persistence of Spanish Imperial
	Power on the Eve of the Demise of the Spanish Habsburgs", European History Quarterly, vol. 29,
	no. 1, pp. 5-38.
	TAVERNIER Bruno, 1970, "Press Limited.
	A Short Account from, and Description of the Isthmus of Darien, Where the Scots Collony are Settled,
	Edinburgh, John Vallange, 1699.
	ALEXANDER Sir William, 1624, An Encouragement to Colonies, London, W. Stansby.
	ARMITAGE David, 1997, "Making the Empire British: Scotland in the Atlantic World, 1542-1707",
	Past & Present, no. 55, pp. 34-63.
	BAILYN Bernard & CLIVE George, 1954, "England's Cultural Provinces: Scotland and America", The
	William and Mary Quarterly, Scotland and America, vol. 11, no. 2, pp. 200-13.
	BOTELLA-ORDINAS Eva, 2010, "Debating Empires, Inventing Empires: British Territorial Claims
	Études écossaises, 19 | 2017

BIBLIOGRAPHY

"A Against the Spaniards in America,

1670-1714", Journal of Early Modern Cultural Studies, vol. 10, no. 1 "

From "the Doors of the Seas" to a Watery Debacle: The Sea, Scottish Colonizat...Études écossaises, 19 | 2017


Jonathan Weber
email: j.weber@unistra.fr

Sébastien Lefèvre
email: sebastien.lefevre@univ-ubs.fr

Pierre Gançarski
email: gancarski@unistra.fr

Spatio-Temporal Quasi-Flat Zones for Morphological Video Segmentation

Keywords: Quasi-flat zones, video segmentation, segmentation personalization

In order to face the various needs of users, user-driven segmentation methods are expected to provide more relevant results than fully automatic approaches. Within Mathematical Morphology, several user-driven approaches have been proposed, mostly relying on the watershed transform. Nevertheless, Soille (IEEE TPAMI, 2008) has recently suggested another solution by gathering puzzle pieces computed as Quasi-Flat Zones (QFZ) of an image. In this paper, we study more deeply this user-driven segmentation scheme in the context of video data. Thus we also introduce the concept of Spatio-Temporal QFZ and propose several methods for extracting such zones from a video sequence.

Introduction

Following the increase of textual and then image data in personal databases and Web repositories, we are currently facing the same evolution with video data. Many video processing schemes or related use cases require a prior segmentation to get the objects-of-interest to be further processed. However, the segmentation of a given video is often not unique and depends on user needs. Thus it is necessary to rely on a segmentation method able to provide a personalized result.

Video segmentation methods designed within the framework of Mathematical Morphology may be clustered in two categories: automatic methods [START_REF] Agnus | Segmentation spatio-temporelle de squences d'images par des oprateurs de morphologie mathmatique[END_REF][START_REF] Chien | Predictive watershed: a fast watershed algorithm for video segmentation[END_REF] which do not require any user interaction (apart from parameter settings) and interactive methods [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF] (but also video extension of [START_REF] Rivest | Marker-controlled segmentation: an application to electrical borehole imaging[END_REF]) where the user has to draw some markers over objects-of-interest in order to drive the segmentation process. Results returned by automatic methods are then not adapted to user needs and often face the problem of over-segmentation. Interactive methods are more time-consuming but provide a personalized result. Another solution to solve the problem of segmentation personalization is to provide an over-segmentation which will then be reduced by the user through region merging in order him to obtain the expected segmentation. Image over-segmentation may be achieved using flat zones [START_REF] Serra | Connected operators and pyramids[END_REF] but it then results in an extreme over-segmentation. Quasi-Flat Zones have been introduced in order to reduce this over-segmentation while keeping interesting properties of flat zones. QFZ are based on a less restrictive criteria to build the regions, thus leading to larger regions, while keeping a low computational cost and region borders able to represent most of the frontiers between the objects-of-interest. Besides, Soille [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] notices that QFZ are not really segmentation methods but rather methods which split an image into puzzle pieces. Identifying the QFZ is then a preprocessing step in an image segmentation process based on merging of puzzle pieces. This merging may be driven by the user, thus solving the problem of segmentation personalization. Let us observe however that there is no definition of QFZ for video sequences yet.

In this article, we recall the QFZ definition in the framework of logical predicate connectivity introduced by Soille [START_REF] Soille | On genuine connectivity relations based on logical predicates[END_REF][START_REF] Soille | Constrained connectivity and transition regions[END_REF]. We then extend this definition to video sequences, and study how it can be applied to video segmentation personalization. Finally we give some conclusions and indicate future research directions.

QFZ-based image segmentation

Logical Predicate Connectivity

QFZ rely on the concept of α-connected path. A path is said α-connected if all paths between any pair of its pixels are Lipschitz-continuous, thus leading to the following definition.

A path P, considering a neighbourhood N , and composed of n pixels (p 0 , p 1 , ..., p n-1 ) is an α-connected path (α-P) if and only if:

∀i ∈ [0, n -2], p i ∈ N (p i+1 ) and |f (p i ) -f (p i+1 )| ≤ α (1)
This notion let us define the most simple QFZ, i.e., α-connected zones [9] which will be noted here α-CC. An α-CC is defined as:

α-CC(p) = {p} ∪ {Q | ∀q ∈ Q, α-P(p, q) = ∅} (2)
The α-CC of a pixel p is then the set of pixels to which it is linked through an α-connected path. Let us observe that flat zones are a particular case of α-CC with α = 0. The α-CC have the following hierarchical property which will be useful later in this paper:

∀α ≤ α, α -CC(p) ⊆ α-CC(p) (3)
Segmenting an image into α-CC results in an under-segmentation. If α is set too high, it will lead to a chaining effect, which may result on a single QFZ for the whole image (this depends of the image under consideration and the α value of course). In order to counter this problem, new QFZ definitions based on α-CC have been elaborated. In a goal of unification of existing works, Soille and Grazzini [START_REF] Soille | On genuine connectivity relations based on logical predicates[END_REF][START_REF] Soille | Constrained connectivity and transition regions[END_REF] have proposed a theoretical framework called logical predicate connectivity. We recall that a logical predicate P return true when the parameter satisfies the predicate, false otherwise. They define a new kind of QFZ (noted (P 1 , ..., P n )-CC here) which lead to QFZ satisfying all the n logical predicates.

Various predicates may be involved, for instance: global range predicate which checks if the difference between minimal and maximal values of pixels within a QFZ is below a threshold (ω); connectivity index which is the ratio between the number of 2-pixels α-connected paths and the number of 2-pixels paths within a QFZ. This predicate is verified if the index is higher than a threshold (β). The (P 1 , ..., P n )-CC thus consists in seeking, for each pixel p, the largest α-CC satisfying all the predicates. Thanks to the property 3, we know that if α < α then α -CC(p) is less or equal to α-CC(p). When predicates are not verified for a given value of α, we can use this property to decide to decrement α in order to check if the predicates are verified for a lower value and to loop until finding the maximal value of α for which all the predicates are verified:

(P 1 , ..., P n )-CC(p) = α -CC(p) ∀k ∈ {1, ..., n} P k (α -CC(p)) = true ∀α" ≤ α , ∀q ∈ α -CC(p), P k (α"-CC(q)) = true (4)
This theoretical framework is adapted to methods ensuring the unicity property. Indeed we are seeking the largest α -CC verifying all logical predicates. It is thus not possible to consider methods which do not provide a unique QFZ segmentation. More than only a framework to unify existing definitions, the (P 1 , ..., P n )-CC also allows to elaborate new QFZ definitions. Three predicates are currently used within the QFZ: local range (α), global range (ω) and connectivity index (β). In the framework introduced by Soille and Grazzini, it is possible to include predicates related to other features (perimeter, area, etc.) but also to more complex descriptors (texture, gradient, etc.) as long as these predicates fulfill the condition defined in Eq. ( 4). Some clues to using QFZ in multivariate images have been given by Soille [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF]: α is assumed to be a vector with the same value in all components. Then, α may be easily ordered through a total ordering (decrementing α = (3, 3, 3) gives α = (2, 2, 2)). Global range predicate is processed similarly, and is true only if it is verified marginally for all bands.

In the sequel of this article, we will denote by QFZ the colour QFZ built using (P 1 , ..., P n )-CC with only the global range predicate and a given α.

Filtering

QFZ suffer from the transition region problem. Transition regions are regions between two objects where a staircase phenomenon occurs on edge pixel values. This is due to the image discretization process and the subsequent value interpolation. This artefact leads to an over-segmentation near to the edges which will then be made of tiny QFZ. Some solutions have been proposed to solve this problem. Soille and Grazzini [START_REF] Soille | Constrained connectivity and transition regions[END_REF] define transition regions as QFZ containing only transition pixels. Every pixel which is not a local extremum is considered as a transition pixel. All QFZ corresponding to transition regions are removed, and remaining QFZ are enlarged using a region growing algorithm [START_REF] Adams | Seeded region growing[END_REF]. After the removal of these regions, the amount of flat zones is reduced significantly.

The solution proposed by Soille and Grazzini does not depend of any parameter and relies on a precise definition of a transition region. But from our experiments, we have observed that many regions of a few pixels remains after applying their strategy. These regions do not fit with the definition of transition regions, but are still sources of a high over-segmentation. Thus, a more efficient and robust filtering method is still lacking.

Other authors have proposed QFZ filtering methods using a QFZ minimal area thresholding step. Angulo and Serra [START_REF] Angulo | Color segmentation by ordered mergings[END_REF] suggest to merge QFZ characterized by an area lower than a given threshold with the most similar neighbouring QFZ. With this method, no more transition region is present in the final segmentation. Zanoguera [START_REF] Tous | Segmentation interactive d'images fixes et de squences vido base sur des hierarchies de partitions[END_REF] removes QFZ with an area below a given threshould (thus including transition regions) before applying a Watershed transform to enlarge remaining QFZ in areas where small QFZ have been removed. Soille [START_REF] Soille | Constrained connectivity for the processing of very-high-resolution satellite images[END_REF] proposes a filtering method based on an iterative increase of the minimal area, followed at each iteration by both a region growing algorithm relying on QFZ with area greater or equal to minimal area and an image simplification algorithm. The simplified image will then be segmented into QFZ at the next iteration. This process is repeated until filtered QFZ become stable. Following some ideas introduced in these methods, we have also design a filtering method. It relies on the Seeded Region Growing (SRG) algorithm [START_REF] Adams | Seeded region growing[END_REF] but we apply it on the QFZ rather than on the pixels. To do so, we consider a minimal area threshold similarly to existing approaches. We set all QFZ with an area greater or equal to this threshold as seeds for the SRG algorithm which is applied on the region adjacency graph. We thus obtain a much more reduced over-segmentation compared to the result obtained without filtering. The highest the area threshold is, the more reduced the over-segmentation is. But in the same time, it is much more probable to obtain an under-segmentation of some objects-of-interest. Our region growing being applied on QFZ rather than on pixels, the proposed method requires a low computational cost.

Extension to video data

Limits of a 3D straight extension

The most direct extension of QFZ to video sequences is to consider a video sequence as a 3-D spatio-temporal cube. We can reuse the existing definitions, thus changing only the neighbourhood considered (spatio-temporal rather than purely spatial).

Computing the (P 1 , ..., P n )-CC in 3D, we obtain a higher spatial oversegmentation than in 2D. On the carphone sample (Fig. 2.a) for α = ω = 20 (we will use these values in the sequel), we obtain on average 4441CC per frame in 2D vs. 6779CC per frame in 3D (55040CC on the full sample). Indeed, by analysing the video sequences in 3D, the considered neighborhood contains more pixels and therefore an α-CC contains more pixels (see chaining effect discussed above). This naturally increases the risk of violating one of the considered predicates. Thus, the largest α-CC satisfying all predicates is often produced with a small α value. This leads to tiny QFZ of only a few pixels, while such QFZ are unusable for video segmentation.

Sequential processing of spatial and temporal dimensions

As 3D approach is not suitable for video processing, we consider rather the 2D+t approach. In this approach, we successively (and no more jointly) consider the spatial and temporal dimensions, as illustrated in Fig. 1. We discuss here first the spatial to temporal (2D + t) approach and then the temporal to spatial (t + 2D) approach. With the spatial to temporal approach, QFZ are first built on each frame independently. Then they are considered as nodes of a graph which are valued (here we consider the QFZ mean value). Edges are then introduced to temporally connect QFZ from successive frames and overlapping spatial coordinates. Each edge is valued by the difference between related node values. The new QFZ are the largest connected components of nodes whose connecting edges have a value less or equal to α and which do not violate any predicate. We observe that (P 1 , ..., P n )-CC produced significantly fewer regions in 2D + t (23926CC), thus reducing the extreme segmentation we noted in 3D (55040CC). This can be explained by the distinct computing of the two dimensions (spatial and temporal). In 2D + t the first processing (spatial only) produces spatially wider QFZ reducing the spatial over-segmentation. But, then the second processing (temporal) introduces temporal over-segmentation. This is due to the predicate constraints: the regions being spatially more extensive, they are less homogeneous and there-fore may have significantly different means which will violate a predicate during the temporal computing of (P 1 , ..., P n )-CC.

With the temporal to spatial approach, QFZ are first built for each spatial coordinate independently, according to the temporal dimension. After this temporal processing, we therefore obtained an extreme spatial over-segmentation since, for each frame, each pixel belongs to a different QFZ. Similarly to the 2D + t case, we consider QFZ as nodes of a graph and apply the same process as previously, but considering here the spatial dimension instead of the temporal one. We note that (P 1 , ..., P n )-CC produces fewer regions (16, 830CC) than the 2D + t approach due to a smaller temporal over-segmentation.

Let us observe that the (P 1 , ..., P n )-CC highlights an interesting phenomenon. Due to their different order when processing spatial and temporal dimensions, the approaches 2D + t and t + 2D induce different over-segmentations: a reduced spatial but high temporal one for the former, and a higher spatial but reduced temporal one for the latter. Nevertheless, both approaches provide better results than the 3D approach. Selecting between 2D + t and t + 2D depends on the video under consideration. It may seem better to use the first approach with short videos of high-resolution, and to use the second for long videos of lowerresolution. Moreover, let us note that the spatial and the temporal processing are both relying on (P 1 , ..., P n )-CC, which guarantees the uniqueness of the result. Thus they also ensure this fundamental property.

Filtering

The filtering methods presented in section 2.2 can be extended to video data. As far as our method based on a minimum area threshold is concerned, adaptation depends on the chosen approach. For the 3D approach, we could trivially extend the method and no longer consider a minimum area but a minimum volume. However, if considering a minimum volume would be effective in the context of truly three-dimensional images, it is not suitable for video that are spatiotemporal and not purely spatial. Indeed, assuming a minimum volume, a QFZ having few pixels in a spatial area, but on many frames, would be kept despite the fact it is probably not an object but a part of an object. Thus, we use a threshold of minimum mean area, the mean area being computed as follows:

A mean = # QFZ pixels # frames where the QFZ is present [START_REF] Serra | Connected operators and pyramids[END_REF] For the 2D + t approach, we may also use this definition, but we rather use the filtering after the 2D processing. So we apply the filtering area not at the end of the process, but rather after the first stage (i.e., prior to temporal processing). Doing so allows us to have fewer QFZ to be processed during the temporal step.

We could do the same for the t + 2D approach by filtering QFZ produced by the temporal processing. But setting a threshold on the minimum number of frames in which a pixel must belong to the same QFZ would have been tricky and very probably without any sense. Therefore we filter the QFZ in the same manner as for the 3D approach, once the QFZ building is achieved.

Similarly to the image filtering, the oversegmentation is here strongly reduced. Indeed, setting the threshold of minimum mean area to 10 pixels, we get 980CC for 2D + t and 319CC for t + 2D. In addition, we get few or no under-segmentation, which makes obtained QFZ relevant for segmentation.

Filtering by minimum area threshold is very effective in reducing QFZ oversegmentation in video sequences. We obtain a very substantial over-segmentation reduction while maintaining the QFZ quality. By combining the definitions of video QFZ and the filtering area, we obtain an effective method of video presegmentation. This pre-segmentation can be used by QFZ merging methods to obtain user-personnalized segmentation.

User-driven video segmentation

Encountered in image segmentation, over-segmentation is even more present when dealing with video segmentation. For instance, when processing the sample carphone (Fig. 2.a) with the Predictive Watershed [START_REF] Chien | Predictive watershed: a fast watershed algorithm for video segmentation[END_REF], we obtained about 2000 regions. This problem happens obviously also with segmentation by quasi-flat zones: segmenting the same sequence by (P 1 , ..., P n )-CC t+2D, with α = ω = 20 and a minimal area of 10 also provides an over-segmentation (319CC). Moreover, the resulting segmentation is not personnalized. This drawback may be solved by relying on user interaction. Such an interaction aims the user to both customize the segmentation and reduce over-segmentation. User-driven segmentation is a well-known principle in Mathematical Morphology, and has been recently used by the watershed from propagated markers method [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF]. In the context of QFZ, as indicated by Soille [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF], it may correspond to the assembling of puzzle pieces.

We suggest a new principle for user-interactivity in video segmentation by defining a QFZ segmentation guided by markers. First, a base QFZ segmentation is produced. Then, the user draws markers on the video data. Thus, he customizes the segmentation by indicating his objects-of-interest. QFZ beneath the markers are considered as the seeds of a Seeded Region Growing algorithm [START_REF] Adams | Seeded region growing[END_REF]. The region growing will then merge the different QFZ according to their distance in terms of color, which can be related to an α parameter in the QFZ context. Since the user only see original video (and not QFZ), it is possible that several markers are found over the same QFZ. In this case, we consider that there are two possibilities: either the marker has been ill-drawed or the QFZ is ill-segmented. Here, we assume that the user has well-drawn the marker and that the QFZ has to be corrected. To do so, this QFZ is segmented using Seeded Region Growing with the user's markers as seeds. Thus, ill-segmented QFZ is corrected: it both improves the accuracy of the initial over-segmentation and solve the problem of having multiple markers over the same QFZ.

In order to evaluate the relevance of our proposal, we conducted some experiments on the carphone sequence. We compared the (P 1 , ..., P n )-CC 2D + t and t + 2D methods to the Marker-Based Watershed known as the standard interactive segmentation method of Mathematical Morphology. We also compared interactive QFZ to the Seeded Region Growing involved in our method, in order to show how our method benefits from such algorithm and what it offers compared to a direct processing of Seeded Region Growing. In this perspective, we used three different settings of markers (Fig. 2). The results of these experiments are presented in Tab. 1. We denote here by precision the average spatial distance (in pixels) between the frontiers of the resulting segmentation and those of the reference segmentation. We used two sets of parameters (α, ω) for (P 1 , ..., P n )-CC to show that our method is robust to parameter settings (which have besides not been optimized). Let us observe that, whatever the markers used, our method always provides better results than the other two approaches. However, like the other two interactive methods, the interactive QFZ segmentation is very sensitive to the markers given by the user. We also compared our method to a more recent method, the Watershed from Propagated Markers [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF], for which we used the binding of markers and the region-based motion propagation. As the objective here was to compare our method to a recent interactive approach in similar conditions (here the time required for the user), we did not allow the marker correction by the user and marked only the first frame. The results are given in Tab. 2 and show that marker-based (P 1 , ..., P n )-CC in these conditions is more accurate than the Watershed from Propagated Markers.

Conclusion

In this paper, we proposed both an extension of QFZ to video sequences and an interactive method for assembling these QFZ in order to build a user-personnalized segmentation. The separate processing of spatial and temporal dimensions improves the segmentation compared to a straight three-dimensional processing of video data. The proposed method for assembling QFZ according to the user's needs is intuitive and provides good results compared to other existing methods.

Our future work will focus on improving the markers. Indeed, the video is currently only marked before the processing. However, it seems relevant to be able to correct markers (like what is done in [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF]) in order to iteratively improve the segmentation. Indeed the eventual correction of some QFZ will improve the over-segmentation at each iteration. Moreover, most of the computational cost of our approach is linked to the initial QFZ segmentation: the marker-based QFZ merging is very efficient because it is performed on the QFZ adjacency graph, unlike other interactive segmentation methods that restart all the segmentation process when modifying markers (cf. Marker-based Watershed and Seeded Region Growing). We also consider to apply video QFZ on other data spaces, such as optical flow values instead of pixel values. Moreover, we plan to improve the QFZ merging process by using other features than only the mean color.

Finally, as our method is based on a graph reduction process, we would like to design a machine learning scheme to understand how to perform segmentation from this reduction process. The idea is here to perform first a learning of some videos marked by the user to then enable the system to segment unmarked, but simply over-segmented with QFZ, video sequences.

Fig. 1 .

 1 Fig. 1. Video Quasi-Flat Zones production by separated processing of spatial and temporal dimensions.

Fig. 2 .

 2 Fig. 2. Markers on sequence carphone (a) frame 7 of extract from carphone sequence, b) few points on frame 7, c) heavy markers on frame 7, def) heavy markers on frame 3,7 and 10)

Table 1 .

 1 Comparison of frontier precision with different markers (a) a few points on the median frame, b) heavy markers one the median frame, c) heavy markers on three frames)

	Method	Parameters Precision
		(a) (b) (c)
	(P1, ..., Pn)-CC 2D + t	α = ω = 20 0.94 1.10 0.81
	(P1, ..., Pn)-CC 2D + t	α = ω = 30 1.00 0.77 0.72
	(P1, ..., Pn)-CC t + 2D	α = ω = 20 2.92 0.92 1.45
	(P1, ..., Pn)-CC t + 2D	α = ω = 30 6.25 0.34 0.84
	Marker-Based Watershed	7.77 2.72 1.76
	Seeded Region Growing	8.73 3.23 2.62

Table 2 .

 2 Comparison of frontier precision between (P1, ..., Pn)-CC and watershed from propagated markers

	Method	Parameters Precision
	(P1, ..., Pn)-CC 2D + t	α = ω = 20	0.81
	(P1, ..., Pn)-CC 2D + t	α = ω = 30	0.73
	(P1, ..., Pn)-CC t + 2D	α = ω = 20
	(P1, ..., Pn)-CC t + 2D	α = ω = 30	0.71
	Watershed From Propagated Markers		2.02


Jonathan Weber
email: j.weber@unistra.fr

Sébastien Lefèvre
email: sebastien.lefevre@univ-ubs.fr

Pierre Ganc

Interactive Video Segmentation based on Quasi-Flat Zones

Keywords: Video analysis, Object segmentation, Interactive process, Quasi-Flat Zones, Morphological approach

Video data is continuously increasing in personal databases and Web repositories. To exploit such data, a prior segmentation is often needed in order to get the objects-of-interest to be further processed. However, the segmentation of a given video is often not unique and indeed depends on user needs. Personalized segmentation may be achieved using interactive methods but only if their computational cost stays reasonable to enable user interactivity.

We address here the problem of interactive video segmentation and introduce a 2-step segmentation scheme: 1) offline processing to automatically extract quasi-flat zones from video data, and 2) online processing to interactively gather quasi-flat zones and build objects-of-interest. Our approach is able to deal with multiple objects, robust to errors introduced by the automatic segmentation step, and does not require to perform again the whole segmentation process each time the user provides some feedback.

I. INTRODUCTION

Following the increase of textual and then image data in personal databases and Web repositories, we are currently facing the same evolution with video data. Many video processing schemes or related use cases require a prior segmentation in order to get the objects-of-interest to be further processed, e.g. video object mining [START_REF] Weber | Video object mining: Issues and perspectives[END_REF]. However, the segmentation of a given video is often not unique and depends on user needs. While video segmentation is still an open and ill-defined problem, personalized or user-based segmentation may be achieved using for instance interactive methods. However, such methods can only ensure user interactivity if their computational cost stays reasonable, since the user will not accept to wait too long between each interaction.

In this paper, we address the problem of interactive video segmentation and introduce a new segmentation scheme, which is based on two steps: 1) offline processing to extract quasi-flat zones from video data, and 2) online processing to interactively gather quasi-flat zones and build objects-ofinterest. This paper is organized as follows: we first recall some recent interactive video segmentation methods in order to underline our contribution. We then deal with a recent morphological segmentation tool, called segmentation into Quasi-Flat Zones (QFZ), and provide its definitions for both the well-established image case and the more recently addressed video case [START_REF]Spatio-temporal quasi-flat zones for morphological video segmentation[END_REF]. The next sections are dedicated to our interactive segmentation method based on QFZ and its evaluation and comparison against existing approaches. Finally, we conclude and present some perspectives.

II. INTERACTIVE VIDEO SEGMENTATION

Interactive video segmentation means that a user is involved to guide the segmentation process. It can be easily achieved by allowing the user to change segmentation parameter settings and to see the subsequent results, but this kind of user interactivity is far from being intuitive. There are mainly two intuitive schemes for interactive video segmentation: either the user provides a visual input (i.e., she draws markers) to guide the segmentation process, or she is offered a way to correct segmentation results built from an automatic process.

Price et al. [START_REF] Price | Livecut: Learning-based interactive video segmentation by evaluation of multiple propagated cues[END_REF] propose a correction method based on automatic video segmentation obtained through graph-cut and different features computed from tiny regions returned by a watershed segmentation used as a preprocessing step. The segmentation is computed frame by frame. The user can correct the result of each frame, and its feedback is also propagated to the next frame following a feature weighting process within the graph-cut scheme. Flores and Lotufo [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF] design a method based on the marker-based watershed involving both marker drawing and correction. The user draws markers on the first frame to guide the watershed process. The result of the watershed segmentation is then used to define new markers to be used in the next frame according to inter-frame motion. The user can correct the markers in any frame: it will result in a new segmentation of the current frame and an updating of the segmentation results of the following frames. Bai and Sapiro [START_REF] Bai | A geodesic framework for fast interactive image and video segmentation and matting[END_REF] combine markers and geodesic distance to segment a video as a 3D image. Each pixel is assigned to the closest marker according to its geodesic distance to markers, and a weighted gradient is used to compute the markers. Zhi and Ji [START_REF] Zhi | Interactive video object segmentation: fast seeded region merging approach[END_REF] combine watershed segmentation and region merging. While the former is used as a preprocessing step, the latter relies on a seeded region growing algorithm and is applied on the region adjacency graph of the initial watershed segmentation. The result can be corrected by assigning manually each incorrect region to foreground or background.

While these methods provide good results, they suffer from some limitations: [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF], [START_REF] Bai | A geodesic framework for fast interactive image and video segmentation and matting[END_REF], [START_REF] Zhi | Interactive video object segmentation: fast seeded region merging approach[END_REF] are only able to deal with a single main object vs. its background; [START_REF] Price | Livecut: Learning-based interactive video segmentation by evaluation of multiple propagated cues[END_REF], [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF], [START_REF] Zhi | Interactive video object segmentation: fast seeded region merging approach[END_REF] are framebased approaches, and the user is then expected to check each frame of the video sequence; [START_REF] Price | Livecut: Learning-based interactive video segmentation by evaluation of multiple propagated cues[END_REF], [START_REF] Zhi | Interactive video object segmentation: fast seeded region merging approach[END_REF] rely on an automatic preprocessing step to provide an initial segmentation result which cannot be further corrected; finally, user correction in [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF], [START_REF] Bai | A geodesic framework for fast interactive image and video segmentation and matting[END_REF] requires to perform again the whole segmentation process.

In order to overcome these limitations and to propose an efficient interactive video segmentation method, we suggest to first build a spatio-temporal oversegmentation result, and then merge the different regions according to user markers. Segmentation correction is achieved by editing the markers and performing again only the merging step and not the whole segmentation process. If irrelevant regions are found within the initial oversegmentation result, the segmentation process is locally recomputed according to user feedback. The initial oversegmentation result is made of Quasi-Flat Zones (QFZ) which have interesting frontiers and may be considered as puzzle pieces [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] to be further gathered into objects. We present this tool in the next section.

III. QUASI-FLAT ZONES

A. Still Image QFZ Flat zones [START_REF] Serra | Connected operators and pyramids[END_REF] have been studied within the field of Mathematical Morphology and are seen as elements with interesting properties. Indeed, a flat zone is defined as a connected set of pixels having the same value. Since object frontiers in digital images are mostly located between pixels of different values, object frontiers are expected to be included in frontiers between flat zones (apart if the image resolution is insufficient, which will not be considered here). However, flat-zones are often only a few pixels wide so the resulting partition is an extreme oversegmentation and is hardly exploitable. Less constrained definitions have thus been proposed, leading for instance to the Quasi-Flat Zones and more precisely the α-CC (see [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] for a survey on QFZ).

The α-CC of a pixel p is defined as the connected set of pixels which can be reached through (at least) one path verifying the following condition: the difference between values of successive pixels within the path is less or equal to a given parameter α. Let us observe that flat zones are a particular case of α-CC with α = 0. But, contrary to flat zones, segmenting an image into α-CC with α > 0 may result in an undersegmentation phenomenon. If α is set too high, it will lead to a so-called chaining effect, which may even result on a single QFZ for the whole image. In order to counter this problem, several new QFZ definitions based on α-CC have been elaborated (see [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF] for more details). These definitions have been subsequently unified by Soille and Grazzini [START_REF] Soille | On genuine connectivity relations based on logical predicates[END_REF], [START_REF] Soille | Constrained connectivity and transition regions[END_REF], who propose a theoretical framework called logical predicate connectivity.

In this new framework, a QFZ (noted (P 1 , . . . , P n )-CC here) is expected to satisfy all the n logical predicates P i . We will denote by P i (S) the fact that a predicate P i is valid over a set S. Various predicates may be involved, such as the global range predicate which is true if and only if the difference between minimal and maximal pixel values within a QFZ is less or equal to a given threshold ω. The (P 1 , . . . , P n )-CC thus consists in finding, for each pixel p, the largest α-CC which satisfies all the predicates. Moreover, since the following property holds:

∀α ≤ α, α -CC(p) ⊆ α-CC(p) (1)
an iterative computation scheme may be involved. Indeed, when predicates are not verified for a given value of α, we only need to decrement α and check once again if the predicates are verified. This loop is repeated until finding the maximal value of α for which all the predicates are verified:

(P 1 , . . . , P n )-CC(p) = α -CC(p) | ∀k ∈ {1, . . . , n}, ∀α" ≤ α , ∀q ∈ α -CC(p), P k (α -CC(p)) and P k (α -CC(q)) (2)
Some clues to define QFZ in multivariate images have also been given by Soille [START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF], where α is assumed to be a vector with the same value in all components. Thus α may be easily ordered through a total ordering (e.g., decrementing α = (3, 3, 3) gives α = (2, 2, 2)). Global range predicate is processed similarly, and is true only if it is verified marginally for all bands.

QFZ are well defined for still images. Their extension to video is not straightforward and implies some new segmentation schemes. We have already addressed this problem [START_REF]Spatio-temporal quasi-flat zones for morphological video segmentation[END_REF] and recall this previous work in the next section.

B. Spatio-temporal QFZ

Extending the concept of QFZ to video data may be achieved by several ways. Probably the easiest one consists in a 3D straight extension, where a spatio-temporal neighbourhood is considered instead of a spatial one. However, spatial and temporal dimensions are intrinsically different and results provided by such a trivial 3D approach may not be relevant. We rather consider here a 2D + t method which successively (and no more jointly) deal with the spatial and temporal dimensions. First, we compute the QFZ considering only the spatial dimension, i.e. on a frame by frame basis. QFZ are then considered as elementary units, represented within a graph structure where each QFZ or node is valued (e.g., using the QFZ mean value). The temporal dimension is then studied to connect QFZ from successive frames which have overlapping spatial coordinates. The graph structure is updated by adding edges for each connection between QFZ. Edges are also valued by the distance (e.g., euclidean distance) between their associated nodes. In this 2D + t segmentation scheme, the QFZ are defined within the graph as the largest connected components of nodes whose connecting edges have a value less or equal to α and which do not violate any predicate. This video extension of QFZ is presented in figure 1. Let us observe that we can apply this process by inverting spatial and temporal dimensions, i.e., starting by identifying QFZ using a temporal neighbourhood only, and then linking nodes by edges considering a spatial neighbourhood. Experimental results performed by the authors have demonstrated a superiority of 2D + t and t + 2D approaches over the 3D approach. Thus these oversegmentation schemes will be used further in this paper.

While our interactive segmentation scheme relies on an oversegmentation result provided by the computation of the QFZ, the oversegmentation effect should not be too important to make the subsequent merging step computationally efficient and to ensure user interactivity. Thus, we also apply a filtering process to reduce oversegmentation induced by the QFZ approach. In still images, QFZ filtering often consists in keeping only QFZ having a minimal spatial area. We extend this principle to video data by considering the average spatial area of the QFZ, computed as the ratio between the spatiotemporal volume and the length of the QFZ (i.e., the ratio between the number of pixels within the QFZ and the number of successive frames where the QFZ appears). All QFZ with a average spatial area below the filtering threshold are merged with the neighbouring QFZ having the most similar mean color. Let us note that this criterion was shown to provide better results than a straight extension of 2D area to 3D volume.

IV. INTERACTIVE SEGMENTATION SCHEME

As indicated in the first sections, we aim in this paper to introduce a new interactive video segmentation method able to overcome drawbacks encountered by existing works (see Sec. II). User interactivity is only possible if the segmentation process requires a relatively low computational cost. Nevertheless, building a meaningful video segmentation needs to process a huge data volume (i.e., duration × framerate × image width × image height pixels). Thus we propose here a two-step segmentation approach, where the first step is performed offline and does not need user intervention, while the second step is online and interactive. This approach is presented in figure 2.

A. Offline Part

The offline part consists in building a first segmentation into QFZ from the whole set of pixels contained in the video sequence. QFZ are computed using the scheme presented in Sec. III. More precisely, we consider the (P 1 , . . . , P n )-CC definition with the 2D + t extension to video data. QFZ are then represented through a spatio-temporal region adjacency graph (RAG). These operations are the most computationally intensive steps of our method, and are thus performed offline (i.e., before user interactivity).

B. Online Part

The online part relies on the user to refine interactively the initial QFZ oversegmentation and build a user-based or personalized segmentation. First, the user is asked to edit and provide markers to the segmentation refinement process. To do so, she is expected to draw scribbles over both objects-ofinterest and background. Each scribble is assigned to a label, and scribbles related to the same label are considered as a single marker even if they are not spatiotemporally connected. By this way, scribbles may be drawn in different frames.

Contrary to existing works, the initial segmentation (resulting here from the offline step) may be corrected by the user if needed. This occurs when a given QFZ is overlayed by multiple user markers. In this case, either the QFZ or the user scribbles are irrelevant. We assume here that the user does not make any mistake while drawing scribbles, and that the illsegmented QFZ needs to be segmented again according to user scribbles. This is achieved using a marker-based watershed based on user markers. The spatio-temporal RAG is then updated according to this new segmentation. While this userbased correction of initial segmentation increases the oversegmentation effect and requires an additional computational cost, it also improves the quality of QFZ and related frontiers from a user point-of-view. The initial or corrected RAG is then interactively segmented using an algorithm inspired from the Seeded Region Growing (SRG) approach. Each interaction is a sequence of the following operations:

1) Nodes representing QFZ overlayed by user markers are labelled as merged: they are considered as seeds in the SRG paradigm. All the other RAG nodes are labelled as unmerged.

2) Edges between merged and unmerged nodes are valued by the distance between node attributes (e.g., mean color). 3) Edge with the least value is removed and corresponding merged and unmerged nodes are merged. The modified RAG is then corrected by updating edge values of the new merged node. This merging process is iterated until all unmerged nodes have been incorporated into merged ones. 4) Nodes related to the same marker are merged in order to produce a node per user marker (instead of a node per QFZ overlayed by a user marker). 5) The graph segmentation is then mapped back to the video and displayed to the user. If she is not satisfied by the result, she may correct the existing markers, add new markers or remove existing ones. The RAG is reinitialized and the iterative process is repeated until user validation.

V. RESULTS AND DISCUSSION

To illustrate the successive steps of our method, we consider the sequence carphone (176 × 144 pixels on 381 frames) and provided a sample corresponding to the frame 186 in Fig. 3. We consider here the 2D + t video extension and following parameters: α = ω = 20, mean area = 10. For the sake of clarity, still images are given but they are indeed samples from a spatio-temporal segmentation process. The initial QFZ segmentation (b) results in 35 560 spatio-temporal regions (while the original video (a) contains 9 656 064 pixels). The user is expected to draw a marker for each connected region-of-interest, see (c) for an example of markers. The result given in (d) has been obtained by marking only a few frames within the video. Indeed, users are advised to mark only the median frame in a first time before computing a first segmentation result. Then this result may be corrected by adding/modifying/removing markers on any frame. The final segmentation is here composed of three objects-of-interest: a man, the inside of the car and the outside.

Table I illustrates the computation time required to segment the sequence carphone by the 2D + t approach with different (α, ω) parameters. The offline time measures QFZ computation and RAG creation steps, while the online time measures one user interaction, i. step for the whole video sequence (a frame-related measure is also provided). Here the correction of the initial segmentation has not been considered since it only occurs when several markers overlay a single QFZ, which is quite rare in our case since the QFZ build an oversegmentation. Let us observe however that for high values of (α, ω), such a correction may occur more frequently. Nevertheless, in this case online computation time is lowered since the number of QFZ (and subsequently the graph size) is reduced. We also provide in this table a comparison with the watershed from propagated markers [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF] and with the standard marker-based watershed [START_REF] Rivest | Marker-controlled segmentation: an application to electrical borehole imaging[END_REF] extended to video data (considered here as a 3D volume). The comparison element is the online time which measures the efficiency of the interactive process (i.e., how long a user has to wait before being informed that she has to provide a new feedback to the segmentation process?). Our method performs far more better than these two methods thanks to its offline preprocessing step. Indeed, when other methods need tens of seconds for the online processing, our method needs less than a second. Though the marker-based QFZ needs more offline processing time than other methods (above two times the needs of [START_REF] Flores | Watershed from propagated markers: An interactive method to morphological object segmentation in image sequences[END_REF]), it is totally compensated by the online processing efficiency which is more important in an interactive context. Besides, we also need to evaluate the precision of the results produced by our method vs. those of other similar works. To do so, we compare our marker-based QFZ to marker-based watershed (MBWS) and seeded region growing (SRG). We choose these two methods because we use MBWS for illsegmented region refinement and we apply a kind of SRG on our spatio-temporal RAG video representation to obtain the personalized segmentation. The goal of this comparison is to show that our approach, which relies on these basic methods, gives better results than the straight application of them. To perform the precision evaluation, we use an extract of the sequence carphone of 80 frames for which we have a ground truth (let us notice that general-purpose spatio-temporal segmentation datasets and benchmarks are still missing). We evaluate the results using the mean value of Jaccard-Index which has been used in image segmentation evaluation [START_REF] Mcguinness | A comparative evaluation of interactive segmentation algorithms[END_REF]. Its values are in [0,1], 1 represents a perfect matching between segmentation and reference. We compute it independently for each class and average the result to obtain a global criterion.

The different results are obtained by markers set only on the median frame. Results are shown in table II and show that both MBQFZ video approaches gives better results than SRG. We can conclude that our method benefits from applying SRG on QFZ instead of relying on a direct application of the SRG algorithm on video pixels. Moreover, we can observe that our method is able to produce results better or close to those obtained with the marker-based watershed. Let us also note that these results are obtained by different combinations of parameters α,ω and mean area threshold, thus showing a relative robustness of our method to parameter settings. But selecting best parameters for this video segmentation task is still an open problem. While our interactive method is based on the principle of QFZ which is basically an homogeneous region extraction operator, we could expect some difficulties to segment highly textured objects. In practice, as it is illustrated by the segmentation of the outside of the car, our method is able to extract textured object without marking all the different segments of the textured area. This video also shows important motion from both the man and the outside of the car. Even with this motion, our method is able to extract the object marked by the user while not using motion information. This is possible because of the overlapping spatial definition of each object in successive frames. In the case of very fast objects (e.g., a soccer ball) with no spatial overlapping in successive frames, our method will need a motion compensation step to be able to correctly segment these types of object. From these few preliminary experiments, we have observed that our method provides promising results. In fact, it produces results close to marker-based watershed but requires less online computation time allowing better interaction. It now requires to be more deeply evaluated using a standard benchmark for interactive video segmentation, but we face the lack of such benchmark in the community. Since our current implementation is not optimized yet, some improvements may still be brought to offer a better efficiency (both within the offline part which is not so efficient, and within the online part to offer an even more interactive experience for the enduser). The few experiments presented in this section have been performed using a Java image processing framework developed in our laboratory and run on a i7-720QM processor (1.6 GHz) PC.

VI. CONCLUSION

In this paper, we have addressed the problem of interactive video segmentation. We have introduced a two-step approach where most of the computational effort is first made offline to produce an oversegmentation of the video sequence, while the online interactive step involves user feedback to efficiently return objects-of-interest. Offline segmentation is achieved by computing spatio-temporal quasi-flat zones from the video data and by building a spatio-temporal region adjacency graph. Online process is performed through a marker-based approach where the user draws scribbles over each object-of-interest. User feedback introduced during this online process may even result in a refinement of the initial oversegmentation result.

Future works will focus on the computational optimization of the method in order to demonstrate the relevance of the proposed interactive scheme with high-resolution data. Parallelization would help to take advantage of current multi-core processors. Besides, refinement process consisting in online QFZ segmentation needs also to be optimized. Furthermore, we plan to compute and integrate motion information within the QFZ graph in order to improve the merging process. Finally, we have to perform deeper evaluations and comparisons with the state-of-the-art approaches by considering several criteria such as the qualitative evaluation of the segmentation result (which needs a ground truth to be provided) and the user-time (or number of interactions) needed to achieve this result.

Fig. 1 .

 1 Fig. 1. Video Quasi-Flat Zones production by separated processing of spatial and temporal dimensions.

Fig. 2 .

 2 Fig. 2. Interactive marker-based QFZ framework.

Fig. 3 .

 3 Fig. 3. Different steps on frame 186: a) original frame, b) initial QFZ segmentation, c) scribbled markers, d) final segmentation.

TABLE I EFFICIENCY

 I EVALUATION AND COMPARISON OF INTERACTIVE VIDEO SEGMENTATION OF THE carphone SEQUENCE: COMPUTATION TIME (IN SECONDS) REQUIRED BY OUR MARKER-BASED QFZ (MBQFZ) ACCORDING TO DIFFERENT α AND ω SETTINGS AND TWO OTHER APPROACHES, WATERSHED FROM PROPAGATED MARKERS [4] (WSFPM), AND STANDARD MARKER-BASED WATERSHED (MBWS).

ACKNOWLEDGEMENTS

This work has been supported by Ready Business System, Entzheim, France and the French National Association for Research and Technology (ANRT). We particulary thank Christian Dhinaut from RBS for his support.