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?

Novice

Your edit has the correct idea. 1,2,3,4,5,6 -> 1.5, 3.5, 5.5. Another example is 6,0,6,0,6,0 -> 3, 3, 3; which is better than 0,0,0 or 6,6,6. – Trichloride

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.

Marishamariska

So a one dimensional downscale algorithm that counts average could look like this (6 points down to 3 points): 1,2,3,4,5,6 = (1+2)/2,(3+4)/2,(5+6)/2. Correct? Here, the sample grid includes two points during scale, but should I sample more points in more directions anyway? – Novice

Yes you could do it that way. More samples generally means better pictures, but you should be wary. Pixels that are far away from the new kernel should usually contribute less to the new pixel than one that is close. – Marishamariska

I think the images are missing. Or did you really want to display this image of DVD cover? Could you repost the images please? It would help a lot. – Byte

Apparently Imgur has assigned the original image's URL to another, unrelated, image? – Farron

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.

Revive

Very nice answer, I needed a pen and paper to go along but I think Ive got it now. But assuming we divide the size with some even number (2,4,8) so that the sample grid aligns perfectly with the old pixel grid. Would I then always take an equal amount of pixel data from each pixel within each cell of the sample grid? – Novice

if it is even you could average. There are many, many different ways to scale an image. – Revive

Another way to think about it is in the same conceptual manner where the physical size won't change but the width of the pixel does, but instead taking into account how many original pixels and how much of each pixel the new pixel consumes. This would work nicely on even numbers (e.g. when scaling horizontally from 4 pixels to 2, each new pixel would consume two old pixels - average them equally). – Revive

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.

Sympathy

But scaling down with an even divisor (2, 4, 8) by simply discarding data also produce sampling errors, correct? – Novice

Yes, it will definitely not be the same as 'actually' re-sampling the source data. However, interpolation 'guesses' where things may be but it does not guarantee that they are actually there. You will need to re-sample the original data if you want it to be accurate. – Metric

"Averaging" is better than discarding -- it can produces a smoother downscaled result. In some cases, more sophisticated filters are used to weight groups of points when downscaling. When downscaling a 2-d image, you'll have to cluster many points, not just a few adjacent points. – Antipope

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

Trichloride

Can you restore the image? – Dammar

@nobar: sorry, but I have no idea where the image went and certainly don't have a 5 year old copy. Hopefully SO or imageshack will restore it... do you know how long it's been gone? Otherwise, I may get a chance to redo it, but I don't have that now. – Trichloride

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!

Outrange

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.

Eicher