01-30-2003, 02:07 AM
I always thought Huffman encoding was easy, I had to write a Huffman encoder in Java as a first year project, it gives really nice results for the right kinds of data as well. :-)
* digs out notes on JPEG format *
Yeah that is nasty, even so far as to have different compression formulas for PAL and NTSC JPEGs. Compression is done around two chrominance and one luminance values (because the eyes responds more to the former) and breaking the image into 8x8 blocks. The blocks are then passed through a Discrete Cosine Transformation (DCT) to create a set of 8x8 matrices. Quantization then removes the less important DCT values, each individual application must provide its own quantization tables for loss-compression tradeoff (these arent part of the JPEG standard). The differences of the {0, 0} values are then calculated, reducing most of them to small values.
The 64 elements are then linearized with a zig-zag and compressed using RLE (;-)), usually there are lots of zeros in the lower right corner of the matrix so this compresses quite well. Then the resulting data is Huffman encoded for easy transmition. JPEG gives about 20:1 compression ratio. Running the algorithm backwards will decompress it in about the same time taken to compress it.
JPEG is a bit tricky, but at least it isnt as bad as MPEG (which is the same only worse) or bzip which one of my tutors commented on "The author of bzip compression was clearly on heavy drugs at the time and I could show you how the compression algorithm works, but you honestly wouldnt believe me" ;-).
* digs out notes on JPEG format *
Yeah that is nasty, even so far as to have different compression formulas for PAL and NTSC JPEGs. Compression is done around two chrominance and one luminance values (because the eyes responds more to the former) and breaking the image into 8x8 blocks. The blocks are then passed through a Discrete Cosine Transformation (DCT) to create a set of 8x8 matrices. Quantization then removes the less important DCT values, each individual application must provide its own quantization tables for loss-compression tradeoff (these arent part of the JPEG standard). The differences of the {0, 0} values are then calculated, reducing most of them to small values.
The 64 elements are then linearized with a zig-zag and compressed using RLE (;-)), usually there are lots of zeros in the lower right corner of the matrix so this compresses quite well. Then the resulting data is Huffman encoded for easy transmition. JPEG gives about 20:1 compression ratio. Running the algorithm backwards will decompress it in about the same time taken to compress it.
JPEG is a bit tricky, but at least it isnt as bad as MPEG (which is the same only worse) or bzip which one of my tutors commented on "The author of bzip compression was clearly on heavy drugs at the time and I could show you how the compression algorithm works, but you honestly wouldnt believe me" ;-).
esus saves.... Passes to Moses, shoots, he scores!