Image Processing Reference
In-Depth Information
p is integer, tillk<N.Inordertousesymmetry of trigonometric functions in a maximal way,
N should be a power of 2, similarly to Radix-2 approach used in FFT algorithm. IfN=2q,
recurrent minimization is possible till p = q. The twiddle factors for successive minimization
steps m equal to
cos
2
2
q
2
p
+
m
2
1 , because the sum of step index m and range factor p
is constant and equals to q. For the rest of indices twiddle factor depends on fractional angle
α
=
π
2
q
−
m
−
1
=
−
N
.
After the 1st step of minimization, the terms of the sum (13) for odd indices depends only on
the odd multiplicity of the fractional angle
N
2
−
A
n
cos
2
N
(
k
1
∑
X
k
=
α
k
2
n
+
1
)
(14)
=
−
n
N
1
Using a following trigonometric identity
1
2
cos
α
=
β
(
(
α
+
β
)+
(
α − β
))
cos
cos
cos
(15)
π
2
N
. Thus:
k
β
=
the fractional angles can be increased by the factor of 2 for
cos
k
cos
k
N
n
N
/2
∑
α
k
2
cos
k
π
N
(
X
k
=
2
N
×
+
)
+
A
n
n
1
(16)
n
=
N
−
1
Let us notice that:
1).
cos
k
, for n = N-1, hence pure
A
n
coefficient survives,
(
k
π
)=(
−
1
)
2
because of odd k,
3). the rest of indices appear in cosine terms twice in
A
n
+
1
and
A
n
coefficients, which allows
introducing the new set of variables
k
2
2).
cos
(
)=
0, for
n
=
B
N
−
1
=
A
N
−
1
B
N
−
1
−
n
=
A
N
−
n
+
A
N
−
1
−
n
(17)
The range of
B
n
indices is continuous and can be split again on even and odd parts. The above
procedure can be repeated in recurrence.
5. 8-point DCT algorithm
ForN=8according to formulae (12) and (17) we get :
A
0,1,2,3
=
x
0,1,2,3
+
A
7,6,5,4
=
x
0,1,2,3
−
x
7,6,5,4
x
7,6,5,4
(18)
=
+
=
−
=
+
=
B
0,1
A
0,1
A
3,2
B
2,3
A
0,1
A
3,2
B
6,5,4
A
7,6,5
A
6,5,4
B
7
A
7
(19)
For even indices the DCT coefficients are expressed as follows:
2
√
2
X
0
11
1
1
B
0
4
S
2
X
2
S
4
11
1
B
3
=
=
B
3
+
(20)
X
4
S
6
X
6
−
B
1
−
1
−
B
2
where
cos
k
16
S
k
=
(21)
