Mathieu Mangeot
email: mathieu@mangeot.org

David Thevenin
email: thevenin@nii.ac.jp

Online Generic Editing of Heterogeneous Dictionary Entries in Papillon Project

The Papillon project is a collaborative project to establish a multilingual dictionary on the Web. This project started 4 years ago with French and Japanese. The partners are now also working on English, Chinese, Lao, Malay, Thai and Vietnamese. It aims to apply the LINUX cooperative construction paradigm to establish a broadcoverage multilingual dictionary. Users can contribute directly on the server by adding new data or correcting existing errors. Their contributions are stored in the user space until checked by a specialist before being fully integrated into the database. The resulting data is then publicly available and freely distributable. An essential condition for the success of the project is to find a handy solution for all the participants to be able to contribute online by editing dictionary entries.In this paper, we describe our solution for an online generic editor of dictionary entries based on the description of their structure.

Introduction

The Papillon Project [START_REF] Sérasset | Papillon lexical database project: Monolingual dictionaries and interlingual links[END_REF]) is a cooperative project for a multilingual dictionary on the Web with the following languages: English, Chinese, French, Japanese, Lao, Malay, Thai and Vietnamese. The dictionary structure makes it very simple to add a new language at any time. It aims to apply the LINUX construction paradigm to establish a multilingual usage dictionary with broadcoverage.

This project is based on the participation of voluntary contributors. In order to be really attractive, this project must imperatively find a convenient solution so that contributors can easily edit the dictionary entries. Since Papillon dictionary is available on a web server and the contributors are located all around the world, the obvious solution is to implement an editor available online. Unfortunately, the existing so-lutions (HTML forms, java applets) have important limitations. Thus, we propose an entirely generic solution that can adapt very easily not only the interfaces to the various entry structures needing to be edited but also to the user needs and competences.

Firstly, we outline the issue addressed in this paper; and draw up an overview of the existing methods for dictionary entry edition. A presentation of the chosen method follows detailing its integration in the Papillon server. Finally, we show an example of the online edition of a dictionary entry.

Addressed Issue and Requirements

In this paper, the addressed issue is how to edit online dictionary entries with heterogeneous structures.

Online Edition

In order to build a multilingual dictionary that covers a lot of languages, we need large competences in those languages. It may be possible to find an expert with enough knowledge of 3 or 4 languages but when that number reaches 10 languages (like now), it is almost impossible. Thus, we need contributors from all over the world.

Furthermore, in order to avoid pollution of the database, we plan a two-step integration of the contributions in the database. When a contributor finishes a new contribution, it is stored into his/her private user space until it is revised by a specialist and integrated into the database. Then, each data needs to be revised although the revisers may not work in the same place of the initial contributors.

Thus, the first requirement for the editor is to work online on the Web.

Heterogeneous Entry Structures

The Papillon platform is built for generic purposes. Thus, it can manipulate not only the Papillon dictionary but also any kind of dictionary encoded in XML [START_REF] Mangeot | An xml markup language framework for lexical databases environments: the dictionary markup language[END_REF]. The lexical data is organized in 3 layers:

• Limbo contains dictionaries in their original format and structure;

• Purgatory contains dictionaries in their original format but encoded in XML;

• Paradise contains the target dictionary, in our case Papillon dictionary.

The Purgatory data can be reused for building the Paradise dictionary. We would like then to be able to edit different dictionaries structures from Paradise but also from Purgatory. Furthermore, being Papillon a research project, entry structures may evolve during the life of the project, since they are not fixed from the beginning.

Hence, the second requirement is that the editor must deal with heterogeneous and evolving entry structures.

Extra Requirements

Previous requirements must be fulfilled, whilst the following ones are optional.

The contributors will have various competences and use the editor for different purposes (a specialist in speech may add the pronunciation, a linguist may enter grammatical information, a translator would like to add interlingual links, and a reviewer will check the existing contributions, etc.).

The second optional requirement concerns the adaptation to the user platform. The increasing number of smart mobile phones and PDAs makes real the following scenarios: adding an interlingual link with a mobile phone, adding small parts of information with a PDA and revising the whole entry with a workstation.

It would then be very convenient if the editor could adapt itself both to the user and to the platform.

Final Aim

Guided by these requirements, our final aim is to generate, as much automatically as possible, online interfaces for editing dictionary entries. It has to be taken into account the fact that entry structures are heterogeneous and may vary and to try to adapt as much as possible these interfaces to the different kinds of users and platforms.

Overview of Existing Editing Methods

Local and Ad Hoc

The best way to implement a most comfortable editor for the users is to implement an adhoc application like the one developed for the NADIA-DEC project: DECID [START_REF] Sérasset | Le projet nadia-dec : vers un dictionnaire explicatif et combinatoire informatisé ?[END_REF].

