home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4797 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  3.3 KB
  1. Path: sparky!uunet!europa.asd.contel.com!emory!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!tgl
  2. From: tgl+@cs.cmu.edu (Tom Lane)
  3. Newsgroups: comp.compression
  4. Subject: Re: JPEG compression
  5. Summary: it ain't that simple
  6. Keywords: JPEG, compression
  7. Message-ID: <C1F6I4.675.2@cs.cmu.edu>
  8. Date: 25 Jan 93 17:13:09 GMT
  9. Article-I.D.: cs.C1F6I4.675.2
  10. References: <peterb.727926960@wambenger>
  11. Sender: news@cs.cmu.edu (Usenet News System)
  12. Organization: School of Computer Science, Carnegie Mellon
  13. Lines: 59
  14. Nntp-Posting-Host: g.gp.cs.cmu.edu
  15.  
  16. peterb@cs.uwa.oz.au (Peter Bousfield) asks:
  17. > It is my understanding that JPEG compression works in basically two parts.
  18. > Step 1: DCT (Discrete Cosine Transform)
  19. > and
  20. > Step 2: Huffman Coding ...
  21. > 
  22. > I was wanting to know which of these two steps contributes more to the
  23. > compression.  That is, how good is the compression without Huffman coding
  24. > (eg is it 50% worse or only 10% worse.)
  25.  
  26. Well, it's not really that simple.  The DCT is done to make the data more
  27. compressible, not to achieve any compression itself.  (In fact, the raw
  28. volume of data that comes out of the DCT stage is more than what goes into
  29. it: 11 bits/pixel instead of 8.)  So in one sense the Huffman stage
  30. achieves *all* the compression.  But obviously that statement doesn't
  31. capture what's going on.
  32.  
  33. This is analogous to the distinction between modeling and coding.  (I believe
  34. the comp.compression FAQ talks about this; or see Mark Nelson's book, or any
  35. other recent textbook on data compression.)  You express the data in a form
  36. that exposes redundancy, then you use a coding technique to remove the
  37. redundancy.
  38.  
  39. I think of JPEG as containing three types of steps:
  40.  
  41. 1. Transformation of the data into a more suitable form.
  42.    This covers two stages: colorspace change and DCT.
  43.    The data volume is not reduced here, and in fact these steps are 100%
  44.    reversible except for roundoff error.
  45.  
  46. 2. Data reduction.
  47.    This likewise covers two stages: downsampling and DCT coefficient
  48.    quantization.
  49.    In these steps we deliberately throw away data, being careful to throw
  50.    away that data which is least visible to the human eye (which the
  51.    preceding steps have separated out for us).  These steps are
  52.    parameterized so that we can trade off file size against image quality,
  53.    by adjusting how much data is thrown away.
  54.  
  55. 3. Entropy coding.
  56.    This is either Huffman or arithmetic coding, depending on the depth of
  57.    your wallet :-).
  58.    In this step we efficiently encode the remaining data.  This step is
  59.    lossless (the entropy decoder will exactly reconstruct what was given
  60.    to the entropy encoder).  We rely on the prior steps to have presented us
  61.    with data in a highly redundant form --- for example, there are typically
  62.    a LOT of zeroes.
  63.  
  64. I think the initial question might really have meant "can I use a different
  65. entropy encoder?".  Sure, any lossless compression technique will work for
  66. step 3.  (In my group's initial experiments with JPEG, we ran the output of
  67. step 2 through good old Unix compress, and got reasonable compression.)
  68. But the particular variants of Huffman and arithmetic coding specified by
  69. the standard are tuned to the characteristics of the data stream that
  70. normally emerges from the prior stages.  You won't get as good compression
  71. if you use a general-purpose compression method.
  72.  
  73.             tom lane
  74.             organizer, Independent JPEG Group
  75.