home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / Documents / FAQ / Compression-faq / part2 < prev    next >
Encoding:
Internet Message Format  |  1993-08-10  |  56.4 KB

  1. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!usc!math.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!doc.ic.ac.uk!uknet!mcsun!julienas!chorus!chorus.fr
  2. From: jloup@chorus.fr (Jean-loup Gailly)
  3. Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
  4. Subject: comp.compression Frequently Asked Questions (part 2/3)
  5. Summary: *** READ THIS BEFORE POSTING ***
  6. Keywords: data compression, FAQ
  7. Message-ID: <compr2_10aug93@chorus.fr>
  8. Date: 10 Aug 93 20:55:14 GMT
  9. Expires: 30 Sep 93 16:17:20 GMT
  10. References: <compr1_10aug93@chorus.fr>
  11. Sender: news@chorus.chorus.fr
  12. Reply-To: jloup@chorus.fr
  13. Followup-To: comp.compression
  14. Lines: 1106
  15. Approved: news-answers-request@MIT.Edu
  16. Supersedes: <compr2_9jul93@chorus.fr>
  17. Xref: senator-bedfellow.mit.edu comp.compression:8381 comp.compression.research:894 news.answers:11233 comp.answers:1557
  18.  
  19. Archive-name: compression-faq/part2
  20. Last-modified: June 21st, 1993
  21.  
  22. This file is part 2 of a set of Frequently Asked Questions for the
  23. groups comp.compression and comp.compression.research.
  24. If you did not get part 1 or 3, you can get them by ftp
  25. on rtfm.mit.edu in directory
  26.    /pub/usenet/news.answers/compression-faq
  27.  
  28. If you don't want to see this FAQ regularly, please add the subject
  29. line to your kill file. If you have corrections or suggestions for
  30. this FAQ, send them to Jean-loup Gailly <jloup@chorus.fr>.  Thank you.
  31.  
  32. Contents
  33. ========
  34.  
  35. Part 2: (Long) introductions to data compression techniques
  36.  
  37. [70] Introduction to data compression (long)
  38.        Huffman and Related Compression Techniques
  39.        Arithmetic Coding
  40.        Substitutional Compressors
  41.           The LZ78 family of compressors
  42.           The LZ77 family of compressors
  43.  
  44. [71] Introduction to MPEG (long)
  45.        What is MPEG?
  46.        Does it have anything to do with JPEG?
  47.        Then what's JBIG and MHEG?
  48.        What has MPEG accomplished?
  49.        So how does MPEG I work?
  50.        What about the audio compression?
  51.        So how much does it compress?
  52.        What's phase II?
  53.        When will all this be finished?
  54.        How do I join MPEG?
  55.        How do I get the documents, like the MPEG I draft?
  56.  
  57. [72] What is wavelet theory?
  58. [73] What is the theoretical compression limit?
  59. [74] Introduction to JBIG
  60. [75] Introduction to JPEG
  61.  
  62. Part 3: (Long) list of image compression hardware
  63.  
  64. [85] Image compression hardware
  65. [99] Acknowledgments
  66.  
  67.  
  68. Search for "Subject: [#]" to get to question number # quickly. Some news
  69. readers can also take advantage of the message digest format used here.
  70.  
  71. ------------------------------------------------------------------------------
  72.  
  73. Subject: [70] Introduction to data compression (long)
  74.  
  75.  
  76. Written by Peter Gutmann <pgut1@cs.aukuni.ac.nz>.
  77.  
  78.  Huffman and Related Compression Techniques
  79.  ------------------------------------------
  80.  
  81.   *Huffman compression* is a statistical data compression technique which 
  82. gives a reduction in the average code length used to represent the symbols of 
  83. a alphabet.  The Huffman code is an example of a code which is optimal in the 
  84. case where all symbols probabilities are integral powers of 1/2.  A Huffman 
  85. code can be built in the following manner:
  86.  
  87.   (1) Rank all symbols in order of probability of occurrence.
  88.     
  89.   (2) Successively combine the two symbols of the lowest probability to form
  90.       a new composite symbol; eventually we will build a binary tree where
  91.       each node is the probability of all nodes beneath it.
  92.  
  93.   (3) Trace a path to each leaf, noticing the direction at each node.
  94.  
  95.   For a given frequency distribution, there are many possible Huffman codes,
  96. but the total compressed length will be the same. It is possible to
  97. define a 'canonical' Huffman tree, that is, pick one of these alternative
  98. trees. Such a canonical tree can then be represented very compactly, by
  99. transmitting only the bit length of each code. This technique is used
  100. in most archivers (pkzip, lha, zoo, arj, ...).
  101.  
  102.  
  103.   A technique related to Huffman coding is *Shannon-Fano coding*, which
  104. works as follows:
  105.  
  106.   (1) Divide the set of symbols into two equal or almost equal subsets
  107.       based on the probability of occurrence of characters in each
  108.       subset.  The first subset is assigned a binary zero, the second
  109.       a binary one.
  110.  
  111.   (2) Repeat step (1) until all subsets have a single element.
  112.  
  113. The algorithm used to create the Huffman codes is bottom-up, and the
  114. one for the Shannon-Fano codes is top-down. Huffman encoding always
  115. generates optimal codes, Shannon-Fano sometimes uses a few more bits.
  116.  
  117.  
  118.  Arithmetic Coding
  119.  -----------------
  120.  
  121.   It would appear that Huffman or Shannon-Fano coding is the perfect
  122. means of compressing data.  However, this is *not* the case.  As
  123. mentioned above, these coding methods are optimal when and only when
  124. the symbol probabilities are integral powers of 1/2, which is usually
  125. not the case.
  126.  
  127.   The technique of *arithmetic coding* does not have this restriction:
  128. It achieves the same effect as treating the message as one single unit
  129. (a technique which would, for Huffman coding, require enumeration of
  130. every single possible message), and thus attains the theoretical
  131. entropy bound to compression efficiency for any source.
  132.  
  133.   Arithmetic coding works by representing a number by an interval of real 
  134. numbers between 0 and 1.  As the message becomes longer, the interval needed 
  135. to represent it becomes smaller and smaller, and the number of bits needed to 
  136. specify that interval increases.  Successive symbols in the message reduce 
  137. this interval in accordance with the probability of that symbol. The more
  138. likely symbols reduce the range by less, and thus add fewer bits to the   
  139. message.
  140.  
  141.      1                                             Codewords
  142.     +-----------+-----------+-----------+           /-----\
  143.     |           |8/9 YY     |  Detail   |<- 31/32    .11111
  144.     |           +-----------+-----------+<- 15/16    .1111
  145.     |    Y      |           | too small |<- 14/16    .1110
  146.     |2/3        |    YX     | for text  |<- 6/8      .110
  147.     +-----------+-----------+-----------+
  148.     |           |           |16/27 XYY  |<- 10/16    .1010
  149.     |           |           +-----------+
  150.     |           |    XY     |           |
  151.     |           |           |   XYX     |<- 4/8      .100
  152.     |           |4/9        |           |
  153.     |           +-----------+-----------+
  154.     |           |           |           |
  155.     |    X      |           |   XXY     |<- 3/8      .011
  156.     |           |           |8/27       |
  157.     |           |           +-----------+
  158.     |           |    XX     |           |
  159.     |           |           |           |<- 1/4      .01
  160.     |           |           |   XXX     |
  161.     |           |           |           |
  162.     |0          |           |           |
  163.     +-----------+-----------+-----------+
  164.  
  165.   As an example of arithmetic coding, lets consider the example of two
  166. symbols X and Y, of probabilities 0.66 and 0.33. To encode this message, we
  167. examine the first symbol: If it is a X, we choose the lower partition; if
  168. it is a Y, we choose the upper partition.  Continuing in this manner for
  169. three symbols, we get the codewords shown to the right of the diagram above
  170. - they can be found by simply taking an appropriate location in the
  171. interval for that particular set of symbols and turning it into a binary
  172. fraction. In practice, it is also necessary to add a special end-of-data
  173. symbol, which is not represented in this simpe example.
  174.         
  175.   In this case the arithmetic code is not completely efficient, which is due 
  176. to the shortness of the message - with longer messages the coding efficiency 
  177. does indeed approach 100%.
  178.  
  179.   Now that we have an efficient encoding technique, what can we do with it? 
  180. What we need is a technique for building a model of the data which we can 
  181. then use with the encoder.  The simplest model is a fixed one, for example a 
  182. table of standard letter frequencies for English text which we can then use 
  183. to get letter probabilities.  An improvement on this technique is to use an 
  184. *adaptive model*, in other words a model which adjusts itself to the data 
  185. which is being compressed as the data is compressed.  We can convert the 
  186. fixed model into an adaptive one by adjusting the symbol frequencies after 
  187. each new symbol is encoded, allowing the model to track the data being 
  188. transmitted.  However, we can do much better than that.
  189.  
  190. Using the symbol probabilities by themselves is not a particularly good
  191. estimate of the true entropy of the data: We can take into account
  192. intersymbol probabilities as well.  The best compressors available today
  193. take this approach: DMC (Dynamic Markov Coding) starts with a zero-order
  194. Markov model and gradually extends this initial model as compression
  195. progresses; PPM (Prediction by Partial Matching) looks for a match of the
  196. text to be compressed in an order-n context.  If no match is found, it
  197. drops to an order n-1 context, until it reaches order 0.  Both these
  198. techniques thus obtain a much better model of the data to be compressed,
  199. which, combined with the use of arithmetic coding, results in superior
  200. compression performance.
  201.  
  202.   So if arithmetic coding-based compressors are so powerful, why are they not 
  203. used universally?  Apart from the fact that they are relatively new and 
  204. haven't come into general use too much yet, there is also one major concern:  
  205. The fact that they consume rather large amounts of computing resources, both 
  206. in terms of CPU power and memory.  The building of sophisticated models for 
  207. the compression can chew through a fair amount of memory (especially in the 
  208. case of DMC, where the model can grow without bounds); and the arithmetic 
  209. coding itself involves a fair amount of number crunching.
  210. There is however an alternative approach, a class of compressors generally 
  211. referred to as *substitutional* or *dictionary-based compressors*.
  212.  
  213.  Substitutional Compressors
  214.  --------------------------
  215.  
  216.   The basic idea behind a substitutional compressor is to replace an 
  217. occurrence of a particular phrase or group of bytes in a piece of data with a 
  218. reference to a previous occurrence of that phrase.  There are two main 
  219. classes of schemes, named after Jakob Ziv and Abraham Lempel, who first 
  220. proposed them in 1977 and 1978.
  221.  
  222. <The LZ78 family of compressors>
  223.  
  224.   LZ78-based schemes work by entering phrases into a *dictionary* and then, 
  225. when a repeat occurrence of that particular phrase is found, outputting the 
  226. dictionary index instead of the phrase.  There exist several compression 
  227. algorithms based on this principle, differing mainly in the manner in which 
  228. they manage the dictionary.  The most well-known scheme (in fact the most 
  229. well-known of all the Lempel-Ziv compressors, the one which is generally (and 
  230. mistakenly) referred to as "Lempel-Ziv Compression"), is Terry Welch's LZW 
  231. scheme, which he designed in 1984 for implementation in hardware for high- 
  232. performance disk controllers.
  233.  
  234. Input string: /WED/WE/WEE/WEB
  235.  
  236. Character input:    Code output:    New code value and associated string:
  237.     /W                  /                   256 = /W
  238.     E                   W                   257 = WE
  239.     D                   E                   258 = ED
  240.     /                   D                   259 = D/
  241.     WE                  256                 260 = /WE
  242.     /                   E                   261 = E/
  243.     WEE                 260                 262 = /WEE
  244.     /W                  261                 263 = E/W
  245.     EB                  257                 264 = WEB
  246.     <END>               B
  247.     
  248.   LZW starts with a 4K dictionary, of which entries 0-255 refer to individual 
  249. bytes, and entries 256-4095 refer to substrings.  Each time a new code is 
  250. generated it means a new string has been parsed.  New strings are generated 
  251. by appending the current character K to the end of an existing string w.  The 
  252. algorithm for LZW compression is as follows:
  253.  
  254.   set w = NIL
  255.   loop
  256.       read a character K
  257.       if wK exists is in the dictionary
  258.           w = wK
  259.       else
  260.           output the code for w
  261.           add wK to the string table
  262.           w = K
  263.   endloop
  264.  
  265.   A sample run of LZW over a (highly redundant) input string can be seen in 
  266. the diagram above.  The strings are built up character-by-character starting 
  267. with a code value of 256.  LZW decompression takes the stream of codes and 
  268. uses it to exactly recreate the original input data.  Just like the 
  269. compression algorithm, the decompressor adds a new string to the dictionary 
  270. each time it reads in a new code.  All it needs to do in addition is to 
  271. translate each incoming code into a string and send it to the output.  A 
  272. sample run of the LZW decompressor is shown in below.
  273.  
  274. Input code: /WED<256>E<260><261><257>B
  275.  
  276. Input code:        Output string:     New code value and associated string:
  277.     /                  /            
  278.     W                  W                      256 = /W
  279.     E                  E                      257 = WE
  280.     D                  D                      258 = ED
  281.     256                /W                     259 = D/
  282.     E                  E                      260 = /WE
  283.     260                /WE                    261 = E/
  284.     261                E/                     262 = /WEE
  285.     257                WE                     263 = E/W
  286.     B                  B                      264 = WEB
  287.            
  288.   The most remarkable feature of this type of compression is that the entire 
  289. dictionary has been transmitted to the decoder without actually explicitly 
  290. transmitting the dictionary.  At the end of the run, the decoder will have a 
  291. dictionary identical to the one the encoder has, built up entirely as part of 
  292. the decoding process.
  293.     LZW is more commonly encountered today in a variant known as LZC, after 
  294. its use in the UNIX "compress" program.  In this variant, pointers do not 
  295. have a fixed length.  Rather, they start with a length of 9 bits, and then 
  296. slowly grow to their maximum possible length once all the pointers of a 
  297. particular size have been used up.  Furthermore, the dictionary is not frozen 
  298. once it is full as for LZW - the program continually monitors compression 
  299. performance, and once this starts decreasing the entire dictionary is 
  300. discarded and rebuilt from scratch.  More recent schemes use some sort of 
  301. least-recently-used algorithm to discard little-used phrases once the 
  302. dictionary becomes full rather than throwing away the entire dictionary.  
  303.  
  304. Finally, not all schemes build up the dictionary by adding a single new 
  305. character to the end of the current phrase. An alternative technique is to 
  306. concatenate the previous two phrases (LZMW), which results in a faster 
  307. buildup of longer phrases than the character-by-character buildup of the 
  308. other methods.  The disadvantage of this method is that a more sophisticated 
  309. data structure is needed to handle the dictionary.
  310.  
  311. [A good introduction to LZW, MW, AP and Y coding is given in the yabba
  312. package. For ftp information, see question 2 in part one, file type .Y]
  313.  
  314.  
  315. <The LZ77 family of compressors>
  316.  
  317.   LZ77-based schemes keep track of the last n bytes of data seen, and when a 
  318. phrase is encountered that has already been seen, they output a pair of 
  319. values corresponding to the position of the phrase in the previously-seen 
  320. buffer of data, and the length of the phrase.  In effect the compressor moves 
  321. a fixed-size *window* over the data (generally referred to as a *sliding 
  322. window*), with the position part of the (position, length) pair referring to 
  323. the position of the phrase within the window.  The most commonly used 
  324. algorithms are derived from the LZSS scheme described by James Storer and 
  325. Thomas Szymanski in 1982.  In this the compressor maintains a window of size 
  326. N bytes and a *lookahead buffer* the contents of which it tries to find a 
  327. match for in the window:
  328.  
  329.   while( lookAheadBuffer not empty )
  330.       {
  331.       get a pointer ( position, match ) to the longest match in the window
  332.           for the lookahead buffer;
  333.  
  334.       if( length > MINIMUM_MATCH_LENGTH )
  335.           {
  336.           output a ( position, length ) pair;
  337.           shift the window length characters along;
  338.           }
  339.       else
  340.           {
  341.           output the first character in the lookahead buffer;
  342.           shift the window 1 character along;
  343.           }
  344.       }
  345.         
  346.   Decompression is simple and fast:  Whenever a ( position, length ) pair is 
  347. encountered, go to that ( position ) in the window and copy ( length ) bytes 
  348. to the output.
  349.  
  350.   Sliding-window-based schemes can be simplified by numbering the input text
  351. characters mod N, in effect creating a circular buffer.  The sliding window
  352. approach automatically creates the LRU effect which must be done explicitly in
  353. LZ78 schemes.  Variants of this method apply additional compression to the
  354. output of the LZSS compressor, which include a simple variable-length code
  355. (LZB), dynamic Huffman coding (LZH), and Shannon-Fano coding (ZIP 1.x)), all
  356. of which result in a certain degree of improvement over the basic scheme,
  357. especially when the data are rather random and the LZSS compressor has little
  358. effect.
  359.   Recently an algorithm was developed which combines the ideas behind LZ77 and
  360. LZ78 to produce a hybrid called LZFG.  LZFG uses the standard sliding window,
  361. but stores the data in a modified trie data structure and produces as output
  362. the position of the text in the trie.  Since LZFG only inserts complete
  363. *phrases* into the dictionary, it should run faster than other LZ77-based
  364. compressors.
  365.  
  366. All popular archivers (arj, lha, zip, zoo) are variations on the LZ77 theme.
  367.  
  368. ------------------------------------------------------------------------------
  369.  
  370. Subject: [71] Introduction to MPEG (long)
  371.  
  372.  
  373. For MPEG players, see item 15 in part 1 of the FAQ.  Frank Gadegast
  374. <phade@cs.tu-berlin.de> also posts a FAQ specialized in MPEG.
  375.  
  376. Introduction written by Mark Adler <madler@cco.caltech.edu> around  
  377. January 1992 (and hence wildly out of date in this fast moving  
  378. area--any volunteers to update this section are welcome):
  379.  
  380. Q. What is MPEG?
  381. A. MPEG is a group of people that meet under ISO (the International
  382.    Standards Organization) to generate standards for digital video
  383.    (sequences of images in time) and audio compression.  In particular,
  384.    they define a compressed bit stream, which implicitly defines a
  385.    decompressor.  However, the compression algorithms are up to the
  386.    individual manufacturers, and that is where proprietary advantage
  387.    is obtained within the scope of a publicly available international
  388.    standard.  MPEG meets roughly four times a year for roughly a week
  389.    each time.  In between meetings, a great deal of work is done by
  390.    the members, so it doesn't all happen at the meetings.  The work
  391.    is organized and planned at the meetings.
  392.  
  393. Q. So what does MPEG stand for?
  394. A. Moving Pictures Experts Group.
  395.  
  396. Q. Does it have anything to do with JPEG?
  397. A. Well, it sounds the same, and they are part of the same subcommittee
  398.    of ISO along with JBIG and MHEG, and they usually meet at the same
  399.    place at the same time.  However, they are different sets of people
  400.    with few or no common individual members, and they have different
  401.    charters and requirements.  JPEG is for still image compression.
  402.  
  403. Q. Then what's JBIG and MHEG?
  404. A. Sorry I mentioned them. Ok, I'll simply say that JBIG is for binary
  405.    image compression (like faxes), and MHEG is for multi-media data
  406.    standards (like integrating stills, video, audio, text, etc.).
  407.    For an introduction to JBIG, see question 74 below.
  408.  
  409. Q. Ok, I'll stick to MPEG.  What has MPEG accomplished?
  410. A. So far (as of January 1992), they have completed the "Committee
  411.    Draft" of MPEG phase I, colloquially called MPEG I.  It defines
  412.    a bit stream for compressed video and audio optimized to fit into
  413.    a bandwidth (data rate) of 1.5 Mbits/s.  This rate is special
  414.    because it is the data rate of (uncompressed) audio CD's and DAT's.
  415.    The draft is in three parts, video, audio, and systems, where the
  416.    last part gives the integration of the audio and video streams
  417.    with the proper timestamping to allow synchronization of the two.
  418.    They have also gotten well into MPEG phase II, whose task is to
  419.    define a bitstream for video and audio coded at around 3 to 10
  420.    Mbits/s.
  421.  
  422. Q. So how does MPEG I work?
  423. A. First off, it starts with a relatively low resolution video
  424.    sequence (possibly decimated from the original) of about 352 by
  425.    240 frames by 30 frames/s (US--different numbers for Europe),
  426.    but original high (CD) quality audio.  The images are in color,
  427.    but converted to YUV space, and the two chrominance channels
  428.    (U and V) are decimated further to 176 by 120 pixels.  It turns
  429.    out that you can get away with a lot less resolution in those
  430.    channels and not notice it, at least in "natural" (not computer
  431.    generated) images.
  432.  
  433.    The basic scheme is to predict motion from frame to frame in the
  434.    temporal direction, and then to use DCT's (discrete cosine
  435.    transforms) to organize the redundancy in the spatial directions.
  436.    The DCT's are done on 8x8 blocks, and the motion prediction is
  437.    done in the luminance (Y) channel on 16x16 blocks.  In other words,
  438.    given the 16x16 block in the current frame that you are trying to
  439.    code, you look for a close match to that block in a previous or
  440.    future frame (there are backward prediction modes where later
  441.    frames are sent first to allow interpolating between frames).
  442.    The DCT coefficients (of either the actual data, or the difference
  443.    between this block and the close match) are "quantized", which
  444.    means that you divide them by some value to drop bits off the
  445.    bottom end.  Hopefully, many of the coefficients will then end up
  446.    being zero.  The quantization can change for every "macroblock"
  447.    (a macroblock is 16x16 of Y and the corresponding 8x8's in both
  448.    U and V).  The results of all of this, which include the DCT
  449.    coefficients, the motion vectors, and the quantization parameters
  450.    (and other stuff) is Huffman coded using fixed tables.  The DCT
  451.    coefficients have a special Huffman table that is "two-dimensional"
  452.    in that one code specifies a run-length of zeros and the non-zero
  453.    value that ended the run.  Also, the motion vectors and the DC
  454.    DCT components are DPCM (subtracted from the last one) coded.
  455.  
  456. Q. So is each frame predicted from the last frame?
  457. A. No.  The scheme is a little more complicated than that.  There are
  458.    three types of coded frames.  There are "I" or intra frames.  They
  459.    are simply a frame coded as a still image, not using any past
  460.    history.  You have to start somewhere.  Then there are "P" or
  461.    predicted frames.  They are predicted from the most recently
  462.    reconstructed I or P frame.  (I'm describing this from the point
  463.    of view of the decompressor.)  Each macroblock in a P frame can
  464.    either come with a vector and difference DCT coefficients for a
  465.    close match in the last I or P, or it can just be "intra" coded
  466.    (like in the I frames) if there was no good match.
  467.  
  468.    Lastly, there are "B" or bidirectional frames.  They are predicted
  469.    from the closest two I or P frames, one in the past and one in the
  470.    future.  You search for matching blocks in those frames, and try
  471.    three different things to see which works best.  (Now I have the
  472.    point of view of the compressor, just to confuse you.)  You try using
  473.    the forward vector, the backward vector, and you try averaging the
  474.    two blocks from the future and past frames, and subtracting that from
  475.    the block being coded.  If none of those work well, you can intra-
  476.    code the block.
  477.  
  478.    The sequence of decoded frames usually goes like:
  479.  
  480.    IBBPBBPBBPBBIBBPBBPB...
  481.  
  482.    Where there are 12 frames from I to I (for US and Japan anyway.)
  483.    This is based on a random access requirement that you need a
  484.    starting point at least once every 0.4 seconds or so.  The ratio
  485.    of P's to B's is based on experience.
  486.  
  487.    Of course, for the decoder to work, you have to send that first
  488.    P *before* the first two B's, so the compressed data stream ends
  489.    up looking like:
  490.  
  491.    0xx312645...
  492.  
  493.    where those are frame numbers.  xx might be nothing (if this is
  494.    the true starting point), or it might be the B's of frames -2 and
  495.    -1 if we're in the middle of the stream somewhere.
  496.  
  497.    You have to decode the I, then decode the P, keep both of those
  498.    in memory, and then decode the two B's.  You probably display the
  499.    I while you're decoding the P, and display the B's as you're
  500.    decoding them, and then display the P as you're decoding the next
  501.    P, and so on.
  502.  
  503. Q. You've got to be kidding.
  504. A. No, really!
  505.  
  506. Q. Hmm.  Where did they get 352x240?
  507. A. That derives from the CCIR-601 digital television standard which
  508.    is used by professional digital video equipment.  It is (in the US)
  509.    720 by 243 by 60 fields (not frames) per second, where the fields
  510.    are interlaced when displayed.  (It is important to note though
  511.    that fields are actually acquired and displayed a 60th of a second
  512.    apart.)  The chrominance channels are 360 by 243 by 60 fields a
  513.    second, again interlaced.  This degree of chrominance decimation
  514.    (2:1 in the horizontal direction) is called 4:2:2.  The source
  515.    input format for MPEG I, called SIF, is CCIR-601 decimated by 2:1
  516.    in the horizontal direction, 2:1 in the time direction, and an
  517.    additional 2:1 in the chrominance vertical direction.  And some
  518.    lines are cut off to make sure things divide by 8 or 16 where
  519.    needed.
  520.  
  521. Q. What if I'm in Europe?
  522. A. For 50 Hz display standards (PAL, SECAM) change the number of lines
  523.    in a field from 243 or 240 to 288, and change the display rate to
  524.    50 fields/s or 25 frames/s.  Similarly, change the 120 lines in
  525.    the decimated chrominance channels to 144 lines.  Since 288*50 is
  526.    exactly equal to 240*60, the two formats have the same source data
  527.    rate.
  528.  
  529. Q. You didn't mention anything about the audio compression.
  530. A. Oh, right.  Well, I don't know as much about the audio compression.
  531.    Basically they use very carefully developed psychoacoustic models
  532.    derived from experiments with the best obtainable listeners to
  533.    pick out pieces of the sound that you can't hear.  There are what
  534.    are called "masking" effects where, for example, a large component
  535.    at one frequency will prevent you from hearing lower energy parts
  536.    at nearby frequencies, where the relative energy vs. frequency
  537.    that is masked is described by some empirical curve.  There are
  538.    similar temporal masking effects, as well as some more complicated
  539.    interactions where a temporal effect can unmask a frequency, and
  540.    vice-versa.
  541.  
  542.    The sound is broken up into spectral chunks with a hybrid scheme
  543.    that combines sine transforms with subband transforms, and the
  544.    psychoacoustic model written in terms of those chunks.  Whatever
  545.    can be removed or reduced in precision is, and the remainder is
  546.    sent.  It's a little more complicated than that, since the bits
  547.    have to be allocated across the bands.  And, of course, what is
  548.    sent is entropy coded.
  549.  
  550. Q. So how much does it compress?
  551. A. As I mentioned before, audio CD data rates are about 1.5 Mbits/s.
  552.    You can compress the same stereo program down to 256 Kbits/s with
  553.    no loss in discernable quality.  (So they say.  For the most part
  554.    it's true, but every once in a while a weird thing might happen
  555.    that you'll notice.  However the effect is very small, and it takes
  556.    a listener trained to notice these particular types of effects.)
  557.    That's about 6:1 compression.  So, a CD MPEG I stream would have
  558.    about 1.25 MBits/s left for video.  The number I usually see though
  559.    is 1.15 MBits/s (maybe you need the rest for the system data
  560.    stream).  You can then calculate the video compression ratio from
  561.    the numbers here to be about 26:1.  If you step back and think
  562.    about that, it's little short of a miracle.  Of course, it's lossy
  563.    compression, but it can be pretty hard sometimes to see the loss,
  564.    if you're comparing the SIF original to the SIF decompressed.  There
  565.    is, however, a very noticeable loss if you're coming from CCIR-601
  566.    and have to decimate to SIF, but that's another matter.  I'm not
  567.    counting that in the 26:1.
  568.  
  569.    The standard also provides for other bit rates ranging from 32Kbits/s
  570.    for a single channel, up to 448 Kbits/s for stereo.
  571.  
  572. Q. What's phase II?
  573. A. As I said, there is a considerable loss of quality in going from
  574.    CCIR-601 to SIF resolution.  For entertainment video, it's simply
  575.    not acceptable.  You want to use more bits and code all or almost
  576.    all the CCIR-601 data.  From subjective testing at the Japan
  577.    meeting in November 1991, it seems that 4 MBits/s can give very
  578.    good quality compared to the original CCIR-601 material.  The
  579.    objective of phase II is to define a bit stream optimized for these
  580.    resolutions and bit rates.
  581.  
  582. Q. Why not just scale up what you're doing with MPEG I?
  583. A. The main difficulty is the interlacing.  The simplest way to extend
  584.    MPEG I to interlaced material is to put the fields together into
  585.    frames (720x486x30/s).  This results in bad motion artifacts that
  586.    stem from the fact that moving objects are in different places
  587.    in the two fields, and so don't line up in the frames.  Compressing
  588.    and decompressing without taking that into account somehow tends to
  589.    muddle the objects in the two different fields.
  590.  
  591.    The other thing you might try is to code the even and odd field
  592.    streams separately.  This avoids the motion artifacts, but as you
  593.    might imagine, doesn't get very good compression since you are not
  594.    using the redundancy between the even and odd fields where there
  595.    is not much motion (which is typically most of image).
  596.  
  597.    Or you can code it as a single stream of fields.  Or you can
  598.    interpolate lines.  Or, etc. etc.  There are many things you can
  599.    try, and the point of MPEG II is to figure out what works well.
  600.    MPEG II is not limited to consider only derivations of MPEG I.
  601.    There were several non-MPEG I-like schemes in the competition in
  602.    November, and some aspects of those algorithms may or may not
  603.    make it into the final standard for entertainment video compression.
  604.  
  605. Q. So what works?
  606. A. Basically, derivations of MPEG I worked quite well, with one that
  607.    used wavelet subband coding instead of DCT's that also worked very
  608.    well.  Also among the worked-very-well's was a scheme that did not
  609.    use B frames at all, just I and P's.  All of them, except maybe one,
  610.    did some sort of adaptive frame/field coding, where a decision is
  611.    made on a macroblock basis as to whether to code that one as one
  612.    frame macroblock or as two field macroblocks.  Some other aspects
  613.    are how to code I-frames--some suggest predicting the even field
  614.    from the odd field.  Or you can predict evens from evens and odds
  615.    or odds from evens and odds or any field from any other field, etc.
  616.  
  617. Q. So what works?
  618. A. Ok, we're not really sure what works best yet.  The next step is
  619.    to define a "test model" to start from, that incorporates most of
  620.    the salient features of the worked-very-well proposals in a
  621.    simple way.  Then experiments will be done on that test model,
  622.    making a mod at a time, and seeing what makes it better and what
  623.    makes it worse.  Example experiments are, B's or no B's, DCT vs.
  624.    wavelets, various field prediction modes, etc.  The requirements,
  625.    such as implementation cost, quality, random access, etc. will all
  626.    feed into this process as well.
  627.  
  628. Q. When will all this be finished?
  629. A. I don't know.  I'd have to hope in about a year or less.
  630.  
  631. Q. How do I join MPEG?
  632. A. You don't join MPEG.  You have to participate in ISO as part of a
  633.    national delegation.  How you get to be part of the national
  634.    delegation is up to each nation.  I only know the U.S., where you
  635.    have to attend the corresponding ANSI meetings to be able to
  636.    attend the ISO meetings.  Your company or institution has to be
  637.    willing to sink some bucks into travel since, naturally, these
  638.    meetings are held all over the world.  (For example, Paris,
  639.    Santa Clara, Kurihama Japan, Singapore, Haifa Israel, Rio de
  640.    Janeiro, London, etc.)
  641.  
  642. Q. Well, then how do I get the documents, like the MPEG I draft?
  643. A. MPEG is a draft ISO standard. It's exact name is ISO CD 11172.
  644.    The draft consists of three parts: System, Video, and Audio. The
  645.    System part (11172-1) deals with synchronization and multiplexing
  646.    of audio-visual information, while the Video (11172-2) and Audio
  647.    part (11172-3) address the video and the audio compression techniques
  648.    respectively.
  649.  
  650.    You may order it from your national standards body (e.g. ANSI in
  651.    the USA) or buy it from companies like
  652.      OMNICOM
  653.      phone +44 438 742424
  654.      FAX +44 438 740154
  655.  
  656. ------------------------------------------------------------------------------
  657.  
  658. Subject: [72] What is wavelet theory?
  659.  
  660.  
  661. Preprints and software are available by anonymous ftp from the
  662. Yale Mathematics Department computer ceres.math.yale.edu[130.132.23.22],
  663. in pub/wavelets and pub/software.
  664.  
  665. epic and hcompress are wavelet coders. (For source code, see item 15
  666. in part one).
  667.  
  668. Bill Press of Harvard/CfA has made some things available for anonymous
  669. ftp on cfata4.harvard.edu [128.103.40.79] in directory /pub. There is
  670. a short TeX article on wavelet theory (wavelet.tex, to be included in
  671. a future edition of Numerical Recipes), some sample wavelet code
  672. (wavelet.f, in FORTRAN - sigh), and a beta version of an astronomical
  673. image compression program which he is currently developing (FITS
  674. format data files only, in fitspress08.tar.Z).
  675.  
  676. A mailing list dedicated to research on wavelets has been set up at the
  677. University of South Carolina. To subscribe to this mailing list, send a
  678. message with "subscribe" as the subject to wavelet@math.scarolina.edu.
  679.  
  680.  
  681. A 5 minute course in wavelet transforms, by Richard Kirk <rak@crosfield.co.uk>:
  682.  
  683. Do you know what a Haar transform is? Its a transform to another orthonormal
  684. space (like the DFT), but the basis functions are a set of square wave bursts
  685. like this...
  686.  
  687.    +--+                         +------+
  688.    +  |  +------------------    +      |      +--------------
  689.       +--+                             +------+
  690.  
  691.          +--+                                 +------+
  692.    ------+  |  +------------    --------------+      |      +
  693.             +--+                                     +------+
  694.  
  695.                +--+             +-------------+
  696.    ------------+  |  +------    +             |             +
  697.                   +--+                        +-------------+
  698.  
  699.                      +--+       +---------------------------+
  700.    ------------------+  |  +    +                           +
  701.                         +--+
  702.  
  703. This is the set of functions for an 8-element 1-D Haar transform. You
  704. can probably see how to extend this to higher orders and higher dimensions
  705. yourself. This is dead easy to calculate, but it is not what is usually
  706. understood by a wavelet transform.
  707.  
  708. If you look at the eight Haar functions you see we have four functions
  709. that code the highest resolution detail, two functions that code the
  710. coarser detail, one function that codes the coarser detail still, and the 
  711. top function that codes the average value for the whole `image'.
  712.  
  713. Haar function can be used to code images instead of the DFT. With bilevel
  714. images (such as text) the result can look better, and it is quicker to code.
  715. Flattish regions, textures, and soft edges in scanned images get a nasty
  716. `blocking' feel to them. This is obvious on hardcopy, but can be disguised on
  717. color CRTs by the effects of the shadow mask. The DCT gives more consistent
  718. results.
  719.  
  720. This connects up with another bit of maths sometimes called Multispectral
  721. Image Analysis, sometimes called Image Pyramids.
  722.  
  723. Suppose you want to produce a discretely sampled image from a continuous 
  724. function. You would do this by effectively `scanning' the function using a
  725. sinc function [ sin(x)/x ] `aperture'. This was proved by Shannon in the 
  726. `forties. You can do the same thing starting with a high resolution
  727. discretely sampled image. You can then get a whole set of images showing 
  728. the edges at different resolutions by differencing the image at one
  729. resolution with another version at another resolution. If you have made this
  730. set of images properly they ought to all add together to give the original 
  731. image.
  732.  
  733. This is an expansion of data. Suppose you started off with a 1K*1K image.
  734. You now may have a 64*64 low resolution image plus difference images at 128*128
  735. 256*256, 512*512 and 1K*1K. 
  736.  
  737. Where has this extra data come from? If you look at the difference images you 
  738. will see there is obviously some redundancy as most of the values are near 
  739. zero. From the way we constructed the levels we know that locally the average
  740. must approach zero in all levels but the top. We could then construct a set of
  741. functions out of the sync functions at any level so that their total value 
  742. at all higher levels is zero. This gives us an orthonormal set of basis 
  743. functions for a transform. The transform resembles the Haar transform a bit,
  744. but has symmetric wave pulses that decay away continuously in either direction
  745. rather than square waves that cut off sharply. This transform is the
  746. wavelet transform ( got to the point at last!! ).
  747.  
  748. These wavelet functions have been likened to the edge detecting functions
  749. believed to be present in the human retina.
  750.  
  751.  
  752. Loren I. Petrich <lip@s1.gov> adds that order 2 or 3 Daubechies
  753. discrete wavelet transforms have a speed comparable to DCT's, and
  754. usually achieve compression a factor of 2 better for the same image
  755. quality than the JPEG 8*8 DCT. (See item 25 in part 1 of this FAQ for
  756. references on fast DCT algorithms.)
  757.  
  758. ------------------------------------------------------------------------------
  759.  
  760. Subject: [73] What is the theoretical compression limit?
  761.  
  762.  
  763. There is no compressor that is guaranteed to compress all possible input
  764. files. If it compresses some files, then it must enlarge some others.
  765. This can be proven by a simple counting argument (see question 9).
  766.  
  767. As an extreme example, the following algorithm achieves 100%
  768. compression for one special input file and enlarges all other files by
  769. only one bit:
  770.  
  771. - if the input data is <insert your favorite one here>, output an empty file.
  772. - otherwise output one bit (zero or one) followed by the input data.
  773.  
  774. The concept of theoretical compression limit is meaningful only
  775. if you have a model for your input data. See question 70 above
  776. for some examples of data models.
  777.  
  778. ------------------------------------------------------------------------------
  779.  
  780. Subject: [74] Introduction to JBIG
  781.  
  782.  
  783. A short introduction, written by Mark Adler <madler@cco.caltech.edu>:
  784.  
  785.   JBIG losslessly compresses binary (one-bit/pixel) images.  (The B stands
  786.   for bi-level.)  Basically it models the redundancy in the image as the
  787.   correlations of the pixel currently being coded with a set of nearby
  788.   pixels called the template.  An example template might be the two
  789.   pixels preceding this one on the same line, and the five pixels centered
  790.   above this pixel on the previous line.  Note that this choice only
  791.   involves pixels that have already been seen from a scanner.
  792.  
  793.   The current pixel is then arithmetically coded based on the eight-bit
  794.   (including the pixel being coded) state so formed.  So there are (in this
  795.   case) 256 contexts to be coded.  The arithmetic coder and probability
  796.   estimator for the contexts are actually IBM's (patented) Q-coder.  The
  797.   Q-coder uses low precision, rapidly adaptable (those two are related)
  798.   probability estimation combined with a multiply-less arithmetic coder.
  799.   The probability estimation is intimately tied to the interval calculations
  800.   necessary for the arithmetic coding.
  801.  
  802.   JBIG actually goes beyond this and has adaptive templates, and probably
  803.   some other bells and whistles I don't know about.  You can find a
  804.   description of the Q-coder as well as the ancestor of JBIG in the Nov 88
  805.   issue of the IBM Journal of Research and Development.  This is a very
  806.   complete and well written set of five articles that describe the Q-coder
  807.   and a bi-level image coder that uses the Q-coder.
  808.  
  809.   You can use JBIG on grey-scale or even color images by simply applying
  810.   the algorithm one bit-plane at a time.  You would want to recode the
  811.   grey or color levels first though, so that adjacent levels differ in
  812.   only one bit (called Gray-coding).  I hear that this works well up to
  813.   about six bits per pixel, beyond which JPEG's lossless mode works better.
  814.   You need to use the Q-coder with JPEG also to get this performance.
  815.  
  816.   Actually no lossless mode works well beyond six bits per pixel, since
  817.   those low bits tend to be noise, which doesn't compress at all.
  818.  
  819.   Anyway, the intent of JBIG is to replace the current, less effective
  820.   group 3 and 4 fax algorithms.
  821.  
  822.  
  823. Another introduction to JBIG, written by Hank van Bekkem <jbek@oce.nl>:
  824.  
  825.   The following description of the JBIG algorithm is derived from
  826.   experiences with a software implementation I wrote following the
  827.   specifications in the revision 4.1 draft of September 16, 1991. The
  828.   source will not be made available in the public domain, as parts of
  829.   JBIG are patented.
  830.  
  831.   JBIG (Joint Bi-level Image Experts Group) is an experts group of ISO,
  832.   IEC and CCITT (JTC1/SC2/WG9 and SGVIII). Its job is to define a
  833.   compression standard for lossless image coding ([1]). The main
  834.   characteristics of the proposed algorithm are:
  835.   - Compatible progressive/sequential coding. This means that a
  836.     progressively coded image can be decoded sequentially, and the
  837.     other way around.
  838.   - JBIG will be a lossless image compression standard: all bits in
  839.     your images before and after compression and decompression will be
  840.     exactly the same.
  841.  
  842.   In the rest of this text I will first describe the JBIG algorithm in
  843.   a short abstract of the draft. I will conclude by saying something
  844.   about the value of JBIG.
  845.  
  846.  
  847.   JBIG algorithm.
  848.   --------------
  849.  
  850.   JBIG parameter P specifies the number of bits per pixel in the image.
  851.   Its allowable range is 1 through 255, but starting at P=8 or so,
  852.   compression will be more efficient using other algorithms. On the
  853.   other hand, medical images such as chest X-rays are often stored with
  854.   12 bits per pixel, while no distorsion is allowed, so JBIG can
  855.   certainly be of use in this area. To limit the number of bit changes
  856.   between adjacent decimal values (e.g. 127 and 128), it is wise to use
  857.   Gray coding before compressing multi-level images with JBIG. JBIG
  858.   then compresses the image on a bitplane basis, so the rest of this
  859.   text assumes bi-level pixels.
  860.  
  861.   Progressive coding is a way to send an image gradually to a receiver
  862.   instead of all at once. During sending, more detail is sent, and the
  863.   receiver can build the image from low to high detail. JBIG uses
  864.   discrete steps of detail by successively doubling the resolution. The
  865.   sender computes a number of resolution layers D, and transmits these
  866.   starting at the lowest resolution Dl. Resolution reduction uses
  867.   pixels in the high resolution layer and some already computed low
  868.   resolution pixels as an index into a lookup table. The contents of
  869.   this table can be specified by the user.
  870.  
  871.   Compatibility between progressive and sequential coding is achieved
  872.   by dividing an image into stripes. Each stripe is a horizontal bar
  873.   with a user definable height. Each stripe is separately coded and
  874.   transmitted, and the user can define in which order stripes,
  875.   resolutions and bitplanes (if P>1) are intermixed in the coded data.
  876.   A progressive coded image can be decoded sequentially by decoding
  877.   each stripe, beginning by the one at the top of the image, to its
  878.   full resolution, and then proceeding to the next stripe. Progressive
  879.   decoding can be done by decoding only a specific resolution layer
  880.   from all stripes.
  881.  
  882.   After dividing an image into bitplanes, resolution layers and
  883.   stripes, eventually a number of small bi-level bitmaps are left to
  884.   compress. Compression is done using a Q-coder. Reference [2]
  885.   contains a full description, I will only outline the basic principles
  886.   here.
  887.  
  888.   The Q-coder codes bi-level pixels as symbols using the probability of
  889.   occurrence of these symbols in a certain context. JBIG defines two
  890.   kinds of context, one for the lowest resolution layer (the base
  891.   layer), and one for all other layers (differential layers).
  892.   Differential layer contexts contain pixels in the layer to be coded,
  893.   and in the corresponding lower resolution layer.
  894.  
  895.   For each combination of pixel values in a context, the probability
  896.   distribution of black and white pixels can be different. In an all
  897.   white context, the probability of coding a white pixel will be much
  898.   greater than that of coding a black pixel. The Q-coder assigns, just
  899.   like a Huffman coder, more bits to less probable symbols, and so
  900.   achieves compression. The Q-coder can, unlike a Huffmann coder,
  901.   assign one output codebit to more than one input symbol, and thus is
  902.   able to compress bi-level pixels without explicit clustering, as
  903.   would be necessary using a Huffman coder.
  904.  
  905.   Maximum compression will be achieved when all probabilities (one set
  906.   for each combination of pixel values in the context) follow the
  907.   probabilities of the pixels. The Q-coder therefore continuously
  908.   adapts these probabilities to the symbols it sees.
  909.  
  910.  
  911.   JBIG value.
  912.   ----------
  913.  
  914.   In my opinion, JBIG can be regarded as two combined devices:
  915.   - Providing the user the service of sending or storing multiple
  916.     representations of images at different resolutions without any
  917.     extra cost in storage. Differential layer contexts contain pixels
  918.     in two resolution layers, and so enable the Q-coder to effectively
  919.     code the difference in information between the two layers, instead
  920.     of the information contained in every layer. This means that,
  921.     within a margin of approximately 5%, the number of resolution
  922.     layers doesn't effect the compression ratio.
  923.   - Providing the user a very efficient compression algorithm, mainly
  924.     for use with bi-level images. Compared to CCITT Group 4, JBIG is
  925.     approximately 10% to 50% better on text and line art, and even
  926.     better on halftones. JBIG is however, just like Group 4, somewhat
  927.     sensitive to noise in images. This means that the compression ratio
  928.     decreases when the amount of noise in your images increases.
  929.  
  930.   An example of an application would be browsing through an image
  931.   database, e.g. an EDMS (engineering document management system).
  932.   Large A0 size drawings at 300 dpi or so would be stored using five
  933.   resolution layers. The lowest resolution layer would fit on a
  934.   computer screen. Base layer compressed data would be stored at the
  935.   beginning of the compressed file, thus making browsing through large
  936.   numbers of compressed drawings possible by reading and decompressing
  937.   just the first small part of all files. When the user stops browsing,
  938.   the system could automatically start decompressing all remaining
  939.   detail for printing at high resolution.
  940.  
  941.   [1] "Progressive Bi-level Image Compression, Revision 4.1", ISO/IEC
  942.       JTC1/SC2/WG9, CD 11544, September 16, 1991
  943.   [2] "An overview of the basic principles of the Q-coder adaptive
  944.       binary arithmetic coder", W.B. Pennebaker, J.L. Mitchell, G.G.
  945.       Langdon, R.B. Arps, IBM Journal of research and development,
  946.       Vol.32, No.6, November 1988, pp. 771-726 (See also the other
  947.       articles about the Q-coder in this issue)
  948.  
  949. ------------------------------------------------------------------------------
  950.  
  951. Subject: [75] Introduction to JPEG
  952.  
  953. Here is a brief overview of the inner workings of JPEG, plus some
  954. references for more detailed information, written by Tom Lane
  955. <tgl+@cs.cmu.edu>.  Please read item 19 in part 1 first.
  956.  
  957. JPEG works on either full-color or gray-scale images; it does not handle
  958. bilevel (black and white) images, at least not efficiently.  It doesn't
  959. handle colormapped images either; you have to pre-expand those into an
  960. unmapped full-color representation.  JPEG works best on "continuous tone"
  961. images; images with many sudden jumps in color values will not compress well.
  962.  
  963. There are a lot of parameters to the JPEG compression process.  By adjusting
  964. the parameters, you can trade off compressed image size against reconstructed
  965. image quality over a *very* wide range.  You can get image quality ranging
  966. from op-art (at 100x smaller than the original 24-bit image) to quite
  967. indistinguishable from the source (at about 3x smaller).  Usually the
  968. threshold of visible difference from the source image is somewhere around 10x
  969. to 20x smaller than the original, ie, 1 to 2 bits per pixel for color images.
  970. Grayscale requires a little bit less space.
  971.  
  972. JPEG defines a "baseline" lossy algorithm, plus optional extensions for
  973. progressive and hierarchical coding.  There is also a separate lossless
  974. compression mode; this typically gives about 2:1 compression, ie about 12
  975. bits per color pixel.  Most currently available JPEG hardware and software
  976. handles only the baseline mode.
  977.  
  978.  
  979. Here's the outline of the baseline compression algorithm:
  980.  
  981. 1. Transform the image into a suitable color space.  This is a no-op for
  982. grayscale, but for color images you generally want to transform RGB into a
  983. luminance/chrominance color space (YCbCr, YUV, etc).  The luminance component
  984. is grayscale and the other two axes are color information.  The reason for
  985. doing this is that you can afford to lose a lot more information in the
  986. chrominance components than you can in the luminance component; the human eye
  987. is not as sensitive to high-frequency color info as it is to high-frequency
  988. luminance.  (See any TV system for precedents.)  You don't have to change the
  989. color space if you don't want to, as the remainder of the algorithm works on
  990. each color component independently, and doesn't care just what the data is.
  991. However, compression will be less since you will have to code all the
  992. components at luminance quality.
  993.  
  994. 2. (Optional) Downsample each component by averaging together groups of
  995. pixels.  The luminance component is left at full resolution, while the color
  996. components are usually reduced 2:1 horizontally and either 2:1 or 1:1 (no
  997. change) vertically.  In JPEG-speak these alternatives are usually called
  998. 2h2v and 2h1v sampling, but you may also see the terms "411" and "422"
  999. sampling.  This step immediately reduces the data volume by one-half or
  1000. one-third, while having almost no impact on perceived quality.  (Obviously
  1001. this would not be true if you tried it in RGB color space...)  Note that
  1002. downsampling is not applicable to gray-scale data.
  1003.  
  1004. 3. Group the pixel values for each component into 8x8 blocks.  Transform each
  1005. 8x8 block through a discrete cosine transform (DCT); this is a relative of the
  1006. Fourier transform and likewise gives a frequency map, with 8x8 components.
  1007. Thus you now have numbers representing the average value in each block and
  1008. successively higher-frequency changes within the block.  The motivation for
  1009. doing this is that you can now throw away high-frequency information without
  1010. affecting low-frequency information.  (The DCT transform itself is reversible
  1011. except for roundoff error.)  See question 25 for fast DCT algorithms.
  1012.  
  1013. 4. In each block, divide each of the 64 frequency components by a separate
  1014. "quantization coefficient", and round the results to integers.  This is the
  1015. fundamental information-losing step.  A Q.C. of 1 loses no information;
  1016. larger Q.C.s lose successively more info.  The higher frequencies are normally
  1017. reduced much more than the lower.  (All 64 Q.C.s are parameters to the
  1018. compression process; tuning them for best results is a black art.  It seems
  1019. likely that the best values are yet to be discovered.  Most existing coders
  1020. use simple multiples of the example tables given in the JPEG standard.)
  1021.  
  1022. 5. Encode the reduced coefficients using either Huffman or arithmetic coding.
  1023. (Strictly speaking, baseline JPEG only allows Huffman coding; arithmetic
  1024. coding is an optional extension.)   Notice that this step is lossless, so it
  1025. doesn't affect image quality.  The arithmetic coding option uses Q-coding;
  1026. it is identical to the coder used in JBIG (see question 74).  Be aware that
  1027. Q-coding is patented.  Most existing implementations support only the Huffman
  1028. mode, so as to avoid license fees.  The arithmetic mode offers maybe 5 or 10%
  1029. better compression, which isn't enough to justify paying fees.
  1030.  
  1031. 6. Tack on appropriate headers, etc, and output the result.  In an
  1032. "interchange" JPEG file, all of the compression parameters are included
  1033. in the headers so that the decompressor can reverse the process.  For
  1034. specialized applications, the spec permits the parameters to be omitted
  1035. from the file; this saves several hundred bytes of overhead, but it means
  1036. that the decompressor must know what parameters the compressor used.
  1037.  
  1038.  
  1039. The decompression algorithm reverses this process, and typically adds some
  1040. smoothing steps to reduce pixel-to-pixel discontinuities.
  1041.  
  1042.  
  1043. Extensions:
  1044.  
  1045. The progressive mode is intended to support real-time transmission of images.
  1046. It allows the DCT coefficients to be sent incrementally in multiple "scans"
  1047. of the image.  With each scan, the decoder can produce a higher-quality
  1048. rendition of the image.  Thus a low-quality preview can be sent very quickly,
  1049. then refined as time allows.  Notice that the decoder must do essentially a
  1050. full JPEG decode cycle for each scan, so this scheme is useful only with fast
  1051. decoders (meaning dedicated hardware, at least at present).  However, the
  1052. total number of bits sent can actually be somewhat less than is necessary in
  1053. the baseline mode, especially if arithmetic coding is used.  So progressive
  1054. coding might be useful even if the decoder will simply save up the bits and
  1055. make only one output pass.
  1056.  
  1057. The hierarchical mode represents an image at multiple resolutions.  For
  1058. example, one could provide 512x512, 1024x1024, and 2048x2048 versions of the
  1059. image.  The higher-resolution images are coded as differences from the next
  1060. smaller image, and thus require many fewer bits than they would if stored
  1061. independently.  (However, the total number of bits will be greater than that
  1062. needed to store just the highest-resolution frame.)  Note that the individual
  1063. frames in a hierarchical sequence may be coded progressively if desired.
  1064.  
  1065.  
  1066. Lossless JPEG:
  1067.  
  1068. The separate lossless mode does not use DCT, since roundoff errors prevent a
  1069. DCT calculation from being lossless.  For the same reason, one would not
  1070. normally use colorspace conversion or downsampling, although these are
  1071. permitted by the standard.  The lossless mode simply codes the difference
  1072. between each pixel and the "predicted" value for the pixel.  The predicted
  1073. value is a simple function of the already-transmitted pixels just above and
  1074. to the left of the current one (eg, their average; 8 different predictor
  1075. functions are permitted).  The sequence of differences is encoded using the
  1076. same back end (Huffman or arithmetic) used in the lossy mode.
  1077.  
  1078. The main reason for providing a lossless option is that it makes a good
  1079. adjunct to the hierarchical mode: the final scan in a hierarchical sequence
  1080. can be a lossless coding of the remaining differences, to achieve overall
  1081. losslessness.  This isn't quite as useful as it may at first appear, because
  1082. exact losslessness is not guaranteed unless the encoder and decoder have
  1083. identical IDCT implementations (ie identical roundoff errors).
  1084.  
  1085.  
  1086. References:
  1087.  
  1088. For a good technical introduction to JPEG, see:
  1089.     Wallace, Gregory K.  "The JPEG Still Picture Compression Standard",
  1090.     Communications of the ACM, April 1991 (vol. 34 no. 4), pp. 30-44.
  1091. (Adjacent articles in that issue discuss MPEG motion picture compression,
  1092. applications of JPEG, and related topics.)  If you don't have the CACM issue
  1093. handy, a PostScript file containing a revised version of this article is
  1094. available at ftp.uu.net, graphics/jpeg/wallace.ps.Z.  The file (actually a
  1095. preprint for an article to appear in IEEE Trans. Consum. Elect.) omits the
  1096. sample images that appeared in CACM, but it includes corrections and some
  1097. added material.  Note: the Wallace article is copyright ACM and IEEE, and
  1098. it may not be used for commercial purposes.
  1099.  
  1100. An alternative, more leisurely explanation of JPEG can be found in "The Data
  1101. Compression Book" by Mark Nelson ([Nel 1991], see question 7).  This book
  1102. provides excellent introductions to many data compression methods including
  1103. JPEG, plus sample source code in C.  The JPEG-related source code is far from
  1104. industrial-strength, but it's a pretty good learning tool.
  1105.  
  1106. An excellent textbook about JPEG is "JPEG Still Image Data Compression
  1107. Standard" by William B. Pennebaker and Joan L. Mitchell.  Published by Van
  1108. Nostrand Reinhold, 1993, ISBN 0-442-01272-1.  650 pages, price US$59.95.
  1109. (VNR will accept credit card orders at 800/842-3636, or get your local
  1110. bookstore to order it.)  This book includes the complete text of the ISO
  1111. JPEG standards, DIS 10918-1 and draft DIS 10918-2.  Review by Tom Lane:
  1112. "This is by far the most complete exposition of JPEG in existence.  It's
  1113. written by two people who know what they are talking about: both serve on the
  1114. ISO JPEG standards committee.  If you want to know how JPEG works or why it
  1115. works that way, this is the book to have."
  1116.  
  1117. There are a number of errors in the first printing of the Pennebaker
  1118. & Mitchell book.  An errata list is available at ftp.uu.net:
  1119. graphics/jpeg/pm.errata.  At last report, all were fixed in the
  1120. second printing.
  1121.  
  1122. The official specification of JPEG is not currently available on-line.
  1123. I hear that CCITT specs may be on-line sometime soon, which would change this.
  1124. At the moment, your best bet is to buy the Pennebaker and Mitchell textbook.
  1125.