Abstract:
An encoding scheme dynamically adjusts a quantization rounding offset parameter used for encoding pictures according to statistics of previously encoded pictures of similar type. A look-up table can be used to store different relative quantization rounding offset parameters associated with different numbers of bits required to encode the pictures. The dynamically adjusted quantization rounding offset scheme achieves better coding performance at high bit rates. In one example, the dynamic quantization offset values are applied to a Uniform-Reconstruction-Quantizer (URQ) used for Laplacian sources.

Description:
BACKGROUND 
     Most quantization related schemes adjust quantization parameters to control picture quality and bit allocation. For example, a block based signal compression system employs quantization of codewords or transform coefficients and includes circuitry for adaptively controlling the quantization. Adaptivity of quantization may be a function of coding cost or bandwidth. Coding cost may be determined on a macroblock basis but averaged over a window of macroblocks centered on a macroblock currently being quantized. Other block or macroblock motion attributes can also be used to modify the quantizing function. However, these encoding schemes do not address the problems associated with quantization threshold or rounding. 
     For example, in existing video encoding systems, quantization offset parameters are typically pre-fixed constants, such as ½, ⅓, and ⅙, etc. In the H.264 reference software encoder, which is considered as a collection of many state-of-art video encoding tools, the relative quantization rounding offset is set to ⅓ for all Intra modes, while the rounding offset is set to ⅙ for all Inter modes. 
     These and other picture encoding schemes evaluate data quantity from stored picture data and detect inter-picture correlation. Picture data compression is then adaptively selected based upon the evaluated value of the information quantity and the inter-picture correlation information. The basic quantization step is then adaptively adjusted according to bit allocation and picture correlation. However, problems associated with quantization rounding are not taken into account. 
     The present invention addresses this and other problems associated with the prior art. 
     SUMMARY OF THE INVENTION 
     An encoding scheme dynamically adjusts a quantization rounding offset parameter used for encoding pictures according to statistics of previously encoded pictures of similar type. A look-up table can be used to store different relative quantization rounding offset parameters associated with different numbers of bits required to encode the pictures. The dynamically adjusted quantization rounding offset scheme achieves better coding performance at high bit rates. In one example, the dynamic quantization offset values are applied to a Uniform-Reconstruction-Quantizer (URQ) used for Laplacian sources. 
     The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a graph showing the relationship between an average number of bits per sample and relative quantization offset values. 
         FIG. 2  is a graph showing how the relative quantization offset values are applied to basic quantization set sizes. 
         FIG. 3  is a block diagram of an encoder that uses the relative quantization offset scheme. 
         FIG. 4  is a more detailed diagram of a predictive encoder that uses the relative quantization offset scheme. 
         FIG. 5  is a flow diagram showing in more detail one embodiment of the relative quantization offset scheme. 
         FIGS. 6 and 7  are graphs showing sample results for encoders using the relative quantization offset scheme. 
     
    
    
     DETAILED DESCRIPTION 
     A Uniform-Reconstruction-Quantizer (URQ) has been used in many compression systems. Compared to other quantizers, the advantage of URQ is its simplicity on the decoder side and negligible rate-distortion performance difference from the optimal quantizers. The H.264 encoding scheme is a typical example of a compression standard that uses URQ and is herein incorporated by reference. 
     A set of optimal relative quantization offset parameters can be identified for each reconstruction level and used to achieve improved encoding performance in the URQ. The rate-distortion performance difference between the optimal multi-adaptive offset URQ and URQ-with-single-adaptive offset is quite small for some input sources, such as Laplacian sources. Therefore, to ease computational requirements, a single relative quantization offset parameter can be applied to all quantization levels, as in the latest H.264 JM software. 
     For a typical rate-distortion constrained quantizer, the cost function is formulated as
 
Cost= D+λH    (1)
 
where D represents the distortion, H represents the entropy or number of bits per sample after quantization, and the Lagrange multiplier λ represents a relative weighting factor between the distortion and the entropy.
 
     For URQ-with-single-adaptive offset, the optimal solution is the single quantization rounding offset value that minimizes the cost function for a given quantization step size. More specifically, for Laplacian sources with variance as σ 2 =2 (without loss of generality) 
     
       
         
           
             
               
                 
                   λ 
                   = 
                   
                     ln 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       2 
                       · 
                       
                         
                           
                             
                               ( 
                               
                                 s 
                                 - 
                                 δ 
                               
                               ) 
                             
                             2 
                           
                           - 
                           
                             δ 
                             2 
                           
                         
                         s 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     and
 
 H=B ( e   −T )+ e   −T [1+ B ( e   −s )/(1− e   −s )]  (3)
 
 D= γ( T ,0)+γ( s ,δ) e   −T /(1 −e   −s )   (4)
 
     where s represents the quantization step size and
 
 B ( p )=− p log 2 ( p )−(1 −p )log 2 (1 −p )   (5)
 
