How to calc 8-bit version of 16-bit scan value

[Wayne Fulton]

Using simple binary math in multiplication would otherwise result in a
maximum value of 255*256=65280, thus wasting potential accuracy of 255
values.

It doesnt waste anything. It simply misleads.

Remember the three men and bellhop and $30 problem about "what happened to
the missing dollar?" The early mislead reminds me of it... get them
started thinking wrong first, and then they cant figure out a simple
problem.

To convert 16 to 8 bits, simply shift it right 8 bits (which is the same
thing as /256, and the same thing as just using the high byte).

65535 is of interest because it is the largest possible number which can be
stored in 16 bits. It's value is FFFF in hex, which shows this limit.

Shift FFFF right 8 bits to give FF hex, which is 255 decimal.

255 is the largest possible number which can be stored in 8 bits,
and the FF hex shows this limit.

Shifting 8 bits (or dividing by 256) can retain all 256 possible unique
values 0 to 255.

However dividing by 257 results in only 255 possible results
(257x255=65535) and does not give every same numerical result (making it
wrong of course, although probably no one would ever notice).

Your 65280 is FF00, and shifting right 8 bits gives the same FF value.
Any value from 65280 to 65535 correctly gives 255 (as 8 bits).
This is linear beginning at zero - any value 0 to 255 gives 0.

Dividing 65535 by 256 is 255.996...

Yes, 255 is exactly the right answer, the only possible right answer.
255 is absolutely the largest conceivable or possible number that can be
stored in 8 bits, and so it is an extremely appropriate value to represent
the range of largest possible 16 bit numbers (65280..65535).

We cannot retain 16 bit precision in 8 bits.

 

[SJS]

My current formula is :

output = ((input / 65536) E (1 / 2.2)) * 256

I would like to thank everybody who has contributed to this thread.
My revised formula is :

output = ((((input + 1) / 65536) E (1 / 2.2)) * 256) - 1

However, this doesn't apply at light levels below 0.18 (11795/65536).
This is detailed on www.poynton.com/notes/colour_and_gamma/GammaFAQ.html
and explains how I can get 8-bit values of 1 or 2. I think my Canon
scanner applies the formula down to about half the above point but it is
so inconsistent that it is hard to be sure.

Thanks again to all. I apologise for any friction caused.

Regards,

Steven

 

[Kennedy McEwen]

For reference, all methods of converting 16-bit data to 8-bit should
result in *exactly* 256 sequential 16-bit numbers resulting in the same
8-bit result for *every* 8-bit value. Your proposed formula results in
257 16-bit numbers mapping to every 8-bit except for 0 and 255, which
have 128 each. Why do you want to discriminate against these levels?

Don't they teach basic arithmetic in schools any more?

It depends on the kind of math you use. For example, f(x) is a linear
function that maps [0 .. 65535] to [0.0 .. 1.0]. In other words, f(x)
can be written as f(x) = x / 65535.

Likewise, g(x) maps [0 .. 255] to [0.0 .. 1.0] and can be written as
g(x) = x / 255.

Now we need a function h(x) from [0 .. 65535] to [0 .. 255] such that
f(x) = g(h(x)). Now x/65535 = h(x) / 255 therefore, h(x) = 255 / 65535 =
1 / 257.

Fine up to that last part. Between 0 and 65535 inclusive there are 65536
states of equal weighting. Similarly, between 0 and 255 inclusive there
are 256 states. Hence each state in the smaller space is produced from
65536/256 = 256 states in the larger space. Rounding, up or down,
merely adds an offset to the data. Since we are dealing with two number
ranges which are positive integers, ie. there are no negative numbers to
round up to zero and no numbers can round up to greater than 255, the
rounding is simply truncation.

 

[Kennedy McEwen]

Don't they teach basic arithmetic in schools any more?

It depends on the kind of math you use. For example, f(x) is a linear
function that maps [0 .. 65535] to [0.0 .. 1.0].

Correct. Range mapping doesn't have to follow simple powers of 2 boundaries.

Exactly, but you need to take account of the number of unique states in
each range, not the upper limit only. Zero is an important mathematical
concept and is particularly relevant here.

