I see that paq8h can compress jpeg files.  Is this lossy compression?

Jon.

jondelac@gmail.com wrote:
> I see that paq8h can compress jpeg files.  Is this lossy compression?

No, 100% lossless

Fulcrum wrote:
> jondelac@gmail.com wrote:
> > I see that paq8h can compress jpeg files.  Is this lossy compression?
>
> No, 100% lossless

Hi,
I hate asking questions when source is available, but I must admit the
code is difficult to follow...

I am very familiar with PAQ and the techniques used in most PAQ
versions...
Do you know what the general logic (idea) is that is being used in
paq8h to get better predictions on the DCT coef values?  I see that the
zigzag is undone and that the author is walking the DCT matrices in
natural order... but what is the logic behind the predictions?  I dont
understand the role of the basic prediction function... it seems to be
accessing the coef values in some sort of pattern to provide the
predictor some context and in addition, the prediction is put through
some sort of secondary sequensing... what exactly is going on here?

Jon.

Fulcrum wrote:
> jondelac@gmail.com wrote:
> > I see that paq8h can compress jpeg files.  Is this lossy compression?
>
> No, 100% lossless

Hi,
I hate asking questions when source is available, but I must admit the
code is difficult to follow...

I am very familiar with PAQ and the techniques used in most PAQ
versions...
Do you know what the general logic (idea) is that is being used in
paq8h to get better predictions on the DCT coef values?  I see that the
zigzag is undone and that the author is walking the DCT matrices in
natural order... but what is the logic behind the predictions?  I dont
understand the role of the basic prediction function... it seems to be
accessing the coef values in some sort of pattern to provide the
predictor some context and in addition, the prediction is put through
some sort of secondary sequensing... what exactly is going on here?

Jon.

jondelac@gmail.com wrote:
> Fulcrum wrote:
> > jondelac@gmail.com wrote:
> > > I see that paq8h can compress jpeg files.  Is this lossy compression?
> >
> > No, 100% lossless
>
> Hi,
> I hate asking questions when source is available, but I must admit the
> code is difficult to follow...
>
> I am very familiar with PAQ and the techniques used in most PAQ
> versions...
> Do you know what the general logic (idea) is that is being used in
> paq8h to get better predictions on the DCT coef values?  I see that the
> zigzag is undone and that the author is walking the DCT matrices in
> natural order... but what is the logic behind the predictions?  I dont
> understand the role of the basic prediction function... it seems to be
> accessing the coef values in some sort of pattern to provide the
> predictor some context and in addition, the prediction is put through
> some sort of secondary sequensing... what exactly is going on here?
>
> Jon.

The program parses the jpeg image into Huffman codes, then predicts the
next code using the decoded image as context.  The decoding is only
back to the DCT coefficients (the lossless part), not back to the
original image.  The most useful context is just the u,v coordinates
and color, but there are many other contexts that also improve
compression a bit.

The algorithm is different than the one used by Stuffit, according to
their patent application.  (I did not patent anything in the paq8
algorithm).  Stuffit transforms the jpeg image back to the DCT
coefficients and compresses that directly using a context model.
During decompression, it has to transform the coefficients back to the
jpeg image.  paq8 is different in that there is no conversion back to
jpeg.  The decoding to DCT is done by both the compressor and
decompressor to get context.  However, Stuffit gets better compression.

-- Matt Mahoney

