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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Could you be more specific? $\endgroup$– jojeck ♦Jul 6, 2014 at 13:10
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
-
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$– rayryengJul 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$ 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$ 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$– rayryengJul 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$– rayryengJul 18, 2014 at 7:24
$\begingroup$
$\endgroup$
3
Zig-zag scanning is not a property of DCT, rather it is employed after the quantization of DCT coefficients, and before the Category / Run length coding (CAT-RLE) of them.
N x N blocks of typical images are low-pass in nature. Most of the signal energy is packed in the lower frequency DCT coefficients which are distributed circularly about the origin. Zig-zag scanning of those coefficients begins from the lowest frequency, and moves through a circular pattern from inside to outside.
The resulting 1D sequence typically will have a number of initial non-zero coefficients (based on the quality setting), and will be all zeroes afterwards, requiring no bits to encode yielding huge compression of the block.
CAT-RLE counts the number of consecutive zeroes in the zigzag scanned sequence, before coding the next 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 2D-DCT coefficients into a 1D sequence such that CAT/RLE coding can take advantage of the consecutive zeroes that result.
-
$\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$– Fat32Jul 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