Xref: utzoo comp.lang.postscript:7830 comp.dcom.fax:165
Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!stanford.edu!agate!ucbvax!ucbvax.berkeley.edu!sam
From: sam@oxford.berkeley.edu (Sam Leffler)
Newsgroups: comp.lang.postscript,comp.dcom.fax
Subject: Re: Compression of image matrices
Keywords: images, data compression,
Message-ID: <41286@ucbvax.BERKELEY.EDU>
Date: 8 Mar 91 18:24:15 GMT
References: <11757@pasteur.Berkeley.EDU>
Sender: nobody@ucbvax.BERKELEY.EDU
Reply-To: sam@oxford.berkeley.edu (Sam Leffler)
Lines: 41

I tried a number of different schemes for printing Group 3
facsimile on PostScript printers, including decoding the binary
Group 3 data with PostScript in the printer.  My final solution
for the problem was to write a preprocessor that converted
the Group 3-encoded data to a compressed sequence of line draw
operations.  This worked out reasonably well, although it still
took around a 1 minute/page to print a filled page of text on
a LaserWriter-class PostScript printer connected by a 9600
baud serial line.

The basic algorithm for converting the image is straightforward:

1. convert the rasterized data to a sequence of horizontal
   move-draw operations (note that if you're working with
   g3-encoded data, this operation is trivial -- it *is* the g3
   encoding).
2. select an encoding for the move-draw operations (for
   example, using frequency of use)
3. emit a postscript dictionary that defines the move-draw
   operations as short tokens (e.g. /a {100 rmove 2 rlineto})
4. emit the move-draw operations using the dictionary
   encoding built in step 3.

The key things to consider are:

1. how much time you devote to doing the encoding.
2. how much compression you get from doing the encoding.

If you spend lots of time doing the encoding, then you might've
been better off just sending the raw image instead.  Likewise,
halftone data and such may not compress well using a simplistic
scheme -- you may want to do things like rotate the image, look
for coherence in the move-draw pairs, etc.

In any event, this scheme tends to work well for text.  However,
if you're printing lots of facsimile, you're best off getting a printer
that's more suited for your needs -- either one that supports the
PS Level 2 operators for transferring encoded data, or one that
takes plain rasters.

	Sam