CN106454349B - A Motion Estimation Block Matching Method Based on H.265 Video Coding - Google Patents

Abstract

A kind of estimation block matching method based on H.265 Video coding, the present invention relates to estimation block matching methods.The purpose of the invention is to reduce the computation complexity of the estimation in H.265 video standard cataloged procedure and reduce the scramble time.A kind of estimation block matching method detailed process based on H.265 Video coding are as follows: Step 1: the primary election stage: according to the division feature of inter prediction unit, select corresponding down-sampling scheme, according to the threshold value of setting, candidate matches group is selected from all match blocks；Step 2: the selected stage: carrying out selecting final match block based on the selected of rate-distortion optimization criterion to the candidate matches group that the primary election stage obtains, complete the process of the Block- matching in estimation.The present invention is used for the estimation Block- matching field of Video coding.

Description

A Motion Estimation Block Matching Method Based on H.265 Video Coding

technical field

The present invention relates to a motion estimation block matching method.

Background technique

In recent years, with the popularization of smart mobile terminals, video applications have become more and more diverse, and the amount of video data has grown at an alarming rate. The amount of high-definition image data is huge. In order to meet the needs of new video applications, ITU-T cooperated with ISO/IEC and released a new generation of high-efficiency video coding standard H.265 in 2013. H.265 adopts the traditional hybrid video coding framework, and makes technical innovations in each module of the framework, including support for more intra-frame and inter-frame prediction modes, combination of transform and quantization, sample adaptive compensation, CABAC entropy coding, etc. . These new technologies enable H.265 to save about 50% of the code rate compared to H.264/AVC under the same encoding quality. While improving the compression rate, H.265 brings great computational complexity and increases decoding and encoding time, which has become a bottleneck restricting the wide application of H.265.

Motion estimation is one of the core technologies in video compression coding. The use of motion estimation and motion compensation techniques can eliminate the temporal redundancy of video signals, thereby improving coding efficiency. However, motion estimation is also one of the most complex and time-consuming parts of the H.265 video coding standard.

SUMMARY OF THE INVENTION

The purpose of the present invention is to propose a motion estimation block matching method based on H.265 video coding in order to reduce the computational complexity and coding time of motion estimation in the H.265 video standard coding process.

The specific process of a motion estimation block matching method based on H.265 video coding is as follows:

Step 1, the primary selection stage: according to the division characteristics of the inter-frame prediction unit, select the corresponding downsampling scheme, and select the candidate matching group from all the matching blocks according to the set threshold;

Step 2: Selection stage: select the candidate matching groups obtained in the primary selection stage based on rate-distortion optimization criteria, select the final matching block, and complete the process of block matching in motion estimation.

The beneficial effects of the present invention are:

The invention provides an algorithm design structure for fast block matching of motion estimation in H.265. According to the basic principle of motion estimation, an optimized acceleration algorithm is proposed in the block matching process. The design of the algorithm aims to accelerate the motion estimation operation while taking into account the code rate, reduce the computational complexity of block matching, and thus improve the coding speed. After researching and analyzing the motion estimation and block matching algorithms, the feasibility and practicability of the algorithm are demonstrated, and an optimization algorithm for the step-by-step selection mode is proposed. The matching blocks are searched through the two steps of primary selection and selection, and the matching pixels are reduced. points, so as to achieve the purpose of speeding up the encoding speed.

In the test sequence, the encoding time is shortened by 10.70% to 17.94%, the bit rate is increased by 0.26% to 2.67%, and the PSNR does not drop by more than 0.1.

The motion estimation of H.265 inter-frame prediction is performed by prediction units, and different prediction units have different characteristics. The whole process needs to traverse too many prediction units and pixels, resulting in a long running time, which is quite unfavorable for the fast encoding and decoding requirements of high-definition video, so an optimization scheme is adopted to speed up the operation of motion estimation. When performing block matching, the matching process is divided into two steps. In the primary selection stage, different downsampling modes are selected from the algorithm according to the division size and shape of the prediction unit, fully considering the characteristics of block division in H.265. Calculate the difference between the pixel points on the down-sampling template of the current frame and the reference frame to take an absolute value, and accumulate the calculated absolute value to obtain an error value of a prediction block. Set the adaptive threshold and compare the error value with the adaptive threshold. If the error value is less than the threshold, it is marked as a candidate matching block, otherwise it is marked as a non-candidate matching block. The primary selection process effectively avoids computing all the pixels in the prediction unit.

In the selection stage, a matching group with a high matching possibility is obtained through the primary selection, and the candidate blocks in the matching group are selected based on the rate-distortion optimization criterion, and the final matching block is selected. The process needs to calculate all the pixels in the prediction unit, which ensures the prediction accuracy of motion estimation. The matching block search method, which combines primary selection and selection, reduces a large amount of calculation of block matching in the primary selection stage, and improves the calculation speed of block matching in motion estimation. At the same time, the selection stage ensures the matching accuracy of the predicted blocks and avoids falling into the local optimum.

