CN101795409B - content adaptive fractional pixel motion estimation method - Google Patents

Abstract

The invention belongs to the field of video coding in signal processing, and relates to a content adaptive fractional pixel motion estimation method. Including an invalid fractional pixel motion vector search and omission method based on flat area macroblock prediction: By detecting whether the motion vector of mode 1 in the 7 modes of H.264 motion estimation falls on an integer pixel, it is determined whether the current macroblock is a flat block. For flat blocks, subsequent modes only do regular integer-pixel motion vector searches. For non-flat blocks, regular integer and fractional pixel motion vector searches are performed. The improved enhanced diamond template search method based on the predicted vector uses an improved search template, stops the search within the [-2, 2] range of the predicted motion vector, and omits the calculation of a few pairs of codes outside the [-2, 2] range Fractional pixel sampling points with little efficiency improvement. The content-adaptive fractional pixel motion estimation method reduces the fractional pixel search points by an average of 75.6% compared with the fractional pixel full search method (FFPS) in the case of a slight decrease in the peak signal-to-noise ratio (PSNR) (0.095-0.209dB). The motion estimation module saves 38.5% computation on average. The adaptive fractional pixel motion estimation method of the present invention can reduce the calculation amount of fractional pixel motion estimation on the basis of ensuring the accuracy of motion estimation.

Description

Content Adaptive Fractional Pixel Motion Estimation Method

technical field

The invention belongs to the field of video coding in signal processing, and especially proposes a new content-adaptive fractional pixel motion estimation method for the latest international video coding standard H.264/AVC. On the basis of ensuring the accuracy of motion estimation, the calculation amount of fractional pixel motion estimation can be reduced.

Background technique

Ostermann，Jan Bormans，Peter List，Detlev Marpe，Matthias Narroschke，Fernando Pereira，Thomas Stockhammer，ThomasWedi.Video coding with H.264/AVC：tools，performance，and complexity[J].IEEE Circuits andSystems Magazine，2004，4(1)：7-28.)。H.264的高性能是以计算复杂度的提高为代价的，其计算复杂度大约是H.263的4至5倍，其中，运动估计模块的计算量占到整个编码器的50％-90％(参见Yu-Wen Huang，Ching-Yeh Chen，Chen-Han Tsai，Chun-Fu Shen，Liang-Gee Chen.Surveyon block matching motion estimation algorithms and architectures with new results[J].Journal ofVLSI Signal Processing Systems for Signal，Image，and Video Technology，2006，42(3)：297-320.)。H.264/AVC is the latest international video coding standard formulated by JVT (Joint Video Team), a joint video group jointly established by ITU-T and ISO/IEC. In the H.264 video coding system, motion estimation can effectively remove the time redundancy of adjacent frames in the video sequence, which largely determines the coding speed, compression rate and decoding video quality of the video encoder. Therefore, the H.264 motion estimation module adds a variety of coding techniques, such as 1/4 pixel prediction accuracy, multiple reference frames, and tree-structured motion compensation. The performance of H.264/AVC surpasses all previous video encoders. Under the premise of the same encoding quality, the bit rate generated by H.264/AVCBaseline Profile is about 40% lower than that of H.263Baseline (see

Ostermann, Jan Bormans, Peter List, Detlev Marpe, Matthias Narroschke, Fernando Pereira, Thomas Stockhammer, Thomas Wedi. Video coding with H.264/AVC: tools, performance, and complexity[J]. IEEE Circuits and Systems Magazine, 2004, 4( 1): 7-28.). The high performance of H.264 is at the cost of increased computational complexity, which is about 4 to 5 times that of H.263. Among them, the calculation of the motion estimation module accounts for 50%-90% of the entire encoder. % (see Yu-Wen Huang, Ching-Yeh Chen, Chen-Han Tsai, Chun-Fu Shen, Liang-Gee Chen. Survey on block matching motion estimation algorithms and architectures with new results[J]. Journal of VLSI Signal Processing Systems for Signal , Image, and Video Technology, 2006, 42(3): 297-320.).

