KR20020010171A - Adaptive Predicted Direction Search Method for Block Matching Motion Estimation - Google Patents

Abstract

PURPOSE: An adaptive prediction directivity searching method for block matching motion estimation, which estimates motion vector using time correlation in continuous frames of a motion picture and spatial correlation between blocks in the current frame, is provided to improve compression performance and prevent local searching caused by insufficient information. CONSTITUTION: A motion direction of the current frame block is calculated using motion vector of the previous frame block and motion vector of the previous blocks in the current frame. The first search point is calculated in the calculated motion direction of the current frame block. A search area is set based on the first search point, and motion vector is found from search points constructing the searching area.

Description

Adaptive Predicted Direction Search Method for Block Matching Motion Estimation}

The present invention relates to a motion estimation method of an image encoding system. More specifically, the present invention relates to a motion estimation method using a temporal association between blocks and a spatial association between blocks within a current frame. An adaptive prediction directional search method for block matching motion estimation is performed.

1 is a block diagram of a general video encoding system. The raw image data input to the video encoding system is input to the motion estimation and compensation unit 101. The motion estimation and compensation unit 101 performs motion estimation using previous image data, and removes duplicate data in the time domain existing in the original image data, and outputs motion compensated image data. The inter / intra mode determiner 102 calculates the prediction error in the spatial domain for the original image data and the motion compensated image data, and then determines the inter / intra mode using the calculated prediction error. Output the signal.

Next, the selector 103 selects original image data when the mode determination signal output from the inter / intra mode determination unit 102 is an intra mode (INTRA_MODE), and when the mode determination signal is an inter mode (INTER_MODE). Next, motion compensated image data is selected and output to the image encoder 104. The image encoder 104 encodes image data output from the selector 103 and outputs the encoded bitstream to the outside. In this case, the image encoder 104 performs image encoding by removing redundant data in the spatial region of the input image data.

Such an image encoding system needs to accurately find a motion vector by the motion estimation and compensator 101. If the motion vector is not accurate, the inter / intra mode determination unit 102 may incorrectly determine an encoding mode. Grows That is, it is necessary to encode the motion compensated image data by determining the inter mode, and by encoding the original image data by determining the intra mode, the coding efficiency is reduced. In addition, when the motion vector is not accurate in this way, since the information amount of the motion compensated image data increases, even if the inter / intra mode determiner makes the correct mode determination, the encoding efficiency of the image decreases.

Motion estimation in the motion estimation and compensation unit of the video encoding system includes a global search method and a fast search method. The global search method performs a motion search on all points included in the search area around the position of the previous frame block having the same coordinates as the current frame block to find the best motion vector. This global search method has the advantage of finding the optimal motion vector among the motion estimation techniques, while it has the disadvantage that the computational amount is too large because it searches all the points included in the search area.

The fast search method is a proposed search method for reducing the calculation amount, which is a disadvantage of the global search method described above, and includes a three-step search method or a diamond search method. In order to reduce the amount of computation, the fast search method searches local motions by searching only a few specific search points to find a motion vector. As a result, the compression performance of the image is degraded.

Accordingly, an object of the present invention for solving the above problems of the prior art, a motion vector by using the temporal association in a continuous frame and the spatial association between blocks within the current frame in the case of a moving image By estimating a, an object of the present invention is to provide an adaptive prediction directional search method for block matching motion estimation that can improve local compression performance and prevent local search caused by insufficient information.

1 is a block diagram of a general video encoding system;

2 is a graph showing a relationship between a position and an angle of a motion vector;

3 is a graph illustrating a relationship between a final angle of a motion vector and a direction of a block;

4 is a view illustrating a principle of using spatial correlation in a current frame;

5 is a graph illustrating a motion vector search estimation process according to the present invention;

6 is a diagram illustrating a search region reset according to two search patterns according to the present invention.

According to an aspect of the present invention, an adaptive prediction directional search method for block matching motion estimation according to the present invention is directed to an adaptive prediction directional search method for block matching motion estimation using spatiotemporal characteristics in a frame including motion information. ,

Calculating a motion direction of the current frame block by using the motion vector of the previous frame block and the motion vector of the previous blocks in the current frame;

A second step of calculating a first search position in the movement direction of the current frame block calculated in the first step; And

And a third step of setting a search area around the first search position determined in the second step and searching for a motion vector at the search point constituting the search area.

According to the present invention, there is provided a computer-readable recording medium having recorded thereon a program for executing the adaptive predictive directional search method for the block-matched motion estimation as described above.

Hereinafter, an adaptive prediction directional searching method for block matching motion estimation according to an embodiment of the present invention will be described in detail with reference to the accompanying drawings.

An adaptive prediction directional searching method according to the present invention includes a first step of calculating a motion direction through a motion vector of a previous frame block and a motion vector of previous blocks in a current frame; A second step of calculating a first search position in the direction calculated in the first step; And a third step of searching for a motion vector in a search area consisting of nine adjacent search points based on the position determined in the second step.

Equation 1 is used to determine the direction of movement in the first step.

Here, 'asin' is an arcsine function, and x and y are components of the motion vector of the previous frame block. Here, the obtained defense MVAngle is the one quadrant angle in FIG. 2 is a graph showing a relationship between a motion vector and a final angle. That is, the method of calculating the angle according to the position of the motion vector is displayed.

