Compression - Why level-shift on JPEG?

Author

Why level-shift on JPEG?

Jackson

2004-09-23, 8:56 pm

Why does the JPEG spec perform a level-shift of 128, thus changing the
range from [0,255] to [-128, 127]? In some previous posts, someone
mentioned that it helps to achieve a greater precision when run
through the DCT. Another post said that it was to prevent 'overflow'
when running the #'s through the DCT. Are any of these ideas correct?
What is 'overflow' when running these #'s through DCT?

thanks,
Jackson

Phil Carmody

2004-09-24, 3:55 am

jsmith193300@yahoo.com (Jackson) writes:

> Why does the JPEG spec perform a level-shift of 128, thus changing the
> range from [0,255] to [-128, 127]? In some previous posts, someone
> mentioned that it helps to achieve a greater precision when run
> through the DCT. Another post said that it was to prevent 'overflow'
> when running the #'s through the DCT. Are any of these ideas correct?
> What is 'overflow' when running these #'s through DCT?

Take 8 random numbers between 0 and 255.
Take 8 more.
Evaluate the dot product of these vectors.
Repeat several times, see what range of values the dot product takes.

Now repeat the experiment with numbers between -128 and 127.

Et voila, the answer magically appears.

Phil
--
They no longer do my traditional winks tournament lunch - liver and bacon.
It's just what you need during a winks tournament lunchtime to replace lost
.... liver. -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'

Jackson

2004-09-24, 3:55 pm

Phil,

I ran the test, but the answer is not evident to me. Assuming I did
this right (it's very possible I did not) Here are the range values I
received:

[-16103, 24663] [87733,188900]
[-38029,20313] [60580,178870]
[-18894,4329] [67935,174585]

Thanks,
Jackson

Phil Carmody

2004-09-25, 8:57 am

jsmith193300@yahoo.com (Jackson) writes:

> Phil,
>
> I ran the test, but the answer is not evident to me. Assuming I did
> this right (it's very possible I did not) Here are the range values I
> received:
>
> [-16103, 24663] [87733,188900]
> [-38029,20313] [60580,178870]
> [-18894,4329] [67935,174585]

^ narrow range of expected values
^ wide range of expected values

Which requires more precision to store, a narrow range of values,
or a wide range?

Phil
--
They no longer do my traditional winks tournament lunch - liver and bacon.
It's just what you need during a winks tournament lunchtime to replace lost
.... liver. -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'

Korejwa

2004-09-28, 8:55 am

Phil:

I'm not an expert on this, nor am I a college student, nor do I have the
resources to experiment on this issue without investing many many hours of
my time.

I don't mean to be rude, but I'd really like a direct answer to this
question without having to spend a few w

s figuring it out for myself.
If you know why level-shifted values are prefered over all-positive
values, could you please fill us in? Thanks.

On 25 Sep 2004 13:28:03 +0300, Phil Carmody
<thefatphil_demunged@yahoo.co.uk> wrote:

> jsmith193300@yahoo.com (Jackson) writes:
>
>
> ^ narrow range of expected values
> ^ wide range of expected values
>
> Which requires more precision to store, a narrow range of values,
> or a wide range?
>
> Phil

Guido Vollbeding

2004-09-28, 8:55 am

Korejwa wrote:
>
> I don't mean to be rude, but I'd really like a direct answer to this
> question without having to spend a few w

s figuring it out for myself.
> If you know why level-shifted values are prefered over all-positive
> values, could you please fill us in? Thanks.

Here is another argument:
When you perform the DCT on the input samples, you end up with positive
_and_ negative AC coefficients in any way, *independent* from the level
of input samples! It is only the DC range which is dependent on the
input level!
In fact, in prior versions of my extended DCT module (see
http://jpegclub.org/cjpeg/jfdctint.c) I decided to avoid the input
level-shift completely - this has *no* influence on the calculation
of AC coefficients when properly done!
However, the DC calculation may be critical under certain circumstances,
that's why I abandoned that approach eventually.
If the inputs are not level-shifted, then the DC will also be not
level-shifted, and thus not be *conform* with the AC coefficients.
However, with level-shifted inputs the DC will also be level-shifted
and thus will have the same range as AC coefficients. This has
certain advantages especially in limited precision integer
implementations.

Regards
Guido

Guido Vollbeding

2004-09-28, 3:55 pm

> In fact, in prior versions of my extended DCT module (see
> http://jpegclub.org/cjpeg/jfdctint.c) I decided to avoid the input
> level-shift completely - this has *no* influence on the calculation
> of AC coefficients when properly done!
> However, the DC calculation may be critical under certain circumstances,
> that's why I abandoned that approach eventually.

BTW, the standard 8x8 DCT (and also 16x16 in my module) would still
work perfectly well with non-level-shifted inputs under any
circumstances! (Can level-shift only the DC *after* the calculation.)

However, for the new scaling features I have introduced special
*scaled* DCTs with fractional multipliers, and it is only due to
this feature that the moved level-shifting method doesn't work well
under *any* circumstances. I remark 'any' because it still worked
under 'usual' circumstances (full 32-bit integer arithmetic).
Only when using reduced 16x16=>32 bit optimized integer multiply
in the code would this method fail in these cases.
Therefore, for more generality, I retained the original
level-shifting of input samples.

Regards
Guido

Flavius Vespasianus

2004-10-30, 3:55 am

jsmith193300@yahoo.com (Jackson) wrote in
news:680af4.0409231610.75fdad0d@posting.google.com:

> Why does the JPEG spec perform a level-shift of 128, thus changing the
> range from [0,255] to [-128, 127]? In some previous posts, someone
> mentioned that it helps to achieve a greater precision when run
> through the DCT. Another post said that it was to prevent 'overflow'
> when running the #'s through the DCT. Are any of these ideas correct?
> What is 'overflow' when running these #'s through DCT?

The reason is that it reduces the possible ranges for the value of the DC
coefficient after running through the DCT.

Michael Spirko

2004-11-11, 3:55 pm

Flavius Vespasianus <nl@nl.com> wrote in message news:<twBgd.11205$KJ6.2391@newsread1.news.pas.earthlink.net>...
> jsmith193300@yahoo.com (Jackson) wrote in
> news:680af4.0409231610.75fdad0d@posting.google.com:
>
>
> The reason is that it reduces the possible ranges for the value of the DC
> coefficient after running through the DCT.

With my medium-level of understanding of programming, and low-level of
compression i will try to explain my thoughts. For the
compress/decompress to decipher weather an interger is possitive or
negative the simply need one byte... a 0 for a possitive number and a
1 for a negative number (or vise-versa). Now if the ranges we're [0,
255] the possiblility of an extra digit requires at least 2 extra
bytes. While this one byte difference doesn't seem like much... well
it's compression and it makes the compression more efficient with
ABSOLUTELY no decrease in quality.

Anyway, that's my understanding of it, if i'm totally faulty in my
reasoning please let me know, compression (especially fractal)
interests me a lot

Sponsored Links