Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Fast Dynamic Programming for Elastic Registration of Curves

Published

Author(s)

Javier Bernal, Gunay Dogan, Robert C. 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
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
Created July 1, 2016, Updated November 10, 2018