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.