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.

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.
Created June 8, 2015, Updated November 10, 2018