• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for matematiske fag
  • View Item
  •   Home
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for matematiske fag
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A Semi-Discretized Method for Optimal Reparametrization of Curves

Wøien, Esten Nicolai
Master thesis
Thumbnail
View/Open
no.ntnu:inspera:2536008.pdf (1.605Mb)
URI
http://hdl.handle.net/11250/2624611
Date
2019
Metadata
Show full item record
Collections
  • Institutt for matematiske fag [1793]
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.
 
Publisher
NTNU

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit