A Discrete Framework to Find the Optimal Matching Between Manifold-Valued Curves

The aim of this paper is to find an optimal matching between manifold-valued curves, and thereby adequately compare their shapes, seen as equivalent classes with respect to the action of reparameterization. Using a canonical decomposition of a path in a principal bundle, we introduce a simple algorithm that finds an optimal matching between two curves by computing the geodesic of the infinite-dimensional manifold of curves that is at all time horizontal to the fibers of the shape bundle. We focus on the elastic metric studied in Le Brigant (J Geom Mech 9(2):131–156, 2017) using the so-called square root velocity framework. The quotient structure of the shape bundle is examined, and in particular horizontality with respect to the fibers. These results are more generally given for any elastic metric. We then introduce a comprehensive discrete framework which correctly approximates the smooth setting when the base manifold has constant sectional curvature. It is itself a Riemannian structure on the product manifold \(M^{n}\) of “discrete curves” given by n points, and we show its convergence to the continuous model as the size n of the discretization goes to \(\infty \). Illustrations of geodesics and optimal matchings between discrete curves are given in the hyperbolic plane, the plane and the sphere, for synthetic and real data, and comparison with dynamic programming (Srivastava and Klassen in Functional and shape data analysis, Springer, Berlin, 2016) is established.