Revised fast 2D linear filtering

Abstract

In some applications, concerning the linear filtering problem, one has to process millions of signal samples. Therefore, the computation of the convolution requires a lot of time. It is known that for multi-dimensional input signals, the popular approach is to compute the convolution in the frequency domain which is sometimes referred to as the fast convolution. The fast convolution can be more efficient than the ordinary version if the number of kernel samples is large enough. Using 2D DFT (discrete Fourier transform) for calculation of a 2D linear convolution, it is assumed here, that some linear time-invariant (LTI) filter’s 2D input signal samples are updated by a sensor in real time. It is urgent for every new input signal sample or for small part of new samples to evaluate new output frequency samples (f.s.). The idea is that 2D FFT (fast Fourier transform) should not be recalculated with every new input signal sample, it is needed just to modify the algorithm, when the new input sample replaces the old one. An example with ordinary and modified 8-point 2D FFT is given as well.