## 4.2. Video Compression

JPEG
H.261
MPEG

Reference: Chapter 6 of Steinmetz and Nahrstedt

### Motivations:

1. Uncompressed video and audio data are huge. In HDTV, the bit rate easily exceeds 1 Gbps. --> big problems for storage and network communications.

2. The compression ratio of lossless methods (e.g., Huffman, Arithmetic, LZW) is not high enough for image and video compression, especially when distribution of pixel values is relatively flat.

The following will be discussed:

- Spatial Redundancy Removal -- Intraframe coding (JPEG)

- Spatial and temporal Redundancy Removal -- Intraframe and Interframe coding (H.261, MPEG)

## 4.2.1. JPEG

### 1. What is JPEG?

- "Joint Photographic Expert Group". Voted as international standard in 1992.

- Works with color and grayscale images, e.g., satellite, medical, ...

### 2. JPEG overview

- Encoding

- Decoding -- Reverse the order

### 3. Major Steps

- DCT (Discrete Cosine Transformation)

- Quantization

- Zigzag Scan

- DPCM on DC component

- RLE on AC Components

- Entropy Coding

### 3a. Discrete Cosine Transform (DCT)

- Overview:

- Definition (8 point DCT):

  Question: What is F[0,0]? -- define DC and AC components.

- The 64 (8 x 8) DCT basis functions

- Why DCT not FFT?

  DCT is like FFT, but can approximate lines well with few coeff.

