CN102917225A - Method for quickly selecting HEVC (high-efficiency video coding) inframe coding units - Google Patents

Abstract

The present invention provides a fast selection method of an HEVC intra-frame coding unit. The per-CU rate-distortion cost due to the absolute error and SAD approximation 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. The present invention uses a template matching method based on a non-normalized gradient histogram to realize fast selection of a CU, thereby improving the encoding speed of the HEVC intra-frame prediction method. Use the unnormalized 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.

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. the

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. 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. the

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 8x8CU 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. the

In the existing HEVC intra-frame encoding process, each LCU is encoded by traversing the CUs 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

The technical solution adopted by the present invention for solving the above-mentioned technology is, HEVC intra-frame coding unit fast 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;

的非归一化梯度直方图，判断在当前编码帧中当前深度i下已编码的分割标识符为分割split的编码单元数目

以及分割标识符为不分割unsplit的编码单元数目

是否均大于等于预设的模板匹配启动门限N，如否，进行基于率失真代价的编码单元尺度判断，即进入步骤3；如是，进行基于模板匹配的编码单元尺度判断，即进入步骤4；  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;

分别进行unsplit方式编码、split方式编码，比较两种编码方式的率失真代价大小，选择率失真代价较小的方式为分割标识符赋值；当编码单元

的分割标识符赋值为unsplit，则进入步骤5；如编码单元

的分割标识符赋值为split，则进入步骤6；  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;

的非归一化梯度直方图与当前编码帧中当前深度i下已编码的编码单元的非归一化梯度直方图进行匹配，找出与编码单元最相似的设定个数l个已编码的编码单元；判断l个已编码的编码单元的的分割标识符是否全部相同，如否，返回步骤3；如l个已编码的编码单元的的分割标识符均为unsplit，则对编码单元

进行unsplit方式编码并对应编码方式下的计算率失真代价，再进入步骤5；如l个已编码的编码单元的的分割标识符均为split，对编码单元

进行unsplit方式编码并计算对应编码方式下的率失真代价，再进入步骤6；其中，l≤N；  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 setting number is l coded coding units; judge whether the segmentation identifiers of l coded coding units are all the same, if not, return to step 3; such as the segmentation of l coded coding units identifiers are unsplit, then the code unit

Perform unsplit coding and calculate the rate-distortion cost corresponding to the coding method, and then enter step 5; if the split identifiers of l coded coding units are all split, the coding unit

Perform unsplit encoding and calculate the rate-distortion cost in the corresponding encoding mode, and then enter step 6; where l≤N;

初值为0；  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;

初值为0；判断当前深度i是否为编码尺度8x8对应的深度，如当前深度为编码尺度8x8对应的深度，再进一步判断当前LCU在当前深度下是否还有需要尺度判断的编码单元，如是，更新k=k+1，返回步骤2，如否，进入步骤7；如当前深度不为8x8对应的深度，则更新当前深度i＝i+1，返回步骤2；  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, 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

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. the

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

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. the

