CS4624 Ch6 - Compression

Compression Techniques

• Interpolation
  
  
  • Basic idea is shown in the linear case. Consider sequence IBPBP of numbers 6,10.5, 13,17,21. Interpolation replaces 10.5 by 1 which is computed as 10.5-(6+13)/2 and similarly replaces 17 by 0 which is computed as 17-(13+21)/2.
    
  • Also used to reconstitute an image that has been subsampled. Ex.: Start with a 16x16 block coded YUV 24bpp, keep 8 bpp for Y, but subsample U and V by 4:1 so have only 4x4 color matrix. That leads to 9 instead of 24bpp, as in DVI. Interpolation will reconstruct the original from the 4x4 matrix.
    
  • Used in MPEG interframe compression for B frames that are interpolation compressed based on nearest I and/or P frame on either side. This gives roughly 2:1 to 5:1 compression relative to a P frame.
    
  
  
• Prediction
  
  
  • DPCM with sequence 32, 34, 37, 40 with 32, +2, +3, +3
    
  • ADPCM with step sizes as powers of 2 (2^x) and sequence 16, 32, 64, 80 might be coded as x=4, 1, 1, x=5, 1, x=4, 1
    
  • MPEG uses prediction for P frames, from previous I or P frame. This gives roughly 3:1 savings vs. I frames. It relies upon motion compensation.
  
  
• Transform
  
  
  • Simple example, text Fig. 6.2, for 2x2 array of pixels: A, B, C, D might have transform: X0=A, X1=B-A, X2=C-A, X3=D-A and inverse transform: A=X0, B=X1+X0, C=X2+X0, D=X3+X0.
    
  • For an initial array A=10, B=13, C=12, D=11 we get transformed array X0=10, X1=3, X2=2, X3=1. So for 3/4 of the data we reduce the need from 4 bits to represent a value to only needing 2 bits.
    
  • JPEG codec using DCT
  
  
• Huffman-like coding
  
  
  • Assume p(A)=.5, p(B)=.25, p(C)=.25
    
  • Code A=0, B=10, C=11
    
  • Code lengths are |A|=1, |B|=|C|=2
    
  • Then average code length is (SUM of p(i)*|i|) = 1.5 which is less than 2 which would result from normal codings like 00, 01, 10
    
  
  
• Other Statistical Coding
  
  
  • zig-zag ordering
    
  • Run-length on 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 is 1*2, 4*1, 6*0
    
  • Run-length works in 2 dimensions for Group 3 FAX.