CN102917225B - HEVC intraframe coding unit fast selecting method - Google Patents

Abstract

The invention provides a kind of HEVC intraframe coding unit fast selecting method.Relevant with the histogram of gradients of the non-normalized of CU owing to being similar to absolute error and SAD the rate distortion costs of each CU obtained.The CU of two equal dimensions, its non-normalized histogram of gradients similarity degree is higher, and segmentation identifier is more equal.The present invention uses the template matches mode based on non-normalized histogram of gradients to realize the quick selection of CU, thus improves the method for the coding rate of HEVC intra-frame prediction method.Utilize non-normalized histogram of gradients as feature to judge that each CU is the need of being divided into four less CU.Under the condition meeting template matches, eliminate the step comparing encoding rate distortion cost one by one.

Description

HEVC intra coding unit fast selection method

technical field

The present invention proposes a high-performance video coding (High Efficiency Video Coding, HEVC) technology, and particularly relates to a technology for selecting a predictive coding unit during coding.

Background technique

With the development and maturity of high-definition video technology, a large number of high-definition video applications have emerged in people's daily life. Various applications of high-definition video have been welcomed and favored by users. However, the larger amount of data brought by the higher resolution makes high-definition video more demanding on the compression performance of the video codec algorithm. The current video codec standards (such as H.264/AVC, etc.) often cannot well meet the compression performance requirements of high-definition video. In order to meet the requirements of new video applications for codec standards, the Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T/ISO/IEC is developing a new next-generation video codec standard HEVC. . In order to be suitable for real-time application of video technology, we need to increase the encoding speed of HEVC. The present invention is mainly dedicated to improving the HEVC intra-frame coding speed and reducing the computational complexity.

At present, there is mainly a type of fast algorithm for HEVC intra-frame coding. That is, fast selection based on the predicted direction. In this method, the prediction direction is judged by the gradient information of the current block; and the prediction direction of the adjacent block is used to assist in judging the prediction direction of the current block. However, most of these methods improve intra coding speed by enabling fast selection of prediction directions. There is no attempt to solve the problem from the perspective of fast selection of coding units (CU, Coding Unit). In fact, the CU scales during intra-frame coding are 64x64, 32x32, 16x16, and 8x8. When encoding each 64x64 largest coding unit (LCU), it is necessary to traverse down from the scale 64x64 to 8x8 according to the quadtree structure for rate-distortion optimization and select the most suitable CU scale. Since the minimum size of a CU is 8x8, it cannot be further divided into smaller CUs for an 8x8CU. But the 8x8 CU can be divided into four 4x4 prediction units (Prediction Unit, PU) to encode. If we can quickly predict the final intra-coded CU scale, then many CU prediction processes can be saved during the intra prediction process.

In the existing HEVC intra-frame coding process, each LCU is coded by traversing the CUs with scales from 64x64 (minimum depth) to 8x8 according to the quadtree structure. Each CU has a split flag (splitflag) during traversal. This splitflag is used to determine whether the current CU needs to be divided into four smaller-scale CUs, that is, to calculate and compare the rate-distortion cost J _split of the CU under the current size after split encoding and the rate-distortion cost J _unsplit of unsplit encoding. size; when the rate-distortion cost J _unsplit is less than or equal to the rate-distortion cost J _split , the current CU is no longer split, and the split identifier marking the CU is unsplit; when the rate-distortion cost J _unsplit is greater than the rate-distortion cost J _split , the current CU The CU still needs to be split, mark the split identifier of the CU as split, and continue to use the rate-distortion cost to judge whether it needs to be further split after the CU is split, until the judgment of the minimum scale 8x8 (maximum depth) is completed, in the current While the split identifier of the CU is determined, the encoding information of the mode corresponding to the split identifier is saved to update the corresponding encoding information of the current LCU.

Contents of the invention

The technical problem to be solved by the present invention is a method for rapidly selecting HEVC intra-frame coding units based on template matching.

The technical solution adopted by the present invention for solving the above-mentioned technology is, HEVC intra-frame coding unit quick selection method, comprises the following steps:

Step 1. From the largest coding unit LCU to be predicted sequentially extracted in the current coding frame, judge the coding unit size of the LCU from the depth corresponding to the largest coding scale;

Step 2. Calculate the kth coding unit of the current coding frame at the current depth i The unnormalized gradient histogram of , judging that the coded segmentation identifier at the current depth i in the current coding frame is the number of coding units for the split split And the split identifier is the number of coding units that do not split unsplit Whether they are all greater than or equal to the preset template matching start threshold N, if not, judge the coding unit size based on the rate-distortion cost, that is, go to step 3; if yes, judge the coding unit size based on template matching, that is, go to step 4;

