A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves
Abstract
Effective computational tools for shape analysis are needed in many areas of science and engineering. We address this and propose a new fast iterative algorithm to compute the elastic geodesic distance between shapes of closed planar curves. The original algorithm for this has cubic time complexity with respect to the number of nodes per curve. Hence it is not suitable for large shape data sets. We aim for large-scale shape analysis and thus propose an iterative algorithm based on the original one but with quadratic time complexity. In practice, we observe subquadratic, almost linear running times, and that our algorithm scales very well with large numbers of nodes. The key to our algorithm is the decoupling of the optimization for the starting point and rotation from that of the reparametrization, and the development of fast dynamic programming and iterative nonlinear constrained optimization algorithms that work in tandem to compute optimal reparametrizations fast.
Cite
Text
Dogan et al. "A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves." Conference on Computer Vision and Pattern Recognition, 2015. doi:10.1109/CVPR.2015.7299050Markdown
[Dogan et al. "A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves." Conference on Computer Vision and Pattern Recognition, 2015.](https://mlanthology.org/cvpr/2015/dogan2015cvpr-fast/) doi:10.1109/CVPR.2015.7299050BibTeX
@inproceedings{dogan2015cvpr-fast,
title = {{A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves}},
author = {Dogan, Gunay and Bernal, Javier and Hagwood, Charles R.},
booktitle = {Conference on Computer Vision and Pattern Recognition},
year = {2015},
doi = {10.1109/CVPR.2015.7299050},
url = {https://mlanthology.org/cvpr/2015/dogan2015cvpr-fast/}
}