Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Fast Dynamic Programming for Elastic Registration of Curves

Published

Author(s)

Javier Bernal, Gunay Dogan, Robert Hagwood

Abstract

Curve registration problems in data analysis and com- puter vision can often be reduced to the problem of match- ing two functions defined on an interval. Dynamic Pro- gramming (DP) is an effective approach to solve this prob- lem. In this paper, we propose a DP algorithm that runs in O(N ) time to compute optimal diffeomorphisms for elas- tic registration of curves with N nodes. This algorithm contrasts favorably with other DP algorithms used for this problem: the commonly used DP of quadratic time com- plexity, and the original DP that guarantees a globally op- timal solution with cubic time complexity. Key to our com- putational efficiency is the savings achieved by reducing our search space, focusing on thin strips around graphs of esti- mates of optimal diffeomorphism. Estimates and strips are obtained with a multigrid approach: an optimal diffeomor- phism obtained from a lower resolution grid using DP is progressively projected to ones of higher resolution until full resolution is attained. Additionally, our DP algorithm is designed so that it can handle nonuniformly discretized curves. This enables us to realize further savings in com- putations, since in the case of complicated curves requiring large numbers of nodes for a high-fidelity representation, we can distribute curve nodes adaptively, focusing nodes in parts of high variation. We demonstrate effectiveness of our DP algorithm on several registration problems in elas- tic shape analysis, and functional data analysis.
Proceedings Title
Proceedings of 2nd international workshop on differential geometry in computer vision and machine learning (DIFF-CVML'16) in conjunction with CVPR 2016, Las Vegas, 2016.
Conference Dates
June 26-July 1, 2016
Conference Location
Las Vegas, NV, US
Conference Title
2nd international workshop on differential geometry in computer vision and machine learning (DIFF-CVML'16) in conjunction with CVPR 2016, Las Vegas, 2016.

Keywords

dynamic programming, elastic shape analysis, shape distance, curve registration, function alignment

Citation

Bernal, J. , Dogan, G. and Hagwood, R. (2016), Fast Dynamic Programming for Elastic Registration of Curves, Proceedings of 2nd international workshop on differential geometry in computer vision and machine learning (DIFF-CVML'16) in conjunction with CVPR 2016, Las Vegas, 2016., Las Vegas, NV, US, [online], https://doi.org/10.1109/CVPRW.2016.137, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=920781 (Accessed March 28, 2024)
Created June 30, 2016, Updated April 1, 2022