It was conceived to edit entries for the ECD (Mel'čuk et al., 1984889296). The Papillon microstructure is based on a simplification of this structure. We were indeed very interested by such software. It is very convenient -for example -for editing complex lexical functions.

But several drawbacks made it impossible to use in our project. First, the editor was developed ad hoc for a particular entry structure. If we want to change that structure, we must reimplement changes in the editor.

Second, the editor is platform-dependent (here written and compiled for MacOs). The users have to work locally and cannot contribute online.

Distributed and Democratic

This solution implemented for the construction of the French-UNL dictionary [START_REF] Sérasset | L'édition lexicographique dans un système générique de gestion de bases lexicales multilingues[END_REF] project is called "democratic" because it uses common and widespread applications (works on Windows and MacOs) such as Microsoft Word.

The first step is to prepare pre-existing data on the server (implemented here in Macintosh Common Lisp). Then, the data is converted into rtf by using a different Word style for each part of information (the style "headword" for the headword, the style "pos" for the part-ofspeech, etc.) and exported. The clients can open the resulting rtf files locally with their Word and edit the entries. Finally, the Word rtf files are reintegrated into the database via a reverse conversion program.

This solution leads to the construction of 20,000 entries with 50,000 word senses. It was considered as a very convenient method, nevertheless, two important drawbacks prevented us to reuse this solution. The first is that in order to convert easily from the database to rtf and vice-versa, the dictionary entry structure cannot be too complex. Furthermore, when the user edits the entry with Word, it is very difficult to control the syntax of the entry, even if some Word macros can partially remedy this problem.

The second is the communication between the users and the database. The Word files have to be sent to the users, for example via email. It introduces inevitably some delay. Furthermore, during the time when the file is stored on the user machine, no other user can edit the contents of the file. It was also observed that sometimes, users abandon their job and forget to send their files back to the server.

Online and HTML Forms

In order to work online, we should then use either HTML forms, or a Java applet. The use of HTML forms is interesting at a first glance, because the implementation is fast and all HTML browsers can use HTML forms.

On the other hand, the simplicity of the forms leads to important limitations. The only existing interactors are: buttons, textboxes, pop-up menus, and checkboxes.

JavaScripts offer the possibility to enrich the interactors by verifying for example the content of a textbox, etc. However, very often they raise compatibility problems and only some browsers can interpret them correctly. Thus, we will avoid them as much as possible.

One of the major drawbacks of this solution is our need to modify the source code of the HTML form each time we want to modify the entry structure. We also need to write as many HTML forms as there are different entry structures.

Online and Java Applets

In order to remedy the limitations of the HTML forms and to continue to work online, there is the possibility to use a java applet that will be executed on the client side. Theoretically, it is possible to develop an ad hoc editor for any complicated structure, like the 3.1 solution.

Nevertheless, the problems linked to the use of a java applet are numerous: the client machine must have java installed, and it must be the same java version of the applet. Furthermore, the execution is made on the client machine, which can be problematic for not very powerful machines. Moreover, nowadays there is a strong decrease of java applets usage on the Web mainly due to the previous compatibility problems.

Conclusion

As a result, none of these existing solutions can fully fulfil our requirements: online edition and heterogeneous entry structures. We might then use other approaches that are more generic like the ones used in interface conception in order to build our editor. In the remainder of this paper, we will detail how we used an interface generation module in Papillon server in order to generate semi-automatically editing interfaces.

Using an Interface Generation Module

This Papillon module has to generate graphic user interfaces for consulting and editing dictionary entries. We base our approach on the work done on Plasticity of User interfaces [START_REF] Thevenin | Plasticity of user interfaces: Framework and research agenda[END_REF] and the tool ART-Studio [START_REF] Calvary | Unifying reference framework for the development of plastic user interfaces[END_REF]. They propose frameworks and mechanisms to generate semiautomatically graphic user interfaces for different targets. Below we present the design framework and models used.

Framework for the UI generation

Our approach [START_REF] Calvary | Plasticity of user interfaces: A revised reference framework[END_REF] is based on four-generation steps (Figure 1). The first is a manual design for producing initial models. It includes the application description with the data, tasks and instances models, and the description of the context of use. This latter generally includes the platform where the interaction is done, the user who interacts and the environment where the user is. In our case we do not describe the environment, since it is too difficult and not really pertinent for Papillon.

From there, we are able to generate the Abstract User Interface (AUI). This is a platform independent UI. It represents the basic structure of the dialogue between a user and a computer. In the third step, we generate the Concrete User Interface (CUI) based on the Abstract User Interface (AUI). It is an instantiation of the AUI for a given platform. Once the interactor (widget) and the navigation in UI have been chosen, it is a prototype of the executable UI. The last stage is the generation of Final User Interface (FUI). This is the same as concrete user interface (CUI) but it can be executed.

We will now focus on some models that describe the application.

Application Models: Data & Task

The Data model describes the concepts that the user manipulates in any context of use. When considering plasticity issues, the data model should cover all usage contexts, envisioned for the interactive system. By doing so, designers obtain a global reusable reference model that can be specialized according to user needs or As showed on Figure 2, the model of concepts will drive the choice of interactors and the structure of the interface.

Instance Model

It describes instances of the concepts manipulated by the user interface and the dependence graph between them. For example there is the concept "Entry" and one of its instances "scientifique". (cf. Figure 3). This model is described at design time, before generation, and linked with the task model (a task uses a set of instances). Each instance will be effectively created at run-time with data coming from the Papillon database.

Platform and Interactors Models

A platform is described by interaction capacity (for example, screen size, mouse or pen, keyboard, speech recognition, etc.). These capacities will influence the choice of interactors, presentation layouts or the navigation in the user interface.

Associated to the platform there are the interactors (widgets) proposed by the graphic toolsbox of the targeted language (for example Swing or AWT for Java). In this project interactors are coming from HMTL Forms (textBox, comboBox, popup menu, button, checkBox, ra-dioButton) and HTML tags. We also had to build more complex interactors by a combination of HTML Forms and HTML Tags.

User Model

Previous research has shown the difficulty to describe the cognitive aspects of user behavior. Therefore, we will simplify by defining different user classes (tourist, student, business man, etc.). Each class will be consisting of a set of design preferences. Depending on the target class, the generator will use appropriate design rules.

The model is not yet implemented; it is implicitly used in the data & task models. We defined different views of data according to the target:

• all data is rendered for the workstation editing interface for lexicographers,

• only headword and grammatical class are rendered and examples are browsable on the mobile phone interface for a "normal" dictionary user.

Concrete User Interface Model

This model, based on an independent user interface language, describes the graphic user interface, as the final device will render it. It is target-dependent.

Final User Interface

From the CUI model, the generator produces a final interface that will be executed by the targeted device, and links it with the Papillon database. In our case we produce:

• HTML code for the workstation, Figure 4: Generated GUI

• Tiny XHTML code for AU mobile phones,

• and CGI links for the communication with the database.

Figure 4 shows a simple example of a final generated UI.

Integrating the Module in Papillon Server

Implementation

The Papillon server is based on Enhydra, a web server of Java dynamic objects. The data is stored as XML objects into an SQL database: PostgresQL. ARTStudio tool is entirely written in Java. For its integration into the Papillon/Enhydra server, we created a java archive for the codes to stay independent.

The Papillon/Enhydra server can store java objects during a user session. When the user connects to the Papillon server with a browser, a session is created and the user is identified thanks to a cookie. When the user opens the dictionary entry editor, the java objects needed for the editor will be kept until the end of the session.

A Working Session

When the editor is launched, the models corresponding to the entry structure are loaded. Then, if an entry is given as a parameter (editing an existing entry), the entry template is instantiated with the data contained in that entry. If no entry is given, the template is instantiated with an empty entry. Finally, the instantiated models and entry templates are stored into the session data and the result is displayed embedded in an HTML form, through a Web page (Figure 4).

Then, after a user modification (e.g. adding an item to the examples list), the HTML form At the end of the session, the modified entry is extracted from the session data and then stored as a contribution in the database.

An Editing Example

6.1 A Dictionary Entry Figure 5 shows an abstract view of a simple dictionary entry. It is the entry "scientifique" (scientific) of a French monolingual dictionary. The entry has been simplified on purpose. The entries are stored as XML text into the database.

Entry Structure

The generation of the graphic interface is mostly based on the dictionary microstructure. In the Papillon project, we describe them with XML schemata. We chose XML schemata instead of DTDs because they allow for a more precise description of the data structure and handled types. For example, it is possible to describe the textual content of an XML element as a closed value list. In this example, the French part-ofspeech type is a closed list of "nom", "verb", and "adj".

Figure 6 is an abstract view of the structure corresponding to the previous French monolingual dictionary entry.

Entry Displayed in the Editor

The dictionary entry of Figure 5 is displayed in the HTML editor as in Figure 4. In the following one (Figure 7), an example has been added in the list by pushing the + button. Two interesting points may be highlighted. You can note that not only the content of the entry is in Japanese, but also the text labels of the information. For example, the first one, ‹úWž (midashigo) means headword. The interface generator is multitarget: it generates the whole HTML content. It is then possible to redefine the labels for each language.

The second point is the complexity of the entry structure. There is a list of lexical functions. Each lexical function consists of a name and a list of valgroups (group of values), and in turn, each valgroup consists of a list of values. Finally, each value is a textbox. The lists are nested the one in the other one and it is possible to use the lists + and -operators at any level.

Evaluation

Preamble

This paper focuses on one particular functionality of the Papillon platform: the generic editor. Its purpose is not to present the building of Papillon dictionary or the progress of Papillon Project as a whole. The evaluation will then focus on the editor. The contribution phase on Papillon project has not begun yet. Thus, for the moment, very few users tested the editor. We have not yet enough data to evaluate seriously the usability of the interface. Then, the evaluation will be driven on the technical aspects of the editor.

In order to evaluate the genericity and the usability of the editor, we generated interfaces for two other dictionary structures: the GDEF Estonian-French dictionary and the WaDoku-JiTen Japanese-German dictionary.

Edition of the GDEF dictionary

The GDEF project (Big Estonian-French Dictionary) is managed by Antoine Chalvin from INALCO, Paris. The dictionary microstructure is radically different from the Papillon dictionary as you will see in Figure 9 compared to figure 8. You may notice the 6 levels of recursion embedded in the entry structure.

It took about one week to write the interface description files for the new dictionary structure in order to generate properly a complete interface for the GDEF dictionary.

Edition of the WaDokuJiTen

The WaDokuJiTen project is managed by Ulrich Apel, now invited researcher at NII, Tokyo. The dictionary is originally stored in a File-Maker database. It has more than 200,000 entries. It took four days to export integrate the dictionary in Papillon platform and to write the files needed for the generation of the editor interface. The integration was done in 4 steps: export the dictionary from FileMaker into an XML file, tag the implicit structure with a perl script, write the metadata files and upload the dictionary on the Papillon server.

The dictionary microstructure is simpler than the previous one (see figure 10). It took only two days to write the files needed for the generation of the editor interface.

Conclusion

The implementation of ARTStudio and Papillon plateform started separately four years ago. The development of the HTML generation module in ARTStudio and its integration into Papillon platform took about a year from the first specifications and the installation of a complete and functional version on the Papillon server. The collaboration between a specialist of computational lexicography and a specialist of the adaptability of interfaces has produced very original and interesting work. Furthermore, the evaluation and the feedback received from the users is very positive. Now, we want to further pursue this work following several paths.

First of all, only a specialist can use the existing interface for Papillon entry since it is too complex for a beginner. We plan to generate different interface types adapted to the varied user needs and competences. Thanks to the modularity of the editor, we need only to describe the tasks and instance models corresponding to the desired interface.

For the moment, the interface generation is not fully automatic; some of the model descriptions used by the editor have to be written "by hand". This is why we are working now on automating the whole generation process and the implementation of graphical editors allowing users to post-edit or modify a generated interface description.

  Figure 1: Multitarget Generation Framework

  Figure 3: Relation Between the XML Entry and its Corresponding Instance

Figure 5 :

 5 Figure 5: Abstract View of an Entry

Figure 6 :

 6 Figure 6: Structure of an Entry

Figure 8 :

 8 Figure 8: Papillon Entry Displayed in the Editor

Figure 9 :

 9 Figure 9: GDEF Entry Displayed in the Editor


Giacomo Nardi
email: nardi@ceremade.dauphine.fr

Gabriel Peyré
email: peyre@ceremade.dauphine.fr

Franc ¸ois-Xavier Vialard
email: vialard@ceremade.dauphine.fr

Geodesics on Shape Spaces with Bounded Variation and Sobolev Metrics

Keywords: 2010 Mathematics Subject Classification: Primary 49J45, 58B05, Secondary 49M25, 68U05 Geodesics, Martingale, BV 2 -curves, shape registration

This paper studies the space of BV 2 planar curves endowed with the BV 2 Finsler metric over its tangent space of displacement vector fields. Such a space is of interest for applications in image processing and computer vision because it enables piecewise regular curves that undergo piecewise regular deformations, such as articulations. The main contribution of this paper is the proof of the existence of a shortest path between any two BV 2 curves for this Finsler metric. The method of proof relies on the construction of a martingale on a space satisfying the Radon-Nikodym property and on the invariance under reparametrization of the Finsler metric. This method applies more generally to similar cases such as the space of curves with H k metrics for k 2 integer. This space has a strong Riemannian structure and is geodesically complete. Thus, our result shows that the exponential map is surjective, which is complementary to geodesic completeness in infinite dimensions. We propose a finite element discretization of the minimal geodesic problem, and use a gradient descent method to compute a stationary point of a regularized energy. Numerical illustrations show the qualitative difference between BV 2 and H 2 geodesics.

Introduction

This paper addresses the problem of the existence of minimal geodesics in spaces of planar curves endowed with several metrics over the tangent spaces. Given two initial curves we prove the existence of a minimizing geodesic joining them. Such a result is proved by the direct methods of calculus of variations.

We treat the case of BV 2 -curves and H k -curves (k 2 integer). Although the proof's strategy is the same, the BV 2 and H k cases are slightly different and the proof in the H k case is simpler. This difference is essentially due to the inherent geometric structures (Riemannian or Finslerian) of each space.

We also propose a finite element discretization of the minimal geodesic problem. We further relax the problem to obtain a smooth non-convex minimization problem. This enables the use of a gradient descent algorithm to compute a stationary point of the corresponding functional. Although these stationary points are not in general global minimizers of the energy, they can be used to explore numerically the geometry of the corresponding spaces of curves, and to illustrate the differences between the Sobolev and BV 2 metrics.

Previous Works

Shape spaces as Riemannian spaces. The mathematical study of spaces of curves has been largely investigated in the last years, see for instance [START_REF] Younes | Computable elastic distances between shapes[END_REF][START_REF] Mennucci | Level set and PDE based reconstruction methods: Applications to inverse problems and image processing[END_REF]. The set of curves is naturally modeled over a Riemannian manifold [START_REF] Michor | Riemannian geometries on spaces of plane curves[END_REF]. This corresponds to using a Hilbertian metric on each tangent plane of the space of curves, i.e. the set of vector fields which deform infinitesimally a given curve. Several recent works [START_REF] Michor | Riemannian geometries on spaces of plane curves[END_REF][START_REF] Charpiat | Designing spatially coherent minimizing flows for variational problems based on active contours[END_REF][START_REF] Yezzi | Metrics in the space of curves[END_REF][START_REF] Yezzi | Conformal metrics and true "gradient flows" for curves[END_REF] point out that the choice of the metric notably affects the results of gradient descent algorithms for the numerical minimization of functionals. Carefully designing the metric is thus crucial to reach better local minima of the energy and also to compute descent flows with specific behaviors. These issues are important for applications in image processing (e.g. image segmentation) and computer vision (e.g. shape registration). Typical examples of such a Riemannian metrics are Sobolev-type metrics [START_REF] Sundaramoorthi | Sobolev Active Contours[END_REF][START_REF] Sundaramoorthi | Tracking with Sobolev active contours[END_REF][START_REF] Sundaramoorthi | New Possibilities with Sobolev Active Contours[END_REF][START_REF] Sundaramoorthi | Properties of Sobolev-type metrics in the space of curves. Interfaces and Free Boundaries[END_REF] which lead to smooth curve evolutions.

Shape spaces as Finslerian spaces. It is possible to extend this Riemannian framework by considering more general metrics on the tangent planes of the space of curves. Finsler spaces make use of Banach norms instead of Hilbertian norms [START_REF] Bao | An introduction to Riemaniann-Finsler geometry[END_REF]. A few recent works [START_REF] Mennucci | Level set and PDE based reconstruction methods: Applications to inverse problems and image processing[END_REF][START_REF] Yezzi | Metrics in the space of curves[END_REF][START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF] have studied the theoretical properties of Finslerian spaces of curves.

Finsler metrics are used in [START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF] to perform curve evolution in the space of BV 2 -curves. The authors make use of a generalized gradient which is the steepest descent direction according to the Finsler metric. The corresponding gradient flow enables piecewise regular evolutions, which is useful for applications such as registration of articulated shapes. The present work naturally follows [START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF]. Instead of considering gradient flows to minimize smooth functionals, we consider the minimal geodesic problem. The existence of solutions to this problem is important to understand the underlying space of curves. This problem is also useful to perform registration of two shapes in computer vision applications.

Geodesics in shape spaces. The computation of geodesics over Riemannian spaces is now routinely used in many imaging applications. Typical examples of applications include shape registration [START_REF] Sundaramoorthi | A new geometric metric in the space of curves, and applications to tracking deforming objects by prediction and filtering[END_REF][START_REF] Vaillant | Statistics on diffeomorphisms via tangent space representations[END_REF][START_REF] Trouvé | Shape splines and stochastic shape evolutions: A second order point of view[END_REF], tracking [START_REF] Sundaramoorthi | A new geometric metric in the space of curves, and applications to tracking deforming objects by prediction and filtering[END_REF] and shape deformation [START_REF] Kilian | Geometric modeling in shape space[END_REF]. Geodesic computations also serve as the basis to perform statistics on shape spaces, see for instance [START_REF] Vaillant | Statistics on diffeomorphisms via tangent space representations[END_REF][START_REF] Arsigny | A Log-Euclidean framework for statistics on diffeomorphisms[END_REF] and to generalize standard tools from Euclidean geometry such as averages [START_REF] Arsigny | Geometric means in a novel vector space structure on symmetric positive-definite matrices[END_REF], linear regression [START_REF] Niethammer | Geodesic regression for image time-series[END_REF] and cubic splines [START_REF] Trouvé | Shape splines and stochastic shape evolutions: A second order point of view[END_REF], to name a few. However, due to the infinite dimensional nature of shape spaces, not all Riemannian structures lead to well-posed length-minimizing problems. For instance, a striking result [START_REF] Michor | Riemannian geometries on spaces of plane curves[END_REF][START_REF] Yezzi | Conformal metrics and true "gradient flows" for curves[END_REF][START_REF] Yezzi | Metrics in the space of curves[END_REF] is that the natural L 2 -metric on the space of curves is degenerate, despite its widespread use in computer vision applications. Indeed, the geodesic distance between any pair of curves is equal to zero.

The study of the geodesic distance over shape spaces (modeled as curves, surfaces or diffeomorphisms) has been widely developed in the past ten years [START_REF] Michor | A zoo of diffeomorphism groups on R n[END_REF][START_REF] Bauer | Sobolev metrics on the manifold of all Riemannian metrics[END_REF][START_REF] Bauer | Sobolev metrics on shape space, II: Weighted Sobolev metrics and almost local metrics[END_REF]. We refer the reader to [START_REF] Bauer | Overview of the geometries of shape spaces and diffeomorphism groups[END_REF] for a review of this field of research. These authors typically address the questions of existence of the exponential map, geodesic completeness (the exponential map is defined for all time) and the computation of the curvature. In some situations of interest, the shape space has a strong Riemannian metric so that the exponential map is a local diffeomorphism. In [START_REF] Michor | An overview of the Riemannian metrics on spaces of curves using the hamiltonian approach[END_REF] the authors describe geodesic equations for Sobolev metrics. They show in Section 4.3 the local existence and uniqueness of a geodesic with prescribed initial conditions. This result is improved in [START_REF] Bruveris | Geodesic completeness for Sobolev metrics on the space of immersed plane curves[END_REF], where the authors prove the existence for all time. Both previous results are proved by techniques from ordinary differential equations. In contrast, local existence (and uniqueness) of minimizing geodesics with prescribed boundary conditions (i.e. between a pair of curves) is typically obtained using the exponential map. In finite dimension, existence of minimizing geodesics between any two points (global existence) is obtained by the Hopf-Rinow theorem [START_REF] Milnor | Morse theory[END_REF]. Indeed, if the exponential map is defined for all times (i.e. the space is geodesically complete) then global existence holds. This however is not true in infinite dimensions, and a counter example of non-existence of a geodesic between two points over a manifold is given in see [START_REF] Grossman | Hilbert manifolds without epiconjugate points[END_REF]. An even more pathological case is described in [START_REF] Atkin | The Hopf-Rinow theorem is false in infinite dimensions[END_REF] where an example is given where the exponential map is not surjective although the manifold is geodesically complete. Some positive results exist for infinite dimensional manifold (see in particular Theorem B in [START_REF] Ekeland | The Hopf-Rinow theorem in infinite dimension[END_REF] and Theorem 1.3.36 in [START_REF] Mennucci | Level set and PDE based reconstruction methods: Applications to inverse problems and image processing[END_REF]) but the surjectivity of the exponential map still needs to be checked directly on a case-by-case basis.

In the case of a Finsler structure on the shape space, the situation is more complicated since the norm over the tangent plane is often non-differentiable. This non-differentiability is indeed crucial to deal with curves and evolutions that are not smooth. This implies that geodesic equations need to be understood in a weak sense. More precisely, the minimal geodesic problem can be seen as a Bolza problem on the trajectories H 1 ([0, 1], BV 2 (S 1 , R 2 )). In [START_REF] Mordukhovich | Variation Analysis and Generalized Differentiation II, Applications[END_REF] several necessary conditions for existence of solutions to Bolza problems in Banach spaces are proved within the framework of differential inclusions. Unfortunately, these results require some hypotheses on the Banach space (for instance the Radon-Nikodym property for the dual space) that are not satisfied by the space of functions with bounded variation we consider in this paper. We thus tackle these issues in the present work and prove local and global existence of minimal geodesics in the space of BV 2 curves. We also show how similar techniques can be applied to the case of Sobolev metrics.

Contributions

Section 2 deals with the Finsler space of BV 2 -curves. Our main contribution is Theorems 2.15 proving the existence of a minimizing geodesic between two BV 2 -curves. We also explain how this result can be generalized to the setting of geometric curves (i.e. up to reparameterizations).

Section 3 extends these results to H k -curves with k 2 integer, which gives rise to Theorem 3.2 and Theorem 3.5. Our results are complementary to those presented in [START_REF] Michor | An overview of the Riemannian metrics on spaces of curves using the hamiltonian approach[END_REF] and [START_REF] Bruveris | Geodesic completeness for Sobolev metrics on the space of immersed plane curves[END_REF] where the authors show the geodesic completeness of curves endowed with the H k -metrics with k 2 integer. We indeed show that the exponential map is surjective.

Section 4 proposes a discretized minimal geodesic problem for BV 2 and Sobolev curves. We show numerical simulations for the calculation of stationary points of a regularized energy, which is smooth and thus allows one to use gradient descent schemes.

Geodesics in the Space of BV -Curves

In this section we define immersed parameterized BV 2 -curves and prove useful properties (Section 2.1). We also define a geodesic Finsler distance on that space and prove results of existence (Sections 2.2). Finally, we extend this framework to the case of geometric curves (Section 2.3).

The strategy is as follows: we first prove that the geodesic distance is locally equivalent to the distance defined by the ambient Banach norm and then prove existence using a convergent martingale to a minimum. Lastly, existence of geodesics between geometric curves is obtained thanks to a similar argument on the quotient space.

The Finsler Space of Parameterized BV 2 -curves

The following definition defines the space of immersed parameterized BV 2 -curves. This is the obvious generalization of the space of smooth immersed curves

Imm(S 1 , R 2 ) = c ∈ C ∞ (S 1 , R 2 ) : c ′ (x) = 0 ∀ x ∈ S 1 to the space of BV 2 (S 1 , R 2 ) curves, which are not necessarily smooth. We remind that f ∈ BV 2 (S 1 , R 2 ) (we identify S 1 with [0, 1]) if f ∈ W 1,1 (S 1 , R 2 )
and its second variation is finite:

|D 2 f |(S 1 ) = sup S 1 f (s) • g ′′ (s) dγ(s) : g ∈ C ∞ c (S 1 , R 2 ), g L ∞ (S 1 ,R) 1 < ∞ .
Then, the BV 2 -norm is defined as

f BV 2 (S 1 ,R 2 ) = f W 1,1 (S 1 ,R 2 ) + |D 2 f |(S 1 ) .
We also remind that BV 2 (S 1 , R 2 ) ⊂ W 1,∞ (S 1 , R 2 ) and, in particular, BV 2 -functions are continuous.

Definition 2.1 (BV 2 immersed curves). We consider the Banach space BV 2 (S 1 , R 2 ), where S 1 is the unit circle. For every γ ∈ BV 2 (S 1 , R 2 ) we consider the following property

0 / ∈ Conv(γ ′ (s + ), γ ′ (s -)) ∀ s ∈ S 1 (2.1)
where Conv denotes the convex envelope (a line segment) of the right and left limits (γ ′ (s -), γ ′ (s + )) of the derivative of γ at s.

In the following we define the space B of immersed BV 2 parameterized curves as the set of counterclockwise oriented curves belonging to the following set:

B = γ ∈ BV 2 (S 1 , R 2 ) : γ satisfies (2.1) .
(2.2)

Note that due to the existence of both clockwise and counter-clockwise parametrizations, the open set (see Proposition 2.5) defined in (2.2) is not connected. Remark 2.2 (Unit speed parameterization). Property (2.1) allows one to define the unit speed parameterization for γ:

s γ : S 1 → S 1 s γ (s) = 1 L (γ) s s 0 |γ ′ (t)| dt , s 0 ∈ S 1
where L (γ) denotes the length of γ defined as

L (γ) = S 1 |γ ′ (s)|ds .
Finally we point out that for every curve γ its unit speed parameterization is given by γ • ϕ γ where ϕ γ = s -1 γ .

Remark 2.3 (Reparameterizations). In the following we denotes by Diff(S 1 ) the set of homeomorphisms ϕ ∈ BV 2 (S 1 , S 1 ) such that ϕ -1 ∈ BV 2 (S 1 , S 1 ).

Note that any ϕ ∈ Diff(S 1 ) can be lifted (see [START_REF] Ghys | Groups acting on the circle[END_REF]) to a diffeomorphism φ of R. Therefore, Diff(S 1 ) can be interpreted as a subset of BV 2 (S 1 , S 1 ). Since the reparametrization can be chosen up to the choice of a basepoint, we can assume that lifts of reparametrizations can be written as Id + ( φ -Id) with φ -Id ∈ BV 2 (S 1 , R). This implies in particular that the weak topologies on reparametrizations correspond to the weak topologies on BV 2 (S 1 , S 1 ).

Remark 2.4. By Claim 3 p.218 in [START_REF] Evans | Measure theory and fine properties of functions[END_REF], we have the continuous embedding of BV in L ∞ (S 1 , R 2 ):

∀ u ∈ BV (S 1 , R 2 ), u L ∞ (S 1 ,R 2 ) u BV (S 1 ,R 2 ) . (2.3)
We use this continuous embedding to prove in the following proposition that B is an open set of BV 2 (S 1 , R 2 ).

Proposition 2.5. Let γ 0 ∈ B be parameterized by the unit speed parameterization. We have

γ ∈ BV 2 (S 1 , R 2 ) : γ -γ 0 BV 2 (S 1 ,R 2 ) L (γ 0 ) 2 ⊂ B , (2.4)
which proves that B is an open set of BV 2 (S 1 , R 2 ).

Proof. As γ 0 ∈ B is parameterized by the unit speed parameterization we have |γ ′ 0 (s)| = L (γ 0 ) for every s ∈ S 1 , so that we have

L (γ 0 ) = min s∈S 1 |γ ′ 0 (s)| . Now, by (2.3), we have u L ∞ (S 1 ,R 2 ) u BV (S 1 ,R 2 ) for every u ∈ BV (S 1 , R 2 ), so every curve γ ∈ BV 2 (S 1 , R 2 ) such that γ -γ 0 BV 2 (S 1 ,R 2 )
L (γ 0 ) 2 satisfies (2.1). Property (2.1) allows to generalize standard properties from the setting of smooth curves to BV 2 -curves. Note also that this condition implies that the support of the curve has no cusp points.

We can now generalize to BV 2 curves the usual properties of smooth curves.

T V γ (f ) = sup S 1 f (s) • dg dγ(s) (s) dγ(s) : g ∈ C ∞ c (S 1 , R 2 ), g L ∞ (S 1 ,R 2 ) 1 (2.6)
and

T V 2 γ (f ) = sup S 1 f (s) • d 2 g dγ(s) 2 (s) dγ(s) : g ∈ C ∞ c (S 1 , R 2 ), g L ∞ (S 1 ,R 2 ) 1 . (2.7)
We also remark that

f ′ L 1 (S 1 ,R 2 ) = df dγ L 1 (γ) .
Then the BV 2 (γ)-norm is defined as it follows

f BV 2 (γ) = S 1 |f ||γ ′ | ds + S 1 |f ′ | ds + T V 2 γ (f ) ∀ f ∈ BV 2 (γ) .
Finally, we remind that

f BV 2 (γ) = f • ϕ γ w BV 2 (S 1 ,R) , f w BV 2 (S 1 ,R) = L (γ) f L 1 (S 1 ,R) + f ′ L 1 (S 1 ,R) + 1 L (γ) |Df |(S 1 ) ∀f ∈ BV 2 (S 1 , R) . (2.8)
Moreover, analogously to Lemma 2.13 in [START_REF] Bruveris | Geodesic completeness for Sobolev metrics on the space of immersed plane curves[END_REF], we have the following Poincaré inequality

f L ∞ (S 1 ,R 2 ) 1 L (γ) S 1 f dγ + T V γ df dγ ∀ f ∈ BV (γ) .
(2.9)

Remark 2.8 (Weighted norms). Similarly to [START_REF] Bruveris | Geodesic completeness for Sobolev metrics on the space of immersed plane curves[END_REF], we could consider some weighted BV 2 -norms, defined as

f BV 2 (S 1 ,R 2 ) = a 0 f L 1 (S 1 ,R 2 ) + a 1 f ′ L 1 (S 1 ,R 2 ) + a 2 |D 2 f |(S 1
) where a i > 0 for i = 1, 2, 3. We can define the norm on the tangent space by the same constants.

One can easily verify that our results can be generalized to such a framework. In fact, previous norm is equivalent to the classic-one and the positive constants do not affect the bounds and the convergences properties that we prove in this work.

The following proposition proves that the tangent space to a given curve in B and BV 2 (S 1 , R 2 ) represent the same space of functions with equivalent norms. Proposition 2.9. Let γ ∈ B. The following properties hold:

1. The sets BV 2 (γ) and BV 2 (S 1 , R 2 ) coincide and their norm are equivalent. More precisely, there exist two positive constants M γ , m γ such that, for all f ∈ BV 2 (S 1 , R 2 )

m γ f BV 2 (S 1 ,R 2 ) f BV 2 (Γ) M γ f BV 2 (S 1 ,R 2 ) . (2.10) 2. We have f L ∞ (S 1 ,R 2 ) = f L ∞ (γ) . (2.11)
Proof. (Proof of (2.10)) We suppose that f is not equal to zero. In the case of the L 1 -norm on f , the result follows from (2.1) and the compactness of S 1 . The constants are given respectively by

M 0 γ = |γ ′ | L ∞ (S 1 ,R 2 ) m 0 γ = min s∈S 1 |γ ′ (s)|.
Moreover by a straightforward calculation one can easily see that the L 1 (γ) and L 1 (S 1 , R 2 )-norms of the first derivative coincide. So it is sufficient to obtain the result for the second variation of f ∈ BV 2 (γ).

By integration by part, we have

S 1 f (s) • d 2 g dγ 2 (s) (s) dγ(s) = S 1 f ′ |γ ′ | g ′ (s) ds
where we used the fact that dg dγ(s) = g ′ |γ ′ | . This implies in particular that

T V 2 γ (f ) = D f ′ |γ ′ | (S 1 ) . Since 1 |γ ′ | ∈ BV (S 1 , R 2 ) and BV (S 1 , R 2 ) is a Banach algebra, we get |D f ′ |γ ′ | |(S 1 ) |Df ′ |(S 1 )|D 1 |γ ′ | |(S 1 ). Now, as |Df ′ |(S 1 ) |D 2 f |(S 1
), we get the upper bound taking the constant

M 2 γ = D 1 |γ ′ | (S 1
) .

On the other hand, we have

S 1 f ′ g ′ (s) ds = S 1 df dγ(s) (s) dg dγ(s) (s) |γ ′ |dγ(s) so that |Df ′ |(S 1 ) = T V γ df dγ(s) |γ ′ | , which implies that |D 2 f |(S 1 ) T V γ (|γ ′ |)T V 2 γ (f ) |γ ′ | BV (S 1 ,R) T V 2 γ (f ) . (2.12)
Therefore, the result is proved by taking the constant

m 2 γ = 1 |γ ′ | BV (S 1 ,R 2 )
•

The lemma ensues setting

M γ = max {M 0 γ , M 2 γ } = max |γ ′ | L ∞ (S 1 ,R 2 ) , D 1 |γ ′ | (S 1 ) , m γ = min {m 0 γ , m 2 γ } = min min s∈S 1 |γ ′ (s)| , 1/ |γ ′ (•)| BV (S 1 ,R 2 ) .
(2.13)

(Proof of (2.11
)) It follows straightforwardly from (2.1) that the two measures are equivalent, i.e.

A ds = 0 ⇔ A dΓ(s) = 0
for every open set A of the circle.

Existence of Geodesics

In this section, we prove that geodesics for the induced Finsler metric exist for any given couple of curves in the same homotopy class. Definition 2.10 (Paths in B). For every γ 0 , γ 1 ∈ B, we define a path in B joining γ 0 and γ 1 as a function

Γ : t ∈ [0, 1] → Γ(t) ∈ B such that Γ(0) = γ 0 Γ(1) = γ 1 . (2.14)
For every γ 0 , γ 1 ∈ B, we denote P(γ 0 , γ 1 ) the class of all paths joining γ 0 , γ 1 and belonging to

H 1 ([0, 1], B). It holds in particular ∀ a.e. s ∈ S 1 , 1 0 Γ t (t)(s)dt = γ 1 (s) -γ 0 (s) (2.15)
where Γ t denotes the derivative of Γ with respect to t. In the following Γ ′ (t) denotes the derivative of the curves Γ(t) ∈ BV 2 (S 1 , R 2 ) with respect to s.

Definition 2.11 (Geodesic paths in B). For every path Γ we consider the following energy

E(Γ) = 1 0 Γ t (t) 2 BV 2 (Γ(t)) dt. (2.16)
The geodesic distance between γ 0 and γ 1 is denoted by d(γ 0 , γ 1 ) and defined by

d 2 (γ 0 , γ 1 ) = inf {E(Γ) : Γ ∈ P(γ 0 , γ 1 )} .
(2.17)

A geodesic between γ 0 and γ 1 is a path Γ ∈ P(γ 0 , γ 1 ) such that

E( Γ) = d 2 (γ 0 , γ 1 ).
Note that because of the lack of smoothness of the BV 2 norm over the tangent space, it is not possible to define an exponential map. Geodesics should thus be understood as minimal geodesics, and are thus homotopies defined using the variational problem (2.17). Recall that the existence of (minimizing) geodesics is not granted in infinite dimension. When the metric is Riemannian and even if the manifold is geodesically complete, the existence of minimizers is not guaranteed since the Hopf-Rinow theorem does not hold in infinite dimension, see Section 1.1.

Remark 2.12 (Time-reparameterization and geodesic energy). We point out that analogously to Remark 2.2 we can reparameterize every non-trivial homotopy Γ (i.e. satisfying E(Γ) = 0) with respect to the time-unit speed parameterization, defined as the inverse of the following parameter:

t Γ : [0, 1] → [0, 1] ∀ t ∈ [0, 1], t Γ (t) = 1 E 1 (Γ) t 0 Γ τ (τ ) BV 2 (Γ(τ )) dτ ,
where

E 1 (Γ) = 1 0 Γ τ (τ ) BV 2 (Γ(τ )) dτ .
In particular, if Γ τ (τ ) BV 2 (Γ(τ )) = 0 for every t, by reparameterizing the homotopy with respect to previous parameter we obtain a parameterization with constant velocity

Γ t (t) BV 2 (Γ(t)) = E 1 (Γ) ∀ t ∈ [0, 1] .
(2.18)

In the general case, for every ε > 0, we can always prove the existence of a time-parameterization such that

Γ t (t) BV 2 (Γ(t)) E 1 (Γ) + ε ∀ t ∈ [0, 1] .
This implies in particular that E 1 (Γ) = E(Γ • t -1 Γ ) for every path Γ. Then, the minimizers of E 1 coincide with the minimizers of E reparameterized with respect to the parameter t Γ . This justifies the definition of the geodesic energy E by a L 2 -norm. We refer to [START_REF] Younes | Shapes and Diffeomorphisms[END_REF] (see Theorem 8.18 and Corollary 8.19, p.175) for more details.

We prove now that constants m Γ(t) and M Γ(t) defined in (2.13) are uniformly bounded on minimizing paths.

To this end we need the following lemma.

Lemma 2.13. Let Γ ∈ P(γ 0 , γ 1 ). Then the following properties hold:

1. The function t → g(t) = Γ ′ (t) L ∞ (S 1 ,R 2 )
belongs to C([0, 1], B), so in particular it admits a maximum and a positive minimum on [0, 1]. Moreover min

t∈[0,1] min s∈S 1 |Γ ′ (t)(s)| > 0 .
2. For every t ∈ [0, 1] we have

L (γ 0 )e -E(Γ) L (Γ(t)) L (γ 0 )e E(Γ) (2.19)
and for all s ∈ S 1 , (min

s∈S 1 |γ ′ 0 (s)|)e -E(Γ) |Γ ′ (t)(s)| γ ′ 0 L ∞ (S 1 ,R 2 ) e E(Γ) .
(2.20)

Proof. 1. By Definition 2.11, every Γ ∈ P(γ 0 , γ 1 ) belongs to

H 1 ([0, 1], B) so in particular to C([0, 1], B). Now, as BV 2 (S 1 , R 2 ) is embedded in L ∞ (S 1 , R 2 )
, we get the continuity of g. Moreover, from (2.1) and the compactness of S 1 , it follows that

min s∈S 1 |Γ ′ (t)(s)| > 0, ∀ t ∈ [0, 1]
which implies that min

t∈[0,1] g(t) > 0.
The second statement is a straightforward consequence of (2.1)

and the compactness of [0, 1]. This implies in particular that functions t → L (Γ(t)) and t → |Γ ′ (t)(s)| (for every s ∈ S 1 ) are continuous.

2. By Remark 2.12 we can suppose that the time-velocity is constant. We have

∂L (Γ(t)) ∂t = S 1 Γ ′ t (t) |Γ ′ (t)| , Γ ′ (t) ds dΓ t (t) dΓ(t) L 1 (Γ(t)) L (Γ(t)) ,
and, as dΓt(t) dΓ(t) has null average, by (2.9), we have

dΓ t (t) dΓ(t) L ∞ (S 1 ,R 2 ) E(Γ) . This implies ∂ log(L (Γ(t))) ∂t E(Γ) ∀ t ∈ [0, 1],
and, by integrating in time between 0 and t, we get

L (γ 0 )e -E(Γ) L (Γ(t)) L (γ 0 )e E(Γ) .
Similarly we have

∂|Γ ′ (t)(s)| ∂t = Γ ′ t (t) |Γ ′ (t)| , Γ ′ (t)(s) dΓ t (t)(s) dΓ(t) L ∞ (S 1 ,R 2 ) |Γ ′ (t)(s)|
and, as above, we get

∂ log(|Γ ′ (t)(s)|) ∂t E(Γ), ∀ s ∈ S 1 ∀ t ∈ [0, 1].
The result follows by integrating in time.

Proposition 2.14. Let γ 0 ∈ B and we consider the geodesic ball

B d (γ 0 , r) = {γ ∈ B | d(γ 0 , γ) < r} .
Then constants m γ and M γ defined in (2.13) verify

C 1 e -C 0 r 2 m γ M γ C 2 e C 0 r 2 ∀ γ ∈ B d (γ 0 , r) (2.21)
where C 0 , C 1 , C 2 are three positive constants depending on γ 0 (see (2.24) and (2.27)).

Proof. Given γ ∈ B, we show that

C 1 e -C 0 E(Γ) m Γ(t) M Γ(t) C 2 e C 0 E(Γ) ∀ t ∈ [0, 1]
for every Γ ∈ P(γ 0 , γ). Then, for every γ ∈ B d (γ 0 , r), the result follows from previous inequality by considering a path Γ ∈ P(γ 0 , γ) such that E(Γ) r 2 and setting t = 1.

Because of (2.20), we have

(min s∈S 1 |γ ′ 0 (s)|)e -E(Γ) min s∈S 1 |Γ ′ (t)(s)| |Γ ′ (t)| L ∞ (S 1 ,R 2 ) γ ′ 0 L ∞ (S 1 ,R 2 ) e E(Γ) .
(2.22)

for every t ∈ [0, 1]. By setting f (t) = Γ ′ (t) in (2.
12) and by a time-reprameterization, we get

|D 2 Γ ′ (t)|(S 1 ) |Γ ′ (t)| BV (S 1 ,R) E(Γ) . (2.23) Thus Γ ′ (t) -γ ′ 0 BV (S 1 ,R) t 0 Γ ′ τ BV (S 1 ,R) dτ = t 0 [ Γ ′ τ L 1 (S 1 ,R 2 ) + |D 2 Γ τ |(S 1 )]dτ
and, by (2.23) and (2.18), we have

Γ ′ (t) -γ ′ 0 BV (S 1 ,R) E(Γ) + t 0 |Γ ′ (t)| BV (S 1 ,R) E(Γ)dτ .
In particular, by the chain rule for BV -functions ([1]: Theorem 3.96 p. 189), we have

|Γ ′ (t)| BV (S 1 ,R) C 0 Γ ′ (t) BV (S 1 ,R)
where

C 0 = max    1, 1 min s∈S 1 |γ ′ 0 (s)|    . (2.24) Then |Γ ′ (t)| BV (S 1 ,R) C 0 γ ′ 0 BV (S 1 ,R) + E(Γ) + t 0 |Γ ′ (t)| BV (S 1 ,R) E(Γ)dτ
and by the Gronwall's inequality we get

|Γ ′ (t)| BV (S 1 ,R) C 0 ( γ ′ 0 BV (S 1 ,R) + E(Γ))e C 0 E(Γ) . (2.25)
From previous relationship implies that

e -C 0 E(Γ) C 0 ( γ ′ 0 BV (S 1 ,R) + E(Γ)) 1 |Γ ′ (t)| BV (S 1 ,R 2 ) D 1 |Γ ′ (t)| (S 1 ) C 0 ( γ ′ 0 BV (S 1 ,R) + E(Γ)) min s∈S 1 |γ ′ 0 (s)| 2 e C 0 E(Γ) (2.26)
where we used the chain rule for BV -functions to prove the second inequality. The result follows from (2.22) and (2.26) by setting

C 1 = min min s∈S 1 |γ ′ 0 (s)| , 1 C 0 ( γ ′ 0 BV (S 1 ,R) + E(Γ)) , C 2 = max    γ ′ 0 L ∞ (S 1 ,R 2 ) , C 0 ( γ ′ 0 BV (S 1 ,R) + E(Γ)) min s∈S 1 |γ ′ 0 (s)| 2    .
(2.27)

We can now prove an existence result for geodesics.

Theorem 2.15 (Existence). Let γ 0 , γ 1 ∈ B such that d(γ 0 , γ 1 ) < ∞. Then, there exists a geodesic between γ 0 and γ 1 .

Proof. Let {Γ h } h ⊂ P(γ 0 , γ 1 ) be a minimizing sequence for E. Without loss of generality we can suppose sup h E(Γ h ) < +∞. We also remark that, from the previous lemma, it follows

0 < inf h inf t∈[0,1] m Γ h (t) < sup h sup t∈[0,1] M Γ h (t) < +∞ .
Step 1: Definition of a limit path. For every n > 1 we consider the dyadic decomposition of [0, 1] given by the intervals

I n,k = [ k 2 n , k + 1 2 n [ for k ∈ [0, 2 n -1] (2.28)
and, for every t ∈ [0, 1] we define

f h n (t) = 2 n I n,k Γ h τ (τ ) dτ,
where I n,k is the interval containing t. Remark that, for every n and h, f m Γ h (t) > 0 and, by (2.10), we get

h n : [0, 1] → BV 2 (S 1 , R 2 ) is piecewise-constant and 1 0 f h n (τ ) dτ = 1 0 Γ h t (t) dt = Γ(1) -Γ(0) . ( 2
f h n (t) 2 BV 2 (S 1 ,R 2 ) 2 n 1 0 Γ h t (t) 2 BV 2 (Γ(t)) m Γ(t) 2 n m E(Γ h ) ∀ t ∈ [0, 1] . (2.30)
So, by a diagonal extraction, we can take a subsequence (not relabeled) and a piecewise-constant function

f ∞ n : [0, 1] → BV 2 (S 1 , R 2 ) such that ∀ (n, k), f h n (t) * -BV 2 ⇀ f ∞ n (t), ∀ t ∈ [0, 1] and 1 0 f ∞ n (t) 2 BV 2 (S 1 ,R 2 ) dt lim inf h→∞ 1 0 f h n (t) 2 BV 2 (S 1 ,R 2 ) dt .
Moreover we can write

I n,k = [k2 -n , (2k + 1)2 -n-1 [∪[(2k + 1)2 -n-1 , (k + 1)2 -n [ and f h n+1 (t) = 2 n+1 I n+1,2k Γ h t (t)dt ∀ t ∈ [k2 -n , (2k + 1)2 -n-1 [ f h n+1 (t) = 2 n+1 I n+1,2k+1 Γ h t (t)dt ∀ t ∈ [(2k + 1)2 -n-1 , (k + 1)2 -n [ therefore I n,k f h n+1 (t)dt = I n,k Γ h t (t)dt f h n (t) = 2 n I n,k f h n+1 (t)dt ∀ t ∈ I n,k .
Then, by the Dominated Convergence Theorem, we get

f ∞ n (t) = 2 n I n,k f ∞ n+1 (t)dt (2.31) which implies that {f ∞ n } is a BV 2 (S
1 0 f ∞ n (t) 2 BV 2 (S 1 ,R 2 ) dt lim inf h→∞ 1 0 f h n (t) 2 BV 2 (S 1 ,R 2 ) dt lim inf h→∞ E(Γ h ) m . Now, as BV 2 (S 1 , R 2 ) is embedded in H 1 (S 1 , R 2 ), this implies that {f ∞ n } is a bounded martingale in L 2 ([0, 1], H 1 (S 1 , R 2 )) so,
. 215), f ∞ n (t) → f (t) in H 1 (S 1 , R 2 )
for almost every t. Note also that, as f ∞ n ∈ BV 2 (S 1 , R 2 ) and the second variation is lower semicontinuous with respect to the

W 1,1 (S 1 , R 2 )-convergence, we actually get f ∈ L 2 ([0, 1], BV 2 (S 1 , R 2 )).
We can now define a candidate to be a minimum of E by setting

Γ ∞ (t) = t 0 f (τ ) dτ + Γ(0), ∀ t ∈ [0, 1] . (2.32)
We can easily verify that

Γ ∞ ∈ H 1 ([0, 1], BV 2 (S 1 , R 2
)) and that Γ ∞ verifies (2.15). In fact, by the Dominated Convergence Theorem and (2.29), we have

1 0 f (τ ) dτ = lim n→∞ 1 0 f ∞ n (τ ) dτ = lim n→∞ lim h→∞ 1 0 f h n (τ ) dτ = Γ(1, •) -Γ(0, •) .
This implies in particular that Γ ∞ verifies (2.14). So we get Γ ∞ ∈ P(γ 0 , γ 1 ).

Step 2: Γ ∞ is a geodesic path. We now prove that Γ h (t) → Γ ∞ (t) in W 1,1 (S 1 , R 2 ) for every t. For that we denote by Γ ∞ n and Γ h n the paths defined by f ∞ n and f h n through (2.32). Now, by definition of f h n and a straightforward calculation, we get that

Γ h (t) -Γ h n (t) W 1,1 (S 1 ,R 2 ) is small for n large enough. Moreover, as f h n (t) * -BV 2 ⇀ f ∞ n (t) for every t and f ∞ n → f in L 2 ([0, 1], BV 2 (S 1 , R 2 )) we have Γ ∞ n (t) -Γ h n (t) W 1,1 (S 1 ,R 2 ) → 0 , as h → ∞ and that Γ ∞ n (t) -Γ ∞ (t) W 1,1 (S 1 ,R 2 )
is small for n large enough. This implies that

Γ h (t) -Γ ∞ (t) W 1,1 (S 1 ,R 2 ) → 0 .
(2.33)

By the same arguments we can show that

Γ h t (t) -Γ ∞ t (t) W 1,1 (S 1 ,R 2 ) → 0 , ∀ t ∈ [0, 1] , (2.34)
which implies in particular that

{Γ h t (t)} h is bounded in BV 2 (S 1 , R 2 ) for almost every t. Now, as Γ h (t) converges in W 1,1 (S 1 , R 2 ) towards Γ ∞ (t) ∈ BV 2 (S 1 , R 2 )
, the unit speed parameterizations at the time t, denoted respectively by ϕ h (t) and ϕ ∞ (t), also converge in W 1,1 (S 1 , S 1 ). Moreover, for a fixed time t, we have

Γ h t (t) 2 BV 2 (Γ h (t)) = Γ h t • ϕ h (t) 2 BV 2 (S 1 ,R 2 ) . Since {Γ h t (t)} h is bounded in BV 2 (S 1 , R 2
) and the two terms involved in the composition converge in W 1,1 (S 1 , R 2 ), we have

Γ h t • ϕ h (t) -Γ h t • ϕ ∞ (t) W 1,1 (S 1 ,R 2 ) Γ h t BV 2 (S 1 ,R 2 ) ϕ h (t) -ϕ ∞ (t) W 1,1 (S 1 ,R 2 ) Γ h t • ϕ ∞ (t) -Γ ∞ t • ϕ ∞ (t) W 1,1 (S 1 ,R 2 ) C Γ h t -Γ ∞ t W 1,1 (S 1 ,R 2 )
where

C = max {1, (ϕ ∞ -1 ) ′ L ∞ (S 1 ,R 2 ) } .

This implies in particular that

Γ h t • ϕ h (t) W 1,1 (S 1 ,R 2 ) → Γ ∞ t • ϕ ∞ (t) . (2.35)
Now we remark that, because of the W 1,1 -convergence, we have L (Γ h (t)) → L (Γ(t)). Moreover, the second variation is lower semi-continuous with respect to the W 1,1 -convergence. Then, by (2.8), for every t we get

Γ ∞ t (t) BV 2 (Γ ∞ (t)) = Γ ∞ t • ϕ ∞ (t) w BV 2 (S 1 ,R 2 ) lim inf h→∞ Γ h t • ϕ h (t) w BV 2 (S 1 ,R 2 ) = lim inf h→∞ Γ h t (t) BV 2 (Γ h (t)) .
(2.36)

By integrating the previous inequality and using Fatou's Lemma we get that Γ ∞ minimizes E, which ends the proof.

Remark 2.16. In order to get the semicontinuity's inequality (2.36), we actually just would need the convergence in (2.35) with respect to the BV 2 -weak topology. We point out that it is very difficult to characterize such a topology, which explains the choice of the weak-* topology (i.e. we look at BV 2 (S 1 , R 2 ) as a dual Banach space) in the previous proof. Moreover, the martingale approach allows one to get strong convergence in W 1,1 without applying any strong-compactness criterion for Sobolev spaces. This is a key point of the proof because the BV 2 -norm is semicontinuous with respect to the strong W 1,1 -topology.

Inspired by the previous proof we can define the following topology on H 1 ([0, 1], B): Definition 2.17 (σ-topology). Let {Γ h } h ⊂ H 1 ([0, 1], B) and Γ ∈ H 1 ([0, 1], B). We say that Γ h converges to Γ with respect to the σ-topology (denoted by Γ h σ → Γ) if there exists a sequence of piecewise constant functions {f ∞ n } such that:

(i) (BV 2 -* weak convergence). Let {I n,k } n,k the collection of the intervals giving the dyadic decomposition of [0, 1] defined in (2.28), then the sequence

f h n (t) = 2 n I n,k Γ h τ (τ ) dτ verifies ∀ (n, k) f h n (t) * -BV 2 ⇀ f ∞ n (t) ∀ t ∈ [0, 1] as h → ∞; (ii) (Martingale convergence). We have lim n→∞ f ∞ n -Γ t L 2 ([0,1],H 1 (S 1 ,R 2 )) = 0 .
Then, the proof of Theorem 2.15 proves actually the following result:

Theorem 2.18. The following properties hold:

(i) Every bounded set of H 1 ([0, 1], B) is sequentially compact with respect to σ-topology and the σ-convergence implies the strong convergence in H 1 ([0, 1], W 1,1 (S 1 , R 2 ));

(ii) The energy E is lower semicontinuous with respect to the σ-topology.

Remark 2.19. The proof of Theorem 2.15 can now be presented as it follows. We can suppose that

{Γ h } ⊂ H 1 ([0, 1], B) with sup h E(Γ h ) < ∞. Then {Γ h } is uniformly bounded in H 1 ([0, 1], B
) and, by points (i) and (ii) of previous theorem, energy E reaches its minimum on H 1 ([0, 1], B).

Geodesic Distance Between Geometric Curves

Theorem 2.15 shows the existence of a geodesic between any two parameterized curves in B. We are interested now in defining a geometric distance between geometric curves (i.e., up to parameterization).

The space of geometric curves is defined as B/Diff(S 1 ). For every γ ∈ B its equivalence class (called also geometric curve) is denoted by [γ].

Next proposition defines a distance on the set of curves belonging to B up to reparameterization.

Proposition 2.20. The Procrustean dissimilarity measure defined by

D([γ 0 ], [γ 1 ]) = inf {d(γ 0 • ϕ, γ 1 • ψ) : ϕ, ψ ∈ Diff(S 1 )} (2.37)
is a distance on the set of B-curves up to reparameterization.

Proof. The function D is symmetric, non-negative and it is equal to zero if

[γ 0 ] = [γ 1 ].
Remark also that, the distance d is invariant under reparameterization, so that

d(γ 0 , γ 1 ) = d(γ 0 • ϕ, γ 1 • ϕ), ∀ ϕ ∈ Diff(S 1 ) . (2.38)
Then from the invariance (2.38) it follows that for every ϕ 1 , ϕ 2 , ϕ 3 ∈ Diff(S 1 ) and γ 1 , γ 2 , γ 3 ∈ B we have

d(γ 1 • ϕ 1 , γ 2 • ϕ 2 ) d(γ 1 • ϕ 1 , γ 3 • ϕ 3 ) + d(γ 3 • ϕ 3 , γ 2 • ϕ 2 ) = d(γ 1 • ϕ 1 • ϕ -1 3 , γ 3 ) + d(γ 3 , γ 2 • ϕ 2 • ϕ - 1
3 ) which implies that the triangle inequality is satisfied for D.

We prove now that D(

[γ 0 ], [γ 1 ]) = 0 implies that [γ 0 ] = [γ 1 ]
. We assume that γ 0 is parameterized by the unit speed parameterization (this is possible because of the invariance of d under reparameterization). So there exists a sequence ϕ h of reparameterizations such that

d(γ 0 , γ 1 • ϕ h ) 1 h .
By Lemma 2.14, minimal energies E(Γ h ) are uniformly bounded and

C = inf h inf t m Γ h (t) > 0.
Then, similarly to (2.30), we get

γ 0 -γ 1 • ϕ h 2 BV 2 (S 1 ,R 2 ) 1 Ch 2
for h large enough. Thus, the support of γ 0 and γ 1 coincide which implies, by Proposition 2.6, that there exists ϕ ∈ Diff(S 1 ) such that γ 0 = γ 1 • ϕ.

Next theorem proves a existence result for geodesics. Proof. In the following we denoted by γ 0 and γ 1 the parameterizations by the unit speed parameterization. Because of the invariance (2.38) we can write

D([γ 0 ], [γ 1 ]) = inf {d(γ 0 , γ 1 • ψ) : ψ ∈ Diff(S 1 )}.

We consider a sequence {ψ

h } h ⊂ Diff(S 1 ) such that d(γ 0 , γ 1 • ψ h ) → D([γ 0 ], [γ 1 ]
) and we suppose that sup h d(γ 0 , γ 1 • ψ h ) < ∞. By Theorem 2.15, for every h, there exists a geodesic Γ h between γ 0 and γ

1 • ψ h and d 2 (γ 0 , γ 1 • ψ h ) = E(Γ h ). We show that there exists ψ ∞ ∈ Diff(S 1 ) such that D([γ 0 ], [γ 1 ]) = d(γ 0 , γ 1 • ψ ∞ ).
By the same arguments used in the proof of Theorem 2.15, we can define (see Step 1) a path

Γ ∞ ∈ H 1 ([0, 1], BV 2 (S 1 , R 2 )) such that 1 0 Γ h t (t)(s)dt → 1 0 Γ ∞ t (t)(s)dt , (2.39)
and (see Step 2)

Γ h (t) W 1,1 (S 1 ,R 2 ) -→ Γ ∞ (t), ∀ t ∈ [0, 1] (2.40) Γ h t (t) W 1,1 (S 1 ,R 2 ) -→ Γ ∞ t (t), ∀ t ∈ [0, 1]. (2.41)
Now, because of (2.15), we have

1 0 Γ h t (t)(s)dt = γ 1 • ψ h (s) -γ 0 (s) ∀ s ∈ S 1 . (2.42) As {γ 1 • ψ h } is bounded in BV 2 (S 1 , R 2
) there exists a subsequence (not relabeled) converging BV 2 -* weakly towards some curve having the same support that γ 1 . So, by Proposition 2.6, there exists ψ ∞ ∈ Diff(S 1 ) such that

γ 1 • ψ h * -BV 2 (S 1 ,R 2 ) ⇀ γ 1 • ψ ∞ . Now, as Γ h (0) = γ 0 and Γ h (1) = γ 1 • ψ h , from (2.40), it follows Γ ∞ (0) = γ 0 Γ ∞ (1) = γ 1 • ψ ∞ which implies that Γ ∞ ∈ P(γ 0 , γ 1 • ψ ∞ ).
Moreover, denoting by ϕ h and ϕ ∞ the unit speed parameterization of Γ h (t) and Γ ∞ (t) respectively, by (2.40) we have

ϕ h → ϕ ∞ in W 1,1 (S 1 , R 2 ).
Then, similarly to (2.36), we get

Γ ∞ t (t) BV 2 (Γ ∞ (t)) lim inf h→∞ Γ h t (t) BV 2 (Γ h (t)) .
By integrating the previous inequality and using Fatou's Lemma we get

E(Γ ∞ ) lim h→∞ E(Γ h ) = lim h→∞ d 2 (γ 0 , γ 1 • ψ h ) = D 2 ([γ 0 ], [γ 1 ]) , which implies that D 2 ([γ 0 ], [γ 1 ]) = d 2 (γ 0 , γ 1 • ψ ∞ ) = E(Γ ∞ ).

Geodesics in the Space of Sobolev Curves

In this section, we study the geodesic boundary value problem in the class of curves belonging to H k (S 1 , R 2 ) with k 2 integer.

We remind that

H k (S 1 , R 2 ) ⊂ C 1 (S 1 , R 2 ), ∀ k 2 . (3.1)
In this framework, the proof of existence of geodesics is simpler, since H k (S 1 , R 2 ) being a Hilbert space, the weak topology can be used instead of the BV 2 -*weak one.

We define the class of the parameterized H k -curves as follows.

Definition 3.1 (H k -curves). We define H k as the class of counterclockwise oriented curves belonging to H k (S 1 , R 2 ) (k 2 integer) and verifying (2.1). For every γ ∈ H k the unit speed parameterization ϕ γ can be defined as in Remark 2.2.

From (3.1) it follows that there exists a constant C such that

γ ′ L ∞ (S 1 ,R 2 ) C γ H k (S 1 ,R 2 ) , ∀ γ ∈ H k . (3.2)
Moreover, it is easy to verify that H k is an open set of H k (S 1 , R 2 ). In fact, similarly to the BV 2case, for every γ 0 ∈ H k , which is parameterized by the unit speed parameterization, (3.

2) implies that γ ∈ H k : γ -γ 0 H k (S 1 ,R 2 ) L (γ 0 ) 2C ⊂ H k . (3.3)
We point out that local properties of reparameterization proved in Proposition 2.6 can be easily generalized to H k -curves.

As in the previous section we define the space H k (γ) as the space H k (S 1 , R 2 ), where integration and derivation are performed with respect to the measure dγ = |γ ′ |ds. Concerning the tangent space, for any γ ∈ H k , we set

T γ H k = H k (γ).
As in the previous section, for every γ 0 , γ 1 ∈ H k we consider the class of paths Γ ∈ H 1 ([0, 1], H k ) such that Γ(0) = γ 0 and Γ(1) = γ 1 . The energy of a path is defined as

E(Γ) = 1 0 Γ t (t) 2 H k (Γ(t)) dt
and the geodesic distance d(γ 0 , γ 1 ) is defined accordingly (see Definition 2.11). Moreover, Lemma 5.1 in [START_REF] Bruveris | Geodesic completeness for Sobolev metrics on the space of immersed plane curves[END_REF] proves the equivalence of the norms of H k (S 1 , R 2 ) and H k (γ). Such a result states that, for every γ 0 ∈ H k , there exists a constant C = C(γ 0 , D) > 0 such that

1 C f H k (S 1 ,R 2 ) f H k (γ) C f H k (S 1 ,R 2 ) (3.4)
for every γ ∈ H k such that d(γ 0 , γ) < D. This proves in particular that the constant C is uniformly bounded on every geodesic ball. Finally, in order to compare the H k -norm after reparameterization, we remark that

f H k (γ) = f • ϕ γ w H k (S 1 ,R 2 ) ( f w H k (S 1 ,R 2 ) ) 2 = L (γ) 2 f 2 L 2 (S 1 ,R 2 ) + L (γ) 2(1-k) f (k) 2 L 2 (S 1 ,R 2 ) , ∀ f ∈ H k (S 1 , R 2 ). (3.5)
We prove now an existence result for geodesics in the Sobolev framework. Theorem 3.2 (Existence). Let γ 0 , γ 1 ∈ H k such that d(γ 0 , γ 1 ) < ∞. Then, there exists a geodesic between γ 0 and γ 1 .

Proof. Because of (3.4) there exists a constant M > 0 such that

1 0 Γ h t (t) 2 H k (S 1 ,R 2 ) dt 1 0 M Γ h t (t) 2 H k (Γ(t)) dt M E(Γ) . (3.6)
This implies that

Γ h t is uniformly bounded in L 2 ([0, 1], H k (S 1 , R 2 )
) and, because of the boundary conditions, that

Γ h is uniformly bounded in H 1 ([0, 1], H k (S 1 , R 2 )).
Therefore there exists a subsequence of Γ h that weakly converges in H 1 ([0, 1], H k (S 1 , R 2 )). Since the embedding

H 1 ([0, 1], H k (S 1 , R 2 )) ⊂ C([0, 1], H k-1 (S 1 , R 2 )) is compact, this subsequence (not relabeled) converges to a path Γ ∞ ∈ L 2 ([0, 1], C(S 1 , R 2 )), Γ h → Γ ∞ in C([0, 1], H k-1 (S 1 , R 2 )) .

This proves in particular that

Γ h (t) W 1,1 (S 1 ,R 2 ) → Γ ∞ (t), ∀ t ∈ [0, 1] and Γ h t (t) H k (S 1 ,R 2 ) ⇀ Γ ∞ t (t), ∀ t ∈ [0, 1] . Now, as Γ h (t) converges in W 1,1 (S 1 , R 2 ) towards Γ ∞ (t)
, the unit speed parameterizations at the time t, denoted respectively by ϕ h (t) and ϕ ∞ (t), also converge in W 1,1 (S 1 , S 1 ). Thus, by the same arguments used for (2.35

) (Γ h t • ϕ h (t) being bounded in H s (S 1 , R 2
)), we have

Γ h t • ϕ h (t) H k (S 1 ,R 2 ) ⇀ Γ ∞ t • ϕ ∞ (t), ∀ t ∈ [0, 1] .
Now, because of (3.5), we have

Γ h t (t) H k (Γ(t)) = Γ h t • ϕ h (t) w H k (S 1 ,R 2 )
. Moreover, because of the strong convergence of the unit speed parameterizations we get L (Γ h (t)) → L (Γ ∞ (t)) for every t. Then, for every t, we get

Γ ∞ t (t) w H k (Γ(t)) = Γ ∞ t • ϕ ∞ (t) w H k (S 1 ,R 2 ) lim inf h→∞ Γ h t • ϕ h (t) w H k (S 1 ,R 2 ) = lim inf h→∞ Γ h t (t) H k (Γ(t))
.

By integrating the previous inequality and using Fatou's Lemma we get that Γ ∞ minimizes E and the theorem ensues.

In [START_REF] Bruveris | Geodesic completeness for Sobolev metrics on the space of immersed plane curves[END_REF], the authors prove (Theorem 1.1) that the space of immersed curves is geodesically complete with respect to the H k -metrics (k 2 integer). Since H k -metrics (k 2 integer) are smooth Riemannian metrics, minimizing geodesics are given locally by the exponential map. Moreover, from Theorem 3.2, we have the existence of minimal geodesics (in our variational sense) between any two points. Therefore, the minimizing curve found by our variational approach coincides with an exponential ray. Thus, we have the following corollary.

Corollary 3.3 (Surjectivity of the exponential map). The exponential map on H k for k 2 integer is defined for all time and is surjective.

The so-called Fréchet or Kärcher means often used in imaging are a particular case of minimizers of the distance to a closed subset. The surjectivity of the exponential map enables the use of [START_REF] Azagra | Proximal calculus on Riemannian manifolds[END_REF]Theorem 3.5] which proves that the projection onto a closed subset is unique on a dense subset. A direct theoretical consequence of this surjectivity result is the following result. Proposition 3.4. Let k 2 be an integer. For any integer n 1, there exists a dense subset D ⊂ H n k , such that the Kärcher mean associated with any (γ 1 , . . . , γ n ) ∈ D, defined as a minimizer of

min γ∈H k n i=1 d(γ, γ i ) 2 , (3.7)
is unique.

Proof. Let S be the diagonal in

H n k . The set S is a closed subset of H k × . . . × H k n times
. In [5, Theorem 3.5] the authors prove that the set of minimizers of arg min y∈S d(x, y) is a singleton for a dense subset in H n k . Analogously to the BV 2 -case we can define a distance D between two geometric curves (see Proposition 2.20). By the same arguments used to prove Theorem 2.21 (it suffices to use the H kweak convergence instead of the BV 2 -weak* one) we obtain the following result:

Theorem 3.5 (Geometric existence). Let γ 0 γ 1 ∈ H k such that D([γ 0 ], [γ 1 ]) < ∞. Then there exists a minimizer of D([γ 0 ], [γ 1 ]).

Numerical Computations of Geodesics

In this section we discretize and relax Problem (2.17) in order to approximate numerically geodesic paths. Note that since we use a gradient descent to minimize a discretized and relaxed energy, the resulting optimal discrete homotopy aims at approximating stationary points of the geodesic energy, and that these homotopies cannot be guaranteed to be globally minimizing geodesics.

Penalized Boundary Condition at t = 1

To obtain a simple numerical scheme, we first relax the constraint Γ(1) = γ 1 by adding at the energy E a data fidelity term H(Γ(1), γ 1 ) taking into account the deviation between Γ(1) and γ 1 . In the following we make use of the H functional defined in [START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF] (equation 5.4).

Such a functional is defined as the following distance between two curves

H(γ, λ) 2 = T (γ, γ) + T (λ, λ) -2T (γ, λ) , ∀γ, λ ∈ B where T (γ, λ) = S 1 S 1 n γ (s) • n λ (t) k (γ(s), λ(t)) dγ(s)dλ(t) with k(v, w) = e -v-w 2 2σ 2 + e -v-w 2 2δ 2 , ∀v, w ∈ R 2 .
Here (σ, δ) are positive constant that should adapted depending on the targeted application. This functional H was initially proposed in [START_REF] Vaillant | Surface matching via currents[END_REF] as a norm on a reproducing Hilbert space of currents. It can be shown to be a metric on the space of geometric curves, which explains why it is a good candidate to enforce approximately the boundary constraint at time t = 1. We remind that H is continuous with respect to strong topology of W 1,1 (S 1 , R 2 ). We refer to [START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF] for its properties and its discretization using finite elements.

Then, given two curves γ 0 , γ 1 ∈ B, we consider the following problem

min {F (Γ) : Γ ∈ H 1 ([0, 1], B) , Γ(0) = γ 0 } F (Γ) = H(Γ(1), γ 1 ) + E(Γ). (4.1)
To allows for more flexibility in the numerical experiments, we introduce a weighted BV 2 norm in the definition (2.16) of the energy E. Given some positive weights (λ 0 , λ 1 , λ 2 ) ∈ (R + ) 3 , we consider in this section

E(Γ) = 1 0 Γ t (t) BV 2 (Γ(t)) dt , (4.2)
where, for all γ ∈ B and v ∈ T γ B,

v BV 2 (γ) = S 1 λ 0 |v(s)| + λ 1 dv dγ (s) + λ 2 d 2 v dγ 2 (s) dγ(s).

Regularized Problem and Γ-convergence

The energy minimized in (4.1) is both non-smooth and non-convex. In order to compute stationary points using a gradient descent scheme, we further relax this problem by smoothing the R 2 -norm used to caclulate the BV 2 -norm. This approach is justified by a Γ-convergence result in Theorem 4.1.

The energy E is regularized as

E ε (Γ) = 1 0 Γ t (t) ε BV 2 (Γ(t)) dt . (4.3)
where ε > 0 controls the amount of smoothing, and the smoothed BV 2 -norm is defined, for γ ∈ B and v ∈ T γ B, as

v ε BV 2 (γ) = S 1 λ 0 |v(s)| ε + λ 1 dv dγ (s) ε |γ ′ (s)| ε ds + λ 2 T V 2 γ (v), where ∀x ∈ R 2 , |x| ε = |x| 2 + ε 2 .
A regularization of the second total variation is given by (4.10) in the case of the finite element space. The initial problem (4.1) is then replaced by

min {F ε (Γ) : Γ ∈ H 1 ([0, 1], B) , Γ(0) = γ 0 } F ε (Γ) = H(Γ(1), γ 1 ) + E ε (Γ) (4.4)
This smoothing approach is justified by the following theorem Moreover if {Γ ε } ε is a sequence of minimizers of F ε then there exists a subsequence (not relabelled) such that Γ ε σ → Γ as ε → 0 (see Definition 2.17) and Γ is a minimizer of F .

Proof. Remark that F anf F ε are not equal to infinity. Then, by Theorem 2.18 (iii), F and F ε reach their minima on X.

As {F ε } ε is a decreasing sequence converging to F pointwise, we get

lim ε→0 min Γ∈X F ε (Γ) = inf ε>0 min Γ∈X F ε (Γ) = min Γ∈X inf ε>0 F ε (Γ) = min Γ∈X F (Γ) . (4.5)
Thus, if {Γ ε } is a sequence of minimizers of F ε we have F (Γ ε ) F ε (Γ ε ) so that {Γ ε } is a minimizing sequence for F . Then, by Theorem 2.18, there exists Γ ∈ X and a subsequence (not relabelled) such that Γ ε σ → Γ as ε → 0. As F is lower semicontinuous with respect to the σ convergence, from (4.5), it follows that Γ is a minimizer of F .

Finite Element Space

In the following, to ease the notation, we identify R 2 with C and S 1 with [0, 1] using periodic boundary conditions.

To approximate numerically stationary points of (4.4), we discretize this problem by using finite element approximations of the homotopies, which are piecewise linear along the s variable and piecewise constant along the t variable. This choice of elements is justified by the fact that the evaluation of the energy requires the use of two derivatives along the s variable, and a single derivative along the t variable.

Finite elements curves.

A piecewise affine curve with n node is defined as

∀ s ∈ [0, 1], γ(s) = n j=1 γj ξ j (s)
where we used piecewise affine finite elements

ξ j (s) = max 0, 1 -n s - j n s ∈ [0, 1], ∀ j = 1, . . . , n -1 ξ n (s) = max {0, 1 -n |s|} + max {0, 1 -n |s -1|} , s ∈ [0, 1].
Here, γ ∈ C n denotes the coordinates of γ and we denote γ = P 1 (γ) the corresponding bijection.

Finite elements homotopies. We consider the finite dimensional space of homotopies of the form

∀(t, s) ∈ [0, 1] 2 , Γ(t)(s) = N i=1 n j=1 Γi,j ζ i (t)ξ j (s) (4.6)
where we used piecewise constant finite elements

ζ i (t) = I [ i N , i+1 N ] (t) ∀ i = 1, ..., N -1 , ζ N (t) = I [0, 1 N ] (t) ,
Here, Γ ∈ C N ×n denotes the coordinates of Γ and we denote Γ = P 0,1 ( Γ) the corresponding bijection.

Discretized Energies

The initial infinite dimensional optimization problem (4.4) is discretized by restricting the minimization to the finite element space described by (4.6) as follow

min F ε ( Γ) : Γ ∈ C N ×n , Γ1,• = γ0 where F ε ( Γ) = F ε (Γ) (4.7)
where Γ = P 0,1 ( Γ) and where the input boundary curves are γ 0 = P 1 (γ 0 ), γ 1 = P 1 (γ 1 ), which are assumed to be piecewise affine finite elements. We have denoted here Γ i,• = (Γ i,j ) n j=1 ∈ R n . In order to ease the computation of gradients, we note that the energy F ε can be decomposed as

F ε ( Γ) = H(P 1 ( ΓN,• ), γ 1 ) + E ε ( Γ) where E ε ( Γ) = 1 N -1 N -1 i=1 J( Γi,• , ṽi ) (4.8)
where we denoted the discrete time derivative vector field as

ṽi = Γi+1,• -Γi,• N -1 ∈ C n .
For γ ∈ C n and ṽ ∈ C n , we used the notation J(γ, ṽ) = 2 ℓ=0 λ ℓ J ℓ (γ, ṽ).

and we define bellow the explicit computation of the terms J ℓ (γ, ṽ) for ℓ = 0, 1, 2.

Zero order energy term (ℓ = 0). The L 1 norm of a piecewise affine field v = P 1 (ṽ) tangent to a piecewise affine curve γ = P 1 (γ) can be computed as

S 1 |v(s)| ε |γ ′ (s)| ε ds = n i=1 n|∆ + (γ) i | ε n i+1 n i n |ṽ i ξ i (s) + ṽi+1 ξ i+1 (s)| ε ds.
This quantity cannot be evaluated in closed form. For numerical simplicity, we thus approximate the integral by the trapezoidal rule. With a slight abuse of notation (this is only an approximate equality), we define the discrete L 1 -norm as

J 0 (γ, ṽ) = 1 2 n i=1 |∆ + (γ) i | ε n |ṽ i | ε + |ṽ i+1 | ε ,
where we used the following forward finite difference operator

∆ + : C n → C n , ∆ + (γ) i = γi+1 -γi .
First order energy term (ℓ = 1). We point out that

dv dγ = n i=1 ∆ + (ṽ) i |∆ + (γ) i | ε n ζ i (4.9)
which implies that

S 1 dv dγ(s) ε |γ ′ (s)| ε ds = n i=1 i+1 n i n n|∆ + (ṽ) i | ε n ds.
Then the discretized L 1 -norm of the first derivative is defined by

J 1 (γ, ṽ) = n i=1 |∆ + (ṽ) i | ε n .
Second order energy term (ℓ = 2). As the first derivative is piecewise constant, the second variation coincides with the sum of the jumps of the first derivative. In fact, for every g ∈ C 1 c (S 1 , R 2 ), we have

S 1 dv dγ(s) , dg dγ(s) dγ(s) = n i=1 i+1 n i n dv dγ(s) , g ′ (s) ds = = n i=1 dv dγ i -1 n - dv dγ i n , g i n .
Then, by (4.9), the second variation T V 2 γ (v) can be defined as

J 2 (γ, ṽ) = n i=1 ∆ + (ṽ) i+1 |∆ + (γ) i+1 | ε n - ∆ + (ṽ) i |∆ + (γ) i | ε n ε . ( 4

.10)

We point out that J 2 represents a regularized definition of the second total variation because we evaluate the jumps by the smoothed norm | • | ε .

Minimization with Gradient Descent

The finite problem (4.7) is an unconstrained optimization on the variable ( Γ2,• , . . . , ΓN,• ), since Γ1,• = γ0 is fixed. The function F ε being minimized is C 1 with a Lipschitz gradient, and we thus make use of a gradient descent method. In the following, we compute gradient for the canonical inner product in C N ×n .

Starting from some Γ(0) ∈ C N ×n , we iterate

Γ(k+1) = Γ(k) -τ k ∇F ε ( Γ(k) ) (4.11)
where τ k > 0 is the descent step. A small enough gradient step size (or an adaptive line search strategy) ensures that the iterates converge toward a stationary point Γ (∞) of F ε . The gradient ∇F ε ( Γ) is given by its partial derivatives as, for i = 2, . . . , N -1,

∂ Γi F ε ( Γ) = 1 N -1 ∂ 1 J( Γi , ṽi ) - 1 N -1 ∂ 2 J( Γi+1 , ṽi+1 ) + 1 N -1 ∂ 2 J( Γi-1 , ṽi-1 )
where ∂ 1 J (reap. ∂ 2 J) is the derivative of J with respect to the first (resp. second) variable and

∂ ΓN F ε = δ + 1 (N -1) 2 ∂ 1 J( ΓN-1 , ṽN-1 ) ,
where δ is the gradient of the map γ → H(P 1 (γ), γ 1 ) at γ = ΓN,• . This gradient can be computed as detailed in [START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF].

Numerical Results

In this section we show some numerical examples of computations of a stationary points Γ(∞) of the problem (4.7) that is intended to approximate geodesics for the BV 2 metric. We use a similar approach to approximate geodesic for the H k metric, for k = 2, by replacing E in (4.2) by

E(Γ) = 1 0 Γ t (t) H s (Γ(t)) dt (4.12)
where, for all γ ∈ H s (S 1 , R 2 ) and v ∈ H s (γ),

v H s (γ) = S 1 µ 0 |v(s)| 2 + µ 1 dv dγ (s) 2 + µ 2 d 2 v dγ 2 (s) 2 dγ(s),
where the parameter (µ 0 , µ 1 , µ 2 ) ∈ (R + ) 3 can be tuned for each particular application. Note that, on contrast to the BV 2 case, this Sobolev energy is a smooth functional, and one thus does not need to perform a regularization (4.3), or equivalently, one can use ε = 0 in this case. We do not detail the computation of the gradient of the discretized version of the functional (4.12), since these computations are very similar to the BV 2 case.

In the following experiments, we use a discretization grid of size (N, n) = (10, 256). The weights are set to (λ 0 , λ 1 , λ 2 ) = (1, 0, 1) and (µ 0 , µ 1 , µ 2 ) = (1, 0, 1) (the curves are normalized to fit in [0, 1] 2 ). These experiments can be seen as toy models illustrations for the shape registration problem, were one seeks for a meaningful bijection between two geometric curves parameterized by γ 0 and γ 1 . Note that the energies being minimized are highly non-convex, so that the initialization Γ (0) of the gradient descent (4.11) plays a crucial role.

Figure 1, top row, shows a simple test case, for which using a trivial constant initialization Γ(0) i = γ0 , for both BV 2 and H 2 metric, produces a valid homotopy Γ (∞) between γ 0 and γ 1 . One can observe that while both homotopies are similar, the Sobolev metric produces a slightly smoother regular evolution of curves. This is to be expected, since piecewise affine curves are not in the Sobolev space H 2 (S 1 , R 2 ).

Figure 1, bottom row, shows a more complicated case, where using a trivial initialization Γ(0) fails to give a correct result Γ(∞) , because the gradient descent is trapped in a poor local minimum. We thus use as initialization the natural bijection Γ(0) which is piecewise affine and correctly links the singular points of the curves γ 0 and γ 1 . It turns out that this homotopy is a stationary point of the energy (4.7), which can be checked on the numerical results obtained by the gradient descent. On the contrary, the Sobolev metric finds a slightly different homotopy, which leads to smoother intermediate curves.

BV 2 Sobolev Figure 1: Homotopies Γ (∞) obtained for BV 2 -Finsler energy (left) and Sobolev metric (right). Each image displays the initial curve γ 0 (black one) and γ 1 (dash line) and the optimal { Γi,• } i where the index 1 i N is indicated by color variations between blue (i = 1) and red (i = N ).

Conclusion

The variational approach defined in this work represents a general strategy to prove existence of minimal geodesics with respect to Finslerian metrics. The uniqueness is at the moment an open question.

In order to generalize previous results to more general Banach spaces, we point out the main properties which must be satisfied by the Banach topology:

(i) the two constants m γ , M γ appearing in Proposition 2.9 must be bounded on geodesic balls;

(ii) the topology of the space must imply a suitable convergence of the reparameterizations in order to get semi-continuity of the norm of {Γ h t • ϕ h (t)} h ; in the BV 2 -case such a topology is the W 1,1 -strong topology.

For the BV 2 metric, the major difficulty concerns the characterization of the weak topology of the space of the paths. The usual characterization of the dual of Boncher spaces H 1 ([0, 1], B) (B is a Banach space) requires that the dual of B verifies the Radon-Nikodym property ( [START_REF] Bochner | Linear functionals on certain spaces of abstractly-valued functions[END_REF], [START_REF] Cengiz | The dual of the bochner space L p (µ, e) for arbitrary µ[END_REF]). We point out that the martingale argument used to prove Theorem 2.15 avoids this problem and allows one to define a suitable topology in such a space guaranteeing the lower semi-continuity of the geodesic energy.

Moreover, as pointed out in the introduction, the necessary conditions proved in [START_REF] Mordukhovich | Variation Analysis and Generalized Differentiation II, Applications[END_REF] are not valid in our case. This represents an interesting direction of research because optimality conditions allow one to study regularity properties of minimal geodesics. It is an open question if the generalized Euler-Lagrange equations in [START_REF] Mordukhovich | Variation Analysis and Generalized Differentiation II, Applications[END_REF] can be generalized to our case and give the Hamiltonian geodesic equations. Strongly linked to this question is the issue of convergence of the numerical method. Indeed, the convergence of the sequence of discretized problems would imply the existence of geodesic equations.

From a numerical point of view, as we pointed out, the minimal geodesic energy suffers from many poor local minima. To avoid some of these poor local minima, it is possible to modify the metric to take into account some prior on the set of deformations. For instance, in the spirit of [START_REF] Charpiat | Finsler Steepest Descent with Applications to Piecewise-regular Curve Evolution[END_REF], a Finsler metric can be designed to favor piecewise rigid motions.

. 29 )

 29 Now, we have m = infh min t∈[0,1]

  by the Convergence Theorem for Martingales ([15] : Theorem 5.4.5, p

Theorem 2 . 21 (

 221 Geometric existence). Let γ 0 γ 1 ∈ B such that D([γ 0 ], [γ 1 ]) < ∞. Then there exists a minimizer of D([γ 0 ], [γ 1 ]).

Theorem 4 . 1 .

 41 Let γ 0 ∈ B and X = {Γ ∈ H 1 ([0, 1], B ∩ B r (γ 0 )) : Γ(0) = γ 0 },where B r (γ 0 ) is defined as in the point (iii) of Theorem 2.18. Then lim ε→0 min Γ∈X F ε (Γ) = min Γ∈X F (Γ) .

  Proposition 2.6. For every γ ∈ B the set [γ] = γ(S 1 ) can be locally represented as the graph of a BV 2 -function. For everyγ 1 , γ 2 ∈ B such that [γ 1 ] = [γ 2 ], there exists a homeomorphism ϕ ∈ BV 2 (S 1 , S 1 ) such that γ 1 = γ 2 • ϕ . BV 2 (S 1 , R 2 ), its first and second variations with respect to the measure dγ are defined respectively by

		(2.5)
	Proof. See [14], Proposition 3.7.
	Note that the diffeomorphism ϕ appearing in (2.5) is not unique.
	Definition 2.7 (Tangent space). For any γ ∈ B, we set T γ B = BV 2 (γ) the space BV 2 (S 1 , R 2 )
	equipped with the measure dγ(s) = |γ ′ (s)|ds. In BV 2 (γ) , integration and differentiation is done
	with respect to dγ(s). Namely, the notation dg dγ(s) (s) stands for 1 |γ ′ (s)|	dg ds .
	Moreover, for every f ∈

Acknowledgements

The authors want to warmly thank Martins Bruveris for pointing out the geodesic completeness of the Sobolev metric on immersed plane curves. This work has been supported by the European Research Council (ERC project SIGMA-Vision).