CN101170696B - A Motion Estimation Method - Google Patents

Abstract

The present invention relates to a motion estimation method in video processing, comprising: step 1, determining the size of continuous macroblocks according to the size of on-chip memory, and dividing all macroblocks in one frame into several continuous 16×16 macroblocks , all the macroblocks in each continuous macroblock are on the same line in a frame, and the required on-chip buffer is allocated; step 2, the current frame and the reference frame need to select the mode for the continuous macroblock Luminance and chrominance data are copied to the on-chip buffer; step 3 and step 5 are to accurately obtain the starting point of prediction; steps 6 to 10 are to find the best matching point after obtaining the best matching point through the discontinuous cross search method Match the block and end this motion estimation. This method makes full use of the fact that the distribution probability of the motion vector in the horizontal and vertical directions is much larger than that in other directions, and combined with the starting point prediction strategy, it improves the possibility of the initial search point being close to the best matching point and reduces the search amount.

Description

A Motion Estimation Method

technical field

The invention relates to a motion estimation method in the process of video processing, in particular to a motion estimation method which can improve the speed and precision of motion estimation.

Background technique

Since the video sequence contains a large amount of information, it would consume resources to store or transmit the information without processing it, so the compression of the video sequence has become a hot topic. Since there is time redundancy between adjacent frames of a continuous motion image sequence, motion estimation (Motion Estimation) can be used to compress the image data. Motion estimation is a very computationally expensive part of video compression, so many fast motion estimation methods in this area have been proposed.

There are many methods for motion estimation, and block matching is one of them. Block matching motion estimation (Block_matching, ME) is simple in theory and easy to implement. Now most image compression standards such as: ITU_TH.26L, MPEG_1\MPEG_2, etc. use the block matching method for motion estimation. The main idea of this method is to divide a frame of image into 16×16 macroblocks, further divide the macroblocks into smaller sub-blocks according to the situation, and then compare these blocks with the pixels in the search area in the reference frame , get the block most similar to the current block and make a difference with it, and encode the difference after further processing, so as to achieve the purpose of data compression.

The more classic methods in block matching motion estimation include global search method (FS), two-dimensional logarithmic search method, three-step search method, four-step search method, new three-step search method, cross search method and diamond search method. At the same time, there are many methods of combining several search models, such as: cross-diamond search method, cross-hexagon search method, etc. Among these search methods, FS is the most direct and clear and has the best effect. It compares all the pixels in the search window, and finally obtains the best reference block, but FS is too computationally intensive to be used in practice; , The three-step search method has a significant effect in reducing the amount of calculation, but the initial search step is too large, and it is easy to fall into a local minimum, resulting in poor matching accuracy; the diamond search method uses the center bias characteristic of the motion vector, while ensuring the image quality At the same time, it also significantly reduces the amount of calculation and improves the search speed, but this method still has shortcomings. Although this method considers the characteristics of the center distribution of the motion vector, it ignores another feature of the motion vector, that is: the motion vector is in The distribution probabilities of the horizontal and vertical directions are much larger than the rest of the directions.

Contents of the invention

In order to overcome the shortcomings of the low speed and precision of motion estimation in the prior art, the present invention provides a motion estimation method, which makes full use of the distribution characteristics of motion vectors whose distribution probability in the horizontal and vertical directions is much larger than that in other directions , combined with the starting point prediction strategy, will provide a new fast motion estimation method, which improves the possibility that the initial search point is close to the best matching point and reduces the search amount.

The technical scheme adopted in the present invention is: a kind of motion estimation method, it is characterized in that, this method comprises the step: step 1, when beginning, determine the size of continuous macroblock according to the size of on-chip memory (ISRAM), put in a frame All macroblocks are divided into several continuous 16×16 macroblocks, all macroblocks in each continuous macroblock are on the same line in a frame, and the required on-chip buffer is allocated; step 2, the current frame and In the reference frame, the brightness and chrominance data required for mode selection of continuous macroblocks are copied to the on-chip buffer; step 3, select the prediction block; step 4, calculate the prediction vector; step 5, predict the starting point; step 6. Start the discontinuous cross-shaped search with the predicted starting point as the center; Step 7, expand the discontinuous cross-shaped search method to calculate the pixel point SAD (Sum of Absolute Difference, SAD for short) value ; Step 8, find the point with the smallest SAD value as the best matching point; Step 9, find the best matching block according to the best matching point; Step 10, exit the search and end this motion estimation.

The beneficial effect of the present invention is: because all macroblocks in a frame are divided into several continuous macroblocks, all macroblocks in each continuous macroblock are all on the same line in a frame, and the required brightness of mode selection , The chromaticity data is copied to the on-chip buffer, which reduces data exchange, speeds up data access, and speeds up the calculation speed of video compression. Make full use of the distribution characteristics of the motion vector, use the discontinuous cross-shaped search, you can find the best matching point faster, and in the discontinuous cross-shaped search, the first step of the search can cover a larger area, which can better It has the advantages of avoiding the occurrence of local minimum in motion estimation.

Description of drawings

FIG. 1 shows a flowchart of a motion estimation method according to an embodiment of the present invention;

Figure 2 shows a block distribution diagram for prediction block selection;

Fig. 3 shows the result of the first step of the search template of the discontinuous cross search method;

Fig. 4 shows the result of the second step of the search template of the discontinuous cross search method;

Fig. 5 shows the result of the supplementary calculation of the first step of the search template of the discontinuous cross search method;

Fig. 6 shows the results of the second and third steps of the search template of the discontinuous cross search method.

Detailed ways

Below in conjunction with accompanying drawing and embodiment as example the present invention is further described:

In this embodiment, the TMS320DM64x series multimedia processing chip of Texas Instruments (TI) is selected as the hardware platform of this embodiment. The TMS320DM64x series of multimedia processing chips from Texas Instruments (TI) is suitable for digital media applications. The DM64x has a first-level cache (cache) and division configuration RAM/Cache on-chip, as well as 64 32-bit general-purpose registers. These storage spaces ensure large-scale Audio and video processing programs run efficiently and quickly. The first-level cache is divided into program cache and data cache, and the access speed is fast. The configurable RAM/Cache can be divided into on-chip memory (ISRAM) and secondary cache. The on-chip memory (ISRAM) can store programs and data, and the access speed is fast. The second level cache is also a high-speed cache that improves the access speed of programs and data. The EDMA controller used by DM64x has 64 independent DMA channels, and its transmission configuration information is stored in RAM, which can handle multiple DMA transmission tasks at the same time. DMA transmission only requires the minimal intervention of the DSP core, thus effectively improving the processing speed of the system. In this embodiment, the AVS standard is selected for motion estimation calculation.

The flow chart shown in Figure 1 provides the concrete process of the present embodiment:

Step 1. Initially determine the size of the macroblock that can put motion estimation-related data into the on-chip memory according to the size of the DSP's effective on-chip memory (ISRAM), and allocate the required on-chip buffer (ISRAM). The number of macroblocks is determined according to the size of the available on-chip memory and the value range of the motion vector:

Generally, assuming that the number of these macroblocks is L, the value range of the motion vector is -N~N, the size of the effective on-chip memory is M ₀ bytes, and the number of reference frames is 1 frame, then

$\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; [</span>\frac{{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 416</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 64</span>}\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; 8</span>}\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="N"\; filenames="S2007100506193E00021.png"\; state="\{\{state\}\}">N</figure-callout></span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; 928</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 64</span>}\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; ]</span>$

Determine the actual required on-chip buffer size M (bytes) according to the calculated size L of the macroblock,

M=2×(16×L+2N)×(16+2N)+(L+1)×16×26

Step 2, copy the luminance and chrominance data required for motion estimation of these macroblocks in the current frame and the reference frame to the on-chip buffer by means of DMA. These data include: luminance and chrominance data in these macroblocks of the current frame; luminance and chrominance data in corresponding positions in the reference frame.

Step 3: According to the principle of block selection in the present invention, select a prediction block.

Step 4: Calculate the prediction vector, according to the formula:

Pred_mv=w1*MVa+w2*MVb+w3*MVc+w4MVd+w5MVe, calculate Pred_mv.

Step 5: Predict the starting point.

Step 6: Start a discontinuous cross-shaped search with the predicted starting point as the center.

Step 7, expand the discontinuous cross-shaped search method, and calculate the SAD values of 9 pixels in the horizontal and vertical directions within the search area, as shown in Figure 3.

Step 8, calculate the SAD values of 9 pixel points according to step 7, find the point with the smallest SAD, divide the following three situations, and perform the following steps respectively:

Step 8.1, the search point is within the search area,

(a) If the point is the central point, then calculate the SAD values of the four points around the point, up, down, left and right, as shown in Figure 4, to find the point with the smallest SAD value;

