Markus Kuhn -- 1995-09-20
This text explains how to include the functions provided by the
JBIG-KIT portable image compression library into your application
software.
1 Introduction to JBIG
Below follows a short introduction into some technical aspects of the JBIG standard. More detailed information is provided in the "Introduction and overview" section of the JBIG standard. Information about how to obtain a copy of the standard is available on the Internet from <http://www.itu.ch/> 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 lowest resolution layer and D the highest one. Each next higher resolution layer has exactly twice the number of rows and columns than the previous one. 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. In order to allow implementations which 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 and the number of stripes in all resolution layers of one image is equal.
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). These are the data blocks of which each encodes the content of one single stripe in one plane and resolution layer. Between the SDEs, other information blocks (called floating marker segments) can also be present, which 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 |
| |
+------------------------------------------------+
| |
| 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 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 JBIG<->PBM conversion tools that are provided in this package as demonstration applications do. However as the BIE format has been designed for a large number of very different applications and also in order 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. A large number of features expected from a good file format are missing in the BIE data stream:
Raw BIE data streams alone are consequently no suitable format for document archiving and exchange. A standard format for this purpose would typically combine a BIE representing the image data together 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 so that they can also contain JBIG compressed data.
On the other hand in database applications for instance, a BIE might
be directly stored in a variable length field. Auxiliary information
on which efficient search operations are required would then be stored
in other fields of the same record.
2 Compressing an image
2.1 Format of the source image
For processing by the library, the image has to be present in memory as separate bitmap planes. Each byte of a bitmap contains eight pixels, the most significant bit represents the leftmost of these pixels. 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 be handled directly by the Xlib library of the X Window System.
As JBIG can also handle images with several 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, i.e. 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, a small increase in coding efficiency can be reached.
A Gray code is also a binary representation of integer numbers, but has the property that the representations of i and (i+1) differ always 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 Gray code 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.
If instead of a Gray code, a normal binary weighted code is used for
encoding a pixel intensity in several bit planes, then it makes sense
to store the most significant bit in the first plane which is
transmitted first. This way, a decoder could increase the precision of
the displayed pixel intensities and the basic structure of the image
becomes already visible while data is still arriving.
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.
Although the library is written in C and not in C++, the interface follows the concepts of object oriented programming. 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 delivered
bytes. The pointer file is transparently delivered to
data_out as specified in jbg_enc_init(). Usually, data_out
will write the BIE portion to a file, send it to a
network connection or append it to some memory buffer.
file A pointer parameter which is transparently passed to
data_out() and allows data_out() to distinguish by which
compression task it has been called in multi-threaded
applications.
In the simplest case, the compression is then started by calling the function
void jbg_enc_out(struct jbg_enc_state *s);
which will deliver the complete BIE to data_out(). After this, a call to the destructor function
void jbg_enc_free(struct jbg_enc_state *s);
will release any memory allocated by the previous functions.
A minimal example application which sends the BIE of the above example bitmap to stdout looks like this:
/* A sample JBIG encoding application */
#include <stdio.h> #include "jbig.h"
void output_bie(unsigned char *start, size_t len, void *file)
{
fwrite(start, 1, len, (FILE *) file);
return;
}
int main()
{
unsigned char bitmap[15] = {
/* 23 x 5 pixels, "JBIG" */
0x7c, 0xe2, 0x38, 0x04, 0x92, 0x40, 0x04, 0xe2,
0x5c, 0x44, 0x92, 0x44, 0x38, 0xe2, 0x38
};
unsigned char *bitmaps[1] = { bitmap };
struct jbg_enc_state se;
jbg_enc_init(&se, 23, 5, 1, bitmaps,
output_bie, stdout); /* initialize encoder */
jbg_enc_out(&se); /* encode image */
jbg_enc_free(&se); /* release allocated resources */
return 0;
}
This software produces a 42 byte long BIE. (JBIG is not very good at
compressing extremely small images like in this example, because the
arithmetic encoder requires some startup data in order to generate
reasonable statistics which influence the compression process and
because there is some header overhead.)
2.3 More about compression
If jbg_enc_out() is called directly after jbg_enc_init(), the following default values are used for various compression parameters:
In order to change any of these default parameters, additional functions have to be called between jbg_enc_init() and jbg_enc_out().
In order to activate progressive encoding, it is possible to specify with
void jbg_enc_layers(struct jbg_enc_state *s, int d);
the number d of differential resolution layers which shall be encoded in addition to the lowest resolution layer 0. For example, if a 300 dpi document has to be stored and the lowest resolution layer shall have 75 dpi so that a screen previewer can directly decompress only the required resolution, then a call
jbg_enc_layers(&se, 2);
will cause three resolution layers with 75, 150 and 300 dots per inch.
If the application does not know what typical resolutions are used and simply wants to ensure that the lowest resolution layer will fit into a given maximal window size, then as an alternative, a call to
int jbg_enc_lrlmax(struct jbg_enc_state *s, unsigned long mwidth,
unsigned long mheight);
will cause the library to automatically determine the suitable number of resolutions so that the lowest resolution layer 0 will not be larger than mwidth x mheight pixels. E.g. if one wants to ensure that systems with a 640 x 480 pixel large screen can decode the required resolution directly, then call
jbg_enc_lrlmax(&se, 640, 480);
The return value is the number of differential layers selected.
After the number of resolution layers has been specified by calls to jbg_enc_layers() or jbg_enc_lrlmax(), by default all these layers will be written into the BIE. This can be changed with a call to
int jbg_enc_lrange(struct jbg_enc_state *s, int dl, int dh);
Parameter dl specifies the lowest resolution layer and dh the highest resolution layer that will appear in the BIE. If e.g. only layer 0 shall be written to the first BIE and layer 1 and 2 shall be written to a second one, then before writing the first BIE, one calls
jbg_enc_lrange(&se, 0, 0);
and before writing the second BIE with jbg_enc_out(), one calls
jbg_enc_lrange(&se, 1, 2);
If any of the parameters is negative, it will be ignored. The return value is the total number of differential layers which will represent the input image. This way, jbg_enc_lrange(&se, -1, -1) can be used to query the layer of the full image.
A number of other more exotic options of the JBIG algorithm can be modified by calling
void jbg_enc_options(struct jbg_enc_state *s, int order, int options,
long l0, int mx, int my);
before calling jbg_enc_out().
The order parameter can be a combination of the bits JBG_HITOLO, JBG_SEQ, JBG_ILEAVE and JBG_SMID and it determines in which order the SDEs are stored in the BIE. The bits have the following meaning:
JBG_HITOLO Usually, the lower resolution layers are stored before
the higher resolution layers, so that a decoder can
already start to display a low resolution version of
the full image once a prefix of the BIE has been
received. When this bit is set however, the BIE will
contain the higher layers before the lower layers. This
avoids additional buffer memory in the encoder and is
intended for applications where the encoder is connected
to a database which can easily reorder the SDEs before
sending them to a decoder. Warning: JBIG decoders are
not expected to support the HITOLO option (e.g. the
JBIG-KIT decoder does currently not) so you should
normally not use it.
JBG_SEQ Usually, at first all stripes of one resolution layer
are written to the BIE and then all stripes of the next
layer, and so on. When the SEQ bit is set however, then
all layers of the first stripe will be written,
followed by all layers of the second stripe, etc. This
option also should normally never be required and is
not supported by the current JBIG-KIT decoder.
JBG_SMID In case there exist several bit planes, then the order of
the stripes is determined by 3 loops over all stripes,
all planes and all layers. When SMID is set, the loop
over all stripes is the middle loop.
JBG_ILEAVE If this bit is set, then at first all layers of one
plane are written before the encoder starts with the next
plane.
The above description might be somewhat confusing, but the following table (see also Table 11 in ITU-T T.82) makes clear how the three bits JBG_SEQ, JBIG_ILEAVE and JBG_SMID influence the ordering of the loops over all stripes, planes and layers:
Loops:
JBG_SEQ JBG_ILEAVE JBG_SMID | Outer Middle Inner
------------------------------------+---------------------------
0 0 0 | p d s
0 1 0 | d p s
0 1 1 | d s p
1 0 0 | s p d
1 0 1 | p s d
1 1 0 | s d p
p: plane, s: stripe, d: layer
By default, the order combination JBG_ILEAVE | JBG_SMID is used.
The options value can contain the following bits, which activate some of the optional algorithms defined by JBIG:
JBG_LRLTWO Normally, in the lowest resolution layer, pixels
from three lines around the next pixel are used
in order to determine the context in which the next
pixel is encoded. Some people in the JBIG committee
seem to have argued that using only 2 lines will
make software implementations a little bit faster,
however others have argued that using only two lines
will decrease compression efficiency by around 5%.
As you might expect from a committee, now both
alternatives are allowed and if JBG_LRLTWO is set,
the slightly faster but 5% less well compressing two
line alternative is selected. God bless the committees.
Although probably nobody will ever need this option,
it has been implemented in JBIG-KIT and is off by
default.
JBG_TPDON This activates the "typical prediction" algorithm
for differential layers which avoids that large
areas of equal color have to be encoded at all.
This is on by default and there is no good reason to
switch it off except for debugging or preparing data
for cheap JBIG hardware which does not support this
option.
JBG_TPBON Like JBG_TPDON this activates the "typical prediction"
algorithm in the lowest resolution layer. Also activated
by default.
JBG_DPON This bit activates for the differential resolution
layers the "deterministic prediction" algorithm,
which avoids that higher resolution layer pixels are
encoded when their value can already be determined
with the knowledge of the neighbor pixels, the
corresponding lower resolution pixels and the
resolution reduction algorithm. This is also
activated by default and one only might perhaps want
to deactivate it if the default resolution reduction
algorithm is replaced by a new one.
JBG_DELAY_AT Use a slightly less efficient algorithm to determine
when an adaptive template change is necessary. With
this bit set, the encoder output is compatible to the
conformance test examples in cause 7.2 of ITU-T T.82.
Then all adaptive template changes are delayed until
the first line of the next stripe. This option is by
default deactivated and only required for passing a
special compatibility test suite.
In addition, parameter l0 in jbg_enc_options() allows to specify the number of lines per stripe in resolution layer 0. The parameters mx and my change the maximal offset allowed for the adaptive template pixel. The JBIG-KIT implementation allows currently a maximal mx value of 23 in the encoder and 32 in the decoder. Parameter my is at the moment ignored and always set to 0. As the standard requires of all decoder implementations only a maximum supported mx = 16 and my = 0, higher values should normally be avoided in order to guarantee interoperability. Default is mx = 8 and my = 0. If any of the parameters order, options, l0, mx or my is negative, then this value is ignored and the current value stays unmodified.
The resolution reduction and deterministic prediction tables can also
be replaced. However as these options are anyway only for experts,
please have a look at the source code of jbg_enc_out() and the struct
members dppriv and res_tab of struct jbg_enc_state for the details of
how to do this in case you really need it. The functions
jbg_int2dppriv and jbg_dppriv2int are provided in order to convert the
DPTABLE data from the format used in the standard into the more
efficient format used internally by JBIG-KIT.
3 Decompressing an image
Like with the compression functions, if you want to use the JBIG-KIT library, you have to put the line
#include "jbig.h"
into your source code and link your executable with libjbig.a.
The state of a JBIG decoder is stored completely in a struct and you will have to define a variable like
struct jbg_dec_state sd;
which is initialized by a call to
void jbg_dec_init(struct jbg_dec_state *s);
After this, you can directly start to pass data from the BIE to the decoder by calling the function
int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len,
size_t *cnt);
The pointer data points to the first byte of a data block with length len, which contains bytes from a BIE. It is not necessary to pass a whole BIE at once to jbg_dec_in(), it can arrive fragmented in any way by calling jbg_dec_in() several times. It is also possible to send several BIEs concatenated to jbg_dec_in(), however these then have to fit together. If you send several BIEs to the decoder, the lowest resolution layer in each following BIE has to be the highest resolution layer in the previous BIE plus one and the image sizes and number of planes also have to fit together, otherwise jbg_dec_in() will return the error JBG_ENOCONT after the header of the new BIE has been received completely.
If pointer cnt is not NULL, then the number of bytes actually read from the data block is stored there. In case the data block did not contain the end of the BIE, then the value JBG_EAGAIN will be returned and *cnt equals len.
Once the end of a BIE has been reached, the return value of jbg_dec_in() will be JBG_EOK. After this has happened, the functions and macros
long jbg_dec_getwidth(struct jbg_dec_state *s); long jbg_dec_getheight(struct jbg_dec_state *s); int jbg_dec_getplanes(struct jbg_dec_state *s); unsigned char *jbg_dec_getimage(struct jbg_dec_state *s, int plane); long jbg_dec_getsize(struct jbg_dec_state *s);
can be used to query the dimensions of the now completely decoded image and to get a pointer to all bitmap planes. The bitmaps are stored as described in section 2.1. The function jbg_dec_getsize() calculates the number of bytes which one bitmap requires.
Before calling jbg_dec_in() the first time, it is possible to specify with a call to
void jbg_dec_maxsize(struct jbg_dec_state *s, unsigned long xmax,
unsigned long ymax);
an abort criterion for progressively encoded images. For instance if an application will display a whole document on a screen which is 1024 x 768 pixels large, then this application should call
jbg_dec_maxsize(&sd, 1024, 768);
before the decoding process starts. If the image has been encoded in progressive mode (i.e. with several resolution layers), then the decoder will stop with a return value JBG_EOK_INTR after the largest resolution layer which is still smaller than 1024 x 768. However this is no guarantee that the image which can then be read out using jbg_dec_getimage(), etc. is really not larger than the specified maximal size. The application will have to check the size of the image, because the decoder does not automatically apply a resolution reduction if no suitable resolution layer is available in the BIE.
If jbg_dec_in() returned JBG_EOK_INTR or JBG_EOK, then it is possible to continue calling jbg_dec_in() with the remaining data in order to either decode the remaining resolution layers of the current BIE or in order to add another BIE with additional resolution layers. In both cases, after jbg_dec_in() returned JBG_EOK_INTR or JBG_EOK, *cnt is probably not equal to len and the remainder of the data block which has not yet been processed by the decoder has to be delivered to jbg_dec_in() again.
If any other return value than JBG_EOK, JBG_EOK_INTR or JBG_EAGAIN has been returned by jbg_dec_in(), then an error has occured and
void jbg_dec_free(struct jbg_dec_state *s);
should be called in order to release any allocated memory. The destructor jbg_dec_free() should of course also be called, once the decoded bitmap returned by jbg_dec_getimage() is no longer required and the memory can be released.
The function
const char *jbg_strerror(int errnum, int language);
returns a pointer to a short single line test message which explains the return value of jbg_dec_in(). This message can be used in order to provide the user a brief informative message about what when wrong while decompressing the JBIG image. The error messages are available in several languages and in several character sets. Currently supported are the following values for the language parameter:
JBG_EN English messages in ASCII JBG_DE_8859_1 German messages in ISO 8859-1 Latin 1 character set JBG_DE_UTF_8 German messages in ISO 10646/Unicode UTF-8 encoding
The current implementation of the JBIG-KIT decoder has the following limitations:
[end]