Natalia Grabar
email: natalia.grabar@univ-lille.fr

Clément Vincent Claveau
email: vincent.claveau@irisa.frclement.dalloux@irisa.fr

Clément Dalloux

CAS: French Corpus with Clinical Cases

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Textual corpora are extremely important for various NLP applications as they provide information necessary for creating, setting and testing these applications and the corresponding tools. Yet, in some areas, due to confidentiality or to ethical reasons, it is complicated and even impossible to access representative textual data. Medical and legal areas correspond to such examples: in the legal area, information on lawsuits and trials remain confidential, while in the medical area, the medical secret must be respected. In both situations, personal data cannot be used. For several years now, anonymization and de-identification methods and tools have been made available and provide competitive and reliable results [START_REF] Ruch | Medical document anonymization with a semantic lexicon[END_REF][START_REF] Sibanda | Role of local context in de-identification of ungrammatical, fragmented test[END_REF][START_REF] Uzuner | Evaluating the state-of-the-art in automatic de-identification[END_REF][START_REF] Grouin | Automatic de-identification of french clinical records: Comparison of rule-based and machine-learning approches[END_REF] reaching up to 90% precision and recall. But even de-identified data may be difficult to be freely accessed and used for the research purpose because there is a risk of re-identification of people, and more particularly of patients [START_REF] Meystre | Can physicians recognize their own patients in de-identified notes?[END_REF][START_REF] Grouin | Is it possible to recover personal health information from an automatically de-identified corpus of French EHRs?[END_REF] because several medical histories are unique, or because of other reasons. Hence, the application of the de-identification tools on personal data often does not permit to make these data freely available and usable within the research context.

Yet, there is a real need for the development of methods and tools for several applications suited for such restricted areas. For instance, in the medical area, it is important to have suitable tools for information retrieval and extraction, for the recruiting of patients for clinical trials, and for performing several other important tasks such as indexing, study of temporality, negation, etc. [START_REF] Pj Embi | Development of an electronic health record-based clinical trial alert system to enhance recruitment at the point of care[END_REF][START_REF] Hamon | Linguistic approach for identification of medication names and related information in clinical narratives[END_REF][START_REF] Uzuner | 2010 i2b2/va challenge on concepts, assertions, and relations in clinical text[END_REF][START_REF] Fletcher | Improving the recruitment activity of clinicians in randomised controlled trials: A systematic review[END_REF][START_REF] Sun | Evaluating temporal relations in clinical text: 2012 i2b2 challenge[END_REF][START_REF] Campillo-Gimenez | Improving the pre-screening of eligible patients in order to increase enrollment in cancer clinical trials[END_REF][START_REF] Kang | EliIE: An open-source information extraction system for clinical trial eligibility criteria[END_REF]. Another important issue is related to the reliability of tools and to the reproducibility of study results across similar data from different sources. The scientific research and clinical community are indeed increasingly coming under criticism for the lack of reproducibility in the biomedical area [START_REF] Chapman | Overcoming barriers to nlp for clinical text: the role of shared tasks and the need for additional creative solutions[END_REF][START_REF] Collins | Nih plans to enhance reproducibility[END_REF][START_REF] Bretonnel Cohen | Reproducibility in natural language processing: A case study of two r libraries for mining pubmed/medline[END_REF], as well as in other areas. First step towards the reproducibility of results is the availability of freely usable tools and corpora. In our work, we are mainly concerned by building freely available corpora from the medical area.

The purpose of our work is to introduce the CAS corpus with French medical data, containing clinical cases such as those published in scientific literature or used for the education and training of medical students. In what follows, we first present some works on creation of medical corpora stressing more particularly on corpora freely available for the research (Section 2). We then introduce and describe the CAS corpus in French (Section 3) and its current annotations. We conclude with some directions for the future work (Section 4).

