Rate-distortion optimized coding mode selection for video coders

• US 6,167,162 A
• Filed: 10/04/1999
• Issued: 12/26/2000
• Est. Priority Date: 10/23/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Yang, Kyeong Ho, Jacquin, Arnaud Eric
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Wu, Jingge
• Application Number:
  US09/411,112
• Time in Patent Office: 449 Days
• Field of Search: 382/251, 382/250, 382/232, 382/253, 348/405, 348/406, 348/407, 341/200, 375/240, 375/245, 342/197
• US Class Current: 382/251
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: H04N 19/109 among a plurality of temporal predictive coding modes
• CPC Class Codes: H04N 19/11 among a plurality of spatial predictive coding modes
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers

Abstract

A new method for real time implementation of rate-distortion optimized coding mode selection is disclosed that can be efficiently applied to H-263-compatible video codecs and other codecs of similar type. A normalized rate-distortion model is used to efficiently compute the rate and the distortion when encoding motion-compensated prediction error signals, instead of performing DCT, quantization and entropy-encoding. A fast algorithm is also disclosed that determines sub-optimal values of coding parameters such as the quantization parameter and the Lagrangian multiplier, λ, for the trellis search. Very good rate control and picture quality are achieved, especially when the disclosed techniques are applied in very low bitrate video coding.

Claims

1. In a coder for coding frames of input video information, each frame comprising an ordered plurality, i=1, 2, . . . , n, of slices, each slice comprising an ordered sequence j=1, 2, . . . , m of macroblocks, each macroblock comprising a plurality of input signal values, the coder having a plurality of modes for coding macroblocks, a method for selecting a coding mode, M_i,j for the jth macroblock in the ith slice, the method comprising

determining values for a cost function, J_i,j, a quantizing parameter QP and a Langrangian multipliers λ

, where J_i,j (.)=D_i,j (.)+λ

R_i,j (.), D_i,j is the distortion for the jth macroblock in the with strip, and R_i,j is the rate for coding the jth macroblock in the with strip, and

determining a set of coding modes for each macroblock that satisfy ##EQU3##

2. The method of claim 1 wherein said rates and distortions are determined using a normalized rate-distortion model.

3. The method of claim 2 wherein said macroblocks are characterized by the variance of input values in respective macroblocks.

4. The method of claim 2 wherein said macroblocks are characterized by the mean of input values in respective macroblocks.

5. The method of claim 2 wherein said rates and distortions determined using said normalized rate-distortion model are obtained from values stored in a memory.

6. The method of claim 2 wherein said minimums are determined using a trellis search.

7. The method of claim 6 wherein said minimums for QP and λ

are determined by an exhaustive trellis search using values for said cost function determined using said normalized rate-distortion model.

8. The method of claim 6 wherein said minimums for QP and λ

are approximated using a suboptimal search method.

9. The method of claim 8 wherein said suboptimal search method comprises determining the relationships where a, b, α

, and β

are model parameters which are computed in the coding mode optimization process.

10. The method of claim 9 wherein c and γ

are set to 1.0 and 0.7, respectively.

11. The method of claim 1 where said minimums are achieved approximately, using a suboptimal method, the suboptimal method comprising

A. determining the target number of bits, R_T for encoding the n^th frame X(_n), which is a function of the buffer fullness.

B. determining a suboptimal QP by performing the method comprising

(i) setting λ

=λ

_overall and and QP=QP₀ =QP.sub.(n-), where λ

_overall is the average of λ

s over the previous 10 frames and QP.sub.(n-) is QP for the previous frame;

(ii) performing coding mode optimization with (QP₀, λ

_overall) to obtain the corresponding overall distortion D₀ and the required number of bits R₀ ;

(iii) If R₀ <

R_T, set QP₁ =QP₀ -δ

, otherwise set QP₁ =QP₀ +δ

, where δ

is a non-negative small integer;

(iv) determine D₁ and R₁ with QP=QP₁ ;

