Curve registration problems in data analysis and com- puter vision can often be reduced to the problem of match- ing two functions defined on an interval. Dynamic Pro- gramming (DP) is an effective approach to solve this prob- lem. In this paper, we propose a DP algorithm that runs in O(N ) time to compute optimal diffeomorphisms for elas- tic registration of curves with N nodes. This algorithm contrasts favorably with other DP algorithms used for this problem: the commonly used DP of quadratic time com- plexity, and the original DP that guarantees a globally op- timal solution with cubic time complexity. Key to our com- putational efficiency is the savings achieved by reducing our search space, focusing on thin strips around graphs of esti- mates of optimal diffeomorphism. Estimates and strips are obtained with a multigrid approach: an optimal diffeomor- phism obtained from a lower resolution grid using DP is progressively projected to ones of higher resolution until full resolution is attained. Additionally, our DP algorithm is designed so that it can handle nonuniformly discretized curves. This enables us to realize further savings in com- putations, since in the case of complicated curves requiring large numbers of nodes for a high-fidelity representation, we can distribute curve nodes adaptively, focusing nodes in parts of high variation. We demonstrate effectiveness of our DP algorithm on several registration problems in elas- tic shape analysis, and functional data analysis.
Proceedings of 2nd international workshop on differential geometry in computer vision and machine learning (DIFF-CVML'16) in conjunction with CVPR 2016, Las Vegas, 2016.
June 26-July 1, 2016
Las Vegas, NV
2nd international workshop on differential geometry in computer vision and machine learning (DIFF-CVML'16) in conjunction with CVPR 2016, Las Vegas, 2016.
dynamic programming, elastic shape analysis, shape distance, curve registration, function alignment