Full Search Content Independent Block Matching Based on the Fast Fourier Transform


Steven Kilthau

In digital video compression, the frames of the video are broken up into small blocks. To increase the compression ratio we would like to take the difference of each block with a similar block of pixels from the previous frame. The process of searching in a given range for the block of pixels that is most similar to the block in the current frame is referred to as block matching. The algorithm that we present is called the FFT Block Matching Algorithm (FFTBMA).

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.