FFT-based Alignment of 2D Closed Curves with Application to Elastic Shape Analysis

Günay Doğan, Javier Bernal and Charles Hagwood

Abstract

For many shape analysis problems in computer vision and scientific imaging (e.g., computational anatomy, morphological cytometry), the ability to align two closed curves in the plane is crucial. If the curves have the same length and are centered at the origin the critical steps to an optimal alignment are finding the best rotation for one curve to match the other and redefining the starting point of the rotated curve so that the starting points of the two curves match. Unlike open curves, closed curves do not have fixed starting points, and this introduces an additional degree of freedom in the alignment. Hence the common naive method to find the best rotation and starting point for optimal alignment has $O(N^2)$ time complexity, N the number of nodes per curve. This can be slow for curves with large numbers of nodes. In this paper, we propose a new $O(N log N)$ algorithm for this problem based on the Fast Fourier Transform. Together with uniform resampling of the curves with respect to arc length, the new algorithm results in an order of magnitude speed-up in our experiments. Additionally, we describe how we can use our new algorithm as part of elastic shape distance computations between closed curves to obtain accurate shape distance values at a fraction of the cost of previous approaches.

Session

Workshop: 1st International Workshop on DIFFerential Geometry in Computer Vision for Analysis of Shapes, Images and Trajectories (DIFF-CV)

Files

PDF iconPaper (PDF, 303K)

DOI

10.5244/C.29.DIFFCV.12
https://dx.doi.org/10.5244/C.29.DIFFCV.12

Citation

Günay Doğan, Javier Bernal and Charles Hagwood. FFT-based Alignment of 2D Closed Curves with Application to Elastic Shape Analysis. In H. Drira, S. Kurtek, and P. Turaga, editors, Proceedings of the 1st International Workshop on DIFFerential Geometry in Computer Vision for Analysis of Shapes, Images and Trajectories (DIFF-CV 2015), pages 12.1-12.10. BMVA Press, September 2015.

Bibtex

@inproceedings{DIFFCV2015_12,
	title={FFT-based Alignment of 2D Closed Curves with Application to Elastic Shape Analysis},
	author={Günay Doğan and Javier Bernal and Charles Hagwood},
	year={2015},
	month={September},
	pages={12.1-12.10},
	articleno={12},
	numpages={10},
	booktitle={Proceedings of the 1st International Workshop on DIFFerential Geometry in Computer Vision for Analysis of Shapes, Images and Trajectories (DIFF-CV 2015)},
	publisher={BMVA Press},
	editor={H. Drira, S. Kurtek, and P. Turaga},
	doi={10.5244/C.29.DIFFCV.12},
	isbn={1-901725-56-1},
	url={https://dx.doi.org/10.5244/C.29.DIFFCV.12}
}