Within the medical area, we can distinguish two main types of medical corpora: scientific and clinical. Scientific corpora are issued from scientific publications and reporting. Such corpora are becoming increasingly available for the research thanks to the recent and less recent initiatives dedicated to the open publication, such as those promoted by the NLM (National Library of Medicine) through the PUBMED portal1 and specifically dedicated to the biomedical area, and by the HAL2 and ISTEX3 initiatives, which provide generic portals for accessing scientific publications from various areas, including medicine. Such corpora describe the research works, their motivation, methods, results and issues on precise research questions. Other portals may also provide access to scientific literature following specific purposes, like indexing of reliable literature, such as proposed by HON [START_REF] Boyer | Health on the net automated database of health and medical information[END_REF], CIS-MEF (Darmoni et al., 1999), and other similar initiatives [START_REF] Risk | Review of internet information quality initiatives[END_REF]. Thanks to some research works, there are also scientific corpora which provide precise annotations and categorizations. These are mainly built for the purposes of challenges [START_REF] Kelly | Overview of the share/clef ehealth evaluation lab 2013[END_REF][START_REF] Goeuriot | Share/clef ehealth evaluation lab 2014, task 3: User-centred health information retrieval[END_REF] but may also be provided from works of researchers, such as POS-tag [START_REF] Tsuruoka | Developing a robust part-of-speech tagger for biomedical text[END_REF] and negation [START_REF] Szarvas | The BioScope corpus: annotation for negation, uncertainty and their scope in biomedical texts[END_REF] annotated corpora. As for clinical corpora, they are related to hospital and clinical events of patients. Such corpora typically describe medical history of patients and the medical care they are undergoing. It is complicated to obtain free access to this kind of medical data and, for this reason, there are very few clinical corpora freely available for the research. In our work, we are mainly interested in clinical corpora: the proposed literature review of the existing work is aimed at clinical corpora which are freely available for the research. We present here the main existing clinical corpora.

MIMIC (Medical Information Mart for Intensive Care) corpora, now in their version III, provide the largest available set of structured and unstructured clinical data in English. MIMIC III is a single-center database comprising information relating to patients admitted to critical care units at a large tertiary care hospital. These data include vi-A term female infant was born by vaginal delivery with normal birth weight, body length and APGAR score, from a 42-year-old mother with 13 previous pregnancies resulting in 3 miscarriages and 10 live births. The mother had no history of antenatal medical illness nor of exposure to smoking, drinking and other drugs. At birth, general and systemic examination revealed a round face, single palmar crease, left precordial systolic murmur. Two hours after birth a deterioration of the general condition occurred, with generalized hypotonia, cyanosis, poor feeding. The blood count revealed white blood cell count of 35.6*10 /µL with 20.6*10 /µL, 57.9% monocytes, normal neutrophils, lymphocytes and eosinophils count, hemoglobin levels of 19.1 g/dl and 27*10 /µL platelets count. The acute phase reactants were negative. Because she maintained the altered general condition and the platelets ranged between 17-18 *10 /µL, on the 8th day after birth she was referred to our unit for proper diagnosis and treatment. Physical examination showed a phenotype suggestive for Down syndrome, later confirmed by karyotyping (47, XX + 21). She was lethargic, tachypneic and a systolic heart murmur was observed. The liver was 2 cm below the right costal margin, along with a slight enlargement of the spleen. The laboratory tests on the first day of admission in our unit revealed a white blood count of 15.8*10 /µL, with an abnormal monocyte count (increased absolute and percentile count: 5.66*10 /µL, respectively 35.5%), normal absolute neutrophil count (5.53*10 /µL), a hemoglobin level of 15.9 g/dl and severe thrombocytopenia (15*10 /µL). The biochemical parameters including electrolytes, uric acid, creatinine, bilirubin, liver enzymes were normal. The serum lactate dehydrogenase was raised. The bacterial culture work-up and titers of antibodies against toxoplasmosis, cytomegalovirus, Epstein Barr virus, hepatitis C, HIV were negative. The peripheral blood smear presented atypical cells. The bone marrow aspiration showed hemodiluted aspirate with blast cells. Immunophenotyping revealed 23% blast cells, positive for megakaryocytic markers (CD42b, CD41, CD61), myeloid markers (CD33), progenitor cell markers (CD117, CD34) and T cell marker -CD7 positive. MPO and HLA/DR were negative. The mutational status of AM-LETO, PML-RARα, FLT3 and NPM1 fusion genes came out absent. The positive diagnosis was acute megakaryoblastic leukemia (AMKL). The echocardiography found a patent foramen ovale. The infant underwent chemotherapy according to the Down syndrome-specific AML chemotherapy protocol, consisting in four cycles of treatment: the first two cycles (induction phase) included combinations of cytarabine and liposomal daunorubicin and the last two cycles (consolidation phase): etoposide, cytarabine and mitoxantrone. Our patient aquired clinical and hematological remission without serious adverse events. 3 The CAS corpus

Content of the corpus

We present the CAS corpus in French. It contains clinical cases such as published in scientific literature and training material. Cases from these different sources are included in the corpus. Usually, the source data are available as pdf files. Their conversion in the text format is automatic but then needs to be fully checked out in order to correct potential segmentation errors (remove the paratext specific to a given journal, verify the conversion of columns, of end of lines and pages, etc.).