For example, converting [0 .. 65535] to the range [-128 .. 127] also
maps 65536 states onto 256 states and hence the divisor for each of the
former to the latter is 65536/256 = 256. Were the latter range [-10 ..
15] then there would be 26 states, so the divisor is 65536/26 =
2520.'615384'

 

[Kennedy McEwen]

As I said, in binary integer calculation, shifting bits, and multiplying or
dividing by a power of 2 is correct, truncation is implicit in most
programming languages. But in this case we are trying to preserve as much
accuracy as possible when mapping(!) one range to another.

Using simple binary math in multiplication would otherwise result in a
maximum value of 255*256=65280, thus wasting potential accuracy of 255
values.


Range mapping is the name of the game. It is not erroneous, but intended
behavior!!!

Dividing 65535 by 256 is 255.996... (that is closer to 256 than 255, so you
prefer an error of almost 1 bit). Dividing 65535 by 257 is 255, a perfect
mapping of range maxima.

No, that is mere rounding, in terms of which states are mapped to each
other. Whilst 255.996 is closer to 256 than 255, the effect is matched
by an equal and opposite shift of numbers just below 255, and all the
way down the scale to 0. In your own words, range mapping is the name
of the game, not rounding to the nearest value!

 

[Philip Homburg]

For reference, all methods of converting 16-bit data to 8-bit should
result in *exactly* 256 sequential 16-bit numbers resulting in the same
8-bit result for *every* 8-bit value. Your proposed formula results in
257 16-bit numbers mapping to every 8-bit except for 0 and 255, which
have 128 each. Why do you want to discriminate against these levels?

Don't they teach basic arithmetic in schools any more?

It depends on the kind of math you use. For example, f(x) is a linear
function that maps [0 .. 65535] to [0.0 .. 1.0]. In other words, f(x)
can be written as f(x) = x / 65535.

Likewise, g(x) maps [0 .. 255] to [0.0 .. 1.0] and can be written as
g(x) = x / 255.

Now we need a function h(x) from [0 .. 65535] to [0 .. 255] such that
f(x) = g(h(x)). Now x/65535 = h(x) / 255 therefore, h(x) = 255 / 65535 =
1 / 257.

Fine up to that last part. Between 0 and 65535 inclusive there are 65536
states of equal weighting. Similarly, between 0 and 255 inclusive there
are 256 states. Hence each state in the smaller space is produced from
65536/256 = 256 states in the larger space. Rounding, up or down,
merely adds an offset to the data. Since we are dealing with two number
ranges which are positive integers, ie. there are no negative numbers to
round up to zero and no numbers can round up to greater than 255, the
rounding is simply truncation.

Arguments like this usually lead to the wrong results. You assume that
'there are 65536 states of equal weighting', but that is completely irrelevant
for pictures.

Furthermore, truncation leads to a much larger rounding error than 'normal'
rounding.

Basically your method preserves the shape of the histogram at the expense of
a larger delta-E. I guess most people would like to get the smallest delta-E.

 

[Bart van der Wolf]

SNIP

Shift FFFF right 8 bits to give FF hex, which is 255 decimal.

Which means you truncate (instead of round) at the expense of accuracy, thus
causing the error to be almost 1 bit (0.FF).
SNIP

However dividing by 257 results in only 255 possible results

No, it produces exactly 256 possible results, while reducing the error in
the process (e.g. 65535 / 256 = 255 + an error of 255/256, but 65535/257=255
+0).

It would be even more accurate to first add 127.5, as Chris Cox explained:
floor((65535 + 128) / 257) = 255 with the loss of precision evenly spread
around the result. The accuracy of that mapping is as good as can be
achieved in 8-bit precision.

Your 65280 is FF00,

It is not mine ;-) but it is the result of 255*256.

and shifting right 8 bits gives the same FF value. Any value from
65280 to 65535 correctly gives 255 (as 8 bits).

One should strive for an inaccuracy of no more than 128/255, but it
increases to 255/256.

SNIP

We cannot retain 16 bit precision in 8 bits.

Correct, but we can minimize the error to half a bit at most. In this I have
to agree with Chris Cox.

