Soft decision and iterative video coding for MPEG and H.264
View Patent ↗A method of encoding video data using soft decision quantization makes use of iterative encoding to provide the ability to optimize encoding across different functional elements in a hybrid video encoder. Iterative encoding is used to allow quantization step size, motion prediction and quantization levels to be optimized despite their interrelated nature.
1. A method of encoding a digitized video frame comprising:
receiving the digitized video frame via a receiver;
applying a motion compensation and a transform to the digitized video frame to obtain a transformed residual;
applying a soft decision quantization to the transformed residual to obtain quantized transform coefficients;
wherein applying the soft decision quantization includes computing a block of quantized transform coefficients, u, for each block in the plurality as
u
=
arg
min
u
c
-
u
⊗
dq
[
p
r
em
]
·
2
p
quo
/
64
⊗
B
2
+
λ
·
r
(
u
)
;
and
entropy encoding the quantized transform coefficients along with the motion compensation,
wherein c is the transformed residual,
dq[p rem ]·2 P quo /64{circle around (×)}B|
is a dequantization calculation, λ is a Lagrangian multiplier, and r(u) is a number of bits for coding u.
2. The method of claim 1 wherein the encoded video frame is either a H.264 frame or a MPEG frame.
3. The method of claim 1 wherein the soft decision quantization is designed for symbiotic co-operation with the method of entropy coding employed in entropy coding the soft decision quantized transform coefficients.
4. The method of claim 1 wherein applying the soft decision quantization includes computing the quantized transform coefficients, U, as
U
=
arg
min
U
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
U
)
,
where q is a quantization step size, d(•,•)represents the distortion between the residual frame and the quantized residual frame determined from U and quantization step sizes, and r(U) is the number of bits needed for the method of entropy coding to encode U.
5. The method of claim 1 wherein applying the soft decision quantization includes:
applying a soft decision quantization, based on a predetermined motion prediction, to the transformed residual to obtain quantized transform coefficients, the applied soft decision quantization having predetermined quantization step sizes;
computing updated quantization step sizes in accordance with the quantized transform coefficients; and
iteratively obtaining new quantized transform coefficients using the computed quantization step sizes, and computing the updated quantization step sizes in accordance until a rate distortion cost associated with the quantized transform coefficients and quantization step sizes is less than a predetermined threshold.
6. The method of claim 5 wherein applying the soft decision quantization includes computing the quantized transform coefficients, U, as
U
=
arg
min
U
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
U
)
,
where q is a quantization step size, d(•,•) represents the distortion between the residual frame and the quantized residual frame determined from U and quantization step sizes, and r(U) is the number of bits needed for the method of entropy coding to encode U.
7. The method of claim 5 wherein iteratively obtaining new quantized transform coefficients, U, and computing the updated quantization step sizes, q, involve determining the set
{
q
,
U
}
as
{
q
,
U
}
=
arg
min
q
,
U
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
(
r
(
U
)
+
r
(
q
)
)
,
where r(q) is the number of bits needed for the method of entropy coding to encode q.
8. The method of claim 5 wherein computing updated quantization step sizes, q, in accordance with the quantized transform coefficients U includes determining q as
q
=
arg
min
q
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
q
)
.
9. The method of claim 8 wherein determining q includes using a Viterbi search to traverse a trellis representing the quantization step sizes of the solution space of q and the corresponding rate distortion cost of each state transition.
10. The method of claim 1 further including determining a motion prediction in accordance with the quantized residual determined from the quantized transformed residual, which in turn is determined from quantized transform coefficients and quantization step sizes.
11. The method of claim 10 wherein determining the motion prediction, {m,V} includes computing
{
m
,
V
}
=
arg
min
m
,
V
∑
k
=
1
16
K
d
(
X
-
P
(
m
,
V
)
,
Z
^
)
+
λ
·
(
r
(
V
)
+
r
(
m
)
)
where {circumflex over (Z)} represents a reconstruction of the quantized residual, X-P(m, V) is the residual resulting from the prediction P(m, V), and r(m) and r(V) represents the number of bits needed for the method of entropy coding to encode the prediction P(m, V).
12. The method of claim 10 further including
obtaining a new residual using the determined motion prediction and applying the transform to the new residual to obtain an updated transformed residual;
applying the soft decision quantization to the updated transformed residual in accordance with the determined motion prediction to obtain an updated quantized residual;
updating the motion prediction in accordance with the updated quantized residual; and
repeating the steps of obtaining a new residual, applying the soft decision quantization to the updated transformed residual and updating the motion prediction until a rate distortion cost associated with the motion compensation and updated quantized residual is smaller than a predetermined rate distortion threshold.
13. The method of claim 12 wherein applying the soft decision quantization includes obtaining updated quantized transform coefficients U as
U
=
arg
min
U
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
U
)
,
where q is a quantization step size, d(•,•)represents the distortion between the residual frame and the updated quantized residual frame determined from U and quantization step sizes, and r(U) is the number of bits needed for the method of entropy coding to encode U.
14. The method of claim 13 wherein obtaining updated U is followed by the steps of:
determining new quantization step sizes in accordance with U; and
iteratively repeating the steps of obtaining U and determining new quantization step sizes until a rate distortion cost associated with the quantized residual is below a predetermined threshold.
15. The method of claim 14 wherein determining new quantization step sizes includes calculating the step size, q, as
q
=
arg
min
q
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
q
)
,
where U is the newly updated quantized transform coefficients.
16. The method of claim 12 wherein updating the motion prediction, {m,V} includes computing
{
m
,
V
}
=
arg
min
m
,
V
∑
k
=
1
16
K
d
(
X
-
P
(
m
,
V
)
,
Z
^
)
+
λ
·
(
r
(
V
)
+
r
(
m
)
)
where {circumflex over (Z)} represents the newly updated quantized residual.
17. The method of claim 1 wherein applying a soft decision quantization includes:
dividing the transformed residual into a plurality of distinct blocks;
computing soft decision quantized transform coefficients for each of the plurality of distinct blocks; and
combining the quantized transform coefficients of each of the plurality of blocks to obtain quantized transform coefficients for the entire transformed residual.
18. The method of claim 1 wherein computing the block of quantized transform coefficients comprises:
constructing a graph having paths from a start node to an end node, the paths representing all possible quantized transform coefficients for the given transformed residual, each path having a cost defined as the sum of all costs allocated to all branch transitions from one state to another along the path, the cost being equal to the rate distortion cost of the corresponding block of quantized transform coefficients u calculated as
∥ c−u{circle around (×)}dq[p rem ]·2 p quo /64{circle around (×)} B∥ 2 +λ·r ( u );
traversing the path in the graph leading from the start node to the end node having the minimum associated cost; and
determining the quantized transform coefficients associated with the traversed path.
19. The method of claim 18 wherein nodes in the graph are connected to neighboring nodes as determined by characteristics of the method of entropy coding applied in the step of entropy coding the soft decision quantized transformed coefficients.
20. The method of claim 19 where the step of traversing the path includes using dynamic programming to find the path in the graph leading from the start node to the end node having the minimum associated cost.
21. The method of claim 19 wherein nodes are connected to neighboring nodes by branches, each branch having a weight determined in accordance with characteristics of the method of entropy coding applied in the step of entropy coding the soft decision quantized transformed coefficients.
22. The method of claim 1 wherein the entropy coding comprises an adaptive context model.
23. The method of claim 1 wherein the entropy coding is one of CALVC and CABAC.
24. An apparatus for encoding a digitized video frame comprising:
an encoder for receiving the digitized video frame;
a motion compensator for applying a motion compensation to the digitized video frame to obtain a residual;
a transform processor for applying a transform to the residual to obtain a transformed residual;
a soft quantization processor for applying a soft decision quantization to the transformed residual to obtain quantized transform coefficients;
wherein the soft quantization processor computes the soft decision quantized transform coefficients including computing a block of quantized transform coefficients, u, for each block in the plurality as
u
=
arg
min
u
c
-
u
⊗
dp
[
p
rem
]
·
2
p
quo
/
64
⊗
B
2
+
λ
·
r
(
u
)
;
and
an entropy encoder for encoding the quantized transform coefficients and quantization step sizes along with motion prediction,
wherein c is the transformed residual,
dq[p rem ]·2 P quo /64{circle around (×)}B|
is a dequantization calculation, λ is a Lagrangian multiplier, and r(u) is a number of bits for coding u.
25. The apparatus of claim 24 wherein when the soft quantization processor applies the soft decision quantization, the soft quantization processor further computes the quantized transform coefficients, U, as
U
=
arg
min
U
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
U
)
,
where q is a quantization step size, d(•,•)represents the distortion between the residual frame and the quantized residual frame determined from U and quantization step sizes, and r(U) is the number of bits needed for the method of entropy coding to encode U.
26. The apparatus of claim 24 wherein the motion compensator and soft quantization processor interact to determine a motion prediction in accordance with the quantized residual determined from the quantized transformed residual, which in turn is determined from quantized transform coefficients and quantization step sizes.
27. The apparatus of claim 24 wherein the entropy encoder encodes in one of CALVC and CABAC.
28. The apparatus of claim 24 wherein the encoded video frame is either a H.264 frame or a MPEG frame.