Similarly to clinical documents, the content of clinical cases depends on the clinical situations which are illustrated and on the disorders, but also on the purpose of the presented cases (description of diagnoses, treatments or procedures, expected audience, etc.). Figure 1 presents an example of clinical case in English. Such data are de-identified by the auhors and their publication is done with the written permission of patients. The case reports can be related to any medical situation (diagnosis, treatment, procedure, follow-up...) patient history, lab results, clinical evolution, treatment, etc. can also be provided for the illustration of clinical cases. Finally, these clinical cases are discussed. Hence, such cases may present an extensive description of medical problems. Such publications gather medical information related to clinical discourse (clinical cases) and to scientific discourse (introduction and discussion). Related scientific literature is also provided.

As we can see from Figure 1, the clinical part of publications on clinical cases may be very similar to clinical documents: it describes patients, and proposes their diagnosis based on examination, imaging, and biological and genetic information. Besides, numerical values and abbreviations are also present. Misspellings, which are quite frequent in clinical documents, may be missing in publications on clinical cases.

Annotation of the corpus

Currently, the corpus contains linguistic and semantic annotations.

At the linguistic level, the corpus is PoS-tagged and lemmatized with a tool developed in-house and available as a web-service at https:// anonymized_url. Then, several layers of semantic annotation are performed automatically:

• Concept Unique Identifiers (CUI) corresponding to French terms from the UMLS [START_REF] Da Lindberg | The unified medical language system[END_REF] for single or multiword terms. For multi-word terms, the annotations exploits the IOB (Inside-Outside-Begin) format. For instance, the two-word term vitamine B12 is encoded as follows:

... O vitamine B-C0042845 B12 I-C0042845 ... O

In the current version of the corpus, in case of several concurrent CUIs, only the longest, and supposedly more precise, CUIs are kept.

For instance, carence en vitamine B12 (deficiency in B12 vitamin) (C0042847) will be preferred to vitamine B12 (C0042845);

• Negation. Negation indicates whether a given disorder, procedure or treatment are present or not in the medical history and care of a given patient. For this reason, its annotation and detection are important. We adopt the approach proposed by [START_REF] Fancellu | Neural networks for negation scope detection[END_REF] and adapted for French by [START_REF] Dalloux | Portée de la négation : détection par apprentissage supervisé en franc ¸ais et portugais brésilien[END_REF] based on Machine Learning techniques trained on annotated data. This follows a two-step process: (1) the negation markers are detected with a specifically trained CRF;

(2) the scope of each detected marker is found with a neural network (Bi-LSTM with a CRF layer). On the French and English data tested, the detection of negation gives up to 0.98 for the cues and 0.86 for their scope;

• Uncertainty. Uncertainty is also an integral part of medical discourse and should be taken into account for a more precise computing of the status of disorders, procedures and treatments. A set of markers has been built manually. Since there may be several markers of negation and uncertainty in a sentence, they are numbered with their scopes accordingly.

In Table 1, we present an excerpt from the corpus with all the aforementioned linguistic and semantic annotations for the sentence L'adolescent paraît triste et ne parle pas. (The teenager seems to be sad and doesn't speak.)

Annotation statistics

Overall, the corpus currently contains 20,363 sentences and over 397,000 word occurrences excluding punctuation marks. Table 2 indicates the number of units automatically recognized for each category.

Conclusion

We presented a new corpus in French which provides medical data close to those produced in the clinical context: description of clinical cases and their discussion. Overall, the corpus currently contains over 397,000 word occurrences excluding punctuation marks. The corpus is currently annotated with several layers of information: linguistic (PoS-tagging, lemmas) and semantic (the UMLS concepts, uncertainty, negation and their scopes). The corpus will be enriched with more clinical cases published. Other annotation layers will be added and their correctness cross-validated by human annotators. The enriched version of the corpus will undergo a more detailed description, such as statistics on age and gender of patients, their diseases, or the sources of publications.

Besides, similar corpora will be built for other languages. For instance, the repository of clinical cases in English is available on a dedicated website Archive of Clinical Cases8 respecting the Creative Commons License.

The very purpose of our work is to make these annotated corpora freely available for research. We expect that this may encourage development of

Figure 1 :

 1 Figure 1: Example of clinical case

Table 1 :

 1 Example of the annotated sentence from the corpus (B-u-x stands for the beginning of the uncertainty cue or scope number x, B-n-y for the negation cue or scope number y)

	and to any disor-

Table 2 :

 2 Statistics on annotations 0.90 F-measure for the cues and 0.80 for the scope.

