A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves

Published

June 8, 2015

Author(s)

Gunay Dogan, Javier Bernal, Robert C. Hagwood

Abstract

Effective computational tools for shape analysis are needed in many areas of science and engineering. We address this and propose a fast algorithm to compute the geodesic distance between elastic closed curves in the plane. The original algorithm for the distance has cubic time complexity with respect to the number of nodes on the curve. Hence, it is not suitable for large shape data sets. We aim for large-scale shape analysis and thus propose a novel iterative algorithm 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 on the curves. The key to our algorithm is the decoupling of the optimization for the starting point and rotation and the optimization for the reparameterization function. Moreover, we develop a fast dynamic programming algorithm and a nonlinear constrained optimization algorithm that work in tandem to compute optimal reparameterizations fast.

Proceedings Title

IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015

Conference Dates

June 7-12, 2015

Conference Location

Boston, MA

Conference Title

CVPR 2015

Pub Type

Conferences

Download Paper

https://doi.org/10.1109/CVPR.2015.7299050

Keywords

shape metrology, geodesics, algorithms, computation complexity.

Citation

Dogan, G. , Bernal, J. and Hagwood, R. (2015), A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves, IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015, Boston, MA, [online], https://doi.org/10.1109/CVPR.2015.7299050 (Accessed October 28, 2025)