Fast and accurate computation of the Fourier transform of an image

We use the Battle.Lemarié scaling function in an algorithm for fast computation of the Fourier transform of a piecewise smooth function f. Namely, we compute for —N m, n N (with a given accuracy) the integrals *,1 1 • f(m, n) = I I 1(2;,y) dy (0.1)Jo JO in O(ND)+O(N2 log N) operations, where ND is the number of subdomains where the function f is smooth. We consider an application of this algorithm to image processing. Notwithstanding that it might be advantageous to consider an image as a piecewise smooth function f, it is a common practice in image processing to simply take the FFT of the pixel values of the image in order to evaluate the Fourier transform. Due to the jump discontinuities of the function f, the accuracy of such a computation is poor. We propose our algorithm as a tool for the accurate computation of the Fourier transform of an image since the direct evaluation of (0.1) is very costly. 1. IMAGE AS A PIECEWISE SMOOTH FUNCTION It is natural and useful to consider an image as a piecewise smooth function. For example, the goal o