https://www.ncbi.nlm.nih.gov/pubmed

https://hal.archives-ouvertes.fr/

https://www.istex.fr/ tal signs, medications, laboratory measurements, observations and notes charted by care providers, fluid balance, procedure codes, diagnostic codes, imaging reports, hospital length of stay, survival data, and more. The database supports applications including academic and industrial research, quality improvement initiatives, and higher education coursework[START_REF] Alistair | MIMIC-iii, a freely accessible critical care database[END_REF]. These data are widely used by researchers, for instance for the prediction of mortality[START_REF] Rs Anand | Predicting mortality in diabetic icu patients using machine learning and severity indices[END_REF][START_REF] Feng | Transthoracic echocardiography and mortality in sepsis: analysis of the mimic-iii database[END_REF], for the diagnosis identification and coding[START_REF] Adler Perotte | Diagnosis code assignment: models and evaluation metrics[END_REF][START_REF] Li | Automated ICD-9 coding via a deep learning approach[END_REF], for the study of temporality[START_REF] Che | Recurrent neural networks for multivariate time series with missing values[END_REF] or for the identification of similar clinical notes[START_REF] Gabriel | Identifying and characterizing highly similar notes in big clinical note datasets[END_REF] to cite just a few of such works. Data from these corpora are also used in challenges, such as I2B2, N2C2 and CLEF-eHEALTH.I2B2 (Informatics for Integrating Biology and the

Bedside) 4 is an NIH-funded initiative promoting the development and test of NLP tools for healthcare improvement. In order to enhance the ability of NLP tools to process fine grained information from clinical records, I2B2 challenges provide sets of fully deidentified clinical notes enriched with specific annotations[START_REF] Uzuner | Second i2b2 workshop on natural language processing challenges for clinical records[END_REF][START_REF] Uzuner | 2010 i2b2/va challenge on concepts, assertions, and relations in clinical text[END_REF][START_REF] Sun | Evaluating temporal relations in clinical text: 2012 i2b2 challenge[END_REF], such as: deidentification, smoking status, medication-related information, semantic relations between entities, or temporality. The clinical corpora and their annotations built for the I2B2 NLP challenges are available now for the general research purposes.N2C2 (National NLP

Clinical Challenges) 5 , held for the first time in 2018, is dedicated to the inclusion of patients in clinical trials and the detection of adverse-drug events.

CLEF-eHEALTH challenges 6 held in 2013 and 2014 provide annotations for the detection of disorders and normalization of abbreviations, in 2016 the focus was done on structuring of Australian free-text nurse notes, and in 2016 and 2017 death reports in

French, provided by the CépiDc 7 , have been processed for the extraction of death causes.Finally, medical data, close to those handled in the clinical context, can be found in the clinical trials protocols. One example is the corpus of clinical trials annotated with information on numerical 4 https://www.i2b2.org/NLP/DataSets/ Main.php 5 https://n2c2.dbmi.hms.harvard.edu/ 6 https://sites.google.com/site/ shareclefehealth/ 7 http://www.cepidc.inserm.fr/

http://www.clinicalcases.eu robust NLP tools for medical free-text documents in French and other languages.

Acknowledgements

This work was partly funded by the French government support granted to the CominLabs LabEx managed by the ANR in Investing for the Future program under reference ANR-10-LABX-07-01.

The authors would like to thank Cyril Grouin for the discussions on existing medical corpora and the reviewers for their helpful comments.


Thoraya Ben Chattah

Sébastien Bougleux
email: bougleux@unicaen.fr

Olivier Lézoray
email: olivier.lezoray@unicaen.fr

Atef Hamouda

Patch-based potentials for interactive contour extraction

Keywords: Contour extraction, Patch, Minimal paths

The problem of interactive contour extraction of targeted objects of interest in images is challenging and finds many applications in image editing tasks. Several methods have been proposed to address this problem with a common objective: performing an accurate contour extraction with minimum user effort. For minimal paths techniques, achieving this goal depends critically on the ability of the so-called potential map to capture edges. In this context we propose new patch-based potentials designed to have small values at the boundary of the targeted object. To evaluate these potentials, we consider the livewire framework and quantify their abilities in terms of number of needed seed points. Both visual and quantitative results demonstrated the strong capability of our proposed potentials in reducing the user's interaction while preserving a good accuracy of extraction.

Introduction

