Patent Publication Number: US-2005141615-A1

Title: Motion vector estimating method and motion vector estimating apparatus using block matching process

Description:
CROSS-REFERENCE TO RELATED APPLICATION  
      This application claims the benefit of Korean Patent Application No. 2003-99041, filed on Dec. 29, 2003, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein by reference.  
     BACKGROUND OF THE INVENTION  
      1. Field of the Invention  
      The present invention relates to encoding and decoding a moving picture or image, and more specifically, to a motion vector estimating method and a motion vector estimating apparatus using a block matching process for encoding a moving picture or image.  
      2. Description of the Related Art  
      In general, a motion vector for a certain image block is estimated by determining a search area and detecting an image block most closely matching with pixel values of the desired image block. That is, an image block most similar to the desired image block is detected while moving the desired image block over the search area by a pixel, and a position of the image block is determined as the motion vector. However, since degrees of similarity of the pixel values should be calculated while moving the desired image block over the search area of every pixel, the above method requires a large amount of calculation.  
     SUMMARY OF THE INVENTION  
      Additional aspects and/or advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.  
      Accordingly, an aspect of the invention provides a motion vector estimating method and a motion vector estimating apparatus in which the amount of calculation for estimating a motion vector is reduced by sub-sampling a macroblock and a search area.  
      According to an aspect of the invention, a motion vector estimating method includes calculating correlation values corresponding to a plurality of correlation calculating patterns selected in accordance with types of a present picture, and determining a correlation calculating pattern on the basis of a calculation result; and selecting a sub-sampling pattern corresponding to the correlation calculating pattern determined in the calculating of the correlation values, sub-sampling a present image block and a search area, and then estimating a motion vector.  
      An aspect of the motion vector estimating method may further include converting the estimated motion vector into a size corresponding to a size of the search area before the sub-sampling.  
      An aspect of the calculating of the correlation values includes calculating correlation values of a predetermined pattern selected depending upon whether the present picture is an interlaced picture or a progressive picture; and selecting a pattern of which the calculated correlation value is the smallest.  
      According to another aspect of the invention, a motion vector estimating apparatus includes a pattern determining unit that calculates correlation values corresponding to a plurality of correlation calculating patterns selected in accordance with types of a present picture, and determines a correlation calculating pattern on the basis of a calculation result; a sub-sampling unit that selects a sub-sampling pattern corresponding to the determined correlation calculating pattern, and sub-samples a present image block and a search area; and a motion vector estimating unit that estimates a motion vector of the sub-sampled image block and the sub-sampled search area.  
      An aspect of the motion vector estimating unit converts the estimated motion vector into a size corresponding to a size of the search area before the sub-sampling.  
      An aspect of the pattern determining unit calculates correlation values of a predetermined pattern selected depending upon whether the present picture is an interlaced picture or a progressive picture, and selects a pattern of which the calculated correlation value is the smallest.  
      An aspect of the sub-sampling unit sub-samples the present image block and the search area by discarding pixels in even lines or odd lines when the determined correlation calculating pattern is a horizontal or vertical pattern, and sub-samples the present image block and the search area by alternately discarding even and odd pixels every line when the determined correlation calculating pattern is a diagonal pattern. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
      The above and/or other features and advantages of the invention will become more apparent and readily appreciated from detailed description of exemplary embodiments thereof with reference to the accompanying drawings in which:  
       FIG. 1  is a diagram illustrating estimation of a motion vector by using a block matching process according to an aspect of the invention;  
       FIG. 2  is a diagram illustrating estimation of a motion vector by performing the block matching process on a search area according to an aspect of the invention;  
       FIG. 3  is a flowchart illustrating a motion vector estimating method according to an aspect of the present invention;  
       FIGS. 4A through 4D  are diagrams illustrating patterns used for calculating correlation values according to an aspect of the invention;  
       FIGS. 5A through 5C  are diagrams illustrating a sub-sampling process according to an aspect of the invention;  
       FIG. 6  is a block diagram illustrating a motion vector estimating apparatus according to an aspect of the invention; and  
       FIG. 7  is a diagram of a display apparatus for generating an image to be displayed according to an aspect of the invention. 
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS  
      Reference will now be made in detail to the embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below to explain the present invention by referring to the figures.  
       FIG. 1  is a diagram illustrating estimation of a motion vector by using a block matching process according to an aspect of the invention. The image used in  FIG. 1  is an airplane shape. When the airplane shape is moved with an advance of time from t 1  to t 2 , it is determined how much the airplane shape is moved by searching a predetermined search area  120  for the same shape as the airplane shape. The searching process may be performed in a unit of macroblock  110 , and it is found out how much the macroblock  110  is moved. For example, the moved macroblock  130  is detected by determining the search area  120  and searching all of the possible image blocks within the range of the search area  120 . A degree of movement of the detected macroblock  130  is considered as a motion vector. The motion vector is dependent on various conditions, such as how the search area  120  is set to and whether the block matching process should be performed on the overall pixels in the search area  120 .  
       FIG. 2  is a diagram illustrating estimation of a motion vector by performing a block matching process on a search area  220 . When estimating a motion vector by using the block matching process, a predetermined search area  220  is defined, sums of absolute differences (SADs) are calculated while moving the macroblock  210  over the search area  220 , and an image block of which the SAD is the smallest is detected, thereby determining a motion vector (MVx, MVy) of a k-th macroblock  210 . The SADs may be calculated using Equation 1:  
                     (     MVx   ,   MVy     )     =       ⁢     arg   ⁢           ⁢   min   ⁢           ⁢         SAD   k         (     m   ,   n     )     ∈   S       ⁡     (     m   ,   n     )                         SAD   k     ⁡     (     m   ,   n     )       =       ⁢       ∑     i   =   0     16     ⁢           ⁢       ∑     j   =   0     16     ⁢           ⁢            F     i   ,   j       -     F       i   +   m     ,     j   +   n       R                              (     Equation   ⁢           ⁢   1     )               
      That is, the SADs are calculated from pixel values of the present image block and the search area while moving the present image block  210  over the search area  220  by m pixels in a horizontal direction and n pixels in a vertical direction. Since the calculation of SAD is carried out to all the pixels in the search area  220 , m and n can become ±sx and ±sy, respectively. When the SAD of the image block after movement by m and n pixels is the smallest, (m, n) is a motion vector (MVx, MVy). In this way, the SADs are calculated while moving the present image block  210  over the search area  220 . F i,j  used in the calculation of SAD is a brightness of a pixel located at an i-th row and a j-th column in a present frame or field, and F R   i+mj+n  is a brightness of a pixel located at an i+m row and a j+n column in a reference frame or field. If the search area for a motion vector is set to ±sx in a horizontal direction and ±sy in a vertical direction, the calculation of SAD should be carried out as many times as (2sx+1)×(2sy+1) so as to estimate a motion vector of one macroblock  210 .  
       FIG. 3  is a flowchart illustrating a motion vector estimating method according to an aspect of the invention. In operation  310 , a type of an input picture is checked. That is, it is determined whether the input picture is an interlaced picture or a progressive picture. In operation  320 , when the input picture is the interlaced picture, correlation calculating patterns only in horizontal and diagonal directions are used to calculate the correlation values without using a correlation calculating pattern in a vertical direction. In operation  330 , when the input picture is the progressive picture, the correlation calculating patterns in the horizontal, vertical and diagonal directions are used to calculate the correlation values.  
       FIGS. 4A through 4D  are diagrams illustrating examples of patterns used for calculating the correlation values. When the present picture is the progressive picture, the correlation values are calculated in accordance with the patterns shown in  FIGS. 4A through 4D , and when the present picture is the interlaced picture, the correlation values are calculated in accordance with the patterns shown in  FIGS. 4B through 4D . In operation  340 , one correlation calculating pattern is selected on the basis of the calculation result.  
      The selection of the correlation calculating pattern is carried out on the basis of the correlation values between the pixels. For example, in the present macro block, the correlation values between the adjacent pixels, using the patterns shown in  FIGS. 4A through 4D , are calculated, and the pattern having the smallest correlation value is selected. The calculation of correlation values can be carried out, for example, by using a difference in brightness between a hatched pixel and a pixel adjacent thereto. In operation  350 , the search area and the present macroblock are sub-sampled correspondingly with the selected pattern. The sub-sampling process will be described later with reference to  FIGS. 5A through 5C . The SAD of the sub-sampled macroblock and the search area is calculated, thereby determining a motion vector. In operation  370 , the determined motion vector is converted into a size corresponding to a size of the motion vector before carrying out the sub-sampling process. That is, since the sub-sampling process has been carried out, a size of the original image has been decreased into a half, and thus the size of the motion vector has been decreased into a half, so that the size of the motion vector is doubled to correspond to the size of the original image.  
       FIGS. 5A through 5C  are diagrams illustrating an example of the sub-sampling process. When the vertical correlation calculating pattern shown in  FIG. 4A  is used, a sub-sampling pattern shown in  FIG. 5A  is used. When the horizontal correlation calculating pattern shown in  FIG. 4B  is used, a sub-sampling pattern shown in  FIG. 5B  is used. When the diagonal correlation calculating pattern shown in  FIG. 4C  or  4 D is used, a sub-sampling pattern shown in  FIG. 5C  is used.  
       FIG. 6  is a block diagram illustrating a motion vector estimating apparatus  600  according to an aspect of the invention. The motion vector estimating apparatus  600  includes a pattern determining unit  610 , a sub-sampling unit  620 , and a motion vector estimating unit  630 . It is understood that the apparatus can be included in a display in an apparatus used to generate images to be displayed and/or in a computer used to display images. Further, the images can be reproduced from a medium in the apparatus or from the transmitted data.  
      The pattern determining unit  610  calculates the correlation values corresponding to a plurality of correlation calculating patterns selected in accordance with characteristic data of the present picture, and determines the correlation calculating pattern on the basis of the calculation result. That is, the pattern determining unit  610  calculates the correlation values of a predetermined pattern selected depending upon whether the present picture is an interlaced picture or a progressive picture, and then selects a pattern of which the correlation value is the smallest. The correlation value may relate to either adjacent pixels or a difference in brightness between a hatched pixel and a pixel adjacent thereto.  
      The sub-sampling unit  620  selects a sub-sampling pattern corresponding to the determined correlation calculating pattern, and sub-samples the present image block and the search area. That is, the sub-sampling unit  620  sub-samples the present image block and the search area by discarding pixels in even lines or odd lines when the determined correlation calculating pattern is the horizontal or vertical pattern, and sub-samples the present image block and the search area by alternately discarding even and odd pixels on every line when the determined correlation calculating pattern is a diagonal pattern. The sub-sampling unit  620  also converts the estimated motion vector into a size corresponding to the size of the search area before carrying out the sub-sampling process. The motion vector estimating unit  630  estimates the motion vector of the sub-sampled image block and the sub-sampled search area. That is, the motion vector is estimated by calculating the SAD between the pixels.  
      Estimation of the motion vector using the sub-sampling process is described below in more detail. In the left pattern of  FIG. 5A  or  5 B, horizontal pixel components of the macroblock and the search area take odd pixels of the original image through the sub-sampling process, and in the right pattern of  FIG. 5A  or  5 B, horizontal pixel components of the macroblock and the search area take even pixels of the original image through the sub-sampling process. In the pattern of  FIG. 5C , the macroblock and the search area alternately take the even pixels and the odd pixels of the original image. The motion vector is determined on the basis of the SAD in the vertical even line and the SAD in the vertical odd line. That is, a horizontal component of the motion vector has the even pixel component or the odd pixel component on the basis of comparison of the two SADs.  
      The aforementioned motion vector estimating method may be embodied as a computer program read by at least one computer. Codes and code segments constituting the programs can be easily construed by programmers skilled in the art to which the present invention pertains. The motion vector estimating method according to an aspect of the invention is embodied by storing the program on at least one computer readable medium and executing the program on at least one computer. Examples of the computer readable media include magnetic storage medium, optical recording media, and carrier waves.  
       FIG. 7  is a diagram illustrating a display apparatus  700  for generating an image to be displayed. The display apparatus  700  includes at least one display device  710  to display the generated image and the motion vector estimating apparatus  600 , as illustrated in  FIG. 6 . The motion vector estimating apparatus  600  provides a calculated motion vector to the at least one display device  710  so that an image is displayed. The display device  710  may include a television monitor, a computer monitor, etc. It is further understood that the display device  710  may be located inside of or integral with the display apparatus  700 .  
      As described above, according to the invention, it is possible to avoid deterioration of the image quality and reduce the amount of calculation into a half or less of (2sx+1)×(2sy+1) in estimating a motion vector of a macroblock.  
      Although a few embodiments of the present invention have been shown and described, it would 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 claims and their equivalents.