In the H.264 encoder, motion estimation includes two parts: integer pixel motion estimation and fractional pixel motion estimation. Fractional pixel motion estimation is the process of interpolating on the basis of obtaining an integer pixel motion vector (MV: motion vector), and searching for a motion vector with fractional pixel precision. Fractional pixel motion estimation can greatly improve the performance of encoders in terms of compressed video quality and compression rate. Experimental results show that the average compression rate of the fractional pixel motion estimation method is 48% higher than that of the whole pixel motion estimation method, and at the same time, the peak signal-to-noise ratio (PSNR) is increased by 1-3dB. However, fractional pixel motion estimation greatly increases the computational load of the entire motion estimation module due to extra operations such as interpolation and fractional pixel search.

Integer pixel motion estimation method is a research hotspot in recent years. The H.264 standard JM reference software uses two fast integer pixel motion estimation methods UMHexagonS (see Zhibo Chen, Peng Zhou, Yun He, Yidong Chen. Fast integer pel and fractional pel motion estimation for JVT[C], JVT-F017, 2002.) and EPZS (cf. Alexis Michael Tourapis, Hye-Yeon Cheong, Pankaj Topiwala. Fast ME in the JM reference software [C], JVT-P026, 2005.), greatly reduces the number of search points compared to full search methods (the average number of search points for each motion vector is reduced to less than 10), and the computational complexity is reduced by more than 90%. H.264 uses tree structure motion compensation, and there are 7 modes of motion estimation. If the traditional full fractional pixel search method (full fractional pixel search) with 1/4 precision is used, each mode requires 16 search points, and each macro A block needs to search 112 points. Therefore, the improvement of fractional pixel precision motion estimation method becomes the key to the optimization of the whole motion estimation module.

At present, H.264/AVC adopts two fractional pixel motion estimation methods, fractional pixel full search method (FFPS: FullFractional Pixel Search) and center-based fractional pixel search method (CBFPS: Center Based Fractional PixelSearch). (See Zhibo Chen, Peng Zhou, Yun He, Yidong Chen. Fast integer pel and fractional pelmotion estimation for JVT[C], JVT-F017, 2002.)

The FFPS method is shown in Figure 1. FFPS performs a hierarchical search centered on the best integer pixel: first, calculate the 8 1/2 pixel positions around the best integer pixel position, and find the best 1/2 pixel matching point; then, calculate the best 1/2 pixel around The 8 1/4 pixel positions, find the best 1/4 pixel matching point, as the best motion vector of FFPS. FFPS needs to calculate 16 pixel positions.

The CBFPS method is shown in Figure 2. CBFPS adopts the search strategy of vector prediction and progressive refinement: firstly, the fractional pixel prediction motion vector (Pred_x, Pred_y) is obtained by calculating the median value of motion vectors of adjacent blocks, and the original search center (0, 0) and the prediction motion vector are compared The matching error of (Pred_x, Pred_y), where the search point that produces the smallest error is used as the starting point of the sub-pixel search; then, using a diamond template (see Jo Yew Tham, Surendra Ranganath, Maitreya Ranganath, Ashraf Ali Kassim. A novel unrestricted center- biased diamond search algorithm for block motionestimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1998, 8(4): 369-377.) Iterate to gradually refine and calculate the final fractional pixel matching points. Compared with FFPS, CBFPS can reduce the calculation amount by 20%, while the image quality is almost unchanged, which is a very effective fast fractional pixel search method.

Inter prediction in the H.264/AVC standard provides greater flexibility than previous coding standards. Using tree structure motion compensation, each macro block can be divided into 16×16, 8×16, 16×8, 8×8 blocks; when using 8×8 blocks, it can be further divided into 8 smaller blocks ×4, 4×8, and 4×4 sub-blocks, as shown in Figure 3.

When performing motion estimation, the encoder needs to use the SKIP mode for the entire prediction mode set {SKIP (to use the SKIP mode to effectively encode large-area static areas and consistent motion areas. The SKIP mode is also a motion compensation prediction mode with a block size of 16×16, only No need to encode any motion and prediction residual information), 16×16, 8×16, 16×8, 8×8, 8×4, 4×8, 4×4} motion estimation in each partition mode separately , to get their respective motion vectors. The encoder comprehensively considers the number of bits required to encode the residual value and the number of bits required to encode the motion vector, and then selects the best prediction mode. The method for H.264/AVC to select the optimal mode is called Rate Distortion Optimization (RDO). The RDO-based mode selection method encodes macroblocks in each candidate mode and compares the resulting rate-distortion costs, and selects the mode with the smallest rate-distortion cost as the best encoding mode.

