I have made a low-pass-filter for image analysis using 2-dimensional FFT. It simply consists of 3 steps, (1) FFT of an original image, (2) replace high-frequency components (> cut-off frequency) by zero on the Fourier plane, and (3) inverse-FFT to reconstruct a filtered image. It works correctly. However, now I need to speed-up the filter for large-size images.
I am wondering if it is possible to speed up the filter by taking advantage of the limited number of nonzero components on the Fourier plane. For example, when the cut-off frequency is 1/10 of the size of the Fourier plane, I have non-zero region only in 1% of the 2D Fourier plane. If we truncate the rest of 99% region and apply the inverse FFT to the 1% region, we can obtain a low-pass-filtered image with a 10-times-sparse sampling. This inverse-FFT is much faster, but I want to have a filtered image with the same sampling points as the original image.
Now, my question is whether there is a method to recover the filtered-image with the sample sampling. If I misunderstand something, I would be happy to have it pointed out. Thanks.
Sinc interpolation (aka Whittaker–Shannon interpolation) would exactly recover the filtered image from the subsampled image that you describe. The problem is that implementing sinc interpolation in the spatial domain is expensive, and is preferably instead implemented in back the frequency domain, so this doesn't help speed up the filtering. As Yves suggested, a better idea is to use a more efficient interpolation like bicubic for approximately the same results.
But if approximate is Ok, I suggest to avoid the FFT in the first place. An NxN 2D FFT costs O(N² log N). You can get fast O(N²) lowpass filtering by applying IIR (recursive) filters in the spatial domain. See for instance the "Box" and "Alvarez–Mazorra" methods in A Survey of Gaussian Convolution Algorithms for a couple simple fast approximations of Gaussian filtering.