Matt Mahoney wrote:
> jondelac@gmail.com wrote:
> > Fulcrum wrote:
> > > jondelac@gmail.com wrote:
> > > > I see that paq8h can compress jpeg files.  Is this lossy compression?
> > >
> > > No, 100% lossless
> >
> > Hi,
> > I hate asking questions when source is available, but I must admit the
> > code is difficult to follow...
> >
> > I am very familiar with PAQ and the techniques used in most PAQ
> > versions...
> > Do you know what the general logic (idea) is that is being used in
> > paq8h to get better predictions on the DCT coef values?  I see that the
> > zigzag is undone and that the author is walking the DCT matrices in
> > natural order... but what is the logic behind the predictions?  I dont
> > understand the role of the basic prediction function... it seems to be
> > accessing the coef values in some sort of pattern to provide the
> > predictor some context and in addition, the prediction is put through
> > some sort of secondary sequensing... what exactly is going on here?
> >
> > Jon.
>
> The program parses the jpeg image into Huffman codes, then predicts the
> next code using the decoded image as context.  The decoding is only
> back to the DCT coefficients (the lossless part), not back to the
> original image.  The most useful context is just the u,v coordinates
> and color, but there are many other contexts that also improve
> compression a bit.
>
> The algorithm is different than the one used by Stuffit, according to
> their patent application.  (I did not patent anything in the paq8
> algorithm).  Stuffit transforms the jpeg image back to the DCT
> coefficients and compresses that directly using a context model.
> During decompression, it has to transform the coefficients back to the
> jpeg image.  paq8 is different in that there is no conversion back to
> jpeg.  The decoding to DCT is done by both the compressor and
> decompressor to get context.  However, Stuffit gets better compression.
>
> -- Matt Mahoney


Few questions...

1. In paq8h, what is the context algorithm... as in, what is the
formula for the context to predict the next bit?  From your reply, I
understand it is the u, v and color components... but can you explain
how you extract that... as in, when you are trying to predict a ceof in
the compressor, which previous y, u and color values are you using for
the bit of the current coef you are trying to predict?

2. From the stuffit transform you describe, are you saying that stuffit
decodes beyond the DCT and goes to the actual image and that is where
it is different from paq8h?  In that case, wouldnt stuffit introduce
lossyness?  I am reading your email as saying, paq8h gets its context
from DCT and stuffit gets its context from the actual image... is that
correct?

Jon.

jondelac@gmail.com wrote:
> Matt Mahoney wrote:
> > jondelac@gmail.com wrote:
> > > Fulcrum wrote:
> > > > jondelac@gmail.com wrote:
> > > > > I see that paq8h can compress jpeg files.  Is this lossy compression?
> > > >
> > > > No, 100% lossless
> > >
> > > Hi,
> > > I hate asking questions when source is available, but I must admit the
> > > code is difficult to follow...
> > >
> > > I am very familiar with PAQ and the techniques used in most PAQ
> > > versions...
> > > Do you know what the general logic (idea) is that is being used in
> > > paq8h to get better predictions on the DCT coef values?  I see that the
> > > zigzag is undone and that the author is walking the DCT matrices in
> > > natural order... but what is the logic behind the predictions?  I dont
> > > understand the role of the basic prediction function... it seems to be
> > > accessing the coef values in some sort of pattern to provide the
> > > predictor some context and in addition, the prediction is put through
> > > some sort of secondary sequensing... what exactly is going on here?
> > >
> > > Jon.
> >
> > The program parses the jpeg image into Huffman codes, then predicts the
> > next code using the decoded image as context.  The decoding is only
> > back to the DCT coefficients (the lossless part), not back to the
> > original image.  The most useful context is just the u,v coordinates
> > and color, but there are many other contexts that also improve
> > compression a bit.
> >
> > The algorithm is different than the one used by Stuffit, according to
> > their patent application.  (I did not patent anything in the paq8
> > algorithm).  Stuffit transforms the jpeg image back to the DCT
> > coefficients and compresses that directly using a context model.
> > During decompression, it has to transform the coefficients back to the
> > jpeg image.  paq8 is different in that there is no conversion back to
> > jpeg.  The decoding to DCT is done by both the compressor and
> > decompressor to get context.  However, Stuffit gets better compression.
> >
> > -- Matt Mahoney
>
>
> Few questions...
>
> 1. In paq8h, what is the context algorithm... as in, what is the
> formula for the context to predict the next bit?  From your reply, I
> understand it is the u, v and color components... but can you explain
> how you extract that... as in, when you are trying to predict a ceof in
> the compressor, which previous y, u and color values are you using for
> the bit of the current coef you are trying to predict?

