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 video frame comprising:
applying a transform to the video frame to obtain transform coefficients;
iteratively determining quantized transform coefficients for the transform coefficients by assuming a fixed prediction,
applying a soft decision quantization, using the fixed prediction, for fixed quantization step sizes to the transform coefficients to obtain quantized transform coefficients,
updating the quantization step sizes using the quantized transform coefficients, and
repeating the applying the soft decision quantization for the updated step sizes and the updating the step sizes, until a rate distortion cost associated with the quantized transform coefficients and quantization step sizes is below a predefined threshold;
determining a motion compensation in accordance with the iteratively determined quantized transform coefficients and quantization step sizes; and
entropy encoding the iteratively quantized transform coefficients and quantization step sizes,
wherein the determining a motion compensation includes
computing a motion prediction in accordance with a quantized residual frame determined from the iteratively determined quantized transform coefficients and quantization step sizes,
iteratively applying the soft decision quantization using the computed motion prediction and updating the step sizes, until a rate distortion cost associated with the quantized transform coefficients encoding is below a predetermined threshold, and
repeating the computing the motion prediction and the iteratively applying the soft decision quantization and updating the step size, until an actual rate distortion cost associated with the motion prediction and encoded quantized transform coefficients is below a predetermined rate distortion cost threshold.
2. A method of encoding a video frame comprising:
applying a transform to the video frame to obtain transform coefficients;
applying a soft decision quantization to the transform coefficients to obtain quantized transformed coefficients; and
entropy coding the soft decision quantized transformed coefficients,
wherein the applying the soft decision quantization includes:
applying a soft decision quantization, based on a predetermined motion prediction, to the transform coefficients to obtain the 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.
3. The method of claim 2 wherein the soft decision quantization is designed for symbiotic co-operation with the method of entropy coding employed in the entropy coding the soft decision quantized transformed coefficients.
4. The method of claim 2 wherein the 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 2 wherein the iteratively obtaining new quantized transform coefficients, U, and the 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.
6. The method of claim 2 wherein the 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
)
.
7. The method of claim 6 wherein the 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.
8. A method of encoding a video frame comprising:
applying a transform to the video frame to obtain transform coefficients;
applying a soft decision quantization to the transform coefficients to obtain quantized transformed coefficients, by
dividing the transform coefficients 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 the quantized transform coefficients;
determining a motion prediction in accordance with a quantized residually determining a quantized transformed residual from the quantized transform coefficients and quantization step sizes and determining the quantized residual from the quantized transformed residual; and
entropy coding the soft decision quantized transformed coefficients.
9. The method of claim 8 wherein the 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).
10. The method of claim 8 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 obtaining a new residual, the applying the soft decision quantization to the updated transformed residual and the 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.
11. The method of claim 10 wherein the 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.
12. The method of claim 11 wherein the obtaining updated U is followed by:
determining new quantization step sizes in accordance with U; and
iteratively repeating the obtaining U and the determining new quantization step sizes, until a rate distortion cost associated with the quantized residual is below a predetermined threshold.
13. The method of claim 12 wherein the 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.
14. The method of claim 10 wherein the 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.
15. A method of encoding a video frame comprising:
applying a transform to the video frame to obtain transform coefficients;
applying a soft decision quantization to the transform coefficients to obtain quantized transformed coefficients; and
entropy coding the soft decision quantized transformed coefficients
wherein the applying a soft decision quantization includes
dividing the transform coefficients 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 the quantized transform coefficients for the entire frame.
16. The method of claim 15 wherein the computing the soft decision quantized transform coefficients includes computing a block of quantized transform coefficients, u, for each block in the plurality as
u
=
arg
min
u
c
-
u
⊗
d
q
[
p
rem
]
·
2
p
quo
/
64
)
⊗
B
2
+
λ
·
r
(
u
)
.
17. The method of claim 16 wherein the computing the block of quantized transform coefficients includes
constructing a graph having paths from a start node to an end node, the paths representing all possible blocks of quantized transform coefficients for the frame, 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 (x)}dq[p rem ]·2 p quo /64) {circle around (x)}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.
18. The method of claim 17 wherein nodes in the graph are connected to neighboring nodes as determined by characteristics of the method of entropy coding applied in the entropy coding the soft decision quantized transform coefficients.
19. The method of claim 17 where the 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.
20. The method of claim 18 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 entropy coding the soft decision quantized transform coefficients.
21. The method of claim 18 wherein the method of entropy coding is context adaptive variable length coding.
22. A method of encoding a video frame comprising:
applying a transform to the video frame to obtain transform coefficients;
iteratively applying a soft decision quantization, having defined quantization step sizes, to the transform coefficients to obtain quantized transform coefficients, and updating the defined quantization step sizes in accordance with the quantized transform coefficients until a rate distortion cost associated with the iteratively quantized transform coefficients and quantization step sizes is below a threshold;
iteratively determining a motion prediction based on an iteratively quantized residual determined from the iteratively quantized transform coefficients and quantization step sizes, applying the motion prediction and the transform to the original video frame to obtain an updated transformed residual and iteratively applying the soft decision quantization to the updated transformed residual and updating defined quantization step sizes in accordance with the determined motion compensation, until a rate distortion cost associated with the quantized residual and motion prediction is below a threshold; and
entropy coding the quantized residual along with the determined motion compensation,
wherein the 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.
23. The method of claim 22 wherein the soft decision quantization is designed for symbiotic co-operation with the method of entropy coding employed in the entropy coding the quantized residual.
24. The method of claim 22 wherein the updating the quantization step sizes computes new quantization step sizes q as
q
=
arg
min
q
∑
k
=
1
16
K
d
(
z
k
,
T
-
1
(
u
k
·
q
⌈
k
/
16
⌉
)
)
+
λ
·
r
(
q
)
.
25. The method of claim 22 wherein the 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
)
)
.
26. A method of encoding a video frame comprising:
applying a transform to the video frame to obtain transform coefficients;
iteratively determining quantized transform coefficients for the transform coefficients by assuming a fixed prediction,
applying a soft decision quantization, using the fixed prediction, for fixed quantization step sizes to the transform coefficients to obtain quantized transform coefficients,
updating the quantization step sizes using the quantized transform coefficients, and
repeating the applying the soft decision quantization for the updated step sizes and the updating the step sizes, until a rate distortion cost associated with the quantized transform coefficients and quantization step sizes is below a predefined threshold; and
entropy encoding the iteratively quantized transform coefficients and quantization step sizes,
wherein the applying a soft decision quantization includes
dividing the transform coefficients 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 the quantized transform coefficients for the entire frame.
27. The method of claim 26 wherein the computing the soft decision quantized transform coefficients includes computing a block of quantized transform coefficients, u, for each block in the plurality as
u
=
arg
min
u
c
-
u
⊗
dq
[
p
rem
]
·
2
p
quo
/
64
)
⊗
B
2
+
λ
·
r
(
u
)
.
28. The method of claim 27 wherein the computing the block of quantized transform coefficients includes
constructing a graph having paths from a start node to an end node, the paths representing all possible blocks of quantized transform coefficients for the frame, 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 (x)}dq[p rem ]·2 p quo /64) {circle around (x)}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.
29. The method of claim 28 wherein nodes in the graph are connected to neighboring nodes as determined by characteristics of the method of entropy coding applied in entropy coding the soft decision quantized transform coefficients.
30. The method of claim 28 where the 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.
31. The method of claim 29 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 entropy coding the soft decision quantized transform coefficients.
32. The method of claim 29 wherein the method of entropy coding is context adaptive variable length coding.
33. The method claimed in claim 2 , wherein entropy coding comprises applying a context-adaptive entropy coder, and wherein applying a soft decision quantization comprises:
constructing a graph representing a plurality of sequences of quantized transform coefficients for the transform coefficients; and
selecting in said graph a sequence of quantized transform coefficients that has a minimum rate-distortion cost, wherein the rate-distortion cost includes a rate cost based upon the context-adaptive entropy coder.
34. The method claimed in claim 33 , wherein each node of said graph comprises a respective context state of said context-adaptive entropy coder.
35. The method claimed in claim 34 , wherein each transition between a pair of said nodes represents a particular quantized transform coefficient.
36. The method claimed in claim 8 , wherein entropy coding comprises applying a context-adaptive entropy coder, and wherein applying a soft decision quantization comprises:
constructing a graph representing a plurality of sequences of quantized transform coefficients for the transform coefficients; and
selecting in said graph a sequence of quantized transform coefficients that has a minimum rate-distortion cost, wherein the rate-distortion cost includes a rate cost based upon the context-adaptive entropy coder.
37. The method claimed in claim 36 , wherein each node of said graph comprises a respective context state of said context-adaptive entropy coder.
38. The method claimed in claim 37 , wherein each transition between a pair of said nodes represents a particular quantized transform coefficient.
39. The method claimed in claim 15 , wherein entropy coding comprises applying a context-adaptive entropy coder, and wherein applying a soft decision quantization comprises:
constructing a graph representing a plurality of sequences of quantized transform coefficients for the transform coefficients; and
selecting in said graph a sequence of quantized transform coefficients that has a minimum rate-distortion cost, wherein the rate-distortion cost includes a rate cost based upon the context-adaptive entropy coder.
40. The method claimed in claim 39 , wherein each node of said graph comprises a respective context state of said context-adaptive entropy coder.
41. The method claimed in claim 40 , wherein each transition between a pair of said nodes represents a particular quantized transform coefficient.