Fast Dynamic Programming for Elastic Registration of Curves

Javier Bernal, Gunay Dogan, Charles R. Hagwood; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2016, pp. 111-118

Abstract


Curve registration problems are ubiquitous in data analysis and computer vision. We propose a dynamic programming (DP) algorithm that runs in O(N) time to compute optimal diffeomorphisms for elastic registration of curves with N nodes. Our algorithm compares favorably with other DP algorithms for this problem: the commonly used DP with O(N^2) cost, and the original DP that guarantees a global optimality with O(N^4) cost. We achieve fast run times by reducing our search space, focusing on a strip around an estimate of the optimum, obtained with a multigrid approach: optimal solutions from lower resolutions are progressively projected to ones of higher resolution. Additionally, our algorithm is designed to handle nonuniformly discretized curves, enabling further savings in computations, because we can distribute the curve nodes adaptively and work with fewer nodes. We show its effectiveness on several shape analysis examples.

Related Material


[pdf]
[bibtex]
@InProceedings{Bernal_2016_CVPR_Workshops,
author = {Bernal, Javier and Dogan, Gunay and Hagwood, Charles R.},
title = {Fast Dynamic Programming for Elastic Registration of Curves},
booktitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops},
month = {June},
year = {2016}
}