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 for obtaining an optimal sequence of quantized coefficients for a block of transform residuals from a video, for encoding the video in a video encoder, the method comprising:
constructing a graph representing a plurality of sequences of quantized coefficients for the block of transform residuals, wherein each node in the graph includes a rate cost determined from a context in a context-adaptive entropy encoder; and
selecting in said graph a sequence of quantized coefficients that has a minimum rate-distortion cost, wherein rate-distortion cost is based on distortion cost and rate cost, and wherein rate cost is based on the context-adaptive entropy encoder, wherein the context-adaptive entropy encoder defines a plurality of contexts, and wherein entropy encoding of an element of a quantized coefficient is dependent upon selection of one of the contexts for that element.
2. The method of claim 1 , wherein rate-distortion cost is a linear sum of distortion cost and rate cost.
3. The method of claim 2 , wherein distortion cost for each sequence of quantized coefficients is calculated as a distortion, in the transform domain, between the block of transformed coefficients and a reconstructed block of transformed coefficients obtained from that sequence of quantized coefficients.
4. The method of claim 1 , wherein said graph comprises a plurality of nodes, including a start node and an end node; wherein each node represents a respective context state of the entropy encoder; wherein each node is connected by transitions to neighbouring nodes, based on state-transitions in the entropy encoder; and wherein each of said plurality of sequences of quantized coefficients is represented by a corresponding path in the graph from said start node to said end node.
5. The method of claim 4 , wherein a respective rate-distortion cost for each path in the graph from said start node to said end node is the sum of respective rate-distortion costs for all transitions on that path.
6. The method of claim 5 , wherein said rate-distortion for a transition from a first node to a second node is the rate-distortion due to a state-transition from a context state corresponding to said first node to a context state corresponding to said second node.
7. The method of claim 4 , wherein said selecting comprises:
traversing a path in said graph from said start node to said end node that represents said sequence that has said minimum rate-distortion cost; and
determining said optimal sequence of quantized coefficients corresponding to said traversed path.
8. The method of claim 1 , wherein said graph is a trellis.
9. The method of claim 8 , wherein said selecting comprises using a Viterbi algorithm.
10. The method of claim 9 , wherein said trellis includes parallel transitions between a pair of neighbouring nodes.
11. The method of claim 1 , wherein said entropy encoder is adapted to perform at least one of: context-adaptive binary arithmetic coding (CABAC) context-adaptive binary arithmetic coding (CABAC), context-adaptive arithmetic coding, and context-adaptive entropy coding.
12. A Apparatus for obtaining an optimal sequence of quantized coefficients for a block of transform residuals from a video, for encoding the video in a video encoder, the method comprising:
constructing a graph representing a plurality of sequences of quantized coefficients for the block of transform residuals, wherein each node in the graph includes a rate cost determined from a context in a context-adaptive entropy encoder; and
selecting in said graph a sequence of quantized coefficients that has a minimum rate-distortion cost, wherein rate-distortion cost is based on distortion cost and rate cost, and wherein rate cost is based on the context-adaptive entropy encoder, wherein the context-adaptive entropy encoder defines a plurality of contexts, and wherein entropy encoding of an element of a quantized coefficient is dependent upon selection of one of the contexts for that element.
13. The apparatus of claim 12 , wherein rate-distortion cost is a linear sum of distortion cost and rate cost.
14. The apparatus of claim 13 , wherein distortion cost for each sequence of quantized coefficients is calculated as a distortion, in the transform domain, between the block of transformed coefficients and a reconstructed block of transformed coefficients obtained from that sequence of quantized coefficients.
15. The apparatus of claim 12 , wherein said graph comprises a plurality of nodes, including a start node and an end node; wherein each node represents a respective context state of the entropy encoder; wherein each node is connected by transitions to neighbouring nodes, based on state-transitions in the entropy encoder; and wherein each of said plurality of sequences of quantized coefficients is represented by a corresponding path in the graph from said start node to said end node.
16. The apparatus of claim 15 , wherein a respective rate-distortion cost for each path in the graph from said start node to said end node is the sum of respective rate-distortion costs for all transitions on that path.
17. The apparatus of claim 16 , wherein said rate-distortion for a transition from a first node to a second node is the rate-distortion due to a state-transition from a context state corresponding to said first node to a context state corresponding to said second node.
18. The apparatus of claim 15 , wherein being configured to select comprises being configured to:
traverse a path in said graph from said start node to said end node that represents said sequence that has said minimum rate-distortion cost; and
determine said optimal sequence of quantized coefficients corresponding to said traversed path.
19. The apparatus of claim 12 , wherein said graph is a trellis.
20. The apparatus of claim 19 , wherein being configured to select comprises being configured to use a Viterbi algorithm.
21. The apparatus of claim 20 , wherein said trellis includes parallel transitions between a pair of neighbouring nodes.
22. The apparatus of claim 12 , wherein said entropy encoder is adapted to perform at least one of: context-adaptive binary arithmetic coding (CABAC) context-adaptive binary arithmetic coding (CABAC), context-adaptive arithmetic coding, and context-adaptive entropy coding.
23. A non-transitory computer-readable medium embodying computer-executable instructions for obtaining an optimal sequence of quantized coefficients for a block of transform residuals from a video, for encoding the video in a video encoder, the method comprising:
constructing a graph representing a plurality of sequences of quantized coefficients for the block of transform residuals, wherein each node in the graph includes a rate cost determined from a context in a context-adaptive entropy encoder; and
selecting in said graph a sequence of quantized coefficients that has a minimum rate-distortion cost, wherein rate-distortion cost is based on distortion cost and rate cost, and wherein rate cost is based on the context-adaptive entropy encoder,
wherein the context-adaptive entropy encoder defines a plurality of contexts, and wherein entropy encoding of an element of a quantized coefficient is dependent upon selection of one of the contexts for that element.
24. The method claimed in claim 1 , wherein constructing the graph includes, for each node, determining the context associated with the node based upon the context-adaptive entropy encoder and at least one coefficient of a previous node.
25. The method claimed in claim 1 , wherein constructing the graph includes, for each node, determining the context associated with the node based upon the context-adaptive entropy encoder and a position of a corresponding quantized coefficient in the sequence.
26. The method claimed in claim 1 , wherein constructing the graph includes, for each coefficient in the sequence, defining a plurality of nodes, each node representing a context in the context-adaptive entropy encoder, and determining a rate cost for that node using a context-dependent rate function.
27. The method claimed in claim 26 , wherein determining a rate cost for that node includes determining the context represented by that node based upon at least one previous quantized coefficient in the sequence.
28. The method claimed in claim 27 , wherein determining the context represented by that node is based, in part, upon at a position of the node in the sequence.
29. The method claimed in claim 1 , wherein the context is determined based upon a value of a preceding quantized coefficient in the sequence.
30. The method claimed in claim 1 , wherein constructing the graph includes defining transitions between nodes, and wherein each transition has an associated quantization coefficient level.