FasT-Match: Fast Affine Template Matching
Authors:
- Simon KormanSKSimon Korman
- Daniel ReichmanDRDaniel Reichman
- Gilad TsurGTGilad Tsur
- Shai AvidanSAShai Avidan
- 1 June 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 2331-2338
Abstract
Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sub linear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.Keywords
This publication has 13 references indexed in Scilit:
- Globally Optimal Estimation of Nonrigid Image DistortionInternational Journal of Computer Vision, 2011
- ASIFT: A New Framework for Fully Affine Invariant Image ComparisonSIAM Journal on Imaging Sciences, 2009
- Accelerating Pattern Matching or How Much Can You Slide?2007
- A Comparison of Affine Region DetectorsInternational Journal of Computer Vision, 2005
- A performance evaluation of local descriptorsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2005
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Lucas-Kanade 20 Years On: A Unifying FrameworkInternational Journal of Computer Vision, 2004
- Retrieval of translated, rotated and scaled color texturesPattern Recognition, 2003
- Rotation-invariant pattern matching using wavelet decompositionPattern Recognition Letters, 2002
- Modelling the Power Spectra of Natural Images: Statistics and InformationVision Research, 1996