Patent Publication Number: US-2007121726-A1

Title: Motion estimator and motion estimating method

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
      This application claims the benefit under 35 U.S.C. §119(a) of Korean Patent Application No. 2005-0115546, filed on Nov. 30, 2005, in the Korean Intellectual Property Office, the entire disclosure of which is hereby incorporated by reference.  
     BACKGROUND OF THE INVENTION  
      1. Field of Invention  
      The present invention relates to a motion estimator and a motion estimating method. More particularly, the present invention relates to a motion estimator and a motion estimating method for modeling global motion.  
      2. Description of the Related Art  
      A conventional method for modeling global motion will be described with reference to  FIGS. 1A and 1B .  
      As illustrated in  FIG. 1A , in order to estimate motion of a frame by interpolation, a plurality of candidate vectors are calculated on the basis of a current frame and a previous frame. The candidate vectors can be variously selected. As illustrated in  FIG. 1A , the candidate vectors can include a vector SL of a block B adjacent to a current block A, a vector SR of a block C adjacent to the current block A, vectors TR and TL of the previous frame, a zero vector T, a global vector, and the like.  
      A motion vector for a block to be interpolated is selected according to a predetermined cost function. Then, data of the corresponding block is interpolated using the selected motion vector.  
      Here, the global vector, which is one of the candidate vectors, is obtained by the following Equation 1.  
               C   ⁡     (     X   ,   n     )       =     [               p   1     ⁡     (   n   )       +         p   3     ⁡     (   n   )       ⁢   X                       p   2     ⁡     (   n   )       +         p   4     ⁡     (   n   )       ⁢   X       ,                     (   1   )             
 
      Where, n represents an n-th frame, x and y respectively represent x and y coordinates of the corresponding block, p 1  and p 2  represent panning factors, and p 3  and p 4  represent zooming factors.  
      In order to obtain the global vector, as illustrated in  FIG. 1B , some of the motion vectors are sampled. An example where 9 motion vectors are sampled is described. By substituting the resultant sampled data pairs (V 1 , V 2 ), (V 1 , V 3 ), (V 2 , V 3 ), (V 4 , V 5 ), (V 4 , V 6 ), (V 5 , V 6 ), (V 7 , V 8 ), (V 7 , V 9 ), (V 8 , V 9 ), (V 1 , V 4 ), (V 1 , V 7 ), (V 4 , V 7 ), (V 2 , V 5 ), (V 2 , V 8 ), (V 5 , V 8 ), (V 3 , V 6 ), (V 3 , V 9 ), (V 6 , V 9 ) into equation 1, 18 values which can be p 1 , p 2 , p 3  and p 4  are obtained. Then, median filtering is performed on the 18 values, thereby finally deciding p 1 , p 2 , p 3 , and p 4 .  
      However, in the conventional method for obtaining a global vector, since a limited number of motion vectors are sampled, errors are significant when incorrect vectors are sampled, which can make the obtained global vector incorrect. Further, if the number of samples increases in order to solve the problem, more calculators and complicated calculations are required so that the configuration of the hardware may be complicated and more expensive.  
      Accordingly, there is a need for an improved apparatus and method for estimating motion.  
     SUMMARY OF THE INVENTION  
      Exemplary embodiments of the present invention address at least the above problems and/or disadvantages and provide at least the advantages described below. Accordingly, it is an exemplary aspect of the present invention to provide a motion estimator and a motion estimating method which are capable of obtaining a correct global vector while simplifying the configuration of the hardware.  
      The foregoing and/or other exemplary aspects of the present invention can be achieved by providing a motion estimator comprising a candidate vector calculating unit for determining a plurality of candidate vectors for each block of a frame to be interpolated, on the basis of a current frame and a previous frame, a final motion deciding unit for selecting a candidate vector among the plurality of candidate vectors according to a desired criteria and for outputting the selected candidate vector as a final motion vector of a corresponding block, and a global vector modeling unit for performing regression analysis based on final motion vectors to model a global vector calculating formula and for providing the global vector calculating formula to the candidate vector calculating unit, wherein the candidate vector calculating unit calculates a global vector for each block of a next frame to be interpolated according to the modeled global vector calculating formula, and provides the global vector as one of the plurality of candidate vectors to the candidate vector deciding unit.  
      According to another exemplary aspect of the present invention, the global vector modeling unit samples the final motion vectors to model the global vector calculating formula.  
      According to another exemplary aspect of the present invention, the global vector modeling unit models the global vector calculating formula through a linear regression analysis method.  
      According to another exemplary aspect of the present invention, the global vector calculating formula is modeled as follows:
 
 Mv   x   =a   x   x+b   x 
 
 Mv   y   =a   y   y+b   y ,
 
      wherein  
           [           a   x               b   x           ]     =             1       n   ⁢       ∑     k   =   1     n     ⁢     x   k   2         -       (       ∑     k   =   1     n     ⁢     x   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     x   k                   -       ∑     k   =   1     n     ⁢     x   k                 ∑     k   =   1     n     ⁢     x   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     x   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     x   k               ]       ⁢     
     [           a   y               b   y           ]     =         1       n   ⁢       ∑     k   =   1     n     ⁢     y   k   2         -       (       ∑     k   =   1     n     ⁢     y   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     y   k                   -       ∑     k   =   1     n     ⁢     y   k                 ∑     k   =   1     n     ⁢     y   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     y   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     y   k               ]           ,       
 
      where, Mvx and Mvy, which are global vectors, respectively represent an x-directional motion value and a y-directional motion value, x and y are respectively index values of x and y coordinates of the block, ax and ay are respectively an x-directional zooming factor and a y-directional zooming factor, and bx and by are respectively an x-directional panning factor and a y-direction panning factor.  
      According to another exemplary aspect of the present invention, the motion estimator further comprises a frame interpolating unit for interpolating an intermediate frame to be inserted between the current frame and the previous frame, according to the final motion vector.  
      According to another exemplary aspect of the present invention, the final motion deciding unit comprises a candidate vector selector selecting a candidate vector among the plurality of candidate vectors, and a vector compensator for compensating the candidate vector selected by the candidate vector selector and outputting the compensated candidate vector as the final motion vector.  
      The foregoing and/or other aspects of the present invention can be achieved by providing a motion estimating method comprising determining a plurality of candidate vectors for each of blocks of a frame to be interpolated, on the basis of a current frame and a previous frame, selecting a candidate vector among the plurality of candidate vectors according to a desired criteria, outputting the selected candidate vector as a final motion vector of a corresponding block, performing regression analysis based on the final motion vectors to model a global vector calculating formula and providing the global vector calculating formula to the candidate vector calculating unit, wherein the determining the plurality of candidate vectors comprises determining a global vector for each block of a next frame to be interpolated, according to the global vector calculating formula, and providing the global vector as the candidate vector of the plurality of candidate vectors to the candidate vector deciding unit.  
      According to another exemplary aspect of the present invention, in the modeling of the global vector calculating formula, the global vector calculating formula is modeled by sampling the final motion vectors.  
      According to another exemplary aspect of the present invention, in the modeling of the global vector calculating formula, the global vector calculating formula is modeled through a linear regression analysis method.  
      According to another exemplary aspect of the present invention, the global vector calculating formula is modeled as follows:
 
 Mv   x   =a   x   x+b   x 
 
 Mv   y   =a   y   y+b   y ,
 
      wherein,  
           [           a   x               b   x           ]     =             1       n   ⁢       ∑     k   =   1     n     ⁢     x   k   2         -       (       ∑     k   =   1     n     ⁢     x   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     x   k                   -       ∑     k   =   1     n     ⁢     x   k                 ∑     k   =   1     n     ⁢     x   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     x   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     x   k               ]       ⁢     
     [           a   y               b   y           ]     =         1       n   ⁢       ∑     k   =   1     n     ⁢     y   k   2         -       (       ∑     k   =   1     n     ⁢     y   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     y   k                   -       ∑     k   =   1     n     ⁢     y   k                 ∑     k   =   1     n     ⁢     y   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     y   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     y   k               ]           ,       
 
      where, Mvx and Mvy, which are global vectors, respectively represent an x-directional motion value and a y-directional motion value, x and y are respectively index values of x and y coordinates of the block, ax and ay are respectively an x-directional zooming factor and a y-directional zooming factor, and bx and by are respectively an x-directional panning factor and a y-direction panning factor.  
      According to another exemplary aspect of the present invention, the method further comprises interpolating an intermediate frame to be inserted between the current frame and the previous frame, according to the compensated final motion vector.  
      According to another exemplary aspect of the present invention, the outputting of the final motion vector comprises selecting a candidate vector among the plurality of candidate vectors, compensating the selected candidate vector and outputting the compensated candidate vector as the final motion vector.  
      The foregoing and/or other exemplary aspects of the present invention can be achieved by providing a global motion estimator comprising a motion estimating unit for estimating a motion vector for each block of a frame to be interpolated, on the basis of a current frame and a previous frame, a global modeling unit for performing regression analysis based on the estimated motion vector and for modeling a global vector calculating formula and a global vector calculating unit for calculating a global vector for each block of a next frame to be interpolated, according to the global vector calculating formula.  
      According to another exemplary aspect of the present invention, the global modeling unit models the global vector calculating formula by sampling the motion vectors.  
      According to another exemplary aspect of the present invention, the global modeling unit models the global vector calculating formula through a linear regression analysis method.  
      According to another exemplary aspect of the present invention, the global vector calculating formula is modeled as follows:
 
 Mv   x   =a   x   x+b   x 
 
 Mv   y   =a   y   y+b   y ,
 
      wherein,  
           [           a   x               b   x           ]     =             1       n   ⁢       ∑     k   =   1     n     ⁢     x   k   2         -       (       ∑     k   =   1     n     ⁢     x   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     x   k                   -       ∑     k   =   1     n     ⁢     x   k                 ∑     k   =   1     n     ⁢     x   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     x   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     x   k               ]       ⁢     
     [           a   y               b   y           ]     =         1       n   ⁢       ∑     k   =   1     n     ⁢     y   k   2         -       (       ∑     k   =   1     n     ⁢     y   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     y   k                   -       ∑     k   =   1     n     ⁢     y   k                 ∑     k   =   1     n     ⁢     y   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     y   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     y   k               ]           ,       
 
      where, Mvx and Mvy, which are global vectors, respectively represent an x-directional motion value and a y-directional motion value, x and y are respectively index values of x and y coordinates of the block, ax and ay are respectively an x-directional zooming factor and a y-directional zooming factor, and bx and by are respectively an x-directional panning factor and a y-direction panning factor. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
      The above and/or other exemplary aspects and advantages of the prevent invention will become apparent and more readily appreciated from the following description of the exemplary embodiments, taken in conjunction with the accompany drawings, in which:  
       FIGS. 1A and 1B  are views for explaining a conventional method for estimating a motion vector.  
       FIG. 2  is a control block diagram of a motion estimator according to an exemplary embodiment of the present invention; and  
       FIG. 3  is a flowchart illustrating a motion estimating method according to an exemplary embodiment of the present invention.  
    
    
      Throughout the drawings, the same drawing reference numerals will be understood to refer to the same elements, features, and structures.  
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS  
      The matters defined in the description such as a detailed construction and elements are provided to assist in a comprehensive understanding of the embodiments of the invention and are merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the embodiments described herein can be made without departing from the scope and spirit of the invention. Also, descriptions of well-known functions and constructions are omitted for clarity and conciseness. Reference will now be made in detail to exemplary embodiments of the present invention which are illustrated in the accompanying drawings.  
       FIG. 2  is a control block diagram of a motion estimator according to an exemplary embodiment of the present invention. Referring to  FIG. 2 , the motion estimator includes a candidate vector calculating unit  10 , a final motion deciding unit  20 , and a global vector modeling unit  30 .  
      The candidate vector calculating unit  10  determines a plurality of candidate vectors on the basis of a current frame and a previous frame. The candidate vector calculating unit  10  may include one or more candidate vector calculators corresponding to the respective candidate vectors.  
      For example, the candidate vector calculators may divide the current frame into a plurality of blocks, apply a Full Search Block Matching (FSBM) algorithm to a desired search region of the previous frame corresponding to a reference block to thus determine a plurality of motion prediction error values, and then estimate candidate vectors of the respective blocks on the basis of locations having minimum motion prediction error values. Here, the motion prediction error values can be determined by various methods, such as Sum of Absolute Difference (SAD), Mean Absolute Difference (MAD), and the like.  
      The candidate vector calculating unit  10  may include a global vector calculating unit  11  for determining a global vector of each block according to a global vector calculating formula modeled by the global vector modeling unit  30  which will be described later. The global vector calculating unit  11  determines a global vector of each block by substituting an index of each block into the modeled global vector calculating formula.  
      The candidate vector calculating unit  10  may generate motion vectors of blocks adjacent to the reference block of a current frame and/or motion vectors of blocks adjacent to the reference block of the previous frame as candidate vectors.  
      The candidate vectors are referred to as CV 1 , CV 2 , CV 3 , CV 4 , . . . as shown in  FIG. 2 .  
      The final motion deciding unit  20  selects one of the candidate vectors output from the candidate vector calculating unit  10 , and outputs it as a final motion vector of a block to be interpolated. At this time, the final motion deciding unit  20  selects a candidate vector according to a desired criteria. For example, the final motion deciding unit  20  substitutes the respective candidate vectors in the cost function, and selects a candidate vector for which the value of the cost function is minimum. However, exemplary embodiments of the present invention are not limited to this, and various error analysis methods can be applied.  
      The final motion deciding unit  20  according to an exemplary embodiment of the present invention may include a candidate vector selector  21  for selecting one of the plurality of candidate vectors according to the desired criteria as described above, and a vector compensator  23  for compensating the selected vector.  
      Here, the vector compensator  23  compensates the selected motion vector in order to minimize a specific pattern or a blocking artifact. Various compensation methods can be used to compensate the motion vector. Here, the vector compensator  23  may be included in the candidate vector calculating unit  10  as well as the final motion deciding unit  20  so as to compensate the calculated respective candidate vectors.  
      The final motion vector decided by the final motion deciding unit  20  is output to the global vector modeling unit  30 . The global vector modeling unit  30  performs regression analysis based on the final motion vector and models or determines a global vector calculating formula.  
      The global vector calculating formula is defined in equation 2.
 
 Mv   x   =a   x   x+b   x 
 
 Mv   y   =a   y   y+b   y ,
 
      where, Mvx and Mvy, which are global vectors, respectively represent an x-directional motion value and a y-directional motion value, x and y are respectively index values of x and y coordinates of a block, ax and ay are respectively an x-directional zooming factor and a y-directional zooming factor, and bx and by are respectively an x-directional panning factor and a y-direction panning factor.  
      For example, when resolution of an image frame is 720×480 and the size of a reference block is 16×16, the range of x of the image frame is 0-45, the range of y of the image frame is 1-29, and the image frame is divided into 1380 blocks.  
      If final motion vectors of the respective blocks are compensated by the vector compensator  23 , equation 2 can be rewritten for the respective blocks, as the following equation 3.
 
 Mvx   0   =a   x ·0 +b   x    Mvy   0   =a   y ·0 +b   y 
 
 Mvx   1   =a   x ·1 +b   x    Mvy   1   =a   y ·1 +b   y 
 
. . .
 
 Mvx   1378   =a   x ·1378 +b   x   . Mvy   1378   =a   y ·1378 +b   y 
 
 Mvx   1379   =a   x ·1379 +b   x    Mvy   1379   =a   y ·1379 +b   y   (3)
 
      If n blocks exist, equation 3 can be rewritten as equation 4 which is a general formula.
 
 Mvx   0   =a   x ·0 +b   x    Mvy   0   =a   y ·0 +b   y 
 
 Mvx   1   =a   x ·1 +b   x    Mvy   1   =a   y ·1 +b   y 
 
. . .
 
 Mvx   n−2   =a   x ·(n−2)+ b   x    Mvy   n−2   =a   y ·(n−2) +b   y 
 
 Mvx   n−1   =a   x ·(n−1)+ b   x    Mvy   n−1   =a   y ·(n−1) +b   y   (4)
 
      Meanwhile, equation 4 can be expressed by the following equation 5 which is a matrix.  
               [           Mv   ⁢           ⁢     x   0               ⋮             Mv   ⁢           ⁢     x     n   -   1               ]     =           [         0       1           ⋮       1             n   -   1         1         ]     ⁡     [           a   x               b   x           ]       ⁢     
     [           Mv   ⁢           ⁢     y   0               ⋮             Mv   ⁢           ⁢     y     n   -   1               ]     =       [         0       1           ⋮       1             n   -   1         1         ]     ⁡     [           a   y               b   y           ]                 (   5   )             
 
      Equation 5 can be rewritten as equation 7 by applying equation 6 with respect to ax and bx.
 
( Ax=b→x =( A   T   A ) −1 ( A   T   b ))  (6)
 
  
               [           a   x               b   x           ]     =         1       n   ⁢       ∑     k   =   1     n     ⁢     x   k   2         -       (       ∑     k   =   1     n     ⁢     x   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     x   k                   -       ∑     k   =   1     n     ⁢     x   k                 ∑     k   =   1     n     ⁢     x   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     x   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     x   k               ]               (   7   )             
 
      Likewise, ay and by can be obtained by the following Equation 8.  
               [           a   y               b   y           ]     =         1       n   ⁢       ∑     k   =   1     n     ⁢     y   k   2         -       (       ∑     k   =   1     n     ⁢     y   k       )     2         ⁡     [         n         -       ∑     k   =   1     n     ⁢     y   k                   -       ∑     k   =   1     n     ⁢     y   k                 ∑     k   =   1     n     ⁢     y   k   2             ]       ⁡     [             ∑     k   =   1     n     ⁢       x   k     ⁢   Mv   ⁢           ⁢     y   k                     ∑     k   =   1     n     ⁢     Mv   ⁢           ⁢     y   k               ]               (   8   )             
 
      As seen in equations 7 and 8, ax, ay, bx, and by can be obtained through the index and motion value of the corresponding block. Accordingly, complicated calculations are not required, and correct global vectors can be obtained because coefficient values are obtained from motion vectors of entire blocks, differently from the conventional method. Meanwhile, the global vector calculating formula can be obtained by sampling a desired number of blocks without using motion vectors of entire blocks. In the conventional global vector calculator, increasing the number of samplings puts a greater load on hardware. However, in exemplary embodiments of the present invention, an increase in the number of samplings does not have the same negative influence on hardware.  
      The global vector calculating formula modeled by the global vector modeling unit  30  is provided to the candidate vector calculating unit  10 . The global vector calculating unit  11  determines a global vector by substituting index values of x and y coordinates of a block to the global vector calculating formula. The resultant global vector is provided as one of the plurality of candidate vectors to the final motion deciding unit  20 . Here, the global vector calculating formula modeled by the global vector modeling unit  30  is used to obtain global vectors of a next frame.  
      Meanwhile, the final motion vector decided by the final motion deciding unit  20  is used to generate a new intermediate frame in a frame interpolating unit  40 . That is, the frame interpolating unit  40  interpolates the new intermediate frame to be inserted between the current frame and the previous frame, on the basis of the final motion vector.  
      Hereinafter, an exemplary method for calculating a global vector in the motion estimator illustrated in  FIG. 2  will be described with reference to  FIG. 3 .  
      Referring to  FIGS. 2 and 3 , the candidate vector calculating unit  10  determines a plurality of candidate vectors on the basis of the current frame and the previous frame (S 100 ). Then, the candidate vector selector  21  selects one of the plurality of candidate vectors according to a desired criteria (S 101 ). The selected motion vector is processed by the vector compensator  23  and is output as a final motion vector (S 102 ).  
      Then, the global vector modeling unit  30  models the global vector calculating formula on the basis of the final motion vectors (S 103 ). Details therefor will be not described as they have been described above. The global vector calculating unit  11  determines global vectors of a next frame according to the global vector calculating formula (S 104 ). The calculated global vector may be provided as one of the plurality of candidate vectors.  
      As described above, according to exemplary embodiments of the present invention, there are provided a motion estimator and a motion estimating method which are capable of obtaining correct global vectors while simplifying the configuration of the hardware.  
      Certain exemplary embodiments of the present invention can also be embodied as computer-readable codes on a computer-readable recording medium. The computer-readable recording medium is any data storage device that can store data which can thereafter be read by a computer system. Examples of the computer-readable recording medium include, but are not limited to, read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, optical data storage devices, and carrier waves (such as data transmission through the Internet). The computer-readable recording medium can also be distributed over network-coupled computer systems so that the computer-readable code is stored and executed in a distributed fashion. Also, functional programs, codes, and code segments for accomplishing the present invention can be easily construed as within the scope of the invention by programmers skilled in the art to which the present invention pertains.  
      Although a few exemplary embodiments of the present invention have been shown and described, it will be appreciated by those skilled in the art that changes may be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the appended claims and their equivalents.