TY - CONF T1 - Multi-level fast multipole method for thin plate spline evaluation T2 - Image Processing, 2004. ICIP '04. 2004 International Conference on Y1 - 2004 A1 - Zandifar,A. A1 - Lim,S. A1 - Duraiswami, Ramani A1 - Gumerov, Nail A. A1 - Davis, Larry S. KW - (mathematics); KW - Computer KW - deformation; KW - evaluation; KW - fast KW - image KW - MATCHING KW - matching; KW - metal KW - method; KW - multilevel KW - multipole KW - nonrigid KW - pixel; KW - plate KW - plate; KW - processing; KW - registration; KW - resolution; KW - spline KW - splines KW - thin KW - vision; AB - 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 muitipole 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(N2) to O(N log N). We show that the fast evaluation outperforms the brute force method while maintaining acceptable error bound. JA - Image Processing, 2004. ICIP '04. 2004 International Conference on VL - 3 M3 - 10.1109/ICIP.2004.1421395 ER -