Bart

 

[Bart van der Wolf]

SNIP

I still don't think the 257 concept is correct.

I agree it is not optimal, but it is better than 256. Why not use floating
point and round the result to the nearest integer? Modern FPU
implementations are very fast.

Bart

 

[Bart van der Wolf]

Exactly, but you need to take account of the number of unique states in
each range, not the upper limit only.

Fair enough, but then you'll have to admit that neither 256 nor 257 by
themselves have a 'nice' error distribution.

Zero is an important mathematical concept and is particularly relevant

here.

True, but even if we divide with a restriction to use integers, shouldn't
the accuracy error be 128/255 at most? And how likely is a negative result
when we start with 16-bit values that are equal to, or larger than, zero.

To do justice to such a range mapping, while preserving half bit accuracy
and while avoiding negative numbers, one arrives at the solution that Chris
Cox gave. It really is a logical compromise.

Bart

 

[Kennedy McEwen]

Fair enough, but then you'll have to admit that neither 256 nor 257 by
themselves have a 'nice' error distribution.

No - its a perfectly nice error distribution as it is with 256, thank
you.

here.

True, but even if we divide with a restriction to use integers, shouldn't
the accuracy error be 128/255 at most?

What are you considering to be error? Rounding is merely an offset
shift, not a range error.

And how likely is a negative result
when we start with 16-bit values that are equal to, or larger than, zero.

Truncation can never give a negative result, both source and target
range are greater than zero.

To do justice to such a range mapping, while preserving half bit accuracy
and while avoiding negative numbers, one arrives at the solution that Chris
Cox gave. It really is a logical compromise.

No it isn't, division by 256 completely avoids any error. It is integer
arithmetic.

 

[Kennedy McEwen]

Arguments like this usually lead to the wrong results. You assume that
'there are 65536 states of equal weighting', but that is completely irrelevant
for pictures.

Arguments like this usually mean that the arguer doesn't understand why
it isn't irrelevant, whether for pictures or basic maths! Reminds me of
my old university maths lecturer - "It is obvious that..." meant it was
too difficult to explain in a one hour lecture, he had long forgotten
the argument himself or he had never understood it in the first place!

Furthermore, truncation leads to a much larger rounding error than 'normal'
rounding.

No, it leads to asymmetric "rounding" error, but a perfectly symmetric
truncation error. Rounding leads to greater truncation error. Who are
you to say which is better?

Basically your method preserves the shape of the histogram at the expense of
a larger delta-E. I guess most people would like to get the smallest delta-E.

No, the error is just the same 0 .. 0.999', as opposed to -0.5 ..
0.499'. So, given that the "delta-E" is just the same, which is better?

 

[Kennedy McEwen]

SNIP

I agree it is not optimal, but it is better than 256. Why not use floating
point and round the result to the nearest integer? Modern FPU
implementations are very fast.

Why not use floating point and truncate to the nearest integer? No
matter how fast modern FPU's are, shift right 8 is considerably faster
on most Intel and Motorolla CPUs. ;-)

 

[Wayne Fulton]

Which means you truncate (instead of round) at the expense of accuracy, thus
causing the error to be almost 1 bit (0.FF).

Rounding is a fine tool used to benefit arithmetic computation, but this
task is not computing anything. We already have perfectly good data and
the goal should be to NOT change it. This data is in the form of 65536
possible 16-bit values, and our only goal is to sort it into 256 possible
8-bit values, specifically exactly 256 equally spaced groups each holding
exactly 256 values.

The data values are of course already correctly divided this way by high
byte value (each possible high byte represents 256 possible and equally
spaced 16-bit values - the natural way). The result of the truncation
method (shift by 8 or divide by 256) simply groups the data in the way it
is already grouped by high byte values, without additional false
manipulation. There are precisely 256 equal groups, equally spaced over the
entire range (including perfectly at the end points), each group containing
precisely 256 values. It simply doesnt get any better. There is no issue
about rounding the values at all, nor is it about computing NEW values.

Accuracy is of course important, but I am more impressed with its
preservation than in any so-called halfbit accuracy of the +127/257
manipulation. You may think the range is better centered on the 8 bit
value, but it is already arranged in a different way which works extremely
well without exception.

