An Efficient Partitioning-Based Scheme for 2-D Convolution and Signal Processing Applications

摘要

A new scheme for efficiently computing the 2-dimensional (2-D) linear convolution between a fixed filter and an input sequence is presented. The scheme is particularly suitable for a special type of linear convolutions encountered in several 2-D applications, such as image registration and 2-D block adaptive filtering. In this type of convolution the involved filter is assumed fixed for a number of outputs which is less (or much less) than the number of filter taps. By properly partitioning both the filter and the input sequences the whole problem is divided into a number of smaller convolution problems which in turn are solved efficiently in the frequency-domain using Fast Fourier Transform (FFT). The scheme exhibits considerably reduced computational complexity as compared to other well-known FFT-based techniques. Moreover it lends itself for parallel implementation as well as for efficient VLSI implementation since it employs FFTs of relatively small size.