Posted: August 2005

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:

• Read all IFD tags and output info: Done
• Uncompressed images: mostly done (colors are wrong)
• Packed images: mostly done (colors are wrong)
• Modified Huffman decompression: mostly done (no big endian)
• CCITT Group3 2D decompression: mostly done (no big endian/not heavily tested)
• CCITT Group4 2D decompression: mostly done (no big endian/not heavily tested/found problems already)
• LZW: started

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 :).

http://www.adventimaging.com/support/ccitt.htm - This page explains the concepts behind Group 3/4 compression
http://einstein.informatik.uni-oldenburg.de/rechnernetze/ccitt_t4.htm - Another useful page explaining the concept behind Group 3/4 compression
http://web.archive.org/web/20020628195336/http://www.netnam.vn/unescocourse/computervision/104.htm - 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 white only. 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 here: http://www.faqs.org/rfcs/rfc804.html. Note that the black and white huffman tables are different. The huffman codes for this image would therefore look like this:
1000 010 0111 (00000) <--- binary digits
1000 010 0111 (00000)
1000 010 0111 (00000)
0111 11 0111 (000000)
So on the first line you'll see the huffman code 1000 which stands for 3 whites, then 010 which stands for 1 black, and 0111 which stands for 2 whites. In this version of Huffman RLE all image lines need to be padded to a byte boundary, so to do that we add 00000 to the end of it. If you made the image above into a real TIFF and wrote it to disk and opened it up with a hex editor, you will find it written like so:
10000100 11100000 0x84 0xe0
10000100 11100000 0x84 0xe0
10000100 11100000 0x84 0xe0
01111101 11000000 0x7d 0xc0

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.

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:
EOL code, k=1, 0 whites, 3 black, 1 white, 2 black
EOL code, k=0, V(0), V(0), V(0), V(0)
EOL code, k=1, 0 whites, 3 black, 1 white, 2 black
EOL code, k=0, V(0), Vl(1), V(0), V(0)
First thing you will notice 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:
CCITT Horiz (001) 0 white, 3 black, Vl(2), V(0)
V(0), V(0), V(0), V(0)
V(0), V(0), V(0), V(0)
V(0), Vl(1), V(0), V(0)

The binary codes to create this image:
001 00110101 10 000010 1 1 1 1 1 1 1 1 1 1 010 11 (000000 padding)
Hex values saved to disk: 26 b0 5f fa c0
The file format for Group 4 is the same as Group 3, except there is no K value and no EOL that has to be read out of the file.

Download

Copyright 1997-2018 - Michael Kohn