Step 3. Judgment step of coding unit scale based on rate-distortion cost: for coding units at current depth i Perform unsplit encoding and split encoding respectively, compare the rate-distortion cost of the two encoding methods, and select the method with the lower rate-distortion cost to assign a value to the split identifier; when the encoding unit The split identifier of is assigned as unsplit, then go to step 5; if the coding unit Assign the split identifier of split to split, then go to step 6;

Step 4. Step of judging the coding unit scale based on template matching: the coding unit The non-normalized gradient histogram of is matched with the non-normalized gradient histogram of the coded coding unit at the current depth i in the current coding frame to find out the coding unit The most similar set number x coded coding units; judge whether the segmentation identifiers of the x coded coding units are all the same, if not, return to step 3; such as the segmentation identifiers of the x coded coding units symbols are unsplit, then the code unit Perform unsplit coding and calculate the rate-distortion cost corresponding to the coding method, and then go to step 5; if the split identifiers of the x coded coding units are all split, the coding unit Perform split coding and calculate the rate-distortion cost in the corresponding coding method, and then enter step 6; where, x≤N;

Step 5. Retain the rate-distortion cost and encoding information encoded in the unsplit mode, and update the number of coding units whose segmentation identifier is unsplit at the current depth i in the current encoding frame The initial value is 0;

Step 6. Retain the rate-distortion cost and encoding information encoded in the split mode, and update the number of coding units whose split identifier is split at the current depth i in the current encoding frame The initial value is 0; determine whether the current depth i is the depth corresponding to the encoding scale 8x8, if the current depth is the depth corresponding to the encoding scale 8x8, then further determine whether the current LCU still has a coding unit that needs scale judgment under the current depth, if so, Update k=k+1, return to step 2, if not, enter step 7; if the current depth is not the depth corresponding to 8x8, then update the current depth i=i+1, return to step 2;

Step 7. Determine whether there are unencoded coding units in the current LCU. If so, update the current depth i to the depth corresponding to the scale of the next unencoded coding unit. If not, the current LCU has been encoded, and further judge whether it has reached The frame end of the current coded frame, if the end of the frame is reached, the encoding of the current coded frame ends, if the end of the frame is not reached, return to step 1.

The present invention proposes a template matching method based on a non-normalized gradient histogram to realize fast selection of a CU, thereby improving the coding speed of the HEVC intra prediction method.

After analysis, it is found that the rate-distortion cost of each CU approximated by absolute error and SAD is proportional to the difference between the predicted pixel and the source pixel, and this proportional relationship is related to the unnormalized gradient histogram of the CU. The more similar the unnormalized gradient histograms of two CUs of equal scale are, the more likely the split identifiers are equal. Therefore, the present invention uses the non-normalized gradient histogram as a feature to judge whether each CU needs to be divided into four smaller CUs. Under the condition of satisfying the template matching, the step of comparing the encoding rate distortion cost one by one is omitted.

The beneficial effect of the present invention is that, based on the non-normalized histogram, the method of template matching is used to predict the block mode of the current CU, the calculation complexity is low, the detection accuracy is high, the method is simple and efficient, and there is almost no loss in ensuring the coding quality Under the premise of greatly reducing the time complexity of HEVC intra prediction.

Description of drawings

Figure 1 is an example of template matching fast prediction method.

Detailed ways

The present invention uses the non-normalized gradient histogram as a feature to judge whether the current CU needs to be divided into four smaller CUs. Consider that within the same video frame, similar regions may appear repeatedly. We use a template matching method to find x CUs that are most similar to the unnormalized gradient histogram of the current CU among the CUs of the same scale that have been coded in front of the current frame, and judge by the corresponding splitflag of these x CUs The splitflag of the current CU. When the splitflags of the x CUs are all the same, the splitflag of the current CU is also equal to the splitflags of the x CUs. Otherwise, when the x CUs are not completely the same, the current CU is determined to be split or unsplit according to the existing rate-distortion cost comparison method.

As shown in Figure 1, the black block cu _k is the CU currently being encoded. C={cu ₀ ,cu ₁ ,...,cu _k-1 } is a set of coded CUs in the current frame, consisting of gray blocks and white blocks. The gray block is the split block, and the white block is the unsplit block. The process of template matching is to search for x CUs most similar to cu _k in C. If the splitflags of the x CU pairs are the same, then cu _k also adopts the same splitflag. Otherwise, calculate the rate-distortion cost of the current CU in the case of split and unsplit, and select splitflag by comparing the rate-distortion cost. Right now

