KR19990086890A - Motion estimation method - Google Patents

Abstract

A motion estimation method for finding the most similar block among pictures after obtaining a motion vector to remove the redundancy of the time axis. In particular, a first step of obtaining a median value of motion vectors of a plurality of neighboring macroblocks already obtained; The second step is to perform motion estimation by obtaining the motion vector of the current macroblock in the given search area based on the value, and obtain the motion vector using the new search area obtained by the neighboring motion vector, and then perform the motion estimation. The motion estimation capability has been improved in this fast moving image, and it can be applied to products that need to find a fast moving motion vector with a small amount of computation in the future. In particular, in the case of limited encoder performance or when real-time processing is required, a motion vector must be found in a small search area, and in this case, a more accurate motion vector can be found.

Description

Motion estimation method

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to video compression, and more particularly, to a motion estimation method in a moving picture expert group (MPEG) encoder.

Key factors supporting multimedia include digitalization and image compression technology. Recently, digitalization of information has been rapidly developed, and image compression technology is very important.

Moving Pictures Expert Group (MPEG) is an international standard for the compression encoding of digital video, the most critical technology in a multimedia environment.

At this time, in order to efficiently compress the video sequence that changes with time, it is absolutely necessary to remove the redundancy of the time axis as well as the two-dimensional redundancy of the image data. Therefore, the MPEG video compression algorithm is based on two basic techniques. . In other words, a block-based motion estimation and compensation are used to reduce temporal redundancy, and a discrete cosine transform (DCT) is used to reduce spatial redundancy.

FIG. 1 is a block diagram of a general video compression, in particular, an MPEG encoder. The DCT unit 11 removes correlation of data through two-dimensional axis transformation. For this purpose, each block divided after a picture by a block unit is divided. The axis is converted according to the DCT equation. The axially transformed data tends to converge in one direction (lower frequency side). Only the collected data are quantized in the quantization unit 12 and then output to the variable length coding (VLC) unit 13. The VLC unit 13 displays a frequent value as a small number of bits and a rare value as a large number of bits to reduce the total number of bits and then transmit the first-in-first-out (FIFO) memory 17. In addition, the quantized data is dequantized by the inverse quantization unit 14 and IDCT by the IDCT unit 15 and then output to the motion estimation / motion compensation (ME / MC) unit 16.

On the other hand, since pictures that are continuous on the time axis mainly move a person or an object in the center portion of the screen, the motion estimation and compensation unit 16 uses this property to remove the redundancy of the time axis. That is, the amount of data to be transmitted can be greatly reduced by taking and filling a similar portion from the previous picture even if it is not changed or moved.

For example, when the output of the IDCT unit 15 and the output of the motion estimation and compensation unit 16 are added and stored in the frame memory, the data stored in the frame memory when the motion of the currently input picture is estimated becomes the previous picture.

Finding the most similar block among the pictures is called motion estimation and motion vector (MV) is used to represent the displacement of how much motion is moved.

The motion compensation process uses forward and backward prediction blocks, and there are two motion compensation frames. P-frames are motion compensated only by forward prediction and are used to predict the next P-frame by itself. It is also used for forward and backward prediction of B-frames (frames predicted in both directions). However, B-frames are not used for prediction by themselves.

In other words, an I (Intra) picture is a reference picture when compressing and encoding an arbitrary picture, and removes only redundancy in a spatial direction by applying DCT transformation and quantization processes of the original signal for each block. P (Predicted) picture is predicted closest to the original picture from I, P-picture. Prediction error signal and motion vector between motion compensation with I-picture or P-picture already encoded are encoded per macroblock, and prediction error. The signal is quantized and VLC after a DCT operation per block. Bi-Directional (B) pictures are predicted only in the previous I- and P-pictures to construct the screen, and then I- and P-pictures are predicted in the reverse direction. It's a rather complex picture that creates an averaged picture and selects the predicted picture that most closely resembles the original.

The I picture is input to the DCT unit 11 as it is to perform DCT, and the I or P picture is compensated for by the motion estimation and motion compensation unit 16, and then the difference between the current input signal and the DCT unit 11. Output to DCT.

As described above, the motion estimation and compensator 16 utilizes the fact that the current frame is significantly associated with the previous frame in the transmission of successive moving images. The motion estimation and compensation unit 16 divides the image processing into units of 16 × 16 macroblocks in a given search area. Compared to the pixels of the previous frame to find the most close motion vector, the motion vector obtained here can similarly reconstruct a large part of the original image.

