Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!aplcen!samsung!umich!umeecs!zip!spencer From: spencer@eecs.umich.edu (Spencer W. Thomas) Newsgroups: comp.graphics Subject: Re: Compression of multi-bit images Message-ID: Date: 4 Jun 90 21:08:21 GMT References: <8099@b11.ingr.com> Sender: news@zip.eecs.umich.edu Organization: University of Michigan EECS Dept Lines: 53 In-reply-to: dan@b11.ingr.com's message of 3 Jun 90 02:51:19 GMT Lossless methods: A popular method is LZW (Lempel-Ziv-Welch) as found in the Unix 'compress' program. This doesn't work worth a hoot on scanned images, as they have too much noise, and LZW relies on patterns. For 24-bit data, you need a code size of at least 16 bits. It probably helps to store your data RRRR... GGGG... BBBB... instead of RGBRGB (at least, this seems to be true for scanned images, the opposite may be true for computer-generated images). Simple Huffman (adaptive or otherwise (the Unix 'pack' program) may do well if the pixel intensity (consider R,G,B values separately) histogram is not flat, even on scanned images. Arithmetic coding will do better, but is harder to do. Typical computer generated images (with no texture mapping, anyway) compress reasonably well with run-length encoding. Lossy methods: The method currently getting all the noise is DCT (discrete cosine transform) encoding. The idea is to take a "Fourier transform" (discrete cosine transform, actually, since the values are all real) of little (typically 8x8, I think) blocks of the image. Only the first few coefficients for each block are saved. (If only the first coefficient was saved, you would get back an image with little (8x8) blocks, each a constant color.) Potentially more efficient, but definitely more expensive and complicated, is vector quantization (I suppose DCT is an instance of this, really). In this method, you pick a set of representative "cells" (little blocks of pixels), and then, for each block in the input image, you find the cell in the set that "most closely" matches the input cell. You then output a code representing the representative cell. Depending on the size of your "code book", very large compression ratios can be achieved. (For example, if you had an 8-bit imput image and 2 4x4 cells, one all black and one all white, in the code book, then your compression ratio would be 512:1, because 512 (4x4x8) bits in the input give you one bit in the output (either black or white). Of course, the reconstructed image would look like s**t.) (Digression: under quite reasonable assumptions, you can "prove" that 200 bits are sufficient to encode all images. Maybe I'll give the details in another message sometime.) The real trick in VQ is picking the code book, of course. I have seen 100:1 compression on scanned images that ended up looking about as good (or bad, depending on your point of view) as a VHS tape recorded on the slow speed. Do I have code for these? Nope, except run-length encoding. If you're on Unix, try using 'compress' on your images. =Spencer (spencer@eecs.umich.edu) -- =Spencer (spencer@eecs.umich.edu)