In these pages we present a library and sample
program that implement the FFT Block Matching Algorithm as
presented in the paper "Full Search Content Independent Block
Matching Based On The Fast Fourier Transform" by Steven
L. Kilthau, Mark S. Drew, and Torsten
Möller. A link to
the pre-publication version of the paper is also
included.
The FFT Block Matching Algorithm is independent of image content
and is faster than other full-search methods. The method employs a
novel data structure called the Windowed-Sum-Squared-Table, and uses
the fast Fourier transform (FFT) in its computation of the sum squared
difference (SSD) metric. Use of the SSD metric allows for higher peak
signal to noise ratios than other fast block matching algorithms which
require the sum of absolute difference (SAD) metric. However, because
of the complex floating point and integer math used in our computation
of the SSD metric, our method is aimed at software implementations
only. Test results show that our method has a running time 13%-29% of
that for the exhaustive search, depending on the size of the search
range.
For our method to gain better acceptance and use, we present here a
pre-compiled library that works in conjunction with the Fastest
Foureir Transform in the West (FFTW).