The rate-distortion cost function is defined as follows:

J(s,c,MODE|QP, _λMODE )=SSD(s,c,MODE|QP)+ _λMODE ·R(s,c,MODE|QP)(1)

Wherein, Qp is a quantization parameter (Quantization Parameter), MODE is a candidate macroblock coding mode, and for I frame and P frame, the Lagrangian factor λ _MODE =0.85×2 ^QP/3 . SSD is the sum of the mean square errors of the original signal s and the reconstructed signal c, as a distortion measure. R is the quantization parameter QP and the number of bits required to encode this macroblock under the mode MODE (including macroblock header information, motion vectors, coefficients after residual transformation and quantization, etc.).

Figure 4 shows the calculation process of the rate-distortion cost in a certain candidate mode. It can be seen that in order to calculate the rate-distortion cost corresponding to the candidate mode, the processes of motion estimation/compensation, transformation, quantization and entropy coding are required to obtain the encoding requirements in this mode. Inverse quantization/inverse transformation is also required to obtain the reconstructed signal, and the whole process has a high computational complexity. It can be seen from the formula (1) that the rate-distortion cost is a compromise between the distortion and the required number of bits, and the weight of the number of bits is the Lagrangian factor, whose value is a monotone function of the quantization parameter.

Contents of the invention

The purpose of the present invention is to overcome the disadvantages of the prior art, and propose a content-adaptive fractional pixel motion estimation method. On the basis of ensuring the accuracy of motion estimation, the calculation amount of fractional pixel motion estimation can be reduced. This method is applicable to the H.264 international standard, but not limited to H.264, and can be extended to other video compression international standards and non-international standard applications.

The invention proposes a content-adaptive fractional pixel motion estimation method. It is characterized in that it adopts an invalid fractional pixel motion vector search omission method based on flat area macroblock prediction and an improved enhanced diamond template search method based on prediction vector.

The method of searching and omitting invalid fractional pixel motion vectors based on flat area macroblock prediction is as follows:

By detecting whether the motion vector of mode 1 in the 7 modes of H.264 motion estimation falls on an integer pixel, it is determined whether the current macroblock is a flat block. For flat blocks, subsequent modes only perform regular integer-pixel motion vector searches, not fractional-pixel motion vector searches. For the non-flat block, the conventional integral pixel and fractional pixel motion vector searches are performed, and the following improved prediction vector-based enhanced diamond template search method is used for the fractional pixel motion vector search.

The improved enhanced diamond template search method based on prediction vector is as follows:

Step 1: Predict the fractional pixel motion vector of the current block from adjacent blocks to obtain FMVP, ie (Pred_x, Pred_y). Directly use FMVP as the starting point of the search.

Step 2: Compare the matching errors of the 4 diamond-shaped search points around the search start point (Pred_x, Pred_y) and (Pred_x, Pred_y), if the minimum sum of absolute errors MSAD is located at (Pred_x, Pred_y), stop the fractional pixel motion vector Search, otherwise go to the third step to search.

Step 3: If the best matching point is opposite to the sub-best matching point, select the best matching point MV as the final fractional pixel motion vector; if the best matching point is adjacent to the sub-best matching point, calculate its neighbor The matching error of the point on the square template, if MSAD is still the best matching point of rhombus, then choose the best matching point of rhombus MV as the final fractional pixel motion vector, otherwise proceed to the next step.

Step 4: Take the search point on the square template in the third step as the center, and use the rhombus template to search for points around it. Select the MASD point as the final fractional pixel motion vector.

Compared with the prior art, the present invention has the advantages that: the method for searching and omitting invalid fractional pixel motion vectors based on flat region macroblock prediction fully utilizes the correlation of motion estimation modes. From the motion vector of mode 1, the flat block SMB is predicted. For SMB, the remaining 6 matching modes only perform integer pixel search and skip sub-pixel search. Experiments show that this method can reduce the calculation amount of fractional pixel motion vector search by 28.70%-56.00% under the premise of ensuring the quality of the decoded image. The method is self-contained and combined with the enhanced diamond template search method based on predictive vectors proposed in this paper, it can further reduce the computational load of fractional pixel motion estimation. Compared with the optimal method FFPS, the content-adaptive fractional pixel motion estimation method saves 38.5% of calculation time on average, and the PSNR loss does not exceed 0.209dB. Especially, for video sequences with slow motion, it can save 46% computation time and maintain comparable or even better PSNR.

