Cryptography Reference
In-Depth Information
Zigzag scanning
23
*
0,3
0,8
1,3
0, -18
0, -3
0, -3
0, -1
0, -1
3,1
0,1
0,1
1,1
EOB
1011000
0111
10111000
11100111
1101001101
0100
0100
000
000
111011
001
001
11001
1010
23
23
3 -18 -3
3 -18 -3
1
1
0
0
0
0
0
0
8
8
3
3
-3
-3
1
1
1
1
0
0
0
0
0
0
0
0
-1
-1
0
0
0
0
0
0
0
0
0
0
0
0
23, 3, -18, -3, 1, 0, 0, 0, 8, 3, -3, 1,
1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1,
0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-1
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Huffman
coding
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Run length coding
(a) DCT coefficients (b) Zigzag scanning result (c) Run length (d) Huffman
coding
coding
Fig. 2.8.
Zigzag scanning, run length scanning and variable length coding.
in Fig. 2.8(c), (1, 3), indicates that there is one zero between the current
nonzero AC value 3, and its preceding nonzero AC value 8, and so on. The last
symbol,
EOB
, in Fig. 2.8(c), is the acronym of End of the Block, indicating
that there are no nonzero values in the remaining sequence of this 88
block. Therefore, by comparing Fig. 2.8(b) and Fig. 2.8(c), we can find that
run length coding is quite effective in representing the zigzag scanned DCT
coe
cients.
In general, the effectiveness of run length coding depends on the number
of equal values in a data stream in relation to the total number of input
data. Effectiveness degrades when the input does not contain too many equal
values. For example, if we apply run length coding directly to the original
image block, say, Fig. 2.6(c), the result will then be disastrous as we would
actually expand the data instead of compressing it.
2.2.7 Variable Length Coding in Image and Video Coding
After the run length coding, we have many different pairs of (
Length
,
Run
),
and the occurrences of these run length pairs are not the same. Typically the
simpler pairs, such as (0, 1), (0,−1), (1, 1) and (1,−1), appear much often than
the others such as (0,−18). Therefore these run length pairs can be effectively
compressed by entropy coding, such as Huffman coding or arithmetic coding,
as we have explained in Section 2.2.2 and Section 2.2.3.
As we have mentioned previously, arithmetic coding is superior to Huff-
man coding in terms of speed and e
ciency. Unfortunately it is patented and
hence has restrictions on its use. Arithmetic coding partly gains its superior-
ity by being adaptive, i.e. being able to produce probability estimates on
the fly. Huffman coding on the other hand is simpler and requires a set of
