Image Compression-II 1 IMAGE COMPRESSION-II Week IX Image Compression-II 2 IMAGE COMPRESSION  Data redundancy  Self-information and Entropy  Error-free and lossy compression  Huffman coding  Predictive coding  Transform codingImage Compression-II 3 Data Redundancy • CODING: Fewer bits to represent frequent symbols. • INTERPIXEL / INTERFRAME: Neighboring pixels have similar values. • PSYCHOVISUAL: Human visual system can not simultaneously distinguish all colors. Image Compression-II 4 L l r p r AavgkkLrk= →=−∑( ) ( ) ( )01Coding Redundancy (contd.)  Consider equation (A): It makes sense to assign fewer bits to those rk for which pr(rk) are large in order to reduce the sum.  this achieves data compression and results in a variable length code.  More probable gray levels will have fewer # of bits.Image Compression-II 5 General Model General compression model Channel Channel encoder Source encoder Channel decoder Source decoder Source encoder f(x,y) Mapper Quantizer Symbol encoder f(x,y) g(x,y) To channel Image Compression-II 6 8.2.9: Predictive coding To reduce / eliminate interpixel redundancies Lossless predictive coding: ENCODER Σ"Image Predictor P QSymbol encoder + - fn fn en Compressed Image ^ Prediction error en= fn−ˆfnImage Compression-II 7 Decoder symbol decoder Σ"+ + Compressed image en fn Predictor fn original image Prediction error: en = fn - fn en is coded using a variable length code (symbol encoder) fn = en + fn ^ ^ ^ Image Compression-II 8 Example Example 1: ˆfn=Intαifn−ii=1m∑ → Linear predictor ; m = order of predictorExample 2: ˆf (x,y)=Intαif (x, y − i)i=1m∑ x y f(x,y) In 2- D X Wxy Past information Current pixel f (x,y) = Σ α (x’, y’) f (x’, y) (x’, y’) ε W xyImage Compression-II 9 An example of first order predictor Prediction error image Histograms of original and error images. ˆ(,)[(,1)fxyIntfxy=−Image Compression-II 10 Predictive coding and temporal redundancy f∧(x, y,t) = round[αf (x, y,t − 1)]e(x, y,t) = f (x, y,t) − f∧(x, y,t)Image Compression-II 11 Lossy Compression (pp. 596) Lossy compression: uses a quantizer to compress further the number of bits required to encode the ‘error’. First consider this: P Σ" Q Enc e en . Dec Σ" P en . fn ~ . fn fn ^ + Notice that, unlike in the case of loss-less prediction, in lossy prediction the predictors P “see” different inputs at the encoder and decoder e e f fn n n≠ ⇒ ≠~fn Image Compression-II 12 Quantization error This results in a gradual buildup of error which is due to the quantization error at the encoder site. In order to minimize this buildup of error due to quantization we should ensure that ‘Ps’ have the same input in both the cases. fn 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 fn = fn-1; ^ en = 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 en = 0 2 2 2 2 . . . . . . fn = 0 2 4 6 8 10 . . . . . . . Quantizer: e=0 if less than1; e=2 if >= 1.Image Compression-II 13 Example f e fe fn n nn n= += +−α1 f feeen nnnn==+ >− <−αξξ100and Example: 0 < α < 1 prediction coefficient Image Compression-II 14 Predictive Coding With Feedback f(x,y) + - Q symbol encoder + + P en en fn .fn ^ This feedback loop prevents error building fn = en + fn . . ^ . Compressed image Compressed image Symbol decoder P + + fn en fn ^ fn = en + fn . . ^ . . uncompressed imageImage Compression-II 15 Example with feedback fn = 0 1 2 3 4 en = _ 1 2 1 2 en = _ 0 2 0 2 .fn = 0 0 2 2 4 . fn = _ 0 0 2 2 ^ f(x,y) + - Q + + P en en fn .fn ^ Note: The quantizer used here is-- floor (en/2)*2. This is different from the one used in the earlier example. Note that this would result in a worse response if used without Feedback (output will be flat at “0”). . Image Compression-II 16 Another example {14, 15, 14, 15, 13, 15, 15, 14, 20, 26, 27, 28, 27, 27, 29, 37, 37, 62, 75, 77, 78, 79, 80, 81, 81, 82, 82}Image Compression-II 17 A comparison (Fig 8.23) Image Compression-II 18 Four linear predictorsImage Compression-II 19 Motion compensation in Video Coding sequence: e.g.,