Huffman code length 16 in lossless JPEG
Dave Harvey
about lossless compression, and I wonder if anyone can provide or point me
to an authoratative answer.
The question concerns Huffman codes of length 16, and their interpretation:
The Cornell lossless code, and my limited JPEG texts suggest that a 16 bit
code should be trated just like any other, but:
GE images (both the old faulty version and the new corrected implementation)
require that the value of any difference with a code length of 16 should
always be 32768 (0x8000).
There are images around that use both formats, and I would like to be able
a) to know which are which to enable correct decoding
b) to know which is the definitive "correct" answer for my own output files.
Any thoughts would be mcuh appreciated.
Dave Harvey
Medical Connections
Tom Lane
> The question concerns Huffman codes of length 16, and their interpretation:
> The Cornell lossless code, and my limited JPEG texts suggest that a 16 bit
> code should be trated just like any other, but:
> GE images (both the old faulty version and the new corrected implementation)
> require that the value of any difference with a code length of 16 should
> always be 32768 (0x8000).
I think you are confusing Huffman code length with number of bits in
the difference value.
There isn't any particular difference between Huffman *codes* of
length 16 bits and codes of any other length in JPEG (but recall
that the JPEG spec puts an upper limit of 16 on the bit length
of Huffman codes).
However, if you are encoding 16-bit lossless data, there definitely
is a special case for *magnitude category* 16. The only possible
member of that category is difference 32768, so the JPEG spec says
that *no* extra bits should be emitted after the Huffman code for
magnitude category 16, rather than the 16 extra bits that you might
expect. The decoder is supposed to know that the difference must
be 32768 when it decodes that Huffman symbol.
The authoritative reference for this is section H.1.2.2 and table
H.2 of ISO 10918-1.
A quick look at the Cornell lossless codec (June 1994 release) shows
that it is *clearly wrong* on this point, because it does not make a
special case for nbits=16. The case is fairly improbable (and can't
happen at all for sample depths less than 16) so it's not too
surprising that the bug escaped detection.
The PVRG lossless codec (v1.2.1) looks like it gets it right.
I do not know whether GE gets it right or not.
I have heard a couple of people assert that the Cornell codec is
unreliable for bit depths > 8, but I couldn't say whether this is
its only problem. It'd be a pretty trivial fix if this is the
only bug for high-depth data...
> There are images around that use both formats, and I would like to be able
> a) to know which are which to enable correct decoding
I don't see any reliable way to cope with both correct and incorrect
files, unless you want to try to intuit from the header markers which
encoder produced a file :-(. Perhaps you should just offer both
"right" and "wrong" ways of decoding, and let the user try the other
one if one does not work --- or maybe even automatically retry if you
detect corrupted input, as you likely would when reading a file with
the wrong choice.
regards, tom lane
organizer, Independent JPEG Group
med...@dial.pipex.com
> I think you are confusing Huffman code length with number of bits in
> the difference value.
...
> However, if you are encoding 16-bit lossless data, there definitely
> is a special case for *magnitude category* 16. The only possible
> member of that category is difference 32768, so the JPEG spec says
> that *no* extra bits should be emitted after the Huffman code for
> magnitude category 16, rather than the 16 extra bits that you might
> expect. The decoder is supposed to know that the difference must
> be 32768 when it decodes that Huffman symbol.
...
> A quick look at the Cornell lossless codec (June 1994 release) shows
> that it is *clearly wrong* on this point, because it does not make a
> special case for nbits=16.
I must admit to being a DICOM rather than a compression specialist, so please
excuse my erroneous terminology.
The information is, however, just what I need for my fix. In fact, I have had
a decode fix for a long time, but had viewed it as just one of the many GE
oddities, and it was only when I read GE images _without_ the other errors,
that I realised that I/Cornell may be the ones wrong on this point.
> The case is fairly improbable (and can't
> happen at all for sample depths less than 16) so it's not too
> surprising that the bug escaped detection.
In fact, its NOT uncommon in 16 bit medical images, as the very first pixel
often has a value of 0 (in MRI anyway), and as the predictor for the first
pixel is half the full range, the first difference is normally...32768 !
> I don't see any reliable way to cope with both correct and incorrect
> files, unless you want to try to intuit from the header markers which
> encoder produced a file :-(. Perhaps you should just offer both
> "right" and "wrong" ways of decoding, and let the user try the other
> one if one does not work --- or maybe even automatically retry if you
> detect corrupted input, as you likely would when reading a file with
> the wrong choice.
I knew the implementation UID value had to have some use, but until this, I
hadn't reckoned what it was. I'll probably put a list of known "faulty"
implementation UIDs in a registry key (this will include my own previous
versions), and maintain the old read behaviour for such images. Of course, if
anyone knows a better way, I'd still be open to ideas.
Anyway TOM, thanks again for your _very_ helpful reply
Dave Harvey
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own