Effective bit depth of averaged pixels?

[leright]

Hello,

I am trying to figure out how many effective bits of color depth are carried in the red channel of a number of averaged pixels.

For instance, a single 24 bit pixel carries 8 bits per color channel (RGB). Therefore, you can generate 2^8 = 256 red levels, 2^8 = 256 green levels, and 2^8 = 256 blue levels. Now, let's say you take n pixels and average them together. The total number of averaged red values is the number of combinations you can generate with n pixels, where each pixel can carry 256 possible red values. If I knew the number of combinations I could generate then I could easily determine the number of "effective" bits. 2^b = # of combinations, where b is the number of effective bits.

So, how many combinations of red channel values can I generate with n pixels, where each pixel can have 256 different red channel values?

 

[rbj]

you might want to be more specific by what you mean by "effective". every time you average a pair of numbers with identical bit depth, you gain one additional bit (just as would happen when you add two numbers of the same bit depth). if you are thinking of noise level resulting in quantization, then every time you average four numbers with the same bit depth, then you gain one more effective bit even though there are actually two extra bits. in that case, the LSB is a noisy bit.

 

[Redbelly98]

For n pixels of 256 levels each, we would have 256ⁿ possible combinations.

If you simply take the sum of the n pixel values, you would have 256*n possible values.

 

[leright]

For n pixels of 256 levels each, we would have 256ⁿ possible combinations.

I don't think this is correct. This is the total number of permutations. for instance, if we have 4 pixels and we have the values 1, 6, 20, and 35, then all of the permutations of these 4 numbers are identical combinations and therefore produce the same average. I need the total number of unique combinations, not the total number of permutations.

 

[Redbelly98]

I always get "permutations" and "combinations" mixed up. Sorry.
Yes, 256^n is the number of permutations. For example, [1,6,20,25] is different than [6,1,20,25]If you really want the total number of combinations, that is more difficult because we are allowed to repeat numbers. From the "combinations with repetition" section near the bottom of this page:
http://www.mathsisfun.com/combinatorics/combinations-permutations.html ,
I get that the answer is

$$\frac{(256+4-1)!}{4! \ (256-1)!} = \frac{256 \cdot 257 \cdot 258 \cdot 259}{4!}$$

or more generally, for n pixels:

$$\frac{(256+n-1)!}{n! \ (256-1)!}$$

However:
If you are just going to take the average of the pixel values, there are actually
255*n + 1
possibilities. In this case different combinations will produce the same result. For example, [1,6,20,25] and [2,5,20,25] have the same sum (52) or average (13).

The possible averages, if it is 4 pixels, are:
0
0.25
0.5
0.75
1
...
254
254.25
254.5
254.75
255

That's 255*4+1 or 1021 possible values. The formula I gave in post #3, 254*n, was an approximation to this when I hadn't thought things through thoroughly.

Hope that helps clear things up.

 

[leright]

I always get "permutations" and "combinations" mixed up. Sorry.
Yes, 256^n is the number of permutations. For example, [1,6,20,25] is different than [6,1,20,25]If you really want the total number of combinations, that is more difficult because we are allowed to repeat numbers. From the "combinations with repetition" section near the bottom of this page:
http://www.mathsisfun.com/combinatorics/combinations-permutations.html ,
I get that the answer is

$$\frac{(256+4-1)!}{4! \ (256-1)!} = \frac{256 \cdot 257 \cdot 258 \cdot 259}{4!}$$

or more generally, for n pixels:

$$\frac{(256+n-1)!}{n! \ (256-1)!}$$

However:
If you are just going to take the average of the pixel values, there are actually
255*n + 1
possibilities. In this case different combinations will produce the same result. For example, [1,6,20,25] and [2,5,20,25] have the same sum (52) or average (13).

The possible averages, if it is 4 pixels, are:
0
0.25
0.5
0.75
1
...
254
254.25
254.5
254.75
255

That's 255*4+1 or 1021 possible values. The formula I gave in post #3, 254*n, was an approximation to this when I hadn't thought things through thoroughly.

Hope that helps clear things up.

yeah, I need to determine how many unique averages I can generate with n pixels and 256 values per pixel. that looks right. However, is there a more rigorous way to prove the above expression, other than listing the possibilities?

Thanks.

 

[Redbelly98]

You're welcome.

You probably realize this, but if the average gets rounded off to an integer, then you're stuck at 256 no matter how many pixels are averaged.

 

[leright]

You're welcome.

You probably realize this, but if the average gets rounded off to an integer, then you're stuck at 256 no matter how many pixels are averaged.

yeah, I realize that. The average isn't being rounded.

How do I prove, without listing possibilities, how many unique averages there are?

Thanks

 

[rbj]

The average isn't being rounded.

How do I prove, without listing possibilities, how many unique averages there are?

i think that number is simply the number of levels per pixel times the number of pixels being averaged. the number of unique averages there are is the same number as the number of unique sums.

so every time you double the number of pixels being averaged, you increase the bit depth by one bit if, by "bit depth", you mean the number of bits necessary to not lose any information. but if you quadrupled the number if pixels averaged, even though you might think you need to add two bits to the bit depth, the LSB is noisy and you've really only increased your number of meaningful bits by 1. that is an issue of noise and information theory.

 

[leright]

i think that number is simply the number of levels per pixel times the number of pixels being averaged. the number of unique averages there are is the same number as the number of unique sums.

so every time you double the number of pixels being averaged, you increase the bit depth by one bit if, by "bit depth", you mean the number of bits necessary to not lose any information. but if you quadrupled the number if pixels averaged, even though you might think you need to add two bits to the bit depth, the LSB is noisy and you've really only increased your number of meaningful bits by 1. that is an issue of noise and information theory.

ok, I am confused now. I will think about thi some more and get back with you. :)

Thanks everyone for your help.

 

[Redbelly98]

You need three numbers to get the total number of possible average values:

1. The lowest possible average value
2. The highest possible average value
3. The increment in possible average values.

For #1, use the least possible pixel value for all pixels (=0)
For #2, use the highest possible value for all pixels (=255)
For #3, how much does the average change if you increase the value of one pixel element by 1, and leave the remaining pixels the same? Answer: 1/n

From these, you can get the total number possible.

 

[leright]

This makes sense.

Thanks

You need three numbers to get the total number of possible average values:

1. The lowest possible average value
2. The highest possible average value
3. The increment in possible average values.

For #1, use the least possible pixel value for all pixels (=0)
For #2, use the highest possible value for all pixels (=255)
For #3, how much does the average change if you increase the value of one pixel element by 1, and leave the remaining pixels the same? Answer: 1/n

From these, you can get the total number possible.