CN102917225B

CN102917225B - HEVC intraframe coding unit fast selecting method

Info

Publication number: CN102917225B
Application number: CN201210411951.9A
Authority: CN
Inventors: 李宏亮; 熊健
Original assignee: University of Electronic Science and Technology of China
Current assignee: University of Electronic Science and Technology of China
Priority date: 2012-10-25
Filing date: 2012-10-25
Publication date: 2015-10-28
Anticipated expiration: 2032-10-25
Also published as: CN102917225A

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-frame coding unit quick selection method

Technical Field

The present invention relates to a High Efficiency Video Coding (HEVC) technology, and more particularly, to a technology for selecting a prediction Coding unit in Coding.

Background

Along with the development and maturity of high-definition video technology, a large number of applications of high-definition videos emerge in daily life. Various applications for high definition video are popular and appreciated by users. However, the higher resolution brings larger data volume, so that the high definition video has higher requirement on the compression performance of the video coding and decoding algorithm. The current video coding and decoding standards (such as H.264/AVC) often cannot well meet the requirement of high-definition video on compression performance. In order to meet the requirements of new Video applications on Coding and decoding standards, a Joint Video Coding Joint coordination Team (JCT-VC) of ITU-T/ISO/IEC is making a new next-generation Video Coding standard HEVC at the day. To be suitable for real-time applications of video technology, we need to improve the coding speed of HEVC. The invention mainly aims to improve the intra-frame coding speed of HEVC and reduce the computational complexity.

Currently, there is mainly a class of fast algorithms for HEVC intra coding. I.e. a fast selection based on the prediction direction. The method comprises the steps of judging the prediction direction through gradient information of a current block; the prediction direction of the neighboring block is also used to assist in determining the prediction direction to the current block. However, most of these methods improve the intra-coding speed by enabling quick selection of the prediction direction. No attempt is made to solve the problem from the perspective of a quick selection of Coding Units (CUs). In fact, the dimensions of a CU when intra-coded are 64x64, 32x32, 16x16, 8x 8. When each maximum coding unit (LCU) of 64x64 is coded, rate distortion optimization needs to be performed by traversing from the scale 64x64 to 8x8 according to a quadtree structure, and the most suitable CU scale is selected. Since the smallest dimension of a CU is 8x8, it is no longer possible for 8x8CU to split down into smaller CUs. But 8x8CU may be coded in 4 Prediction Units (PUs) of 4x 4. If we can predict the final intra-coded CU scale quickly, many CU prediction processes can be omitted in the intra prediction process.

In the existing HEVC intra coding process, the coding of each LCU is traversed by a CU from 64x64 (depth minimum) to 8x8 scale in a quadtree structure. Each CU has a partition identifier (split flag) during the traversal. This split flag is used to determine whether the current CU needs to be split into four smaller-sized CUs, i.e. the rate-distortion cost J after split coding for the CU at the current size is calculated and compared_splitRate-distortion cost J with undivided coding_unsplitThe size of (d); current rate distortion cost J_unsplitLess than or equal to a rate-distortion cost J_splitIf yes, the current CU is not divided any more, and the division identifier of the CU is marked as unsplit; current rate distortion cost J_unsplitGreater than the rate-distortion cost J_splitIf the current CU needs to be divided, the division identifier of the CU is marked as split, and whether further division is needed after the CU is divided is determined by using the rate-distortion cost until the minimum scale 8x8 (with the maximum depth) is determined, and the corresponding coding information of the current LCU is updated by storing the coding information of the mode corresponding to the division identifier while the division identifier of the current CU is determined.

Disclosure of Invention

The invention aims to solve the technical problem of a method for quickly selecting HEVC intra-frame coding units based on template matching.

The invention adopts the technical scheme that the HEVC intra-frame coding unit quick selection method comprises the following steps:

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 of the current coding frame under the current depth iThe non-normalized gradient histogram of (1) determines the number of coding units of which the partition identifier coded at the current depth i in the current coding frame is partition splitAnd the number of coding units with split identifier as undividedWhether 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 iRespectively 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 unitThe partition identifier is assigned as unsplit, and then the step 5 is carried out; such as a coding unitIf the partition identifier is assigned as split, then step 6 is entered;