(v) model the R-QP curve by calculating a and b in

from (QP₀, R₀) and (QP₁, R₁);

##EQU4## (vi) using said model, calculate the suboptimal QP* corresponding to R_T ;

C. model the R-D curve in

using (D₂, R₂) obtained with (QP*,λ

_overall) to obtain a suboptimal λ

*;

##EQU5## D. performing rate-distortion coding mode optimization with (QP*, λ

*).

12. The method of claim 11 wherein c and γ

are 1.0 and 0.7, respectively.

13. In a coder for coding frames of input video information, each frame comprising an ordered plurality, i=1, 2, . . . , n, of slices, each slice comprising an ordered sequence j=1, 2, . . . , m of macroblocks, each macroblock comprising a plurality of input signal values, the coder having a plurality of modes for coding macroblocks, a system for selecting a coding mode, M_i,j for the jth macroblock in the ith slice, the system comprising

means for determining values for a cost function, J_i,j, a quantizing parameter QP and a Langrangian multiplierλ

, where J_i,j (.)=D_i,j (.)+λ

R_i,j (.), D_i,j is the distortion for the jth macroblock in the ith strip, and R_i,j is the rate for coding the jth macroblock in the ith strip, and

means for determining a set of coding modes for each macroblock that satisfy ##EQU6##

14. The system of claim 13 wherein said means for determining a set of coding modes comprises means for determining rates and distortions using a normalized rate-distortion model.

15. The system of claim 14 wherein said macroblocks are characterized by the variance of input values in respective macroblocks.

16. The system of claim 14 wherein said macroblocks are characterized by the mean of input values in respective macroblocks.

17. The system of claim 14 wherein said means for determining a set of coding modes comprises means for obtaining said rates and distortions from values stored in a memory.

18. The system of claim 14 wherein said means for determining a set of coding modes comprises means for performing a trellis search.

19. The system of claim 18 wherein said means for performing a trellis search comprises means for performing an exhaustive trellis search using values for said cost function determined using said normalized rate-distortion model.

20. The system of claim 18 wherein said means for performing a trellis search comprises means for determining minimum values for QP and λ

approximately using a suboptimal search method.

21. The system of claim 20 wherein said means for determining minimum values for QP and λ

approximately comprises means for determining the relationships where a, b, α

, and β

are model parameters which are computed by said means for determining rates and distortions using a normalized rate-distortion model.

22. The system of claim 13 wherein c and γ

are set to 1.0 and 0.7, respectively.

23. The system of claim 13 where said minimums are achieved approximately by a suboptimal search system, the suboptimal search system comprising

A. means determining the target number of bits, R_T for encoding the n^th frame X(_n), which is a function of the buffer fullness.

B. means for determining a suboptimal QP by performing the method comprising

(i) means for setting λ

=λ

_overall and QP=QP₀ =QP.sub.(n-), where λ

_overall is the average of λ

s over the previous 10 frames and QP.sub.(n-) is QP for the previous frame;

(ii) means for performing coding mode optimization with (QP₀, λ

_overall) to obtain the corresponding overall distortion D₀ and the required number of bits R₀ ;

(iii) means for setting QP₁ =QP₀ -δ

if R₀ <

R_T, and otherwise setting QP₁ =QP₀ +δ

, where δ

is a non-negative small integer;

(iv) means for determing D₁ and R₁ with QP=QP₁ ;

(v) modeling the R-QP curve by calculating a and b in ##EQU7## from (QP₀, R₀) and (QP₁, R₁);

(vi) means for calculating the suboptimal QP* corresponding to R_T using said model,

C. means for modeling the R-D curve in ##EQU8## using (D₂, R₂) obtained with (QP*,λ

_overall), to obtain a suboptimal λ

*;

D. means for performing rate-distortion coding mode optimization with (QP*, λ

*).

24. The system of claim 23 wherein c and γ

are 1.0 and 0.7, respectively.