- Computing the DCT

  - Factoring reduces problem to a series of 1D DCTs:

  - Most software implementations use fixed point arithmetic. Some fast implementations approximate coefficients so all multiplies are shifts and adds.

  - World record is 11 multiplies and 29 adds. (C. Loeffler, A. Ligtenberg and G. Moschytz, "Practical Fast 1-D DCT Algorithms with 11 Multiplications", Proc. Int'l. Conf. on Acoustics, Speech, and Signal Processing 1989 (ICASSP `89), pp. 988-991)

### 3b. Quantization

- Why? -- To throw out bits

- Example: 101101 = 45 (6 bits).
  Truncate to 4 bits: 1011 = 11.
  Truncate to 3 bits: 101 = 5.

- Quantization error is the main source of the Lossy Compression.

#### Uniform quantization

- Divide by constant N and round result (N = 4 or 8 in examples above).

- Non powers-of-two gives fine control (e.g., N = 6 loses 2.5 bits)

#### Quantization Tables

- In JPEG, each F[u,v] is divided by a constant q(u,v).

- Table of q(u,v) is called quantization table.

      ----------------------------------
      16  11  10  16  24   40   51   61
      12  12  14  19  26   58   60   55
      14  13  16  24  40   57   69   56
      14  17  22  29  51   87   80   62
      18  22  37  56  68   109  103  77
      24  35  55  64  81   104  113  92
      49  64  78  87  103  121  120  101
      72  92  95  98  112  100  103  99
      ----------------------------------

- Eye is most sensitive to low frequencies (upper left corner), less sensitive to high frequencies (lower right corner)

- Standard defines 2 default quantization tables, one for luminance (above), one for chrominance.

- Q: How would changing the numbers affect the picture (e.g., if I doubled them all)?

  Quality factor in most implementations is the scaling factor for default quantization tables.

- Custom quantization tables can be put in image/scan header.

### 3c. Zig-zag Scan

- Why? -- to group low frequency coefficients in top of vector.

- Maps 8 x 8 to a 1 x 64 vector

### 3d. Differential Pulse Code Modulation (DPCM) on DC component

- DC component is large and varied, but often close to previous value (like lossless JPEG).

- Encode the difference from previous 8x8 blocks -- DPCM

### 3e. Run Length Encode (RLE) on AC components

- 1x64 vector has lots of zeros in it

- Encode as (skip, value) pairs, where skip is the number of zeros and value is the next non-zero component.

- Send (0,0) as end-of-block sentinel value.

### 3f. Entropy Coding

- Categorize DC values into SSS (number of bits needed to represent) and actual bits.

          --------------------
             Value       SSS
               0          0
              -1,1        1
           -3,-2,2,3      2
          -7..-4,4..7     3
          --------------------

- Example: if DC value is 4, 3 bits are needed.

  Send off SSS as Huffman symbol, followed by actual 3 bits.

- For AC components (skip, value), encode the composite symbol (skip,SSS) using the Huffman coding.

- Huffman Tables can be custom (sent in header) or default.

### 4. Overview of the JPEG bitstream

- A "Frame" is a picture, a "scan" is a pass through the pixels (e.g., the red component), a "segment" is a group of blocks, a "block" is an 8x8 group of pixels.

- Frame header:
  sample precision
  (width, height) of image
  number of components
  unique ID (for each component)
  horizontal/vertical sampling factors (for each component)
  quantization table to use (for each component)

- Scan header
  Number of components in scan
  component ID (for each component)
  Huffman table for each component (for each component)

- Misc. (can occur between headers)
  Quantization tables
  Huffman Tables
  Arithmetic Coding Tables
  Comments
  Application Data

### 5. Various JPEG Modes

- Baseline/Sequential -- the one that we described in detail

- Lossless

- Progressive

- Hierarchical

- "Motion JPEG" -- Baseline JPEG applied to each image in a video.

1. Lossless Mode

   - A special case of the JPEG where indeed there is no loss

   - Take difference from previous pixels (not blocks as in the Baseline mode) as a "predictor".

     Predictor uses linear combination of previously encoded neighbors.
     It can be one of seven different predictor based on pixels neighbors

   - Since it uses only previously encoded neighbors, first row always uses P2, first column always uses P1.

   - Effect of Predictor (test with 20 images)

     Note: "2D" predictors (4-7) always do better than "1D" predictors.

   Comparison with Other Lossless Compression Programs (compression ratio):

       -----------------------------------------------------------------
            Compression Program              Compression Ratio
                                       Lena  football    F-18   flowers
       -----------------------------------------------------------------
               lossless JPEG           1.45     1.54     2.29     1.26
           optimal lossless JPEG       1.49     1.67     2.71     1.33
              compress (LZW)           0.86     1.24     2.21     0.87
             gzip (Lempel-Ziv)         1.08     1.36     3.10     1.05
       gzip -9 (optimal Lempel-Ziv)    1.08     1.36     3.13     1.05
           pack (Huffman coding)       1.02     1.12     1.19     1.00
       -----------------------------------------------------------------

2. Progressive Mode

   - Goal: display low quality image and successively improve.

   - Two ways to successively improve image:

     1. Spectral selection: Send DC component, then first few AC, some more AC, etc.

     2. Successive approximation: send DCT coefficients MSB (most significant bit) to LSB (least significant bit).

3. Hierarchical Mode

   A Three-level Hierarchical JPEG Encoder

   (From V. Bhaskaran and K. Konstantinides, "Image and Video Compression Standards: Algorithms and Architectures", Kluwer Academic Publishers, 1995.)

   - Down-sample by factors of 2 in each direction.

     Example: map 640x480 to 320x240

   - Code smaller image using another method (Progressive, Baseline, or Lossless).

   - Decode and up-sample encoded image

   - Encode difference between the up-sampled and the original using Progressive, Baseline, or Lossless.

   - Can be repeated multiple times.

   - Good for viewing high resolution image on low resolution display.

4. JPEG-2

   - Big change was to use adaptive quantization

### Further Exploration

Try the Interactive JPEG examples and the JPEG examples.

## 4.2.2. H. 261

- Developed by CCITT in 1988-1990

- Meant for videoconferencing, videotelephone applications over ISDN telephone lines.

- Baseline ISDN is 64 kbits/sec, and integral multiples (px64)

### 1. Overview of H.261

- Decoded Sequence

- Frame types are CCIR 601 CIF (352x288) and QCIF (176x144) images with 4:2:0 subsampling.

- Two frame types: Intraframes (I-frames) and Interframes (P-frames)

- I-frames use basically JPEG

- P-frames use "pseudo-differences" from previous frame ("predicted"), so frames depend on each other.

- I-frame provide us with an accessing point.

### 2. Intra Frame Coding

- Macroblocks are 16x16 pixel areas on Y plane of original image.

  A macroblock usually consists of 4 Y blocks, 1 Cr block, and 1 Cb block.

- Quantization is by constant value for all DCT coefficients (i.e., no quantization table as in JPEG).

### 3. Inter-frame (P-frame) Coding

- An Coding Example (P-frame)

- Previous image is called reference image.

- Image to code is called target image.

- Actually, the difference is encoded.

- Subtle points:

  1. Need to used decoded image as reference image, not original. Why?

  2. We're using "Mean Absolute Difference" (MAD) to decide best block. Can also use "Mean Squared Error" (MSE) = sum(E*E)

### 4. Details -- How the Macroblock is Coded

- Many macroblocks will be exact matches (or close enough). So send address of each block in image --> Addr

- Sometimes no good match can be found, so send INTRA block --> Type

- Will want to vary the quantization to fine tune compression, so send quantization value --> Quant

- Motion vector --> vector

- Some blocks in macroblock will match well, others match poorly. So send bitmask indicating which blocks are present (Coded Block Pattern, or CBP).

- Send the blocks (4 Y, 1 Cr, 1 Cb) as in JPEG.

### 5. H.261 Bitstream Structure

- Need to delineate boundaries between pictures, so send Picture Start Code --> PSC

- Need timestamp for picture (used later for audio synchronization), so send Temporal Reference --> TR

- Is this a P-frame or an I-frame? Send Picture Type --> PType

- Picture is divided into regions of 11x3 macroblocks called Groups of Blocks --> GOB

- Might want to skip whole groups, so send Group Number (Grp #)

- Might want to use one quantization value for whole group, so send Group Quantization Value --> GQuant

- Overall, bitstream is designed so we can skip data whenever possible while still unambiguous.

### 6. H.261 Codec

### 7. Hard Problems in H.261

- Motion vector search

- Propagation of Errors

- Bit-rate Control

### 7a. Motion Vector Search

- -- pixels in the macro block with upper left corner (x,y) in the Target.

  -- pixels in the macro block with upper left corner (x+i,y+j) in the Reference.

  Cost function is:

  Where MAE stands for Mean Absolute Error.

- Goal is to find a vector (u, v) such that MAE (u, v) is minimum

- Full Search Method:

  1. Search the whole [-p,p] searching region.

  2. Cost is: operations,
     assuming that each pixel comparison needs 3 operations (Subtraction, Absolute value, Addition).

- Two-Dimensional Logarithmic Search:

  Similar to binary search. MAE function is initially computed within a window of [-p/2, p/2] at nine locations as shown in the figure.

  Repeat until the size of the search region is one pixel wide:

  1. Find one of the nine locations that yields the minimum MAE

  2. Form a new searching region with half of the previous size and centered at the location found in step 1.

- Hierarchical Motion Estimation:

  1. Form several low resolution version of the target and reference pictures

  2. Find the best match motion vector in the lowerest resolution version.

  3. Modify the motion vector level by level when going up

- Performance comparison:

          -----------------------------------------------------------------
      	Search Method          Operation for 720x480 at 30 fps
      				 p = 15                 p=7
          -----------------------------------------------------------------
            Full Search               29.89 GOPS            6.99 GOPS
            Logarithmic                1.02 GOPS          777.60 MOPS
            Hierarchical             507.38 MOPS          398.52 MOPS
          -----------------------------------------------------------------

### 7b. Propagation of Errors

- Send an I-frame every once in a while

- Make sure you use decoded frame for comparison

### 7c. Bit-rate Control

- Simple feedback loop based on "buffer fullness"

  If buffer is too full, increase the quantization scale factor to reduce the data.

## 4.2.3. MPEG

### 1. What is MPEG ?

- "Motion Picture Expert Group", established circa 1990 to create standard for delivery of audio and video

- MPEG-1 Target: VHS quality on a CD-ROM (320 x 240 + CD audio @ 1.5 Mbits/sec)

- Standard had three parts:

  1. Video: based on H.261 and JPEG

  2. Audio: based on MUSICAM technology

  3. System: control interleaving of streams

### 2. MPEG Video

- Recall H.261 dependencies:

- Problem: many macroblocks need information not in the reference frame.

- Example:

- MPEG solution: add third frame type: bidirectional frame, or B-frame

- B-frames search for macroblock in past and future frames.

- Typical pattern is IBBPBBPBB IBBPBBPBB IBBPBBPBB

  Actual pattern is up to encoder, and need not be regular.

### 3. Differences from H.261

- Larger gaps between I and P frames, so expand motion vector search range.

- To get better encoding, allow motion vectors to be specified to fraction of a pixel (1/2 pixels).

- Bitstream syntax must allow random access, forward/backward play, etc.

- Added notion of slice for synchronization after loss/corrupt data. Example: picture with 7 slices:

- B frame macroblocks can specify two motion vectors (one to past and one to future), indicating result is to be averaged.

- Compression performance of MPEG 1

      ------------------------------
      Type      Size     Compression
      ------------------------------
       I      18   KB        7:1
       P       6   KB       20:1
       B       2.5 KB       50:1
      Avg      4.8 KB       27:1
      ------------------------------

### 4. MPEG Video Bitstream

- Public domain tool `mpeg_stat` and `mpeg_bits` will analyze a bitstream.

- Sequence Information

  1. Video Params include width, height, aspect ratio of pixels, picture rate.

  2. Bitstream Params are bit rate, buffer size, and constrained parameters flag (means bitstream can be decoded by most hardware)

  3. Two types of QTs: one for intra-coded blocks (I-frames) and one for inter-coded blocks (P-frames).

- Group of Pictures (GOP) information

  1. Time code: bit field with SMPTE time code (hours, minutes, seconds, frame).

  2. GOP Params are bits describing structure of GOP. Is GOP closed? Does it have a dangling pointer broken?

- Picture Information

  1. Type: I, P, or B-frame?

  2. Buffer Params indicate how full decoder's buffer should be before starting decode.

  3. Encode Params indicate whether half pixel motion vectors are used.

- Slice information

  1. Vert Pos: what line does this slice start on?

  2. QScale: How is the quantization table scaled in this slice?

- Macroblock information

  1. Addr Incr: number of MBs to skip.

  2. Type: Does this MB use a motion vector? What type?

  3. QScale: How is the quantization table scaled in this MB?

  4. Coded Block Pattern (CBP): bitmap indicating which blocks are coded.

### 5. Decoding MPEG Video in Software

- Software Decoder goals: portable, multiple display types

- Breakdown of time

      -------------------------
           Function      % Time
      Parsing Bitstream  17.4%
      IDCT               14.2%
      Reconstruction     31.5%
      Dithering          24.5%
      Misc. Arith.       9.9%
      Other              2.7%
      -------------------------

### 6. MPEG-2, MPEG-3, and MPEG-4

- MPEG-2 target applications

      --------------------------------------------------------------------
        Level        size     Pixels/sec   bit-rate      Application
                                           (Mbits)
      --------------------------------------------------------------------
      Low         352 x 240       3 M         4        consumer tape equiv.
      Main        720 x 480      10 M        15        studio TV
      High 1440  1440 x 1152     47 M        60        consumer HDTV
      High       1920 x 1080     63 M        80        film production
      --------------------------------------------------------------------

- Differences from MPEG-1

  1. Search on fields, not just frames.

  2. 4:2:2 and 4:4:4 macroblocks

  3. Frame sizes as large as 16383 x 16383

  4. Scalable modes: Temporal, Progressive,...

  5. Non-linear macroblock quantization factor

  6. A bunch of minor fixes (see MPEG FAQ for more details)

- MPEG-3: Originally for HDTV (1920 x 1080), got folded into MPEG-2

- MPEG-4: Very little published information. Originally targeted at very low bit-rate communication (4.8 to 64 kb/sec). Now addressing video processing...

### Further Exploration

MPEG Resources on the Web.

###### Last Updated: 6/26/96

Top | Chap 4 | CMPT 365 Home Page | CS