An in-depth look at how fax images are constructed and an efficient way to decode and display them. Several articles have already appeared describing how electronic facsimile works; what I plan to do in this article is go into detail about working with fax image data and provide an efficient way of decoding those images. With the low cost of fax modems in the past couple of years, a great many of today's faxed documents never touch actual paper; they are sent and received purely as electronic images between two computers. Recent advances in software have brought an unprecedented level of convenience to composing and sending these images, but it's the receiving end that this article is going to focus on. For programmers who want to write their own fax software, or those who want to write their own post-processing code, I will explain the whys and hows of fax data encoding as well as efficient code to decompress them. A little background is necessary to understand how the fax standard came about. Before the days of the digital fax, there was the analog fax; used mostly for transmitting weather pictures, the original fax was typically sent over radio waves and used audio modulation to encode intensity levels. Being an analog signal, the resulting images had various levels of gray and were quite pleasing to the eye. The problems with these images were the long transmission time and fidelity of the signal they required. In the early 1970's various digital imaging methods were being experimented with, but the cost of the equipment was too expensive to be practical. In the late 1970's, when microprocessors, memory and modems were beginning to be reasonably priced, the digital fax was practical to implement. The CCITT (International Telegraph and Telephone Consultative Committee) met and ratified the Group 3 fax transmission standard. This standard specifies a method of transmitting black and white image data, in a compressed form, over standard telephone lines. The specification outlined how the image data is created, and the audio signal protocol between the sender and receiver. Data compression was a concern for faxes from the beginning because scanned image data tends to be rather large. Consider that a 200x200 dpi 8.5x11" page (1728x2200 pixels) scanned as 1 bit per pixel consumes 475200 bytes. To transmit this much data at 9600 baud would take almost seven minutes. Considerable cost savings can be had by reducing the amount of data to transmit. After analyzing many typical printed pages, a scheme was invented to handle both compressing the data and recovering from transmission errors. The 'fax' way of looking at a printed page is to see a series of horizontal 'runs' on each line, alternating between black and white. Each line is encoded independently and a sync pattern is added to the end. This scheme allows each line to be decoded independently so, in case of an error in transmission, only the erroneous lines will be wrong and the rest of the document can continue without problems by resynching on the next valid line. By encoding the images as run-length data, this allowed for error recovery, but did not do a great job of compressing the data. Statistical evidence showed that the typical page was composed of many small black runs and fewer long white runs. By using a modified Huffman encoding scheme, the statistical probability of these run lengths could be used to achieved a reasonable compression ratio: frequently occurring run lengths where assigned the shortest codes and infrequently occurring run lengths were assigned the longest codes. The statistical information used for encoding fax images is a fixed table so that it does not have be transmitted with each page, but being fixed information it will not always be optimal for all images. The CCITT later improved on the original one-dimensional encoding scheme by adding a two-dimensional option; this option allows better compression ratios by encoding each line as the changes from the previous line. To allow for resynchronization after errors, small groups of lines are encoded this way so that an error will not corrupt the whole page. These two schemes were given the name G3 encoding which stands for the third group meeting of the CCITT. A short while later, another scheme named G4 was created for use on error-free channels. G4 is basically the same the the G3 2-dimensional scheme except that it codes the entire document two-dimensionally with no resynchronization breaks; since each line is dependent on the one above it, a single error will propagate all the way down the page. G4 was originally meant to be used over ISDN, but has gotten widespread use as a compact image archiving format for storage of bilevel images. Because of the complexity of the two-dimensional image encoding scheme, I will cover the one-dimensional scheme in this article and leave describing the two-dimensional method for the future. Specifics of fax data encoding Fill bits are used to ensure that the receiving equipment has enough time to print each line. At the start of a fax transmission session, the receiver tells the transmitter how fast it can print each line; with this information and the data transmission rate, the transmitter must ensure that each line contains enough bits to give the receiver time enough to print it. Any lines that are too short at padded with zeros placed in front of the EOL code. The following example encoded line demonstrates all of these concepts at once. The line is the first line of the image and is five black pixels followed by 1723 white pixels. The receiver has indicated that it needs 10ms to print a line and the transmission is taking place at 4800 baud. Therefore, each line must be a minimum of 48 bits in length to give the receiver time to print it. EOL W0 B5 FILL EOL The encoding of the runs of pixels as Huffman (minimum redundancy) codes presents a problem for writing an efficient decoder since the codes do not fall neatly on byte boundaries. The creation of a Huffman code table is based on the probabilities of each code and assigns the shortest code to the most probable symbol and the longest code to the least probable. The codes are also designed to not need separators; each code is uniquely decodable. The codes can be decoded by picking up one bit at a time and traversing the Huffman 'tree'; branching left for a zero and right for a one. This solution is the most obvious one from the creation of the codes, but is definitely not the most efficient. The nature of Huffman codes allows a more elegant solution to this problem. Since the codes are designed to be unique sequences of bits when decoded from start to finish, we can use this fact to construct a table for decoding each code in one iteration instead of one iteration per bit. By using the code as an address to index into our table, we can decode the bit sequence in one step. Suppose we look at the white terminating codes from table-1 and design a decoder table for them. These codes are from four to eight bits in length. If we were to left justify the code (place the first bit of the code in the MSB of a word) and use it as an address to index our lookup table, we would see that for codes shorter than eight bits, there would need to be repeated entries in our table for all possible bit patterns. For example, if the code we are decoding is for a white run length of four, the bit sequence would be 1011XXXX where the last four bits are actually the beginning of the next code word. Therefore, our table would have to have sixteen identical entries all with a code value of four and a length of four bits. This would lead one to believe that a table of this type representing all of the fax codes would require a great deal of space because of all the repeated entries, but the way I devised the decode tables they require a total of only 4352 bytes. The heart of efficient decoding of the variable length
fax codes is looking at the code table the 'right' way. According
to one of the IBM researchers (who shall remain nameless) who helped
invent the fax standard, the fax Huffman codes were designed to
fit within 8 bits and have a variable number of leading zeros. If
you look at table-1 you will see that this is true, but decoding
them based on this fact would lead to an inefficient decoder. If
the codes are looked at as having 2 to 13 bits in length, a table
to describe them all would require 2^13 or 8192 pairs of entries.
I have studied these tables for quite some time and what I came
up with is a non-obvious grouping of the codes which leads to three
distinct, small tables and a much more efficient decoder (see table
1). The three groups the codes fall into are: Files and Bit-Order The Huffman Decoder The while() loop collects makeup codes (lengths > 63) until a terminating code (lengths < 64) is reached. To decode a run-length, 16-bits are read from the input data and shifted so that the first bit of the code is positioned at the MSB of the short variable. 16 is a very convenient word size because each of the codes can be up to 9 bits in length and up to 7 bits offset into a byte. After the codeword is read, the upper 4 bits are tested to see if they are zeroes; this step determines which lookup table will be used. If the first 4 bits are zeroes, the current pointer is shifted forward by 4 bits, and another 16 bits are read. The actual bit length of the code is then referenced from the lookup table, as well as the graphic run length. This process repeats, with the run lengths summed together, until a terminating code is encountered. The main fax decode routine scans each line in this manner until the RTC (six EOLs) is encountered. Each line alternates between white and black until an EOL or 1728 pixels are decoded. The Viewer Going Further 1) Scale the drawing of the image before using GDI
functions; for Win32, use the CreateDIBSection() API to return a
pointer to the bitmaps memory to eliminate the need to use SetBitmapBits(). The Sky is the Limit
iBit = *bitnum; /*
Faster to use a direct vars */ iLen = 64; /* force first pass through loop */ while (iLen > 63) /*
Until a terminating code is found */ Table 1 Make-up Codes Extended Make-up codes (white + black)
Webdesign by Deep Magic Studios - HanaHo Games, Inc. Copyright © 2002 |