Abstract:
The claimed invention relates to efficient use of data for multiple reference picture motion estimation. Multiple reference picture motion estimation involves a large amount of data due to the processing of multiple reference pictures. The claimed invention discloses a method  101  and a system for implementing this method to reduce the memory size required for data storage and the bandwidth required for data loading. The claimed invention thus improves the efficiency of performing multiple reference picture motion estimation.

Description:
RELATED APPLICATION 
       [0001]    There are no related applications. 
       TECHNICAL FIELD 
       [0002]    The claimed invention relates generally to image/video signal processing. In particular, the claimed invention relates to motion estimation for video encoding and motion detection. In particular, the motion estimation in the claimed invention refers to multiple reference picture motion estimation. Furthermore, the claimed invention relates to efficient use of data for multiple reference picture motion estimation. The claimed invention is applicable in motion estimation algorithm with fixed search range as well as motion estimation algorithm with non-fixed search range. 
       SUMMARY OF THE INVENTION 
       [0003]    For transmission or other purposes, a digital video is encoded to reduce the video size and thus the bandwidth required. At the receiver side, the encoded digital video will be decoded to reproduce the digital video. 
         [0004]    Motion estimation is a common technique used in various video coding. Motion estimation exploits the temporal redundancy to achieve bandwidth reduction because a video is simply a series of pictures (also known as frames), and the content of these pictures is repetitive as the pictures share similar scenes or objects. Therefore, data required for transmission can be reduced if the pattern of how they are going to repeat themselves in the subsequent pictures is known. 
         [0005]    In order to know the pattern of how data are going to repeat themselves in the subsequent pictures, pictures need to be compared with one another to see how they match with each other. For example, in order to encode a picture, another picture which immediately precedes the picture to be encoded is used for comparison. In order to enhance the accuracy of the comparison result, more than one picture which are neighbors to the picture to be encoded are used, for example, an object in a picture may fail to appear in the immediate subsequent picture and cannot be matched because it may be blocked by a moving car; however, it will appear in the following pictures for matching to be done after the moving car has gone. These pictures which are used for comparing with the picture to be encoded are known as reference pictures, therefore, motion estimation which makes use of multiple reference pictures is generally known as multiple reference picture motion estimation. The picture to be encoded is generally known as current picture. 
         [0006]    To process those pictures, a huge computation power or memory size is required if the processing is done in a picture-by-picture manner. Therefore, pictures are further divided into smaller units known as blocks (macroblock is one kind of blocks) for processing. A picture block is a block in a picture, and the terms “picture block” and “block” are used interchangeably hereinafter. 
         [0007]    For motion estimation involving multiple reference pictures, multiple reference blocks of multiple reference pictures are required to be loaded into the internal memory, for example, cache, from an external memory, for example, RAM (random access memory), in order to process a current picture. However, a problem arises; firstly, the loading of data from external memory to internal memory takes time. Therefore, it is time-consuming if each block in a current picture needs to wait for multiple reference blocks of multiple reference pictures to be loaded before performing multiple reference picture motion estimation. Secondly, the storage of multiple reference blocks of multiple reference pictures for each block in a current picture requires a large internal memory. 
         [0008]    Therefore, instead of having to wait for loading multiple reference blocks of multiple reference pictures into internal memory, the claimed invention provides a solution to save time and to reduce the size requirement of the internal memory. 
         [0009]    In order to achieve such efficiency improvement, the claimed invention adopts three approaches as follows; firstly, at each time instance, one or more current pictures are compared with a single reference picture concurrently. That means multiple current pictures may be referenced to a single reference picture concurrently and processing such as encoding and motion estimation is performed for each of these multiple current pictures in parallel. Therefore, reference blocks of each reference picture need not be loaded into the internal memory or be present in the internal memory for multiple time instances because all current pictures which are required to reference to this reference picture have done so within a single time instance. 
         [0010]    Secondly, instead of waiting all the multiple reference pictures to be available for processing, each current picture is processed with one reference picture at a time. Therefore, there is no need to wait for the loading of multiple blocks of multiple reference pictures and no huge memory size is required to hold all the multiple blocks of multiple reference pictures. 
         [0011]    Thirdly, the claimed invention does not limit the reference picture type, the reference picture can be the original raw picture, the reconstructed picture, synthesis picture and so on. 
         [0012]    In this document, the terms “frame” and “picture” are used interchangeably hereinafter to represent a picture in a video. For a multiple reference picture motion estimation, a current picture, which may be under encoding, references to one or more reference pictures. The claimed invention allows multiple current pictures which are under processing to reference to a single reference picture. The claimed invention reuses the overlapped searching region without any shift operation. 
         [0013]    Consequently, at any time instance, not all the multiple blocks of multiple reference pictures are required to be loaded into the internal memory. The size of the internal memory of the claimed invention is reduced and the idle time before processing a current picture to wait for the internal memory to be loaded with multiple blocks of multiple reference pictures is reduced. Search window data for temporally adjacent reference blocks, i.e. the reference pictures, are thus reused. Memory bandwidth is reduced because not all multiple reference pictures are required to be loaded at a time. 
         [0014]    The claimed invention is suitable for FPGA and DSP implementation among others. 
         [0015]    It is an object of the claimed invention to not only consider the single reference picture motion estimation data reuse and internal memory reduction but also consider the multiple reference picture motion estimation algorithm. The claimed invention also overcomes the limitation of the parallel operation of direct memory access (DMA) and motion estimation (ME) as well as some limitations to the motion estimation precision. The claimed invention enables the parallel running of multiple reference search modules so that searches are performed for one or more current pictures simultaneously. 
         [0016]    It is a further object of the claimed invention to simplify the control logic of reference blocks loading to support different block types (such as 16×16/16×8/8×16/8×8 and others) multiple reference picture motion estimation. The claimed invention supports multiple inter block type as well as multiple block types and only needs to run interpolation module once to encode M block types rather than running interpolation module N×M times for supporting N reference pictures and M block types (M: 0-9) so that calculation overlay problem can be overcome. 
         [0017]    It is a further object to further decrease the bandwidth requirement by incorporating data reuse for block matching motion estimation into the claimed invention. The claimed invention fulfills low bandwidth requirements. 
         [0018]    It is a further object of the claimed invention to enable data reuse for multiple reference picture motion estimation. The claimed invention is capable to be combined with certain single picture data reuse methods, such as Level C, Level C+, to enhance the performance. 
         [0019]    It is a further object of the claimed invention to enhance the coding efficiency. The claimed invention decreases the algorithm control logic complexity. 
         [0020]    It is a further object of the claimed invention to enable the claimed invention to be applicable in motion estimation algorithm with fixed search range as well as motion estimation algorithm with non-fixed search range. 
         [0021]    It is a further object of the claimed invention to decrease the bus bandwidth and internal memory requirement. 
         [0022]    It is a further object of the clamed invention to decrease the algorithm control logic complexity. 
         [0023]    Other aspects of the claimed invention are also disclosed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0024]    These and other objects, aspects and embodiments of this claimed invention will be described hereinafter in more details with reference to the following drawings, in which: 
           [0025]      FIG. 1  shows a flow diagram of the processing for multiple reference picture motion estimation. 
           [0026]      FIG. 2  shows the content in internal memory and external memory at different time instances during coding for an embodiment where 5 reference pictures are used. 
           [0027]      FIG. 3  shows a block diagram of an embodiment of motion estimation process using double buffer. 
           [0028]      FIG. 4  shows an implementation example for five reference frames without B frame, having a coding pattern of IPPPPP. 
           [0029]      FIG. 5  shows an implementation example for two reference frames with one B frame (no hierarchic-B frame). 
           [0030]      FIG. 6  shows an implementation example for two reference frames with one B frame (no hierarchic-B frame), having a coding pattern of IBPBPBPBP, with parallel operations. 
           [0031]      FIG. 7  shows an implementation example for two reference frames with two B frames (no hierarchic-B frame), having a coding pattern of IBBPBBPBBPBBP. 
           [0032]      FIG. 8  shows an implementation example for two reference frames with three B frames (with hierarchic-B frame), having a coding pattern of IBbBPBbBPBbBPBbBP. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0033]      FIG. 1  shows a flow diagram of the processing for multiple reference picture motion estimation. Multiple current pictures are referenced to one single reference picture. There are N current pictures to make up the multiple current pictures. The parameter n is equal to the reference picture number. Current blocks with the same pixel position from different current pictures are loaded. If current blocks&#39; predict motion vectors point to different position, then a decision module is used to decide how large a reference block need to be loaded into an internal memory. 
         [0034]    In an embodiment, the following assumptions are made, and the data/parameters in use are for illustrative purposes whereas the method as illustrated is capable to be easily adapted to any other data/parameters: 
         [0035]    1. The encoder supports N reference pictures, n changes from 0 to N−1. 
         [0036]    2. The size of motion information (sizeof (blk_info)) is equal to 64 bytes: sizeof (blk_info)=64; 
         [0037]    3. Block width (blk_width) is equal to 16: blk_width=16; 
         [0038]    4. Block height (blk_height) is equal to 16 : blk_height=16; 
         [0039]    5. Search range (SR) is from −127 to 128, i.e., [−127, 128]: SR=128; 
         [0040]    6. Reference block width equal to ((SR&lt;&lt;1)+blk_width); 
         [0041]    7. Picture_width is the horizontal size of the picture; 
         [0042]    8. Picture_height is the vertical size of the picture; 
         [0043]    9. Frame_rate is the frame rate per second of the input video sequence. 
         [0044]    Furthermore, the following are defined for external memory organization: 
         [0045]    1. Original video sequences, which include current encoding picture, is curr_pic[n] whereas 0≦n&lt;N. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 curr_pic[0] (the 1 st  picture to be encoded, also representing the one 
               
               
                   
                 currently being encoded); 
               
               
                   
                 curr_pic[1] (the 2 nd  picture to be encoded); 
               
               
                   
                 ...... 
               
               
                   
                 curr_pic[N−1] (the N th  picture to be encoded). 
               
               
                   
                   
               
             
          
         
       
     
         [0046]    2. Reference picture is one of the previous reonstructed pictures: ref_pic. 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 ref_pic is curr_pic[0]’s 1 st  reference picture; 
               
               
                   
                 ref_pic is curr_pic[1]’s 2 nd  reference picture; 
               
               
                   
                 ....... 
               
               
                   
                 ref_pic is curr_pic[N−1]’s Nth reference picture. 
               
               
                   
                   
               
             
          
         
       
     
         [0047]    3. Predict pictures are pred_pic[n] whereas 0≦n&lt;N.
       Predict picture is formed by the predict blocks, which are saved to the external memory by motion estimation engine block by block.       
 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 pred_pic[0] is curr_pic[0]’s predict picture; 
               
               
                   
                 pred_pic[1] is curr_pic[1]’s predict picture; 
               
               
                   
                 ...... 
               
               
                   
                 pred_pic[N−1] is curr_pic[N−1]’s predict picture. 
               
               
                   
                   
               
             
          
         
       
     
         [0049]    4. Best Information pictures are info_pic[n] whereas 0≦n&lt;N.
       Best information picture is formed by the best info blocks, which are saved to the external memory by motion estimation engine block by block.       
 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 info_pic[0] is curr_pic[0]’s best information pictures; 
               
               
                   
                 info_pic[1] is curr_pic[1]’s best information pictures; 
               
               
                   
                 ...... 
               
               
                   
                 info_pic[N−1] is curr_pic[N−1]’s best information pictures. 
               
               
                   
                   
               
             
          
         
       
     
         [0051]    In addition to the external data organization, the following are defined for internal data organization: 
         [0052]    1. Memory for current block of curr_pic[n] is curr_blk[n] whereas 0≦n&lt;N; 
         [0053]    2. Memory for reference block of ref_pic is ref_blk; 
         [0054]    3. Memory for Motion information of curr_blk[n] is blk_info[n] whereas 0≦n&lt;N; 
         [0055]    4. Memory for Predict block data of curr_blk[n] is pred_blk[n] whereas 0≦n&lt;N; 
         [0056]    5. Reconstructed block data of curr_pic[ 0 ] is recon_blk whereas 0≦n&lt;N; 
         [0057]    6. 1 set of Half (½) pixel arrays and 1 set of quarter (¼) pixel arrays for ref_blk. Different fractional search algorithms lead to different fractional array sizes; 
         [0058]    7. Neighbor blocks&#39; motion information is neigh_info;
       a. Left blocks motion information is left_info;   b. Up row blocks motion information is up_info[block_col];   Different motion estimation algorithms need different neigh_info sizes.       
 
         [0062]    According to the above definitions, the encoding flow is defined as follows: 
         [0063]    Step 1: In a current picture loading step  101 , start with a new current picture (curr_pic[ 0 ]) in which the encoder are initialized. Correspondingly, the picture coding type and other related header information are determined before proceeding to the block encoding process. 
         [0064]    Step 2: Begin the block encoding process. For example, the encoder supports N reference frames. N current blocks are loaded from the subsequent N encoding current pictures to the internal memory. The N current blocks (curr_blk[n]) are loaded from the original video sequence in external memory to internal memory in the following way: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Load 1st curr_blk[0] from curr_pic[0]; 
               
               
                   
                 Load 2nd curr_blk[1] from curr_pic[1]; 
               
               
                   
                 ...... 
               
               
                   
                 Load Nth curr_blk[N−1] from curr_pic[N−1]; 
               
               
                   
                   
               
             
          
         
       
       
         
           
             As a result, the internal memory size for curr_blk[n] is: 
           
         
       
     
         [0000]        N× 16×16=256N bytes       If N is equal to 5, then the internal memory size is:         
         [0000]      256×5=1280 bytes       The bandwidth for data loading is Picture_width×Picture_height×frame_rate×N (bytes/second).         
         [0068]    Step 3: In a reference block loading step  102 , load one reference block (ref_blk) for all current block (curr_blk[n]) from a reference picture (ref_pic) in external memory to internal memory according to the search range. 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                 Load blk_info[n] for all curr_blk[n] from external memory to internal 
               
               
                 memory; 
               
               
                 Load ref_blk from ref_pic; 
               
               
                 Load blk_info[0] from pic_info[0] in external memory; 
               
               
                 Load blk_info[1] from pic_info[1] in external memory; 
               
               
                 ...... 
               
               
                 Load blk_info[N−1] from pic_info[N−1] in external memory; 
               
               
                   
               
             
          
         
       
       
         
           
             As a result, the internal memory for reference data is: 
           
         
       
     
         [0000]      ( SR× 2+blk_width)×( SR× 2+blk_height)=(128×2+16)×(128×2+16)=73,984 bytes       The bandwidth for reference data loading is:         
         [0000]      ( SR× 2+blk_width)×( SR× 2+blk_height)×total_block_number×frame_rate=(128×2+16)×(128×2+16)×total_block_number×frame_rate=73,984×total_block_number×frame-rate (bytes/second)       Whereas: total_block_number=Picture_width×Picture_Height/(blk_width×blk_height)   The internal memory size for block motion information is:         
         [0000]      sizeof(blk-info)× N= 64N bytes.       If N equal to 5, then the internal memory size is:         
         [0000]      64×5=320 bytes       Total internal memory for reference data and motion information is:         
         [0000]      73,984+320=74,304 bytes       The bandwidth for block motion information loading is:         
         [0000]      sizeof(blk_info)× N ×total_block_number×frame_rate=64×N×total_block_number×frame_rate bytes/second       Whereas: total_block_number=Picture_width×Picture_Height/(blk_width×blk-height)         
         [0077]    Step 4: In an integer pixel motion estimation step  103 , perform integer pixel motion estimation for all the current blocks (curr_blk[n]) by using the reference block (ref_blk). Find the best integer motion information blk_info[n], such as motion vectors, and the best integer matching blocks (pred_blk[n]) in the reference block (ref_blk) of the reference picture (ref_pic) for all the current blocks (curr_blk[n]). Each encoder can decide which motion estimation algorithm to be used. In general, motion estimation algorithms can be classified into three types: 
         [0078]    1. Fixed search center and fixed search range. This type of motion estimation algorithms are hardware friendly, most of the hardware design use this kind of motion estimation implementation. 
         [0079]    2. Non-fixed search center but with fixed search range which is not good for hardware implementation. 
         [0080]    3. Non-fixed search center and non-fixed search range which is bad for hardware implementation. 
         [0000]    
       
         
               
             
               
             
           
               
                   
               
               
                 Integer ME process flow: 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Search ref_blk for curr_blk[0]; 
               
               
                 Search ref_blk for curr_blk[1]; 
               
               
                 ...... 
               
               
                 Search ref_blk for curr_blk[N−1]; 
               
               
                 Find N best motion information blk_info[n] and N integer predict data 
               
               
                 pred_blk[n] from ref_blk for all the curr_blk[n]. 
               
               
                   
               
             
          
         
       
     
         [0081]    Step 5: In an interpolation step  104 , prepare the data for fractional search. Interpolate the half and quarter pixel arrays for the reference block (ref_blk). 
         [0082]    Interpolate the horizontal, vertical and cross half pixel arrays for ref_blk; 
         [0083]    Interpolate the horizontal, vertical and cross quarter pixel arrays for the reference block (ref_blk). 
         [0084]    Step 6: In a fractional pixel search step  105 , do fractional pixel search for all current blocks curr_blk[n] by using the half pixel and quarter pixel reference arrays, and get all the best matching block (pred_blk[n]), i.e. predict block in a predict picture and the motion information (blk_info[n]) corresponding to the best matching block (pre_blk[n]) after the fractional search has been finished. 
         [0085]    In a comparing step  106 , compare the results with the motion information which are obtained from Step 3 for all the current blocks (curr_blk[n]) and update the best results to the motion information (blk_info[n]) and the best matching block (pred_blk[n]). 
         [0086]    Step 7: In a best result updating step  107 , store the updated best matching block (pred_blk[n]) and the corresponding motion information (blk_info[n]) for all the current blocks (curr_blk[n]) back to the external memory if necessary. If the best matching block (pred_blk[n]) and the corresponding motion information (blk_info[n]) have not been updated, they do not need to be stored back to external memory again. 
         [0087]    So the maximum bandwidth for pred_blk[n] and blk_info[n] which are stored back to the external memory is: 
         [0000]        N ×(sizeof(blk_info)+(blk_width×blk_height))×total_block_number×frame_rate= N ×(64+16×16)×total_block_number×frame_rate=320N×total_block_number×frame_rate bytes/sonds       If N equal to 5, then the bandwidth is:         
         [0000]      320×5×total_block_number×frame_rate=1600×total_block_number×frame-rate bytes/second       Whereas: total_block_number=Picture_width×Picture_Height/(blk_width×blk_height)         
         [0090]    Step 8: In a reference block checking step  108 , if the current coding block&#39;s (curr_blk[ 0 ]) best matching block (pred_blk[ 0 ]) is not coming from the reference block (ref_blk), the encoder needs to load the best matching block (pred_blk[ 0 ]) from external memory in a best matching block loading step  118 . Otherwise, do nothing.
       So the maximum bandwidth for pred_blk[ 0 ] loading from external memory is:       
 
         [0000]      blk_width×blk_height×total_block_number×frame_rate=16×16×total_block_number×frame_rate=256×total_block_number×frame_rate (bytes/second)       Whereas: total_block_number=Picture_width×Picture_Height/(blk_width×blk_height)         
         [0093]    Step 9: In a difference block generating step  109 , obtain a difference block by subtracting the current coding block (curr_blk[ 0 ]) and the best matching block (pred_blk[ 0 ]). 
         [0094]    Step 10: In a processing step  110 , implement DCT/Quant/VLC/De-Quant/IDCT based on the Difference block obtained from the difference block generating step  109 . 
         [0095]    Step 11: In a reconstructing step  111 , reconstruct the current block to generate the reconstructed block (recon_blk). 
         [0096]    Step 12: Reconstructed block (recon_blk), store the reconstructed block (recon_blk) back to the external memory, if the current picture (curr_pic[ 0 ]) can be used as reference picture according to a reference picture checking step  122 , the reconstructed block (recon_blk) will be saved as the reference picture (ref_pic) into the reference picture list for next coming encoding picture, otherwise only store it to display picture buffer in a reconstructed block storing step  123 .
       The bandwidth for storing recon_blk to external memory is:       
 
         [0000]      blk_width×blk_height×total_block_number×frame_rate=(16×16)×total_block_number×frame_rate=256×total_block_number×frame_rate bytes/second       Whereas: total_block_number=Picture_width×Picture_Height/(blk_width×blk_height)         
         [0099]    Step 13: In a next block looping step  113 , if all the blocks in the current picture (curr_pic[ 0 ]) has been processed, go to Step 1 and begin to process the next encoding picture until all the pictures have been processed, then exit in a ending step  120 . Otherwise, go to Step 1 and continue to process the next block in the current picture (curr_pic[ 0 ]). 
         [0100]      FIG. 2  shows the content in internal memory and external memory at different time instances during coding for an embodiment where 5 reference pictures are used. Along the coding timeline  240 , internal memory at a first time instance  210  contains the coding all blocks in a current picture curr_pic[ 0 ] one by one. All the coding blocks are currently being encoded. The internal memory at a first time instance  210  also contains blocks from current pictures curr_pic[ 1 ], curr_pic[ 2 ], curr_pic[ 3 ] and curr_pic[ 4 ]. The internal memory at a second time instance  220  contains the coding all blocks in a current picture curr_pic[ 1 ], as well as blocks from current pictures curr_pic[ 2 ], curr_pic[ 3 ], curr_pic[ 4 ] and curr_pic[ 5 ]. The internal memory at a third time instance  230  contains the coding all blocks in a current picture curr_pic[ 2 ], as well as blocks from current pictures curr_pic[ 3 ], curr_pic[ 4 ], curr_pic[ 5 ] and curr_pic[ 6 ]. At any time instances, an external memory is used to store the best motion information (blk_info and the predict block (pred_blk) for a current picture. Assuming there are five reference pictures, the start address of the “blk_info &amp; pred_blk” stored in the SDRAM is calculated as follows: 
         [0000]      Addr_pic( n+ 0)=Start_Addr+sizeof(pic_info)×( n  % 5) 
         [0000]      Addr_pic( n+ 1)=Start_Addr+sizeof(pic_info)×( n  % 5+1) 
         [0000]      Addr_pic( n+ 2)=Start_Addr+sizeof(pic_info)×( n  % 5+2) 
         [0000]      Addr_pic( n+ 3)=Start_Addr+sizeof(pic_info)×( n  % 5+3) 
         [0000]      Addr_pic( n+ 4)=Start_Addr+sizeof(pic_info)×( n  % 5+4)       Whereas, Start_Addr is the start address of the “pic_info” stored in the SDRAM   pic_info is “blk_info” &amp; “pred_blk” of all the blocks in one picture.         
         [0103]    The best motion information (blk_info) and the predict block (pred_blk) for all blocks of the current picture curr_pic[ 0 ] are computed from the block from the current picture curr_pic[ 0 ] in the internal memory at the first time instance  210 . Then the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 0 ] is stored in the first address location  201  in the external memory. Starting from the second time instance, the first address location  201  in the external memory will be used to store the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 5 ] which are to be computed by the block from the current picture curr_pic[ 5 ] in the internal memory at the second time instance  220 , the block from the current picture curr_pic[ 5 ] in the internal memory at the third time instance  230 , the block from the current picture curr_pic[ 5 ] in the internal memory at the fourth time instance (not shown), the block from the current picture curr_pic[ 5 ] in the internal memory at the fifth time instance (not shown) and the block from the current picture curr_pic[ 5 ] in the internal memory at the sixth time instance (not shown). 
         [0104]    The best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 1 ] are computed from the block from the current picture curr_pic[ 1 ] in the internal memory at the first time instance  210  and the block from the current picture curr_pic[ 1 ] in the internal memory at the second time instance  220 . Then the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 1 ] is stored in the second address location  202  in the external memory. Starting from the third time instance, the second address location  202  in the external memory will be used to store the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 6 ] which are to be computed by the block from the current picture curr_pic[ 6 ] in the internal memory at the third time instance  230  and the 4 other processes for the current picture curr_pic[ 6 ] blocks in the internal memory at the subsequent 4 time instances (not shown). The best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 2 ] are computed from the block from the current picture curr_pic[ 2 ] in the internal memory at the first time instance  210 , the block from the current picture curr_pic[ 2 ] in the internal memory at the second time instance  220  and the block from the current picture curr_pic[ 2 ] in the internal memory at the third time instance  230 . Then the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 2 ] is stored in the third address location  203  in the external memory. 
         [0105]    The best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 3 ] are computed from the block from the current picture curr_pic[ 3 ] in the internal memory at the first time instance  210 , the block from the current picture curr_pic[ 3 ] in the internal memory at the second time instance  220 , the block from the current picture curr_pic[ 3 ] in the internal memory at the third time instance  230  and the block from the current picture curr_pic[ 3 ] in the internal memory at the fourth time instance (not shown). Then the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 3 ] is stored in the fourth address location  204  in the external memory. 
         [0106]    The best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 4 ] are computed from the block from the current picture curr_pic[ 4 ] in the internal memory at the first time instance  210 , the block from the current picture curr_pic[ 4 ] in the internal memory at the second time instance  220 , the block from the current picture curr_pic[ 4 ] in the internal memory at the third time instance  230 , the other two processes for the current picture curr_pic[ 4 ] blocks in the internal memory at the subsequently two time instances (not shown). Then the best motion information (blk_info) and the predict block (pred_blk) for the current picture curr_pic[ 4 ] is stored in the fifth address location  205  in the external memory. 
         [0107]      FIG. 3  shows a block diagram of an embodiment of motion estimation process using double buffer. A double buffer contains a first buffer  301  and a second buffer  302 . Five current blocks and a reference block are loaded into the first buffer  301 . Using the content in the first buffer  301 , five motion estimation operations ME 0 , ME 1 , ME 2 , ME 3  and ME 4  are performed in a motion estimation step  320 . At the same time another five current blocks and a reference block are loaded into the second buffer  302  in parallel with the ME process. In other words, one buffer is loaded with five current blocks and one reference block in a first step  310 , one buffer is used by ME process in motion estimation step  320 . In the meantime, the best motion information (blk_info) and the predict block (pred_blk) for the coding process of block BLK 0  and the best motion information for four blocks BLK 1 , BLK 2 , BLK 3  and BLK 4  in the first buffer  301  of the double buffer is used in the Mode decision step  340 . The best motion information (blk_info) and the predict block (pred_blk) for the next coding process of block BLK 0  and the best motion information for four blocks BLK 1 , BLK 2 , BLK 3  and BLK 4  are loaded into the second buffer  302  of the double buffer in the second loading step  330 . In a mode decision step  340 , the coding mode of whether inter mode or intra mode is used is decided for all blocks after receiving the data from the motion estimation step  320  and the second loading step  330 . Subsequently, the best motion information (blk_info) and predict block (pred_blk) are updated and stored into one of the first buffer  301  and the second buffer  302  in the double buffer for blocks BLK 1 , BLK 2 , BLK 3 , and BLK 4  in the step  350 . In an internal buffer update step  360 , the internal double buffers are exchanged for next operation. The whole process keeps iterated until it comes to a stop in a termination step  370  when all the blocks of all current pictures available complete the coding process. 
         [0108]      FIG. 4  shows an implementation example for five reference frames without B frame, having a coding pattern of IPPPPP. In IPPPPP coding pattern, I represents the intra prediction frame, P represents the inter prediction frame. At a first time instance, the reconstructed frame I 0  (recon_I 0 )  400  is reconstructed from the intra prediction frame I 0   410 . The reconstructed frame I 0  (recon_I 0 )  400  is used as a reference frame for input frames P 1   411 , P 2   412 , P 3   413 , P 4   414  and P 5   415 . Subsequently, at a second time instance, the reconstructed frame P 1  (recon_P 1 )  401  is reconstructed from the inter prediction frame P 1   411 . The reconstructed frame P 1  (recon_P 1 )  401  is used as a reference frame for input frames P 2   412 , P 3   413 , P 4   414 , P 5   415  and P 6   416 , so on and so forth. Consequently, a n th  reconstructed frame is used as a reference frame of the (n+1) th  input frame, (n+2) th  input frame, (n+3) th  input frame, (n+4) th  input frame and (n+5) th  input frame. Consequently, the 1 st  input frame P 1   411  only has one reference frame P 1  (recon_P 1 )  401 . The 2 nd  input frame P 2   412  only has two reference frames P 1  (recon_P 1 )  401  and P 2  (recon_P 2 )  402 . The 3 rd  input frame P 3   413  only has three reference frames P 1  (recon_P 1 )  401 , P 2  (recon_P 2 )  402  and P 3  (recon_P 3 )  403 . The 4 th  input frame P 4   414  only has four reference frames P 1  (recon_P 1 )  401 , P 2  (recon_P 2 )  402 , P 3  (recon_P 3 )  403  and P 4  (recon_P 4   404 . But for P 5   415  and frames subsequent to P 5 , there are maximum five reference frames available for each frame. For example, there are five reference frames I 0  (recon_I 0 )  400 , P 1  (recon_P 1 )  401 , P 2  (recon_P 2 )  402 , P 3  (recon_P 3 )  403 , P 4  (recon_P 4 )  404  available as input blocks in the 5 th  input frame P 5   415 . There are five reference frames P 1  (recon_P 1 )  401 , P 2  (recon_P 2 )  402 , P 3  (recon_P 3 )  403 , P 4  (recon_P 4 )  404 , P 5  (recon_P 5 )  405  available as input blocks in the 6 th  input frame P 6   416 , so on and so forth. The input frames I 0   410 , P 1   411 , P 2   412 , P 3   413  and P 4   414  have less than five reference frames because there is no previous frame for these five frames. Consequently, for an nth input frame, it has reconstructed frames (n−5) th , (n−4) th , (n−3) th , (n−2) th , (n−i) th  as long as the reconstructed frames are available for the index number is more than or equal to zero. 
         [0109]    In this embodiment, there are 5 reference pictures. Furthermore, half pixel interpolation and quarter pixel interpolation may also be supported. In the claimed invention, only one interpolation operation is required for each coding block during horizontal half pixel interpolation and horizontal quarter pixel interpolation. Only one interpolation operation is required for each coding block during vertical half pixel interpolation and vertical quarter pixel interpolation. Only one interpolation operation is required for each coding block during cross half pixel interpolation and cross quarter pixel interpolation. This is much more efficient than any method which requires 5 interpolation operations for each coding block during each of half and quarter pixel interpolations in horizontal, vertical and cross directions. 
         [0110]      FIG. 5  shows a flowchart for the implementation of two reference frames with one B frame (no hierarchic-B frame). A reference pictures buffer  501  stores one or more reference pictures. A display pictures buffer  502  stores one or more display pictures. The input picture I 0  (inI_ 0 )  504  is encoded and reconstructed. The reconstructed picture of input picture I 0  (inI_O)  504  is stored into the reference pictures buffer  501 . The reconstructed picture of input picture I 0  (inI_ 0 )  504  is stored into the display pictures buffer  502 . The reconstructed picture of input picture I 0  in the reference pictures buffer  501  is the reference picture for the input pictures P 1 , B 1 , and P 2 . In other words, the reconstructed picture of the input picture I 0  provides a reference block for each input block (inP_ 1 _ 0 )  511  from the input picture P 1 , a reference block for each input block (inB_ 1 _ 0 )  512  from the input picture P 2 , and a reference block for each input block (inP_ 2 _ 0 )  513 . The input picture P 1 , B 1  and P 2  do motion estimation. The input picture P 1  is encoded and reconstructed. The reconstructed picture of input picture P 1  is stored into the reference pictures buffer  501  and the display pictures buffer  502 . The reconstructed picture of input picture P 1  in the reference pictures buffer  501  is the reference picture for the input pictures B 1 , P 2 , B 2 , and P 3  for motion estimation. In other words, the reconstructed picture of input picture P 1  provides a reference block for each input block (inB_ 1 _ 1 )  521  from the input picture B 1 , a reference block for each input block (inP_ 2 _ 1 )  522  from the input picture P 2 , a reference block for each input block (inB_ 2 _ 1 )  523  from the input picture B 2 , and a reference block for each input block (inP_ 3 _ 1 )  524  from the input picture P 3 . The input pictures B 1 , P 2 , B 2 , P 3  do motion estimation. The input picture B 1  is encoded and reconstructed. The reconstructed picture of input picture B 1  is stored into the display pictures buffer  502 . Using the P 2 &#39;s best motion information (blk_info) and predict block (pred_blk) which have already been obtained in previous step, P 2  is encoded and reconstruct, The reconstructed picture of input picture P 2   505  is stored into the reference pictures buffer  501  and the display pictures buffer  502 . The reconstructed picture of input picture P 2  (mem 2 ) in the reference pictures buffer  501  is the reference picture for the input pictures B 2 , P 3 , B 3 , and P 4  for motion estimation. In other words, the reconstructed picture of input picture P 2  (mem 2 ) provides a reference block for each input block (inB_ 2 _ 2 )  531  from the input picture B 2 , a reference block for each input block (inP_ 3 _ 2 )  532  from the input picture P 3 , a reference block for each input block (inB_ 3 _ 2 )  533  from the input picture B 3 , and a reference block for each input block (inP_ 4 _ 2 )  534  from the input picture P 4 . The input pictures B 2 , P 3 , B 3 , P 4  do motion estimation. The input picture B 2  is encoded and reconstructed. The reconstructed picture of input picture B 2  is stored into the display pictures buffer  502 . Using the P 3 &#39;s best motion info (blk_info) and predict block (pred_blk) which have already got in previous step, P 3  is encoded. The reconstructed picture of input picture P 3   506  is stored into the reference pictures buffer  501  and the display pictures buffer  502 . The reconstructed picture of input picture P 3  (mem 3 ) in the reference pictures buffer  501  is the reference picture for the input pictures B 3 , P 4 , B 4 , and P 5  for motion estimation. In other words, the reconstructed picture of input picture P 3  (mem 3 ) provides a reference block for each input block (inB_ 3 _ 3 )  541  from the input picture B 3 , a reference block for each input block (inP_ 4 _ 3 )  542  from the input picture P 4 , a reference block for each input block (inB_ 4 _ 3 )  543  from the input picture B 4 , and a reference block for each input block (inP_ 5 _ 3 )  544  from the input picture P 5 . The input pictures B 3 , P 4 , B 4 , P 5  do motion estimation. The input picture B 3  is encoded and reconstructed. The reconstructed picture of input picture B 3  is stored into the display pictures buffer  502 . Using the P 4 &#39;s best motion info (blk_info) and predict block (pred_blk) which have already got in previous step, P 4  is encoded and reconstructed. The reconstructed picture of input picture P 4  (mem 4 )  507  is stored into the reference pictures buffer  501  and the display pictures buffer  502 . The pictures, i.e., frames of a video of N frames, are originally in an order of I 0 , B 1 , P 1 , B 2 , P 2 , B 3 , P 3 , B 4 , P 4 , . . . , B(n−1), P(n−1). The order of encoding these frames are I 0 , P 1 , B 1 , P 2 , B 2 , P 3 , B 3 , P 4 , B 4 , . . . , P(n−1), B(n−1). The process continues until all N input pictures are encoded, assuming there are N pictures in the video sequence to be encoded. 
         [0111]    Therefore, in this embodiment, at some time instance, it can support partially parallel and pipeline. Such as the motion estimation process can be pipelined with the coding and reconstruct operation. Multiple motion estimation processes can be running in parallel or serial based on the hardware implementation. 
         [0112]      FIG. 6  shows an implementation example for two reference frames with one B frame (no hierarchic-B frame), having a coding pattern of IBPBPBPBP, with parallel operations. In the IBPBPBPBP coding pattern, I represents the Intra prediction frame, P represents the inter prediction frame, B represents bi-directional inter prediction frame and is not used as reference frame. The maximum number of reference frames is two frames. This embodiment features two reference frames with one B frame, without hierarchic B frames. Two reference frames without hierarchic B frames means the following three points: The first point is B 0  can reference I 0  and P 0 , B 1  can reference P 0  and P 1 , etc. The second point is P 1  can reference I 0  and P 0 , P 2  can reference P 0  and P 1 , etc. The third point is B frame will not be used as a reference frame. 
         [0113]    I 0   601  has no reference frame and is encoded into a reconstructed frame recon_I 0   602 . The reconstructed frame recon_I 0   602  is used as the reference frame for P 0   611 , B 0   612 , and P 1   613 . The input pictures P 0   611 , B 0   612  and P 1   613  do motion estimation. P 0   611  is encoded into a reconstructed frame recon_P 0   610 . The reconstructed frame recon_P 0   610  is the reference frame for B 0   621 , P 1   622 , B 1   623  and P 2   624 . The input pictures B 0   621 , P 1   622 , B 1   623 , P 2   624  do motion estimation. B 0   621  is encoded into a reconstructed frame recon_B 0   620  and P 1   622  is encoded into a reconstructed frame recon_P 1   629 . The reconstructed frame recon_P 1   629  is the reference frame for B 1   631 , P 2   632 , B 2   633  and P 3   634 . The input pictures B 1 , P 2 , B 2 , P 3  do motion estimation. B 1   631  is encoded into a reconstructed frame recon_B 1   630  and P 2   632  is encoded into a reconstructed frame recon_P 2   639 . recon_P 2   639  is the reference frame for B 2   641 , P 3   642 , B 3   643  and P 4   644 . The input pictures B 2   641 , P 3   642 , B 3   643 , P 4   644  do motion estimation, B 2   641  is encoded into a reconstructed frame recon B 2   640  and P 3   642  is encoded into a reconstructed frame recon_P 3   649 . The reconstructed frame recon_P 3   649  is the reference frame for B 3   651 , P 4   652 , B 4   653  and P 5   654 . The input pictures B 3   651 , P 4   652 , B 4   653  and P 5   654  do motion estimation B 3   651  is encoded into a reconstructed frame recon_B 3   650  and P 4   652  is encoded into a reconstructed frame recon_P 4   659 , so on and so forth. The process continues until all N input frames are encoded, assuming there are N frames in the video to be encoded. In this embodiment of IBPBPBPBP coding pattern, at the B frame coding and reconstruct stage, there is parallel P frame coding and reconstruct stage. 
         [0114]    Therefore, in this embodiment, at each time instance, there are parallel and pipeline running of the following operations for different input frames: motion estimation, coding and reconstruct operation. For example, when blocks in B 0  is encoded and reconstructed, motion estimation is applied to blocks in P 1  in parallel, and when blocks in P 1  is encoded and reconstructed, motion estimation is applied to blocks in B 1  in parallel. There is no need to store the best match block of P 1  back into external memory, and there is no need to reload the original P 1  when it is encoded and reconstructed, the bandwidth is thus further reduced. 
         [0115]      FIG. 7  shows an implementation example for two reference frames with two B frames (no hierarchic-B frame), having a coding pattern of IBBPBBPBBPBBP. In the IBBPBBPBBPBBP coding pattern, I represents the Intra prediction frame, P represents the inter prediction frame, B represents bidirectional inter prediction frame and is not used as reference frame. The maximum number of reference frame is two frames. The input frame I 0   701  has no reference frame and is encoded and reconstructed into a reconstructed frame recon_I 0   702 . The reconstructed frame recon_I 0   702  is the reference frame of the input frames P 0   711 , B 0   712 , B 1   713 , P 1   714 . The input pictures P 0   711 , B 0   712 , B 1   713 , P 1   714  do motion estimation. The input frame P 0   711  is encoded and reconstructed into a reconstructed frame recon_P 0   703 . The reconstructed frame recon_P 0   703  is the reference frame of the input frames B 0   721 , B 1   722 , P 1   723 , B 2   724 , B 3   725  and P 2   726 . The input pictures B 0   721 , B 1   722 , P 1   723 , B 2   724 , B 3   725 , P 2   726  do motion estimation. The input frame B 0  ( 712  and  721 ) is encoded and reconstructed into a reconstructed frame recon B 0   720 . The input frame B 1  ( 713  and  722 ) is encoded and reconstructed into a reconstructed frame recon_B 1   728 . The input frame P 1  ( 714  and  723 ) is encoded and reconstructed into a reconstructed frame recon_P 1   729 . The reconstructed frame recon_P 1   729  is the reference frame of the input frames B 2   731 , B 3   732 , P 2   733 , B 4   734 , B 5   735  and P 3   736 . The input pictures B 2   731 , B 3   732 , P 2   733 , B 4   734 , B 5   735 , P 3   736  do motion estimation. The input frame B 2  ( 724  and  731 ) is encoded and reconstructed into a reconstructed frame recon_B 2   730 . The input frame B 3  ( 725  and  732 ) is encoded and reconstructed into a reconstructed frame recon_B 3   738 . The input frame P 2  ( 726  and  733 ) is encoded and reconstructed into a reconstructed frame recon_P 2   739 . The reconstructed frame recon P 2   739  is the reference frame of the input frames B 4   741 , B 5   742 , P 3   743 , B 6   744 , B 7   745  and P 4   746 . The input pictures B 4   741 , B 5   742 , P 3   743 , B 6   744 , B 7   745 , and P 4   746  do motion estimation. The input frame B 4  ( 734  and  741 ) is encoded and reconstructed into a reconstructed frame recon B 4   740 . The input frame B 5  ( 735  and  742 ) is encoded and reconstructed into a reconstructed frame recon_B 5   748 . The input frame P 3  ( 736  and  743 ) is encoded and reconstructed into a reconstructed frame recon_P 3   749 . The process continues until all N input frames are encoded, assuming there are N frames in the video to be encoded. 
         [0116]      FIG. 8  shows an implementation example for two reference frames with three B frames (with hierarchic-B frame), having a coding pattern of IBbBPBbBPBbBPBbBP. In the IBbBPBbBPBbBPBbBP coding pattern, I represents the intra prediction frame and may be used as a reference frame, P represents the inter prediction frame and may be used as a reference frame, B represents bi-directional inter prediction frame and is not used as reference frame, b represents bi-directional inter prediction frame and may also be used as a reference frame. The maximum number of reference frames is two frames. The two reference frames with hierarchic-B means the following points: The first point is B 0  can reference I 0  and b 1 , B 1  can reference b 1  and P 0 , etc; The second point is P 1  can reference I 0  and P 0 , P 2  can reference P 0  and P 1 , etc; and the third point is b 1  can reference I 0  and P 0 , b 4  can reference P 0  and P 1 , etc. 
         [0117]    For example, the input frame I 0   801  has no reference frame and is encoded and reconstructed into a reconstructed frame recon_I 0   802 . The reconstructed frame recon_I 0   802  is the reference frame of the input frames P 0   811 , P 1   812 , b 1   813 , and B 0   814 . The input frames P 0   811 , P 1   812 , b 1   813 , B 0   814  do motion estimation. The input frame P 0   811  is encoded and reconstructed into a reconstructed frame recon_P 0   803 . The reconstructed frame recon_P 0   803  is the reference frame of the input frames P 1   821 , b 1   822 , B 2   823 , P 2   824 , b 4   825  and B 3   826 . The input frames P 1   821 , b 1   822 , B 2   823 , P 2   824 , b 4   825 , B 3   826  do motion estimation. The input frame P 1  ( 812  and  821 ) is encoded and reconstructed into a reconstructed frame recon_P 1   810 . The input frame b 1  ( 813  and  822 ) is encoded and reconstructed into a reconstructed frame recon_b 1   819 . The reconstructed frame recon_b 1   819  is the reference frame of the input frames B 0   831  and B 2   832 . The input frames B 0   831 , B 2   832  do motion estimation. The input frame B 0  ( 814  and  831 ) is encoded and reconstructed into a reconstructed frame recon_B 0   820 . The input frame B 2  ( 823  and  832 ) is encoded and reconstructed into a reconstructed frame recon_B 2   829 . The reconstructed frame recon_P 1   810  is the reference frame of the input frames P 2   841 , b 4   842 , B 5   843 , P 3   844 , b 7   845 , and B 6   846 . The input frames P 2   841 , b 4   842 , B 5   843 , P 3   844 , b 7   845 , B 6   846  do motion estimation. The input frame P 2  ( 824  and  841 ) is encoded and reconstructed into a reconstructed frame recon_P 1   810 . The input frame b 4  ( 825  and  842 ) is encoded and reconstructed into a reconstructed frame recon_b 4   839 . The reconstructed frame recon_b 4   839  is the reference frame of the input frames B 3   851  and B 5   852  for motion estimation. The input frames B 3   851 , B 5   852  do motion estimation. The input frame B 3  ( 826  and  851 ) is encoded and reconstructed into a reconstructed frame recon_B 3   840 . The input frame B 5  ( 843  and  852 ) is encoded and reconstructed into a reconstructed frame recon_B 5   849 . The reconstructed frame recon_P 2   830  is the reference frame of the input frames P 3   861 , b 7   862 , B 8   863 , P 4   864 , b 10   865 , and B 9   866  for motion estimation. The input frames P 3   861 , b 7   862 , B 8   863 , P 4   864 , b 10   865 , B 9   866  do motion estimation. The input frame P 3  ( 844  and  861 ) is encoded and reconstructed into a reconstructed frame recon_P 3   850 . The input frame b 7  ( 845  and  862 ) is encoded and reconstructed into a reconstructed frame recon_b 7   859 . The reconstructed frame recon_b 7   859  is the reference fame of the input frames B 6   871  and B 8   872 . The input frames B 6   871 , B 8   872  do motion estimation. The input frame B 6  ( 846  and  871 ) is encoded and reconstructed into a reconstructed frame recon_B 6   860 . The input frame B 8  ( 863  and  872 ) is encoded and reconstructed into a reconstructed frame recon_B 8   869 . The process continues until all N input frames are encoded, assuming there are N frames in the video to be encoded. 
         [0118]    The description of preferred embodiments of this claimed invention are not exhaustive and any update or modifications to them are obvious to those skilled in the art, and therefore reference is made to the appending claims for determining the scope of this claimed invention. 
       INDUSTRIAL APPLICABILITY 
       [0119]    The claimed invention has industrial applicability in consumer electronics, in particular with video applications. The claimed invention can be used in the video encoder, and in particular, in a multi-standard video encoder. The multi-standard video encoder implements various standards such as H.263, H.263+, H.263++, H264, MPEG-1, MPEG-2, MPEG-4, AVS (Audio Video Standard) and the like. More particularly, the claimed invention is implemented for multiple video standards encoder which supports multiple references picture motion estimation. The claimed invention can be used not only for software implementation but also for hardware implementation. For example, the claimed invention can be implemented in a DSP (digital signal processing) video encoder, Xilinx FPGA chip or SoC ASIC chip.