A lot of the code is just decoding the jpeg image, parsing the headers,
saving the Huffman tables, discarding stuff I don't need like
quantization tables, JFIF headers, comments, etc, then converting
Huffman codes to RS codes and then back to the DCT coefficients in
zigzag order, and computing the u,v coordinates for context.  Then just
like the other models, various contexts are used as indexes to bit
histories (8 bit states), which are then adaptively mapped to
probabilities (StateMaps), which are then combined using neural
networks (Mixers) selected by small contexts, then adjusted using
secondary symbol estimatiton (APM), which adaptively map a probability
and additional small context to a new probability.  Finally the
predicted bits are arithmetic coded.  The jpeg model differs from the
others in that it has its own ContextMap to deal with Huffman codes
that don't fall on byte boundaries.  There is a hash table lookup every
third bit to index a hash table which contains 7 bit histories for the
cases of appending 0, 1, or 2 bits to the major context.  In the normal
ContextMaps, which are optimized for byte aligned contexts, there is a
hash table lookup every 2, 3, 3 bits and there is collision detection.

> 2. From the stuffit transform you describe, are you saying that stuffit
> decodes beyond the DCT and goes to the actual image and that is where
> it is different from paq8h?  In that case, wouldnt stuffit introduce
> lossyness?  I am reading your email as saying, paq8h gets its context
> from DCT and stuffit gets its context from the actual image... is that
> correct?
>
> Jon.

No, Stuffit also decodes back to the DCT coefficients, not the image.
It is different because Stuffit compresses the coeffients, not the
Huffman codes.  This means the decompressor has to do the reverse
transform to convert back to jpeg.  This doubles the amount of code
needed for modeling and introduces possible loss of data if not careful
to restore tables, headers, restart codes, etc. exactly as they were.
I thought about doing it this way but it would have been extra work,
and I didn't know if it would work any better (which it apparently
does).  I do have framework code in paq8x to test the reverse transform
at compress time to ensure it matches the input and abandon the
transform if there is a mismatch, so I could have done the transform
reliably if I wrote it that way.  But it probably would have infringed
on Stuffit's patent.  I had not read their patent before I wrote the
code so it is just luck that I used a different algorithm.

-- Matt Mahoney

