Digital image processing image compression

Nguyễn Công Phương DIGITAL IMAGE PROCESSING Image Compression Contents I. Introduction to Image Processing & Matlab II. Image Acquisition, Types, & File I/O III. Image Arithmetic IV. Affine & Logical Operations, Distortions, & Noise in Images V. Image Transform VI. Spatial & Frequency Domain Filter Design VII. Image Restoration & Blind Deconvolution VIII. Image Compression IX. Edge Detection X. Binary Image Processing XI. Image Encryption & Watermarking XII. Image Classification & Segmentation 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 • 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 2 1 1 1 [ ( , ) ( , )] M N m n MSE f m n g m n M N      10 25520logPSNR MSE      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. Initially, all classes are allocated a predefined maximum number of bits. 2. 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. 4. The total distortion for all classes D is calculated. 5. 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 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 18 JPEG Compression • JPEG: the Joint Photographic Experts Group. • It uses 24-bit color for RGB images. • Advantage: it provides true color while compressing image files more than the lossless compression methods. • Disadvantage: it must use a lossy compression method, so some image data is lost. • The JPEG method is based on the fact that humans are much more aware of small changes in brightness (luminance) than to small changes in color or large changes in color or brightness. sites.google.com/site/ncpdhbkhn 19