Patent Publication Number: US-6671324-B2

Title: Estimating total average distortion in a video with variable frameskip

Description:
FIELD OF THE INVENTION 
     This invention relates generally to video encoding, and more particularly to determining distortion characteristics of videos. 
     BACKGROUND OF THE INVENTION 
     A number of video coding standards support variable frameskip, e.g., H.263 and MPEG-4. With variable frameskip, any number of frames of the input video can be skipped during the coding. That is, the frames remain uncoded. With these video coding standards, the encoder may choose to skip frames of a video to either satisfy buffer constraints, or to optimize the video coding process. However, most encoders only skip frames to satisfy buffer constraints. In this case, the coder is forced to skip frames when limitations on the bandwidth cause the buffer to fill up. Consequently, it is not possible to add any additional frames to the buffer, and the frames remain uncoded until the buffer is drained. This type of frame skipping degrades the quality of the video because the content of the video is not considered. 
     It is a problem to provide an optimal coding method for a video. Specifically, a particular video could be coded with more frames having a lower spatial quality, or fewer frames having a higher spatial quality. This trade-off between spatial and temporal quality is not a simple binary decision, but rather a decision over a finite set of coding parameters. Obviously, the best set of coding parameters will yield the optimal rate-distortion (R-D) curve. The two parameters of interest are the number of frames per second (fps) and a quantization parameter (QP). In the known prior art, the total distortion is measured only for coded frames, and is expressed as the mean-squared error (MSE) between pixels in the original and compressed video. 
     Prior art optimized coding methods do not consider the temporal aspect of rate-distortion, see H. Sun, W. Kwok, M. Chien, and C. H. John Ju, “MPEG coding performance improvement by jointly optimizing coding mode decision and rate control,”  IEEE Trans. Circuits Syst. Video Technol.,  June 1997, T. Weigand, M. Lightstone, D. Mukherjee, T. G. Campbell, S. K. Mitra, “R-D optimized mode selection for very low bit-this rate video coding and the emerging H.263 standard,”  IEEE Trans. Circuits Syst. Video Technol.,  and April 1996, J. Lee and B. W. Dickenson, “Rate-distortion optimized frame type selection for MPEG encoding,”  IEEE Trans. Circuits Syst. Video Technol.,  June 1997. Generally, it is assumed that the frame-rate is fixed. 
     These methods consider optimizations on the quantization parameter, H. Sun, W. Kwok, M. Chien, and C. H. John Ju, “MPEG coding performance improvement by jointly optimizing coding mode decision and rate control,”  IEEE Trans. Circuits Syst. Video Technol.,  June 1997, mode decisions for motion and block coding, T. Weigand, M. Lightstone, D. Mukherjee, T. G. Campbell, S. K. Mitra, “R-D optimized mode selection for very low bit-this rate video coding and the emerging H.263 standard,”  IEEE Trans. Circuits Syst. Video Technol.,  April 1996, and frame-type selection, J. Lee and B. W. Dickenson, “Rate-distortion optimized frame type selection for MPEG encoding,”  IEEE Trans. Circuits Syst. Video Technol.,  June 1997. Such methods can achieve an optimum coding when the frame-rate is fixed, and the bit rate can be for the given frame-rate. However, these methods are less than optimal for varying frame-rates. 
     It should be noted that the trade-off between spatial and temporal quality, while coding, has been described by F. C. Martins, W. Ding, and E. Feig, in “Joint control of spatial quantization and temporal sampling for very low bit rate video,”  Proc. ICASSP,  May 1996. However, in their method, the trade-off was achieved with a user selectable parameter. 
     Therefore, it is desired to provide a better method for determining distortion in a video. 
     SUMMARY OF THE INVENTION 
     The present invention provides a method for determining the distortion in a video subject to variable frameskip processing. If the input video is uncompressed and to be coded, then the distortion is an estimate of the distortion in an output compressed video, whereas if the input video is compressed, then the distortion is an actual measure of distortion in the compressed video. 
     The distortion for coded frames (candidate or actual) is given by a rate-distortion model, and the distortion for uncoded frames (candidate or actual) can be based on an optical flow in the video. The method according to the invention produces accurate distortion values over a range of videos with varying scene complexities. In the case the input video is uncoded, the method can be used for optimizing the trade-off between spatial and temporal quality in a video coder. For a compressed video, the method can also be used to compare the relative quality without having access to the original video. 
     More particularly, a method determining distortion in a video by measuring a spatial distortion in coded frames, and by measuring a temporal distortion and spatial distortion in uncoded frames. The spatial distortion of the coded frames is combined with the temporal distortion and the spatial distortion of the uncoded frames to determine a total average distortion in the video. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flow diagram of a method for determining distortion in a video according to the invention; 
     FIG. 2 is a plot comparing the actual and estimated distortion for coded frames; 
     FIG. 3 is a plot comparing the actual and estimated distortion for the uncoded frames of the Akiyo sequence coded at a fixed frame rate of 10 fps; and 
     FIG. 4 is a plot comparing the actual and estimated distortion for the uncoded frames of the Foreman sequence coded at a fixed frame rate of 15 fps. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Introduction 
     Determining Total Average Distortion 
     As shown in FIG. 1, our invention provides a method  100  for determining the total average distortion  109  in a video  101  subject to variable frameskip processing. If the input video  101  is uncompressed and to be coded, then the frames are candidate coded  112  or uncoded  122  frames, and the total distortion  109  is an estimate of the distortion in an output compressed video, whereas if the input video  101  is compressed, then the frames are actual coded  112  or uncoded  122  frames, and the total distortion  109  is an actual measure of distortion in the compressed video. 
     In one embodiment where the video is uncompressed, a splitter  105  determines which frames are coded ( 112 ), and which frames are skipped ( 122 ). The decision is based on the measured average total distortion  109 . 
     We denote the spatial distortion for coded frames  112  by {overscore (D)} c (Q)  111 , and the temporal and spatial distortion for uncoded frames  122  by {overscore (D)} s (Q, f s )  121 , where Q represents a quantization parameter (QP) used for coding, and f s  a frameskip factor that is related to the number of uncoded frames. 
     The spatial distortion  111  is dependent on the quantizer, a spatial measure, while the temporal distortion  121  depends on both the quantizer and the number of uncoded frames. 
     Although the distortion for uncoded frames does not directly influence the distortion of coded frames, it does influence it indirectly in two ways. First, the number of uncoded frames influences a residual statistical component, and second, it influences the quantizer that is selected. 
     It is important to note that the distortion  111  for the uncoded frames  122  has a direct dependency on the quantization step size in the coded frames  112 . The reason is that the uncoded frames  122  are interpolated from the coded frames  112 , thereby carrying the same spatial quality, in addition to the temporal distortion. 
     Given the above, we determine the average distortion over a specific time interval (t i +f i+f     s   ] by,                    D   _         (       t   i     ,     t     i   +     f   s             ]            (       Q       i   +     f   s       ,            f   s       )       =         1     f   s            [         D   c          (     Q     i   +     f   s         )       +       ∑     k   =     i   +   1         i   +     f   s     -   1              D   s          (       Q   i     ,   k     )           ]       .             (   1   )                         
     In equation 1, the distortion over the specified time interval is due to the spatial distortion of one coded frame at t=t i+fs , plus the temporal distortion of f s   − 1 uncoded frames. The temporal distortion is dependent on the quantizer for the previously coded frame at t=t i . 
     Spatial Distortion 
     It is well known that the variance of the quantization error is given by, 
     
       
         σ q   2   =a· 2 −2R σ z   2 ,  (2)  
       
     
     where σ z   2  is the input signal variance, R is the average rate per sample, and a is a constant that is dependent on the probability distribution function (PDF) of the input signal and quantizer characteristics, see Jayant et al. “ Digital Coding of Waveforms,”  Prentice Hall, 1984. In the absence of entropy coding, the value of a typically varies between 1.0 and 10. With entropy coding, the value of a can be less than 1.0. We use equation 2 to determine  110  the spatial distortion  111  as, 
     
       
           D   c ( Q   i )= a· 2 −2R(t     t     ) ·σ Z   2 .  (3)  
       
     
     Equation 3 is valid for a wide array of quantizers and signal characteristics. Such aspects are accounted for in the value of a. However, as stated above, the number uncoded frames can impact the statistics of the residual. In general, we have determined that the average bits per frame increases for larger values of f s . However, the variance remains substantially the same. This indicates that the variance is incapable of reflecting small differences in the residual that impact the actual relation between rate and distortion. This is caused by the presence of high-frequency coefficients. Actually, it is not only the presence of the high-frequency coefficients, but also their position. If certain run-lengths are not present in a variable length coding table, e.g. Huffman coding, less efficient escape coding techniques must be used. This probably means that f s  affects the PDF of the residual, i.e., the value of a, while holding σ z   2  substantially fixed. 
     We ignore any changes in the residual due to the uncoded frames, and use the model given by equation 3 to determine the spatial distortion  111 . A fixed a and σ z     i     2  determined from the last coded frame is used. 
     Temporal Distortion 
     To determine  120  the temporal distortion  121  of the uncoded frames  122 , we assume, without loss of generality, that a temporal interpolator of a code simply repeats the last coded frame. Other interpolators that average past and future coded frames, or make predictions based on motion, can also be considered. 
     As stated above, the distortion due to uncoded frames has two parts: one due to the coding of the reference frame (last coded frame), and another due to the interpolation error. We express the distortion at t k  as,                      e   k     =         ψ   k     -       ψ   ^     k       =       ψ   k     -       ψ   ~     i                       =           ψ   k     -     ψ   i              Δ                   z     i   ,   k             +         ψ   i     -       ψ   ~     i              Δ                   c   i               ,                 (   4   )                         
     wherein {circumflex over (ψ)} k  denotes the estimated frame at t=t k , {tilde over (ψ)} i  denote the last coded frame at t i &lt;t k , {circumflex over (ψ)} i , and ΔZ i,k  and Δc t  represent the frame interpolation error and coding error, respectively. If these quantities are independent, the mean square error (MSE) is 
     
       
           E{e   k   2   }=E{Δ   2   c   i   }+E{Δ   2   z   i,k },  (5)  
       
     
     which can be equivalently expressed as, 
     
       
           D   s ( Q   i   ,k )= D   c ( Q   i )+ E{Δ   2   z   i,k},   (6)  
       
     
     that is, the combination  130  of the spatial and temporal distortions. Equation 6 implies that the components contributing to the temporal distortion  121  are additive. However, other combinations may also be considered. 
     To derive the expected MSE due to frame interpolation, we first assume that the frame at time t k  is related to the frame at time t i  with motion vectors (Δx(x, y), Δy(x, y)), 
     
       
         ψ k ( x, y )=ψ i ( x+Δx ( x, y ),  y+Δy ( x, y )).  (7)  
       
     
     In the equation 7, it is assumed that every pixel (x, y) has an associated motion vector. In actuality, we approximate the motion at every pixel by having one motion vector per macroblock. Then,                  Δ                   z     i   ,   k         =         ψ   i          (       x   +     Δ                   x     i   ,   k           ,     y   +     Δ                   y     i   ,   k             )       -       ψ   i          (     x   ,   y     )           ,     =           δψ   i       δ                 x          Δ                   x     i   ,   k         +         δψ   i       δ                 y          Δ                   y     i   ,   k             ,           (   8   )                         
     where        (         δψ   i       δ                 x       ,       δψ   i       δ                 y         )                   
     represent the spatial gradients in the x and y directions. Note, this equation is expanded by using a first-order Taylor expansion and is valid for small (Δx, Δy ).This is equivalent to an optical flow equation, where the same condition on motion is also true. 
     It should be noted that equation 8 is less accurate when the amount of motion in a sequence of frames is large. However, for coding applications that estimate the distortion to decide if a lower MSE can be achieved with more uncoded frames, the accuracy of the motion estimation is not so critical because an optimized encoder would not skip frames for such sequences anyway. The MSE incurred by skipping frames in a sequence with large motion would be very large. 
     Treating the spatial gradients and motion vectors as random variables and assuming the motion vectors and spatial gradients are independent and zero-mean, we have, 
     
       
           E{Δ   2   z   i,k }=σ x     i   +σ Δx     i,k   +σ y     i     2 σ y     l     2 σ y     i     2 σ Δy     i,k     2   (9)  
       
     
     where (σ x     i     2 , σ y     i     2 ) represent the variances for the x and y spatial gradients in frame i, and (σ Δx     i,k     2 , σ Δy     i,k     2 ) represent the variances for the motion vectors in the x and y direction. Equation 9 shows that it is sufficient to determine the temporal distortion from the second-order statistics of the motion and spatial gradient. 
     Practical Considerations 
     In practical coding applications, where an encoder would estimate the total distortion, the main problem is to determine  120  the temporal distortion  121  based on past and current data. For instance, equation 9 assumes that the motion between i, the current frame, and k, a future frame is known. However, this would imply that motion estimation is performed for each candidate frame to be coded or not, where these candidate frames have a time index k. This is impractical. Therefore, we assume the motion between frames is linear, and approximate the variance of motion vectors by,                  σ     Δ                   x     i   ,   k         2     ≈       σ     Δ                   x       i   -   fl     ,   i           ·       (       k   -   i       f   l       )     2         ,           (   10   )                         
     where f l  denotes the number of uncoded frames between the last coded frame and its reference frame. 
     Similarly, estimates of the distortion for the next candidate frame to be coded, i.e., the measurement specified by equation 3, requires knowledge of a and σ z     i     2 , which depends on f s . As mentioned above, motion estimation for every candidate frame is not performed, therefore the actual residuals are also unavailable. To overcome this practical difficulty, the residual for future frames can be predicted from the residual of the current frame at, i.e., t=t i . 
     However, as described above, the relationship between the a, σ z     i     2  and the uncoded frames is not as obvious as the relation between motion and in uncoded frames. Also, we have observed that changes in the variance for different numbers of uncoded frames are very small. Therefore, we use the residual variance of the current frame at t=t i  for the candidate frames as well. In this way, changes in D c  are only affected by the “bit budget” for candidate frameskip factors. 
     If the input video  101  is in compressed form, then the data are known, and the estimate become an actual measure of total average distortion. In this case, the above considerations do not apply. 
     Results 
     To confirm the accuracy of our method, we perform two sets of experiments. A first experiment tests the accuracy of the estimated distortion for coded frames and a second experiment to test the accuracy of the estimated distortion for uncoded frames. 
     The testing conditions for the first experiment are as follows. We consider two well known test sequences in FIG.  2 : Akiyo (left) and Foreman (right. Each sequence is coded at its full frame-rate of 30 fps. Three fixed quantizers are used to code each sequence, Q=2 for the first 100 frames, Q=15 for the next 100 frames and Q=30 for the last 100 frames. FIG. 2 shows plots for Akiyo and Foreman in which the estimated distortion is determined according to equation 3, with a=1. 
     From these plots, we first note that for the most part the estimated distortion tracks the actual distortion. Second, in both sequences, the estimation of the coded distortion at fine quantizer values tends to be over-estimated. The reason for this is not clear, but we note that it is possible to use a calibrated value of a to correct this estimation error, or to simply use a fixed MSE when the quantizer is so fine. 
     For the second experiment, we consider the Akiyo sequence coded at a fixed frame-rate of 10 fps and the Foreman sequence coded at a fixed rate of 15 fps. A comparison of the actual and estimated distortion for the uncoded frames in Akiyo is shown in FIG.  3 . The left graph shows the first uncoded frames, while the right plot shows the second uncoded frames. The graph indicates that the estimated distortion in the uncoded frames for Akiyo is quite accurate. 
     FIG. 4 compares the actual and estimated distortion for the uncoded frames in the Foreman sequence. Although the estimated distortion is not as accurate as Akiyo, we can see that it is able to follow variations in the actual distortion quite well. 
     However, because the motion in the sequence is large, the distortion due to frame skipping is a significant factor in the overall distortion. It is safe to say that an optimized coder will never skip frames for such a sequence. Rather, it will resort to using a quantizer until buffer constraints force the encoded sequence to a lower frame-rate. As a result, the accuracy for the distortion of uncoded frames is much more critical for sequences with low to moderate motion. 
     This invention is described using specific terms and examples. It is to be understood that various other adaptations and modifications may be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.