Abstract:
A method and an encoder for SSIM-based bits allocation. The encoder includes a memory and a processor utilized for allocating bits based on SSIM, wherein the processor estimates the model parameter of SSIM-based distortion model for the current picture and determines allocates bits based on the SSIM estimation.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of U.S. patent application Ser. No. 13/632,392, filed Oct. 1, 2012, which claims the benefit of U.S. provisional patent application Ser. No. 61/540,587, filed Sep. 29, 2011, all of which are herein incorporated by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    Field of the Invention 
         [0003]    Embodiments of the present invention generally relate to a method and apparatus for SSIM-based bit allocation. 
         [0004]    Description of the Related Art 
         [0005]    Bit rate affects the video quality. Thus, it is crucial to allocate the effective amount of bits per frame to maintain quality and efficiency/cost. Mean Square Error is still major metric being used in video encoder control and optimization. However, Mean Square Error based encoder is far from perceptual optimization. Even though SSIM (Structural Similarity) index is a good quality metric for subjective video quality assessment and more correlated than Mean Square Error to a human&#39;s visual perception, yet, currently, there is no SSIM-based rate and/or distortion models. 
         [0006]    Therefore, there is a need for a method and/or apparatus for SSIM-based bit allocation. 
       SUMMARY OF THE INVENTION 
       [0007]    Embodiments of the present invention relate to a method and an encoder for SSIM-based bits allocation. The encoder includes a memory and a processor utilized for allocating bits based on SSIM, wherein the processor estimates the model parameter of SSIM-based distortion model for the current picture and determines allocates bits based on the SSIM estimation. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. 
           [0009]      FIG. 1  is an embodiment of a relationship between ln (D′ssim/Dssim) and Rate; 
           [0010]      FIG. 2  is an embodiment of a flow diagram depicting a method for SSIM-based bit allocation; and 
           [0011]      FIG. 3  is an embodiment of an encoder. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    The proposed invention minimizes overall SSIM distortion, which is more correlated with human perceptual quality than MSE, while existing bit allocation methods focus on minimization of overall MSE distortion 
         [0013]    The proposed invention provides the optimal number of bits for each coding unit in a closed form. And encoded video by the proposed bit allocation will be more pleasing to human visual system. 
         [0014]    SSIM index evaluates the quality of reconstructed coded frame r by comparing luminance, contrast and structural similarities between r and original frame o. That is, 
         [0000]    
       
         
           
             
               
                 SSIM 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     o 
                     , 
                     r 
                   
                   ) 
                 
               
               = 
               
                 
                   l 
                    
                   
                     ( 
                     
                       o 
                       , 
                       r 
                     
                     ) 
                   
                 
                 · 
                 
                   c 
                    
                   
                     ( 
                     
                       o 
                       , 
                       r 
                     
                     ) 
                   
                 
                 · 
                 
                   s 
                    
                   
                     ( 
                     
                       o 
                       , 
                       r 
                     
                     ) 
                   
                 
               
             
             , 
             
               
                 where 
                  
                 
                     
                 
                  
                 
                   l 
                    
                   
                     ( 
                     
                       o 
                       , 
                       r 
                     
                     ) 
                   
                 
               
               = 
               
                 
                   
                     2 
                      
                     
                       μ 
                       o 
                     
                      
                     
                       μ 
                       r 
                     
                   
                   + 
                   
                     C 
                     1 
                   
                 
                 
                   
                     μ 
                     o 
                     2 
                   
                   + 
                   
                     μ 
                     r 
                     2 
                   
                   + 
                   
                     C 
                     1 
                   
                 
               
             
             , 
             
               
                 c 
                  
                 
                   ( 
                   
                     o 
                     , 
                     r 
                   
                   ) 
                 
               
               = 
               
                 
                   
                     
                       
                         2 
                          
                         
                           σ 
                           o 
                         
                          
                         
                           σ 
                           r 
                         
                       
                       + 
                       
                         C 
                         2 
                       
                     
                     
                       
                         σ 
                         o 
                         2 
                       
                       + 
                       
                         σ 
                         r 
                         2 
                       
                       + 
                       
                         C 
                         2 
                       
                     
                   
                    
                   
                       
                   
                    
                   and 
                    
                   
                       
                   
                    
                   
                     s 
                      
                     
                       ( 
                       
                         o 
                         , 
                         r 
                       
                       ) 
                     
                   
                 
                 = 
                 
                   
                     
                       
                         2 
                          
                         
                           σ 
                           or 
                         
                       
                       + 
                       
                         C 
                         3 
                       
                     
                     
                       
                         
                           σ 
                           o 
                         
                          
                         
                           σ 
                           r 
                         
                       
                       + 
                       
                         C 
                         3 
                       
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    C 1 , C 2  and C 3  are constants to avoid unstable behavior in the regions of low luminance or low contrast. 
         [0015]    The range of SSIM index is 0 to 1. SSIM index is close to 1 when two frames are similar. For example, when two frames are identical, SSIM index is 1. So distortion is 1−SSIM. With MSE as a distortion metric, it is well known that distortion is modeled by 
         [0000]        D   MSE =σ 2 ·exp {−β R ),
 
         [0000]    where σ 2  is variance of residual signal and where β is model parameter. 
         [0016]    Residual signal is difference between original and prediction. We observe that distortion in terms of SSIM (i.e. 1−SSIM) is modeled by the similar function. That is, 
         [0000]      1−SSIM( o,r )=(1−SSIM( o,p ))·exp {−β R ),
 
         [0000]    where is model parameter and p is prediction. 
         [0017]    By replacing 1−SSIM (o, r) and 1−SSIM (o, p) with D ssim  and D′ ssim , respectively, for simplicity, we have 
         [0000]        D   SSIM   =D′   SSIM ·exp(−β R ),  (1)
 
         [0000]    where is model parameter and p is prediction. 
         [0018]      FIG. 1  is an embodiment of a relationship between ln (D′ssim/Dssim) and Rate.  FIG. 1  shows the relationship between ln (D′ SSIM /D SSIM ) and rate for 5 consecutive P frames from 4 720p sequences. Hence, Eq. (1) is valid with different values of β depending on the characteristics of frames (coding units). 
         [0019]    Applying the SSIM-based distortion model for perceptually optimized bit allocation and assuming that there are n coding units (e.g. frame) to encode with total bit budge R T , the overall perceptual quality is optimized with R T . That is, 
         [0000]    
       
         
           
             
               minimize 
                
               
                   
               
                
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   N 
                 
                  
                 
                     
                 
                  
                 
                   
                     D 
                     
                       SSIM 
                       , 
                       i 
                     
                   
                    
                   
                       
                   
                    
                   subject 
                    
                   
                       
                   
                    
                   to 
                    
                   
                       
                   
                    
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       N 
                     
                      
                     
                         
                     
                      
                     
                       R 
                       i 
                     
                   
                 
               
             
             ≤ 
             
               
                 R 
                 T 
               
               . 
             
           
         
       
     
         [0020]    Here we assume that all coding units are independent. This constrained problem can be converted to the unconstrained problem with Lagrange multiplier: 
         [0000]    
       
         
           
             
               
                 
                   
                     minimize 
                      
                     
                         
                     
                      
                     J 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                           
                       
                        
                       
                         D 
                         
                           SSIM 
                           , 
                           i 
                         
                       
                     
                     + 
                     
                       λ 
                       · 
                       
                         ( 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               R 
                               i 
                             
                           
                           - 
                           
                             R 
                             T 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                           
                       
                        
                       
                         
                           β 
                           i 
                         
                         · 
                         
                           D 
                           
                             SSIM 
                             , 
                             i 
                           
                           ′ 
                         
                         · 
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 - 
                                 
                                   β 
                                   i 
                                 
                               
                                
                               
                                 R 
                                 i 
                               
                             
                             ) 
                           
                         
                       
                     
                     + 
                     
                       λ 
                       · 
                       
                         
                           ( 
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 R 
                                 i 
                               
                             
                             - 
                             
                               R 
                               T 
                             
                           
                           ) 
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
         [0021]    By setting partial derivative w.r.t and λ and R k  to 0, we have optimal bits for coding unit k as 
         [0000]    
       
         
           
             
               
                 
                   
                     R 
                     k 
                   
                   = 
                   
                     
                       
                         1 
                         
                           β 
                           k 
                         
                       
                        
                       
                         ln 
                          
                         
                           ( 
                           
                             
                               β 
                               k 
                             
                             · 
                             
                               D 
                               
                                 SSIM 
                                 , 
                                 k 
                               
                               ′ 
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         1 
                         
                           
                             β 
                             k 
                           
                           · 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               1 
                               
                                 β 
                                 i 
                               
                             
                           
                         
                       
                       · 
                       
                         
                           { 
                           
                             
                               R 
                               T 
                             
                             - 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 
                                   1 
                                   
                                     β 
                                     i 
                                   
                                 
                                  
                                 
                                   ln 
                                    
                                   
                                     ( 
                                     
                                       
                                         β 
                                         i 
                                       
                                       · 
                                       
                                         D 
                                         
                                           SSIM 
                                           , 
                                           i 
                                         
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           } 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0022]    The proposed bit allocation in Eq. 2 can be implemented in various ways. For example, two-pass method and approximated one-pass method. In two pass method, all coding units are coded with fixed QP in the first pass to get β and D′ SSIM  for all coding units in consideration. Then after determining R k  for all coding units, they are finally coded in the second pass. In the approximated one-pass method, β and D′ SSIM  are approximated from previous coding units. In case of frame bit allocation in GOP, β and D′ SSIM  values of all frames in a GOP can be approximated from frames at the same positions in the previous GOP. 
         [0023]      FIG. 2  is an embodiment of a flow diagram depicting a method  2100  for SSIM-based bit allocation. The method  200  starts at step  202  and proceeds to step  204 . At step  204 , the method  200  set GOP count to zero. At step  206 , the method  200  increments the GOP count by 1. At step  208 , the method  200  sets the picture count to zero. At step  210 , the method  200  encodes the current picture in the current GOP. At step  212 , the method  200  estimates the model parameter of SSIM-based distortion model for the current picture. At step  214 , the method  200  determines if the current picture is the last picture in the current GOP. 
         [0024]    If it is not the last picture in the current GOP, the method  200  proceeds to step  216 , wherein the method  200  increments the picture count and returns to step  206 ; otherwise the method proceeds to step  218 . At step  218 , the method  200  determines if the current GOP is the last GOP. If it is, the method  200  proceeds to step  222 ; otherwise, the method  200  proceeds to step  220 . At step  220 , the method  200  determines the target bits for each frame for the next GOP and returns to step  210 . The method  200  ends at step  222 . 
         [0025]      FIG. 3  shows a block diagram of the largest coding units (LCU) processing portion of an example video encoder. A coding control component (not shown) sequences the various operations of the LCU processing, i.e., the coding control component runs the main control loop for video encoding. The coding control component receives a digital video sequence and performs any processing on the input video sequence that is to be done at the picture level, such as determining the coding type (I, P, or B) of a picture based on the high level coding structure, e.g., IPPP, IBBP, hierarchical-B, and dividing a picture into LCUs for further processing. The coding control component also may determine the initial LCU coding unit (CU) structure for each CU and provides information regarding this initial LCU CU structure to the various components of the video encoder as needed. The coding control component also may determine the initial prediction unit (PU) and transform unit (TU) structure for each CU and provides information regarding this initial structure to the various components of the video encoder as needed. 
         [0026]    The LCU processing receives LCUs of the input video sequence from the coding control component and encodes the LCUs under the control of the coding control component to generate the compressed video stream. The CUs in the CU structure of an LCU may be processed by the LCU processing in a depth-first Z-scan order. The LCUs  300  from the coding control unit are provided as one input of a motion estimation component  320 , as one input of an intra-prediction component  324 , and to a positive input of a combiner  302  (e.g., adder or subtractor or the like). Further, although not specifically shown, the prediction mode of each picture as selected by the coding control component is provided to a mode selector component and the entropy encoder  334 . 
         [0027]    The storage component  318  provides reference data to the motion estimation component  320  and to the motion compensation component  322 . The reference data may include one or more previously encoded and decoded CUs, i.e., reconstructed CUs. 
         [0028]    The motion estimation component  320  provides motion data information to the motion compensation component  322  and the entropy encoder  334 . More specifically, the motion estimation component  320  performs tests on CUs in an LCU based on multiple inter-prediction modes (e.g., skip mode, merge mode, and normal or direct inter-prediction) and transform block sizes using reference picture data from storage  318  to choose the best motion vector(s)/prediction mode based on a rate distortion coding cost. To perform the tests, the motion estimation component  320  may begin with the CU structure provided by the coding control component. The motion estimation component  320  may divide each CU indicated in the CU structure into PUs according to the unit sizes of prediction modes and into transform units according to the transform block sizes and calculate the coding costs for each prediction mode and transform block size for each CU. The motion estimation component  320  may also compute CU structure for the LCU and PU/TU partitioning structure for a CU of the LCU by itself 
         [0029]    For coding efficiency, the motion estimation component  320  may also decide to alter the CU structure by further partitioning one or more of the CUs in the CU structure. That is, when choosing the best motion vectors/prediction modes, in addition to testing with the initial CU structure, the motion estimation component  320  may also choose to divide the larger CUs in the initial CU structure into smaller CUs (within the limits of the recursive quadtree structure), and calculate coding costs at lower levels in the coding hierarchy. If the motion estimation component  320  changes the initial CU structure, the modified CU structure is communicated to other components that need the information. 
         [0030]    The motion estimation component  320  provides the selected motion vector (MV) or vectors and the selected prediction mode for each inter-predicted PU of a CU to the motion compensation component  322  and the selected motion vector (MV), reference picture index (indices), prediction direction (if any) to the entropy encoder  334   
         [0031]    The motion compensation component  322  provides motion compensated inter-prediction information to the mode decision component  326  that includes motion compensated inter-predicted PUs, the selected inter-prediction modes for the inter-predicted PUs, and corresponding transform block sizes. The coding costs of the inter-predicted PUs are also provided to the mode decision component  326 . 
         [0032]    The intra-prediction component  324  provides intra-prediction information to the mode decision component  326  that includes intra-predicted PUs and the corresponding intra-prediction modes. That is, the intra-prediction component  324  performs intra-prediction in which tests based on multiple intra-prediction modes and transform unit sizes are performed on CUs in an LCU using previously encoded neighboring PUs from the buffer  328  to choose the best intra-prediction mode for each PU in the CU based on a coding cost. 
         [0033]    To perform the tests, the intra-prediction component  324  may begin with the CU structure provided by the coding control. The intra-prediction component  324  may divide each CU indicated in the CU structure into PUs according to the unit sizes of the intra-prediction modes and into transform units according to the transform block sizes and calculate the coding costs for each prediction mode and transform block size for each PU. For coding efficiency, the intra-prediction component  324  may also decide to alter the CU structure by further partitioning one or more of the CUs in the CU structure. That is, when choosing the best prediction modes, in addition to testing with the initial CU structure, the intra-prediction component  324  may also chose to divide the larger CUs in the initial CU structure into smaller CUs (within the limits of the recursive quadtree structure), and calculate coding costs at lower levels in the coding hierarchy. If the intra-prediction component  324  changes the initial CU structure, the modified CU structure is communicated to other components that need the information. Further, the coding costs of the intra-predicted PUs and the associated transform block sizes are also provided to the mode decision component  326 . 
         [0034]    The mode decision component  326  selects between the motion-compensated inter-predicted PUs from the motion compensation component  322  and the intra-predicted PUs from the intra-prediction component  324  based on the coding costs of the PUs and the picture prediction mode provided by the mode selector component. The decision is made at CU level. Based on the decision as to whether a CU is to be intra- or inter-coded, the intra-predicted PUs or inter-predicted PUs are selected, accordingly. 
         [0035]    The output of the mode decision component  326 , i.e., the predicted PU, is provided to a negative input of the combiner  302  and to a delay component  330 . The associated transform block size is also provided to the transform component  304 . The output of the delay component  330  is provided to another combiner (i.e., an adder)  338 . The combiner  302  subtracts the predicted PU from the current PU to provide a residual PU to the transform component  304 . The resulting residual PU is a set of pixel difference values that quantify differences between pixel values of the original PU and the predicted PU. The residual blocks of all the PUs of a CU form a residual CU block for the transform component  304 . 
         [0036]    The transform component  304  performs block transforms on the residual CU to convert the residual pixel values to transform coefficients and provides the transform coefficients to a quantize component  306 . The transform component  304  receives the transform block sizes for the residual CU and applies transforms of the specified sizes to the CU to generate transform coefficients. 
         [0037]    The quantize component  306  quantizes the transform coefficients based on quantization parameters (QPs) and quantization matrices provided by the coding control component and the transform sizes. The quantize component  306  may also determine the position of the last non-zero coefficient in a TU according to the scan pattern type for the TU and provide the coordinates of this position to the entropy encoder  334  for inclusion in the encoded bit stream. For example, the quantize component  306  may scan the transform coefficients according to the scan pattern type to perform the quantization, and determine the position of the last non-zero coefficient during the scanning/quantization. 
         [0038]    The quantized transform coefficients are taken out of their scan ordering by a scan component  308  and arranged sequentially for entropy coding. The scan component  308  scans the coefficients from the highest frequency position to the lowest frequency position according to the scan pattern type for each TU. In essence, the scan component  308  scans backward through the coefficients of the transform block to serialize the coefficients for entropy coding. As was previously mentioned, a large region of a transform block in the higher frequencies is typically zero. The scan component  308  does not send such large regions of zeros in transform blocks for entropy coding. Rather, the scan component  308  starts with the highest frequency position in the transform block and scans the coefficients backward in highest to lowest frequency order until a coefficient with a non-zero value is located. Once the first coefficient with a non-zero value is located, that coefficient and all remaining coefficient values following the coefficient in the highest to lowest frequency scan order are serialized and passed to the entropy encoder  334 . In some embodiments, the scan component  308  may begin scanning at the position of the last non-zero coefficient in the TU as determined by the quantize component  306 , rather than at the highest frequency position. 
         [0039]    The ordered quantized transform coefficients for a CU provided via the scan component  308  along with header information for the CU are coded by the entropy encoder  334 , which provides a compressed bit stream to a video buffer  336  for transmission or storage. The header information may include the prediction mode used for the CU. The entropy encoder  334  also encodes the CU and PU structure of each LCU. 
         [0040]    The LCU processing includes an embedded decoder. As any compliant decoder is expected to reconstruct an image from a compressed bit stream, the embedded decoder provides the same utility to the video encoder. Knowledge of the reconstructed input allows the video encoder to transmit the appropriate residual energy to compose subsequent pictures. To determine the reconstructed input, i.e., reference data, the ordered quantized transform coefficients for a CU provided via the scan component  308  are returned to their original post-transform arrangement by an inverse scan component  310 , the output of which is provided to a dequantize component  312 , which outputs a reconstructed version of the transform result from the transform component  304 . 
         [0041]    The dequantized transform coefficients are provided to the inverse transform component  314 , which outputs estimated residual information which represents a reconstructed version of a residual CU. The inverse transform component  314  receives the transform block size used to generate the transform coefficients and applies inverse transform(s) of the specified size to the transform coefficients to reconstruct the residual values. The inverse transform component  314  may perform techniques for IDCT pruning as described herein. 
         [0042]    The reconstructed residual CU is provided to the combiner  338 . The combiner  338  adds the delayed selected CU to the reconstructed residual CU to generate an unfiltered reconstructed CU, which becomes part of reconstructed picture information. The reconstructed picture information is provided via a buffer  328  to the intra-prediction component  324  and to an in-loop filter component  316 . The in-loop filter component  316  applies various filters to the reconstructed picture information to improve the reference picture used for encoding/decoding of subsequent pictures. The in-loop filter component  316  may, for example, adaptively apply low-pass filters to block boundaries according to the boundary strength to alleviate blocking artifacts causes by the block-based video coding. The filtered reference data is provided to storage component  318 . 
         [0043]    The encoder efficiency to perform these functions is largely dependent on bit allocation. The encoder  300  allocated bits based on SSIM estimations. Such allocation is described in more detail in  FIG. 2 . 
         [0044]    While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.