Description of drawings

Figure 1 is a schematic diagram of Fractional Full Pixel Search (FFPS).

Fig. 2 is a schematic diagram of center-based fast fractional pixel search (CBFPS).

Fig. 3 is a schematic diagram of H.264 variable macroblock size.

Fig. 4 is a calculation process of the rate-distortion cost in a certain candidate mode.

Figure 5 shows the spatial relationship among the seven modes.

Figure 6 shows common search templates: (a) is a rhombus template; (b) is a square template; (c) is a hexagonal template.

Fig. 7 is a schematic diagram of enhanced diamond template search based on predictive vectors.

FIG. 8 is a flow chart of a method for searching and omitting invalid fractional pixel motion vectors based on flat area macroblock prediction.

Detailed ways

The content-adaptive fractional pixel motion estimation method proposed by the present invention is described in detail as follows in conjunction with the accompanying drawings and specific implementation methods:

The content adaptive fractional pixel motion estimation method proposed by the present invention includes: an invalid fractional pixel motion vector search omission method based on flat area macroblock prediction and an improved enhanced diamond template search method based on predictive vectors. The following are introduced respectively:

A method for searching and omitting invalid fractional pixel motion vectors based on flat area macroblock prediction, comprising the following steps:

Fractional pixel motion estimation can improve compressed video quality and compression rate, however, fractional pixel motion vector search requires a huge amount of computation. If the minimum absolute error sum (MSAD: minimum sum of absolute difference) obtained by the fractional motion vector search is greater than the MSAD obtained by the integer pixel motion vector search, the integer pixel MV is selected as the final MV, and the fractional pixel motion vector search is considered invalid. On the contrary, the fractional pixel motion vector search is effective, and the fractional pixel MV is selected as the final MV. Experiment on the first 20 frames of 7 standard video sequences (among which, News, Container, Silent belong to the test sequence with low spatial detail and slow motion; Paris, Foreman are the test sequence with medium spatial detail and moderate motion intensity; Football is high spatial detail Details and intense motion test sequence), the proportion of the final MV is an integer pixel MV is listed in Table 1.

Table 1 Proportion of integer pixel MV (10 frames, QP=28)

For sequences with gentle motion in video content, such as News, Container, and Silent, more than 80% of the motion vectors are located at integer pixel positions. In fact, for the flat area of the video frame, the fractional pixel search does not improve the coding performance significantly, which is an invalid search. If these flat region blocks can be predicted, unnecessary computation can be reduced by skipping ineffective fractional pixel searches.

Therefore, how to make the encoder adaptively decide whether to perform fractional pixel search according to the video content, that is, how to predict the flat area block of the video frame before fractional pixel motion estimation, is the key to omit the invalid fractional pixel motion estimation vector search .

There is a strong correlation between the seven motion estimation modes of H.264 (the spatial relationship between the seven modes is shown in Figure 5). The flatness of the current macroblock can be predicted using the result of the motion vector search in the upper layer mode. Therefore, if the upper layer mode 1 (16×16) motion vector is at an integer pixel position, such a macroblock is defined as a flat block, referred to as SMB (smoothmacro-block). For SMB, the motion vector search of the lower layer mode can skip the fractional pixel motion vector search.

The search and omission method of invalid fractional pixel motion vectors based on flat region macroblock prediction proposed by the present invention is referred to as SMBP (smooth macro-block prediction). Whether the current macroblock is a flat block is determined by detecting whether the mode 1 motion vector falls on an integer pixel. For flat blocks, subsequent modes only perform regular integer-pixel motion vector searches, not fractional-pixel motion vector searches. For non-flat blocks, regular integer and fractional pixel motion vector searches are performed. The flowchart is shown in Figure 8.

The flat block prediction accuracy rate refers to the ratio of the lower layer mode determined as SMB to perform conventional fractional pixel motion vector search, and its final motion vector falls in the integer pixel position. The accuracy rate is defined as formula (2). See Table 2 for the statistical results of flat block prediction accuracy and the proportion of integer pixel MVs.

