Abstract:
A method of fast motion estimation in VLSI architecture with low-power and high-throughput for multimedia System-on-Chip design is disclosed. The method uses the data prediction and data reuse technique to find out the best matching block within the search range of the reference frame for the target block in the current frame in order to obtain the respective motion vector. The external memory bandwidth and the internal memory size in the video coding system are significantly reduced so as to speed up the process of motion estimation and most of the power consumption for the motion estimation process is further saved in the embedded video coding systems.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates generally to a method of fast motion estimation, and more particularly to a method employing data prediction and data reuse technique for fast motion estimation. 
         [0003]    2. The Prior Arts 
         [0004]    In order to save the storage medium space for storing image data and reduce the bandwidth used for transmitting the image data, original image data is often compressed to obtain compressed image data. When the image data is to be displayed, the compressed image data is recovered to displayable image data by executing a decompression process. The compression process is known as a coding process, while the decompression process is known as a decoding process. 
         [0005]      FIG. 1  is a block diagram schematically illustrating the operation of a conventional image data coding system. Referring to  FIG. 1 , the image data coding system includes motion estimation S 10 , motion compensation S 12 , block codes S 14 , and variable length codes S 16 , by which P-frame bitstream, i.e., the compressed data, can be generated. Among the foregoing, the motion estimation S 10  occupies very much system resources, such as memory space, computation time, and power consumption. Generally speaking, the motion estimation may occupy 76% of memory access, 77% of memory bandwidth, and 78% of computation time. As such, it is very highly desired to enhance the efficiency of the motion estimation S 10  and improve the entire coding efficiency. 
         [0006]      FIG. 2  is a schematic diagram illustrating the motion prediction of the conventional technology. Referring to  FIG. 2 , a search range  50  is selected from a reference frame  40  according to a current block  30  in a current frame  20 . Then, a best matching algorithm (BMA) is utilized to find out a best matching block  60  from all reference blocks in the search range  50 , thus obtaining a corresponding motion vector provided for subsequent variable length codes S 16 . Supposing that the current block  30  is an N×N block, in which N represents a side length of the current block, e.g., 16 as exemplified hereby. The BMA is defined by the following equation. 
         [0000]    
       
         
           
             
               S 
                
               
                   
               
                
               A 
                
               
                   
               
                
               
                 D 
                  
                 
                   ( 
                   
                     i 
                     , 
                     j 
                   
                   ) 
                 
               
             
             = 
             
               
                 ∑ 
                 
                   m 
                   = 
                   0 
                 
                 15 
               
                
               
                 
                   ∑ 
                   
                     n 
                     = 
                     0 
                   
                   15 
                 
                  
                 
                    
                   
                     
                       X 
                        
                       
                         ( 
                         
                           m 
                           , 
                           n 
                         
                         ) 
                       
                     
                     - 
                     
                       Y 
                        
                       
                         ( 
                         
                           
                             m 
                             + 
                             i 
                           
                           , 
                           
                             n 
                             + 
                             j 
                           
                         
                         ) 
                       
                     
                   
                    
                 
               
             
           
         
       
     
         [0000]    In the equation, SAD represents a sum of absolute differences (SAD), X(m, n) represents the image data of the current block  30  at coordinates (m, n), Y(m+i, n+j) represents the image data of the reference block at coordinates (m+i, n+j), in which i is a horizontal coordinate, and j is a vertical coordinate, and i and j are integers. The best matching block  60  is reference block having a minimum SAD value. MV(i, j) shown in  FIG. 2  represents a motion vector directed from coordinates (m, n) to coordinates (m+i, n+j). 
         [0007]      FIG. 3  is a functional block diagram illustrating a conventional image data coding system. Referring to  FIG. 3 , a conventional image data coding system  1  includes an encoder  70 , for searching for a best matching block  60  in the search range  50  of the reference frame  40 . The encoder  70  loads data stored in an external memory  84  via an external bus  90  and a memory interface  82 . The data stored in the external memory  84  is the data of the reference block in the search range  50 . The encoder  70  includes an encoding engine  72 , an internal memory  74 , and a computation engine  76 . The internal memory  74  is adapted for storing the data loaded from the external memory  84 . The computation engine  76  executes a logical computation to obtain the SAD value. The encoding engine  72  finds out the best matching block  60  having the minimum SAD according to the SAD value obtained by the computation engine  76 . 
         [0008]    For calculating the SAD value, data of the external memory  84  must be very frequently loaded to the internal memory  74 . As such, the external bus  90  is required for a large data bandwidth, and the computation engine  76  has to deal with a very heavy load, so that the entire coding efficiency is drastically impaired. Further, a longer time that the computation lasts means a higher power it consumes, thus shortening the operation time of the handheld apparatus is supplied with power by a battery system. Moreover, more data needed to load means a larger capacity of memory required, which inevitably increases the hardware cost of the coding system. As such, several data access schemes for accessing data of the search range are proposed by the conventional technology for saving data transmission and enhancing data reuse. The data access schemes include Level A, Level B, Level C, Level D, and Level C+. 
         [0009]      FIG. 4  is a schematic diagram illustrating the search range of the conventional BMA. Referring to  FIG. 4 , the search range  50  has a width SR H +N−1, a height SR V +N−1, a horizontal searching range SR H , and a vertical searching range SR V . A reference block  61  positioned at a center point of the search range  50  is an N×N block, in which each of the values is counted by pixel as the unit thereof, and SR H =2P H , and SR V =2P V . 
         [0010]      FIG. 5  is a schematic diagram illustrating the Level A scheme of the conventional technology. Referring to  FIG. 5 , in the search range  50 , an overlap region  62  between two successive reference blocks is shown as the dashed region in  FIG. 5 . As such, whenever a next reference block is searched, N×1 pixels data must be loaded from the external memory  82  in advance. Therefore, the size of the internal memory  74  is N×(N−1). However, when data is frequently accessed, the external bus  90  suffers a very heavy load, and the data is not effectively reused. 
         [0011]      FIG. 6  is a schematic diagram illustrating the Level B scheme of the conventional technology. Referring to  FIG. 6 , a search band  51  of the search range  50  in the external memory  82 , as a whole, is retrieved by the coding system. The search band  51  has a width SR H +N−1, and a height N. The coding system obtains the SAD value of a corresponding reference block from the search band  51 . An overlap region  62  of two successive search bands  51  and  52  is shown as the dashed region in  FIG. 6 . The overlap region  62  occupies a size (N−1)×(SR H +N−1) of the internal memory  74 . The data in the overlap region  62  can be reused according to the Level B scheme. In other words, when the coding system executes a next time SAD calculation, the data in the overlap region  62  is not required to be reloaded into the internal memory anymore. Such data has been loaded in advance, and only data of 1×(SR H +N−1) is required to be loaded therein. Therefore, the data load bandwidth can be drastically reduced. 
         [0012]      FIG. 7  is a schematic diagram illustrating the Level C scheme of the conventional technology. Referring to  FIG. 7 , the coding system divides the data of the search range  50  into two stages for loading into the internal memory  74 . At the first time, a search band  51  is loaded. The search band  51  has a width SR H +N−1, and a height SR V +N−1. Then the SAD value is calculated, in which the two successive current blocks CB 0 , CB 1  are selected from left to right as indicated by the arrow shown thereby. Then, another search band  52  is loaded. The search band  52  has a width SR H +N−1, and a height SR V +N−1. However, there is an overlap region  62  between the search band  51  and the search band  52  existed as shown as the dashed region in  FIG. 7 . As such, only data of (N+SR V −1)×(N+SR H −1) is required to be loaded. In other words, the size of the internal memory  74  is (N+SR V −1)×(N+SR H −1). Comparing with Level B scheme, the Level C scheme only needs to twice retrieve data from the external memory, and therefore the data load bandwidth can be drastically reduced. 
         [0013]      FIG. 8  is a schematic diagram illustrating the Level D scheme of the conventional technology. Referring to  FIG. 8 , the Level D scheme is similar to the Level C scheme discussed above. The coding system divides the data of the search range  50  into two stages, i.e., search bands  51  and  52 , for loading into the internal memory  74 . Different from the Level C scheme shown in  FIG. 7 , in which the search bands are vertically partitioned, the Level D scheme shown in  FIG. 8  horizontally partitions the search bands. The search bands  51 ,  52  have a width SR H +W−1, a height SR V +N−1, in which W is the width of an image. The overlap region  62  of the search bands  51 ,  52  is shown as the dashed region in  FIG. 8 . Further, two successive current blocks CB 0  and CB 1  are selected from upside to downside. Therefore, the size of the internal memory  74  is (SR H +W−1)×(SR V −1). 
         [0014]      FIG. 9  is a schematic diagram illustrating the Level C+ scheme of the conventional technology. Referring to  FIG. 9 , the Level C+ scheme is similar to the Level C scheme and the Level D scheme discussed above. According to the Level C+ scheme, the search range  50  is horizontally partitioned and vertically partitioned into four for loading. As such, the size of the internal memory  74  is (SR H +N−1)×(SR V +nN−1), in which n=2. The four successive current blocks CB 0 , CB 1 , CB 2 , and CB 3  are selected in a zigzag manner, indicated by the arrow shown in  FIG. 9 . 
         [0015]    The load bandwidth BW of the external bus  90  is represented by the following equation: 
         [0000]    
       
      
       BW=f×W×H×N×Ra,  
      
     
         [0000]    in which f represents the frame rate, N represents the number of the searched reference frames, W represents the frame width, H represents the frame height, and Ra represents the average external pixel access count for each current pixel in its motion estimation process, and can be defines as: 
         [0000]        Ra =total number of external memory accesses in task/the current pixel count in task 
         [0016]    As such, Ra of the Level A scheme can be expressed as: 
         [0000]    
       
         
           
             
               Ra 
               = 
               
                 
                   SR 
                   V 
                 
                 × 
                 
                   ( 
                   
                     1 
                     + 
                     
                       
                         SR 
                         H 
                       
                       N 
                     
                   
                   ) 
                 
               
             
             ; 
           
         
       
     
         [0017]    Ra of the Level B scheme can be expressed as: 
         [0000]    
       
         
           
             
               Ra 
               = 
               
                 
                   ( 
                   
                     1 
                     + 
                     
                       
                         SR 
                         V 
                       
                       N 
                     
                   
                   ) 
                 
                 × 
                 
                   ( 
                   
                     1 
                     + 
                     
                       
                         SR 
                         H 
                       
                       N 
                     
                   
                   ) 
                 
               
             
             ; 
           
         
       
     
         [0018]    Ra of the Level C scheme can be expressed as: 
         [0000]    
       
         
           
             
               Ra 
               = 
               
                 
                   N 
                   × 
                   
                     
                       
                         SR 
                         V 
                       
                       + 
                       N 
                       - 
                       1 
                     
                     
                       N 
                       × 
                       N 
                     
                   
                 
                 = 
                 
                   1 
                   + 
                   
                     
                       SR 
                       V 
                     
                     N 
                   
                 
               
             
             ; 
           
         
       
     
         [0019]    Ra of the Level D scheme can be expressed as: Ra=1; and 
         [0020]    Ra of the Level C+ scheme can be expressed as: 
         [0000]    
       
         
           
             Ra 
             = 
             
               
                 N 
                 × 
                 
                   
                     
                       SR 
                       V 
                     
                     + 
                     nN 
                     - 
                     1 
                   
                   
                     N 
                     × 
                     nN 
                   
                 
               
               = 
               
                 1 
                 + 
                 
                   
                     
                       SR 
                       V 
                     
                     nN 
                   
                   . 
                 
               
             
           
         
       
     
         [0021]    Comparing the load bandwidths corresponding to the foregoing Level A, Level B, Level C, Level D, and Level C+ schemes, it can be learnt that the Level C scheme and the Level C+ scheme have relative good reusability. 
         [0022]    However, the Level C and Level C+ schemes require for more internal memory spaces, for saving a large amount of image data of the search ranges, thus reducing the data accessing frequency of accessing the external memory. In other words, the hardware cost is traded off for saving the computation time and reducing the load bandwidth. Therefore, the Level C and Level C+ schemes have not solved the problems as expected. 
         [0023]    Further, according to the Level C and Level C+ schemes, the best matching blocks are found out by a full search block matching algorithms (FSBMA). Although easy to apply, the schemes do not have high search efficiency, and do not have an improved search speed. As such, the coding system still consumes too much power. 
         [0024]    Therefore, a method for fast estimation prediction which is adapted for reducing the load bandwidth and saving hardware cost is highly desired for employing a fast searching method with a high data reusability for solving the disadvantages of the conventional technology, i.e., high data load bandwidth and slow searching speed, without changing the architecture of the coding system. 
       SUMMARY OF THE INVENTION 
       [0025]    A primary objective of the present invention is to provide a data predication method for a memory. According to the data prediction method, desired data is transmitted to the internal memory by data prediction. Then, a data reuse technique is used for reducing the data load bandwidth of retrieving data from an external memory, and saving the power consumption of the coding system. In such a way, the best matching block which is best matched with a target block is searched from the search range of the reference frame. Then, a motion vector is obtained for completing the motion prediction process of the coding operation. 
         [0026]    A further objective of the present invention is to provide a data prediction method for a fast memory. According to the data prediction method, the data can be transmitted through the data bus with a less time, thus increasing the searching speed. Therefore, the power consumption of the coding system can be saved, and less internal memory space is required, so that the hardware cost and the overall power consumption can be saved. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0027]    The present invention will be apparent to those skilled in the art by reading the following detailed description of a preferred embodiment thereof, with reference to the attached drawings, in which: 
           [0028]      FIG. 1  is a block diagram schematically illustrating the operation of a conventional image data coding system; 
           [0029]      FIG. 2  is a schematic diagram illustrating the motion prediction of the conventional technology; 
           [0030]      FIG. 3  is a functional block diagram illustrating a conventional image data coding system; 
           [0031]      FIG. 4  is a schematic diagram illustrating the search range of the conventional BMA; 
           [0032]      FIG. 5  is a schematic diagram illustrating the Level A scheme of the conventional technology; 
           [0033]      FIG. 6  is a schematic diagram illustrating the Level B scheme of the conventional technology; 
           [0034]      FIG. 7  is a schematic diagram illustrating the Level C scheme of the conventional technology; 
           [0035]      FIG. 8  is a schematic diagram illustrating the Level D scheme of the conventional technology; 
           [0036]      FIG. 9  is a schematic diagram illustrating the Level C+ scheme of the conventional technology; 
           [0037]      FIG. 10  is a flow chart illustrating a method of fast motion estimation according to an embodiment of the present invention; 
           [0038]      FIG. 11  is a schematic diagram illustrating a fast motion estimation plane according to an embodiment of the present invention; 
           [0039]      FIG. 12  is a schematic diagram illustrating a searching path for searching for a standard image according to the method of fast motion estimation of the present invention; and 
           [0040]      FIG. 13  is a schematic diagram illustrating a searching path for searching for another standard image according to the method of fast motion estimation of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0041]    The accompanying drawings are included to provide a further understanding of the invention, and are incorporated in and constitute a part of this specification. The drawings illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention. 
         [0042]    The present invention provides a method of fast motion estimation. The method of fast motion estimation is adapted for conducting a motion estimation process in two stages, i.e., building a rapid prediction plane and utilizing a high effective search path.  FIG. 10  is a flow chart illustrating a method of fast motion estimation according to an embodiment of the present invention.  FIG. 11  is a schematic diagram illustrating a fast motion estimation plane according to an embodiment of the present invention. For better understanding the operation procedure of the present invention, please refer to  FIGS. 10 and 11  together. 
         [0043]    First at step S 110 , a motion data of the current block of the coding data is retrieved, and then the flow goes to step S 120 . At step S 120 , a rapid prediction plane is set up according to a significantly strong spatial correlation of motion vectors of three neighboring blocks of the current block, in which the neighboring blocks of the current block includes a left block, an upper block, and an upper-left block. According to the rapid prediction plane, the method of fast motion estimation predicts the motion vector of the current block in the search range, and thus predicts a search path of the current block in the search range. As such, the method of fast motion estimation of the present invention is adapted for more effectively saving the searching time, accelerating the searching speed, saving the computation power consumption, and improving the overall efficiency of the searching process. 
         [0044]    As shown in  FIG. 11(   a ), assuming that in the two-dimensional (2-D) real space current frame with each pixel size equaling one unit, the coordinates of a center of the current block is set at (0, 0), then three blocks most adjacent to the current block CB are a left block MB 1 , an upper-left block MB 2 , and the upper block MB 3 , positioned at the left side MB 1 , the upper-left side, and the upper side of the current block CB, respectively. The center of the left block MB 1  has the coordinates of (−16, 0). The center of the upper-left block MB 2  has the coordinates of (−16, 16). The center of the upper block MB 3  has the coordinates of (0, 16). Further, the left block MB 1  has a motion vector MV 1 . The upper-left block MB 2  has a motion vector MV 2 . The upper block MB 3  has a motion vector MV 3 . The rapid prediction plane is set up according to the equation as following. 
         [0000]    
       
         
           
             
               
                 X 
                 a 
               
               + 
               
                 Y 
                 b 
               
               + 
               
                 
                   Z 
                    
                   
                     ( 
                     
                       X 
                       , 
                       Y 
                     
                     ) 
                   
                 
                 c 
               
             
             = 
             1. 
           
         
       
     
         [0000]    where (x, y) is the coordinate of the block center and Z(x, y) is the correlated motion vector of the coordinate (x, y), and a, b, and c are respectively represented as: 
         [0000]        a= 16×( MV   1   −MV   2   +MV   3 )/( MV   2   −MV   3 ) 
         [0000]        b= 16×( MV   1   −MV   2   +MV   3 )/( MV   1   −MV   2 ) 
         [0000]    
       
      
       c=MV 
       1 
       −MV 
       2 
       +MV 
       3  
      
     
         [0045]    Referring to  FIG. 11(   b ), there are shown the rapid prediction plane set up according to the motion vectors MV 1 , MV 2 , and MV 3 , and there is also shown the estimated motion vector of the current block CB. If the motion vectors of the nearest adjacent blocks of the current block CB (e.g., the upper-leftmost current block) are not available, then the time correlated motion vector of the same spatial position is employed for estimating the current motion vector. 
         [0046]    Further, as shown in  FIG. 10 , after step S 120 , the flow goes to step S 130 . At step S 130 , a best matching algorithm, e.g., the diamond search algorithm, is selected, according to the fast-search BMA. The diamond search algorithm includes four points, upper, left, lower, and right points which are equally distant from the target point as a center thereof for a distance. 
         [0047]    After step S 130 , the flow goes to step S 140 . At step S 140 , the search path of each current block in the search range is predicted for each fast-search BMA, and the BMA is calculated for obtaining the best matching block, thus obtaining the a motion vector of the current block relative to the best matched reference block. Taking the diamond search algorithm for example, a best matched point, i.e., a point corresponding to the block having the minimum SAD value, regarding blocks corresponding to the upper, left, lower, and right points is achieved. Then, four points, upper, left, lower, and right points, which are equally distant from the achieved best matched point as a center thereof for a half of the distance are achieved. And then a next best matched point is obtained regarding blocks corresponding to the presently achieved upper, left, lower, and right points, and so forth. The method of fast motion estimation according to the present invention loads the whole data within the predicted search path of current blocks. As such, the method of fast motion estimation according to the present invention not only reuses the data from different search steps to avoid blind data transfer between internal memory and the computation engine, but also avoids loading unnecessary data to the internal memory for each fast-search BMA. Additionally, the method of fast motion estimation according to the present invention reuses data of the two overlapped search paths of two horizontal adjacent blocks, and therefore can reduce the data bandwidth of the external memory and the size of the internal memory. 
         [0048]      FIG. 12  is a schematic diagram illustrating a searching path for searching for a standard image according to the method of fast motion estimation of the present invention. Referring to  FIG. 12 , the search range  50  is exemplified as having a width  64  and a height  48 . The search range  50  is partitioned into two search bands  51 , and  52 . An overlap region of the search band  51  and  52  is 32×48, where each chequer represents a pixel  35 . Taking the blocks CB 13 , CB 14  in the search range  50  for example for further illustration, both of the current blocks CB 13  and CB 14  have a size 16×16, and the current block CB 13  has a motion vector MV 13 , and the current block CB 14  has a motion vector MV 14 . The current block CB 13  has a search path, i.e., search algorithm  33 , and the current block CB 14  has a search path, i.e., search algorithm  34 . The search algorithms  33  and  34  for example are exemplified by the diamond search algorithm. It should be noted, that the method of fast motion estimation shown in the current embodiment uses the search algorithm having a search space with one pixel as a searching unit. In other words, distance of the upper, lower, left, and right points of the search algorithms are one pixel. Therefore, the data required to be loaded for a next search is  16 . As such, the method of fast motion estimation is adapted for very effectively searching, and thus improving the blindly searching disadvantage of the conventional technology. 
         [0049]    In the current embodiment, the image pattern employed in  FIG. 12  is a test image sequence “Container” defined by the Standard Association, i.e., an image that exhibits a lower mobility and regular variation. It can be learnt from  FIG. 12 , the current block  13  rapidly obtains the desired best matched point according to the search algorithm  33 , and then the next current block CB 14  is going to be processed. The internal memory required for processing the current block CB 14  is  320 , and the external memory bandwidth required for processing the current block CB 14  is  288 . Comparing with the Level C scheme, the size of the internal memory of the current embodiment is about 14.5% of that of the Level C scheme, and the external memory bandwidth of the current embodiment is about 38.3% of that of the Level C scheme. 
         [0050]      FIG. 13  is a schematic diagram illustrating a searching path for searching for another standard image according to the method of fast motion estimation of the present invention. Referring to  FIG. 13 , the image pattern employed in  FIG. 13  is a test image sequence “Stefan” defined by the Standard Association, i.e., an image that exhibits a higher mobility and an irregular variation. As shown in  FIG. 13 , the current blocks CB 51 , CB 52  have corresponding search algorithms  37 ,  38 . Comparing with  FIG. 12 , the search algorithms  37 ,  38  have more search points, and therefore more search comparison processing is required for obtaining the best matching block. Comparing with the Level C scheme, the ratio of required internal memory size is 28% of that of the Level C scheme, and the ratio of require external memory bandwidth 64% of that of the Level C scheme. 
         [0051]    As such, it can be learnt from the standard images respectively shown in  FIGS. 12 and 13  that the method of fast motion estimation of the present invention requires less internal memory size and lower external memory bandwidth. However, it should be noted that although exemplified with the diamond search algorithm, the present invention is not restricted as must employ the diamond search algorithm. Other search algorithms can also be employed as an alternative. For example, a three-step search algorithm can be employed. The three-step search algorithm is executed according to a square having a predetermined side length outbound expanded from a center (i.e., the center of the current block). Nine points positioned at upper-left, upper, upper-right, right, lower-right, lower, lower-left, left, and center of the square are selected as the pixel points for search comparison. After finding out the best matched point, the best matched point is taken as a new center point, and a half of the predetermined side length is taken as a new side length to define a new square regarding the new center point and the new side length. In a similar manner, eight points positioned at upper-left, upper, upper-right, right, lower-right, lower, lower-left, and left of the new square are selected as the pixel points for a next stage of comparison processing, and so forth to find out a best matched point corresponding to the new square. The best matched point corresponding to the new square corresponds to a reference block which is the best matching block required by the current block. 
         [0052]    Although the present invention has been described with reference to the preferred embodiments thereof, it is apparent to those skilled in the art that a variety of modifications and changes may be made without departing from the scope of the present invention which is intended to be defined by the appended claims.