# 2D array downsampling and upsampling using bilinear interpolation

I am trying to understand how exactly the upsampling and downsampling of a 2D image I have, would happen using Bilinear interpolation. Now I am aware of how bilinear interpolation works using a 2x2 neighbourhood values to interpolate the data point inside this 2x2 area using weights. But what I am not aware of, is asked below. My objectives and specific queries are -

1.To start with I have a 2D image of values(size MxN). The width(M) and height(N) of this image is not fixed, but will change from case to case. This 2D image needs to be down-sampled using bilinear interpolation to a grid of size PxQ (P and Q are to be configured as input parameters) e.g. lets take PxQ is 8x8. And assume input 2D array image is of size 200x100. i.e 200 columns, 100 rows.

Now how while performing downsampling using bilinear interpolation of this 200x100 image, should I first obtain a downsampled image of size 100x50 (downsampling by 2 in both dimensions using bilinear interpolation); then a 50x25 image(again by doing downsampling by 2 in both dimensions), then a 25x12 image, then a 12x12(this time doing downsampling by linear(not bilinear!) interpolation only along the rows, and finally drop some pixels to get 8x8. Any pointers to exact algorithm or different ways to achieve this, are appreciated.

2.Above question raises another one - how to downsample using bilinear interpolation by a non-integer scale factor, e.g. how to go from a say 8x8 image array to a 6x2 image wherein resampling/scaling factors in both dimensions are not integers.

3.Then when I get a 8x8 sized image I need to upsample it by bilinear interpolation to the same original size I started with- MxN. If I need to go from 8x8 to say 20x20. How would it interpolate in between points in a row and would it interpolate a full row by some means. Again in case of non-integer scale factors how would bilinear interpolation for upsampling happen. Exact steps.

And finally I need to implement this in C.

I tried visualizing these particular questions by taking different examples, but not got a clear picture of how this bilinear interpolation would happen while downsampling and upsampling. All I have is plenty of paper sheets having'dots and crossed' pictures on my desk, but still no clear solution!

Any detailed reading material, books appreciated.

-
I tried visualizing these particular questions by taking different examples, but ...  I suggest to try to visualize it with 1D signals first to graps the idea. –  leonbloy Jul 1 '11 at 16:36

Applying 2D Bilinear interpolation is equivalent to applying two 1D linear interpolations first in one axis, then on the other. Hence, you can (mostly) deal with each axis separatedly, at least for trying to understand the concepts.

Now, a one-dimensional signal can be upsampled by linear interpolation, by an arbitrary factor: I assume you have no problem here. Regarding downsampling, it's another story: linear interpolation (as the name implies) is more oriented to upsampling; it can make sense for downsampling only if the factor is near $1$ [*]. I don't think there is a carved-in-stone procedure here, but a simple procedure could be:

1. If the downsampling ratio $r$ is an integer $k$, do the trivial integer resample: each new downsample value is the average of $k$ original values.

2. Elsewhere, find the nearest lower integer, $r=k s$ where $k<r$ and $s \gtrsim 1$, do first a integer downsample by $k$ and then a linear interpolation by $s$.

This is to be done for each direction, independently.

[*] Actually it could make perfect sense, if the signal were first passed through a low pass filter. But this is (practically and conceptually, not ideally) what we are doing with the averaging.

Added To do the linear interpolation for upsampling (or downsampling by a factor near 1), with non integer ratio: assume an original 1D signal of length $N$, $A[i]$ $i=0 \cdots N-1$ that we want to convert to length $M$, $B[j]$ $j=0 \cdots M-1$ . One way is thinking the signal in a continuous domain $[0,1]$ that we have sampled at points $x=i/N$ in the original ($j/M$ in the transformed) (there are some unimportant variations: we could also take $x=(1+0.5)/N$, etc). Then, if we want to compute $B[j]$, this should ideally coincide with $A[i]$, with $i = j \frac{N}{M}$. But as this will not be (in general) an integer, we interpolate.

$$B[j] = A^*[i] = (i_1 - i) A[i_0] + (i - i_0) A[i_1]$$

where $i_0$, $i_1$ are the integers below and over $i$ (clipped to the range $0 \cdots N-1$), and $A^*[i]$ denotes the idealized-value of the signal in a non-integer sample index.

Bilinear interpolation is, in essence, this same thing, done first in one coordinate, then in the other.

-
So to understand correctly - consider 1D array of say 8 samples, and want to downsample it to 6 samples(sampling ratio 8/6=1.333) then as u said r = ks, if k = 0.5, s = 2. What next - downsample by 0.5(what does it mean to downsample by 0.5?) Can you pls. illustrate for this example from 8 to 6 points? Also I need to understand how exactly a 1D signal can be upsampled by any arbitrary scale factor? e.g. How to go from 4 samples to 6? –  goldenmean Jul 1 '11 at 21:33
@goldenmean: explanation added –  leonbloy Jul 2 '11 at 0:47
@goldenmean: regarding your examples: for 8/6=1.333 k=1 s=1.333, you go directly to the interpolation (you only do the integer subsampling if the ratio is 2 or more). For going to 4 to 6 (for any upsampling) you just do the linear interpolation as above. –  leonbloy Jul 2 '11 at 1:25
Thanks for details. Based on your explanation, I worked out one example of upsampling from 6 to 8 points. Can you please check and confirm If I have got it right? j=[0,1,2,3,4,5,6,7],for interpolated A, i=[0,0.75,1.5,2.25,3,3.75,4.5,5.25]; {(i0,i1)} index pairs for the samples from input to be used for interpolation for each of the 8 output samples are {(0,1),(0,1),(1,2),(2,3),(3,4),(3,4),(4,5),(5,5)}. Then I use the weighted averaging formula for each of these input samples and get the interpolated output sample. Correct. –  goldenmean Jul 2 '11 at 21:56
@goldenmean: Correct. –  leonbloy Jul 2 '11 at 22:30