Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1509 > unrolled thread

IJG arithmetic coding option broken

Back to article view | Back to comp.compression

Contents

  IJG arithmetic coding option broken Thomas Richter <thor@math.tu-berlin.de> - 2012-09-10 09:57 +0200
    Re: IJG arithmetic coding option broken Sven Köhler <remove-sven.koehler@gmail.com> - 2012-09-10 15:00 +0200
      Re: IJG arithmetic coding option broken Thomas Richter <thor@math.tu-berlin.de> - 2012-09-10 15:09 +0200
    Re: IJG arithmetic coding option broken Thomas Richter <thor@math.tu-berlin.de> - 2012-09-10 20:20 +0200

#1509 — IJG arithmetic coding option broken

Hi folks,

JPEG delivered and still delivers for quite a while reference test 
streams for JPEG, as part of the "reference testing procedure" defined 
in 10918-2, and ITU-T.83. These test streams are supposed to be used to 
verify the correctness of implementations, and to help implementers to 
identify defects in their code.

Apparently, Guido Vollbeding (one and only member of IJG) never actually 
did these tests, despite claiming to be compliant. I tried now, in the 
meantime, to see how much of these claims are valid and how far 
"compliance" really goes.

Point one is that IJG actually decodes *zero* of the delivered reference 
streams, and I counted twice. Ok, admittedly, most of them for quite 
obvious and irrelevant reasons, as for example our test streams have 
four or 254 components, something IJG does not handle.

So might it as it is - let's say we can ignore such examples as they are 
probably not very relevant for practical applications.

Nevertheless, there is a big big bug in the arithmetic coding 
implementation. The good news is that the Huffman coding (what you all 
use) seems to be correct, and progressive seems to be correct, but 
arithmetic coding is broken, and if anyone from IJG - that is Guido - 
would have dared to try reference testing as required by the standard, 
he would have noticed.

Trouble is as follows: The arithmetic coding option classifies 
probabilities into several "bins", each bin defines a probability 
estimate. These are also called "contexts" for those of you that are 
aware of the Q coder and its variants - QM coder in the case of JPEG.

Now, while JPEG specifies quite a number of contexts, it also defines 
that *each component* in a scan has to have an *independent set* of 
contexts, i.e. the probability estimates are to be done separately for 
each component (as every good engineer would do). Unfortunately, the IJG 
code uses the same context set, independent of the component.

To verify this problem, download the ITU-T.83 test streams (identical to 
10918-2, JPEG reference testing), in particular test stream D1.JPG from 
process_3.zip. Even if the IJG code is drilled up to support four 
components, this stream is not decoded correctly and the code runs into 
JPEG markers.

If you don't believe reference testing, also read Annex F.2.4. of 
ITU.T-81 (10918-1), the clause that defines the arithmetic coding 
option, *very carefully* and you see what was intended.

IOW, *avoid* the IJG arithmetic coding option - at least if you use more 
than one component per scan - it is broken, and everyone can verify that 
it is.

I mailed to Guido, but he denies that there is a problem (actually, 
without even looking at the reference streams), so I'm publishing it 
here in the hope to avoid further damage, and to invite people to test 
themselves.

It also sheds a certain "light" on this implementation, and on how 
"careful" it is tested against the correct implementation of the 
specifications.

For those of you who want to test and see, here are the streams from the 
ITU, for everyone free to download:

http://www.itu.int/net/itu-t/sigdb/speimage/ImageForm-s.aspx?val=1010083

So long,
	Thomas

[toc] | [next] | [standalone]

#1510

Am 10.09.2012 09:57, schrieb Thomas Richter:
> IOW, *avoid* the IJG arithmetic coding option - at least if you use more
> than one component per scan - it is broken, and everyone can verify that
> it is.

Basically, you're talking about libjpeg, which is pretty much the
standard jpg library shipped by many linux distribution, right?

Did you test popular derivates (for example libjpeg-turbo) as well?


Regards,
  Sven

[toc] | [prev] | [next] | [standalone]

#1511

Am 10.09.2012 15:00, schrieb Sven Köhler:
> Am 10.09.2012 09:57, schrieb Thomas Richter:
>> IOW, *avoid* the IJG arithmetic coding option - at least if you use more
>> than one component per scan - it is broken, and everyone can verify that
>> it is.
>
> Basically, you're talking about libjpeg, which is pretty much the
> standard jpg library shipped by many linux distribution, right?

I am, indeed.

> Did you test popular derivates (for example libjpeg-turbo) as well?

Actually, I didn't. If it uses the same arithmetic coding methods as the 
IJG code, or is based on the IJG code, chances are better than even that 
it is broken, too.

But anyhow, I can only recommend(!) every implementer to test the 
implementation against the ISO/ITU test streams I posted above. This is 
what they are good for. (-;

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1512

Am 10.09.2012 09:57, schrieb Thomas Richter:
> Hi folks,
>

I stand corrected! It is actually more complicated than what I thought - 
the trouble is that the context model depends on the table descriptor of 
the corresponding component, not on the component number - and the D1 
file actually uses four different AC table descriptors and hence four 
different tables. The same is not the case for some other streams, thus 
the trouble.

Sorry folks, this one is definitely my fault and goes on my bill. So 
everything should be in proper order.

So long,
	Thomas

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web