Adding 127 to all values should be just the effect of rounding, with no
actual effect on the tonal linearity, unfortunately except at the
endpoints. It shortchanges the zero group to contain at most only 128
possible values 0..127, instead of the 256 values of 0..255. It also
similarly places too many values into the top group. These are not equal
divisions, and this change sure seems an error, modified data for no
necessary reason.

We know that physical devices know no absolute values for the brightness of
RGB data, each device type reproduces any numeric value as best it can,
different than other devices. Absolute accuracy is pretty much fictitious.
What is important instead is the linearity and the range of the data. The
truncation method gives importance to these factors which actually matter,
without changing the data at all, so I'd call that very accurate.

No, it produces exactly 256 possible results, while reducing the error in
the process (e.g. 65535 / 256 = 255 + an error of 255/256, but 65535/257=255
+0).

Surely your calculator shows the same as mine, that 257x255 = 65535.
Therefore dividing 65535 values by 257 obviously sorts into 255 groups of
257 values each. Granted, there are 65536 values, the extra value could be
another group (not calculated by your method however), but we have already
incorrectly used 255 of that groups values elsewhere. The +127 skew helps
hide this, but this is an approximation when none is needed, and I'd say a
serious error. The correct goal is obviously 256 equal groups of 256
values each, and the data is already equally grouped this way by high byte.
All we need for best result is what the data already says.

You stress that 65535 value, and the /257 scheme seems designed for it, but
it is only one of 65536 possible values. Either method gives 255 for it,
the absolute maximum value possible.

What about the 127 values 128 to 255? Only truncation correctly gives zero
for this set.

I doubt any actual visible harm from the +127/257 scheme, as any other
factor affecting scanned images is vastly larger. It seems wrong
nevertheless.

 

[Bart van der Wolf]

Why not use floating point and truncate to the nearest integer? No
matter how fast modern FPU's are, shift right 8 is considerably faster
on most Intel and Motorolla CPUs. ;-)

Hardly, if you do it once for a LUT (which can also reflect Gamma
adjustment). All subsequent conversions are mere lookups by index.

Bart

 

[Jens-Michael Gross]

No it isn't, division by 256 completely avoids any error. It is integer
arithmetic.

Let's make things easy:

Other range, same topic, simple test.
256 gray levels to 16 gray levels.
Simple way seems to be right-shifting the value by 4 (or dividing by
16).
The other solution would be adding 8 and then dividing by 17.

After doing both, simply compare the result with the original.
(16/256 gray levels are easy enough to differentiate for even the most
untrained eye)

The (strange for you) result is that the second looks _much_ closer to
the original.

Reason: Method one places the 'step' from one value to the next at the
end of a range of 16 values,
while the second method places the steps in the middle of a range of 17
values, with the first and last (black and white) having only half a
range. Which way better fits the reality.
In the first case, the maximum 'error' is 15 (a gray level of original
15 is still black, while 240 is considered maximum white) while the
second solution only has an error of 8 (black is 0..8, white is
247..255)

For 16 to 8 bit conversion the result is the same, but even for the
trained eye the difference is barely visible (definitely not on a
'normal' display or printer)

As someone else pointed out: "Range mapping doesn't have to follow
simple powers of 2 boundaries"

Unfortunately, most 'professional' programmers do not have the faintest
idea of the matter they're working on.
As haven't their (marketing) managers.
Results are programs like Word (offers everything but does nothing
right)

Grossibaer

 

[Jens-Michael Gross]

Rounding is a fine tool used to benefit arithmetic computation, but this
task is not computing anything. We already have perfectly good data and
the goal should be to NOT change it. This data is in the form of 65536
possible 16-bit values, and our only goal is to sort it into 256 possible
8-bit values, specifically exactly 256 equally spaced groups each holding
exactly 256 values.

Well, to prove your statement wrong just go the opposite way and
calculate a 16 bit value from the calculated 8 bit value:

65535/256 is 255. Well, right. but 255*256 = 65280. You're 255/65536 off
your original value.
65535/257 (with rounding) is 255 too. But 255*257 is 65535 again. Zero
error.

