數(shù)字圖像處理,岡薩雷斯,課件英文版Chapter08圖像壓縮

1、Digital Image Processing Chapter 8: Image Compression 11 August 2006,Data vs Information,Information = Matter () Data = The means by which information is conveyed,Reducing the amount of data required to represent a digital image while keeping information as much as possible,Image Compression,Relativ

2、e Data Redundancy and Compression Ratio,Relative Data Redundancy,Compression Ratio,Types of data redundancy,1. Coding redundancy 2. Interpixel redundancy 3. Psychovisual redundancy,Coding Redundancy,Different coding methods yield different amount of data needed to represent the same information.,Exa

3、mple of Coding Redundancy : Variable Length Coding vs. Fixed Length Coding,Lavg 3 bits/symbol,Lavg 2.7 bits/symbol,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Variable Length Coding,Concept: assign the longest code word to the symbol with the least pro

4、bability of occurrence.,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Interpixel Redundancy,Interpixel redundancy: Parts of an image are highly correlated. In other words,we can predict a given pixel from its neighbor.,(Images from Rafael C. Gonzalez and

5、 Richard E. Wood, Digital Image Processing, 2nd Edition.,Run Length Coding,The gray scale image of size 343x1024 pixels,Binary image = 343x1024x1 = 351232 bits,Line No. 100,Run length coding,Line 100: (1,63) (0,87) (1,37) (0,5) (1,4) (0,556) (1,62) (0,210),Total 12166 runs, each run use 11 bits Tota

6、l = 133826 Bits,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Psychovisual Redundancy,The eye does not response with equal sensitivity to all visual information.,8-bit gray scale image,4-bit gray scale image,4-bit IGS image,False contours,(Images from Ra

7、fael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Improved Gray Scale Quantization,Pixel i-1 i i+1 i+2 i+3,Gray level N/A 0110 1100 1000 1011 1000 0111 1111 0100,Sum 0000 0000 0110 1100 1001 0111 1000 1110 1111 0100,IGS Code N/A 0110 1001 1000 1111,+,Algorithm 1. Add the l

8、east significant 4 bits of the previous value of Sum to the 8-bit current pixel. If the most significant 4 bit of the pixel is 1111 then add 0000 instead. Keep the result in Sum 2. Keep only the most significant 4 bits of Sum for IGS code.,Fidelity Criteria: how good is the compression algorithm,Obj

9、ective Fidelity Criterion RMSE, PSNR Subjective Fidelity Criterion: Human Rating,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Image Compression Models,Source encoder,Channel encoder,Source decoder,Channel decoder,Channel,Reduce data redundancy,Increase

10、noise immunity,Noise,Source Encoder and Decoder Models,Mapper,Quantizer,Symbol encoder,Source encoder,Inverse mapper,Symbol decoder,Source decoder,Reduce interpixel redundancy,Reduce psychovisual redundancy,Reduce coding redundancy,Channel Encoder and Decoder,- Hamming code, Turbo code, ,Information

11、 Theory,Measuring information,Entropy or Uncertainty: Average information per symbol,Simple Information System,Binary Symmetric Channel,A = a1, a2 =0, 1 z = P(a1), P(a2),B = b1,b2 =0, 1 v = P(b1), P(b2),Source,Destination,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing,

12、 2nd Edition.,0,1,(1-Pe),Pe,0,1,Pe,(1-Pe),Source,Destination,Pe= probability of error,P(a1),1-P(a1),P(a1)(1-Pe)+(1-P(a1)Pe,(1-P(a1)(1-Pe)+P(a1)Pe,Binary Symmetric Channel,A = a1, a2 =0, 1 z = P(a1), P(a2),B = b1,b2 =0, 1 v = P(b1), P(b2),H(z) = - P(a1)log2P(a1) - P(a2)log2P(a2),Source,Destination,H(

13、z|b1) = - P(a1|b1)log2P(a1|b1) - P(a2|b1)log2P(a2|b1) H(z|b2) = - P(a1|b2)log2P(a1|b2) - P(a2|b2)log2P(a2|b2),H(z|v) = H(z|b1) + H(z|b2),Mutual information,I(z,v)=H(z) - H(z|v),Capacity,Binary Symmetric Channel,Let pe = probability of error,Binary Symmetric Channel,(Images from Rafael C. Gonzalez an

14、d Richard E. Wood, Digital Image Processing, 2nd Edition.,Communication System Model,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,2 Cases to be considered: Noiseless and noisy,Noiseless Coding Theorem,Problem: How to code data as compact as possible?,Sh

15、annons first theorem: defines the minimum average code word length per source that can be achieved.,Let source be A, z which is zero memory source with J symbols. (zero memory = each outcome is independent from other outcomes),then a set of source output of n element be,Example:,for n = 3,Noiseless

16、Coding Theorem (cont.),Probability of each aj is,Entropy of source :,Each code word length l(ai) can be,Then average code word length can be,Noiseless Coding Theorem (cont.),or,The minimum average code word length per source symbol cannot lower than the entropy.,Coding efficiency,We get,from,then,Ex

17、tension Coding Example,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,H = 1.83 Lavg = 1.89,H = 0.918 Lavg = 1,Noisy Coding Theorem,Problem: How to code data as reliable as possible?,Example: Repeat each code 3 times:,Source data = 1,0,0,1,1,Data to be sen

18、t = 111,000,000,111,111,Shannons second theorem: the maximum rate of coded information is,r = Block length,j = code size,Rate Distortion Function for BSC,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Error-Free Compression: Huffman Coding,(Images from Ra

19、fael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Step 1: Source reduction,Huffman coding: give the smallest possible number of code symbols per source symbols.,Error-Free Compression: Huffman Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Proces

20、sing, 2nd Edition.,Step 2: Code assignment procedure,The code is instantaneous uniquely decodable without referencing succeeding symbols.,Near Optimal Variable Length Codes,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Arithmetic Coding,(Images from Rafa

21、el C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Nonblock code: one-to-one correspondence between source symbols And code words does not exist. Concept: The entire sequences of source symbols is assigned a single arithmetic code word in the form of a number in an interval o

22、f real number between 0 and 1.,Arithmetic Coding Example,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,0.2x0.4,0.04+0.8x0.04,0.056+0.8x0.016,0.2x0.2,0.04+0.4x0.04,0.056+0.4x0.016,The number between 0.0688 and 0.06752 can be used to represent the sequence

23、 a1 a2 a3 a3 a4,LZW Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Lempel-Ziv-Welch coding : assign fixed length code words to variable length sequences of source symbols.,24 Bits,9 Bits,LZW Coding Algorithm,0. Initialize a dictionary by all possib

24、le gray values (0-255) 1. Input current pixel 2. If the current pixel combined with previous pixels form one of existing dictionary entries Then 2.1 Move to the next pixel and repeat Step 1 Else 2.2 Output the dictionary location of the currently recognized sequence (which is not include the current

25、 pixel) 2.3 Create a new dictionary entry by appending the currently recognized sequence in 2.2 with the current pixel 2.4 Move to the next pixel and repeat Step 1,LZW Coding Example,Input pixel 39 39 126 126 39 39 126 126 39 39 126 126,Dictionary Location Entry 0 0 1 1 255 255 256 39-39 257 39-126

26、258 126-126 259 126-39 260 39-39-126 261 126-126-39 262 39-39-126-126,Encoded Output (9 bits) 39 39 126 126 256 258 260,Currently recognized Sequences 39 39 126 126 39 39-39 126 126-126 39 39-39 39-39-126 126,Bit-Plane Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Process

27、ing, 2nd Edition.,Original image,Bit 7,Bit 6,Bit 0,Bit plane images,Binary image compression,Binary image compression,Binary image compression,Example of binary image compression: Run length coding,Bit Planes,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.

28、,Original gray scale image,Bit 7,Bit 6,Bit 5,Bit 4,Bit 3,Bit 2,Bit 1,Bit 0,Gray-coded Bit Planes,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,a7,a6,a5,a4,g7,g6,g5,g4,Gray code:,and,ai= Original bit planes,= XOR,Original bit planes,Gray-coded Bit Planes

29、(cont.),a3,a2,a1,a0,g3,g2,g1,g0,There are less 0-1 and 1-0 transitions in grayed code bit planes. Hence gray coded bit planes are more efficient for coding.,Relative Address Coding (RAC),(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Concept: Tracking bin

30、ary transitions that begin and end eack black and white run,Contour tracing and Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Represent each contour by a set of boundary points and directionals.,Error-Free Bit-Plane Coding,(Images from Rafael C. G

31、onzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Lossless VS Lossy Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Lossless coding,Lossy coding,Transform Coding (for fixed resolution transforms),(Images from Rafael C. Gonzalez and

32、 Richard E. Wood, Digital Image Processing, 2nd Edition.,Construct nxn subimages,Forward transform,Quantizer,Symbol encoder,Input image (NxN),Compressed image,Construct nxn subimages,Inverse transform,Symbol decoder,Decompressed image,Decoder,Encoder,Examples of transformations used for image compre

33、ssion: DFT and DCT,Quantization process causes The transform coding “l(fā)ossy”,Transform Coding (for fixed resolution transforms),3 Parameters that effect transform coding performance: Type of transformation Size of subimage Quantization algorithm,2D Discrete Transformation,Forward transform:,Inverse t

34、ransform:,where g(x,y,u,v) = forward transformation kernel or basis function,where h(x,y,u,v) = inverse transformation kernel or inverse basis function,T(u,v) is called the transform coefficient image.,Transform Example: Walsh-Hadamard Basis Functions,(Images from Rafael C. Gonzalez and Richard E. W

35、ood, Digital Image Processing, 2nd Edition.,N = 4,N = 2m,bk(z) = the kth bit of z,Advantage: simple, easy to implement Disadvantage: not good packing ability,Transform Example: Discrete Cosine Basis Functions,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.

36、,DCT is one of the most frequently used transform for image compression. For example, DCT is used in JPG files.,N = 4,N = 4,Advantage: good packing ability, modulate computational complexity,Transform Coding Examples,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd

37、Edition.,Original image 512x512 pixels,Fourier,Hadamard,DCT,Error,Subimage size: 8x8 pixels = 64 pixels,Quatization by truncating 50% of coefficients (only 32 max cofficients are kept.),RMS Error = 1.28,RMS Error = 0.86,RMS Error = 0.68,DCT vs DFT Coding,(Images from Rafael C. Gonzalez and Richard E

38、. Wood, Digital Image Processing, 2nd Edition.,Advantage of DCT over DFT is that the DCT coefficients are more continuous at boundaries of blocks.,DFT coefficients have abrupt changes at boundaries of blocks,1 Block,Subimage Size and Transform Coding Performance,(Images from Rafael C. Gonzalez and R

39、ichard E. Wood, Digital Image Processing, 2nd Edition.,This experiment: Quatization is made by truncating 75% of transform coefficients,DCT is the best,Size 8x8 is enough,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Subimage Size and Transform Coding Pe

40、rformance,Zoomed detail Original,Reconstructed by using 25% of coefficients (CR = 4:1) with 8x8 sub- images,DCT Coefficients,Zoomed detail Subimage size: 8x8 pixels,Zoomed detail Subimage size: 2x2 pixels,Zoomed detail Subimage size: 4x4 pixels,Quantization Process: Bit Allocation,To assign differen

41、t numbers of bits to represent transform coefficients based on importance of each coefficient: - More importance coefficeitns assign a large number of bits - Less importance coefficients assign a small number of bits or not assign at all,2 Popular bit allocation methods 1. Zonal coding : allocate bi

42、ts based on the basis of maximum variance, using fixed mask for all subimages 2. Threshold coding : allocate bits based on maximum magnitudes of coefficients,Example: Results with Different Bit Allocation Methods,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edit

43、ion.,Reconstructed by using 12.5% of coefficients (8 coefficients with largest magnitude are used),Threshold coding Error,Zoom details,Reconstructed by using 12.5% of coefficients (8 coefficients with largest variance are used),Zonal coding Error,Zonal Coding Example,(Images from Rafael C. Gonzalez

44、and Richard E. Wood, Digital Image Processing, 2nd Edition.,Zonal mask,Zonal bit allocation,Threshold Coding Example,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Threshold mask,Thresholded coefficient ordering,Thresholding Coding Quantization,(Images fr

45、om Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,3 Popular Thresholding Methods Method 1: Global thresholding : Use a single global threshold value for all subimages Method 2: N-largest coding: Keep only N largest coefficients Method 3: Normalized thresholding: each

46、subimage is normalized by a normalization matrix before rounding,Example of Normalization Matrix Z(u,v),Bit allocation,Restoration before decompressing,DCT Coding Example,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,(CR = 38:1),(CR = 67:1),Zoom details,

47、Method: - Normalized Thresholding, - Subimage size: 8x8 pixels,Blocking Artifact at Subimage boundaries,Error image RMS Error = 3.42,Wavelet Transform Coding: Multiresolution approach,Unlike DFT and DCT, Wavelet transform is a multiresolution transform.,What is a Wavelet Transform,One up on a time,

48、human uses a line to represent a number. For example,= 25,With this numerical system, we need a lot of space to represent a number 1,000,000.,Then, after an Arabic number system is invented, life is much easier. We can represent a number by a “digit number”:,X,XXX,XXX,The 1st digit = 1x,The 2nd digi

49、t = 10 x,The 3rd digit = 100 x,An Arabic number is one kind of multiresolution Representation.,Like a number, any signal can also be represented by a multiresolution data structure, the wavelet transform.,What is a Wavelet Transform,Wavelet transform has its background from multiresolution analysis

50、and subband coding.,- Nyquist theorem: The minimun sampling rate needed for sampling a signal without loss of information is twice the maximum frequency of the signal. We can perform frequency shift by multiplying a complex sinusiodal signal in time domain.,Other important background:,Wavelet Histor

51、y: Image Pyramid,Pyramidal structured image,Coarser, decrease resolution,Finer, increase resolution,If we smooth and then down sample an image repeatedly, we will get a pyramidal image:,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Image Pyramid and Mult

52、iscale Decomposition,Image NxN,Smooth,Down Sampling By 2,Image N/2xN/2,Question: What Information is loss after down Sampling?,Answer: Loss Information is A prediction error image:,Up Sampling By 2,Interpolate,Predicted Image NxN,Prediction Error (loss details) NxN,S,-,+,Image Pyramid and Multiscale

53、 Decomposition (cont.),Hence we can decompose an image using the following process,Image NxN,Smooth and down sampling by 2,Approxi- -mation Image N/2xN/2,Up sampling by 2 and interpolate,Prediction Error NxN,S,Smooth and down sampling by 2,Approxi- -mation Image N/4xN/4,Up sampling by 2 and interpol

54、ate,Prediction Error N/2xN/2,S,+,-,+,-,.,Image Pyramid and Multiscale Decomposition (cont.),Original Image NxN,Prediction error (residue) NxN,Prediction error N/2xN2,Prediction error N/4xN/4,Approximation image N/8xN/8,=,Multiresolution Representation,Multiresolution Decomposition Process,Note that

55、this process is not a wavelet decomposition process !,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Example of Pyramid Images,Approximation Images (using Gaussian Smoothing),Prediction residues,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital

56、 Image Processing, 2nd Edition.,Subband Coding,x(n) N points,LPF,HPF,Down Sampling by 2,Freq. shift by N/2,Down Sampling by 2,Subband decomposition process,h1(n),h0(n),a(n) N/2 points,d(n) N/2 points,All information of x(n) is completely preserved in a(n) and d(n).,Approximation,Detail,Subband Codin

57、g (cont.),x(n) N points,Up Sampling by 2,Up Sampling by 2,Subband reconstruction process,Interpolation,g0(n),a(n) N/2 points,d(n) N/2 points,Interpolation,Freq. shift by N/2,g1(n),S,Subband Coding (cont.),(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,2D

58、Subband Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Example of 2D Subband Coding,(Images from Rafael C. Gonzalez and Richard E. Wood, Digital Image Processing, 2nd Edition.,Diagonal detail: filtering in both x and y directions using h1(n),Horizo

59、ntal detail: filtering in x- direction using h1(n) and in y- direction using h0(n),Approximation: filtering in both x and y directions using h0(n),Vertical detail: filtering in x- direction using h0(n) and in y- direction using h1(n),1D Discrete Wavelet Transformation,x(n) N points,h j(n),h y(n),h j(n),h y(n