γ( a,b )=( b   2 −2 b +2)(1 −e   −a )− ae   −a ( a −2 b +2)   (6)
 
 T =2( s −δ)   (7)
 
     and the optimal solution of single rounding offset δ can be approximated as 
     
       
         
           
             
               
                 
                   δ 
                   = 
                   
                     1 
                     - 
                     
                       
                         s 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ⅇ 
                           
                             - 
                             s 
                           
                         
                       
                       
                         1 
                         - 
                         
                           ⅇ 
                           
                             - 
                             s 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     It is believed that distribution of transform coefficients in H.264 is close to a Laplacian distribution. Therefore, Eq. 8 can be applied to derive the improved adaptive quantization rounding offset parameter. However, in Eq. 8, the offset is represented as a function of quantization step size, which is different from the actual quantization step size in H.264 as s here is scaled for a source with variance equal to 2. In other words, in one embodiment, the statistics of the transform coefficients may need to be tracked to calculate the signal variance, which requires additional processing capacity and computation cycles. 
     A look-up table based technique can be used to solve the problem with tracking transform coefficient statistics. Since both δ and H are monotonic functions of s, δ can be considered a function of H, i.e., average number of bits per sample. In one embodiment, the relative offset is provided as the ratio between δ and s. 
       FIG. 1  shows one example of the relationship between the number of coefficient bits per sample (H) and the optimized relative quantization offset (δ/s). Of course this is only one example of relative offset values that can be used for different input data entropy. In the example of  FIG. 1 , the number of bits per sample (H) and the associated relative quantization offset values are loaded into a look-up table  34  (see  FIG. 3 ) as discrete values. 
     There could be a variety of different techniques used for generating the values in  FIG. 1 . In one embodiment, the relative quantization offset values are derived from sample transform data and then loaded into a look-up table prior to operation in an encoder. Alternatively, the relative quantization offset values may be generated on the fly in real-time during the encoding process according to Eq. 8 and the identified bits per sample for the encoded data. 
     The one-dimensional array, or look-up table  34 , allows a relative quantization offset value to be derived for any entropy value using a simple linear interpolation. The process of conducting a linear interpolation between discrete points is well known to those skilled in the art and is therefore not described in further detail. 
     The adaptive quantization offset values can also be varied for different types of data. For example, data frames or sub-blocks that generally have a relatively low entropy may use a first set of relative offset table entries and frames or sub-blocks that have a relatively high entropy may use a second set of relative offset table entries. Also as described above, the relative quantization offset values may be used with a Uniform-Reconstruction-Quantizer (URQ) that has uniform quantization step sizes. Alternatively, the relative offset values could be used in quantizers with non-uniform quantization step sizes that may vary for different quantization step levels. 
       FIG. 2  shows graphically how the relative quantization offset values  14  are applied to the Uniform-Reconstruction-Quantizer (URQ). A horizontal line  16  is associated with input data that needs to be quantized. In this example, the input  16  may be transform coefficients derived from encoded image data. The vertical line  18  represents the quantized output values that are output for different ranges of input values  16 . 
     For example, input values  16  between zero and a quantization step size s may be quantized to the same quantized output value  0 . Input values  16  between quantization step size value s and  2   s  are quantized to the same quantized output value of s, input values  16  between quantization step size  2   s  and  3   s  are quantized to the same quantized output value  2   s , etc. The actual output values of course may be different than the values shown in  FIG. 2 . 
     An adaptive quantization offset or roundoff value  14  (δ) is derived according to the data entropy as described above and then applied to the basic quantization step size values s. The adapted quantization step size is shown as dashed lines  20  in  FIG. 2 . As can be seen, the adapted quantization offset  14  in this example shifts the quantization threshold values between the different quantization steps an amount δ to the left. 
     In this example, the adaptive quantization offset value  14  is simply subtracted from each the quantization step size values s. Accordingly, the quantized output value  18  is zero when the input data  16  is between zero and s-δ, s when the input data is between s-δ and  2   s -δ,  2   s  when the input data is between  2   s -δ and  3   s -δ, etc. In other embodiments, the relative quantization offset value δ might be added to the quantization values or multiplied by some constant value prior to being applied to the base quantization step size. Other algorithms can also be used for applying the offset values to the quantization step size depending upon how the offset values and quantization values are derived. 
       FIG. 3  shows one example of an encoder  30  that uses the adaptive quantization offset scheme described above. The encoder  30  conducts a transform operation  32  on received input video frames  28 . The transform operation  32  generates transform coefficients  38  that are then quantized by a quantizer operation  44 . Some part of the encoding operation  30  identifies the average number of bits  36  used to encode a coefficient according to previously encoded transform coefficients  38 . It may require more bits to encode an input video frame  28  containing a relatively large amount of information and require fewer bits to encode an input video frame  28  with a relatively small amount of information. For example, a video frame of a non-moving relatively uniform blue sky may require fewer transform coefficient bits than a video frame that shows a portion of a car chase scene. Thus, the number of transform coefficient bits  36  is related to the amount of entropy in the input video signal  28 . 
     A quantization offset controller  40  uses the number of transform coefficient bits  36  as a lookup index into a quantization offset look-up table  34 . The look-up table  34  for example contains the bits per sample vs. relative offset values shown in  FIG. 1 . The controller  40  identifies the relative quantization offset value  42  in table  34  corresponding to the identified average number of bits  36 . The bit number  36  may reside between two values in look-up table  34 . In this case and as described above, the quantization offset controller  40  may conduct an interpolation using the two quantization offset values that are associated with the two entries in table  34  immediately above and below the identified bit number  36 . 
     The identified or derived relative quantization offset value  42  is then used by the quantizer operation  44  for adaptively modifying the current quantizer step size as described above in  FIG. 2 . The quantized transform coefficients  46  are then output from quantizer  44  for possibly further predictive and entropy encoding before being transmitted, stored, etc. 
       FIG. 4  shows a more detailed view of predictive coder, such as used in the H.264 encoding structure that can use the adaptive quantization offset scheme described above. In this embodiment, a coding control operation  68  also provides adaptive quantization offset control  40 . In the predictive encoder  45 , the output of quantization operation  44  is fed both into an entropy coding operation  66  and an inverse quantization operation  64 . The output of the inverse quantization operation  64  is fed into an inverse transform operation  62 . The inverse transformed data and intra/inter predicted data  52  are fed into a deblocking filter  60 . 
     A frame store  56  outputs the results from the deblocking filter  60  into a motion estimation operation  58 , an inter-block motion compensator  54 , and an intra-block prediction and compensator operation  50 . The outputs for operations  50  and  54  provide the intra/inter prediction data  52 . The residuals from the predicted data  52  and the input video signals  28  are fed into transform operation  32 . 
     In this example, the bit information  36  identifying the number of bits used for coding the input video signal  28  is derived by the entropy coding operation  66 . The entropy coding operation  66  receives the quantized transform coefficients and then identifies a number of bits  36  used for encoding a frame in the input video signals  28 . The controller  40  uses the bit information  36  to identify the adaptive quantization offset values  42 . The identified offset values are then used by the quantization operation  44  for quantizing the transform coefficients  38 . 
     It should be understood that the different operations for the encoders shown in  FIGS. 4 and 5  may be implemented in any combination of hardware and/or software. For example, the entire encoder  30  or  45  may be implemented in software that is executed on one or more processors. Alternatively, some of the encoder operations may be implemented in separate logic circuitry. 
       FIG. 5  describes in more detail how the adaptive quantization offset values are generated during H.264 encoding. Again, the same adaptive quantization scheme can be used for other encoders. In operation  70 , the relative offset is initialized for the first Intra (I), Predictive (P), and Bi-directionally predicted (B) pictures. For example, a value of ⅓ may be initialized for the first I picture and a value of ⅙ initialized for the first P and B pictures. The I pictures are Intra coded pictures where macroblocks are coded without prediction. The I pictures are needed to allow a receiver to have a “starting point” for prediction after a channel change and to recover from errors. 
     The P pictures are predicted pictures that have macroblocks that may be coded with forward prediction from references made from previous I and P pictures or may be intra coded. The B pictures are bi-directionally predicted pictures that have macroblocks that may be coded with forward prediction from previous I or P references, backward prediction from next I or P reference, interpolated prediction from past and future I or P references, or intra coded (no prediction). 
     In operation  72 , the current picture is encoded, for example, as described above in  FIG. 4 . In operation  74 , the total number of bits are counted for each luminance coefficient coding and chrominance coefficient coding for each picture, respectively. In operation  76 , the average number of bits are derived for luminance and chrominance samples. 
     In operation  78 , the relative quantization offset parameters are derived for the luminance and chrominance samples. For example, the offset values are identified in the look-up table  34  ( FIGS. 3 and 4 ) that most closely match the average number of bits derived for the luminance and chrominance samples. The final adapted quantization offset values are then derived from the offset values identified in the look-up table using linear interpolation. If there are more frames to process in operation  80 , the derived adapted quantization offset parameters for the luminance and chrominance are used for the next picture of the same I, P, or B type. 
     Thus, the adaptive quantization offset scheme can be integrated with H.264 JM8.6. Some encoding performance results are shown in the rate-distortion curves shown in  FIGS. 6 and 7 . The adaptive quantization offset scheme can also be directly applied to compression systems other than H.264. For example, the adaptive offset scheme can be used whenever a URQ is applied and the input signals are close to Laplacian sources. If the input signals do not closely follow a Laplacian distribution, the same framework could also be applied when a one-to-one relationship is established between the relative quantization offset and the number of bits per sample. 
     The system described above can use dedicated processor systems, micro controllers, programmable logic devices, or microprocessors that perform some or all of the operations. Some of the operations described above may be implemented in software and other operations may be implemented in hardware. 
     For the sake of convenience, the operations are described as various interconnected functional blocks or distinct software modules. This is not necessary, however, and there may be cases where these functional blocks or modules are equivalently aggregated into a single logic device, program or operation with unclear boundaries. In any event, the functional blocks and software modules or features of the flexible interface can be implemented by themselves, or in combination with other operations in either hardware or software. 
     Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention may be modified in arrangement and detail without departing from such principles. I claim all modifications and variation coming within the spirit and scope of the following claims.