home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / compress / 4286 < prev    next >
Encoding:
Internet Message Format  |  1993-01-01  |  2.8 KB
  1. Xref: sparky comp.compression:4286 comp.dcom.fax:2357 comp.graphics:13303
  2. Newsgroups: comp.compression,comp.dcom.fax,comp.graphics
  3. Path: sparky!uunet!spool.mu.edu!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!torn!news.ccs.queensu.ca!hausner
  4. From: hausner@qucis.queensu.ca (Alejo Hausner)
  5. Subject: Re: I want specs for CCITT group 4 Fax
  6. Message-ID: <C05zrt.Gz3@knot.ccs.queensu.ca>
  7. Sender: news@knot.ccs.queensu.ca (Netnews control)
  8. Organization: M.Sc, C.S, Queen's, Kingston, Canada.
  9. References: <freek.725838286@groucho.phil.ruu.nl>
  10. Date: Fri, 1 Jan 1993 07:35:53 GMT
  11. Lines: 67
  12.  
  13. In article <freek.725838286@groucho.phil.ruu.nl> freek@phil.ruu.nl (Freek Wiedijk) writes:
  14. >Subject says it all.  It is question 18 in the FAQ of
  15. >comp.compression.
  16. >
  17.  
  18. As I understand it, CCITT Group 4 is a method for compressing
  19. pixelized black-and-white images.  I'll give the basic ideas, and
  20. append some references.
  21.  
  22. Most b/w images have have groups of adjacent pixels which are the
  23. same colour.  Thus scanning the image row by row from top to
  24. bottom produces sequences of identical pixels, or "runs".  There
  25. will be a run of black pixels, then a whole run of white one,
  26. then black, etc.  Considerable compression is achieved by
  27. run-length encoding.  This means that instead of sending every
  28. pixel, we send the length of each run, and the colour of the
  29. pixels in the run.  Thus
  30.  
  31.    wwwbbwwwbbbbbwww
  32.  
  33. becomes
  34.  
  35.    3w2b3w5b3w
  36.  
  37. Further compression is possible by noting that runs alternate, so
  38. that the colour of the pixels can be inferred from the context.
  39. As long as we agree that the first run will be white, we just
  40. need to send the numbers
  41.  
  42.    3,2,3,5,3
  43.  
  44. to convey the same information.  If the first run is black, we
  45. stick a 0-length white run to keep things clear.
  46.  
  47. A final step involves using Huffman codes to further compress the
  48. number of bits sent.  For example, printed text will have a lot
  49. of parts where the pixel rows cross the vertical bits of letters.
  50. In those places, there will be runs of 2 or 3 black pixels.  By
  51. using short codes to send those run lengths and longer codes for
  52. others, Huffman coding saves transmission (or storage) time.
  53.  
  54. Hope that helps.
  55.  
  56.  
  57. The reference for a paper on the fax standard is:
  58.  
  59. R. Hunter and A.H. Robinson, "International Digital Facsimile Coding
  60. Standards", in "Proceedings of the IEEE", 68:7, pp 854-867 (1980).
  61.  
  62. Ed Kershenbaum tells me that there is software on the net
  63. implementing the standard:
  64.  
  65. > Take a look at Sam Leffler's public domain tiff library 
  66. > (~/pub/graphics/tiff/v3.0.tar.Z on sgi.com).
  67. >
  68. > Tiff handles Group 4 compression.  Included with the library are several
  69. > utilities to manipulate tiff images.  
  70. >
  71. > The TIFF specification documents include an appendix on the CCITT 
  72. > compression algorithms.  You can download it from the same place
  73. > (TIFF6.ps.Z).
  74. >
  75. > kershenb@gsc.gsi.com
  76.  
  77. Alejo Hausner (hausner@qucis.queensu.ca)
  78.  
  79.  
  80.