step 4, judging the coding unit scale based on template matching: coding unitIs matched with the non-normalized gradient histogram of the coded coding unit at the current depth i in the current coding frame,finding and encoding unitThe most similar set number x of coded coding units; judging whether the segmentation identifiers of the x coded coding units are all the same, if not, returning to the step 3; if the partition identifiers of the x coded coding units are all unsplit, then the coding units are codedCoding 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 x coded coding units are split, the coding units are coded by splitPerforming split mode coding and calculating the rate distortion cost under the corresponding coding mode, and then entering the step 6; wherein x 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, determining whether the current depth is the coding scale 8x8If so, updating k to be k +1, returning to the step 2, and if not, 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.

The invention provides a method for realizing rapid selection of a CU (channel Unit) based on a template matching mode of a non-normalized gradient histogram, so as to improve the coding speed of an HEVC intra-frame prediction method.

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

The method has the advantages that the block division mode of the current CU is predicted by adopting a template matching mode based on the non-normalized histogram, the calculation complexity is low, the detection accuracy is high, the method is simple and efficient, and the time complexity of HEVC intra-frame prediction is greatly reduced on the premise of ensuring that the coding quality is hardly lost.

Drawings

Fig. 1 is an example of a template matching fast prediction method.

Detailed Description

The method utilizes the non-normalized gradient histogram as a feature to judge whether the current CU needs to be divided into four smaller CUs. It is contemplated that similar regions may recur within the same video frame. The method comprises the steps of searching x CUs which are most similar to a non-normalized gradient histogram of a current CU in a CU which is coded in the front of the current CU and has the same scale by adopting a template matching mode, and judging the split flag of the current CU according to the split flags corresponding to the x CUs. When the split flag of the x CUs are all the same, the split flag of the current CU is also equal to the split flag of the x CUs. Otherwise, when the x CUs are not completely the same, the current CU determines that the partition mode is split or unsplit according to the existing rate-distortion cost comparison mode.

As shown in FIG. 1, the black block cu_kThe CU currently being encoded. C ═ cu₀,cu₁,…,cu_k-1And the CU is a set of coded CUs of the current frame and is composed of gray blocks and white blocks. Wherein the grey color block is split block, and the white color block is unsplit block. The process of template matching is to search for cu in C_kThe most similar x CUs. If the split flag for these x CU's is the same, then CU_kThe same split flag was also used. Otherwise, rate distortion cost of the current CU under the conditions of split and unsplit is calculated, and split flag is selected by comparing the rate distortion cost. Namely, it is

<math> <mrow> <msub> <mi>splitflag</mi> <msub> <mi>cu</mi> <mi>k</mi> </msub> </msub> <mo>=</mo> <mfenced open='{' close=''> <mtable> <mtr> <mtd> <mi>unsplit</mi> </mtd> <mtd> <msub> <mi>x</mi> <mi>mu</mi> </msub> <mo>=</mo> <mo>=</mo> <mi>x</mi> <mo>|</mo> <mo>|</mo> <msub> <mi>J</mi> <mi>unsplit</mi> </msub> <mo>≤</mo> <msub> <mi>J</mi> <mi>split</mi> </msub> </mtd> </mtr> <mtr> <mtd> <mi>split</mi> </mtd> <mtd> <msub> <mi>x</mi> <mi>ms</mi> </msub> <mo>=</mo> <mo>=</mo> <mi>x</mi> <mo>|</mo> <mo>|</mo> <msub> <mi>J</mi> <mi>split</mi> </msub> <mo><</mo> <msub> <mi>J</mi> <mi>unsplit</mi> </msub> </mtd> </mtr> </mtable> </mfenced> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mrow> </math>

Wherein x_muAnd x_msThe number of CU of unsplit and split, respectively, of the x best-matched CU. J. the design is a square_splitAnd J_unsplitAnd respectively calculating the rate-distortion cost of the current block according to a split mode and an unsplit mode.

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

<math> <mrow> <mi>min</mi> <mrow> <mo>(</mo> <msubsup> <mi>x</mi> <mi>pu</mi> <mi>i</mi> </msubsup> <mo>,</mo> <msubsup> <mi>x</mi> <mi>ps</mi> <mi>i</mi> </msubsup> <mo>)</mo> </mrow> <mo>&GreaterEqual;</mo> <mi>N</mi> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> </mrow> </math>

wherein,andthe number of unsplit CU and split CU that have been coded in the current frame, respectively.

Because the number of the CUs with smaller scales in the high-definition image is large, in order to enable the matching effect to be better, template sampling matching can be performed on the CUs according to a certain step length s in a similar uniform sampling mode, namely one sample of each s of coded CUs is compared. In order to make the value of the step length s more flexible, the step length s is a dynamic step length, and the size of s is related to the number of coded CUs in the current frame:

s = \max (1, \frac{x_{pu}^{i} + x_{ps}^{i}}{T}) - - - (3)

t is a control parameter and can be adjusted according to experience.

Examples

The invention is realized on an HM6.0 experiment platform, and comprises the following steps:

an initialization step:

step 1: in the largest coding unit LCU to be predicted which is sequentially extracted from the current coding frame, the coding unit scale judgment is carried out on the LCU from the depth corresponding to the largest coding scale; before encoding the CU at depth i of each frame,andinitialization is 0;

a coding unit scale judging step:

step 2: calculating the k-th coding unit of the current coding frame under the current depth iNon-normalized gradient histogram of (a); judging the number of coding units of which the partition identifier coded at the current depth i in the current coding frame is partition splitAnd the number of coding units with split identifier as undividedWhether the template matching starting thresholds are all larger than or equal to a preset template matching starting threshold N or not is judged, namely whether the template matching starting thresholds meet the requirements or not is judged

<math> <mrow> <mi>min</mi> <mrow> <mo>(</mo> <msubsup> <mi>x</mi> <mi>pu</mi> <mi>i</mi> </msubsup> <mo>,</mo> <msubsup> <mi>x</mi> <mi>ps</mi> <mi>i</mi> </msubsup> <mo>)</mo> </mrow> <mo>&GreaterEqual;</mo> <mi>N</mi> </mrow> </math>

And is

<math> <mrow> <mi>max</mi> <mrow> <mo>(</mo> <msubsup> <mi>x</mi> <mi>pu</mi> <mi>i</mi> </msubsup> <mo>,</mo> <msubsup> <mi>x</mi> <mi>ps</mi> <mi>i</mi> </msubsup> <mo>)</mo> </mrow> <mo>&GreaterEqual;</mo> <mi>x</mi> <mo>,</mo> </mrow> </math>

If not, carrying out coding unit scale judgment 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 4, judging the coding unit scale based on template matching: coding unitThe non-normalized gradient histogram of the coded coding unit under the current depth i in the current coding frame is sampled every step length s to be matched with the non-normalized gradient histogram of the coded coding unit under the current depth i in the current coding frame, and the non-normalized gradient histogram of the coded coding unit under the current depth i in the current coding frame is found out and matched with the coding unitThe most similar set number x of coded coding units; judgment ofWhether the partition identifiers of the x coded coding units are all the same, i.e. max (x)_mu,x_ms) If not, returning to the step 3; if the partition identifiers of the x coded coding units are all unsplit, then the coding units are codedCoding 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 x coded coding units are split, the coding units are coded by splitPerforming unsplit mode coding and calculating the rate distortion cost under the corresponding coding mode, and then entering step 6; wherein x is less than or equal to N;

and a circulating judgment step:

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

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 frameJudging whether the current depth i is the depth corresponding to the coding scale 8x8, if so, further judging whether the current LCU has a coding unit needing scale judgment under the current depth, if so, updating k to k +1, returning to the step 2, and if not, 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;

Claims

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, starting coding unit scale judgment on the LCU from a depth corresponding to the largest coding scale;

step 2, calculating the kth coding unit under the current depth i in the current coding frameThe non-normalized gradient histogram of (1) determines the number of coding units of which the partition identifier coded at the current depth i in the current coding frame is partition splitAnd the number of coding units with split identifier as undividedWhether 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 iRespectively 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 unitThe partition identifier is assigned as unsplit, and then the step 5 is carried out; such as a coding unitIf the partition identifier is assigned as split, then step 6 is entered;

step 4, judging the coding unit scale based on template matching: coding unitThe 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 outThe most similar set number x of coded coding units; judging whether the segmentation identifiers of the x coded coding units are all the same, if not, returning to the step 3; if the partition identifiers of the x coded coding units are all unsplit, then the coding units are codedCoding 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 x coded coding units are split, the coding units are coded by splitPerforming split mode coding and calculating the rate distortion cost under the corresponding coding mode, and then entering the step 6; wherein x 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, and if the current depth is the depth corresponding to the coding scale 8x8, further judgingIf the current LCU has a coding unit needing scale judgment under the current depth, if so, updating k to k +1, returning to the step 2, and if not, 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. The HEVC intra-frame coding unit quick selection method of claim 1, wherein in the step 4, the coding unit is codedThe 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. 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.