Matt Mahoney wrote:
> jondelac@gmail.com wrote:
> > Matt Mahoney wrote:
> > > jondelac@gmail.com wrote:
> > > > Fulcrum wrote:
> > > > > jondelac@gmail.com wrote:
> > > > > > I see that paq8h can compress jpeg files.  Is this lossy compression?
> > > > >
> > > > > No, 100% lossless
> > > >
> > > > Hi,
> > > > I hate asking questions when source is available, but I must admit the
> > > > code is difficult to follow...
> > > >
> > > > I am very familiar with PAQ and the techniques used in most PAQ
> > > > versions...
> > > > Do you know what the general logic (idea) is that is being used in
> > > > paq8h to get better predictions on the DCT coef values?  I see that the
> > > > zigzag is undone and that the author is walking the DCT matrices in
> > > > natural order... but what is the logic behind the predictions?  I dont
> > > > understand the role of the basic prediction function... it seems to be
> > > > accessing the coef values in some sort of pattern to provide the
> > > > predictor some context and in addition, the prediction is put through
> > > > some sort of secondary sequensing... what exactly is going on here?
> > > >
> > > > Jon.
> > >
> > > The program parses the jpeg image into Huffman codes, then predicts the
> > > next code using the decoded image as context.  The decoding is only
> > > back to the DCT coefficients (the lossless part), not back to the
> > > original image.  The most useful context is just the u,v coordinates
> > > and color, but there are many other contexts that also improve
> > > compression a bit.
> > >
> > > The algorithm is different than the one used by Stuffit, according to
> > > their patent application.  (I did not patent anything in the paq8
> > > algorithm).  Stuffit transforms the jpeg image back to the DCT
> > > coefficients and compresses that directly using a context model.
> > > During decompression, it has to transform the coefficients back to the
> > > jpeg image.  paq8 is different in that there is no conversion back to
> > > jpeg.  The decoding to DCT is done by both the compressor and
> > > decompressor to get context.  However, Stuffit gets better compression.
> > >
> > > -- Matt Mahoney
> >
> >
> > Few questions...
> >
> > 1. In paq8h, what is the context algorithm... as in, what is the
> > formula for the context to predict the next bit?  From your reply, I
> > understand it is the u, v and color components... but can you explain
> > how you extract that... as in, when you are trying to predict a ceof in
> > the compressor, which previous y, u and color values are you using for
> > the bit of the current coef you are trying to predict?
>
> A lot of the code is just decoding the jpeg image, parsing the headers,
> saving the Huffman tables, discarding stuff I don't need like
> quantization tables, JFIF headers, comments, etc, then converting
> Huffman codes to RS codes and then back to the DCT coefficients in
> zigzag order, and computing the u,v coordinates for context.  Then just
> like the other models, various contexts are used as indexes to bit
> histories (8 bit states), which are then adaptively mapped to
> probabilities (StateMaps), which are then combined using neural
> networks (Mixers) selected by small contexts, then adjusted using
> secondary symbol estimatiton (APM), which adaptively map a probability
> and additional small context to a new probability.  Finally the
> predicted bits are arithmetic coded.  The jpeg model differs from the
> others in that it has its own ContextMap to deal with Huffman codes
> that don't fall on byte boundaries.  There is a hash table lookup every
> third bit to index a hash table which contains 7 bit histories for the
> cases of appending 0, 1, or 2 bits to the major context.  In the normal
> ContextMaps, which are optimized for byte aligned contexts, there is a
> hash table lookup every 2, 3, 3 bits and there is collision detection.
>
> > 2. From the stuffit transform you describe, are you saying that stuffit
> > decodes beyond the DCT and goes to the actual image and that is where
> > it is different from paq8h?  In that case, wouldnt stuffit introduce
> > lossyness?  I am reading your email as saying, paq8h gets its context
> > from DCT and stuffit gets its context from the actual image... is that
> > correct?
> >
> > Jon.
>
> No, Stuffit also decodes back to the DCT coefficients, not the image.
> It is different because Stuffit compresses the coeffients, not the
> Huffman codes.  This means the decompressor has to do the reverse
> transform to convert back to jpeg.  This doubles the amount of code
> needed for modeling and introduces possible loss of data if not careful
> to restore tables, headers, restart codes, etc. exactly as they were.
> I thought about doing it this way but it would have been extra work,
> and I didn't know if it would work any better (which it apparently
> does).  I do have framework code in paq8x to test the reverse transform
> at compress time to ensure it matches the input and abandon the
> transform if there is a mismatch, so I could have done the transform
> reliably if I wrote it that way.  But it probably would have infringed
> on Stuffit's patent.  I had not read their patent before I wrote the
> code so it is just luck that I used a different algorithm.
>
> -- Matt Mahoney

Hi...

1. Regarding paq8h's decoding, since paq8h's jpegModel also decodes as
far back as the DCT, why is it using the huffman values to provide
context?  As far as I understand it, if in paq8h, if we are getting
back to the DCT coeficitents, we have already undone the huffman part
and are already looking at the quantized yuv values... and it seems to
me from the code that it is this that is providing context for the
actual modeling... At this point, it seems similar to what stuffit
describes in their public disclosures...

2. Regarding Stuffit's patent, I beleive they are already infringing on
prior art, namely
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=5&f=G&l=50&co1=AND&d=PTXT&s1=%22jpeg+dct%22&OS=

So I dont think Stuffit will be awarded their patent... I dont actually
even think you can get at Stuffit's patent filing as it is not awarded
yet... There is no where to read what they are doing yet... but from
their public docs, it seems mighty similar to the patent I lised
above...

That said, I do actually get better results on many images with paq8h
even over stuffit... so what ever we are doing in paq8h is really cool.

