Abstract:
A block matching estimation apparatus and a method thereof are disclosed. The block matching estimation apparatus includes a first predetermined number of first processor, each of which receives a search data at a rising edge of a clock, for calculating an absolute difference value between the search data and a reference data; and the first predetermined number of second processor, each of which receives a search data at a falling edge of the clock, for calculating an absolute difference value between the search data and a reference data, wherein the first processor and the second processor are alternately connected. The block matching estimator can decrease its the clock cycles by performing operations at the rising edge and the falling edge of the clock.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to a block matching motion estimator and a method thereof; and, more particularly to a block matching motion estimator reducing its clock cycles and a method thereof which perform two operations in one clock cycle, i.e., one in a rising edge and one in a falling edge.  
         DESCRIPTION OF THE PRIOR ART  
         [0002]    A block matching algorithm is widely used as a motion estimating algorithm for deleting correlation between video data frames.  
           [0003]    The block matching algorithm divides frames which are timely adjacent to a fixed block and estimates movement of the corresponding block.  
           [0004]    A full-search block matching algorithm (FBMA) has the best matching capability in the block matching motion estimating algorithm. In here, the FBMA is expressed by equations (1) and (2) as following.  
                 SAD        (     u   ,   v     )       =       ∑     i   =   0       N   -   1                         ∑     j   =   0       N   -   1                              s        (       u   +   i     ,     v   +   j       )       -     r        (     i   ,   j     )                    ,       -   d     ≤   u     ,     v   ≤     +   d               (   1   )                               
 
           [0005]    Where, SAD represents sum of absolute difference.  
             V= ( u,v )|min SAD( u,v )  (2)  
           [0006]    The FBMA calculates sum of absolute difference (SAD) within search range from −d ˜+d, compares the SAD each other and choose a block which has minimum SAD. Generally, a reference block size (N) and a search range (D) have different horizon value and vertical value but hereby determined to same value for convenience sake and the SAD is used as a matching measure.  
           [0007]    The FBMA has simplicity and regulation in operation so good in realizing of hardware and has the best capability, whereas has numerous operations.  
           [0008]    [0008]FIG. 1 is a diagram illustrating a general motion estimator. As described in FIG. 1, the motion estimator comprising a search area data buffer  110  which stores a search area data (sdata)  111 , motion estimator  120  which calculates motion estimating and a reference block data buffer  130  which delays a reference block data  131 .  
           [0009]    The sdata  111  and a reference block data (idata)  131  are input to the motion estimator to output a motion vector (mvdata)  121 .  
           [0010]    The search area data buffer  110  decrease input data rate of the sdata  111  by storing the former sdata  111  and the current sdata  111  in former stage and current stage respectively and easily response to the various data request according to the motion estimator VLSI architecture.  
           [0011]    Additionally, the reference block data buffer  130  is functioned as a data rate buffer with the search area data buffer  110  and delay the idata  131  and then, at the same as the pdata  112 , output them to the odata  132 .  
           [0012]    The motion estimator  120  actually calculates motion estimating, and according to its VLSI architecture, the sdata  111  or the idata  131  is required one or more data per a clock cycle. And in some cases, it requires the same data one or more times.  
           [0013]    Also the motion estimator  120  architecture has an array of processing elements (PE) thereby has a hardware architecture which carry out operations as many as multipled the number of search block and the number of reference block data. And generally, a given number of clock cycles has smaller than that of operation, so numeral PE performing parallel operations.  
           [0014]    [0014]FIG. 2 is a diagram showing a motion estimation VLSI architecture which general PE operation.  
           [0015]    As described in FIG. 2, the PE  210  inputs an a  211  and a b  212  to output an absolute value of the a  211  minus the b  212 .  
           [0016]    [0016]FIG. 3 is a diagram showing a motion estimation VLSI architecture which is one-dimensional PE array architecture with a column of the PE  311  to  314  in accordance with a first preferred embodiment of the present invention.  
           [0017]    Referring to FIG. 3, a motion estimation VLSI including the PE  311  to  314  which calculate an absolute difference of input data, an adder tree  320  which add the PE  311  to  314  outputted absolute differences, simultaneously, an accumulator  330  which accumulate the adder tree  320  outputted sums of absolute difference (SAD) and a comparator  340  which calculate the minimum SAD from the accumulator outputted accumulated SAD.  
           [0018]    In the SAD operation, absolute differences from all the PE  311  to  314  are added through the adder tree  320 , added SADs in the adder tree  320  are accumulated through the accumulator  330  and then compared with the minimum SAD through the comparator  340 .  
           [0019]    Also, different from the SAD calculating process, in another method, add absolute differences from all the PE  311  to  314  through the adder tree  320  and obtain the SAD in the final PE by transferring the absolute differences to adjacent processing element and accumulate it in the PE, but this method has no advantage in hardware complexity.  
           [0020]    However, the present invention doesn&#39;t affected by the SAD operation circuit.  
           [0021]    The PE structure of one-dimensional array has an advantage of having 100% operation clock efficiency. However, in this structure, the sdata  111  and the idata  131  is provided as many as the number of PE, in each clock cycle, so a buffer architecture and a supply circuit of the search area data buffer  110  and the reference block data buffer  130  are complicated. Accordingly, if the motion estimator has many PEs, one-dimensional array structure is not proper.  
           [0022]    [0022]FIG. 4 is a diagram showing a motion estimation VLSI of a second preferred embodiment of the present invention and, thereby having two-dimensional PE architecture which increasing process element number without increasing an input bandwidth of the sdata  111  and the idata  131 .  
           [0023]    Referring to FIG. 4, the sdata s 0 , s 1 , s 2  and s 3  and the idata i 0 , i 1 , i 2  and i 3  are loaded to an internal latch of a processing element (PE)  401  to  416  for four clock cycles. Hereafter, the sdata s 0 , s 1 , s 2  and s 3  and the idata i 0 , i 1 , i 2  and i 3  are still latched to the PE  401  to  416 , and the sdata s 0 , s 1 , s 2  and s 3  are carried out an absolute different operation by right shift, and add the absolute differences in an adder tree  420 , then obtain minimum SAD by comparing the SAD in a comparator  430 .  
           [0024]    The disadvantage of the above structure is a waste of clock cycles by loading and a large data bandwidth as many as that of PE rows.  
           [0025]    [0025]FIG. 5 is a diagram showing a motion estimating VLSI of a third preferred embodiment of the present invention and, thereby simplify the conventional data supply structure by having two dimensional structure of N×N processing element and (2d)×(N−1) latch. In here, N denotes a reference block size and d denotes a search range.  
           [0026]    Referring to FIG. 5, the reference data (i) is inputted during N×N clock to load in the processing element  501  to  516  and the search area data close its operation by inputting the last search area data.  
           [0027]    Then the SAD of one search area in each clock is obtained and at the same time, optimum search block comparison is processed.  
           [0028]    The above structure has simple data input structure, but on the other side, lots of latch  520  to  531  and loading clock is needed.  
           [0029]    [0029]FIG. 6 is a diagram showing a motion estimating VLSI which using general block matching motion estimating algorithm in accordance with a fourth preferred embodiment of the present invention and, thereby the processing element performing an absolute difference operation and charge the SAD operation in each search block.  
           [0030]    As described in FIG. 6, every SAD of the search block is obtained when every search block data is inputted and a clock cycle is used to search optimum search block by extract the SAD from the every processing element  601  to  625 .  
           [0031]    The number of PEs  601  to  625  is related to a number of the search block and a latch number is determined by a horizonal reference block data number and a vertical search block number.  
           [0032]    Therefore, the above structure is apt to a motion estimator which have small search block, e.g., a half per unit element motion estimation which is carried out after an integer per unit element motion estimation in MPEG-2.  
           [0033]    The structures in FIG. 2 or FIG. 3 have good efficiency in calculation but data supply structure is complicated, the structures in FIGS. 4 and 5 have simple data supply but need many cycles.  
         SUMMARY OF THE INVENTION  
         [0034]    It is, therefore, an object of the present invention to provide a block matching motion estimator reducing its clock cycles and a method thereof.  
           [0035]    In accordance with one aspect of the present invention, there is provided a block matching estimation apparatus including a first predetermined number of first processor, each of which receives a search data at a rising edge of a clock, for calculating an absolute difference value between the search data and a reference data; and the first predetermined number of second processor, each of which receives a search data at a falling edge of the clock, for calculating an absolute difference value between the search data and a reference data, wherein the first processor and the second processor are alternately connected.  
           [0036]    In accordance with another aspect of the present invention, there is provided a block matching estimation method, comprising the steps of: a) receiving a reference signal and two search datas at a clock; b) calculating absolute difference values between the search data and a reference data at a rising edge; and c) calculating absolute difference values between the search data and a reference data at a falling edge.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0037]    The above and other objects and features of the present invention will become apparent from the following description of the preferred embodiments given in conjunction with the accompanying drawings, in which;  
         [0038]    [0038]FIG. 1 is a diagram illustrating a general motion estimator;  
         [0039]    [0039]FIG. 2 is a diagram showing a general PE processor;  
         [0040]    [0040]FIG. 3 is a diagram showing a conventional motion estimation architecture;  
         [0041]    [0041]FIG. 4 is a diagram showing another conventional motion estimation VLSI;  
         [0042]    [0042]FIG. 5 is a diagram showing a further another conventional motion estimation VLSI;  
         [0043]    [0043]FIG. 6 is a diagram showing a still another motion estimation VLSI;  
         [0044]    [0044]FIG. 7 is a diagram showing a block matching motion estimation VLSI for reducing its clock cycles in accordance with a preferred embodiment of the present invention;  
         [0045]    [0045]FIG. 8A is a detailed diagram showing a processing element of FIG. 7;  
         [0046]    [0046]FIG. 8B is a diagram showing a minimum sum of absolute difference (SAD) operation processing in accordance with a preferred embodiment of the present invention; and  
         [0047]    [0047]FIG. 9 is a timing diagram showing a block matching motion estimation VLSI in accordance with a preferred embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0048]    [0048]FIG. 7 is a diagram showing a block matching motion estimation very large scale integration (VLSI) for reducing its clock cycles in accordance with a preferred embodiment of the present invention, which is adopted to a motion estimation VLSI architecture in FIG. 5.  
         [0049]    As described in FIG. 7, the block matching estimating VLSI for reducing clock cycles includes a processing element (PE)  701  to  716  which performing unit calculation and an outer latch (Lr, Lf)  720  to  731  which performing a shift function for aligning unifying a data in case of transferring a data of PE data to next PE.  
         [0050]    The VLSI has two-dimensional PE architecture N×N processing element and (2d)×(N−1) latchs as in the FIG. 5. In here, N and d denotes sizes of a reference block and searching region, respectively.  
         [0051]    The search area data (s 00 , s 01 , s 02  and s 03 ) per cycle are input in a rising edge (s 00 , s 02 , . . . ), in a falling edge (s 01 , s 03 ) of the clock by ones, so two is input per clock cycle and at this time, the search area data is transferred in two per cycle.  
         [0052]    The specific architecture and operation of the PE  701  to  716  and the outer latch  721  to  731  is as below.  
         [0053]    [0053]FIG. 8A is a diagram showing a VLSI for reducing a clock cycle number in accordance with a preferred embodiment of the present invention and describes an inter architecture of the PE and connection between PEs.  
         [0054]    As described in FIG. 8A, a processing element for reducing clock cycles in VLSI is comprising a rising edge processing element PE_r (PE 33 , PE 31 )  810  and  830  and a falling edge processing element PE_f (PE 32 , PE 30 )  820  and  840  for using each edge (rising edge and falling edge), and the processing elements are connected alternately from the PE 33   701  to PE 00   716 .  
         [0055]    The inter architecture of the PE is comprising a latch  813 ,  823 ,  833 , and  843  for loading the search area data s 00 , s 01 , . . . , a latch  814 ,  824 ,  834  and  844  for loading a reference block data (i), an absolute difference calculator  815 ,  816 ,  825 ,  826 ,  835 ,  836 ,  845  and  846  for calculate the i difference, a latch  812 ,  822 ,  832  and  842  for loading the rising edge calculated absolute difference and a latch  811 ,  821 ,  831  and  841  for loading the absolute difference calculated at the falling edge.  
         [0056]    The detailed description of the VLSI operation for reducing clock cycles by adapting to a block matching motion estimation algorithm is as below.  
         [0057]    First of all, the i is input by one data per clock cycle during  16  clocks and loaded to each PE latch  814 ,  824 ,  834  and  844  and the search area data s 00 , s 01 , . . . is input by two data (at the rising edge and the falling edge, respectively) per clock cycle so that they move by two blocks per a cycle.  
         [0058]    The every i is loaded by the above processing and when the search area data is input to the processing element PE 00 , the absolute difference calculator  815 ,  816 ,  825 ,  826 ,  835 ,  836 ,  845  and  846  calculates an absolute difference.  
         [0059]    In case of an odd number processing element PE 33 , PE 31 , . . . the absolute difference calculation is processed by calculating absolute differences between the i loaded in the odd number processing element PE 33 , PE 31 , . . . latch  814  and  834  the i and even number data s 01 , s 03 , . . . of the search area latch  813 ,  833 , then store the value to the Lr  812 ,  832  and then calculate an absolute difference between the i data and s 00 , s 02  . . . , of the search area and store it to Lf  811 ,  831 .  
         [0060]    In case of an even number processing element PE 32 , PE 30 , the absolute difference calculation is processed by calculating absolute differences between the even number processing element PE 32 , PE 30 , . . . latch  823  and  843  loaded the i and an even number data s 00 , s 02 , . . . of the search area latch  823 ,  843 , then store the value to the Lf  821 ,  841  and then calculate an absolute difference between the i data and s 00 , s 02  . . . , of the search area and store it to Lr  822 ,  842 .  
         [0061]    The SAD is obtained by the above obtained absolute difference values  811 ,  812 ,  821 ,  822 ,  831 ,  832 ,  841  and  842  and the process obtaining SAD will be described in FIG. 8B.  
         [0062]    [0062]FIG. 8B is a diagram showing a minimum sum of absolute difference (SAD) operation processing in accordance with a preferred embodiment of the present invention.  
         [0063]    The absolute difference value  811 ,  812 ,  821 ,  822 ,  831 ,  832 ,  841  and  842  which are obtained in FIG. 8A is inputted an accumulator  860  and  862  then the SADs of two search block per a clock are obtained.  
         [0064]    In a first clock, the latch value Lr  812  and  832  of the absolute difference value of the odd processing element PE 33 , PE 31 , . . . and the latch value Lf  821  and  841  of the absolute difference value of the even processing element are added in an accumulator  860  then, a SAD of a first search area SAD 0  is obtained. And the latch value Lf  811  and  831  of the absolute difference value of the odd processing element and the latch value Lr  822  and  842  of the absolute difference value of the even processing element are added in an accumulator  862  then, a SAD of a second search area SAD 1  is obtained. In here, the SAD is compared in a comparing machine  868  to calculate a minimum SAD and a motion vector for estimating motion is determined.  
         [0065]    After that, clock cycles in which only loading occurs are existed, but by inputting final search area data, a final SAD is calculated and motion estimating calculation is end.  
         [0066]    The internal latches  823  and  843  of the processing element PE_f, the internal latches  813  and  833  of the processing element PE_r and the reference block data latches  814 ,  827 ,  834  and  844  are latched by an enable signal “s 0 _en”, “s 1 _en” and “i_en”, respectively. At this time, the processing element PE_f and an outer latch Lf  852  is latched according to the enable signal “s 0 _en” and the processing element PE_r and an outer latch Lr  851  are latched according to the enable signal “s 1 _en”.  
         [0067]    [0067]FIG. 9 is a diagram showing a block matching motion estimating VLSI in accordance with a preferred embodiment of the present invention.  
         [0068]    As described in FIG. 9, a search area (sdata) is inputted through an inputting port s 0  and s 1  of a processing element PE 33   810  in two data per one cycle.  
         [0069]    In the s 0  port, s 00 , s 02 , s 04  are input and latched at an falling edge of a clock and transferred to next processing element, and in the s 1  port, s 01 , s 03 , s 05 , . . . are input and latched at an rising edge of a clock and transferred. In here, the transfer of the sdata is always performed when a clock is triggered and there is no need to be controlled by the enable signal. However, the enable signal can decrease a consumption of power.  
         [0070]    When the transferred sdata is reached to the processing element PE 00 , then the SAD is calculated by adding an absolute difference of all processing elements.  
         [0071]    As described in FIG. 9, a data wave form of the s 0 _in  801  and s 1 _in  802  of the PE 33  are input to s 0  port and s 1  port of the PE 33  when the first data s 00  and s 01  of the sdata are reached to the s 0 _in  803  and s 1 _in  804  of the processing element PE 01 .  
         [0072]    The internal latch Lf output and Lr output wave form  805  of the processing element are an absolute difference output timing of the PE 01  and the PE 00 .  
         [0073]    The latch Lf output of the PE 01  describes a falling edge absolute difference data between data which are input through i 01  and s 0  of PE 01 . And the latch Lr output of the PE 01  describes a search area data which inputted through the PE 01  loaded i 01  and s 1  table, performed an absolute difference operation and latched in an rising edge of the clock.  
         [0074]    The latch Lf output and the latch Lr output of the processing element PE 00  have the same operation and in here, instead of the i 01 , an i 00  is used. The ad 00 , ad 01  . . . , means an absolute difference calculation with the internal block of the processing element is performed with s 00 , s 01 , . . .  
         [0075]    The function of the SAD 0 (sad 00 ) is Lf(ad 00 ) of the PE 00 +Lr(ad 01 ) of the PE 01 +. . . +Lf(ad 32 ) of the PE 32 +Lr(ad 33 ) of the PE 33 . And the function of the SAD 1 (sad 01 ) is Lr(ad 01 ) of the PE 00 +Lf(ad 02 ) of the PE 01 +. . . +Lr(ad 33 ) of the PE 32 +Lf(ad 34 ) of the PE 33 . That is, two SAD is obtained per clock.  
         [0076]    As described above, the block matching estimator in accordance with the present invention can decrease its the clock cycles by performing operations at the rising edge and the falling edge of the clock.  
         [0077]    Although the preferred embodiments of the invention have been disclosed for illustrative purpose, those skilled in the art will be appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as disclosed in the accompanying claims.