Wednesday, September 12, 2007

Filter numpy images with FFT, Python

Generic linear filter support is not currently built into the Python Imaging Library. This module lets you filter a numpy array against an arbitrary kernel:
    >>> I = numpy.asarray('test.jpg'))
    >>> I = filter(I, [[-1,0,1],[-2,0,2],[-1,0,1]])/8+128
    >>> Image.fromarray(numpy.uint8(I)).show()
The Fast Fourier Transform (FFT) is used. The FFT routine included with numpy isn't particularly fast (c.f. FFTW [1]), and in any case using the transform isn't as efficient as applying the filter naively for small filter sizes. Also, for separable kernels (e.g. the Gaussian kernel), it is often faster to perform two 1D convolutions in sequence. However, for large images and filters, using an FFT for convolution is often faster than other approaches. (If an image and filter contain a total of N pixels, then this algorithm takes O(NlogN) time, which is the fastest known time complexity algorithm for the general problem.) Public domain.

Update: A number of image filtering operations are provided in numarray (in the module numpy.numarray.nd_image), such as filtering, image morphology, distance transforms, and segmentation; see [2].