Rate-distortion optimized coding mode selection for video coders

Claim 2

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##

Claim 3

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

Claim 4

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

Claim 5

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

Claim 6

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.

Claim 7

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

Claim 8

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.

Claim 9

The method of claim 6 wherein said minimums for QP and λ are approximated using a suboptimal search method.

Claim 10

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.

Claim 11

The method of claim 9 wherein c and γ are set to 1.0 and 0.7, respectively.

Claim 12

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 0 =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 0 , λ overall ) to obtain the corresponding overall distortion D 0 and the required number of bits R 0 ; (iii) If R 0 <R T , set QP 1 =QP 0 -δ, otherwise set QP 1 =QP 0 +δ, where δ is a non-negative small integer; (iv) determine D 1 and R 1 with QP=QP 1 ; (v) model the R-QP curve by calculating a and b in from (QP 0 , R 0 ) and (QP 1 , R 1 ); ##EQU4## (vi) using said model, calculate the suboptimal QP* corresponding to R T ; C. model the R-D curve in using (D 2 , R 2 ) obtained with (QP*,λ overall ) to obtain a suboptimal λ*; ##EQU5## D. performing rate-distortion coding mode optimization with (QP*, λ*).

Claim 13

The method of claim 11 wherein c and γ are 1.0 and 0.7, respectively.

Claim 14

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##

Claim 15

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##

Claim 16

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.

Claim 17

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

Claim 18

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

Claim 19

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.

Claim 20

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

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

The system of claim 13 wherein c and γ are set to 1.0 and 0.7, respectively.

Claim 25

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 0 =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 0 , λ overall ) to obtain the corresponding overall distortion D 0 and the required number of bits R 0 ; (iii) means for setting QP 1 =QP 0 -δ if R 0 <R T , and otherwise setting QP 1 =QP 0 +δ, where δ is a non-negative small integer; (iv) means for determing D 1 and R 1 with QP=QP 1 ; (v) modeling the R-QP curve by calculating a and b in ##EQU7## from (QP 0 , R 0 ) and (QP 1 , R 1 ); (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 2 , R 2 ) obtained with (QP*,λ overall ), to obtain a suboptimal λ*; D. means for performing rate-distortion coding mode optimization with (QP*, λ*).

Claim 26

The system of claim 23 wherein c and γ are 1.0 and 0.7, respectively.