I just dont understand your comment about using huffman values for
compression... Looking at the code and walking through your
explanation, I see the code undo huffman, and then look at the DCT
matrix (so you are going as far back as you can go with out getting
lossy).  And it seems it is these values that are providing context,
right?  The huffman data seems to be saved away just so the jpeg can be
reconstructed and match bit wise the original data...

Jon

jondelac@gmail.com wrote:
> Matt Mahoney wrote:
> > jondelac@gmail.com wrote:
> > > Matt Mahoney wrote:
> > > > jondelac@gmail.com wrote:
> > > > > Fulcrum wrote:
> > > > > > jondelac@gmail.com wrote:
> > > > > > > I see that paq8h can compress jpeg files.  Is this lossy compression?
> > > > > >
> > > > > > No, 100% lossless
> > > > >
> > > > > Hi,
> > > > > I hate asking questions when source is available, but I must admit the
> > > > > code is difficult to follow...
> > > > >
> > > > > I am very familiar with PAQ and the techniques used in most PAQ
> > > > > versions...
> > > > > Do you know what the general logic (idea) is that is being used in
> > > > > paq8h to get better predictions on the DCT coef values?  I see that the
> > > > > zigzag is undone and that the author is walking the DCT matrices in
> > > > > natural order... but what is the logic behind the predictions?  I dont
> > > > > understand the role of the basic prediction function... it seems to be
> > > > > accessing the coef values in some sort of pattern to provide the
> > > > > predictor some context and in addition, the prediction is put through
> > > > > some sort of secondary sequensing... what exactly is going on here?
> > > > >
> > > > > Jon.
> > > >
> > > > The program parses the jpeg image into Huffman codes, then predicts the
> > > > next code using the decoded image as context.  The decoding is only
> > > > back to the DCT coefficients (the lossless part), not back to the
> > > > original image.  The most useful context is just the u,v coordinates
> > > > and color, but there are many other contexts that also improve
> > > > compression a bit.
> > > >
> > > > The algorithm is different than the one used by Stuffit, according to
> > > > their patent application.  (I did not patent anything in the paq8
> > > > algorithm).  Stuffit transforms the jpeg image back to the DCT
> > > > coefficients and compresses that directly using a context model.
> > > > During decompression, it has to transform the coefficients back to the
> > > > jpeg image.  paq8 is different in that there is no conversion back to
> > > > jpeg.  The decoding to DCT is done by both the compressor and
> > > > decompressor to get context.  However, Stuffit gets better compression.
> > > >
> > > > -- Matt Mahoney
> > >
> > >
> > > Few questions...
> > >
> > > 1. In paq8h, what is the context algorithm... as in, what is the
> > > formula for the context to predict the next bit?  From your reply, I
> > > understand it is the u, v and color components... but can you explain
> > > how you extract that... as in, when you are trying to predict a ceof in
> > > the compressor, which previous y, u and color values are you using for
> > > the bit of the current coef you are trying to predict?
> >
> > A lot of the code is just decoding the jpeg image, parsing the headers,
> > saving the Huffman tables, discarding stuff I don't need like
> > quantization tables, JFIF headers, comments, etc, then converting
> > Huffman codes to RS codes and then back to the DCT coefficients in
> > zigzag order, and computing the u,v coordinates for context.  Then just
> > like the other models, various contexts are used as indexes to bit
> > histories (8 bit states), which are then adaptively mapped to
> > probabilities (StateMaps), which are then combined using neural
> > networks (Mixers) selected by small contexts, then adjusted using
> > secondary symbol estimatiton (APM), which adaptively map a probability
> > and additional small context to a new probability.  Finally the
> > predicted bits are arithmetic coded.  The jpeg model differs from the
> > others in that it has its own ContextMap to deal with Huffman codes
> > that don't fall on byte boundaries.  There is a hash table lookup every
> > third bit to index a hash table which contains 7 bit histories for the
> > cases of appending 0, 1, or 2 bits to the major context.  In the normal
> > ContextMaps, which are optimized for byte aligned contexts, there is a
> > hash table lookup every 2, 3, 3 bits and there is collision detection.
> >
> > > 2. From the stuffit transform you describe, are you saying that stuffit
> > > decodes beyond the DCT and goes to the actual image and that is where
> > > it is different from paq8h?  In that case, wouldnt stuffit introduce
> > > lossyness?  I am reading your email as saying, paq8h gets its context
> > > from DCT and stuffit gets its context from the actual image... is that
> > > correct?
> > >
> > > Jon.
> >
> > No, Stuffit also decodes back to the DCT coefficients, not the image.
> > It is different because Stuffit compresses the coeffients, not the
> > Huffman codes.  This means the decompressor has to do the reverse
> > transform to convert back to jpeg.  This doubles the amount of code
> > needed for modeling and introduces possible loss of data if not careful
> > to restore tables, headers, restart codes, etc. exactly as they were.
> > I thought about doing it this way but it would have been extra work,
> > and I didn't know if it would work any better (which it apparently
> > does).  I do have framework code in paq8x to test the reverse transform
> > at compress time to ensure it matches the input and abandon the
> > transform if there is a mismatch, so I could have done the transform
> > reliably if I wrote it that way.  But it probably would have infringed
> > on Stuffit's patent.  I had not read their patent before I wrote the
> > code so it is just luck that I used a different algorithm.
> >
> > -- Matt Mahoney
>
> Hi...
>
> 1. Regarding paq8h's decoding, since paq8h's jpegModel also decodes as
> far back as the DCT, why is it using the huffman values to provide
> context?  As far as I understand it, if in paq8h, if we are getting
> back to the DCT coeficitents, we have already undone the huffman part
> and are already looking at the quantized yuv values... and it seems to
> me from the code that it is this that is providing context for the
> actual modeling... At this point, it seems similar to what stuffit
> describes in their public disclosures...
>
> 2. Regarding Stuffit's patent, I beleive they are already infringing on
> prior art, namely
> http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=5&f=G&l=50&co1=AND&d=PTXT&s1=%22jpeg+dct%22&OS=
>
> So I dont think Stuffit will be awarded their patent... I dont actually
> even think you can get at Stuffit's patent filing as it is not awarded
> yet... There is no where to read what they are doing yet... but from
> their public docs, it seems mighty similar to the patent I lised
> above...
>
> That said, I do actually get better results on many images with paq8h
> even over stuffit... so what ever we are doing in paq8h is really cool.
>
> I just dont understand your comment about using huffman values for
> compression... Looking at the code and walking through your
> explanation, I see the code undo huffman, and then look at the DCT
> matrix (so you are going as far back as you can go with out getting
> lossy).  And it seems it is these values that are providing context,
> right?  The huffman data seems to be saved away just so the jpeg can be
> reconstructed and match bit wise the original data...
>
> Jon

