Simon Korman (Tel-Aviv University)
Fast-Match is a fast algorithm for approximate template matching under 2D
affine transformations that minimizes the Sum-of-Absolute-Differences (SAD)
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 sublinear 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
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.