1. It can effectively reduce the operation time of motion estimation in the encoding process, thereby reducing the encoding time;

2. The algorithm used does not contain complex and special operations, which is conducive to hardware implementation;

3. For video conferencing and other types of videos, the algorithm has little effect on image quality and transmission bit rate.

Description of drawings

FIG. 1 is a schematic diagram of H.265 motion estimation block matching primary selection;

Fig. 2a is the M×M partition pattern diagram of the H.265 inter-frame prediction unit;

Figure 2b is an M/2×M partition mode diagram of an H.265 inter-frame prediction unit;

Figure 2c is an M×M/2 division pattern diagram of an H.265 inter-frame prediction unit;

FIG. 2d is an M/2×M/2 partition mode diagram of an H.265 inter-frame prediction unit;

Fig. 2e is the M/4×M(L) division mode diagram of the H.265 inter-frame prediction unit, and L is the left;

Figure 2f is the M/4×M(R) division pattern diagram of the H.265 inter-frame prediction unit, where R is the right;

Figure 2g is an M×M/4(U) division pattern diagram of an H.265 inter-frame prediction unit, where U is the top;

Figure 2h is the M×M/4(D) division pattern diagram of the H.265 inter-frame prediction unit, and D is the bottom;

Fig. 3 is the down-sampling template diagram of square prediction block;

Fig. 4 is a down-sampling template diagram of a rectangular prediction block;

Figure 5 is a downsampling template diagram of 32x32 and 64x64 blocks;

Fig. 6 is a flow chart of downsampling template selection;

7 is a schematic diagram of a block matching adaptive algorithm;

Figure 8 is a flowchart of an early cutoff algorithm;

FIG. 9 is a flowchart of the motion estimation block matching module.

Detailed ways

Embodiment 1: This embodiment is described with reference to FIG. 9 . The specific process of a motion estimation block matching method based on H.265 video coding in this embodiment is as follows:

As shown in Figure 1, it is a schematic diagram of the primary selection.

Step 1, the primary selection stage: according to the division characteristics of the inter-frame prediction unit, select the corresponding downsampling scheme, and select the candidate matching group from all matching blocks according to the set adaptive threshold;

Step 2: Selection stage: select the candidate matching groups obtained in the primary selection stage based on rate-distortion optimization criteria, select the final matching block, and complete the process of block matching in motion estimation.

In the first step, the number of matching pixels can be effectively reduced through the primary selection, and the appropriate matching blocks can be selected. The second step of selection can accurately obtain the optimal block that matches, and ensure the coding efficiency as much as possible.

Embodiment 2: The difference between this embodiment and Embodiment 1 is that: in the first step of the preliminary selection stage: according to the division characteristics of the inter-frame prediction unit, the corresponding downsampling scheme is selected, and according to the set threshold, all A candidate matching group is selected from the matching block; the specific process is:

Step 11. The division mode of the inter-frame prediction unit is shown in Figures 2a, 2b, 2c, 2d, 2e, 2f, 2g, and 2h. There are eight kinds of prediction unit divisions in the coding standard, and the shapes are divided into squares and rectangles;

The downsampling templates of prediction blocks with different shapes are shown in Figure 3 and Figure 4. For a square prediction unit, it is determined whether the square is a 32x32 or 64x64 prediction unit, and the downsampling is shown in Figure 5. Sampling scheme; if not, adopt diagonal downsampling scheme;

For rectangular prediction units, a cross-shaped downsampling scheme is used;

Steps 1 and 2: The selection process of the down-sampling template is shown in FIG. 6 , and an appropriate template is selected therefrom. Calculate the absolute value SAD_c of the single pixel difference between the previous frame (time t) and the current frame (time t+1) in the prediction unit;

Accumulate each SAD_c obtained and compare it with Pixel_th; if it is less than or equal to Pixel_th, it indicates that the prediction unit is a matching candidate block, go to Steps 1 and 3, and wait for the selection calculation; if it is greater than Pixel_th, it means that the prediction unit is non-matching Candidate blocks, do not need to be calculated again;

Pixel_th is the adaptive downsampling threshold;

Step 1 and 3: Determine whether the matching candidate block is beyond the search range. If it is beyond the search range, go to Step 2;

Embodiment 3: This embodiment is different from Embodiment 1 or 2 in that: in the step 1 and 2, the selection process of the down-sampling template is shown in FIG. 5 , and an appropriate template is selected therefrom. Calculate the absolute value of the single pixel difference between the previous frame (time t) and the current frame (time t+1) in the prediction unit, and the specific process is to use the following formula:

SAD_c=abs(piOrg[i]-piCur[i])

Among them, piOrg represents the pixel in the current frame, piCur represents the pixel in the previous frame, abs is the absolute value symbol, and SAD_c is the single pixel difference between the previous frame (time t) and the current frame (time t+1) in the prediction unit The absolute value of the value, i is the ith pixel in the prediction unit.

Embodiment 4: The difference between this embodiment and one of Embodiments 1 to 3 is that the specific solution process of the adaptive downsampling threshold Pixel_th in the steps 1 and 2 is as follows:

The image is divided in the form of a coding tree unit (CTU) to obtain a CTU block, and the CTU block is divided again to obtain a prediction unit, and several prediction units share a same threshold;

The current adaptive downsampling threshold is estimated by accumulating and averaging the errors calculated by each prediction unit in the previous CTU. As shown in Figure 7.

In order to adapt to different application scenarios and obtain the best optimization effect, the adaptive downsampling threshold is selected in an adaptive manner; the present invention adopts the adaptive threshold based on the coding tree, as shown in Fig. 7 is a schematic diagram of the realization of the adaptive algorithm , where the letter T represents the T-th CTU block, T+1 represents the CTU adjacent to the T-th block, and the letters a, b, c, and d represent each PU block divided in the CTU.

Embodiment 5: The difference between this embodiment and one of Embodiments 1 to 4 is that the specific process of accumulating each SAD_c obtained in the steps 1 and 2 is as follows:

Among them, f _i (m _u , n _u ) is the pixel value of the coordinates (m _u , n _u ) in the image, the horizontal and vertical coordinates (m _u , n _u ) are the pixels on the downsampling template, the horizontal and vertical coordinates (x , y) represents the motion vector, and the prediction unit whose SAD(x, y) is less than or equal to the adaptive downsampling threshold is used as a matching candidate group; the prediction unit whose SAD(x,y) is greater than the adaptive downsampling threshold is used as a non-matching candidate group ;

M is the length of the prediction block, which is any one of 4, 8, 16, 32, and 64, and M≤4N; N is the height of the prediction block, which is 4, 8, 16, 32, and 64. Any one of them, N≤4M.

Embodiment 6: This embodiment is different from one of Embodiments 1 to 5 in that: the specific solution process of the search range in the steps 1 and 3 is:

A prediction point is obtained from the previous frame, and a rectangular search range is obtained with the prediction point as the center; an early cutoff algorithm is used to process the rectangular search range to obtain the search range.

This paper also adopts the early cutoff algorithm. Define the parameter CountNum in the structure rcStrcut in the official test code HM to record the number of times of selection. The xTZ8PointDiamondSearch function is the main function for TZSearch search. It is called cyclically in the loop body, and the number of loops is related to the search range. Define the parameter Count_th. If CountNum is greater than or equal to Count_th, it will jump out of the loop and no longer search for block matching. The flowchart of the early deadline algorithm is shown in Figure 8.

Embodiment 7: The difference between this embodiment and one of Embodiments 1 to 6 is that the search range is set in the configuration file of the program, and the value of the search range is 64×64.

Embodiment 8: The difference between this embodiment and one of Embodiments 1 to 7 is that: in the selection stage in the second step, the matching group obtained in the primary selection stage is selected based on the rate-distortion optimization criterion, and the final selection is performed. The matching block of , completes the process of block matching in motion estimation; the specific process is:

The prediction unit in the matching candidate block is selected based on the rate-distortion optimization criterion, which draws on the algorithm in the H.265 protocol. The calculation formula is as follows:

J=S(x,y)+λmotion*Rmotion

In the formula, (m, n) are all the pixels in the prediction unit, Rmotion represents the number of bits required for the prediction unit to encode motion information (such as MV, reference image label), etc., and λmotion is the Lagrangian in the motion estimation process. factor, the encoder will choose the value that minimizes the rate-distortion cost J as the final matching block for the current block.

The MV here represents the motion vector Motion Vector.

Adopt the following examples to verify the beneficial effects of the present invention:

Example 1:

Table 1 Comparison of coding performance between fast block matching algorithm and TZSearch algorithm

Specifically, it is prepared according to the following steps:

In the experiment, the server of Harbin Institute of Technology Microelectronics Center is used, and its hardware configuration is Inter XeonE54302.66GHz, memory 4G, RedHat4Linux 32-bit operating system. Use the script to run the 22 video sequences in sequence, and the qp value in the configuration file is 32. The program running time and coding performance are recorded and compared with existing TZSearch optimization algorithms.

Embodiment 2:

Table 2 Test data under different qp

Specifically, it is prepared according to the following steps:

