Introduction
In June 2000, I set out to write a JPEG encoder (I later implemented only two distinct components of an encoder - run-length encoding and Huffman coding). In case you don't know, JPEG is an algorithm (or rather, set of algorithms) for compressing image data. Virtually all photographic images on the web and used by digital cameras use the JPEG algorithm(s). The formal name for JPEG is both ISO/IEC 10918-1 and ITU-T T.81. JPEG stands for the "Joint Photographic Experts Group" of the ISO (see this FAQ page) and the IEC. JPEG compressed data, stored according to a particular file format (almost universally JFIF - JPEG File Interchange Format), is commonly referred to as a "JPEG" file, or simply as a "JPEG". The JPEG algorithm(s) is published in copious detail by both the ITU and the ISO/IEC (it can be purchased online from the ITU or ANSI).
So, how does it work?
WIthout going into unspeakable detail, the basic version of the JPEG algorithm (baseline sequential encoding) is composed of the following steps, more or less (for a grayscale image):- Read in image data and subdivide into 8x8 blocks of pixels.
- Transform each matrix using the Discrete Cosine Transform. This has the effect of representing the data as the composition of cosine functions of varying frequencies.
- Quantize the matrix using a predetermined quantization table. (In English: divide each element in the transformed matrix by the corresponding element in a predefined table and round to integer value).
- Differentially encode the first value of each block, run-length encode (see below) other values.
- Assemble blocks into a continuous stream.
- Huffman encode (see below) resulting values.
What is run-length encoding?
Run-length encoding, or RLE, is perhaps the most basic compression technique: it consists of finding repeating sequences of identical characters / values and replacing them with a more compact notation. For example, the string 'AAAABBBB' is composed of 8 bytes. You could easily create a code, beginning with a symbol that signal the beginning of a sequence, the value repeated, and the number of repetitions - e.g. !A4!B4, which occupies only six bytes. This is the essence of RLE and is exactly what the code I've written does. JPEG uses a form of RLE that is much more complicated but identical in principle. Steps #2 and #3 above, produce matrices which, when read in a particular order (zigzag ordering), contain long strings of 0's which can be compressed using RLE. For more information, see the Algorithm Archive.
What is Huffman coding?
Named after D.A. Huffman, who invented the algorithm in 1952, Huffman coding takes characters/values and assigns them codes of varying lengths, according to their frequencies: values which occur more frequently receive shorter codes and those that occur less frequently receive longer codes. The net result, since the most frequent values receive the shortest codes, which are often shorter than the size of the original values, is data compression. The algorithm will compress a typical text file by roughly 45%. Huffman coding uses a data structure called a Huffman tree, which is a special form of binary tree. Each character is assigned a weight according to its frequency. See the Algorithm Archive for more info.Source Code
Huffman Coding:
huff.c - Huffman encoder
dhuff.c - Huffman decoder
tree.h - Header file common to both files
tree.c - Functions common to both files
Run-length Coding
rle.c - RLE Encoder
drle.c - RLE Decoder
ProcessTree Network
TM
For-pay Internet distributed processing.