Description of drawings

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

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 the l CU that is 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 the l CU The splitflag of the current CU. When the splitflags of the l CUs are the same, the splitflag of the current CU is also equal to the splitflags of the l CUs. Otherwise, when the l 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. the

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 l CUs most similar to cu _k in C. If the splitflags of these l CUs 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>}}_{\text{<span class="notranslate"> k</span>}}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; unsplit</span>}& {\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; mu</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</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">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; ms</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</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>$

Among them, l _mu and l _ms are the number of unsplit and split CUs in the l 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">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; pu</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; l</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>$

和

分别为当前帧中已编码的unsplit CU和split CU的数目。  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">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; pu</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; l</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. the

Example

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

Initialization steps:

和

初始化为0；  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:

的非归一化梯度直方图；判断在当前编码帧中当前深度i下已编码的分割标识符为分割split的编码单元数目

以及分 割标识符为不分割unsplit的编码单元数目

是否均大于等于预设的模板匹配启动门限N，即判断是否满足 $\min (l_{\mathrm{pu}}^i,l_{\mathrm{ps}}^i)\&GreaterEqual;N$ 且 $\max (l_{\mathrm{pu}}^i,l_{\mathrm{ps}}^i)\&GreaterEqual;l,$ 如否，进行基于率失真代价的编码单元尺度判断，即进入步骤3；如是，进行基于模板匹配的编码单元尺度判断，即进入步骤4；  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 (l_{\mathrm{pu}}^i,l_{\mathrm{ps}}^i)\&Greater\; Equal;N$ and $\max (l_{\mathrm{pu}}^i,l_{\mathrm{ps}}^i)\&Greater\; Equal;l,$ 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;

分别进行unsplit方式编码、split方式编码，比较两种编码方式的率失真代价大小，选择率失真代价较小的方式为分割标识符赋值；当编码单元

的分割标识符赋值为unsplit，则进入步骤5；如编码单元

的分割标识符赋值为split，则进入步骤6；  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;

的非归一化梯度直方图与每隔步长s采样当前编码帧中当前深度i下已编码的编码单元的非归一化梯度直方图进行匹配，找出与编码单元

最相似的设定个数l个已编码的编码单元；判断l个已编码的编码单元的的分割标识符是否全部相同，即是否max(l_mu,l_ms)==l，如否，返回步骤3；如l个已编码的编码单元的的分割标识符均为unsplit，则对编码单元进行unsplit方式编码并对应编码方式下的计算率失真代价，再进入步骤5；如l个已编码的编码单元的的分割标识符均为split，对编码单元

进行unsplit方式编码并计算对应编码方式下的率失真代价，再进入步骤6；其中，l≤N；  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 l encoded coding units; judge whether the segmentation identifiers of l encoded coding units are all the same, that is, whether max(l _mu ,l _ms )==l, if not, return Step 3: If the split identifiers of the l 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 enter step 5; if the split identifiers of l coded coding units are all split, the coding unit

Perform unsplit encoding and calculate the rate-distortion cost in the corresponding encoding mode, and then enter step 6; where l≤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

判断当前深度i是否为编码尺度8x8对应的深度，如当前深度为编码尺度8x8对应的深度，再进一步判断当前LCU在当前深度下是否还有需要尺度判断的编码单元，如是，更新k=k+1，返回步骤2，如否，进入步骤7；如当前深度不为8x8对应的深度，则更新当前深度i＝i+1，返回步骤2；  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, 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, 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 encoding of the current coded frame ends, if the end of the frame is not reached, return to step 1. the

Claims (3)

1. The fast HEVC intra-frame coding unit selection method is characterized by comprising the following steps of:

   step 1, in a largest coding unit LCU to be predicted which is sequentially extracted from a current coding frame, carrying out coding unit scale judgment on the LCU from the depth corresponding to the largest coding scale;

   step 2, calculating the kth coding unit under the current depth i in the current coding frame

   

   Of (2) isNormalizing the gradient histogram, and determining the number of coding units with partition split identifier coded at current depth i in the current coding frame

   

   And the number of coding units with split identifier as undivided

   

   Whether the template matching starting thresholds are all larger than or equal to a preset template matching starting threshold N, if not, judging the coding unit scale based on the rate distortion cost, namely entering the step 3; if yes, carrying out coding unit scale judgment based on template matching, namely entering the step 4;

   step 3, coding unit scale judgment based on rate distortion cost: for coding unit under current depth i

   

   Respectively carrying out unsplit mode coding and split mode coding, comparing the rate distortion cost of the two coding modes, and selecting a mode with lower rate distortion cost to assign a partition identifier; when coding unit

   

   The partition identifier is assigned as unsplit, and then the step 5 is carried out; such as a coding unit

   

   If the partition identifier is assigned as split, then step 6 is entered;

   step 4, judging the coding unit scale based on template matching: coding unit

   

   The non-normalized gradient histogram of the current coding frame is matched with the non-normalized gradient histogram of the coding unit coded under the current depth i in the current coding frame, and the coding unit is found out

   

   The most similar set number of coded coding units is l; judging whether the segmentation identifiers of the coded coding units are all the same or not, if not, returning to the step 3; if the partition identifiers of the l coded coding units are all unsplit, the coding units are coded

   

   Coding in an unsplit mode and corresponding to the rate distortion cost under the coding mode, and then entering the step 5; if the partition identifiers of the l coded coding units are split, the coding units are coded by split

   

   Performing unsplit mode coding and calculating the rate distortion cost under the corresponding coding mode, and then entering step 6; wherein l is less than or equal to N;

   step 5, reserving the rate distortion cost and the coding information coded in the unsplit mode, and updating the number of coding units with unsplit partition identifiers coded under the current depth i in the current coding frame

   

   The initial value is 0;

   step 6, reserving rate distortion cost and coding information coded in a split mode, and updating the number of coding units with split identifiers of split in the current depth i in the current coding frame

   

   The initial value is 0; judging whether the current depth i is the depth corresponding to the coding scale 8x8, if so, further judging the current LCU depthIf yes, updating k = k +1, returning to the step 2, and if no, entering the step 7; if the current depth is not the depth corresponding to 8x8, updating the current depth i to i +1, and returning to the step 2;

   and 7, judging whether the current LCU has coding units which are not coded completely, if so, updating the current depth i to be the depth corresponding to the size of the next coding unit which is not coded completely, if not, finishing the coding of the current LCU, further judging whether the frame end of the current coding frame is reached, if so, finishing the coding of the current coding frame, otherwise, returning to the step 1.
2. 2. The HEVC intra-frame coding unit quick selection method of claim 1, wherein in the step 4, the coding unit is coded

   

   The non-normalized gradient histogram of the coded coding unit is sampled according to dynamic step length for matching with the non-normalized gradient histogram of the coded coding unit at the current depth i in the current coding frame, and the value of the dynamic step length is in direct proportion to the number of the coded coding units.
3. 3. The method for quickly selecting an HEVC intra coding unit according to claim 2, wherein the specific method for the value of the dynamic step size is:wherein s is a dynamic step value, and T is a control parameter.

Images