The higher the prediction accuracy, the smaller the matching error, and therefore the smaller the degradation of the decoded image quality and the smaller the bit rate change. It can be seen from Table 2 that for video sequences with slow motion, the accuracy rate of flat block prediction is above 91%, and the method of the present invention can make relatively accurate prediction for such sequences. The reduction ratio of fractional pixel MV is from 28.70% to 56.00%, that is, the method of the present invention can reduce the calculation amount of fractional pixel motion vector search by 28.70% to 56.00%.

Table 2 Flat block prediction accuracy (10 frames, QP=28)

An improved enhanced diamond template search method based on predicted vectors, comprising the following steps:

Fractional pixels are obtained by integer pixel interpolation, and the correlation of search points within the fractional pixel search window is much higher than that of integer pixel search points. When the search point is close to the global minimum, the matching error decreases monotonically. Therefore, many fast fractional pixel motion vector search methods adopt the predicted motion vector (FMVP: fractional predicted mv) as the starting point of search. If the initial point of fractional pixel motion vector search can be accurately predicted, the best MV near FMVP can be searched earlier, and the fractional pixel motion estimation search can be stopped in time.

The FMVP of the current block is determined by the median value of the fractional pixel motion vectors of adjacent blocks (top, left, and top right blocks). FMVP contains two parts of information: integer pixel prediction vector and fractional pixel prediction vector. Use the formula (3) to extract the fractional pixel prediction vector, where mv is the integer pixel motion vector that has been searched, in units of fractional pixels. % is a modulo operation, when β=4, the search precision is 1/4 pixel, and when β=8, the search precision is 1/8 pixel.

frac_pred_mv=(pred_mv-mv)%β(3)

Table 3 shows how well FMVP matches the best fractional pixel MV obtained by FFPS. A match indicates that the FMVP is equal to the best MV; [-1, 1] indicates that the distance between the FMVP and the best MV is within 1 fractional pixel unit.

It can be found from Table 3 that the matching probability of the FMVP of the slow-moving test sequence and the best MV is greater than 82%. The matching probability of the test sequence with medium and high exercise intensity is low, but the probability of its FMVP in the [-2, 2] range of the best MV is above 90%. Therefore, FMVP can be used as a starting point for the fractional pixel motion vector search.

Table 3 Matching degree of FMVP and best score pixel MV

There are three commonly used templates for motion vector search: diamond template, square template and hexagon template. Among them, the diamond-shaped template is the simplest and is adopted by many video encoders, as shown in Figure 6(a); the square template adds 4 points on the diagonal to the diamond-shaped template, which increases the computational complexity and accuracy of search results, as shown in Figure 6(a). 6(b); the hexagon is suitable for occasions where the search range is large. Since the search range of the fractional pixel motion vector is limited to between two integer pixels, the hexagonal template is not suitable for fractional pixel motion vector search, as shown in Figure 6(c ).

The invention proposes an enhanced rhombus template search method based on predictive vectors. Different from CBFPS, since FMVP and the best MV have a higher matching rate, this method does not consider the original search center (0, 0), but directly uses FMVP as the starting point of search; uses enhanced diamond template (EDSP: extended diamond search pattern), combined with the advantages of high accuracy of the square template, increase the search points on the diagonal line on the basis of the diamond template; do not iterate the diamond template, but stop the search at [-2, 2] of FMVP Within the range of [-2, 2], a few fractional pixel motion vector searches outside the range of [-2, 2] that do not greatly improve the coding efficiency are omitted to reduce the number of search points and further reduce the amount of calculation.

Fig. 7 is a schematic diagram of an enhanced diamond template search strategy based on a predictive vector, and the method flow is as follows.

Step 1: Predict the fractional pixel motion vector of the current block from adjacent blocks to obtain FMVP, ie (Pred_x, Pred_y). Directly use FMVP as the starting point of the search.

Step 2: Compare the matching errors of the 4 diamond-shaped search points around the search start point (Pred_x, Pred_y) and (Pred_x, Pred_y), if the minimum sum of absolute errors MSAD is located at (Pred_x, Pred_y), stop the fractional pixel motion vector Search, otherwise go to the third step to search.

