Jump to content
  • Advertisement
Sign in to follow this  
circassia

Why Downsampling : 4 8 16 32

This topic is 2606 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi guys,

when i hear about downsampling i see all the time values like: 4 8 16 32: why? why can i not downsample by factor 5 or 7 ?

Would be nice, if someone could enlighten this novice :D

thanks

Share this post


Link to post
Share on other sites
Advertisement
Likely it's because power-of-2 downsampling is vastly simpler (and thus less computationally expensive) than arbitrary down-sampling. If you, say, halve the size of an image via down-sampling, then each pixel in the destination is an evenly weighted sum of a nice, tidy little 2x2 neighborhood of pixels in the destination (if using linear sampling). Arbitrary downsampling requires calculating weighting factors for sometimes odd-shaped neighborhoods in the original because destination pixels don't always fall in convenient sampling locations in the source image.

Share this post


Link to post
Share on other sites
You can downsample by a factor of 5 or 7 without problems. Just average a nice, tidy little 5x5 or 7x7 neighborhood of pixels.

Computer folk prefer powers of two because it's easy to think about them. For instance, you can implement the 2-fold reduction once and apply it several times if you want to reduce by a larger power of 2.

A more esoteric reason to prefer powers of two for reductions of images or other signals is that it fits well with wavelet analysis. But I don't really think that matters in any of the situations where you've seen people use powers of 2.

Share this post


Link to post
Share on other sites
When you downsample by 2, you can do so with only taking a single (bilinearly filtered) sample from the source texture, and it will give you a perfect result without artefacts such as shimmering -- because that 1 sample is located at the exact intersection of 4 source pixels, leading to a result pixel that is the average of all 4.
The same efficiency scales when downsampling by any power of 2.

Share this post


Link to post
Share on other sites

Arbitrary downsampling requires calculating weighting factors for sometimes odd-shaped neighborhoods in the original because destination pixels don't always fall in convenient sampling locations in the source image.

They are not only odd-shaped neighborhoods: resampling by arbitrary factors requires, instead of fixed FIR filters and fixed decimation, polyphase filters, in which different output samples alternate between sets of completely different filter coefficients rather than mere permutations of the same coefficients. This makes some straightforward FIR filter implementation impossible and adds an awful lot of coefficients for the same accuracy (i.e. for the same filter length).

Share this post


Link to post
Share on other sites

[quote name='FLeBlanc' timestamp='1319644350' post='4877242']
Arbitrary downsampling requires calculating weighting factors for sometimes odd-shaped neighborhoods in the original because destination pixels don't always fall in convenient sampling locations in the source image.

They are not only odd-shaped neighborhoods: resampling by arbitrary factors requires, instead of fixed FIR filters and fixed decimation, polyphase filters, in which different output samples alternate between sets of completely different filter coefficients rather than mere permutations of the same coefficients. This makes some straightforward FIR filter implementation impossible and adds an awful lot of coefficients for the same accuracy (i.e. for the same filter length).
[/quote]

Can you please explain how averaging regularly shaped 5x5 regions is a problem? He didn't suggest reducing by non-integer factors, so I don't know what you are talking about.

What Hodgman said makes sense: Reducing by a factor of 2 can be done very fat because hardware will do the averaging of a 2x2 region for you as a single bilinearly filtered texture lookup in the middle of the 2x2 region.

Share this post


Link to post
Share on other sites
I agree with alvaro. If downsizing by 2x is just averaging the 4 pixels, and downsizing by 4x is doing it again (so in effect, averaging the block of 16 pixels down to 1), then I don't see why a 3x downsize can't just average a 3x3 block of pixels down to 1, or 5x can't be averaging a 5x5 block of pixels down to 1.

If you want to scale down by non-integer amounts, I see how it would start to get weird, because then you don't have easily repeatable pixel boundaries. But 3x3, the 9 source pixels all perfectly fit into the result pixel, with even spacing and perfectly even weight. Just add the values and divide by 9.

Share this post


Link to post
Share on other sites

I agree with alvaro. If downsizing by 2x is just averaging the 4 pixels, and downsizing by 4x is doing it again (so in effect, averaging the block of 16 pixels down to 1), then I don't see why a 3x downsize can't just average a 3x3 block of pixels down to 1, or 5x can't be averaging a 5x5 block of pixels down to 1.

If you want to scale down by non-integer amounts, I see how it would start to get weird, because then you don't have easily repeatable pixel boundaries. But 3x3, the 9 source pixels all perfectly fit into the result pixel, with even spacing and perfectly even weight. Just add the values and divide by 9.


How would you treat the boundaries? You would need both the texture's width and height to be exactly divisible by three (or five, etc.). Powers of two are not exactly divisible by three (etc.), so you cannot use those numbers for downsampling power of two textures.

Share this post


Link to post
Share on other sites

[quote name='DracoLacertae' timestamp='1319834821' post='4877995']
I agree with alvaro. If downsizing by 2x is just averaging the 4 pixels, and downsizing by 4x is doing it again (so in effect, averaging the block of 16 pixels down to 1), then I don't see why a 3x downsize can't just average a 3x3 block of pixels down to 1, or 5x can't be averaging a 5x5 block of pixels down to 1.

If you want to scale down by non-integer amounts, I see how it would start to get weird, because then you don't have easily repeatable pixel boundaries. But 3x3, the 9 source pixels all perfectly fit into the result pixel, with even spacing and perfectly even weight. Just add the values and divide by 9.


How would you treat the boundaries? You would need both the texture's width and height to be exactly divisible by three (or five, etc.). Powers of two are not exactly divisible by three (etc.), so you cannot use those numbers for downsampling power of two textures.
[/quote]
Nor can you use a 2x2 downsampling on a power of three, or a power of five, texture without having special border cases.When you have a texture whose size isn't a multiple of the downsampling, you will have special border cases no matter what factor you use, not just non-two factors.

Share this post


Link to post
Share on other sites
It also has to do with banding around the edges, and being able to recursively down-sample all the way to a single pixel, as in MIP levels.

Think about down-sizing a 256x256 texture by a factor of 5 -- you get 2601 "full" samples plus 51 with 5 "real" samples + 20 "assumed" samples on the vertical and horizontal edges, plus a final sample with only 1 "real" sample and 24 "assumed" samples. Not very pretty, and that's even the naive approach -- maybe its better to center those 2601 "full" samples, leaving a half-pixel border around all edges, and dealing with some truly-weird samples like 2.5 "real" / 22.5 "assumed" or 0.25 "real" / 24.75 "assumed". for this reason you downsize by an even factor of the texture size.

For MIP levels, you ideally want the level with the smallest area to be a 1x1 pixel area that represents the average of all pixels in the original, and for that to happen you need to downsample at a rate which is a power that aligns with both the desired 1x1 size, and the native size of the source image. The de facto standard of power-of-two is largely historical, but will always play well with hardware based on binary states.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!