Despite the high number of research works in image segmentation, interactive contour extraction is still a very challenging image processing problem. In contrast to the traditional image segmentation problem, many real-world applications focus on identifying the pixels belonging to a specific object. Their aim is to precisely delineate the contour of a targeted object. This is at the core of many image editing tasks in photography or medical image analysis: using a selection tool, an object is extracted and the background is removed. This process can be very difficult to do cleanly manually because of the presence of structures with ill-defined borders, and assistive tools can be very beneficial for end-users. For that, it is necessary for the user to provide inputs to ease the object extraction. These inputs can take different forms that are then incorporated into the segmentation process as hard or soft constraints. Since this requires an interaction with the user, all methods try to obtain accurate segmentation results while reducing the user's effort. There are essentially three methods in the literature to allow the user to specify the targeted object. The first is to label some pixels inside/outside the object [START_REF] Liu | Robust interactive image segmentation with automatic boundary refinement[END_REF] and to use a labeling process such as graph-cut based-methods [START_REF] Gulshan | Geodesic star convexity for interactive image segmentation[END_REF]. The second method is to provide a sub-region within the image that contains the object. Bounding boxes have often been considered for that, see [START_REF] Blake | Interactive image segmentation using an adaptive GMMRF model[END_REF], and have been popularized by the GrabCut method [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF]. The third method is to provide a curve close to the boundary or seed points on the boundary. Providing curves has been extensively employed in level sets and snakes methods [START_REF] Cohen | On active contour models and balloons[END_REF]. Providing points has been mainly employed with minimal path approaches [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF]. In the sequel we will focus on that last type of interaction that we call seed-based interactive contour extraction methods.

The paper is organized as follows. Section 2 provides a review of the minimal paths approach for interactive contour extraction and describes the livewire framework. Section 3 describes our patch-based potentials. They are compared in Section 4 through experiments on ISEG dataset.

Seed-based Interactive contour extraction methods

Minimal paths

Most seed-based interactive contour extraction methods rely on minimal paths. Given an image

f : Ω ⊂ R 2 → R n
+ and two seeds p s , p e ∈ Ω located on the contour of an object, the objective is to find a path from p s to p e that represents a piece of contour. In this paper, we consider the classical model presented in [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF]. A path from p s to p e is defined as a parametric curve γ : [0, 1] → Ω so that γ(0) = p s and γ(1) = p e , and its length as the cost:

L(γ) = 1 0 P (γ(s)) γ (s) ds. (1)
γ is the derivative of γ. P : Ω → R * + is a potential function derived from image f that has low values for edges. The length L(γ) is smaller when it goes through low values of P and one can search for curves that minimize L(γ) given a pair of starting and ending points. The goal is therefore to capture the minimal path γ * , also called the geodesic path, that globally minimizes the cost function defined in [START_REF] Blake | Interactive image segmentation using an adaptive GMMRF model[END_REF]:

L(γ * ) = min γ∈A(ps,pe) L(γ) (2)
with A(p s , p e ) the set of all possible paths joining p s to p e . The optimal cost defines the geodesic distance d(p s , p e ) = L(γ * ).

To tackle the minimization problem (2), the geodesic distance map U {ps} : Ω → R + from a point p s to any other point p ∈ Ω is considered: U {ps} (p) = d(p s , p) = min γ∈A(ps,p) L(γ). The distance map is solution of the Eikonal equation: The value U {ps} (p) can be interpreted as the arrival time at p of a front propagating from a point p s with speed 1/P . Fast marching method [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF][START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF] and Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] are often used to compute the values of U {ps} in increasing order, so that the process can be stopped when the end point p e is reached. Then the minimal path between p s and p e can be constructed by applying a back-propagation procedure (gradient descent) starting from p e along the gradient of the map U ps until arriving at p s . See [START_REF] Peyré | Geodesic methods in computer vision and graphics[END_REF] for more details. An interesting thing to note is that the result curve γ * depends strongly on the potential functional P which is usually built such as it takes lower values at the desired structure of interest and higher values elsewhere. Some works have suggested the use of new potential functionals or path cost functions in order to better discriminate the discontinuities between objects and background. To this end, and to go beyond classical edge-based energies, some authors have considered more evolved information such as texture, curvature [START_REF] Chen | Global minimum for curvature penalized minimal path method[END_REF], or orientation [START_REF] Bougleux | Anisotropic geodesics for perceptual grouping and domain meshing[END_REF]. We focus on this track of research in this paper.

∇U {ps} (p) = P (p), ∀p ∈ Ω U {ps} (p s ) = 0 (3)

Livewire interactive contour extraction framework

