Difference between revisions of "Lossy versus Lossless Images" - Rhea

Latest revision as of 12:07, 22 October 2009

Lossy versus Lossless Images: What is the difference?

Background Information

As "analog" 35 mm cameras (and the film used for it!) become more and more obsolete, digital cameras and the storage and transmission of digital images are rapidly becoming the de facto standard for today's photography needs.

The resolution of a camera - e.g. 6 MP (Megapixel) or 10 MP - determines the number of pixels the camera uses to represent the "continuous" signal (e.g. a mountain, or your smiling significant other) that your digital camera is sampling.

Thus the digital camera samples the continuous signal, with a period $ T $ (shutter speed) and "on" for length $ tau $ (related to aperture -- how much light is absorbed):

   $ X_s(t) = s_{tau}(t)x(t) $
   (Note: image is two-dimensional signal)

A digital camera also quantizes the sampled values, because an infinite amount of storage space (i.e. bits) is not available to represent every pixel's hue. A typical digital camera will allocate 24 bits per pixel at the highest quality setting, thus allowing $ 2^{24} = 16,777,216 $ possible color representations. This is sometimes referred to as a 16-million color palette.

Image Formats: Lossless Compression

We all have heard of the various image formats used - for example, JPEG, GIF, TIFF, RAW, PNG, BMP. Of these, TIFF (usually), RAW, PNG, and BMP are referred to as lossless. This means that with the aforementioned compression algorithms, the original signal can be faithfully reconstructed exactly, bit-by-bit. Lossless image compression would be important for such applications such as medical imaging, where it is important that the resolution of the original image is maintained upon compression and decompression. As an example, a lossless compression is important to maintain high contrast and finer details in an MRI scan of brain tissue, so that an accurate diagnosis can be made!

The size of a raw uncompressed digital image that is 10 MP in resolution and allocated 24 bits per pixel will be: $ 10^6 pixels * 24 bits/pixel * 1 MB / 8*10^6 bits = 30 MB $. Typical lossless compression algorithms are able to achieve compression ratios of only about 2:1 (see [1]). (This would reduce the 30 MB file down to about 15 MB.) These algorithms seek to reduce redundancies in the data by representing repeated data with less data (yet the representation is exact and no round-off is done). As an example, suppose a row of a black-and-white image is as follows, where W represents a white pixel and B represents a black pixel:

   BBBBWWBBBBBWBBBWWWWWWWWW

A run-length encoding scheme (see [2]) might represent this as:

   4B2W5B1W3B9W

This encoded representation would be interpreted as "4 B's, 2 W's, 5 B's, 1 W, 3 B's and 9 W's" -- this represents the original signal exactly (i.e. it is lossless) and in 12 characters instead of the original 24 (it should be noted that this will likely be implemented in binary, but the concept does not change).

Lossy Compression Algorithms

Lossy compression algorithms, like JPEG, are used when a reduction in image quality is acceptable or can be tolerated. However, the benefits of this are (typically) reduced file storage (e.g. more pictures to be stored on a digital camera's memory card) and quicker data transmission (e.g. quicker web page loading). Lossy compression algorithms can achieve compression ratios of 10:1 (creating a 3 MB JPEG) with little perceptible difference in quality and up to 50:1 (creating a 0.6 MB JPEG) with noticeable degradation in picture quality (see [3]). These algorithms typically "exploit" the limitations of the human visual system and its inability to pick up minor changes in hue (we are more sensitive to changes in brightness than hue - see [4]). Thus the spectrum of colors can be reduced.

JPEGs are notoriously bad at compressing image files that have large sections of one color surrounded by another color - e.g. black and white text, cartoons, solid squares, etc. This is because JPEG removes the high frequency components that are present in the sharp discontinuities in color (e.g. from black to white) and instead interpolate the rapid change with a more gradual one. In other words, in JPEGs, sharp discontinuities in color are made more gradual, insomuch that the outline of a solid black square outlaid on a white background will now look blurry with "gray" pixels at the periphery of the square. This type of compression artifact can be seen here: [5], in both the text and picture.

An Illustration of the Differences in Lossy versus Lossless Compression

Suppose we have the value 28.5777777

The representation of this "raw" value requires 11 characters, if you include the decimal point.

A lossless algorithm might represent this number as 28.5[6]7, where the [6] represents six 7's in a row. This representation requires 6 characters (8 if you include the brackets).

On the otherhand, a lossy algorithm might represent this value as 28.6, requiring only 4 characters. However, this new representation is no longer equal to the original signal! Round-off has occurred and thus this compression has incurred a loss. An even lossier algorithm (yet with better compression) would represent this value as 29 - requiring only two characters!

Consequently, in digital media, there is always a trade-off in compression (i.e. file size) and accuracy in representing the original data (e.g. level of audio fidelity, video quality).

- Ryan Scheidt