The image reconstructed by the motion vector has a great effect, especially on a background screen having a small movement, and thus an image quality almost close to the original image can be obtained. However, in the part where the motion changes drastically, the difference is larger than the original image. In this case, the image quality can be reconstructed close to the original image by sending additional pixel information to perform intra coding or compensate for the difference without using a motion vector. do. Therefore, the compression rate can be further increased depending on how well the motion vectors are found.

2 is a general motion estimation method, in which a search region is determined by a value of f_code, and the position vector having the smallest difference with the previous frame is found within the range. Here, the f_code value is determined according to the capability of the encoder. In other words, the larger the f_code value, the wider the search region, and thus the faster the motion vector can be found. However, since the computational amount increases, the appropriate search region should be selected in consideration of the encoder's performance or the speed of the motion vector.

For example, the increase of the motion estimation calculation amount according to the change of the search area is as follows.

Search range when f_code = 1: [-8 ∼ 7] in each direction of x, y

(16 × 16 addition and subtraction per pixel) × 16 × 16 = 65,536 additions, subtractions + 256 comparisons.

Search range when f_code = 2: [-16 ~ 15] in each direction of x and y

(16 × 16 addition and subtraction per pixel) × 32 × 32 = 262,114 additions, subtractions + 1024 comparisons.

Therefore, it can be seen that the computation amount increases by four times whenever the f_code value increases by one.

As such, how efficiently a motion vector is found in the video compression greatly affects the compression ratio and the image quality. In particular, the lower the bitrate, the greater the importance of motion estimation and the search area should be widened to find a more accurate motion vector. However, if the search area is widened, the amount of computation increases.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and an object of the present invention is to find a motion vector in a given search range based on a median value of motion vectors of three neighboring macroblocks previously obtained, so that even in a small search area. The present invention provides a motion estimation method for finding an accurate motion vector.

1 is a block diagram of a typical MPEG encoder

2 is a diagram illustrating a process of finding a motion vector in a conventional motion estimation method.

3 is a diagram illustrating an embodiment of a process of finding a motion vector of a current macroblock in a motion estimation method according to the present invention;

4 is a flowchart illustrating a motion estimation process of FIG. 3.

5 is a view showing another embodiment of a process of finding a motion vector of a current macroblock in a motion estimation method according to the present invention;

6 is a table showing experimental results by the motion estimation method of FIG. 3.

FIG. 7 is a table showing experimental results by the motion estimation method of FIG. 5.

Explanation of symbols for main parts of the drawings

11 DCT unit 12 quantization unit

13: VLC section 14: inverse quantization section

15: IDCT unit 16: motion estimation and compensation unit

17: FIFO

According to an aspect of the present invention, there is provided a motion estimation method comprising: a first step of obtaining a median of motion vectors of a plurality of neighboring macroblocks already obtained, and a current macroblock in a given search region based on the median And a second step of performing a motion estimation by obtaining a motion vector of.

The first step is characterized by defining the motion vectors of the plurality of previous macro blocks most relevant to the current macro block.

The motion vectors of the plurality of neighboring macroblocks of the first step may include a motion vector MV1 of the macroblock immediately preceding the current macroblock, a motion vector MV2 of the macroblock located immediately above the current macroblock, and the following. It is characterized by being defined as the motion vector MV3 of the macro block.

The motion vectors of the plurality of neighboring macroblocks of the first step include the motion vector MV1 of the macroblock located immediately before the current macroblock, the motion vector MV2 of the macroblock located immediately above the current macroblock, and the current macro. Characterized in that it is defined as the motion vector (MV3) of the previous frame corresponding to the position of the block.

The second step is characterized in that a motion vector is found in a given search area based on a value of a difference between the intermediate value and the current position having a small difference between the previous frame.

The second step is characterized by finding a SAD (Sum of Absolute Difference) for the intermediate value and the SAD value of the current macroblock and finding a motion vector in a given search region based on the position of the smallest SAD value.

Other objects, features and advantages of the present invention will become apparent from the following detailed description of embodiments taken in conjunction with the accompanying drawings.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings.

Efficient motion estimation in video compression increases the video compression rate and improves the picture quality. At this time, in case of limited encoder performance or real time processing, the actual motion vector should be effectively found in a small search area. In particular, the lower the bitrate, the greater the importance of motion estimation and a more accurate motion vector must be found for this purpose.

Accordingly, the present invention finds a motion vector by using the correlation vectors of neighboring macroblocks.

3 illustrates an embodiment of a motion estimation method according to the present invention. When obtaining a motion vector of a current macroblock, a median value is obtained from three neighboring candidate vectors MV1 and MV2.MV3. The three candidate vectors MV1, MV2, and MV3 are previously obtained motion vectors, the motion vector MV1 of the immediately preceding macroblock of the current macroblock, and the motion vector of the macroblock located immediately above the current macroblock. MV2), the motion vector of the next macroblock (MV3), which has the most association with the motion vector of the current macroblock.

