A Semi-Discretized Method for Optimal Reparametrization of Curves

Abstract

I denne oppgaven utvikler vi en ny metode for optimal omparametrisering av kurver ved bruk av rothastighetstransformasjonen (the square root velocity transform). Metoden bruker dynamisk programmering, men med en bedre håndtering av grunntilfellene enn tidligere metoder. Mens tidligere metoder er fullstendig diskretisert, er den nye metoden kun delvis diskretisert. Dette utnyttes til å oppnå både en bedre konvergensrate og lavere asymptotisk kjøretid sammenlignet med tilsvarende metoder.

Under utviklingen av metoden introduser vi nye hjelpevariabler og nye differensialligninger som karakteriserer optimale løsninger. Metoden er lineær i omparametriseringsfunksjonene, og kvadratisk i avstandsestimatet. I enkelte tilfeller kan henholdsvis kvadratisk og super-kvadratisk konvergens oppnås ved hjelp av ekstrapolasjon. Dette underbygges av numeriske eksperimenter.

In this thesis, we develop a new method for solving the optimal reparametrization problem within the square root velocity framework. The method is based on a dynamic programming approach, but with a more accurate update equation than previous methods. While previous methods are fully discretized, the new method is only semi-discretized. This is utilized to give both a better convergence rate and a lower computational complexity compared to similar methods.

To construct the method, we introduce new auxiliary variables, and establish differential equations characterizing the optimal reparametrizers. The resulting method is linear in the reparametrizers and quadratic in the distance estimate. In certain situations, these convergence rates can be improved to quadratic and super-quadratic, respectively, by the use of extrapolation. This is supported by numerical experiments.