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.

A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves

Published

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

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 November 12, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created June 8, 2015, Updated January 27, 2020