jbig.txt

Using the JBIG-KIT library

Using the JBIG-KIT library
--------------------------

Markus Kuhn -- 2004-06-10


This text explains how to use the functions provided by the JBIG-KIT
portable image compression library in your application software.


1  Introduction to JBIG

We start with a short introduction to JBIG1. More detailed information
is provided in the "Introduction and overview" section of the JBIG1
standard. Information on how to obtain a copy of the standard is
available from <http://www.itu.int/> or <http://www.iso.ch/>.

Image data encoded with the JBIG algorithm is separated into planes,
layers, and stripes. Each plane contains one bit per pixel. The number
of planes stored in a JBIG data stream is the number of bits per
pixel. Resolution layers are numbered from 0 to D with 0 being the
layer with the lowest resolution and D the one with the highest. Each
next higher resolution layer has twice the number of rows and columns.
Layer 0 is encoded independently of any other data, all other
resolution layers are encoded as only the difference between the next
lower and the current layer. For applications that require very quick
access to parts of an image, it is possible to divide an image into
several horizontal stripes. All stripes of one resolution layer have
equal size, except perhaps the final one. The number of stripes of an
image is equal in all resolution layers and in all bit planes.

The compressed data stream specified by the JBIG standard is called a
bi-level image entity (BIE). A BIE consists of a 20-byte header,
followed by an optional 1728-byte table (usually not present, except
in special applications) followed by a sequence of stripe data
entities (SDE). Each SDE encodes the content of one single stripe in
one plane of one resolution layer. Between the SDEs, other information
blocks (called floating marker segments) can also be present. They are
used to change certain parameters of the algorithm in the middle of an
image or contain additional application specific information. A BIE
looks like this:


          +------------------------------------------------+
          |                                                |
          |  20-byte header (with image size, #planes,     |
          |  #layers, stripe size, first layer, options,   |
          |  SDE ordering, ...)                            |
          |                                                |
          +------------------------------------------------+
          |                                                |
          |           optional 1728-byte table             |
          |                                                |
          +------------------------------------------------+
          |                                                |
          |       optional floating marker segments        |
          |                                                |
          +------------------------------------------------+
          |                                                |
          |              stripe data entity                |
          |                                                |
          +------------------------------------------------+
          |                                                |
          |       optional floating marker segments        |
          |                                                |
          +------------------------------------------------+
          |                                                |
          |              stripe data entity                |
          |                                                |
          +------------------------------------------------+
            ...
          +------------------------------------------------+
          |                                                |
          |              stripe data entity                |
          |                                                |
          +------------------------------------------------+


One BIE can contain all resolution layers of an image, but it is also
possible to store various resolution layers in several BIEs. The BIE
header contains the number of the first and the last resolution layer
stored in this BIE, as well as the size of the highest resolution
layer stored in this BIE. Progressive coding is deactivated by simply
storing the image in one single resolution layer.

Different applications might have different requirements for the order
in which the SDEs for stripes of various planes and layers are stored
in the BIE, so all possible sensible orderings are allowed by the
standard and indicated by four bits in the header.

It is possible to use the raw BIE data stream as specified by the JBIG
standard directly as the format of a file used for storing images.
This is what the pbmtojbg and jbgtopbm conversion tools do that are
provided in this package as demonstration applications. However, as
the BIE format has been designed for a large number of very different
applications, and to allow efficient direct processing by special JBIG
hardware chip implementations, the BIE header contains only the
minimum amount of information absolutely required by the decompression
algorithm. Many features expected from a good file format are missing
in the BIE data stream:

  - no "magic code" in the first few bytes to allow identification
    of the file format on a typeless file system and to allow
    automatic distinction from other compression algorithms

  - no standardized way to encode additional information such as a
    textual description, information about the meaning of various bit
    planes, the physical size and resolution of the document, etc.

  - a checksum to ensure image integrity

  - encryption and signature mechanisms

  - many things more

Raw BIE data streams alone may therefore not be a suitable format for
document archiving and exchange. A standard format for this purpose
would typically combine a BIE representing the image data with an
additional header providing auxiliary information into one file.
Existing established multi-purpose file formats with a rich set of
auxiliary information attributes like TIFF could be extended easily to
also hold JBIG compressed data.

