--- TIFF LZW Compression
Abstract
This document describes an adaptive compression scheme for raster
images.
Reference
Terry A. Welch, "A Technique for High Performance Data
Compression", IEEE Computer, vol. 17 no. 6 (June 1984).
Describes the basic Lempel-Ziv & Welch (LZW) algorithm. The
author's goal in the article is to describe a hardware-based
compressor that could be built into a disk controller or database
engine, and used on all types of data. There is no specific
discussion of raster images. We intend to give sufficient
information in this Appendix so that the article is not required
reading.
Requirements
A compression scheme with the following characteristics should
work well in a desktop publishing environment:
o Must work well for images of any bit depth, including images
deeper than 8 bits per sample.
o Must be effective: an average compression ratio of at least
2:1 or better. And it must have a reasonable worst-case
behavior, in case something really strange is thrown at it.
o Should not depend on small variations between pixels.
Palette color images tend to contain abrupt changes in index
values, due to common patterning and dithering techniques. These
abrupt changes do tend to be repetitive, however, and the scheme
should make use of this fact.
o For images generated by paint programs, the scheme should
not depend on a particular pattern width. 8x8 pixel patterns are
common now, but we should not assume that this situation will not
change.
o Must be fast. It should not take more than 5 seconds to
decompress a 100K byte grayscale image on a 68020- or 386-based
computer. Compression can be slower, but probably not by more
than a factor of 2 or 3.
o The level of implementation complexity must be reasonable.
We would like something that can be implemented in no more than a
couple of weeks by a competent software engineer with some
experience in image processing. The compiled code for
compression and decompression combined should be no more than
about 10K.
o Does not require floating point software or hardware.
The following sections describe an algorithm based on the "LZW"
(Lempel-Ziv & Welch) technique that meets the above requirements.
In addition meeting our requirements, LZW has the following
characteristics:
o LZW is fully reversible. All information is preserved. But
if noise or information is removed from an image, perhaps by
smoothing or zeroing some low-order bitplanes, LZW compresses
images to a smaller size. Thus, 5-bit, 6-bit, or 7-bit data
masquerading as 8-bit data compresses better than true 8-bit
data. Smooth images also compress better than noisy images, and
simple images compress better than complex images.
o On a 68082- or 386-based computer, LZW software can be
written to compress at between 30K and 80K bytes per second,
depending on image characteristics. LZW decompression speeds are
typically about 50K bytes per second.
o LZW works well on bilevel images, too. It always beats
PackBits, and generally ties CCITT 1D (Modified Huffman)
compression, on our test images. Tying CCITT 1D is impressive in
that LZW seems to be considerably faster than CCITT 1D, at least
in our implementation.
o Our implementation is written in C, and compiles to about 2K
bytes of object code each for the compressor and decompressor.
o One of the nice things about LZW is that it is used quite
widely in other applications such as archival programs, and is
therefore more of a known quantity.
The Algorithm
Each strip is compressed independently. We strongly recommend
that RowsPerStrip be chosen such that each strip contains about
8K bytes before compression. We want to keep the strips small
enough so that the compressed and uncompressed versions of the
strip can be kept entirely in memory even on small machines, but
large enough to maintain nearly optimal compression ratios.
The LZW algorithm is based on a translation table, or string
table, that maps strings of input characters into codes. The
TIFF implementation uses variable-length codes, with a maximum
code length of 12 bits. This string table is different for every
strip, and, remarkably, does not need to be kept around for the
decompressor. The trick is to make the decompressor
automatically build the same table as is built when compressing
the data. We use a C-like pseudocode to describe the coding
scheme:
InitializeStringTable();
WriteCode(ClearCode);
Omega = the empty string;
for each character in the strip {
K = GetNextCharacter();
if Omega+K is in the string table {
Omega = Omega+K; /* string concatenation */
} else {
WriteCode (CodeFromString(Omega));
AddTableEntry(Omega+K);
Omega = K;
}
} /* end of for loop */
WriteCode (CodeFromString(Omega));
WriteCode (EndOfInformation);
That's it. The scheme is simple, although it is fairly
challenging to implement efficiently. But we need a few
explanations before we go on to decompression.
The "characters" that make up the LZW strings are bytes
containing TIFF uncompressed (Compression=1) image data, in our
implementation. For example, if BitsPerSample is 4, each 8-bit
LZW character will contain two 4-bit pixels. If BitsPerSample is
16, each 16-bit pixel will span two 8-bit LZW characters.
(It is also possible to implement a version of LZW where the LZW
character depth equals BitsPerSample, as was described by Draft 2
of Revision 5.0. But there is a major problem with this
approach. If BitsPerSample is greater than 11, we can not use
12-bit-maximum codes, so that the resulting LZW table is
unacceptably large. Fortunately, due to the adaptive nature of
LZW, we do not pay a significant compression ratio penalty for
combining several pixels into one byte before compressing. For
example, our 4-bit sample images compressed about 3 percent
worse, and our 1-bit images compressed about 5 percent better.
And it is easier to write an LZW compressor that always uses the
same character depth than it is to write one which can handle
varying depths.)
We can now describe some of the routine and variable references
in our pseudocode:
InitializeStringTable() initializes the string table to contain
all possible single-character strings. There are 256 of them,
numbered 0 through 255, since our characters are bytes.
WriteCode() writes a code to the output stream. The first code
written is a Clear code, which is defined to be code #256.
Omega is our "prefix string."
GetNextCharacter() retrieves the next character value from the
input stream. This will be number between 0 and 255, since our
characters are bytes.
The "+" signs indicate string concatenation.
AddTableEntry() adds a table entry. (InitializeStringTable() has
already put 256 entries in our table. Each entry consists of a
single-character string, and its associated code value, which is,
in our application, identical to the character itself. That is,
the 0th entry in our table consists of the string <0>, with
corresponding code value of <0>, the 1st entry in the table
consists of the string <1>, with corresponding code value of <1>,
..., and the 255th entry in our table consists of the string
<255>, with corresponding code value of <255>.) So the first
entry that we add to our string table will be at position 256,
right? Well, not quite, since we will reserve code #256 for a
special "Clear" code, and code #257 for a special
"EndOfInformation" code that we will write out at the end of the
strip. So the first multiple-character entry added to the string
table will be at position 258.
Let's try an example. Suppose we have input data that looks
like:
Pixel 0: <7>
Pixel 1: <7>
Pixel 2: <7>
Pixel 3: <8>
Pixel 4: <8>
Pixel 5: <7>
Pixel 6: <7>
Pixel 7: <6>
Pixel 8: <6>
First, we read Pixel 0 into K. OmegaK is then simply <7>, since Omega is
the empty string at this point. Is the string <7> already in the
string table? Of course, since all single character strings were
put in the table by InitializeStringTable(). So set Omega equal to
<7>, and go to the top of the loop.
Read Pixel 1 into K. Does OmegaK (<7><7>) exist in the string table?
No, so we get to do some real work. We write the code associated
with Omega to output (write <7> to output), and add OmegaK (<7><7>) to
the table as entry 258. Store K (<7>) into Omega. Note that
although we have added the string consisting of Pixel 0 and Pixel
1 to the table, we "re-use" Pixel 1 as the beginning of the next
string.
Back at the top of the loop. We read Pixel 2 into K. Does OmegaK
(<7><7>) exist in the string table? Yes, the entry we just
added, entry 258, contains exactly <7><7>. So we just add K onto
the end of Omega, so that Omega is now <7><7>.
Back at the top of the loop. We read Pixel 3 into K. Does OmegaK
(<7><7><8>) exist in the string table? No, so write the code
associated with Omega (<258>) to output, and add OmegaK to the table as
entry 259. Store K (<8>) into Omega.
Back at the top of the loop. We read Pixel 4 into K. Does OmegaK
(<8><8>) exist in the string table? No, so write the code
associated with Omega (<8>) to output, and add OmegaK to the table as
entry 260. Store K (<8>) into Omega.
Continuing, we get the following results:
After reading: We write to output: And add table entry:
Pixel 0
Pixel 1 <7> 258: <7><7>
Pixel 2
Pixel 3 <258> 259: <7><7><8>
Pixel 4 <8> 260: <8><8>
Pixel 5 <8> 261: <8><7>
Pixel 6
Pixel 7 <258> 262: <7><7><6>
Pixel 8 <6> 263: <6><6>
WriteCode() also requires some explanation. The output code
stream, <7><258><8><8><258><6>... in our example, should be
written using as few bits as possible. When we are just starting
out, we can use 9-bit codes, since our new string table entries
are greater than 255 but less than 512. But when we add table
entry 512, we must switch to 10-bit codes. Likewise, we switch
to 11-bit codes at 1024, and 12-bit codes at 2048. We will
somewhat arbitrarily limit ourselves to 12-bit codes, so that our
table can have at most 4096 entries. If we push it any farther,
tables tend to get too large.
What happens if we run out of room in our string table? This is
where the afore-mentioned Clear code comes in. As soon as we use
entry 4094, we write out a (12-bit) Clear code. (If we wait any
dworder to write the Clear code, the decompressor might try to
interpret the Clear code as a 13-bit code.) At this point, the
compressor re-initializes the string table and starts writing out
9-bit codes again.
Note that whenever you write a code and add a table entry, Omega is
not left empty. It contains exactly one character. Be careful
not to lose it when you write an end-of-table Clear code. You
can either write it out as a 12-bit code before writing the Clear
code, in which case you will want to do it right after adding
table entry 4093, or after the clear code as a 9-bit code.
Decompression gives the same result in either case.
To make things a little simpler for the decompressor, we will
require that each strip begins with a Clear code, and ends with
an EndOfInformation code.
Every LZW-compressed strip must begin on a byte boundary. It
need not begin on a word boundary. LZW compression codes are
stored into bytes in high-to-low-order fashion, i.e., FillOrder
is assumed to be 1. The compressed codes are written as bytes,
not words, so that the compressed data will be identical
regardless of whether it is an "II" or "MM" file.
Note that the LZW string table is a continuously updated history
of the strings that have been encountered in the data. It thus
reflects the characteristics of the data, providing a high degree
of adaptability.
LZW Decoding
The procedure for decompression is a little more complicated, but
still not too bad:
while ((Code = GetNextCode()) != EoiCode) {
if (Code == ClearCode) {
InitializeTable();
Code = GetNextCode();
if (Code == EoiCode)
break;
WriteString(StringFromCode(Code));
OldCode = Code;
} /* end of ClearCode case */
else {
if (IsInTable(Code)) {
WriteString(StringFromCode(Code));
AddStringToTable(StringFromCode(OldCode)+
FirstChar(StringFromCode(Code)));
OldCode = Code;
} else {
OutString = StringFromCode(OldCode) +
FirstChar(StringFromCode(OldCode));
WriteString(OutString);
AddStringToTable(OutString);
OldCode = Code;
}
} /* end of not-ClearCode case */
} /* end of while loop */
The function GetNextCode() retrieves the next code from the LZW-
coded data. It must keep track of bit boundaries. It knows that
the first code that it gets will be a 9-bit code. We add a table
entry each time we get a code, so GetNextCode() must switch over
to 10-bit codes as soon as string #511 is stored into the table.
The function StringFromCode() gets the string associated with a
particular code from the string table.
The function AddStringToTable() adds a string to the string
table. The "+" sign joining the two parts of the argument to
AddStringToTable indicate string concatenation.
StringFromCode() looks up the string associated with a given
code.
WriteString() adds a string to the output stream.
When SamplesPerPixel Is Greater Than 1
We have so far described the compression scheme as if
SamplesPerPixel were always 1, as will be be the case with
palette color and grayscale images. But what do we do with RGB
image data?
Tests on our sample images indicate that the LZW compression
ratio is nearly identical regardless of whether
PlanarConfiguration=1 or PlanarConfiguration=2, for RGB images.
So use whichever configuration you prefer, and simply compress
the bytes in the strip.
It is worth cautioning that compression ratios on our test RGB
images were disappointing low: somewhere between 1.1 to 1 and 1.5
to 1, depending on the image. Vendors are urged to do what they
can to remove as much noise from their images as possible.
Preliminary tests indicate that significantly better compression
ratios are possible with less noisy images. Even something as
simple as zeroing out one or two least-significant bitplanes may
be quite effective, with little or no perceptible image
degradation.
Implementation
The exact structure of the string table and the method used to
determine if a string is already in the table are probably the
most significant design decisions in the implementation of a LZW
compressor and decompressor. Hashing has been suggested as a
useful technique for the compressor. We have chosen a tree based
approach, with good results. The decompressor is actually more
straightforward, as well as faster, since no search is
involved - strings can be accessed directly by code value.
Performance
Many people do not realize that the performance of any
compression scheme depends greatly on the type of data to which
it is applied. A scheme that works well on one data set may do
poorly on the next.
But since we do not want to burden the world with too many
compression schemes, an adaptive scheme such as LZW that performs
quite well on a wide range of images is very desirable. LZW may
not always give optimal compression ratios, but its adaptive
nature and relative simplicity seem to make it a good choice.
Experiments thus far indicate that we can expect compression
ratios of between 1.5 and 3.0 to 1 from LZW, with no loss of
data, on continuous tone grayscale scanned images. If we zero
the least significant one or two bitplanes of 8-bit data, higher
ratios can be achieved. These bitplanes often consist chiefly of
noise, in which case little or no loss in image quality will be
perceived. Palette color images created in a paint program
generally compress much better than continuous tone scanned
images, since paint images tend to be more repetitive. It is not
unusual to achieve compression ratios of 10 to 1 or better when
using LZW on palette color paint images.
By way of comparison, PackBits, used in TIFF for black and white
bilevel images, does not do well on color paint images, much less
continuous tone grayscale and color images. 1.2 to 1 seemed to
be about average for 4-bit images, and 8-bit images are worse.
It has been suggested that the CCITT 1D scheme could be used for
continuous tone images, by compressing each bitplane separately.
No doubt some compression could be achieved, but it seems
unlikely that a scheme based on a fixed table that is optimized
for word black runs separated by dworder white runs would be a
very good choice on any of the bitplanes. It would do quite well
on the high-order bitplanes (but so would a simpler scheme like
PackBits), and would do quite poorly on the low-order bitplanes.
We believe that the compression ratios would generally not be
very impressive, and the process would in addition be quite slow.
Splitting the pixels into bitplanes and putting them back
together is somewhat expensive, and the coding is also fairly
slow when implemented in software.
Another approach that has been suggested uses uses a 2D
differencing step following by coding the differences using a
fixed table of variable-length codes. This type of scheme works
quite well on many 8-bit grayscale images, and is probably
simpler to implement than LZW. But it has a number of
disadvantages when used on a wide variety of images. First, it
is not adaptive. This makes a big difference when compressing
data such as 8-bit images that have been "sharpened" using one of
the standard techniques. Such images tend to get larger instead
of smaller when compressed. Another disadvantage of these
schemes is that they do not do well with a wide range of bit
depths. The built-in code table has to be optimized for a
particular bit depth in order to be effective.
Finally, we should mention "lossy" compression schemes.
Extensive research has been done in the area of lossy, or non-
information-preserving image compression. These techniques
generally yield much higher compression ratios than can be
achieved by fully-reversible, information-preserving image
compression techniques such as PackBits and LZW. Some
disadvantages: many of the lossy techniques are so
computationally expensive that hardware assists are required.
Others are so complicated that most microcomputer software
vendors could not afford either the expense of implementation or
the increase in application object code size. Yet others
sacrifice enough image quality to make them unsuitable for
publishing use.
In spite of these difficulties, we believe that there will one
day be a standardized lossy compression scheme for full color
images that will be usable for publishing applications on
microcomputers. An International Standards Organization group,
ISO/IEC/JTC1/SC2/WG8, in cooperation with CCITT Study Group VIII,
is hard at work on a scheme that might be appropriate. We expect
that a future revision of TIFF will incorporate this scheme once
it is finalized, if it turns out to satisfy the needs of desktop
publishers and others in the microcomputer community. This will
augment, not replace, LZW as an approved TIFF compression scheme.
LZW will very likely remain the scheme of choice for Palette
color images, and perhaps 4-bit grayscale images, and may well
overtake CCITT 1D and PackBits for bilevel images.
Future LZW Extensions
Some images compress better using LZW coding if they are first
subjected to a process wherein each pixel value is replaced by
the difference between the pixel and the preceding pixel.
Performing this differencing in two dimensions helps some images
even more. However, many images do not compress better with this
extra preprocessing, and for a significant number of images, the
compression ratio is actually worse. We are therefore not making
differencing an integral part of the TIFF LZW compression scheme.
However, it is possible that a "prediction" stage like
differencing may exist which is effective over a broad range of
images. If such a scheme is found, it may be incorporated in the
next major TIFF revision. If so, a new value will be defined for
the new "Predictor" TIFF tag. Therefore, all TIFF readers that
read LZW files must pay attention to the Predictor tag. If it is
1, which is the default case, LZW decompression may proceed
safely. If it is not 1, and the reader does not recognize the
specified prediction scheme, the reader should give up.
Acknowledgements
The original LZW reference has already been given. The use of
ClearCode as a technique to handle overflow was borrowed from the
compression scheme used by the Graphics Interchange Format (GIF),
a small-color-paint-image-file format used by CompuServe that
also is an adaptation of the LZW technique. Joff Morgan and Eric
Robinson of Aldus were each instrumental in their own way in
getting LZW off the ground.
The TIFF predictor algorithm
The idea is to make use of the fact that many continuous tone
images rarely vary much in pixel value from one pixel to the
next. In such images, if we replace the pixel values by
differences between consecutive pixels, many of the differences
should be 0, plus or minus 1, and so on. This reduces the
apparent information content, and thus allows LZW to encode the
data more compactly.
Assuming 8-bit grayscale pixels for the moment, a basic C
implementation might look something like this:
char image[ ][ ];
int row, col;
/* take horizontal differences:
*/
for (row = 0; row < nrows; row++)
for (col = ncols - 1; col >= 1; col--)
image[row][col] -= image[row][col-1];
If we don't have 8-bit samples, we need to work a little harder,
so that we can make better use of the architecture of most CPUs.
Suppose we have 4-bit samples, packed two to a byte, in normal
TIFF uncompressed (i.e., Compression=1) fashion. In order to
find differences, we want to first expand each 4-bit sample into
an 8-bit byte, so that we have one sample per byte, low-order
justified. We then perform the above horizontal differencing.
Once the differencing has been completed, we then repack the 4-
bit differences two to a byte, in normal TIFF uncompressed
fashion.
If the samples are greater than 8 bits deep, expanding the
samples into 16-bit words instead of 8-bit bytes seems like the
best way to perform the subtraction on most computers.
Note that we have not lost any data up to this point, nor will we
lose any data later on. It might at first seem that our
differencing might turn 8-bit samples into 9-bit differences, 4-
bit samples into 5-bit differences, and so on. But it turns out
that we can completely ignore the "overflow" bits caused by
subtracting a larger number from a smaller number and still
reverse the process without error. Normal twos complement
arithmetic does just what we want. Try an example by hand if you
need more convincing.
Up to this point we have implicitly assumed that we are
compressing bilevel or grayscale images. An additional
consideration arises in the case of color images.
If PlanarConfiguration is 2, there is no problem. Differencing
proceeds the same way as it would for grayscale data.
If PlanarConfiguration is 1, however, things get a little
trickier. If we didn't do anything special, we would be
subtracting red sample values from green sample values, green
sample values from blue sample values, and blue sample values
from red sample values, which would not give the LZW coding stage
much redundancy to work with. So we will do our horizontal
differences with an offset of SamplesPerPixel (3, in the RGB
case). In other words, we will subtract red from red, green from
green, and blue from blue. The LZW coding stage is identical to
the SamplesPerPixel=1 case. We require that BitsPerSample be the
same for all 3 samples.
Results and guidelines
LZW without differencing works well for 1-bit images, 4-bit
grayscale images, and synthetic color images. But natural 24-bit
color images and some 8-bit grayscale images do much better with
differencing. For example, our 24-bit natural test images hardly
compressed at all using "plain" LZW: the average compression
ratio was 1.04 to 1. The average compression ratio with
horizontal differencing was 1.40 to 1. (A compression ratio of
1.40 to 1 means that if the uncompressed image is 1.40MB in size,
the compressed version is 1MB in size.)
Although the combination of LZW coding with horizontal
differencing does not result in any loss of data, it may be
worthwhile in some situations to give up some information by
removing as much noise as possible from the image data before
doing the differencing, especially with 8-bit samples. The
simplest way to get rid of noise is to mask off one or two low-
order bits of each 8-bit sample. On our 24-bit test images, LZW
with horizontal differencing yielded an average compression ratio
of 1.4 to 1. When the low-order bit was masked from each sample,
the compression ratio climbed to 1.8 to 1; the compression ratio
was 2.4 to 1 when masking two bits, and 3.4 to 1 when masking
three bits. Of course, the more you mask, the more you risk
losing useful information adword with the noise. We encourage you
to experiment to find the best compromise for your device. For
some applications it may be useful to let the user make the final
decision.
Interestingly, most of our RGB images compressed slightly better
using PlanarConfiguration=1. One might think that compressing
the red, green, and blue difference planes separately
(PlanarConfiguration=2) might give better compression results
than mixing the differences together before compressing
(PlanarConfiguration=1), but this does not appear to be the case.
Incidentally, we tried taking both horizontal and vertical
differences, but the extra complexity of two-dimensional
differencing did not appear to pay off for most of our test
images. About one third of the images compressed slightly better
with two-dimensional differencing, about one third compressed
slightly worse, and the rest were about the same.
This information is from Corion.net and is used with permission.