More sophisticated schemes based on assigning a (variable length) code for different runs that occur in the image. For example, we would assign a short code of 4 bits or less to runs that occur often, and longer codes up to 10 or 11 bits to the less common runs of pixel values. |
Named after David Huffman, who established in 1952 how to assign codes given the relative frequency of bytes in a file so that the total coded length was minimized. |
Huffman schemes require that a table that assigns runs to codes. Either a fixed table is used, or the table is constructed and stored along with the image. |
The CCITT Group 3 for bi-level images used a fixed Huffman scheme and is widely used for FAX transmission. Examples of Group 3 encodings: |
20 pixel black run: 0000 1101 000 |
100 pixel white run: 11011 001 0101 |
A pixel run can either have a code (called terminating) or be made up of one or more other codes for runs (called makeup). |