On the other hand, in database applications for instance, a BIE might
be stored directly in a variable length field. Auxiliary information
would then be stored in other fields of the same record, to simply
search operations.


2  Compressing an image

2.1  Format of the source image

To be processed by the JBIG-KIT encoder, the image has to be present
in memory as separate bitmap planes. Each byte of a bitmap contains
eight pixels, where the most significant bit represents the leftmost
of these. Each line of a bitmap has to be stored in an integral number
of bytes. If the image width is not an integral multiple of eight,
then the final byte has to be padded with zero bits.

For example the 23x5 pixels large single plane image:

   .XXXXX..XXX...X...XXX..
   .....X..X..X..X..X.....
   .....X..XXX...X..X.XXX.
   .X...X..X..X..X..X...X.
   ..XXX...XXX...X...XXX..

is represented by the 15 bytes

   01111100 11100010 00111000
   00000100 10010010 01000000
   00000100 11100010 01011100
   01000100 10010010 01000100
   00111000 11100010 00111000

or in hexadecimal notation

   7c e2 38 04 92 40 04 e2 5c 44 92 44 38 e2 38

This is the format used in binary PBM files and it can also be handled
directly by the Xlib library of the X Window System.

As JBIG can also handle images with multiple bit planes, the JBIG-KIT
library functions accept and return always arrays of pointers to
bitmaps with one pointer per plane.

For single-plane images, the standard recommends that a 0 pixel
represents the background and a 1 pixel represents the foreground
color of an image, in other words, 0 is white and 1 is black for
scanned paper documents. For images with several bits per pixel, the
JBIG standard makes no recommendations about how various colors should
be encoded.

For greyscale images, by using a Gray code instead of a simple binary
weighted representation of the pixel intensity, some increase in
coding efficiency can be reached.

A Gray code is also a binary representation of integer numbers, but it
has the property that the representations of the integer numbers i and
(i+1) always differ in exactly one bit. For example, the numbers 0 to
7 can be represented in normal binary code and Gray code as in the
following table:

                           normal
              number    binary code     Gray code
            ---------------------------------------
                0           000            000
                1           001            001
                2           010            011
                3           011            010
                4           100            110
                5           101            111
                6           110            101
                7           111            100

The form of Gray code shown above has the property that the second
half of the code (numbers 4 - 7) is simply the mirrored first half
(numbers 3 - 0) with the first bit set to one. This way, arbitrarily
large Gray codes can be generated quickly by mirroring the above
example and prefixing the first half with zeros and the second half
with ones as often as required. In greyscale images, it is common
practise to use the all-0 code for black and the all-1 code for white.

No matter whether a Gray code or a binary code is used for encoding a
pixel intensity in several bit planes, it always makes sense to store
the most significant (leftmost) bit in plane 0, which is transmitted
first. This way, a decoder could increase the precision of the
displayed pixel intensities while data is still being received and the
basic structure of the image will become visible as early as possible
during the transmission.


2.2  A simple compression application

In order to use JBIG-KIT in your application, just link libjbig.a to
your executable (on Unix systems just add -ljbig and -L. to the
command line options of your compiler, on other systems you will have
to write a new Makefile anyway), copy the file jbig.h into your source
directory and put the line

  #include "jbig.h"

into your source code.

The library interface follows object-oriented programming principles.
You have to declare a variable (object)

  struct jbg_enc_state se;

which contains the current status of an encoder. Then you initialize
the encoder by calling the constructor function

  void jbg_enc_init(struct jbg_enc_state *s, unsigned long x, unsigned long y,
                    int pl, unsigned char **p,
                    void (*data_out)(unsigned char *start, size_t len,
                                     void *file),
                    void *file);

The parameters have the following meaning:

  s             A pointer to the jbg_enc_state structure which you want
                to initialize.

  x             The width of your image.

  y             The height of your image.

  pl            the number of bitmap planes you want to encode.

  p             A pointer to an array of pl pointers, where each is again
                pointing to the first byte of a bitmap as described in
                section 2.1.

  data_out      This is a call-back function which will be called during
                the compression process by libjbig in order to deliver
                the BIE data to the application. The parameters of the
                function data_out are a pointer start to the new block
                of data to be delivered, as well as the number len of