(b) If the point is a point with a radius of 2 in the cross search model, with this point as the center, calculate the SAD values of the 8 pixels in the surrounding rectangular area, as shown in Figure 5, find the minimum SAD value point;

(c) If the point is a point with a radius of 4 in the cross search model, take this point as the center and expand a discontinuous cross search area, as shown in Figure 5. And use this point as the new initial search point, and skip to step 6 to continue execution.

Step 8.2, the search point is on the search boundary,

If any search point falls on the boundary of the search area, the point with the smallest SAD value in this search point is taken as the best matching point.

Step 8.3, the search point is beyond the search area,

When the search range exceeds the search area, take the minimum SAD value among the available points in the area of the search model, and record this point as the best matching point.

Step 9, find the best matching block according to the best matching point.

Step 10, exit the discontinuous cross-shaped search, and end this motion estimation.

The purpose of steps 3 to 5 is to accurately obtain the predicted starting point, and the specific principles are:

The position of the initial center point of the cross search model is predicted, so that the discontinuous cross center point search method is closer to the best matching point, and the search efficiency is further improved. Since the motion of objects in a video sequence is usually rigid body motion, several blocks belonging to an object usually have similar motion vectors. Therefore, the initial motion vector of the current block can be predicted by using the motion vectors of adjacent coded blocks in the time domain and the space domain, which is referred to as a prediction vector (Pred_mv) herein. In order to better predict the Pred_mv of the current block, we need to select the blocks participating in the prediction and define the rules for calculating Pred_mv.

For the block selection rules in this embodiment, the conventional method of predicting motion vectors is used for reference: select the left block, upper block, and upper right block in the space domain of the current block, select the block corresponding to the current block in the time domain, and then take the above several The median of the block's motion vectors. However, the conventional method has the following disadvantages: the processing process of the vector is fixed, and the motion trend of the object in the coded block cannot be well reflected, so that the accuracy of the predicted motion vector is not high.

Therefore, this embodiment mainly adopts the following starting point prediction method:

1) Block selection principle.

The blocks selected to participate in prediction are shown in Figure 2. Among them: A, B and C belong to the left, upper and upper right blocks in the space domain of the current block, D and E belong to the blocks in the time domain, and the position of the D block corresponds to the position of the current block, and the E block and the D block are adjacent. The block selection principle in this paper has one more E block than the previous strategy. The advantage of this is that it can make full use of the motion trend information of objects in adjacent blocks, making the prediction results more accurate.

2) Calculate the rules of Pred_mv.

The calculation rule of Pred_mv uses the method of weighted calculation, and the specific method is shown in formula 2:

Pred_mv＝w1*MVa+w2*MVb+w3*MVc+w4MVd+w5MVe

Wherein: wi is the weight value of each motion vector, and the distribution of the weight value is distributed according to the size ratio of the absolute values of the five motion vectors. MVa, MVb, and MVc are the motion vectors of blocks A, B, and C, respectively, and MVd and MVe are the motion vectors of blocks D and E, respectively. If a certain block is not available, the value of the motion vector of this block is set to zero.

After adopting the starting point prediction technology, the most obvious advantage is that the starting search point of motion estimation can be closer to the best matching point, and the search method only needs to perform fewer steps to find a suitable matching block, thereby reducing the amount of calculation and improving search speed.

The purpose of steps 6 to 8 is to obtain the best matching point through the discontinuous cross-shaped search method, and its specific principles are:

According to the distribution characteristics of motion vectors, this program proposes a discontinuous cross-shaped search method. This method makes full use of the distribution characteristics of motion vectors, and concentrates on searching the points in the central area, horizontal and vertical directions, so that suitable points can be found faster. This method calculates the SAD values of 9 pixels in the horizontal and vertical directions in the search area, and finds the point with the smallest SAD. As shown in Figure 3, the result of the first step of the search template of the discontinuous cross search method, then:

Step 8.1, the search point is within the search area, then includes one of the following steps:

(a) If the point is the center point, as shown in Figure 4, then calculate the SAD values of the upper, lower, left and right points around the point, find the point with the smallest SAD value, and end the search;

(b) If the point is a point with a radius of 2 in the cross search model, as shown in Figure 5, then take this point as the center, calculate the SAD value of the 8 pixel points in the surrounding rectangular area, and find the minimum SAD value point, end the search;

(c) If this point is a point with a radius of 4 in the cross search model, as shown in Figure 5, then take this point as the center, expand a discontinuous cross search area, and re-execute the discontinuous cross search method;

