Graphics Reference
In-Depth Information
(
6.21
) resulting in a total of 28 additions. The 2D transform using Even-Odd
decomposition will require a total of 352 multiplications and 448 additions.
The computational complexity calculation for the 4-point and 8-point inverse
transform can be extended to inverse transforms of larger sizes. In general, the
resulting number of multiplications and additions (excluding the rounding opera-
tions associated with the shift operations) for the two-dimensional
N
-point inverse
transform can be shown to be
0
2
2k2
1
log
2
N
X
@
1
C
A
O
m
u
lt
D
2N
k
D
1
0
1
log
2
N
X
2
k1
2
k1
C
1
@
A
O
add
D
2N
kD1
The number of arithmetic operations for the inverse transform can be further
reduced if knowledge about zero-valued input transform coefficients is assumed. In
an HEVC decoder, this information can be obtained from the entropy decoding or
de-quantization process. For typical video content many blocks of size
N
N
will
have non-zero coefficients only in a
K
K
low frequency sub-block. For example in
[
5
] it was found that on average around 75 % of the transform blocks had non-zero
coefficients only in
K
K
low frequency sub-blocks. Computations can be saved in
two ways for such transform blocks. Figure
6.11
shows the first way. Columns that
are completely zero need not be inverse transformed. So only
K
1D IDCTs along
columns needs to be carried out. However, all
N
rows will need to be transformed
subsequently. The second way to reduce computations is by exploiting the fact that
each of the column and row IDCT is on a vector that has non-zero values only in the
first
K
locations. For example with
K
D
N
/2,
x
4
D
x
5
D
x
6
D
x
7
D
0, roughly half the
computations for the inverse transformation can be eliminated by simplifying Eqs.
(
6.19
-
6.20
)to
Even part:
2
4
3
5
2
4
3
5
z
0
z
1
z
2
z
3
d
16
d
8
x
0
x
2
d
16
d
24
D
d
24
d
16
d
8
d
16
Odd part:
2
3
2
3
z
4
z
5
z
6
z
7
d
28
d
20
x
1
x
3
4
5
4
5
d
20
d
4
D
d
12
d
28
d
4
d
12