Here is the Stuffit patent application.
http://www.freshpatents.com/System-and-method-for-lossless-compression-of-digital-images-dt20060518ptan20060104525.php?type=description

This differs in that USPTO 7,092,965 uses a wavelet transform to
recompress the DCT coefficients (across adjacent pixel blocks).
Stuffit uses a context model.  (If they did claim the same invention, I
doubt the USPTO would notice anyway.  They granted the same LZW patent
to both Unisys and IBM).  It might still be rejected because they make
broad claims that their invention applies to recompression of any
compressed format (zip, MP3, MPEG, etc) but disclose a method only for
JPEG.  Also they claim the invention of determining the input file type
and applying specialized algorithms to each type.  I'm pretty sure
there is prior art (e.g. WinRAR).

Both of these differ from paq8h in that they decompress by
uncompressing the DCT coefficients and compressing back to JPEG.  paq8h
does not do this.  paq8h models the bits in the original JPEG image,
which are in the form of Huffman codes.  It only uses the DCT
coefficients as context to predict these bits.

BTW Stuffit beats paq8f/g/h/i on plain JPEG files like a10.jpg
http://www.maximumcompression.com/data/jpg.php

but Stuffit does not recognize embedded images in other files, e.g.
ohs.doc
http://www.maximumcompression.com/data/doc.php

-- Matt Mahoney