MULTI-LEVEL FAST MULTIPOLE METHOD FOR THIN PLATE SPLINE EVALUATION (TA-P7)

Author(s) : Ali Zandifar (University of Maryland, USA) Ser-Nam Lim (University of Maryland, USA) Ramani Duraiswami (University of Maryland, USA) Nail A. Gumerov (University of Maryland, USA) Larry S. Davis (University of Maryland, USA)

Abstract : Image registration is an important problem in image processing and computer vision. Much recent work in image registration is on matching non-rigid deformations. Thin Plate Splines are an effective image registration method when the deformation between two images can be modeled as the bending of a thin metal plate on point constraints such that the topology is preserved (non-rigid deformation). However, because evaluating the computed TPS model at all the image pixels is computationally expensive, we need to speed it up. We introduce the use of Multi-Level Fast Multipole Method (MLFMM) for this purpose. Our contribution lies in the presentation of a clear and concise MLFMM framework for TPS, which will be useful for future application developments. The achieved speedup using MLFMM is an improvement from $O(Nî2)$ to $O(N \log N)$. We show that the fast evaluation outperforms the brute force method while maintaining acceptable error bound.

Menu