Before entering into the details of our proposed potentials, we focus on how interaction can be considered in seed-based minimal paths interactive contour extraction. When points are provided as seeds in minimal path approaches for contour extraction, the employed methods all adopt the same strategy. The user places seed points that provides an initial labelling for some pixels of the image. Then, an algorithm is performed to propagate the labels of seeds to unlabeled regions until an optimum criterion is reached. If this strategy is similar from one method to another, the interaction with the user for the providing of seeds differs. A first way to proceed consists in iteratively minimizing an energy functional for a given set of seed points on a contour [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF][START_REF] Mille | Combination of piecewise-geodesic paths for interactive segmentation[END_REF]. The main drawback of this type of user interaction is that the user cannot easily add new boundary points on the contour segments that were poorly extracted: this requires a complete Update Potential P (q) ← +∞, ∀ q ∈ γ * ps,pe \ {ps, pe} Compute geodesic distance map U {pe} with P Backtrack to determine the shortest curve γ * pe,p 1 from U {pe} ps ← pe until The user is satisfied with the extracted contour

Γ = Γ ∪ γ * p i+1 ,p 1
re-computation of the solution. A second more popular way to proceed is to let the user place new seed points after each label propagation step.

The user provides starting seed points and the optimal boundary is extracted. Then, the user can add another seed point if he is not satisfied. In that case, the previously extracted boundary is frozen and a new optimal path is computed to the new seed point. This process is repeated until the user decides to close the contour. These methods do belong to the livewire framework. They require an ordered sequence of seed points (provided one after the other) to extract the object's contour. The advantage of this type of interaction is that the user can control and predict the final result. The interaction should be minimal in the sense that few seeds should be used and the largest optimum path between them should be obtained. Algorithm 1 resumes the livewire interactive contour extraction framework and Figure 1 illustrates this interactive process to extract one contour with one of the potentials (P max 3 ) we propose thereafter. Significant examples of the livewire framework include intelligent scissors methods [START_REF] Mortensen | Intelligent scissors for image composition[END_REF], their variations with the on-the-fly extension [START_REF] Falcão | An ultra-fast user-steered image segmentation paradigm: live wire on the fly[END_REF], the G-wire extension [START_REF] Kang | G-wire: A livewire segmentation algorithm based on a generalized graph formulation[END_REF] and the riverbed algorithm [START_REF] Miranda | Riverbed: A novel user-steered image segmentation method based on optimum boundary tracking[END_REF].

Patch-based Potentials

In this section, we introduce new patch-based potentials for livewire contour extraction. Generally speaking, a contour is a curve Γ that separates optimally two regions R + and R -that have different features (e.g., color, texture). Our proposal consists in using patches as texture descriptors to build a potential map that has small values especially for edges pixels.

Notations

For a color image f , the color at a pixel p i = (x i , y i ) T is given by f (p i ) ∈ R 3 . A patch is a rectangular region of size (2w+1) 2 around a pixel and is defined by the vector P(p i ) = (f (p i + t), ∀t ∈ [-w, w] 2 ) T ∈ R 3(2w+1) 2 . The difference between two patches is provided by the L 2 -norm d(P(p i ), P(p j )) = P(p i ) -P(p j ) 2 .

Given t θ,δ a vector of translation δ according to the angle θ with the horizontal line, we can define the left and right pixels at a distance δ of a pixel p i on a line of angle θ with the horizon as: p l,θ,δ i = p i + t θ,δ and p r,θ,δ i = p i -t θ,δ . In the sequel, we will consider lines of angle θ ∈ {0 • , 45 • , 90 • , 135 • }.

Pixel-surround potentials

We propose two first potentials that consider only the pixels surrounding a current pixel p i in a 8-neighborhood. A pixel can be considered as lying on an edge if the patch at its left is different from the patch at its right. If we compute distances between these left and right patches, a high value means a high probability of contour. We therefore define a patch difference centered on p i as:

d θ,δ c (p i ) = d P(p l,θ,δ i ), P(p r,θ,δ i
) . However, the edge is not necessarily oriented along the y axis and we have to test all the possible orientations in a 8-neighborhood to define the potential:

P 1 (p i ) = max θ d θ,1
c (p i ) with δ = 1 since we consider only the surrounding pixels. This first potential is illustrated in Figure 2 (first row, first column). Since a pixel on an edge is also not supposed to be similar to its surrounding pixels, we can enhance this potential by computing upwind left or right differences between the pixel and its neighbors. We define d θ,δ l (p i ) = d P(p i ), P(p l,θ,δ i ) and d θ,δ r (p i ) = d P(p i ), P(p r,θ,δ i

) . Then, we can aggregate all these distances along a direction and take the maximum on all directions:

