Zigzag Reordering

Zigzag reordering shuffles transformed samples in a zigzag pattern before or after transforms and quantization.

Theory

Zigzag reordering is often performed after transforms and quantization because it is likely to result in longer runs of zero coefficients which compress bettern using run length encoding. For example, after a transform operation and quantization, a block of transform coefficients is likely to have the majority of its non-zero coefficients sitting in the upper-left portion of the block:

197 10  0  0
 23  5  0  0
  9  0  0  0
  0  0  0  0

Without the zigzag reordering the subsequent run level encoding would resemble:

197 10 (2x0) 23 5 (2x0) 9 EOB

EOB (End Of Block) indicates that there are no more non-zero coefficients in the block.

However, after applying the following zigzag reorder matrix to the block:

  0  1  5  6
  2  4  7 12
  3  8 11 13
  9 10 14 15

the coefficient matrix becomes:

197 10 23  9
  5  0  0  0
  0  0  0  0
  0  0  0  0

and can be encoded as:

197 10 23 9 5 EOB

What A Multimedia Hacker Needs To Know

In every known codec where the discrete cosine transform (DCT) is employed to convert blocks of video data into a transform domain, the transform step is followed by a zigzag reordering (right after quantization which is essential for driving a lot of less significant coefficients to 0).

Zigzig Visualisations

The following c program and gnuplot script will transform any Ritchie-vintage scantable into an artwork masterpiece. Note that y-axis values are flipped to given screen-like output on a cartesian plane.

 /* output (x,y) pairs for TABLE[n] array of length DIMxDIM */
 #define DIM 8
 #define TABLE ff_zigzag_direct
 int main() {
   int i;
   for(i=0;i<DIM*DIM;i++)
     printf("%i\t%i\n", TABLE[i]%DIM, -TABLE[i]/DIM);
 }

 # plot (x,y) pairs
 unset border
 set key off
 set grid
 plot "pairs.dat" with linespoints linewidth 3 linetype -1 pointtype 7