Results 1 to 27 of 27

Thread: JPEG Huffman Coding

  1. #1
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts

    JPEG Huffman Coding

    Hi all,

    After reading this paper:

    http://www.csd.uoc.gr/~hy438/themata/04-0522.pdf

    it turns out that the usual Huffman custom table (also called optimized JPEG) yields on average a reduction of 1.38% of image's size, but the use of dynamic Huffman coding (which builds an even better Huffman table) almost doubles this figure by yielding on average a further reduction of 1.01%.

    An implementation of Vitter's algorithm (an improved version of the algorithm mentioned in the previous paper, so the compression might be even bigger than 1.01%) in the public domain can be found here:

    http://code.google.com/p/compression...downloads/list

    Who could use this to build a JPEG optimizer by using optimized Huffman coding?

    And still, who can import on windows perl-script?

    http://akuvian.org/src/jpgcrush.tar.gz

  2. #2
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    But AFAIK Vitter's method is not included in the JPEG standard. There are stronger algorithms for reducing JPEG sizes, like PackJPG, StuffIt or PAQ.

  3. #3
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts
    I.e. it is impossible to leave it to carry out within the limits of the same format jpeg?

  4. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    JPEG (like MPEG and other multimedia formats) defines the decoding algorithm. You're free to make any optimizations in encoder provided that produced files decodes properly with reference decoders. If reference decoder does not support Vitter's codes (Vitter's method requires special decoder) then you can't use them to produce compatible output.

    JPEG standard includes arithmetic coding variant that is AFAIR patented, so despite that it's much better even than Vitter's, it's almost never used and not supported by many common JPEG decoders.

    There are programs like jpegoptim or jpegtran that try to optimize JPEGs and probably you can't do noticeably better than them while still producing output compatible with most common decoders.

  5. #5
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts
    And there are other ways to improve compression JPEG within the limits of the same format?

    For example, JPGCrush creates well compressed Progressive images

    And still, there is at whom a compiled version jpegoptim for windows?

  6. #6
    Member
    Join Date
    May 2008
    Location
    HK
    Posts
    160
    Thanks
    4
    Thanked 25 Times in 15 Posts
    Isn't that jpegoptim use same method as jpegtrans?

  7. #7
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    roytam1:
    Probably yes. I'm not very familiar with those programs.

    lorents17:
    Jpegtrans or jpegoptim should be able to convert baseline JPGs to progressive JPGs.

    You can find jpegoptim.exe here: http://pornel.net/jpegoptim although the should be many places with compiled jpegoptim on the Internet.

  8. #8
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts
    There is one idea, truth don't know as to realize.

    As it is known Adobe Photoshop uses the library for creation JPEG. JPEGTran uses library Independent JPEG Group.

    And to tell what library optimizes is better to tell difficultly, and what if to unite these two libraries, but here a question as?

    If to look on JPGCrush it uses JPEGTran as means of creation JPEG, thus parameters sets itself. From here a question, whether it is possible to set parameters which uses Adobe Photoshop for creation JPEG through JPEGTran?

    I mean, to create the application which could analyze jpeg images, and impart in JPEGTran parameters which are used in it jpeg.
    Last edited by lorents17; 11th September 2011 at 18:23.

  9. #9
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Well, you previously said about *optimizing* JPEGs, not converting to JPEGs. Obiously, when it comes to conversion to JPEG one can use a number of tricks, eg blurring chroma before subsampling, subsampling using eg Kaiser method, avoiding gamma ramp, (look at: http://number-none.com/product/Mipma...201/index.html http://number-none.com/product/Mipma...202/index.html ), using different (or even adaptive to input image) quantization tables, etc

    JPEG is not lossless. It focuses on best perceived visual quality. Because of that, you can optimize the lossy stages of algorithm, not only the lossless stages. There are even lossy PNG or FLAC coders, but their existence doesn't mean that PNG or FLAC is inherently lossy.

  10. #10
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts
    del
    Last edited by lorents17; 11th September 2011 at 20:01.

  11. #11
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    jpegoptim and jpegtran are different tools, though work similarly.
    Arithmetic coding patents expired already, but software support is very low.

  12. #12
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts
    Who is able to create -scans file for jpegtran?

  13. #13
    Member
    Join Date
    Sep 2011
    Location
    EU
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    But AFAIK Vitter's method is not included in the JPEG standard.
    If you are saying that JPEG decoders do not build a Huffman tree on the fly, you are right. But if you use Vitter's algorithm to build the optimized Huffman tree and use it to encode the JPEG, JPEG decoders have no way of knowing that they are not using the standard Huffman tree. That's why the paper mentions the further reduction of 1.01% on top of optimized JPEGs using Knuth's algorithm which is not as strong as Vitter's algorithm, so the reduction could be a little bit bigger using Vitter's algorithm.


    Quote Originally Posted by Piotr Tarsa View Post
    There are stronger algorithms for reducing JPEG sizes, like PackJPG, StuffIt or PAQ.
    That's true, but unfortunately they are not compatible with standard JPEG decoders. On the other hand using Vitter's Huffman tree to encode JPEGs is and can be used by everybody today, once they have such an encoder.

  14. #14
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Huffman codes are by definition optimal, ie they are the prefix codes that produce best compression ratio, no matter how did you constructed that codes. So using a different algorithm cannot help in general case. On the other hand, JPEG limits codes length and also inserts a fake symbol with code of all 1's, so in fact JPEG codes aren't true Huffman codes and different algorithm could help. But I don't see how adaptive Huffman coding can help to produce optimal JPEG codes. After a quick search I've found an algorithm for computation of optimal limited-length Huffman codes (ie. something very close to JPEG codes, except that additional unused symbol in JPEG coding, but that should be trivial to handle): http://en.wikipedia.org/wiki/Package-merge_algorithm So that is the algorithm you should use if you want to produce optimal JPEG codes.

  15. #15
    Member
    Join Date
    Sep 2011
    Location
    EU
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    Huffman codes are by definition optimal, ie they are the prefix codes that produce best compression ratio, no matter how did you constructed that codes.
    No, that's not completely true: -The classic Huffman codes are optimal on the limit of large documents and have the implicit assumption of randomness, because on the first step the classic algorithm takes averages to calculate frequencies of occurrence for each symbol-.

    Now that assumptions are not completely satisfied by JPEGs for the web, because they must fit on webpages usually without scrolling (i.e. they are small) and they are not that random, on the contrary they tend to be clustered (think on a sky, for instance). What Knuth's and Vitter's algorithms do is taking advantage of the aforementioned clustering to get an optimized "Huffman" tree which produces shorter encoded sequences. Take a look, for instance at the abstract of Vitter's paper:


    A new one-pass algorithm for constructing dynamic Huffman codes is introduced and analyzed. We also analyze the one-pass algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and the receiver maintain equivalent dynamically varying Huffman trees, and the coding is done in real time. We show that the number of bits used by the new algorithm to encode a message containing t letters is < t bits more than that used by the conventional two-pass Huffman scheme, independent of the alphabet size. This is best possible in the worst case, for any one-pass Huffman method.

    The complete abstract can be read here: http://dl.acm.org/citation.cfm?id=42227

  16. #16
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    JPEG codes are static and Vitter codes are adaptive. It's obvious that with heterogenous data Vitter will win, but only because it's adaptive.

    I think the paper describes encoding incompatible with JPEG, I'll read that paper in a moment.

    Update:
    Well, after a quick look at the abstract, it clearly defines compression scheme incompatible with JPEG.
    Last edited by Piotr Tarsa; 25th September 2011 at 16:53.

  17. #17
    Member
    Join Date
    Sep 2011
    Location
    EU
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Reading the paper posted by lorents17, proves the contrary, at least for Knuth's algorithm.

  18. #18
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Quotes from abstract:

    First incompatibility:
    During the run-length coding, instead
    of pairing a nonzero ac coefficient with the run-length of the pre-
    ceding zero coefficients, our encoder pairs it with the run-length of
    subsequent zeros.
    Second incompatibility:
    This small change makes it possible for our codec
    to code a pair using a separate Huffman code table optimized for
    the position of the nonzero coefficient denoted by the pair.
    Third incompatibility:
    These
    position-dependent code tables can be encoded efficiently without
    incurring a sizable overhead.

    As for dynamic Huffman code:
    Another choice
    is to follow dynamic Huffman coding, [5], proposed for gen-
    eral file compression. In this method, the encoder updates the
    code table after coding each symbol to model any changes in
    the distribution of source symbols. Table I also contains exper-
    imental results, which show that this method obtains a further
    reduction of about 1% only; it is hardly appealing knowing that
    dynamic Huffman coding is highly computational. The reason
    for dynamic Huffman coding not achieving any further com-
    pression in our experiments is that there is hardly any change in
    the global distribution of ac coefficients; all changes are local
    and confined within each DCT block.
    It's also obvious that adaptive Huffman that gives that 1.01 % improvement is incompatible with JPEG, as it requires updating the Huffman tree after each encoded symbol.

    Also the 10% - 15% improvement claim only applies to AC code coefficients, which forms about 50% - 60% of total file size, so the overall improvement would be much less than 10%.
    Last edited by Piotr Tarsa; 25th September 2011 at 17:39.

  19. #19
    Member
    Join Date
    Sep 2011
    Location
    EU
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Concerning the first (second and third) incompatibility, you got it wrong. The paper proposes a new (and incompatible) encoding, because the compatible encoding using dynamic Huffman coding only yields an average gain of 1.01%, cf. table I. Of course they propose an incompatible encoding which yields an average reduction of 15% and you got lost there.

    Concerning your last incompatibility, once more, you got it wrong. Yes, the table is built iteratively (and so it changes usually at every step, because the algorithm finds that there's a better tree), but once the last symbol is reached, it obviously do not change anymore and it is that very last tree which is called the optimized Huffman tree and which is used to encode all the image's data.
    Last edited by jverne; 25th September 2011 at 17:39.

  20. #20
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Dynamic Huffman coding is not used by paper's authors at all, except some results in a single table showing the effect of dynamic (ie. adaptive) Huffman coding (ie. those results that shows 1.01 % improvement over static Huffman coding).

    You cannot compute better static prefix codes than those produced by static Huffman algorithm, that's proved. And JPEG codes are static, so you cannot win anything over conventionally optimized static prefix code tables (ie built with Huffman algorithm) used in JPEG.
    Last edited by Piotr Tarsa; 25th September 2011 at 18:02.

  21. #21
    Member
    Join Date
    Sep 2011
    Location
    EU
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    Dynamic Huffman coding is not used by paper's authors at all, except some results in a single table showing the effect of dynamic (ie. adaptive) Huffman coding (ie. those results that shows 1.01 % improvement over static Huffman coding).
    Yes, the dynamic Huffman coding is only a side note on this paper, i.e. it a known known and that was the point.


    Quote Originally Posted by Piotr Tarsa View Post
    You cannot compute better static prefix codes than those produced by static Huffman algorithm, that's proved. And JPEG codes are static, so you cannot win anything over conventionally optimized static prefix code tables (ie built with Huffman algorithm) used in JPEG.
    Yes you can. The theorem is right and it is valid as long as the following two conditions are satisfied:
    • Limit of big numbers (not necessarily valid for small JPEGs),

    • The sequence is i.i.d., as averages are taken on the first pass (obviously that's not the case of natural images, otherwise you wouldn't recognize anithing on them).
    If this is not obvious, you don't need to believe me, just read this paper:
    http://www.stevenpigeon.com/Publicat...iveHuffman.pdf

    and you'll start to understand that the order of symbols' appearance (optimized Huffman encoding) is as important as their frequency (classic Huffman encoding). It is the order of appearance, which is not i.i.d. that Knuth's and Vitter's algorithms are optimizing.

    For infinite and i.i.d. images, you and the theorem you mention are both right. The point is that natural images (not i.i.d.) used on the web (not big, i.e. not "infinite") usually do not satisfy those two conditions and as Corollary the Huffman trees got after using Knuth's or Vitter's algorithm after they have reached the image's string end compress better than the classic Huffman tree.

  22. #22
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Please make an example. Your posts doesn't make any sense for me.

    For infinite and i.i.d. images, you and the theorem you mention are both right.
    I'm not talking about infinite images, that's obvious. I am talking about normal JPEG files and normal Huffman codes, which are optimal prefix codes, produced by either Huffman's algorithm (when code length is unbounded or unbounded Huffman codes doesn't break the code length limit) or http://en.wikipedia.org/wiki/Package-merge_algorithm (when code length is limited and Huffman algorithm produces too long codes).

    The whole point of Vitter's or Knuth's algorithms is to allow adaptive Huffman encoding in reasonable time, where code lengths depend on the position in original string.

  23. #23
    Member
    Join Date
    Sep 2011
    Location
    EU
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Perhaps an example will help. Look here: http://www.ics.uci.edu/~dan/pubs/DC-Sec4.html

    Here's an excerpt to call your attention:

    Figure 4.3 illustrates an example on which algorithm FGK [Knuth's algorithm] performs better than static Huffman coding even without taking overhead into account. Algorithm FGK transmits 47 bits for this ensemble while the static Huffman code requires 53.
    And here is a recapitulation of why it works:

    Knuth presents methodologies for maintaining the unique prefix attribute required by Huffman codes, while achieving a minimal path length from the root to a leaf. This minimal path length is equivalent to assigning the shortest code possible to a symbol with a given count (frequency).
    taken from this thesis: http://citeseerx.ist.psu.edu/viewdoc...p=rep1&type=ps

  24. #24
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    In Figure 4.3 there's full binary tree for which the compressed size of example will be exactly 53 bits (see: http://ideone.com/SAi8d), the same as in Huffman's algorithm. It will produce a 47 bit output only if you're doing adaptive encoding, which is completely incompatible with JPEG.

  25. #25
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    168
    Thanks
    163
    Thanked 9 Times in 8 Posts

    Photoshop vs Jpegtran

    Good day!
    Now comparing compression JPEG:
    • photoshop (save for web optimized)
    • jpegtran-optimize

    Noticed that some images photoshop compresses better, in others - jpegtran. Raises the question whether it is possible to fix it?
    Theoretically, this can be done using the-scans in jpegtran, but I do not know how to create a file scans?
    Last edited by lorents17; 15th December 2013 at 11:44.

  26. #26
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    448
    Thanks
    1
    Thanked 101 Times in 61 Posts
    Quote Originally Posted by lorents17 View Post
    Good day!
    Now comparing compression JPEG:
    • photoshop (save for web optimized)
    • jpegtran-optimize

    Noticed that some images photoshop compresses better, in others - jpegtran. Raises the question whether it is possible to fix it?
    Theoretically, this can be done using the-scans in jpegtran, but I do not know how to create a file scans?
    It not only depends on the scans (and thus the scan mode), but also the quantization matrices. Photoshop might use a different one (or rather, multiple), and Photoshop might also use a technique called "soft-thresholding" that pushes some coefficients into zero without being zero. The question rather is whether it is worth the trouble.

  27. #27
    Member
    Join Date
    Jun 2013
    Location
    USA
    Posts
    98
    Thanks
    4
    Thanked 14 Times in 12 Posts
    Quote Originally Posted by lorents17 View Post
    Good day!
    Now comparing compression JPEG:
    • photoshop (save for web optimized)
    • jpegtran-optimize

    Noticed that some images photoshop compresses better, in others - jpegtran. Raises the question whether it is possible to fix it?
    Theoretically, this can be done using the-scans in jpegtran, but I do not know how to create a file scans?
    You might want to take a look at jpegrescan: https://github.com/neheb/utilities

    It's a perl script that tries out various scans to find out which compresses the best. the -v option should give more insight as to the scans that were attempted.

    The script is also included in http://css-ig.net/scriptjpg
    Last edited by Mangix; 16th December 2013 at 00:58.

Similar Threads

  1. Detector for ex-JPEG images
    By Alexander Rhatushnyak in forum Data Compression
    Replies: 22
    Last Post: 13th September 2012, 04:18
  2. Coding with restricted alphabet
    By Shelwien in forum Data Compression
    Replies: 0
    Last Post: 26th July 2010, 00:21
  3. Experiments with small dictionary coding
    By Matt Mahoney in forum Data Compression
    Replies: 13
    Last Post: 28th June 2010, 17:34
  4. huffman's Coding
    By swapy in forum Data Compression
    Replies: 5
    Last Post: 12th August 2009, 23:51
  5. RC Coding
    By rasputin in forum Data Compression
    Replies: 10
    Last Post: 6th November 2008, 19:54

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •