CN1181691C - Video Motion Estimation Methods - Google Patents

Abstract

The present invention relates to a method for carrying out motion estimation on the basis of the space coherence of a motion vector field in a searching mode. The present invention comprises the steps that a group of candidate vectors are determined on the basis of a block matching and searching order, according to the motion vectors of some nearby blocks and by an updating mechanism; for each candidate vector, the errors of the current pixel block and a matched reference pixel block thereof are worked out; the errors of the current pixel block and a pixel block at the same position in a reference frame are worked out; the vector with the minimal error value is determined as a motion vector; the estimated motion vector is treated by median filtering to smoothen a vector field. The present invention has the advantages of small calculation amount and low cost. Because the correctness of motion estimation is enhanced, the true motion of an object can be well described by the motion vector field.

Description

Video Motion Estimation Methods

Technical field

The invention belongs to the technical field of digital video processing, and in particular relates to a method for motion estimation by utilizing the time-space correlation of the motion vector field based on the block matching search order.

Background technique

For a long time, motion estimation technology has been widely used in video compression coding and digital video format conversion and other fields. In order to minimize the bandwidth required to transmit digital video data of a given picture quality, a variety of different video compression algorithms have been developed for compressing video data. Several multimedia specification committees have established and proposed standards for encoding/compressing audio and video data. Among them, the well-known and widely accepted international standards are provided by the Moving Picture Experts Group (MPEG), including MPEG-1 and MPEG-2 standards.

Video coding methods mainly include intra-frame compression and inter-frame compression, among which inter-frame compression is the main source of its compression ratio, so existing video compression standards (MPEG1/2/4, H.261/3, etc.) mostly use An inter-frame compression scheme based on motion estimation. The principle is to first divide the current frame into several blocks of the same size, and then search for the most similar matching block within a window of a certain size of the reference frame for each block (current block). The position difference between the current block and the matching block is called a motion vector, and the pixel difference is called a residual block. Since there are many pixels close to 0 in the residual block, the compression ratio can be greatly improved through DCT transformation, quantization, and entropy coding. In the above process, motion estimation is the link of searching for the best matching block. Obviously, motion estimation is not only the most time-consuming, but also directly affects the compression efficiency, which is the key and bottleneck of video compression.

Scanning format conversion is a common problem in computing video, high-definition television, and traditional TV in the current network environment. Scanning formats need to be converted between different systems. Deinterleaving is an essential requirement for conversion of all scan formats in practice. Many deinterleaving algorithms have been proposed, including simple spatial deinterleaving methods and advanced motion compensation deinterleaving methods. The key technology of motion compensation de-interleaving is motion estimation, the complexity and performance of motion estimation will directly determine the complexity and performance of motion compensation de-interleaving. The de-interlacing technology is different from the video compression coding technology for motion estimation, and it emphasizes that the motion vector conforms to the real motion of the object.

Many existing motion estimation methods have some defects: the amount of calculation is too large, and the cost of implementation is high, such as the full search algorithm; assuming the monotonicity of the error surface, it is easy to fall into local optimum, such as some classic block matching methods , such as the three-step method. Most importantly, none of these motion estimation methods can describe the real motion of objects well.

Patent No. 01801368.6 discloses a method of motion estimation. The method first determines a group of candidate vectors for the current pixel block, then selects the optimal candidate vector as the starting point of the search, and searches in a predetermined area to obtain the final motion vector. Patent No. 01100544.0 discloses another method of motion estimation. This method first determines an optimal search starting point for the current search block, then uses a diamond search, and terminates the search process adaptively. Both methods use a fixed order from top to bottom and left to right for block matching search, and use the correlation of the motion vector field in this order to reduce the amount of calculation of motion estimation and improve search speed and accuracy. The number and position of the candidate vectors of these two methods are fixed, and the estimated motion vectors are no longer processed. Using a fixed order to search for block matching can not make full use of the correlation of the motion vector space, and the performance of motion estimation is not evenly distributed in the image space.

