Section 6.4 Huffman Codes
547
As a more specific application of Huffman codes, let’s look at JPEG, a
standardized image compression mechanism for photographic-quality images.
JPEG stands for Joint Photographic Experts Group, the name of the group that
developed this international standard. The need for improved image compression was largely fueled by the desire to transmit images over the Internet. There
are actually two versions of JPEG encoding, lossy and lossless, but the lossy
version is by far the more common. A lossy compression scheme means that
once the compressed data has been unencoded, it does not precisely match
the original—some information has been “lost.” In the case of lossy JPEG
compression, data loss comes from the preprocessing of the image before Huffman encoding is applied; the Huffman encoding/decoding faithfully restores
the data it starts with.
JPEG compression is intended for images to be viewed by humans, and it
takes advantage of the fact that the human eye is much more sensitive to gradients of light and dark than it is to small changes in color. The first step in the
JPEG process is therefore to take the color image information, which is usually
given as 24 bits per pixel, 8 bits for each of the red, green, and blue components,
and transform each pixel into components that capture the luminance (lightness/
darkness) with reduced information about the color components. Next, pixels
with similar color information are grouped together and an “average” color
value is used, while more accurate luminance data are maintained. The data
are then transformed into frequency data (that is, the data are represented as a
combination of cosine waves of varying frequencies), which in turn go through
a “quantization” process (basically rounding the results of a computation) to
end up in integer form. Higher-frequency variations, to which the human eye is
less sensitive, are lost in this process, but again the luminance data are treated
at a finer grain than the color data. Huffman encoding is applied to the result.
Areas of the image whose representations occur often will encode to smaller bit
strings.
A JPEG image file contains not only the compressed data but also the information needed to reverse the compression process (including the information to
reverse the Huffman encoding). The resulting image has lost the high-frequency
changes and color variations that were eliminated in the stages before the Huffman
coding was applied. Parameters in the JPEG encoding process allow tradeoffs to
be made between the amount of compression to be obtained and the faithfulness
of the restored image to the original. Because of the nature of the algorithms used,
JPEG encoding has little or no effect on black-and-white line drawings where
there are no data to throw away.
S e c t i o n 6 . 4
review
tecHniQue
• Find Huffman codes, given a set of characters and
their frequencies.
main iDea
• Given the frequency of characters in a collection of
data, a binary encoding scheme can be found that
minimizes the number of bits required to store the
data but still allows for easy decoding.
W
547
As a more specific application of Huffman codes, let’s look at JPEG, a
standardized image compression mechanism for photographic-quality images.
JPEG stands for Joint Photographic Experts Group, the name of the group that
developed this international standard. The need for improved image compression was largely fueled by the desire to transmit images over the Internet. There
are actually two versions of JPEG encoding, lossy and lossless, but the lossy
version is by far the more common. A lossy compression scheme means that
once the compressed data has been unencoded, it does not precisely match
the original—some information has been “lost.” In the case of lossy JPEG
compression, data loss comes from the preprocessing of the image before Huffman encoding is applied; the Huffman encoding/decoding faithfully restores
the data it starts with.
JPEG compression is intended for images to be viewed by humans, and it
takes advantage of the fact that the human eye is much more sensitive to gradients of light and dark than it is to small changes in color. The first step in the
JPEG process is therefore to take the color image information, which is usually
given as 24 bits per pixel, 8 bits for each of the red, green, and blue components,
and transform each pixel into components that capture the luminance (lightness/
darkness) with reduced information about the color components. Next, pixels
with similar color information are grouped together and an “average” color
value is used, while more accurate luminance data are maintained. The data
are then transformed into frequency data (that is, the data are represented as a
combination of cosine waves of varying frequencies), which in turn go through
a “quantization” process (basically rounding the results of a computation) to
end up in integer form. Higher-frequency variations, to which the human eye is
less sensitive, are lost in this process, but again the luminance data are treated
at a finer grain than the color data. Huffman encoding is applied to the result.
Areas of the image whose representations occur often will encode to smaller bit
strings.
A JPEG image file contains not only the compressed data but also the information needed to reverse the compression process (including the information to
reverse the Huffman encoding). The resulting image has lost the high-frequency
changes and color variations that were eliminated in the stages before the Huffman
coding was applied. Parameters in the JPEG encoding process allow tradeoffs to
be made between the amount of compression to be obtained and the faithfulness
of the restored image to the original. Because of the nature of the algorithms used,
JPEG encoding has little or no effect on black-and-white line drawings where
there are no data to throw away.
S e c t i o n 6 . 4
review
tecHniQue
• Find Huffman codes, given a set of characters and
their frequencies.
main iDea
• Given the frequency of characters in a collection of
data, a binary encoding scheme can be found that
minimizes the number of bits required to store the
data but still allows for easy decoding.
W