Huffman/CCITT Compression In TIFF
Posted: August 2005Introduction
I recently decided to re-write from scratch some TIFF decompression
I wrote a while ago.
I totally forgot how horrible of a file format TIFF is. Talk about
making things overly complicated. I mean it's a nice format in the
respect that the specification is fairly well organized and it supports
many different compression methods, including CCITT Group 3 and 4. The
problems are that, for example, it requires fseeking to read in the
IFD headers, it can do both big endian and little endian (I suppose
it makes it more flexible, but it makes programming and testing much
more difficult and much more prone to errors.. not worth it), the way
this file format
handles big endian is incredibly flawed in many ways.
I could go on and on about things I don't like about TIFF.
I mean, I can see why certain people use it, but still
personally I think
it's garbage. But that's just my opinion :). Anyway, currently this
code isn't very useful at all. Here are the features I plan to put in
eventually and what's done:
Related Projects @mikekohn.net
Explanation Of Compression In TIFF
I decided to some write documentation to help anyone else trying to implement their own TIFF decompression routines. Hopefully this helps someone :).
This page explains the concepts behind Group 3/4 compression
This page has the modified huffman tables:
In order to do either CCITT Group 3 or Group 4 compression/decompression
you must first implement Modified Huffman RLE. In TIFF terms this
is compression type 2. All three of these compressions are black and
Type 2 compression is basically RLE
(run length encoding) saved to disk with huffman codes that come from
a static huffman table. So if you had an image that looked like this:
This picture can be described by counting
the pixels from right to left: 3W, 1B, 2W,
3W, 1B, 2W, 3W, 1B, 2W, 2W, 2B, 2W, where W means whites and B
means blacks (of course). So now the question is, how are these
"run lengths" stored in a file. The run lengths are stored using
a static huffman table. A copy of the tables can be found
Note that the black and white huffman tables are different. The huffman
codes for this image would therefore look like this:
In the static Huffman table, you'll notice that there is a table called Terminating White Codes (and one for black codes) and another table called Make Up White Codes (and again another for black). Basically it works like this, if the code is a "make up code", your next color will be the same one your currently using, but if it's a termination code, the next color will be the opposite. So for example, if your next code is a white pixels code, and the huffman code is 11011, then you'd write out 64 pixels of white and the next code you read will be another white code. You do this until you read a white terminating code and then you know your next code is will be a black code.
Last thing to note, images always start with white codes. If a line on your image doesn't actually start with a white pixel, then you can use the huffman code of 00110101 which means 0 white pixels and switch to black.
CCITT Group 3 and 4 (Compression Types 3 and 4)
These are pretty much the same as standard modified Huffman described above, except that each line can be encoded as the difference between it and the line above. In Group 3 and 4, the following codes are used to describe the difference between the line currently being rendered and the line above:
The above picture encoded with Group 3 looks like this:
First thing noticable is the colors written above are the opposite of what you see in the picture (aka, where the picture is white, the codes above say to write black pixels). I have no idea why they chose to do that, but that is just GROSS. If I remember right (it's been a while) big-endian tiff's use the opposite colors of little-endian, but I can't remember and I haven't had a chance to do this big-endian yet. Anyway, The other thing you'll notice is every line begins with an EOL code. The EOL code is a 12 bit huffman code of 000000000001. This code is always aligned to the right on a byte boundary. Again, this is GROSS. After the EOL code is 1 bit that tells if this line is encoded with standard modified Huffman-RLE or if it uses the CCITT codes to describe the line. If the bit is 1, the line is encoded as it would be if it were using TIFF Compression Type 2 EXCEPT each line is not aligned at the end, it is only aligned on the byte boundary with the EOL code and where the huffman table would tell you to write white dots, you should write black (and where it says to write black dots, you write white). The lines who's k value is 0, you'll use the CCITT codes. You'll notice the white dots start at the same point on line 1 as they do on line 0, so the first CCITT code is a V(0) (no vertical change). Infact since all the pixels are the same from line 0 to line 1, there are simply 4 V(0) codes. On the very last line, you'll notice the Vl(1). On the last line of the image is the only change is the black pixel of the image starts 1 pixel earlier than on the line above, so the codes are V(0) (since there are still 0 white pixels) then Vl(1) (write out black pixels [which in the reversed color scheme are really white.. sorry if this is confusing.. blame whoever came up with that stupid idea of reversing colors] but stop writing black pixels 1 earlier than the line above), then V(0) again which says to write white pixels to the same point as they were written on the line above, and finally V(0) saying to write out black pixels the to the same point as the line above it. Confusing? :(
The above picture encoded with Group 4 looks like this:
The binary codes to create this image:
Downloadtiff-2005-08-06.tar.gz (Source Code)
Copyright 1997-2019 - Michael Kohn