# Best way to resample a signal (image)?

I have an original image $\ I(x_i,y_j)$ where

$\ x_i = i*\Delta x, 0<= i < n_i$

and

$\ y_j = j*\Delta y, 0<= j < n_j$

I am trying to implement a function that resamples the image to:

$\ I(x_k,y_l)$ where

$\ x_k = k*\Delta xx, 0<= k < n_k$

and

$\ y_l = l*\Delta yy, 0<= l < n_l$

The case when $\ \Delta xx <= \Delta x$ and $\ \Delta yy <= \Delta y$ : upsampling, is quite easy (?).

Linear interpolation between nearest neighbours should do a decent job?

Downsampling on the other hand is more tricky.

To make sure Nyquist is followed so that no aliasing occurs; I must lowpass filter before decimating.

How do I do this an good yet simple manner?

I was thinking maybe using the FFT to do both upsampling and downsampling:

1. take the FFT of the image
2. zero pad or truncate the FFT
3. inverse FFT

In the case of zero padding this amount to sinc interpolation (which is better than linear interpolation)?

In the case of truncation this amount to (ideal) lowpass filtering?

So this should be a both simple to implement and very good solution?

I guess one thing to look out for is edge effects.

How do I best avoid this?

I was thinking repeating the image twice in x and y and then circulary shifting it half the width and height of the image. That should make the padded image cyclical periodic.

-
Why not to just use Gaussian blur? Or you can compute weighted sum around sampled pixel instead of blurring+sampling. –  Libor Oct 30 '12 at 16:27
Thanks Libor! Gaussian blur is simple to implement but how do I decide the size of the kernel? –  Andy Oct 30 '12 at 16:32
The larger the kernel, the more accurate the filter. I've seen a suggestion of $\lceil 3\sigma \rceil$ where $\sigma$ is proportional to scale factor, maybe you can use $\sigma=\sqrt{t}$ where $t$ is the scale factor. See Scale space article for more information. –  Libor Oct 30 '12 at 18:57

An FFT approach to filtering/resampling should work fine, but you don't want to just truncate or pad with zeros. That will add effects to the image. See here for more information about FFT resampling.

You could also just do a FIR filter. If you upsample by a ratio of $\frac{p}{q}$ then you would want your anti-aliasing filter to have a normalized bandwidth of $\frac{q}{p}$. You could make the bandwidth a little smaller to get rid of more alias energy, as desired. If you downsample by a ratio of $\frac{p}{q}$ then you would want the filter bandwidth to also be about $\frac{p}{q}$. Again, you could make it a little smaller to get rid of more alias energy.

Once you have your filter you just need to do a two-dimensional convolution and trim the extra resulting samples on each edge. Many signal processing libraries have built-in two-dimensional filtering routines that can do this for you.

-
Thanks Jim! I read your other answer on FFT resampling. You gave an excellent guide on how to do FFT resampling, but I do still not understand mathematically why the number of samples must be a multiple of the decimation rate. Also could you recommend a good signal processing library in C++/C/Fortran? –  Andy Oct 31 '12 at 8:22
If your FFT is $N$ samples long and you're resampling by a ratio of $\frac{p}{q}$, $N$ must be a multiple of $q$ because you want to end up with $\frac{Np}{q}$ samples. If $q$ doesn't divide evenly into $N$, then you will need to produce a "fractional sample", which is impossible. –  Jim Clay Oct 31 '12 at 12:37
No, I'm afraid I don't have a recommendation for C/C++/Fortran libraries. I generally use Matlab and hand-coded C. I know that lots of people use Python and NumPy/SciPy. I googled "signal processing library C++" and saw that there are a number of libraries, but I haven't used any of them. –  Jim Clay Oct 31 '12 at 12:40
I am just trying to get an feel for this: what would be the equivalent convolution kernel in the time domain? I have this (wrong?) idea that FFT resampling equals sinc interpolation and therefore is the theoretical optimal solution. –  Andy Nov 1 '12 at 14:28
You're right, padding with zeros and truncating in the frequency domain is equivalent to ideal sinc interpolation. The problem is, much like nature doesn't like vacuums, nature doesn't like ideal filters. It is known as the Gibbs phenomenon. You can do it in steps though. Try the FFT approach with padding/truncation. If you like the results, great, problem solved. If you don't you can always add the filtering that I described in the other thread. –  Jim Clay Nov 1 '12 at 15:16