Contents of Invention

The purpose of the present invention is to provide a method for motion estimation by using the temporal-spatial correlation of the motion vector field based on the search order of the block matching to address the defects or deficiencies in the prior art. The motion vector estimated by this method can better describe the real motion of the object.

The method includes the following steps: (a) based on the order of block matching search, a group of candidate vectors is determined according to the motion vectors of several blocks near the current block and an update mechanism; (b) for each of the candidate vectors, Calculate the error of the current pixel block and its matching reference pixel block; calculate the error of the current pixel block and the same position pixel block in the reference frame at the same time, and select the vector with the minimum error value above as the motion vector; (c) to the estimated motion vector Perform median filtering to smooth the vector field. Of course, in step (b), the motion vector indicating that the current pixel block matches the pixel block at the same position in the reference frame can be used as another candidate vector in step (a), and the matching errors corresponding to these candidate vectors are calculated at the same time.

The order of block matching search in step (a) can be from top to bottom from left to right, from bottom to top from left to right, from top to bottom from right to left, from bottom to top from right to left; From top to bottom, alternately left to right and right to left, from bottom to top, alternately left to right and right to left; from all around to the center.

The step (a) includes the following steps: (1) According to the order of block matching search, select motion vectors of two processed blocks and a motion vector of an unprocessed block, a total of three vectors are used as initially determined candidate vectors. Two blocks that have been processed select the horizontally and vertically adjacent blocks to the current block; one unprocessed block selects the block in the 45-degree diagonal direction of the current block. (2) Update the initially determined candidate vectors according to an update mechanism.

The update mechanism in step (2) in step (a) is: firstly select one of the two motion vectors of the blocks that have been processed according to the order of matching search among the initially determined candidate vectors in an alternate order. Then, in a predetermined range of vector space, a vector is randomly selected, and this vector is added to the initially determined candidate vector selected for updating to form an updated vector. This updated vector and the other two initially determined candidate vectors which have not been updated together constitute a set of candidate vectors.

Calculating the error in step (b) includes the following steps: (1) expanding the pixel block of the current frame/field to be processed and matching the boundary of the pixel block of the corresponding reference frame through the candidate vector, and subsampling it; (2) For the sub-sampled block pixels, the error between the current pixel block and its matching reference pixel block is calculated.

The calculation error in step (b) may not be sub-sampled, and the error between the current pixel block and its matching reference pixel block is directly calculated.

A simple implementation of reducing the amount of calculation to calculate the error value of the current pixel block and its matching reference pixel block in step (b) includes the following steps: (1) sum the corresponding number of pixels of the current pixel block; The corresponding number of pixels of the reference frame pixel block is summed; (3) the absolute difference of the above two sums is calculated to obtain the motion estimation error. Of course, the SAD values of these pixels can also be directly calculated as the motion estimation error.

Step (c) comprises the following steps: (1) respectively adopting 3*3 2-dimensional median filtering to the horizontal and vertical components of the block motion vector; (2) processing the result of the median filtering output: the output of the median filtering The motion vector composed of the horizontal component and the vertical component, if this vector is not any of the 8 adjacent block motion vectors of the current block participating in the median filter, the motion vector of the original current block is taken as the output, otherwise the result of the median filter is taken as output.

The invention can perform motion estimation on video signals of various formats. In particular, the invention is applicable to motion estimation of digital high definition television signals.

For most images, the moving object is usually larger than the block, and the moving object has inertia, which means that the motion vector field has a great correlation in time and space. Using this correlation can find matching blocks faster and more accurately, greatly reducing the amount of computation. The search order of the general block matching algorithm is from top to bottom and from left to right. This invention can adopt many other search orders and select candidate vectors based on the search order, which can estimate motion more accurately, so that the estimated motion vector Closer to the real motion of the object. In motion estimation, calculating the matching error is the part with the largest amount of calculation. The invention provides a simple and efficient implementation method, which greatly reduces the amount of calculation and the implementation cost. The invention smoothes the estimated vector field, and can use the motion vectors of adjacent blocks to correct motion estimation errors caused by illumination or noise, which improves the accuracy of motion estimation and makes the motion vector field better Describe the real motion of an object.

Description of drawings

Fig. 1 is a schematic diagram of block matching search sequence;

Fig. 2 is another schematic diagram of block matching search order;

Fig. 3 is another schematic diagram of a block matching search order;

Fig. 4 is a schematic diagram of a candidate vector under the search order in Fig. 2;

Fig. 5 is a schematic diagram of another candidate vector under the search order in Fig. 2;

Fig. 6 is a schematic diagram of enlarging block boundaries for subsampling;

Fig. 7 is a schematic diagram of a motion vector field before median filtering;

Fig. 8 is a schematic diagram of a median-filtered motion vector field.

Detailed ways

FIG. 1 is a traditional way of estimating a motion vector by performing a block matching search on the blocks of the current frame/field from left to right and from top to bottom.

FIG. 2 is to estimate the motion vector by performing a block matching search on the blocks of the current frame/field from top to bottom and alternately from left to right and from right to left.

FIG. 3 is to estimate the motion vector by performing a block matching search on the blocks of the current frame/field in order from the periphery to the center.

Fig. 4 illustrates the selection of a candidate vector next to the search sequence in Fig. 2 . The black block in the figure represents the current pixel block, and the motion vectors of blocks with oblique lines are candidate vectors. For pixel blocks that are searched from left to right, the three candidate vectors are the motion vector of the adjacent block to the left of the current block, the motion vector of the adjacent block directly above the current block, and the motion vector of the adjacent block directly above the current block, and the 45-degree diagonal direction below the current block. A block's motion vector.

Fig. 5 illustrates the selection of another candidate vector under the search order in Fig. 2 . The black block in the figure represents the current pixel block, and the motion vectors of blocks with oblique lines are candidate vectors. For pixel blocks that are searched from right to left, the three candidate vectors are the motion vector of the adjacent block to the right of the current block, the motion vector of the adjacent block directly above the current block, and a The block's motion vector.

Selecting candidate vectors based on the block matching search order can use the motion vectors of blocks that have been processed before, which can make the starting point of the motion estimation search more accurate, speed up the search, and reduce the amount of calculation for the search; based on the search order. Selecting candidate vectors can make better and more full use of the temporal and spatial correlation of the motion vector field, making the performance of motion estimation more evenly distributed in space and improving the visual effect.

Figure 6 illustrates expanding block boundaries for subsampling. Blocks surrounded by thick solid lines are original blocks, and blocks surrounded by thick dashed lines are border-enlarged blocks. □ is the original pixel, ■ is the subsampled selected pixel for motion estimation error calculation. Performing motion estimation on an enlarged block can make the result of motion estimation more accurate and reduce block effects; subsampling can reduce the number of pixels used for motion estimation error calculation and reduce the amount of calculation. There are many types of subsampling sampling structures choose.

Figure 7 illustrates the motion vector field before median filtering. The area surrounded by the thick solid line in the figure is the area where the 2D 3*3 median filter is performed. It can be seen that the motion vector of the current block is incorrect due to reasons such as illumination or noise.

Figure 8 illustrates the median filtered motion vector field. It can be seen that according to the spatial correlation of the motion vector field, the median filter corrects the motion vector of the current block by using the vector of the adjacent block, improves the performance of motion estimation, and makes the motion vector better describe the real motion of the object.

