Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Fast Image Filtering

Subject: Fast Image Filtering

From: NIcholas

Date: 28 May, 2010 21:37:21

Message: 1 of 4

Hi,
I have a large image I of size [h,w] and a large filter F of size [h2,w2].
I want to quickly filter I with F but only return the valid portion of the filtering (i.e. the filter value at pixels IFilt(h2/2 : h-h2/2, w2/2: w-h2/2)).

Is there a quick way to do this with FFT without generating the full IFilt matrix?

Subject: Fast Image Filtering

From: Matt J

Date: 28 May, 2010 21:50:15

Message: 2 of 4

"NIcholas " <dsfadfa@aol.com> wrote in message <htpd2h$icd$1@fred.mathworks.com>...
> Hi,
> I have a large image I of size [h,w] and a large filter F of size [h2,w2].
> I want to quickly filter I with F but only return the valid portion of the filtering (i.e. the filter value at pixels IFilt(h2/2 : h-h2/2, w2/2: w-h2/2)).
>
> Is there a quick way to do this with FFT without generating the full IFilt matrix?

You can do this, but it only saves you a modest amount, because you still need the full sized array in Fourier space:

HW=[h+h2,w+w2];

ifft2( fft2(I HW).*fft2(F, HW), [h,w] );

Also, I hope you're certain that FFT domain convolution is required here. If F is much smaller than I in dimension, conv is better (and easier)

Subject: Fast Image Filtering

From: David Young

Date: 29 May, 2010 08:13:04

Message: 3 of 4

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <htpdqm$4uk$1@fred.mathworks.com>...
> "NIcholas " <dsfadfa@aol.com> wrote in message <htpd2h$icd$1@fred.mathworks.com>...
> > Hi,
> > I have a large image I of size [h,w] and a large filter F of size [h2,w2].
> > I want to quickly filter I with F but only return the valid portion of the filtering (i.e. the filter value at pixels IFilt(h2/2 : h-h2/2, w2/2: w-h2/2)).
> >
> > Is there a quick way to do this with FFT without generating the full IFilt matrix?
>
> You can do this, but it only saves you a modest amount, because you still need the full sized array in Fourier space:
>
> HW=[h+h2,w+w2];
>
> ifft2( fft2(I HW).*fft2(F, HW), [h,w] );
>
> Also, I hope you're certain that FFT domain convolution is required here. If F is much smaller than I in dimension, conv is better (and easier)

It's also worth testing whether convolve2, from the file exchange, is faster. It uses a textbook method to reduce the amount of computation for filters that are not full rank (this includes not only separable filters, but also those such as the Laplacian of Gaussian and Gabor functions which are not separable but have less than full rank). For some kinds and sizes of filters it gives a big speedup over conv2, so making the FFT route less necessary. It will also find a reduced-rank approximation to full-rank filters (with control over the error) if you want it to. It has a 'valid' option to give you the bit of the output that you want. See:

http://www.mathworks.com/matlabcentral/fileexchange/22619-fast-2-d-convolution

Subject: Fast Image Filtering

From: Bruno Luong

Date: 29 May, 2010 08:49:05

Message: 4 of 4

"NIcholas " <dsfadfa@aol.com> wrote in message <htpd2h$icd$1@fred.mathworks.com>...
> Hi,
> I have a large image I of size [h,w] and a large filter F of size [h2,w2].
> I want to quickly filter I with F but only return the valid portion of the filtering (i.e. the filter value at pixels IFilt(h2/2 : h-h2/2, w2/2: w-h2/2)).
>
> Is there a quick way to do this with FFT without generating the full IFilt matrix?

This is an fft-based convolution including VALID option. It can also takes advantage of GPU/CUDA your computer is equipped for:
 
http://www.mathworks.com/matlabcentral/fileexchange/24504-fft-based-convolution

The general recommendation is using FFT based convolution for large kernel, traditional convolution for smaller kernel, and David Young's implementation for low rank kernel, (where as it is big or small).

Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us