How does JPEG actually work?
JPEG is an image encoding designed to compress photographs and
similar images effectively, often 5 to 15 times over a raw bitmap
format. It's a lossy format that exploits properties of human vision to
eliminate information that is difficult to distinguish. You see JPEGs
all the time, and if you've seen a JPEG compressed with a low quality
level, you have a good idea of the kinds of visual artifacts that
emerge when JPEG compression is pushed to its limits. But how does it
really work, and how does this cause JPEG artifacts?
The JPEG standard defines a number of different encoding options,
and there are a number of container file formats defined other than the
usual JFIF, but I'm going to discuss a single popular JPEG encoding
method used by many applications. This encoding combines three
different completely independent methods of image compression:
downsampling the chrominance channels, quantization of the discrete
cosine transformation, and entropy coding.
Method 1: Downsampling the chrominance channels
The most obvious way to make an image file smaller is to make the
image smaller - for example, a 100×100 bitmap is 1/4 the size of a
200×200 bitmap. You can expand the image back out to the original size
when viewing it by simply upsampling it. This isn't a great compression
method, since it causes clearly visible artifacts, usually blocky or
blurry effects, especially around detailed, sharp areas.
A different approach is instead of downsampling the entire image, to
only downscale certain channels of the image. For example, the eye's
red-green sensors are more numerous and sensitive than its blue-yellow
sensors, so if we shrink just the blue channel and later re-expand it,
the effect is much less noticable. But the RGB color space is not our
only choice - images can be encoded in many color systems, and for each
of these the channels we choose to downsample will have different
visual effects. This experiment
by Eric Setton of Stanford University demonstrates the effect on image
quality of downsampling various channels in various color systems.
The results are visually obvious: we are sensitive to red and green,
but even more sensitive to intensity or luminance, the relative
brightness of pixels compared to other nearby pixels. This is expressed
by the Y component of the YCbCr system and the V component of the HSV
system. Any downsampling of this information is visually disastrous. On
the other hand, downsampling the chrominance, expressed by the
Cb and Cr components of the YCbCr system, has almost no visual effect
(Cb and Cr stand for "chrominance blue" and "chrominance red" - see a sample image broken up into YCbCr channels in the middle of this page).
For this reason, typical JPEG files convert images to the YCbCr color
space, and then downsample both the Cb and Cr channels by a factor of 2
in both width and height. Further processing of the image proceeds on
each of the three channels independently.
This is the method in JPEG encoding largely responsible for the
artifact known as "color bleeding", where along sharp edges the color
on one side can "bleed" onto the other side. This is because the
chrominance channels, which express the color of pixels, have had each
block of 4 pixels averaged into a single color, and some of these
blocks cross the sharp edge.
Method 2: Quantization of the discrete cosine transformation
Normally, we view an image as simply a grid of pixels, and if we
alter a pixel or group of pixels dramatically, the effect will be
visually obvious. A different approach to storing images is to come up
with a set of "basis" images which can be added together in various
combinations to form the image we want. JPEG encodes each 8-by-8 square
of pixels using the following basis image set of 64 images:
We assign each of these images a relative weight determining how
much influence it has on the image. This weight can be positive or
negative (when negative, the basis image is subtracted). Taken
together, these 64 weights can describe any 8×8 image at all, and they
describe the image precisely. This example at Wikipedia
shows an 8×8 image, its original pixel array, and its new 8×8 array of
weights after being converted using the discrete cosine transform
(which I'll discuss later).
But what's the point of transforming 64 pixel values into 64
weights? For one thing, the resulting data may exhibit more structure,
and so be easier to compress. For example, with blocks from typical
photographs, the basis images in the upper left above have large
weights and the ones in the lower right have small weights.
But to store the weights, which are real numbers, we have to encode
them somehow. The simplest encoding is to just convert them to integers
between -k and k by scaling and rounding them. This works, but there's a tradeoff in our choice of k:
if it's too big, the encoded image will take too much space, but if
it's too small, the rounding might visibly distort the image, since
it's effectively altering the weights.
A more effective approach is to use a different k for each
basis image. This works well because the visual difference caused by
variations in the weights of different basis images is different. The
eye can detect small variations of the weights of the images in the
upper-left, but can overlook much larger variations in the weights of
the images in the lower-right, so we can get away with smaller k and larger rounding error for these weights.
In practice, rather than deal with expensive floating-point numbers,
we round the initial weights to integers and later divide them by fixed
factors called the quantization factors using integer division.
During decoding, we multiply them by these factors again. The
upper-left images have small quantization factors, so that little
information is lost in this process, while the lower-right images have
larger factors. This example shows a commonly used matrix of quantization
factors, one for each basis image, and the result of quantizing the
sample image using them. Observe how much simpler the matrix becomes -
it now contains a large number of entries that are small or zero,
making it much easier to compress. This example
shows how the weight values expand back out during decoding - notice
that although some of the weights are now different, the visual
difference is almost undetectable.
Quantization is the primary source of JPEG artifacts. Because the images in the lower-right
tend to have the largest quantization divisors, JPEG artifacts will
tend to resemble combinations of these images. The matrix of quantization factors can be directly controlled by
altering the JPEG's "quality level", which scales its values up or down.
Quantization compresses the image in two important ways: one, it
limits the effective range of the weights, decreasing the number of
bits required to represent them. Two, many of the weights become identical or zero,
improving compression in the third step, entropy coding.
But this discussion leaves one important question unanswered: how do
we take an arbitrary square of 8×8 pixels and decompose it into a
combination of the basis images? As it turns out, we specifically chose
the images above in a way to make this easy. These images are formed by
cosine waves of various frequencies in the x and y directions, and a
transformation called the discrete cosine transform from Fourier transformation theory allows us to rapidly decompose a signal into these parts in only O(n log n)
time. Because of the importance of JPEGs, over the years very fast and
clever specialised solutions for 8×8 blocks have been created in both
software and hardware. This is also the reason we use small,
constant-sized blocks instead of processing the image as a whole: the
cosine transform step doesn't need to scale up to large bitmaps, so the
transformation as a whole can run in linear (O(n)) time.
Method 3: Entropy coding
Unlike the other steps, entropy coding is lossless. If you've
studied the simple compression techniques used in ZIP files and BMP
files, the techniques of entropy coding should come as no surprise.
We start by turning our 8×8 grid of integers into a linear sequence
of integers. The obvious row-major and column-major orders are not
ideal here, since we expect there to be many zeros in the lower-right
area. Instead, we start with the top-left corner and zig-zag in a
diagonal pattern across the matrix, going back and forth until we reach
the lower-right corner.
Next, we apply the same run-length encoding algorithm used by GIF
files to condense sequences of identical integer values. In areas where
the values are small, we can expect many such runs, particularly runs
of zeros. We use a special code to say "all the remaining values are
zero", which comes in handy.
Finally, we apply Huffman compression to the remaining sequence,
which is a standard lossless compression technique that encodes
frequently used values using less bits than infrequently used values.
Conclusion
And that's it! For each YCbCr channel, for each 8×8 block, we
perform these transformations, and we store the results in a bitstream.
This data is wrapped up in a JFIF container giving metadata about the
image, and the file goes out ready for web browsers to view, completely
unaware of all the data that has been lost. Just don't go sending JPEGs
into space and expect aliens to see them the same way.
Finally, no discussion of the JPEG encoding would be complete
without noting that JPEG is based on research ideas that are now very
old and largely supplanted. The more modern JPEG 2000 encoding
based on wavelets can be pushed much farther before visible artifacts
appear, and includes a surprisingly efficient lossless mode. Of course,
all this improvement is rather moot until common applications actually
support it.
Comments
Anonymous
September 04, 2007
Many thanks for a very useful & wonderfully resourceful informationAnonymous
September 11, 2007
Hiiiii : Well ,thank you for these important inforamtions , really I woundered about the defferent extenstions .. I would like to be a photographer acually I'm , but I have no camera right now , or I can't pay a digital camera its so expansive and I like to begin with professional one after I get started with small and cheap ones , Many thanks , and I'll try to translate the topic , of course I'll tell about this original copy , to Arabic , thank you Mahmoud ( oceano )Anonymous
September 13, 2007
university of michigan dearborn libraryAnonymous
November 27, 2007
Very good article, but a couple of the links in the earlier paragraphs are broken. :( Thanks JasonAnonymous
July 14, 2008
PingBack from http://www.andrewkelsall.com/how-shocking-can-a-jpeg-be/Anonymous
June 07, 2009
PingBack from http://greenteafatburner.info/story.php?id=4043Anonymous
June 18, 2009
PingBack from http://thestoragebench.info/story.php?id=10755