Cơ sở dữ liệu hình ảnh - Chương 10 pptx

10. IMAGE COMPRESSION

10.1 Introduction

The storage requirement for uncompressed video is 23.6 Megabytes/second (512 pixels x

512 pixels x 3 bytes/pixel x 30 frames/second). With MPEG compression, full-motion

video can be compressed down to 187 kilobytes/second at a small sacrifice in quality.

Why should you care?

If your favorite movie is compressed with MPEG-1, the storage requirements are reduced

to 1.3 gigabytes. Using our high bandwidth link, the transfer time would be 7.48 seconds.

This is much better.

Clearly, image compression is needed. This is apparent by the large number of new

hardware and software products dedicated solely to compress images. It is easy to see why

CompuServe came up with the GIF file format to compress graphics files. As computer

graphics attain higher resolution and image processing applications require higher

intensity resolution (more bits per pixel), the need for image compression will increase.

Medical imagery is a prime example of images increasing in both spatial resolution and

intensity resolution. Although humans don't need more than 8 bits per pixel to view gray

scale images, computer vision can analyze data of much higher intensity resolutions.

Compression ratios are commonly present in discussions of data compression. A

compression ratio is simply the size of the original data divided by the size of the

compressed data. A technique that compresses a 1 megabyte image to 100 kilobytes has

achieved a compression ratio of 10.

compression ratio = original data/compressed data = 1 M bytes/ 100 k bytes = 10.0

For a given image, the greater the compression ratio, the smaller the final image will be.

There are two basic types of image compression: lossless compression and lossy

compression. A lossless scheme encodes and decodes the data perfectly, and the resulting

image matches the original image exactly. There is no degradation in the process-no data

is lost.

Lossy compression schemes allow redundant and nonessential information to be lost.

Typically with lossy schemes there is a tradeoff between compression and image quality.

You may be able to compress an image down to an incredibly small size but it looks so

poor that it isn't worth the trouble. Though not always the case, lossy compression

techniques are typically more complex and require more computations.

Lossy image compression schemes remove data from an image that the human eye

wouldn't notice. This works well for images that are meant to be viewed by humans. If the

image is to be analyzed by a machine, lossy compression schemes may not be appropriate.

Computers can easily detect the information loss that the human eye may not. The goal of

lossy compression is that the final decompressed image be visually lossless. Hopefully, the

information removed from the image goes unnoticed by the human eye.

Many people associate huge degradations with lossy image compression. What they don't

realize is that the most of the degradations are small if even noticeable. The entire imaging

operation is lossy, scanning or digitizing the image is a lossy process, and displaying an

image on a screen or printing the hardcopy is lossy. The goal is to keep the losses

indistinguishable.

Which compression technique to use depends on the image data. Some images, especially

those used for medical diagnosis, cannot afford to lose any data. A lossless compression

scheme will need to be used. Computer generated graphics with large areas of the same

color compress well with simple lossless schemes like run length encoding or LZW.

Continuous tone images with complex shapes and shading will require a lossy

compression technique to achieve a high compression ratio. Images with a high degree of

detail that can't be lost, such as detailed CAD drawings, cannot be compressed with lossy

algorithms.

When choosing a compression technique, you must look at more than the achievable

compression ratio. The compression ratio alone tells you nothing about the quality of the

resulting image. Other things to consider are the compression/decompression time,

algorithm complexity, cost and availability of computational resources, and how

standardized the technique is. If you use a compression method that achieves fantastic

compression ratios but you are the only one using it, you will be limited in your

applications. If your images need to be viewed by any hospital in the world, you better use

a standardized compression technique and file format.

If the compression/decompression will be limited to one system or set of systems you may

wish to develop your own algorithm. The algorithms presented in this chapter can be used

like recipes in a cookbook. Perhaps there are different aspects you wish to draw from

different algorithms and optimize them for your specific application (Figure 10. 1).

Figure 10.1 A typical data compression system.

Before presenting the compression algorithms, it is needed to define a few terms used in

the data compression world. A character is a fundamental data element in the input stream.

It may be a single letter of text or a pixel in an image file. Strings are sequences of

characters. The input stream is the source of the uncompressed data to be compressed. It

may be a data file or some communication medium. Codewords are the data elements used

to represent the input characters or character strings. Also the term encoding to mean

compressing is used. As expected, decoding and decompressing are the opposite terms.

In many of the following discussions, ASCII strings is used as data set. The data objects

used in compression could be text, binary data, or in our case, pixels. It is easy to follow a

text string through compression and decompression examples.

10.2 Run Length Encoding

Run length encoding is one of the simplest data compression techniques, taking advantage

of repetitive data. Some images have large areas of constant color. These repeating

characters are called runs. The encoding technique is a simple one. Runs are represented

with a count and the original data byte. For example, a source string of

AAAABBBBBCCCCCCCCDEEEE

could be represented with

4A5B8C1D4E

Four As are represented as 4A. Five Bs are represented as 513 and so forth. This example

represents 22 bytes of data with 10 bytes, achieving a compression ratio of:

22 bytes / 10 bytes = 2.2.

That works fine and dandy for my hand-picked string of ASCII characters. You will

probably never see that set of characters printed in that sequence outside of this book.

What if we pick an actual string of English like:

MyDogHasFleas

It would be encoded

1MlylDlolglHlalslFlllelals

Here we have represented 13 bytes with 26 bytes achieving a compression ratio of 0.5. We

have actually expanded our original data by a factor of two. We need a better method and

luckily, one exists. We can represent unique strings of data as the original strings and run

length encode only repetitive data. This is done with a special prefix character to flag runs.

Runs are then represented as the special character followed by the count followed by the

data. If we use a + as our special prefix character, we can encode the following string

ABCDDDDDDDDEEEEEEEEE

as

ABC+8D+9E

achieving a compression ratio of 2.11 (19 bytes/9 bytes). Since it takes three bytes to

encode a run of data, it makes sense to encode only runs of 3 or longer. Otherwise, you are

expanding your data. What happens when your special prefix character is found in the

source data? If this happens, you must encode your character as a run of length 1. Since

this will expand your data by a factor of 3, you will want to pick a character that occures

infrequently for your prefix character.

The MacPaint image file format uses run length encoding, combining the prefix character

with the count byte (Figure 10.2). It has two types of data strings with corresponding

prefix bytes. One encodes runs of repetitive data. The other encodes strings of unique data.

The two data strings look like those shown in Figure 10.2.

Figure 10.2 MacPaint encoding format

The most significant bit of the prefix byte determines if the string that follows is repeating

data or unique data. If the bit is set, that byte stores the count (in twos complement) of

how many times to repeat the next data byte. If the bit is not set, that byte plus one is the

number of how many of the following bytes are unique and can be copied verbatim to the

output. Only seven bits are used for the count. The width of an original MacPaint image is

576 pixels, so runs are therefore limited to 72 bytes.

The PCX file format run length encodes the separate planes of an image (Figure 10.3). It

sets the two most significant bits if there is a run. This leaves six bits, limiting the count to

63. Other image file formats that use run length encoding are RLE and GEM. The TIFF