zig-zag order

[angelzhang]

hi,experts
In the reference software, pixel's value are decoded
according to zig-zag scan. the order is shown as following:
(0,0),(1,0),(0,1),(0,2),
(1,1),(2,0),(3,0),(2,1),
(1,2),(0,3),(1,3),(2,2),
(3,1),(3,2),(2,3),(3,3),
The order shown above is executed with the array
SNGL_SCAN[16][2] in the function named readCBPandCoeffsFromNAL.

but in the part 8.5.4 of H.264 standard, the figure 8-8 a) shown the
zig-zag order which is different with the reference software. why? please give me some hints.

thanks in advance
angel

[angelzhang]

why no replay?
is the question too easy to answer?

I find that the order used in the softeware can be same as that of the standard if i regard it as another means of 2D array orderring.

am i right?
please give your idea.

angel

[RadicalEd]

What does the spec say? The order you posted should be correct. Zig-zag order for a 4x4 matrix is
{0, _1, _5, _6}
{2, _4, _7, 12}
{3, _8, 11, 13}
{9, 10, 14, 15}

[angelzhang]

hi,RadicalEd
The standard just gives the order same as yours. but i'm confused about the corresponding relationship bettween the LumaList's 16 entry and the location of the matrix.
Given LumaList[7] is present, the data's corresponding location in the 2D array is (2,1) or (1,2) or others ?

thanks for your help.

best regards
angel

[RadicalEd]

Well the first thing you posted isn't a matrix, it's just an array listing the corresponding location on the matrix.

(0,0),(1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(1,3),(2,2),(3,1),(3,2),(2,3),(3,3)

In other words, the first element (0,0) would be at location 0,0 on the matrix I posted. Second element (1,0) would be at 1,0, etc. Here's just any 4x4 matrix in element locations:

0,0 1,0 2,0 3,0
0,1 1,1 2,1 3,1
0,2 1,2 2,2 3,2
0,3 1,3 2,3 3,3

and lumalist is just those values zigzag-scanned. So yes, lumalist[7] would be at location 2,1. Does that help? :O

[angelzhang]

hi, RadicalEd

I get it. and I have had a wrong idea of 2D array's indices as followings:
(0,0)(0,1)(0,2)(0,3)
(1,0)(1,1)(1,2)(1,3)
(2,0)(2,1)(2,2)(2,3)
(3,0)(3,1)(3,2)(3,3)

now, i understand the processing of the reference software.
thanks a lot!

best regards
angel

[nageshrelekar]

Hi all,
I think the zig zag order is used for the only to scan the coefficients, but the luma list is to send the 4x4 block in some order, i dont know i m right or wrong , please help me clear the idea and also let me know why they followed tht order.

[akupenguin]

I get it. and I have had a wrong idea of 2D array's indices as followings:
You may in fact see some implementations use that interpretation; x264 does. And it works, because if you transpose everything related to dct coefficients, including the dct transform itself, it's still consistent and produces the same bitstream as before. Plus the transposed version makes certain assembly optimizations faster.

I think the zig zag order is used for the only to scan the coefficients, but the luma list is to send the 4x4 block in some order, i dont know i m right or wrong , please help me clear the idea and also let me know why they followed that order.
Someone did some empirical study and found that the zigzag is pretty close to optimal at concentrating the nonzero coefficients towards the beginning of the list, which is good for entropy coding.