Subject: adaptive arithmetic coding for images

From: [email-masked] (Ed Vielmetti)
Date: 16 Feb 91 01:21:43 GMT

Here's an article from the QUIPU list which might be interesting to
people who read these groups.

I have not heard of this "JBIG" before, but it sounds interesting --
any leads or pointers to it would be welcomed.

--Ed

ps.  Harry, if you are reading this, could you add your comments?

From: Harry Robinson <[email-masked]>
Subject: Comments on Photo Attribute correspondence
Date: 23 Jan 91 17:04:29 GMT

As the discussion seems to be related to the use of G3 fax coding for pictures
of different sorts, a few comments might be in order.

1. Gp3 coding was designed for compression of documents thought to be typical 
of office correspondence, not for photographs or other types of image. It uses 
a Huffman code optimised for a selected range of representative documents, 
with an optional extension to take account of line to line correlation. It is
not adaptive. The Huffman code is often referred to as the 1D code, and the
code with extension as the the 2D code. The Gp3 code has many options which
facsimile transmitters and receivers may negotiate at call set-up time. 

2. One option of the Gp3 code is the "uncompressed mode". It is intended to 
deal with small areas of a document, eg cross-hatching around borders of text
or line drawings. It does indeed produce a 20% overhead relative to uncoded
documents, but does enable documents with small areas of such material to
coded by the Gp3 algorithm without massive document expansion (negative
compression?) in these difficult areas. It is not intended to code whole
documents since no coding would always be at least 20% more efficient. The 20%
overhead for the uncompressed mode is because it uses bit stuffing in order to
remove 6 or more consecutive "o"s which are used to escape from the
uncompressed mode. 

3. Gp4 code is essentially the same as Gp3 with a few changes to reflect the 
intention to allow it to be used in an error free transmission environment. 
Hence it dispenses with the Gp3 end of line (EOL) code, and will allow all 
scan lines to be coded using the 2D extension (which is not an option in Gp4). 
In Gp3 a K factor of 2 or 4 ensures that one dimensional coding must be used 
periodically in order to limit the vertical propogation of image disturbances 
in the event of transmission errors.
 
4. Gp4 is also intended for higher resolutions (up to 400 x400 picture points 
per inch) although unfortunately the Gp3 compression algorithm was not altered
to optimise its use at higher resolutions. 

5. The Joint Photographic Experts Group (JPEG) is standardising the encoding
of photographic type images which may be relevant to your requirements - I am
not active in this area so I am not sure. However the Joint Bi-level Image
experts Group (JBIG) is another working group in the joint ISO/IEC
JTC1/SC2/WG8 working group on the Coded Representation of Picture and Audio
Information which is certainly relevant.

6. JBIG is concerned with bi-level image, ie images that can be printed for 
example with ink on paper. This means office correspondence type images such 
as currently handled by Gp3 an Gp4. It also means photographic images that 
have been "screened" in order to for example print them on paper. In 
additional to conventional screening, which represents different shades of 
grey by dots of different diameter, dither processes can also be handled, 
so that photographic material that has been electronically converted into a 
two level image can be compressed. 

7. The JBIG experts report that their code is (only) about 20% better than the
Gp4 code for Gp3/ Gp4 type documents. However they claim very much better
results than Gp4 for screened and dithered images. 
 
8. The  JBIG code has been developed over the last few years by the   
"protagonists" in the JBIG experts group, and would seem to be ready for 
agreement. The only stumbling block seems to be whether the vested interests 
can agree, because the JBIG code has a wider potential scope than just 
facsimile transmission, eg image databases and retrieval, which may affect the 
final detail of the standard. In addition to a wider range of applications, 
there are also tradeoffs in terms of whether software or hardware 
optimisations should be included.

8. In summary, I believe that Gp3 and Gp4 should be used for only those images
for which they were designed, ie not for screened or dithered images, and
pressure should be put on JBIG to finalise its standard so we can all use it.

PS. Big Blue and others have invested a lot in the JBIG code, which uses an
adaptive, Arithmetic code, and also has a useful progressive update mode which 
permits images to be received a low resolution, followed by higher resolution 
detail until finally, if needed, the full resolution image is received. Other 
adaptive coding systems do exist which may prove more efficient than the 
current JBIG coding scheme, but they need much development work before they 
can be taken seriously, and in the meantime we should push for JBIG.

Harry Robinson