Subject: Re: compface

From: Richard Burridge <[email-masked]>
Date: Thu, 12 Oct 2000 11:36:22 -0700 (PDT)

Hi Anders,

> I'm working on the faces support for the exmh mail user agent. Exmh 
> currently supports x-faces though a user specified external program. 
> The usual recommendation is to use 'uncompface | ikon2xbm' or 
> 'uncompace -X'. I was thinking that it would be good to have an 
> internal implementation of that functionality if external binaries are 
> not available.
> 
> Is there a spec available for the involved formats? From my glance at 
> compface.h, it looks like the compression algorithm uses externally 
> derived data to set its internal dictionaries and frequency tables. Is 
> that correct?

The best person to ask here is the author of that code, James Ashton.
I worked with James on this when he was at Sydney University (like 10 years
ago). I just did a quick web search, and he appears to now be at ANU. See:

http://www.syseng.anu.edu.au/~jaa/

I've also cc:'ed him on this email. James, here's a blast from the past.
Can you help out?

Thanks.

---

From: James Ashton <[email-masked]>
Date: Fri, 13 Oct 2000 09:34:25 +1100 (EST)

>http://www.syseng.anu.edu.au/~jaa/

That's me.

There's no spec beyond the code I'm afraid.  From my memory, the most
important part of the algorithm (where most of the compression takes
place) is the first step.  Pixels are treated in raster order from left
to right, top to bottom.  A lookup table is used to predict what colour
each pixel will be based on twelve nearby, already calculated pixels:
the two immediately to the left on the same row and five each centred
on two rows above.  Separate lookup tables are used to deal with the
edge cases where not all predictor twelve pixels are in the image.

A new image is generated with pixels set to black only where the above
predictive algorithm is wrong.  Since this image will, in general, be
mostly white with a few black pixels, it can be effectively
compressed.  I think the image is divided up into 16x16 blocks (nine of
them for the default 48x48 faces) and each block is compressed in
turn.  The algorithm notes whether the block is all white, all black,
or a mixture.  In the case of a mixture, the block is divided into four
smaller squares and the algorithm continues recursively.

In order to efficiently code the black/white/mixture information,
statistical information about the probability of each case is used to
minimise the number of bits required.  This step is quite time
consuming as it involves a simple, purpose written, infinite precision
arithmetic library.  The image after this step is effectively
represented as a very large number.

The final stage is simply to print this number in a form transportable
via email.  All printable ASCII characters (95 I think) are used.  The
number is just printed in base 95 using these characters with spaces
and newlines added to keep everything on an 80 character line within
the email headers.

Warning:  The above describes code that I haven't looked at in a long
time.  I hope my memory isn't playing too many tricks on me.
--
James Ashton    		VK1XJA  		  System Administrator
http://wwwsyseng.anu.edu.au/~jaa       	     Department of Systems Engineering
Voice +61 2 6279 8675  Research School of Information Sciences and Engineering
FAX   +61 2 6279 8688				Australian National University
Email [email-masked]   		   Canberra ACT 0200 Australia