views:

1180

answers:

6

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?

+4  A: 

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.

Jeffrey Hantin
But scaling down with an even divisor (2, 4, 8) by simply discarding data also produce sampling errors, correct?
mizipzor
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.
sybreon
"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.
S.Lott
+3  A: 

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.

Demi
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?
mizipzor
if it is even you could average. There are many, many different ways to scale an image.
Demi
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).
Demi
+2  A: 
tom10
A: 

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!

Wuggy
+2  A: 
Unknown
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?
mizipzor
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.
Unknown
A: 

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.

David