P AF 2 (p i ) = max θ AF (d θ,1 s (p i )) (4) with d θ,1 s (p i ) = {d θ,1 l (p i ), d θ,1 c (p i ), d θ,1
r (p i )} and AF an aggregation function among the min, the max and the mean. This second potential is illustrated in Fig. 2 (first row, second column) and Fig. 3.

Band-based potentials

The drawback of the previous potentials is that they are operating on a small neighborhood to discriminate edge from non-edge pixels. It might be much more beneficial to study a larger neighborhood. Indeed if there is a texture edge at pixel p i it is natural to expect that shifted patches to the left are different from shifted patches to the right. To take this into account we generalize the previous potential P 2 to operate on a longer line and to consider pixels that are much farther than a distance δ = 1. To that aim, we consider a band of ns patches on a side of the line and to avoid an overlap between the patch at p i and its left and right patches, we consider pixels at a distance δ ∈ [ , + ns]. For each possible Then we can aggregate all these distances between the band of patches along a direction and take the maximum on all directions:

P AF 3 (p i ) = max θ AF min δ∈[ , +ns] , d θ,δ s (p i ), ∀s ∈ {l, c, r} (5)
This third potential is illustrated in Fig. 2 (second row, first column) and Fig. 3.

Seed-dependent patch-based potential

All the previous potentials we proposed can be considered as blind as they do not take into account the previously positioned seeds to compute the potential.

To overcome this, we design a seed-dependent patch-based potential. Given a seed p s , it is expected that the regions R + (p s ) and R -(p s ) on its both sides will be similar to the other regions for the next points of the contour. However, for the first seed p s = p 1 (Algorithm 1), we have no exact idea of the orientation to define the regions it separates. To cope with this, we search for the angle θ s that maximizes the differences between the set of patches of the two regions. These set of patches are contained within 45 • to the band defined by the angle θ to the horizon. We consider only 5 patches of size 5 × 5 with minimum overlap for each region. Finally for p 1 ,

θ 1 = arg max θ max q1×q2 q1∈R + θ (p1) q2∈R - θ (p1)
d(P(q 1 ), P(q 2 ))

This provides two regions R + θ1 (p 1 ) and R - θ1 (p 1 ) according to the retained orientation θ 1 . For any other seed p s = p 1 , the regions R + θs (p s ) and R - θs (p s ) are defined from the normal N s = (γ * s-1,s (p s )) ⊥ / γ * s-1,s (p s ) to the shortest path γ * s-1,s at p s by the angle θ s = arg min θ ∠(N s , p s p l,θ,

Then, for each point p i of the image, we compute all the pairwise distances between the regions R + θs (p s ) and R + θ (p i ) (and similarly for R -) for different orientations θ around p i . We retain only the minimum value that accounts for a very similar configuration between p s and p i . This can be formulated by:

P 4 (p i ) = min θ       min q1×q2 q1∈R + θ (pi) q2∈R + θs (ps)
d(P(q 1 ), P(q 2 )) + min

q1×q2 q1∈R - θ (pi) q2∈R - θs (ps)
d(P(q 1 ), P(q 2 ))

      (7)
This potential is illustrated in Figure 2 (second row, second column) and Figure 3 (the red point shows the seed p s ). Contrary to the other potentials, it must be computed at each iteration of Algorithm 1.

Experiments

User simulation for contour extraction evaluation

As introduced in [START_REF] Spina | Robot users for the evaluation of boundary-tracking approaches in interactive image segmentation[END_REF], to reliably evaluate the effectiveness of approaches for contour extraction, one should ideally eliminate the user bias, while obtaining quality measures of the result. To cope with this, user agents have to be considered. These agents should be able to simulate the human user behavior through the addition of seeds close to the objects boundary. To do so, they have to evaluate the optimum-boundary segment being computed from a previously selected seed point to a virtual mouse position, seeking for the longest possible segment with minimum acceptable error. A new seed is then added when the error is too high and the agents iterate until closing the contour, just like real users.

To achieve that, we have designed our own user agent dedicated to the livewire framework. A starting point p s close to the ground truth object contour is selected using some criterion. In our case, the point has to be contained in a tube T of radius r on both sides of the contour (Fig. 5b). The virtual mouse position of the user is then simulated by finding a point p e that satisfies three criteria.

First it has to be located in tube T . Second, the length of the path γ ps,pe must be the largest one among all possible paths joining p s and p e . Third, all points of the curve γ ps,pe must be in the tube T . To do so, we perform a dichotomous search along the ground truth object contour (Fig. 5b). To close the contour, the last step of our simulation algorithm consists of trying to find a path γ ps,pe that fulfills the third criterion. If it is not the case, point p e is considered as the new seed starting point of the next iteration, as this is the case in the livewire framework (see Algorithm 1). The final contour being in a tube T of radius r on both sides of the contour, the contour extraction error is proportional to the radius of the tube: the larger r, the higher the contour extraction error.

Results

To demonstrate the ability of the proposed potentials to recover closed boundaries of objects in color images, we have carried out experiments on ISEG [START_REF] Gulshan | Geodesic star convexity for interactive image segmentation[END_REF]. We ran Algorithm 1 for all the potentials with the user agent behavior. To have a fair comparison between the compared potentials, the first starting point is always the same on a given image. The criteria used to compare two potentials will be: i) the average of the ratio between the number of seeds and the length of the ground truth contour (the lesser the better, this will be denoted by % of seeds), ii) the Jaccard index that measures the similarity between the extracted contour and the ground truth. Since we use patch-based potentials, the first question that we can ask is what is the best patch size. We have considered three different patch sizes w ∈ {1, 2, 3} that correspond to 3 × 3, 5 × 5 and 7 × 7 patches. For band-based potentials (i.e., P 3 ), the length of the band is set to ns = 5. For potentials that rely on an aggregation function (P 2 and P 3 ), we consider the min, max and mean aggregation functions. This means that we have three different configurations for each one of these potentials and this will be specified with an upperscript. Figure 4 shows an histogram that counts, on the ISEG dataset, the number of times that a potential gives the minimum % of seeds for different patch sizes. We do not show the Jaccard index since its average values are very close for all potentials (this was attended since we use simulated user agents). From these results, we can see that the best results are mostly always obtained with band-based potentials (with P max

3

). This shows the interest of going farther than the pixel surround and the proposed patch-based potentials have the ability to better delineate the object contour with less seeds when considering 5 × 5 patches. In the sequel we have retained this size.

