Lecture Digital image processing: Image compression

Nguyễn Công Phương

DIGITAL IMAGE PROCESSING

Image Compression

Introduction to Image Processing & Matlab Image Acquisition, Types, & File I/O Image Arithmetic

Image Transform Spatial & Frequency Domain Filter Design Image Restoration & Blind Deconvolution

Binary Image Processing Image Encryption & Watermarking Image Classification & Segmentation

I. II. III. IV. Affine & Logical Operations, Distortions, & Noise in Images V. VI. VII. VIII. Image Compression IX. Edge Detection X. XI. XII. XIII. Image – Based Object Tracking XIV. Face Recognition XV. Soft Computing in Image Processing

sites.google.com/site/ncpdhbkhn 2

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 3

Introduction

• Image compression: algorithmic techniques that can reduce the storage requirements of the image and, at the same time, retain the image information content.

• Aspects of image properties that can be used for

compression: – The interpixel information variation is only significant

at edges of any type, whereas most of the image information content remains a slowly changing variable.

– Our eyes are less sensitive to color changes and are

much more sensitive to intensity.

sites.google.com/site/ncpdhbkhn 4

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 5

Image Compression Steps

1. Specification: This implies specifying the rate (bits

available) and distortion (tolerable error) parameters for the target image.

2. Classification: This implies dividing the image data into various classes, based on their importance. Usually, some type of compression transform is utilized in this step to associate the important features with the most important class of information to be kept in the process of compression.

3. Bit allocation: This implies dividing the available bit

budget among these classes such that the distortion is a minimum.

4. Quantization: This refers to quantizing each class

separately using the bit allocation information derived in step 3.

5. Encoding: This corresponds to encoding each class

separately using an entropy coder and write to the file.

sites.google.com/site/ncpdhbkhn 6

Image Decompression Steps

1. Decoding: Read in the quantized data from the

file, using an entropy decoder (reverse of step 5).

2. Dequantizing: This refers to normalizing the

quantized values (reverse of steps 4 and 3). This also includes any padding or addition of missing values due to the quantization process.

3. Rebuilding: This involves the inverse transform or inverse classification of the normalized data into image pixels, essentially rebuilding the image (reverse of step 2).

sites.google.com/site/ncpdhbkhn 7

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 8

Error Metrics

M N

[

(

2 , )]

(

MSE

, ) f m n

g m n





1   M N  1 m n

1 

PSNR

20log



255 MSE

  

  

• MSE (mean square error): a lower value for

MSE means less error.

• PSNR (peak signal-to-noise ratio): a higher

value of PSNR is good.

sites.google.com/site/ncpdhbkhn 9

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 10

Classifying Image Data

•

In this step, usually the image is represented as a two-dimensional array of coefficients, where each coefficient represents the brightness level at that point.

• From a high-level perspective, one cannot differentiate between

coefficients as more important ones and lesser important ones, but … • Most natural images have smooth color variations, with the fine details

being represented as sharp edges between the smooth variations.

• Technically, the smooth variations in color can be termed low-frequency

variations and the sharp variations, high-frequency variations.

• The low-frequency components (smooth variations) constitute the base of an image, and the high-frequency components (the edges that give the detail) add upon them to refine the image, thereby giving a detailed image.

• Hence, the smooth variations require more importance than the details. • Separating the smooth variations and details of the image can be done in many ways. Two well-known image transforms used for this purpose are the discrete cosine transform (DCT) and the discrete wavelet transform (DWT).

sites.google.com/site/ncpdhbkhn 11

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 12

Bit Allocation

• Bit allocation: the first step in compressing an image is to segregate the image data into different classes. Depending on the importance of the data it contains, each class is allocated a portion of the total bit budget such that the compressed image has the minimum possible distortion.

• Steps: 1.

4. 5.

Initially, all classes are allocated a predefined maximum number of bits. For each class, one bit is reduced from its quota of allocated bits, and the distortion due to the reduction of that one bit is calculated. 3. Of all the classes, the class with minimum distortion for a reduction of one bit is noted, and one bit is reduced from its quota of bits. The total distortion for all classes D is calculated. The total rate for all the classes is calculated as R = P(i)×B(i), where P is the probability and B is the bit allocation for each class.

6. Compare the target rate and distortion specifications with the values

obtained in steps 4 and 5. If not optimal, go to step 2.

sites.google.com/site/ncpdhbkhn 13

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 14

Quantization

• Quantization: the process of approximating the continuous set of

values in the image data with a finite (preferably a much smaller) set of values.

• The input to a quantizer is the original data, and the output is always

one among a finite number of levels.

• The quantizer is a function whose output values are discrete, and

usually finite. Obviously, this is a process of approximation, and a good quantizer is one that represents the original signal with minimum loss or distortion.

• There are two types of quantization: scalar quantization and vector

quantization. – In scalar quantization, each input symbol is treated separately in

producing the output.

– In vector quantization, the input symbols are clubbed together in

groups called vectors, and processed to give the output. This clubbing of data and treating them as a single unit increases the optimality of the vector quantizer, but at the cost of increased computational complexity.

sites.google.com/site/ncpdhbkhn 15

Image Restoration and Blind Deconvolution

1. Introduction 2. Image Compression – Decompression Steps 3. Error Metrics 4. Classifying Image Data 5. Bit Allocation 6. Quantization 7. Entropy Coding 8. JPEG Compression

sites.google.com/site/ncpdhbkhn 16

Entropy Coding

• After the data has been quantized into a finite set of

values, it can be encoded using an entropy coder to give additional compression.

• Entropy means the amount of information present in the data, and an entropy coder encodes the given set of symbols with the minimum number of bits required to represent them.

• Two of the most popular entropy coding schemes are

Huffman coding and arithmetic coding.

• These techniques allocate variable-length codes for

specific symbols (coefficient values in our case) in a set of values to be encoded.

• This saves even more space in terms of storage, thus

adding to the compression.

sites.google.com/site/ncpdhbkhn 17