Another example:

65400/256 is 255. 255*256=65535. Error of 135.
65400/257 is 254. Rounding is calculated by adding 128 (better 127.5) to
the original value.
254*257=65278. Error of 122.

By simply dividing by 256, you'll get an error of 0 to +255, by adding
128 and then dividing by 257 you'll get an error from -128 to +128.
Which is closer to the original in all cases.

No math coprocessor is required, simple integer arithmetics (but no
register shifting).

Grossibaer

 

[Philip Homburg]

No, the error is just the same 0 .. 0.999', as opposed to -0.5 ..
0.499'. So, given that the "delta-E" is just the same, which is better?

Truncation gives an average error (assuming a uniform distribution) of
(close to) 0.5, rounding gives an average error of (close to) 0.25.

There is a reason rounding was invented. Truncation is much easier from
a computational point of view.

 

[Wayne Fulton]

Well, to prove your statement wrong just go the opposite way and
calculate a 16 bit value from the calculated 8 bit value:

65535/256 is 255. Well, right. but 255*256 = 65280. You're 255/65536 off
your original value.
65535/257 (with rounding) is 255 too. But 255*257 is 65535 again. Zero
error.

If 16 bits is needed, then it seems better not to convert to 8 bits first.

I'm curious though... if you convert 8 bit data to 16 bits this way, how do
you keep track of where the data came from, if the data was originally
divided by 256 or by 257? If someone sends you a file, do you ask them
about it? This seems really important if attempting to go back. <g>

Dividing 65535 by 256 gives 255. 255 is the absolute maximum value possible,
we cannot show more in 8 bits.

There is something wrong with dividing by 257 to convert to 8 bits.
There is something wrong with multiplying by 257 to convert to 16 bits.

Because the factor relating these modes 2^8 and 2^16 is obviously 2^8 or
256, in every respect, in every detail. There is no choice about this.

Even if you choose to round by adding 128, the divisor should still be 256,
256 groups each with 256 values, because exactly 256 groups are required, to
match the 256 possible 8 bit values 0..255. Any other choice changes the
distribution. Of course the rounding skews it too, I wouldnt. Dividing by
257 helps hide it, but again, I wouldnt.

This mythical "half bit of accuracy" is very misplaced here. Due the lack
of absolutes, the original data simply isnt nearly that accurate. We were
taught in school about the folly of excessive "accuracy". What is
important is to preserve the distribution of the original data values,
without manipulation. The 16 bit data is already divided very well,
naturally, courtesy of the binary numbering system. Just use the high byte
value, as is. There are various ways to access it, dividing by 256 is one
of them. But use it as it is in the data... dont change the data.

It's the same concept we use for other purposes, for example to sort history
dates into centuries. Centuries are defined as 100 years, so we divide by
100 to place both 1900 and 1999 with the 1900s.
We never add 50 and divide by 101 <g> That does not improve accuracy.

 

[Kennedy McEwen]

Let's make things easy:

Other range, same topic, simple test.
256 gray levels to 16 gray levels.
Simple way seems to be right-shifting the value by 4 (or dividing by
16).
The other solution would be adding 8 and then dividing by 17.

After doing both, simply compare the result with the original.
(16/256 gray levels are easy enough to differentiate for even the most
untrained eye)

The (strange for you) result is that the second looks _much_ closer to
the original.

I disagree - take your example to the full extreme, a binary image with
only black or white. Two states in the final range, 256 states in the
initial range, divide by 256/2 = 128 to get from initial to final using
the "normal" approach or by what, 255/1=255?, using the alternative
method? Which looks more "natural"!

 

[Kennedy McEwen]

Truncation gives an average error (assuming a uniform distribution) of
(close to) 0.5, rounding gives an average error of (close to) 0.25.

All of that depends on where your baseline is drawn from - the centre of
the range or the transition points.

There is a reason rounding was invented. Truncation is much easier from
a computational point of view.

Of course there is a reason - symmetry when dealing with negative
numbers. Truncation rounds positive numbers down in magnitude but
negative numbers up. Images are coded in positive only integers though,
so the reason for rounding is irrelevant.