The hardware configuration is the same as that of the first embodiment; the quantization parameter qp values are respectively taken as 22, 27, 32 and 37, and the rest of the parameter configurations remain unchanged; the encoding performance and running speed under different qp are tested, and the optimization algorithm is carried out with the existing TZSearch. Compare.

The present invention can also have other various embodiments. Without departing from the spirit and essence of the present invention, those skilled in the art can make various corresponding changes and deformations according to the present invention, but these corresponding changes and deformations are all It should belong to the protection scope of the appended claims of the present invention.

Claims (2)

1. a motion estimation block matching method based on H.265 video coding, is characterized in that: a kind of specific process of the motion estimation block matching method based on H.265 video coding is: Step 1, the primary selection stage: according to the division characteristics of the inter-frame prediction unit, select the corresponding downsampling scheme, and select the candidate matching group from all the matching blocks according to the set threshold; Step 2: Selection stage: select the candidate matching groups obtained in the primary selection stage based on rate-distortion optimization criteria, select the final matching block, and complete the process of block matching in motion estimation; The primary selection stage in the first step: according to the division characteristics of the inter-frame prediction unit, select the corresponding downsampling scheme, and select the candidate matching group from all the matching blocks according to the set threshold; the specific process is: Step 11, the division mode of the inter-frame prediction unit PU, there are eight prediction unit divisions in the coding standard, and the shape is divided into square and rectangle; For a square prediction unit, determine whether the square is a 32x32 and 64x64 prediction unit, if so, adopt the downsampling scheme of the glyph; if not, adopt the downsampling scheme of the diagonal; For rectangular prediction units, a cross-shaped downsampling scheme is used; Step 12: Calculate the absolute value SAD_c of the single pixel difference between the previous frame and the current frame in the prediction unit; Accumulate each SAD_c obtained and compare it with Pixel_th; if it is less than or equal to Pixel_th, it indicates that the prediction unit is a matching candidate block, go to Steps 1 and 3, and wait for the selection calculation; if it is greater than Pixel_th, it means that the prediction unit is non-matching Candidate blocks, do not need to be calculated again; Pixel_th is the adaptive downsampling threshold; Step 13: Determine whether the matching candidate block exceeds the search range, if it exceeds the search range, perform step 2; if it does not exceed the search range, search for the next matching candidate block, and perform step 11; In the step 1 and 2, the absolute value of the single pixel difference between the previous frame and the current frame in the prediction unit is calculated, and the specific process is to use the following formula: SAD_c=abs(piOrg[i]-piCur[i]) Among them, piOrg represents the pixel in the current frame, piCur represents the pixel in the previous frame, abs is the symbol of the absolute value, SAD_c is the absolute value of the difference between the previous frame and the current frame single pixel in the prediction unit, and i is the prediction unit. The ith pixel of ; The specific solution process of the adaptive downsampling threshold Pixel_th in the steps 1 and 2 is as follows: The current adaptive downsampling threshold is estimated by accumulating and averaging the errors calculated by each prediction unit in the previous CTU; CTU is the coding tree unit; The specific process of accumulating each SAD_c obtained in the steps 1 and 2 is as follows: in, f _i (m _u , n _u ) is the pixel value of the coordinates (m _u , n _u ) in the image, the horizontal and vertical coordinates (m _u , n _u ) are the pixels on the downsampling template, the horizontal and vertical coordinates (x, y) ) represents a motion vector, and the prediction unit whose SAD(x, y) is less than or equal to the adaptive downsampling threshold is used as a matching candidate group; the prediction unit whose SAD(x, y) is greater than the adaptive downsampling threshold is used as a non-matching candidate group; M is the length of the prediction block, which is any one of 4, 8, 16, 32, and 64, and M≤4N; N is the height of the prediction block, which is 4, 8, 16, 32, and 64. Any one of them, N≤4M; The value of the search range is 64×64; The selection stage in the second step: select the matching group obtained in the primary selection stage based on the rate-distortion optimization criterion, select the final matching block, and complete the process of block matching in motion estimation; the specific process is: The prediction unit in the matching candidate block is selected based on the rate-distortion optimization criterion, and the calculation formula is as follows: J=S(x,y)+λmotion*Rmotion In the formula, (m, n) are all the pixels in the prediction unit, Rmotion is the number of bits required for the prediction unit to encode motion information, λmotion is the Lagrangian factor in the motion estimation process, and the encoder will choose to make rate-distortion The value with the smallest cost J is used as the final matching block of the current block. 2. a kind of motion estimation block matching method based on H.265 video coding according to claim 1, is characterized in that: the concrete solution process of search range in described step 13 is: A prediction point is obtained from the previous frame, and a rectangular search range is obtained with the prediction point as the center; an early cutoff algorithm is used to process the rectangular search range to obtain the search range.