Interpolation algorithms when downscaling

Question

Im trying to understand downscaling. I can see how interpolation algorithms such as bicubic and nearest neighbour can be used when when upscaling, to "fill in the blanks" between the old, known points (pixels, in case of images).

But downscaling? I cant see how any interpolation technique can be used there. There are no blanks to fill!

Ive been stuck with this for far to long, give me a nudge in the right direction. How do you interpolate when you, in fact, remove known data?

Edit: Lets assume we have a one dimensional image, with one colour channel per point. A downscale algorithm scaling 6 to 3 points by average pixel value looks like this: 1,2,3,4,5,6 = (1+2)/2,(3+4)/2,(5+6)/2 Am I on the right track here? Is this interpolation in downscaling rather than just discarding data?

Answer 1

Here you have the original image on top, then a naive removal algorithm in the middle, and an interpolating one at the bottom.

Consider a big spotlight. The light at the center is the brightest, and the light at the edges become darker. When you shine it farther away, would you expect the light beam to suddenly lose the darkness near the edges and become a solid outline of light?

No, and the same thing is happening here to the stackoverflow logo. As you can see in the first downscaling, the picture has lost the softness in its edges and looks horrible. The second downscaling has kept the smoothness at the edges by averaging the pixel surroundings.

A simple convolution filter for you to try is to add the RGB values of the pixel and all other pixels surrounding it, and do a simple average. Then replace the pixel with that value. You can then discard the adjacent pixels since you've already included that information in the central pixel.

Answer 2

If one conceptualizes an original pixel as having a width n, then the center of the pixel is n/2 from either edge.

One may assume that this point, in the center of the pixel defines the color.

If you are downsampling, you can think about it this way conceptually: even though you are reducing the physical size, instead think that you are maintaining the same dimensions, but reducing the number of pixels (which are increasing in size - conceptually). Then one can do the math...

Example: say your image is 1 pixel high and 3 pixels wide, and you are only going to downscale horizontally. Lets say you are going to change this to 2 pixels wide. Now the original image is 3n, and you are turning it to 2 pixels, so therefore each new pixel will take up (3/2) of an original image pixel.

Not think about the centers again... the new pixels' centers are at (3/4)n and at (9/4)n [which is (3/4) + (3/2)]. The original pixels' centers were at (1/2)n, (3/2)n, and (5/2)n. Thus each center is somewhere between where we would find the original pixel's centers - none match up with the original pixels' centers. Let's look at the first pixel at (3/4)n - it is (1/4)n away from the original first pixel, and (3/4)n away from the original second pixel.

If we want to maintain a smooth image, use the inverse relationship: take (3/4) of the color values of the first pixel + (1/4) of the color values of the second, since the new pixel center, conceptually, will be closer to the first original pixel center (n/4 away) than it will be to the second (3n/4 away).

Thus one does not have to truly discard data - one just calculates the appropriate ratios from its neighbors (in a conceptual space where physical size of the total image is not changing). It is an averaging rather than a strict skipping/discarding.

In a 2d image the ratios are more complicated to calculate, but the gist is the same. Interpolate, and pull more of the value from the closest original "neighbors". The resultant image should look quite similar to the original provided the downsample is not terribly severe.

Answer 3

Whether upscaling or downscaling, the "interpolation" going on is in fact re-sampling.

If the number of samples in the scaled-down version is not an even divisor of the full number of samples (pixels, etc), simply discarding data will produce sampling errors that appear in an image as "jaggies". If instead, you interpolate where the new samples would lie in the space between the existing samples using one of the algorithms you mention, the results are much smoother.

You can conceptualize this as first scaling up to the least common multiple of the old and new size, then scaling back down by discarding samples, only without actually generating the intermediate result.

Answer 4

This sketch shows a section through a few pixels that start off as three pixels (black curve) and are downsampled to two pixels (red curve) using the interpolation (blue curve). The interpolation is determined from the original three pixels and the two final pixel are set to the value of the interpolation at the center of each final pixel. (In case it's unclear here, the vertical axis shows is the intensity of each pixel for a single color channel.)

alt text http://img391.imageshack.us/img391/3310/downsampling.png

Answer 5

Whether we're upscaling or downscaling, we need to determine (to some degree of accuracy) what the colour value at a point between two pixels will be.

Lets take a single row of pixels:

P     P     P     P     P     P     P     P     P

and we upsample, we want to know the pixel values to use at the in-between points:

P   P   P   P   P   P   P   P   P   P   P   P   P

and when we downsample, we also want to know the pixels values to use at the in-between points:

P       P       P       P       P       P       P

(Of course, we want to do this in two dimensions rather than one, but it's the same principle.)

So regardless, we need to interpolate to determine the right sample value. Depending on how accurate we want the results, there are different interpolation techniques. Ideally, we'd be properly resampling with all the maths involved... but even that is just interpolation done rigourously!

Answer 6

If you use a windowed sinc filter, such as lanczos, it actually filters out high frequency details that cannot be represented at the lower resolution. An averaging filter doesn't do this, causing artifacts. A sinc filter also produces a sharper image, and works for both upscaling and downscaling.

If you were to upscale an image with sinc, then downscale it back to the original size, you would get almost the exact same image back, whereas if you just averaged the pixels when downsizing, you would end up with something slightly blurrier than the original. If you used a fourier transform to resize, which the windowed sinc tries to approximate, you would get the exact original image back, apart from rounding errors.

Some people don't like the slight ringing around sharp edges that come from using a sinc filter though. I'd suggest averaging for downscaling vector graphics, and sinc for downscaling photos.