Once this best patch size has been fixed, we compare the best potential we have proposed and tested so far, namely P max 3 , with the classical pixeledge potential map [START_REF] Mille | Combination of piecewise-geodesic paths for interactive segmentation[END_REF] based on gradient magnitude and defined as P E = µ +

Conclusion

In this paper new patch-based potentials have been proposed for minimal path contour extraction. Their interest has been assessed in terms of the number points needed to perform the contour extraction, so that the user interaction is potentially minimized. To eliminate the user bias in the interactive process, a dedicated user agent has been conceived. Results have shown that patch-based potentials can overcome the classical pixel-based ones and improve object contour extraction.

  Fig. 1: A livewire interactive contour extraction.

Algorithm 1

 1 Livewire contour extraction framework Potential function P , Seed set S = ∅, extracted contour Γ Select seed point p1 Compute geodesic distance map U {p 1 } with P ps ← p1, S ← S ∪ {ps} repeat Select pe Backtrack to determine the shortest curve γ * ps,pe from U {ps} S ← S ∪ {pe}, Γ ← Γ ∪ γ * ps,pe

Fig. 2 :

 2 Fig. 2: Computation principles of the proposed potentials.

Fig. 3 :

 3 Fig. 3: Potentials maps with 5 × 5 patches, AF = max for P 2 and P 3 , = 2 and ns = 5 for P 3 , and α = 0.3 for P 5 .

Fig. 4 :

 4 Fig. 4: Number of times where a potential gives the minimum % of seeds (a) w = 1 ; (b) w = 2 ; (c) w = 3.

Fig. 5 :

 5 Fig. 5: (a) Quantitative comparison between potentials. (b) Tube of radius r surrounding a ground truth curve and process to find the next seed from the current one (red dot). The black curve is finally retained.

performs always better than the baseline P E potential in terms of both criteria (% of seeds and Jaccard index). It is important to note that a difference of 0.1% on the average % of seeds corresponds to 1.5 points). This is shown in Fig. 5a. However, if the results are in favor of potential P max 3 , this is not the case for potential P 4 . But for some images, P 4 performs better. This is illustrated in Figure 6 where less seeds are needed for the first image. Since no general rule can be devised to choose between potentials P max 3 and P 4 , we choose to combine them with P 5 = αP max 3 + (1 -α)P 4 . To choose the best α, we have tested values within [0, 1] and retained the one that minimizes the % of seeds. We obtained a value of α = 0.3. With this new potential P 5 , one can see that we overpass by far the classical pixel-edge potential as well as all the patch-based potential we considered. In addition, this is true whatever the considered radius r of the user agent, which enforces the robustness of our proposed seed-dependent patch-based potential P 5 .