Step 8.2, if any search point falls on the boundary of the search area, take the point with the smallest SAD value among the search points this time as the best matching point, and end the search;

Step 8.3, if the search range exceeds the search area, take the point with the smallest SAD value among the available points in the search model area as the best matching point.

It can be seen that the discontinuous cross-shaped search method in this scheme gives priority to searching for the center point, horizontal and vertical pixel points in the search area, and makes good use of the center bias characteristics of the motion vector and the motion vector falling in the horizontal and vertical directions. The property that the probability of a direction is greater than the probability of falling in other directions. At the same time, considering the situation when the search point is on the search boundary and the search range exceeds the search area, the points missed in the first round of search are effectively supplemented, which increases the chance of finding the best point and ensures the search accuracy. The amount of calculation is reduced, and the speed of motion estimation is improved.

This embodiment illustrates the principle of the present invention with the motion estimation of AVS standard video data by the TMS320DM64x series multimedia processing chips of Texas Instruments (TI), and those of ordinary skill in the art will realize that any other video compression standards and any hardware The application of the platform to the technical solutions of the present invention, although not explicitly described and shown here, shall be included in the protection scope of the present invention. Furthermore, the examples and formulas and functions described herein are intended to assist the reader in understanding the principles of the invention and should be understood not to be limited to such specifically stated examples and conditions.

Claims (1)

1. A motion estimation method, carried out as follows: Step 1. At the beginning, the size of the continuous macroblocks is determined according to the size of the on-chip memory, and all the macroblocks in one frame are divided into several continuous 16×16 macroblocks, and all the macroblocks in each continuous macroblock are in one on the same line in the frame, and allocate the required on-chip buffer; Step 2, copy the luminance and chrominance data required for mode selection of continuous macroblocks in the current frame and the reference frame to the on-chip buffer; Step 3, select a prediction block, the prediction block includes the left, upper and upper right blocks (A, B, C) in the space domain of the current block and the block (D) corresponding to the position of the current block in the time domain and its neighbors block(E); Step 4, calculate the prediction vector, its calculation formula is: Pred_mv＝W1*MVa+W2*MVb+W3*MVc+W4MVd+W5MVe Where Pred_mv is the prediction vector, W1-W5 is the weight value of each motion vector, and the distribution of weight value is distributed according to the size ratio of the absolute value of the five motion vectors. MVa, MVb, and MVc are the motion vectors of the left, upper, and upper right blocks in the current block space, respectively, MVd and MVe are the motion vectors of the block corresponding to the position of the current block and its adjacent blocks in the time domain of the current block, and if a certain block is not available, the value of the motion vector of the block is set to zero; Step 5, predict the starting point; Step 6, centering on the predicted starting point, start a discontinuous cross-shaped search; Step 7, expand the discontinuous cross-shaped search method, and calculate the pixel absolute difference and SAD value of 9 pixels in the horizontal and vertical directions in the search area; Step 8, according to the pixel absolute difference and the SAD value of the 9 pixel points calculated in step 7, find the minimum point of the pixel absolute difference and the SAD value as the best matching point; Step 9, find the best matching block according to the best matching point; Step 10, exit the discontinuous cross-shaped search, and end this motion estimation; It is characterized by: According to the pixel absolute difference and SAD value of 9 pixel points calculated in step 7, the minimum point of pixel absolute difference and SAD value is obtained, and as step 8 of the best matching point, the following steps are respectively carried out in three situations : Execute the following step 8.1, for the first case where the search point is within the search area: (a) If the point is the center point, then calculate the pixel absolute difference and SAD value of the four points around the point, upper, lower, left and right, and find the minimum point of the pixel absolute difference and SAD value; (b) If the point is a point with a radius of 2 in the cross search model, take this point as the center, calculate the pixel absolute difference and SAD value of the 8 pixels in the surrounding rectangular area, and calculate the pixel absolute difference and SAD value the minimum point; (c) If the point is a point with a radius of 4 in the cross search model, use this point as the center to expand a discontinuous cross search area, and use this point as the new starting search point, then go to step 6 proceed sequentially; Execute the following step 8.2, for the second case where the search point is on the search boundary: If any search point falls on the boundary of the search area, take the point with the smallest pixel absolute difference and SAD value in this search point as the best matching point, and end the search; Execute the following step 8.3, for the third case where the search range exceeds the search area: When the search range exceeds the search area, take the minimum pixel absolute difference and SAD value among the available points in the search model area, and record this point as the best matching point.

Images