${\mathrm{<span\; class="notranslate">\; split\; flag</span>}}_{{\mathrm{<span\; class="notranslate">\; cu</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; unsplit</span>}& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; mu</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; J</span>}}_{\mathrm{<span\; class="notranslate">\; unsplit</span>}}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; J</span>}}_{\mathrm{<span\; class="notranslate">\; split</span>}}\\ \mathrm{<span\; class="notranslate">\; split</span>}& {\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; ms</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; J</span>}}_{\mathrm{<span\; class="notranslate">\; split</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; J</span>}}_{\mathrm{<span\; class="notranslate">\; unsplit</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Where x _mu and x _ms are the number of unsplit and split CUs in the x most matched CUs, respectively. J _split and J _unsplit are the rate-distortion costs calculated according to the split and unsplit methods of the current block, respectively.

In addition, for each CU of depth i, if the coded CU of the current frame only belongs to one type, the current block cannot be distinguished well. Because similar CUs found during matching also belong to this category. In turn, the CUs of the entire frame belong to this category. Obviously, this prediction error is large. Therefore, it is required that before template matching, the minimum value of the number of two types of reference CUs must not be less than a fixed value, that is, the preset template matching start threshold N:

$\mathrm{<span\; class="notranslate">\; min</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; pu</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; ps</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

in, and are the numbers of encoded unsplit CU and split CU in the current frame, respectively.

Since the number of small-scale CUs in high-definition images is large, in order to make the matching effect better, a method similar to uniform sampling can be used to perform template sampling matching on CUs according to a certain step size s, that is, every s encoded CU samples one for comparison. In order to make the value of the step size s more flexible, the step size s is a dynamic step size, and the size of s is related to the number of CUs encoded in the current frame:

$\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\frac{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; pu</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; ps</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

T is a control parameter, which can be adjusted according to experience.

Example

The present invention is realized on the HM6.0 experimental platform, and the steps are as follows:

Initialization steps:

Step 1: From the largest coding unit LCU to be predicted sequentially extracted in the current coding frame, start to judge the coding unit scale of the LCU from the depth corresponding to the maximum coding scale; Before encoding, and initialized to 0;

Coding unit scale judgment steps:

Step 2: Calculate the k-th coding unit of the current coding frame at the current depth i The non-normalized gradient histogram of ; judge that the coded segmentation identifier at the current depth i in the current coding frame is the number of coding units for the split split And the split identifier is the number of coding units that do not split unsplit Whether they are all greater than or equal to the preset template matching start threshold N, that is, to judge whether to meet $\min (x_{\mathrm{pu}}^i,x_{\mathrm{ps}}^i)\&Greater\; Equal;N$ and $\max (x_{\mathrm{pu}}^i,x_{\mathrm{ps}}^i)\&Greater\; Equal;x,$ If not, perform a judgment on the size of the coding unit based on the rate-distortion cost, that is, go to step 3; if yes, perform a judgment on the size of the coding unit based on template matching, that is, go to step 4;

Step 3. Judgment step of coding unit scale based on rate-distortion cost: for coding units at current depth i Perform unsplit encoding and split encoding respectively, compare the rate-distortion cost of the two encoding methods, and select the method with the lower rate-distortion cost to assign a value to the split identifier; when the encoding unit The split identifier of is assigned as unsplit, then go to step 5; if the coding unit Assign the split identifier of split to split, then go to step 6;

Step 4. Step of judging the coding unit scale based on template matching: the coding unit The non-normalized gradient histogram of is matched with the non-normalized gradient histogram of the coded coding unit at the current depth i in the current coding frame sampled every step s, and the unnormalized gradient histogram of the coding unit is found Set the most similar number of x coded coding units; judge whether the division identifiers of x coded coding units are all the same, that is, whether max(x _mu , x _ms )==x, if not, return Step 3: If the split identifiers of the x coded coding units are all unsplit, then the coding unit Perform unsplit coding and calculate the rate-distortion cost corresponding to the coding method, and then go to step 5; if the split identifiers of the x coded coding units are all split, the coding unit Perform unsplit encoding and calculate the rate-distortion cost under the corresponding encoding method, and then enter step 6; where x≤N;

Cycle judgment steps:

Step 5. Retain the rate-distortion cost and encoding information encoded in the unsplit mode, and update the number of coding units whose segmentation identifier is unsplit at the current depth i in the current encoding frame

Step 6. Retain the rate-distortion cost and encoding information encoded in the split mode, and update the number of coding units whose split identifier is split at the current depth i in the current encoding frame Determine whether the current depth i is the depth corresponding to the encoding scale 8x8, if the current depth is the depth corresponding to the encoding scale 8x8, and then further determine whether the current LCU still has coding units that require scale judgment under the current depth, if so, update k=k+ 1. Return to step 2, if not, proceed to step 7; if the current depth is not the depth corresponding to 8x8, update the current depth i=i+1, and return to step 2;

Step 7. Determine whether there are unencoded coding units in the current LCU. If so, update the current depth i to the depth corresponding to the scale of the next unencoded coding unit. If not, the current LCU has been encoded, and further judge whether it has reached The frame end of the current coded frame, if the end of the frame is reached, the coding of the current coded frame ends, if the end of the frame is not reached, return to step 1.

Claims (3)

1. A fast method for selecting a coding unit in an HEVC frame, comprising the following steps: Step 1. From the largest coding unit LCU to be predicted sequentially extracted in the current coding frame, the coding unit scale judgment is performed on the LCU from the depth corresponding to the maximum coding scale; Step 2. Calculate the kth coding unit at the current depth i in the current coding frame The unnormalized gradient histogram of , judging that the coded segmentation identifier at the current depth i in the current coding frame is the number of coding units for the split split And the split identifier is the number of coding units that do not split unsplit Whether they are all greater than or equal to the preset template matching start threshold N, if not, judge the coding unit size based on the rate-distortion cost, that is, go to step 3; if yes, judge the coding unit size based on template matching, that is, go to step 4; Step 3. Judgment step of coding unit scale based on rate-distortion cost: for coding units at current depth i Perform unsplit encoding and split encoding respectively, compare the rate-distortion cost of the two encoding methods, and select the method with the lower rate-distortion cost to assign a value to the split identifier; when the encoding unit The split identifier of is assigned as unsplit, then go to step 5; if the coding unit Assign the split identifier of split to split, then go to step 6; Step 4. Step of judging the coding unit scale based on template matching: the coding unit The non-normalized gradient histogram of is matched with the non-normalized gradient histogram of the coded coding unit at the current depth i in the current coding frame to find out the coding unit The most similar set number of x coded coding units; determine whether the division identifiers of x coded coding units are all the same, if not, return to step 3; such as the division identifiers of x coded coding units Both are unsplit, then the coding unit Perform unsplit coding and calculate the rate-distortion cost corresponding to the coding method, and then go to step 5; if the split identifiers of the x coded coding units are all split, the coding unit Perform split coding and calculate the rate-distortion cost in the corresponding coding method, and then enter step 6; where, x≤N; Step 5. Retain the rate-distortion cost and encoding information encoded in the unsplit mode, and update the number of coding units whose segmentation identifier is unsplit at the current depth i in the current encoding frame The initial value is 0; Step 6. Retain the rate-distortion cost and encoding information encoded in the split mode, and update the number of coding units whose split identifier is split at the current depth i in the current encoding frame The initial value is 0; determine whether the current depth i is the depth corresponding to the encoding scale 8x8, if the current depth is the depth corresponding to the encoding scale 8x8, then further determine whether the current LCU still has a coding unit that needs scale judgment under the current depth, if so, Update k=k+1, return to step 2, if not, enter step 7; if the current depth is not the depth corresponding to 8x8, then update the current depth i=i+1, return to step 2; Step 7. Determine whether there are unencoded coding units in the current LCU. If so, update the current depth i to the depth corresponding to the scale of the next unencoded coding unit. If not, the current LCU has been encoded, and further judge whether it has reached The frame end of the current coded frame, if the end of the frame is reached, the coding of the current coded frame ends, if the end of the frame is not reached, return to step 1. 2. The HEVC intra-frame coding unit fast selection method as claimed in claim 1, characterized in that, in the step 4, the coding unit The unnormalized gradient histogram of is matched with the unnormalized gradient histogram of the coded coding unit sampled according to the dynamic step size under the current depth i in the current coding frame, and the value of the dynamic step size is the same as that of the coded coding unit proportional to the number of coding units. 3. as claimed in claim 2, HEVC intra coding unit quick selection method is characterized in that, the concrete method of described dynamic step size value is: Among them, s is the value of the dynamic step, and T is the control parameter.