Abstract:
A method for RDO (Rate-Distortion Optimization) based on fit-curves contains at least the following steps: calculating a first fit-curve and a second fit-curve according to information regarding a first frame; carrying information regarding a second frame into the first and second fit-curves to calculate fit distortions and fit bit counts; calculating costs according to the fit distortions and the fit bit counts; determining the best block-division mode for the second frame according to the costs; and dividing the second frame into blocks according to the best block-division mode and encoding the second frame.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of China Patent Application No. 201610284379.2, filed on May 3, 2016, the entirety of which is incorporated by reference herein. 
       BACKGROUND 
     Technical Field 
       [0002]    The present invention relates to video encoding, and in particular, it relates to methods for RDO (Rate-Distortion Optimization) based on fit-curves and apparatuses using the same. 
       Description of the Related Art 
       [0003]    RDO (Rate-distortion optimization) is the technology of improving video quality in video compression. It is used to optimize the amount of loss of video quality (the distortion) against the amount of data required to encode the video (the rate). Specifically, RDO determines an encoding mode to achieve a balance between the distortion and the rate to optimize video compression for a video compression system. The encoding mode may indicate a prediction mode, a MV (Motion Vector), a reference frame, or others. The purpose of the encoding-mode determination is to select the best one from multiple candidates. The video compression system may use the Lagrange R-D cost function to determine the best encoding mode as follows: 
         [0000]      min{ J}, J=D+λ·R    (1)
 
         [0000]    D indicates the distortion between a source-frame block and a reconstructed-frame block. In the video encoding system, D may be one of the following values depending on different design requirements: SAD (Sum of Absolute Difference); SATD (Sum of Absolute Transformed Difference); and SSD (Sum of Squared Difference). R indicates bit counts required by the determined prediction mode, MV, reference frame, residual, or others. λ indicates a Lagrange constant. J is the result of the Lagrange R-D cost function. The object of RDO is to determine the candidate with the minimum value J as the best encoding mode, so as to achieve the optimized compression. 
         [0004]    In the conventional RDO, the encoder needs to encode data several times, in each of which is together with one candidate, so as to obtain values R and D of the candidates. Then, the values R and D are input to the Equation (1) to obtain values J, and the candidate with the minimum of the values J is determined as the best encoding mode. However, each time the encoding is performed, the data should undergo T (Transform), Q (Quantization), IT (Inverse Transform), IQ (Inverse Quantization), reconstruction, entropy coding, and so on. It takes excessive computation to encode data several times. The conventional method realized in hardware circuits not only takes excessive hardware but also defers encoding so as to hinder the real-time response. Thus, methods for RDO based on fit-curves and apparatuses using the same are introduced to address the drawbacks. 
       BRIEF SUMMARY 
       [0005]    An embodiment of the invention introduces a method for RDO (Rate-Distortion Optimization) based on fit-curves at least containing steps: calculating a first fit-curve and a second fit-curve according to information regarding a first frame; carrying information regarding a second frame into the first and second fit-curves to calculate fit distortions and fit bit counts; calculating costs according to the fit distortions and the fit bit counts; determining the best block-division mode for the second frame according to the costs; and dividing the second frame into blocks according to the best block-division mode and encoding the second frame. 
         [0006]    An embodiment of the invention further introduces an apparatus for RDO based on fit-curves at least containing an intra-frame/inter-frame prediction module, an RD cost calculation module, and a curve-fitting module. The curve-fitting module calculates a first fit-curve and a second fit-curve according to information regarding a first frame, and carries information regarding a second frame into the first and second fit-curves to calculate fit distortions and fit bit counts. The RD cost calculation module calculates costs according to the fit distortions and the fit bit counts. The intra-frame/inter-frame prediction module determines the best block-division mode for the second frame according to the costs, and divides the second frame into blocks according to the best block-division mode and encodes the second frame. 
         [0007]    A detailed description is given in the following embodiments with reference to the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The present invention can be fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: 
           [0009]      FIG. 1  is a flowchart illustrating a method for RDO based on fit-curves according to an embodiment of the invention; 
           [0010]      FIG. 2  is the system block diagram for RDO based on fit-curves according to an embodiment of the invention; and 
           [0011]      FIG. 3  is a flowchart illustrating a method of video encoding according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims. 
         [0013]    The present invention will be described with respect to particular embodiments and with reference to certain drawings, but the invention is not limited thereto and is only limited by the claims. Furthermore, it should be understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. 
         [0014]    Use of ordinal terms such as “first”, “second”, “third”, etc., in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having the same name (but for use of the ordinal term) to distinguish the claim elements. 
         [0015]    Embodiments of the invention introduce a method for RDO (Rate-Distortion Optimization) based on fit-curves. The method needs to perform fit-curves for certain kinds of data. For an example, a curve fitting is performed on absolute values of syntax to be encoded and total amounts of encoded bits for the syntax to obtain a curve describing relationships between the absolute values of syntax and the total amounts of encoded bits for the syntax. In another example, a curve fitting is performed on distortions between the original frame and the predicted frame and distortions between the original frame and the reconstructed frame to obtain a curve describing relationships between these two kinds of distortions. The method does not need to calculate R and D values like the conventional methods in the subsequent RDO. Instead, after obtaining the curves, the method only requires to calculate the absolute values of syntax to be encoded and carry the absolute values into the corresponding fit-curve to obtain the corresponding values R′, and calculate the distortions between the original frame and the predicted frame and carry the distortions to obtain the corresponding values D′. By using the fit-curves to calculate the values R′ and D′, the calculation complexity and the time deferring for encoding may be reduced.  FIG. 1  is a flowchart illustrating a method for RDO based on fit-curves according to an embodiment of the invention. The method calculates a first fit-curve and a second fit-curve according to information regarding a first frame (referred to as a reference frame) (step S 110 ), carries information regarding a second frame (referred to as a encoding frame) into the first and second fit-curves to calculate fit distortions and fit bit counts (step S 130 ) and calculate costs according to the fit distortions and the fit bit counts (step S 150 ). Next, the method determines the best block-division mode for the second frame according to the costs (step S 170 ) and divides the second frame into blocks according to the best block-division mode and encodes the second frame (step S 190 ). 
         [0016]      FIG. 2  is the system block diagram for RDO based on fit-curves according to an embodiment of the invention. The curve-fitting module  240  may fit a curve using an algorithm of GLS (Generalized Least Squares). GLS estimates the unknown parameters in a regression model under the minimum error sum of square. GLS can be used to perform regression when there is a certain degree of correlation between the explanatory variables (independent variables) of the regression model. The estimation function may be a third-order function as shown in the Equation (2): 
         [0000]        y ( x )= a·x   3   +b·x   2   +c·x+d    (2)
 
         [0017]    The curve-fitting module  240  may calculate values a, b, c and d using the Equation (3): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               1 
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 3 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 4 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 5 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 4 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 5 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 6 
                               
                             
                           
                         
                       
                       ] 
                     
                     · 
                     
                       [ 
                       
                         
                           
                             a 
                           
                         
                         
                           
                             b 
                           
                         
                         
                           
                             c 
                           
                         
                         
                           
                             d 
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               y 
                               i 
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 i 
                               
                               · 
                               
                                 y 
                                 i 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 i 
                                 2 
                               
                               · 
                               
                                 y 
                                 i 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 i 
                                 3 
                               
                               · 
                               
                                 y 
                                 i 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Where N indicates a total amount of samplings, [x i , y i ] indicates values of i-th pair of sampling. After values a, b, c and d are calculated according to information regarding one frame using the Equation (3), the fit-curve of the Equation (2) is generated accordingly. Subsequently, the curve fitting module  240  carries values x of the next frame into the Equation (2) to obtain values y. The curve fitting module  240  fits curves for the parts D and R of the Equation (1) using the Equations (2) and (3). 
         [0018]    Specifically, for the curve fitting of the value D, the curve fitting module  240  may obtain distortions SAD between original pixel values and predicted pixel values of N different PUs (Prediction Units) of the frame from the intra-frame/inter-frame prediction module  210 , and obtain distortions D between original pixel values and reconstructed pixel values of the PUs of the frame from the distortion calculation module  230 , so as to obtain N pairs of [x i1 , y i1 ], where x i1  indicates the distortion between the original pixel value and the predicted pixel value of the i-th PU and y i1  indicates the distortion between the original pixel value and the reconstructed pixel value of the i-th PU. Subsequently, the curve fitting module  240  may calculate values a 1 , b 1 , c 1  and d 1  using the Equation (4): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               1 
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 3 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 4 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 5 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 4 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 5 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 6 
                               
                             
                           
                         
                       
                       ] 
                     
                     · 
                     
                       [ 
                       
                         
                           
                             
                               a 
                               1 
                             
                           
                         
                         
                           
                             
                               b 
                               1 
                             
                           
                         
                         
                           
                             
                               c 
                               1 
                             
                           
                         
                         
                           
                             
                               d 
                               1 
                             
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               y 
                               
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 1 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                               · 
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 2 
                               
                               · 
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                                 3 
                               
                               · 
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   1 
                                 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Finally, the curve fitting module  240  obtains the fit-curve calculated according to the distortions SAD and the distortions D by carrying a 1 , b 1 , c 1  and d 1  into the Equation (5): 
         [0000]        y   1 ( x )= a   1   ·x   3   +b   1   ·x   2   +c   1   ·x+d   1    (5)
 
         [0019]    Specifically, for the curve fitting of the value R, the curve fitting module  240  may obtain absolute values V of syntax of residuals of N different PUs (Prediction Units) of the frame from the intra-frame/inter-frame prediction module  210 , and obtain bit counts R required to encode the syntax of the PUs of the frame from the entropy coding module  220 , so as to obtain N pairs of [x i2 , y i2 ], where x i2  indicates the absolute value of syntax of residual of the i-th PU and y i2  indicates the bit count required to encode the syntax of the i-th PU. Subsequently, the curve fitting module  240  may calculate values a 2 , b 2 , c 2  and d 2  using the Equation (6): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               1 
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 3 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 2 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 4 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 5 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 3 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 4 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 5 
                               
                             
                           
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                                
                               
                                   
                               
                                
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 6 
                               
                             
                           
                         
                       
                       ] 
                     
                     · 
                     
                       [ 
                       
                         
                           
                             
                               a 
                               2 
                             
                           
                         
                         
                           
                             
                               b 
                               2 
                             
                           
                         
                         
                           
                             
                               c 
                               2 
                             
                           
                         
                         
                           
                             
                               d 
                               2 
                             
                           
                         
                       
                       ] 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               y 
                               
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 2 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                               · 
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 2 
                               
                               · 
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               N 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 x 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                                 3 
                               
                               · 
                               
                                 y 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Finally, the curve fitting module  240  obtains the fit-curve calculated according to the syntax of residuals V and the bit counts R by carrying a 2 , b 2 , c 2  and d 2  into the Equation (7): 
         [0000]        y   2 ( x )= a   2   ·x   3   +b   2   ·x   2   +c   2   ·x+d   2    (7)
 
         [0020]      FIG. 3  is a flowchart illustrating a method of video encoding according to an embodiment of the invention. The method is employed in the system as shown in  FIG. 2 . First, a first frame is encoded (step S 310 ). Next, a loop is repeatedly performed to encode the next frame (step S 330 ) until a VS (Video Sequence) is completed encoded (the “Yes” path of step S 350 ). In step S 310 , RDO is not performed. When it is determined how to divide blocks, only the distortions SAD between the original frame and the predicted frame are used to perform the determinations, that is, J=SAD. Specifically, the intra-frame/inter-frame prediction module  210  directly employs the distortions SAD between the original frame and the predicted frame to perform block divisions. After the determinations, the intra-frame/inter-frame prediction module  210  may obtain the best block-division mode and record information regarding values SAD, residuals, MVs and reference frame, or others, under the best block-division mode. Subsequently, the T (Transform)  271 , the Q (Quantization)  273 , the IQ (Inverse Quantization)  275 , the IT (Inverse Transform)  277 , the entropy coding  220  and the reconstruction  279  are calculated for each block. The entropy coding module  220  records the bit counts R required in the entropy encoding and the bit counts R are output to the curve fitting module  240 . In addition, the distortion calculation module  230  calculates the distortions D between the original frame F and the reconstructed frame F′ and the distortions D are output to the curve fitting module  240 . After collecting the required values, the curve fitting module  240  obtains the fit-curve y 1 (x) for the distortions D and the fit-curve y 2 (x) for the required bit counts R using the Equations (4), (5), (6) and (7). In step S 330 , the fit-curves y(x) are used to perform RDO. Specifically, the intra-frame/inter-frame prediction module  210  calculates values SAD of PUs and outputs the values SAD of PUs to the curve fitting module  240 . The curve fitting module  240  carries the values SAD of PUs into the fit-curve y 1 (x) of the Equation (5) to obtain the fit distortions D′. The intra-frame/inter-frame prediction module  210  further calculates absolute values of syntax of residuals V of PUs and outputs the absolute values of syntax of residuals V of PUs to the curve fitting module  240 . The curve fitting module  240  carries the absolute values of syntax of residuals V of PUs into the fit-curve y 2 (x) of the Equation (7) to obtain the fit bit counts R′ r  of PUs. All fit bit counts are summed to obtain a total amount of the fit bit counts R′. The RD cost calculation module  250  calculates the fit RD cost J=D′+λ·R′ and outputs the fit RD cost to the intra-frame/inter-frame prediction module  210 . Subsequently, the intra-frame/inter-frame prediction module  210  employs the values J to determine the best block-division mode. In the meantime, the frame also needs to undergo the calculations of step S 310  to update the fit-curves y 1 (x) and y 2 (x). 
         [0021]    The curve-fitting module  240  and the RD cost calculation module  250  can be implemented in numerous ways, such as with dedicated hardware, or with general-purpose hardware (e.g., a single processor, multiple processors or graphics processing units capable of parallel computations, or others) that is programmed using microcode or software instructions to perform the functions recited herein. The intra-frame/inter-frame prediction module  210 , the entropy coding module  220 , the distortion calculation module  230 , the T  271 , the Q  273 , the IQ  275 , the IT  277  and the reconstruction  279  can be implemented in numerous ways, such as with dedicated hardware, or with general-purpose hardware that is programmed using microcode or software instructions to perform the functions recited herein. 
         [0022]    As to the block-division determinations, the intra-frame/inter-frame prediction module  210 , for example, may determine to divide one 16×16 CU (Coding Unit) into one of four 8×8 PUs, two 8×16 PUs and two 16×8 PUs. Or, the intra-frame/inter-frame prediction module  210  may determine to divide one 8×8 CU into one of four 4×4 PUs, two 4×8 PUs and two 8×4 PUs. 
         [0023]    Although the embodiments have been described in  FIG. 2  as having specific elements, it should be noted that additional elements may be included to achieve better performance without departing from the spirit of the invention. While the process flows described in  FIG. 1  includes a number of operations that appear to occur in a specific order, it should be apparent that these processes can include more or fewer operations, which can be executed serially or in parallel (e.g., using parallel processors or a multi-threading environment). 
         [0024]    While the invention has been described by way of example and in terms of the preferred embodiments, it should be understood that the invention is not limited to the disclosed embodiments. On the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.