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.
IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015
June 7-12, 2015
shape metrology, geodesics, algorithms, computation complexity.