From: jgro@netcom.com (Jeremy G)
Subject: Re: I want specs for CCITT group 4 Fax
Organization: Not that I'm aware of :-)
Date: Fri, 1 Jan 1993 23:40:38 GMT

In article <C05zrt.Gz3@knot.ccs.queensu.ca> hausner@qucis.queensu.ca (Alejo Hausner) writes:
>In article <freek.725838286@groucho.phil.ruu.nl> freek@phil.ruu.nl (Freek Wiedijk) writes:
>>Subject says it all.  It is question 18 in the FAQ of
>>comp.compression.
>>
>
>As I understand it, CCITT Group 4 is a method for compressing
>pixelized black-and-white images.  I'll give the basic ideas, and
>append some references.
>
>Most b/w images have have groups of adjacent pixels which are the
>same colour.  Thus scanning the image row by row from top to
>bottom produces sequences of identical pixels, or "runs".  There
>will be a run of black pixels, then a whole run of white one,
>then black, etc.  Considerable compression is achieved by
>run-length encoding.  This means that instead of sending every
>pixel, we send the length of each run, and the colour of the
>pixels in the run.  Thus
>
>   wwwbbwwwbbbbbwww
>
>becomes
>
>   3w2b3w5b3w
>
>Further compression is possible by noting that runs alternate, so
>that the colour of the pixels can be inferred from the context.
>As long as we agree that the first run will be white, we just
>need to send the numbers
>
>   3,2,3,5,3
>
>to convey the same information.  If the first run is black, we
>stick a 0-length white run to keep things clear.
>
>A final step involves using Huffman codes to further compress the
>number of bits sent.  For example, printed text will have a lot
>of parts where the pixel rows cross the vertical bits of letters.
>In those places, there will be runs of 2 or 3 black pixels.  By
>using short codes to send those run lengths and longer codes for
>others, Huffman coding saves transmission (or storage) time.
>
>Hope that helps.
>


Please note that this does not describe "Group 4" compression.  This
is an excellent description of the standard "uncompressed" (or 1
dimensionally compressed) fax encoding, also known as run-length
encoding.  Group 4, however, takes this another step.

Briefly, Group 4 compression starts with the frist line encoded as
described above.  Then the next line is described relative to the
first line.  Each color transition is described as being so many
pixels to the left or right of the transition in the line above it.
The huffman code for "same place as the line above" is one bit, and
that code occurs *very* frequently (about 50% of the transitions in
the few images I have actually measured).  There are special cases for
dropping or adding transitions, and if the transitions move more than
3 pixels to the left or right, Group 4 switches back to run-length
encoding. 

Group 4 is the ISO standard for compressing Black and White bitmapped
images, although in the worst case, the "compressed" image could be
substantially larger than the uncompressed image (about 3 times the
original size, by my estimation).

You can buy the CCITT spec from Global Engineering Documents, but it
is expensive, as you have to by a whole volume of CCITT standards.
You need CCITT Volume VII, Fasicle VII.3 Recommendations T.0-T.63,
which I think goes for something like $175.  In particular, you need
Recommendation T.6, which is the Group 4 compression standard.

-- 
Jeremy G                    Committed to developing user-friendly products,
jgro@netcom.com             Because technology is supposed to make life easier
Newsgroups: comp.compression