Level decision in rate distortion optimized quantization

Abstract

A computing device, such as a video encoder, determines an initial quantized level for a coefficient of a coefficient block and determines whether the coefficient is less than the product of the initial quantized level and a quantization step size value. In response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value, the computing device determines rate-distortion costs of quantizing the coefficient to be the initial quantized level for the coefficient, the initial quantized level minus one, and in some circumstances, 0. The computing device determines an actual quantized level for the coefficient based at least in part on the calculated rate-distortion costs and includes the actual quantized level in a quantized version of the coefficient block.

What is claimed is:  
     
       1. A method of encoding video data, the method comprising:
 determining an initial quantized level for a coefficient of a coefficient block; 
 determining whether the coefficient is less than the product of the initial quantized level and a quantization step size value; and 
 in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value:
 determining rate-distortion costs of quantizing the coefficient to be the initial quantized level and the initial quantized level minus one; and 
 determining an actual quantized level for the coefficient based at least in part on the determined rate-distortion costs. 
 
 
     
     
       2. The method of  claim 1 , further comprising determining, without determining the rate-distortion costs and in response to determining that the coefficient is not less than the product of the initial quantized level and the quantization step size value, that the actual quantized level for the coefficient is the initial quantized level for the coefficient. 
     
     
       3. The method of  claim 1 , further comprising: in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value:
 determining, in response to determining that the initial quantized level is less than three, the rate-distortion costs of quantizing the coefficient to be the initial quantized level for the coefficient, the initial quantized level minus one, and zero; and 
 determining, in response to determining that the initial quantized level is greater than or equal to three, the rate-distortion costs of quantizing the coefficient to be the initial quantized level and the initial quantized level minus one. 
 
     
     
       4. The method of  claim 1 , wherein the coefficient occurs after a first non-zero coefficient in a reverse scan order in the coefficient block. 
     
     
       5. The method of  claim 1 , further comprising determining a last significant coefficient, the last significant coefficient being the first non-zero coefficient of the coefficient block in a reverse scan order. 
     
     
       6. The method of  claim 1 , further comprising:
 entropy encoding the actual quantized level; and 
 outputting a bitstream that includes the entropy-encoded actual quantized level. 
 
     
     
       7. The method of  claim 1 , wherein determining the actual quantized level comprises selecting an actual quantized level that produces a lowest rate-distortion cost. 
     
     
       8. The method of  claim 7 , further comprising generating a reconstructed value of the coefficient by multiplying the actual quantized level by the quantization step size value. 
     
     
       9. The method of  claim 1 , wherein determining the initial quantized level for the coefficient comprises calculating 
       
         
           
             
               z 
               = 
               
                 
                   ⌊ 
                   
                     
                       
                          
                         w 
                          
                       
                       + 
                       f 
                     
                     Δ 
                   
                   ⌋ 
                 
                 · 
                 
                   sign 
                   ⁡ 
                   
                     ( 
                     W 
                     ) 
                   
                 
               
             
           
         
       
       where z is the initial quantized level for the coefficient, W is an initial value of the coefficient, f is a quantization offset for the coefficient, Δ is the quantization step size value, └·┘ denotes rounding to the nearest integer towards minus infinity and sign( ) is a function that returns the sign of the initial value of the coefficient. 
     
     
       10. The method of  claim 1 , wherein:
 the method further comprises:
 determining, based at least in part on entropies of context models of a previous frame, rate values for the context models; and 
 generating a table that indicates, for each of the context models, a value of λ multiplied by the rate value for the context model, where λ is a fixed value; and 
 
 wherein determining the rate-distortion costs comprises determining, based at least in part on the values in the table, the rate-distortion costs of quantizing the coefficient to be the initial quantized level for the coefficient, the initial quantized level minus one, and zero. 
 
     
     
       11. A computing device that encodes video data, the computing device comprising:
 a data storage medium configured to store encoded video data; and 
 one or more processors, coupled to the data storage medium, that are configured to:
 determine an initial quantized level for a coefficient of a coefficient block; 
 determine whether the coefficient is less than the product of the initial quantized level and a quantization step size value; and 
 in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value:
 determine rate-distortion costs of quantizing the coefficient to be the initial quantized level and the initial quantized level minus one; and 
 determine an actual quantized level for the coefficient based on the determined rate-distortion costs. 
 
 
 
     
     
       12. The computing device of  claim 11 , wherein the one or more processors are further configured to determine, without determining the rate-distortion costs and in response to determining that the coefficient is not less than the product of the initial quantized level and the quantization step size value, that the actual quantized level for the coefficient is the initial quantized level for the coefficient. 
     
     
       13. The computing device of  claim 11 , wherein the one or more processors are configured to:
 in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value:
 determine, in response to determining that the initial quantized level is less than three, the rate-distortion costs of quantizing the coefficient to be the initial quantized level for the coefficient, the initial quantized level minus one, and zero; and 
 determine, in response to determining that the initial quantized level is greater than or equal to three, the rate-distortion costs of quantizing the coefficient to be the initial quantized level and the initial quantized level minus one. 
 
 
     
     
       14. The computing device of  claim 11 , wherein the coefficient occurs after a first non-zero coefficient in a reverse scan order in the coefficient block. 
     
     
       15. The computing device of  claim 11 , wherein the one or more processors are further configured to determine a last significant coefficient, the last significant coefficient being the first non-zero coefficient in a reverse scan order. 
     
     
       16. The computing device of  claim 11 , wherein the one or more processors are further configured to:
 entropy encode the actual quantized level; and 
 output a bitstream that includes the entropy-encoded actual quantized level. 
 
     
     
       17. The computing device of  claim 11 , wherein the one or more processors are configured to determine the actual quantized level at least in part by selecting an actual quantized level that produces a lowest rate-distortion cost. 
     
     
       18. The computing device of  claim 17 , wherein the one or more processors are further configured to generate a reconstructed value of the coefficient by multiplying the actual quantized level by the quantization step size value. 
     
     
       19. The computing device of  claim 11 , wherein the one or more processors are configured to determine the initial quantized level for the coefficient by calculating 
       
         
           
             
               z 
               = 
               
                 
                   ⌊ 
                   
                     
                       
                          
                         w 
                          
                       
                       + 
                       f 
                     
                     Δ 
                   
                   ⌋ 
                 
                 · 
                 
                   sign 
                   ⁡ 
                   
                     ( 
                     W 
                     ) 
                   
                 
               
             
           
         
       
       where z is the initial quantized level for the coefficient, W is an initial value of the coefficient, f is a quantization offset for the coefficient, Δ is the quantization step size value, └·┘ denotes rounding to the nearest integer towards minus infinity and sign( ) is a function that returns the sign of the initial value of the coefficient. 
     
     
       20. The computing device of  claim 11 , wherein the one or more processors are configured to:
 determine, based at least in part on entropies of context models of a previous frame, rate values for the context models; 
 generate a table that indicates, for each of the context models, a value of λ multiplied by the rate value for the context model, where λ is a fixed value; and 
 determine, based at least in part on the values in the table, the rate-distortion costs of quantizing the coefficient to be the initial quantized level for the coefficient, the initial quantized level minus one, and zero. 
 
     
     
       21. A computing device comprising:
 means for determining an initial quantized level for a coefficient of a coefficient block; 
 means for determining whether the coefficient is less than the product of the initial quantized level and a quantization step size value; 
 means for determining, in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value, rate-distortion costs of quantizing the coefficient to be the initial quantized level and the initial quantized level minus one; and 
 means for determining, in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value, an actual quantized level for the coefficient based on the determined rate-distortion costs. 
 
     
     
       22. A non-transitory computer-readable storage medium that stores instructions that, when executed by one or more processors of a computing device, configure the computing device to:
 determine an initial quantized level for a coefficient of a coefficient block; 
 determine whether the coefficient is less than the product of the initial quantized level and a quantization step size value; and 
 in response to determining that the coefficient is less than the product of the initial quantized level and the quantization step size value:
 determine rate-distortion costs of quantizing the coefficient to be the initial quantized level and the initial quantized level minus one; and 
 determine an actual quantized level for the coefficient based on the determined rate-distortion costs.