The specific method of the present invention is firstly to select the motion vectors of the two blocks that have been processed and the horizontally adjacent and vertically adjacent blocks of the current block, one The unprocessed motion vector of the block in the 45-degree diagonal direction of the current block (as shown in Figure 4 or Figure 5) is used as the initially determined candidate vector; two of the initially determined candidate vectors have been processed in the order of matching search Select one of the motion vectors of the blocks in an alternating order and randomly select a vector in a predetermined range of vector space, add this vector to the selected candidate vector that needs to be updated to form The updated vector. This updated vector and the other two initially determined candidate vectors which have not been updated together constitute a set of candidate vectors. Then, for each candidate vector, calculate the error between the current pixel block and its matching reference pixel block, and calculate the error between the current pixel block and the same position pixel block in the reference frame, and determine the vector with the smallest error value as the motion vector. The error value can be obtained by calculating the SAD of these pixels, and the smallest SAD is determined as the motion vector. Finally, a 3*3 2-dimensional median filter is used for the horizontal and vertical components of the estimated block motion vector, if the motion vector composed of the horizontal component and the vertical component output by the median filter is not the 8 current blocks participating in the median filter For any one of the motion vectors of adjacent blocks, take the motion vector of the original current block as output, otherwise take the result of median filtering as output. The vector fields before and after median filtering are shown in Figure 7 and Figure 8.

Claims (8)

1, video motion estimation method, it is characterized in that the method comprises the following steps: (a) Based on the order of block matching search, a group of candidate vectors is determined according to the motion vectors of several blocks near the current block and an update mechanism; (b) For each of the candidate vectors, calculate the error between the current pixel block and its matching reference pixel block, and calculate the error between the current pixel block and the pixel block at the same position in the reference frame, and select the vector with the smallest error value above as the motion vector; (c) Median filtering the estimated motion vectors to smooth the vector field; The method of the step (a) is to firstly select the motion vectors of two processed blocks and the motion vector of an unprocessed block according to the order of block matching search, and a total of three vectors are used as initially determined candidate vectors, Then update the initially determined candidate vectors according to an update mechanism. 2. The video motion estimation method as claimed in claim 1, wherein the method for calculating the error in the step (b) is to expand the boundary between the pixel block of the current frame/field to be processed and the pixel block of the corresponding reference frame, and It is sub-sampled, and then the error between the current pixel block and its matching reference pixel block is calculated for the sub-sampled block pixels. 3. The video motion estimation method according to claim 1, characterized in that calculating the error in step (b) is directly calculating the error between the current pixel block and its matching reference pixel block. 4. The video motion estimation method according to claim 1, characterized in that step (c) is first to adopt 3*3 2-dimensional median filtering for the horizontal and vertical components of the block motion vector respectively, and then output according to the median filtering If the motion vector composed of the horizontal component and the vertical component output by the median filter is not any of the 8 current block adjacent block motion vectors participating in the median filter, the motion vector of the original current block is taken as the output, Otherwise, take the result of median filtering as output. 5. The video motion estimation method according to claim 1, characterized in that the order of block matching search can be from top to bottom and from left to right, from bottom to top and from left to right, from top to bottom and from right to Left, bottom to top, right to left; top to bottom, left to right and right to left, bottom to top, left to right and right to left; all around to the center. 6. The video motion estimation method according to claim 1, characterized in that said two processed blocks are horizontally adjacent and vertically adjacent blocks of the current block; said one unprocessed block is Blocks in the 45-degree diagonal direction of the current block. 7. The video motion estimation method as claimed in claim 1, characterized in that the update mechanism is firstly to alternate the motion vectors of the two blocks that have been processed according to the order of matching search among the initially determined candidate vectors. Select one of them in sequence; then, within a predetermined range of vector space, randomly select a vector and add this vector to the initially determined candidate vector selected for update to form an updated vector. The vector and the other two initially determined candidate vectors that have not been updated together form a set of candidate vectors. 8. The video motion estimation method according to claim 2 or 3, characterized in that the method of calculating the error value of the current pixel block and its matching reference pixel block is to first sum the corresponding number of pixels of the current pixel block, and then calculate the error value of the reference pixel block The corresponding number of pixels in the frame pixel block is summed, and then the absolute difference of the above two sums is calculated to obtain the motion estimation error.

Images