In Equation 1 above, the variable MVAngle is an angle of one quadrant. Therefore, in order to calculate the final angle FMVAngle, the position of the motion vector must be taken into account. The method for calculating the final angle (FMVAngle) is defined in Table 1 below.

The relationship between the final angle of the motion vector calculated by applying MVAngle calculated in Equation 1 to Table 1 and the direction of the block is defined in Table 2 and illustrated in FIG. 3.

The reason for using the directionality of the previous frame block is that since there are many temporal associations in the sequence of images, the probability of successive frame blocks is very high. Table 3 shows the number and probability of successive frame blocks in each image having the same direction, and proceeds in the same direction with a probability of 96.36% and 77.50%.

In addition, in order to take advantage of spatial associations, the orientation of the previous three blocks shown in FIG. 4 is used. That is, the directions of the previous blocks 1, 2 and 3 are used to calculate the directionality of the current frame block 5.

As a result, it is possible to accurately predict the first search position of the current frame block by using the temporal characteristic that the consecutive frames in the movie are more likely to have the same direction and the spatial characteristic that the movement of the previous blocks in the current frame is similar. Do it.

That is, when the direction of each frame block is obtained through the above process, the first search position is determined by multiplying the direction of the block by a weight value. If this is defined as an equation, it is the same as Equation 2.

In the above equation, W is a weight, Vxk is the Vx value of FMVAngle, and Vyk is the Vy value of FMVAngle. In the variable k value, 1 denotes a previous frame block using temporal characteristics, and 2, 3, and 4 denote current frame blocks using spatial characteristics. The direction of these blocks is used to move the first search position and to search for the motion vector of the current block at the moved position.

Looking at the search process, by setting the search area (3 × 3) around the first search position, the search is performed using nine search points. If the smallest SAD (Sum of Absolute Difference) of the nine points, that is, the point with the sum of the absolute values of the differences, is the same as in the previous search, that is, the point with the smallest SAD is the center point of the search region (α, α ) To end the search, otherwise repeat the following steps:

That is, if the point having the smallest SAD in the search process is the horizontal or vertical direction of the center point (α, α) of the search area, for example, the point having the smallest SAD is (α-1, α), (α + 1, If one of α), (α, α + 1) and (α, α-1) adds three new search points with a search pattern as shown in Fig. 6A, the smallest one found above The motion vector is estimated again by resetting the search area with the point having SAD as the center point. At this time, in the process of resetting the new search area, ignore all points outside the search area, redefine the point having the smallest SAD at each step, and if the point having the smallest SAD is the same as the point having the smallest SAD in the previous step, End the search.

On the other hand, if the point having the smallest SAD in the diagonal direction of the center point (α, α) of the search area in the search process, for example, the point having the smallest SAD is (α-1, α-1), (α-1, α + 1), (α + 1, α-1), (α + 1, α + 1)], five new search points are created with a search pattern as shown in FIG. In addition, we estimate the motion vector again with the midpoint of the point with the smallest SAD found above. At this time, in the process of resetting the new search area, ignore all points outside the search area, redefine the point having the smallest SAD at each step, and if the point having the smallest SAD is the same as the point having the smallest SAD in the previous step, End the search.

While the invention has been described above based on the preferred embodiments thereof, these embodiments are intended to illustrate rather than limit the invention. It will be apparent to those skilled in the art that various changes, modifications, or adjustments to the above embodiments can be made without departing from the spirit of the invention. Therefore, the protection scope of the present invention will be limited only by the appended claims, and should be construed as including all such changes, modifications or adjustments.

As described above, according to the present invention, the compression performance of the image is excellent by predicting and correcting in which direction the movement of the current image will proceed using the spatiotemporal correlation of the video.

Claims (5)

An adaptive prediction directional search method for block matching motion estimation using space-time characteristics in successive image frames, Calculating a motion direction of the current frame block by using the motion vector of the previous frame block and the motion vector of the previous blocks in the current frame; A second step of calculating a first search position in the movement direction of the current frame block calculated in the first step; And An adaptive prediction directional search for block-matched motion estimation comprising: setting a search region around the first search position determined in the second step and finding a motion vector at a search point constituting the search region; Way. The method of claim 1, The first step is, After applying the motion vector (x, y) of the previous frame block to the following equation to obtain the angle (MVAngle) of the motion vector, the block-matched motion estimation, characterized in that to obtain the final angle (FMVAngle) according to the position of the motion vector Adaptive Prediction Directional Search Method. <Equation> The method of claim 1, The second step, The method of claim 1, wherein the first search position is obtained by multiplying the directions of the blocks obtained in the first step by a weight. The method of claim 1, The third step, A first sub-step of setting a search area of 3 × 3 around the first search position; A second substep of obtaining SADs of nine search points constituting the 3 × 3 search area; And If the point having the smallest SAD of the nine search points is the center point of the search area, the search is terminated, and if the point is not the center point, the new 3x3 search area is reset to the center point of the point having the smallest SAD. And a third sub-step proceeding to the second sub-step. In the video encoding device, Calculating a motion direction of the current frame block by using the motion vector of the previous frame block and the motion vector of the previous blocks in the current frame; A second step of calculating a first search position in the movement direction of the current frame block calculated in the first step; And And a third step of setting a search area based on the first search position determined in the second step and finding a motion vector at the search points constituting the search area. A computer-readable recording medium recording a program for realizing an adaptive predictive directional searching method for motion estimation. .