4
$\begingroup$

I am not sure why zig zag manner scan is used in DCT. I can guess that might because it moves from low frequency component to high frequency component and as most of the energy is stored in low frequency component that's why this way of scan is favored but not quite sure.

$\endgroup$
1
  • 1
    $\begingroup$ Could you be more specific? $\endgroup$
    – jojek
    Jul 6, 2014 at 13:10

2 Answers 2

4
$\begingroup$

You are right! When it comes to quantization, bit allocation or issues like that scanning in zig zag manner seems to be most efficient.

As you said, (and I emphasize) in Natural Signals, lower frequency coefficients contain most of the energy. In a DCT matrix, as you go along a row the frequency is increasing in the first dimension and as you go along a column the frequency is increasing in the second dimension. A high frequency in any dimension probably contains less energy. So for example the $(2,2)$ entry in an $8\times 8$ DCT matrix $\bf{usually}$ contains more energy than the entry $(1,8)$ in the same matrix.

$\endgroup$
6
  • 1
    $\begingroup$ Another reason why the zigzag scan is used is related to JPEG quantization. As @Mahdi noted, zigzag scanning will order the DCT coefficients so that ones with higher energy appear first, then lower after. There will inevitably be a few non-zero coefficients, followed by many zeroes due to the infrequent occurrence of high frequency high energy coefficients. This ordering is quite optimal for lossless compression algorithms (Huffman, Arithmetic, etc.). DCT coefficient compression happens after zigzag ordering. The final output bitstream will be considerably less than a non-zigzagged order. $\endgroup$
    – rayryeng
    Jul 14, 2014 at 5:32
  • 1
    $\begingroup$ @rayryeng Why is this ordering acutally more suitable for entropy encoding? Doesn’t the range of values stay the same, thus you have to encode the same number of symbols? I would say this ordering is partiuclarily well suited for run-length or delta encoding since the values fluctuate less. $\endgroup$
    – Lenar Hoyt
    Jul 17, 2014 at 21:19
  • $\begingroup$ @rayryeng Is there actually a measure for the magnitude of flucutation of a signal? (Sorry for all these questions.) $\endgroup$
    – Lenar Hoyt
    Jul 17, 2014 at 21:23
  • 1
    $\begingroup$ @mcb - You're right. I actually forgot that RLE comes first, then Huffman coding comes after for the rest for further compression... so I missed a step. After zig-zag ordering comes RLE, then entropy encoding after. Nice spot! $\endgroup$
    – rayryeng
    Jul 18, 2014 at 7:22
  • $\begingroup$ @mcb - I would use classic entropy or information. This represents a rough expectation of how many bits are required to faithfully represent your signal. If there is a lot of fluctuation, you'd probably want more bits to represent this than with something that has less fluctuation... just a hunch, but don't take this as actual fact. $\endgroup$
    – rayryeng
    Jul 18, 2014 at 7:24
3
$\begingroup$

You already gave the spirit of the answer, but let me put it in other words:

First of all, zig-zag scanning is not a property of DCT itself but rather a part of the transform based image coding process.

Zig-zag scanning is employed after the quantization of DCT coefficients per N x N image block, and before the Category / Run length coding of the quantized coefficients.

Typical natural images of N x N (N=8 most typical) blocks are low pass which are reflected in their DCT coefficients as packing most of the signal energy in the lower index coefficients and further distributing them circularly about the origin.

Zig-zag scanning of those coefficients therefore begins from low order coefficients and moves through a circular pattern from inside to outside.

The resulting 1D sequence, after certain number of initial non-zero coefficients (whose number is based on the quality setting) most of the remaining quantized and ZZ scanned coeffficients will be zero requiring no bits to encode; hence copression.

The Category / Run length encoding (RLE) is such that it counts the number of "consequtive zeros" in the scanned sequence before coding a non-zero coefficient into a two part symbol: sym1-sym2. Sym1 (category) is based on the magnitude of the coefficient being coded and sym-2 (run length) is based on the number of zeros before that nonzero coefficient.

zig-zag scanning, therefore, orders the DCT coefficients into an efficient manner for this category/run length coding phase to take advantage of their structure...

$\endgroup$
3
  • $\begingroup$ Without the run length encoding (RLE) - say if only a "huffman tree" style compresion of the resulting quantitized 64 values was used, the ZIGZAG ordering was pointless, correct? Making the pecularity that non-zero values in the quantized matrix appear in the upper-left area of said matrix, is the reasoning behind the ZIGZAG, true? $\endgroup$ Jul 26, 2019 at 9:15
  • $\begingroup$ @humanityANDpeace yes and in much less words than I used in the answer ! RLE will benefit from the ZZ scanned pattern. However, further note that Huffman encoder will also benfit from ZZ, as the RLE symbol frequencies will depend on the scaning order, and these frequencies determine the efficiency of the standard Huffman table. $\endgroup$
    – Fat32
    Jul 26, 2019 at 11:54
  • $\begingroup$ thanks. Your last remark (that RLE will still also benefirt subsequent Huffman encoding) was also mentioned in this article that walks through the process $\endgroup$ Jul 26, 2019 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.