A Lossless 2-D Image Compression Technique for Synthetic Discrete-Tone Images

Jeffrey M. Gilbert and Robert W. Brodersen

A new image compression technique, Flexible Automatic Block Decomposition (FABD), losslessly compresses typical discrete-tone pseudo-color images 1.5 to 5.5 times more compactly than GIF, and up to twice as compactly as JBIG. The algorithm is designed to exploit the two-dimensional redundancy in an image by expressing the image in terms of itself. Several optimizations allow the algorithm to complete in a matter of seconds on a 100 MIPS processor. Decompression is fast and simple, as is required in a web browsing environment. Entropy coding techniques result in a coding rate of typically 0.03 bpp - 0.20 bpp.