The third step: as shown in Figure 7(a), if the best matching point is opposite to the second best matching point, then select the best matching point MV as the final fractional pixel motion vector; as shown in Figure 7(b), if the best matching point Adjacent to the sub-best matching point, calculate the matching error of the point on the adjacent square template, if MSAD is still the best matching point of the rhombus, then select the best matching point MV of the rhombus as the final fractional pixel motion vector, otherwise proceed Next step.

Step 4: Take the search point on the square template in the third step as the center, and use the rhombus template to search for points around it. Select the MASD point as the final fractional pixel motion vector.

The content adaptive fractional pixel motion estimation method proposed by the present invention is tested on the H.264 test platform JM15.0. Six video sequences with representative motion intensity ranging from slow to vigorous were selected for testing. The parameter settings related to motion estimation of JM15.0 encoder are shown in Table 4.

Table 4 Encoder-related parameter settings

EDSP, SMBP+EDSP were compared with FFPS and CBFPS adopted by JM15.0 in terms of method performance: (1) Number of search points (fractional pixels): the number of search points required for each macroblock to obtain the final fractional pixel motion vector, reflecting The matching speed of the method; (2) the change of the peak signal-to-noise ratio (ΔPSNR: Peak Signal Noise Radio): measure the difference between the motion estimation and compensation image and the original image, reflecting the prediction quality of the method; (3) Δ calculation time ( Calculation time saved by motion estimation, including integer pixels and fractional pixels): It reflects the time spent by the encoder on the motion estimation module as a whole. These three experimental parameters are compared with FFPS as the standard.

Table 5 Performance comparison of each method

It can be seen from Table 5 that the EDSP method proposed in this paper has an average of 3.9 search points per macroblock, saving 75.6% compared with FFPS; PSNR loss of EDSP method is no more than 0.13dB compared with FFPS. Combining SMBP with EDSP can further reduce the amount of computation and save computation time. Compared with EDSP, SMBP+EDSP saves an average of 16% computing time for video sequences with gentle motion, such as News, Container, and Silent; and saves an average of 10% computing time for video sequences with moderate motion intensity, such as Paris and Forman; Video sequences with intense motion, such as football, save 7% of computing time. Compared with the optimal method FFPS, SMBP+EDSP saves an average of 38.5% of the calculation time, and the PSNR loss does not exceed 0.209dB; compared with CBFPS, SMBP+EDSP saves an average of 14.7% of the calculation time, and the PSNR loss does not exceed 0.196dB.

Claims (1)

1. invalid fraction pixel motion-vector search omission method that is used for the employing of content adaptive fractional pixel motion estimation method based on the flat site macroblock prediction, whether drop on whole pixel by the motion vector that detects the pattern 1 in 7 kinds of patterns of estimation H.264, judge whether current macro is flat block; For flat block, follow-up mode is only carried out the whole pixel motion vector search of routine, and does not carry out the fraction pixel motion-vector search; For the non-flat forms piece, carry out whole pixel of routine and fraction pixel motion-vector search, it is characterized in that:

At fraction pixel motion-vector search wherein, adopt improved enhancement mode rhombus template searching method based on predictive vector, carry out following four steps:

The first step: the fraction pixel motion vector by adjacent block prediction current block, obtain motion vectors FMVP, promptly (Pred_x, Pred_y); Directly with FMVP as the search starting point;

Second step: comparison search starting point (Pred_x, Pred_y) point of the search of 4 on the rhombus template on every side and (Pred_x, Pred_y) matching error, if least absolute error sum MSAD is positioned at (Pred_x, Pred_y), then stop invalid fraction pixel motion-vector search omission method, otherwise carry out the search of the 3rd step;

The 3rd step: if optimal match point is relative with the suboptimum match point, then selecting optimal match point MV is final fraction pixel motion vector; If optimal match point is adjacent with the suboptimum match point, then calculate the matching error of putting on the square template adjacent with optimal match point, if MSAD still is the rhombus optimal match point, then selecting rhombus optimal match point MV is final fraction pixel motion vector, otherwise carries out next step;

The 4th step: with the search point on the square template in the 3rd step is the center, searches for its point on every side with the rhombus template; The point of selecting MSAD is as final fraction pixel motion vector.

Images