FFT Block Matching Algorithm

Library Samples Paper


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).

License and Copyright

The FFT Block Matching Algorithm implementation presented herein is copyright Steven Kilthau, 2002.

At the current time, only a binary distribution of this library is available.  Source code may be made available if the demand exists.  This binary version of the library runs in Windows and is freely available for personal and educational use.  For commercial inquiries, please contact kilthau@cs.sfu.ca.

Use of FFTW is subject to its own license on copyright.  More information can be found at www.fftw.org

Site maintained by: Steven Kilthau