home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4796 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  3.5 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!strath-cs!bnr.co.uk!stl!crosfield!rak
  2. From: rak@crosfield.co.uk (Richard Kirk)
  3. Newsgroups: comp.compression
  4. Subject: Re: JPEG compression
  5. Keywords: JPEG, compression
  6. Message-ID: <15979@suns6.crosfield.co.uk>
  7. Date: 25 Jan 93 10:31:31 GMT
  8. References: <peterb.727926960@wambenger>
  9. Organization: Crosfield Electronics, Hemel Hempstead, United Kingdom.
  10. Lines: 61
  11.  
  12. In article <peterb.727926960@wambenger> 
  13. peterb@cs.uwa.oz.au (Peter Bousfield) writes:
  14. >It is my understanding that JPEG compression
  15. >works in basically two parts.
  16. >Step 1: DCT (Discrete Cosine Transform)
  17. >Step 2: Huffman Coding
  18. >I was wanting to know which of these
  19. >two steps contributes more to the compression.
  20.  
  21. This is a bit like..
  22. Which contributes more to a car going fast - the wheels or the engine?
  23. ..but here goes...
  24.  
  25. If compression is to work your data probably has some underlying structure
  26. although it may not be obvious from a dump of the bytes.  You can get a
  27. histogram of the pixel values from an image.  Typically this will have peaks
  28. in it as images have patches of this or that in it, but often the patches will
  29. be rather broad because real objects have shading in them.  You could create
  30. a Huffmann table for the straight pixel values and that might give you 10%
  31. saving.
  32.  
  33. The first thing that might strike you when you see a dump of image values is 
  34. that one pixel value is very often similar to the one before it or above it
  35. or below it or beside it.  If you coded not the pixel values but their
  36. differences (vertically, horizontally, or both) then you would find many of
  37. the difference values were on or near zero.  Your histogram would have a
  38. sharp peak, and Huffmann coding might give you a 50% saving on a scanned image.
  39. This is a specific case of a transformation to lower entropy.  The goal is to
  40. transform your numerical data into a form where all the inherent structure is 
  41. now revealed in the frequency of the string of digital values.  The DCT is 
  42. just a rather more complicated form of differencing and averaging.
  43.  
  44. When doing the differencing as described above the saving might be only 50%
  45. for real scanned images because there might be +/-2 units noise on the scan.
  46. [ This does not mean you have a crummy scanner - it would be difficult to 
  47. get a smooth scan of a grey wedge without this noise, but that's another 
  48. story. ]  This would mean that 3 out of your 8 bits were unpredictable noise, 
  49. and so could not be reconstructed by some algorithm however smart.
  50.  
  51. So - why not replace the noise with other noise?  It may not be the same 
  52. noise but that does not affect how the image looks, provided we preserve the
  53. local average and all the broad features.  It is this stage - the quantization
  54. after the DCT where we truncate the DCT real values to integer intervals - that
  55. we dump our 3-bits-out-of-8 overhead ball and chain, and start to get some real
  56. compression done.  In the 1-D DCT the first value gives the average value of
  57. the 8-pixel interval, the second gives the slope (sort-of), the third gives 
  58. you the curvature in the slope - it's a bit like a polynomial - and so a lot
  59. of the properties we see as being important (like the average and the slopes)
  60. are retained.
  61.  
  62. Which contributes more to a car going fast - the wheels or the engine?
  63. Ha! Don't forget the gearbox!
  64.  
  65. P.S Sorry this explanation is a bit rough, but it is Monday.
  66.  
  67.  
  68.  
  69.  
  70. -- 
  71. Richard Kirk         Image Processing Group    Crosfield Electronics Ltd. U.K.
  72. rak@crosfield.co.uk  0442-230000 x3361/3591    Hemel Hempstead, Herts, HP2 7RH
  73.