On Computing Elastic Shape Distances between Curves in d-dimensional Space

Published

June 21, 2021

Author(s)

Javier Bernal, James F. Lawrence, Gunay Dogan, Robert Hagwood

Abstract

The computation of the elastic registration of two simple curves in higher dimensions and therefore of the elastic shape distance between them has been investigated by Srivastava et al. Assuming the first curve has one or more starting points, and the second curve has only one, they accomplish the computation, one starting point of the first curve at a time, by minimizing an L2 type distance between them based on alternating computations of optimal diffeomorphisms of the unit interval and optimal rotation matrices that reparametrize and rotate, respectively, one of the curves. We recreate the work by Srivastava et al., but in contrast to it, again for curves in any dimension, we present a Dynamic Programming algorithm for computing optimal diffeomorphisms that is linear, and justify in a purely algebraic manner the usual algorithm for computing optimal rotation matrices, the Kabsch-Umeyama algorithm, which is based on the computation of the singular value decomposition of a matrix. In addition, we minimize the L2 type distance with a procedure that alternates computations of optimal diffeomorphisms with successive computations of optimal rotation matrices for all starting points of the first curve. Carrying out computations this way is not only more efficient all by itself, but, if both curves are closed, allows applications of the Fast Fourier Transform for computing successively in an even more efficient manner, optimal rotation matrices for all starting points of the first curve.

Citation

Technical Note (NIST TN) - 2164

Report Number

2164

NIST Pub Series

Technical Note (NIST TN)

Pub Type

NIST Pubs

Download Paper

https://doi.org/10.6028/NIST.TN.2164

Local Download

Keywords

dynamic programming, elastic shape distance, FFT, rotation matrix, shape analysis, singular value decomposition, trace

Citation

Bernal, J. , Lawrence, J. , Dogan, G. and Hagwood, R. (2021), On Computing Elastic Shape Distances between Curves in d-dimensional Space, Technical Note (NIST TN), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.TN.2164, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=931562 (Accessed April 23, 2024)