Then, among the above three candidate vectors MV1, MV2, and MV3, the median of the x coordinate and the median of the y coordinate are found, respectively. For example, if the x, y value of MV1 is {4,7}, the x, y value of MV2 is {5,6}, and the x, y value of MV3 is {3,5}, the median value is {4, 6}. After calculating the SAD (Sum of Absolute Difference) for the intermediate value and the SAD value of the current macroblock, the motion vector is searched in the given search region based on the position of the smallest SAD value. That is, the motion vector is searched for in a given search area based on the value of the difference between the intermediate value and the current position and the previous frame.

This takes into account the stationary state where the motion direction of the obtained intermediate value is opposite or no motion direction of the current macroblock.If there is no motion or the direction of motion is opposite, the motion vector is searched in the given search area based on the current position value. If the motion directions are similar, the motion vector is searched for in the given search area based on the median value.

Here, when the motion vector is found based on the median value, as shown in FIG. 3, it can be seen that only the search region is changed around the reference point found as the median value while the f_code value is maintained as it is. This is effective when the movement is fast and the search area is small.

4 is a flowchart illustrating a motion estimation process of FIG. 3.

As described above, in the case of similar motions, the present invention was previously made by using the fact that the motion vector of the neighboring block has much correlation with the motion vector of the current block, rather than finding the motion search region in the given search range around the existing zero. By finding a motion vector in a given search range based on the median value of three neighboring motion vectors, it is possible to find a more accurate motion vector even in a small search range. You can get it.

5 is another embodiment of a motion estimation method according to the present invention. The difference from FIG. 3 is the definition of the third candidate vector MV3, and FIG. 5 shows the motion of the previous frame corresponding to the position of the current macro block. Vectors were defined. Then, an intermediate value is obtained from the three candidate vectors (MV1, MV2.MV3), the SAD of the intermediate value and the SAD value of the current macroblock are calculated, and then, in the given search region based on the position of the smallest SAD value Find the motion vector. Since the process is the same as FIG.

This is because the motion vector to be obtained has the most correlation with the motion vector of the corresponding position of the previous frame. It can be seen that the method of FIG. 5 is more efficient than the method of FIG. This can be seen in FIGS. 6 and 7.

6 and 7 show the results of experiments by the conventional motion estimation method and the motion estimation method according to the present invention as a table, and the experimental conditions are assumed to be encoders of limited performance with low bitrate. 6 is an experimental result of FIG. 3, and FIG. 7 is an experimental result of FIG. 5. However, FIG. 5 has a disadvantage of occupying space in the memory because it must store the motion vector of the previous frame.

The present invention has a great effect when applied to the fast moving moving picture compression in the encoder having a limited performance, in particular can be applied to both the existing MPEG-2 and the current MPEG-4.

As described above, according to the motion estimation method according to the present invention, by estimating the motion vector using the new search region obtained by the neighboring motion vector, the motion estimation capability is improved in the fast moving image, and the amount of computation in the future is small. It can be applied to products that need to find fast moving motion vectors.

In particular, when limited encoder performance or real-time processing is required, the motion vectors must be found in a small search area. In this case, more accurate motion vectors can be found. Good picture quality can be obtained.

Claims (6)

In the motion estimation method to find the most similar block between the pictures to find the motion vector to remove the redundancy of the time axis, A first step of obtaining an intermediate value of motion vectors of a plurality of neighboring macroblocks already obtained; And a second step of performing motion estimation by obtaining a motion vector of a current macroblock in a given search region based on the intermediate value. The method of claim 1, wherein the first step A motion estimation method characterized by finding an intermediate value from motion vectors of a plurality of previous macro blocks most relevant to the current macro block. The method of claim 1, wherein the motion vectors of the plurality of neighboring macroblocks of the first step And a motion vector MV1 of the macro block located immediately before the current macro block, a motion vector MV2 of the macro block located directly above the current macro block, and a motion vector MV3 of the next macro block. Motion estimation method. The method of claim 1, wherein the motion vectors of the plurality of neighboring macroblocks of the first step The motion vector MV1 of the macro block located immediately before the current macro block, the motion vector MV2 of the macro block located directly above the current macro block, and the motion vector MV3 of the previous frame corresponding to the position of the current macro block. Motion estimation method, characterized in that defined by. The method of claim 1, wherein the second step And a motion vector is found in a given search region based on the value of the difference between the intermediate value and the current position and the previous frame. The method of claim 1, wherein the second step A method of estimating a motion vector in a given search region based on a position of a small SAD value after calculating a SAD value of the intermediate value and a SAD value of a current macroblock.