Patent Description:
The present invention relates to video coding. In particular, the present invention relates to coding techniques associated with coding tree design including a binary tree partitioning process for partitioning an image area for different processing such as a coding tree unit (CTU), coding unit (CU), prediction unit (PU) and transform unit (TU).

HEVC is an advanced video coding system developed under the Joint Collaborative Team on Video Coding (JCT-VC) group of video coding experts from <NPL>). In HEVC, one slice is partitioned into multiple coding tree units (CTU). For color video data, each CTU consists of multiple coding tree blocks corresponding to the color components. In main profile, the minimum and the maximum sizes of CTU are specified by the syntax elements in the sequence parameter set (SPS) among the sizes of 8x8, 16x16, 32x32, and 64x64. For each slice, a raster scan traversing through the slice is used for processing the CTU.

The CTU is further partitioned into multiple coding units (CU) to adapt to various local characteristics. A quadtree denoted as the coding tree is used to partition the CTU into multiple CUs. Let CTU size be MxM where M is one of the values of <NUM>, <NUM>, or <NUM>. The CTU can be a single CU or can be split into four smaller units of equal sizes of M/2xM/<NUM>, which are nodes of coding tree. If units are leaf nodes of coding tree, the units become CUs. Otherwise, the quadtree splitting process can be iterated until the size for a node reaches an allowed minimum CU size specified in the SPS (sequence parameter set).

<FIG> illustrates an example of partitioning result for a CU using the quadtree partition process recursively. Every time when a block is partitioned by a quadtree, the original block is split into four sub-blocks. In the next level, the sub-block becomes a new block to be further partitioned. The partitioning process may decide not to split a block. In this case, the block is not further partitioned. The partitioning process may be terminated when a minimum quadtree block size is reached. In some cases, the partitioning process may be terminated when the partition depth reaches a maximum value. The final sub-blocks in solid lines having various block sizes as shown in <FIG> correspond to the boundaries of coding units generated from the partitioning process. This partition process results in a recursive structure representing the partition decisions as shown in <FIG> and the tree-like structure in solid lines is called a coding tree, where each leaf node corresponds to a CU (i.e., one final sub-block). The decision whether to code a picture area using inter-picture (temporal) or intra-picture (spatial) prediction is made at the CU level. In HEVC, the minimum CU size can be 8x8. Therefore, the minimum granularity for switching different prediction type is 8x8.

For prediction process (e.g. inter prediction or intra prediction), each CU is further partitioned into one or more prediction units (PUs). Coupled with the CU, the PU works as a basic representative block for sharing the prediction information. Inside one PU, the same prediction process is applied and the relevant information is transmitted to the decoder on a PU basis. A CU can be split into one, two or four PUs according to the PU splitting type. HEVC defines eight shapes for splitting a CU into one or more PUs as shown in <FIG>. Unlike the CU, the PU may be split only once. In <FIG>, the lower four partitions correspond to asymmetric partition.

After obtaining the residual block for a CU by applying the prediction process to the one or more PUs generated by the splitting process, a CU can be partitioned into transform units (TUs) according to another quadtree structure similar to the coding tree for the CU. In <FIG>, the dotted lines indicate the resulting TU boundaries by quadtree partition of each CU. The TU is a basic representative block having residual or transform coefficients for applying the integer transform and quantization. For each TU, one integer transform having the same size as the TU is applied to obtain residual coefficients. These coefficients are transmitted to the decoder after quantization on a TU basis.

The terms, coding tree block (CTB), coding block (CB), prediction block (PB), and transform block (TB) are defined to specify the <NUM>-D sample array of one color component associated with CTU, CU, PU, and TU, respectively. Thus, a CTU consists of one luma CTB, two chroma CTBs, and associated syntax elements. A similar relationship is valid for CU, PU, and TU.

The same tree partitioning is generally applied to both luma and chroma components, although exceptions may apply when certain minimum sizes are reached for chroma.

The current HEVC block partitioning only uses the quadtree based partitioning to partition a CTU to CU and to partition a CU to TU in a recursive fashion until a limit is reached. On the other hand, the current HEVC allowed up to <NUM> partition types for the PU. However, the PU partition is only performed once for each PU. Therefore, it is desirable to further improve the coding efficiency to meet the needs of ever increasing storage and transmission of video contents.

<CIT> discloses a method for improved chroma encoding and decoding. Multiple partition types are supported for intra chroma coding of a block. The multiple partition types include a set of chroma partition types and a set of luma partition types. The set of chroma partition types are different than the set of luma partition types.

A method of video coding according to the invention is defined by claim <NUM>.

A method of video encoding according to the invention is defined by claim <NUM>.

In the following, a binary tree block partitioning process is disclosed. The binary tree partitioning process can be applied to a block recursively. Every time when the binary tree partitioning process decides to partition a given block, the given block is always split into two smaller blocks, which are also referred as sub-blocks in this disclosure. Exemplary splitting types according to one embodiment are shown in <FIG>, which includes two symmetric binary tree partitioning types and four asymmetric binary tree partitioning types. The symmetric horizontal and vertical splitting types are the simplest splitting types and often achieve the good coding efficiency. Therefore, in one embodiment, only these two symmetric binary tree partitioning types are used. For a given block of size MxN, a flag can be signaled to indicate whether the block is split into two smaller blocks. If yes, a second syntax element is signaled to indicate which splitting type is used. If the horizontal splitting is used then it is split into two blocks of size MxN/<NUM>. If the vertical splitting is used, the block is split into two blocks of size M/2xN. In the embodiment shown in <FIG>, M is equal to N.

The binary tree splitting process can be iterated until the size (width or height) for a splitting block reaches a minimum allowed block size (width or height) or the binary tree partitioning process reaches a maximum allowed binary tree depth. The minimum allowed block size can be specified in high level syntax such as SPS (sequence parameter set), PPS (picture parameter set) or slice header. Since the binary tree has two splitting types (i.e., horizontal and vertical), the minimum allowed block width and height are both indicated. In some cases, the second syntax element to indicate which splitting type is used can be inferred and there is no need to signal the second syntax element. For example, if a block with a width equal to the minimum allowed block width is split, the splitting type must be horizontal partition. If vertical partition were applied, it would result in sub-blocks having block width smaller than the minimum allowed block width. Therefore, horizontal splitting is implicit when vertical splitting would result in a block width smaller than the indicated minimum. Similarly, vertical splitting is implicit when horizontal splitting would result in a block height smaller than the indicated minimum height.

<FIG> illustrates an example of block partitioning process using binary tree to partition a block into final sub-blocks and <FIG> illustrates its corresponding partitioning tree (which is a binary tree in this embodiment). In this example, the partition types consist of two types corresponding to symmetric horizontal partition and vertical partition. In each splitting (i.e., non-leaf node of the binary tree), one flag indicating the splitting type (i.e., horizontal or vertical) is signaled, where <NUM> indicates horizontal splitting and <NUM> indicates vertical splitting. Each final sub-block corresponds to one binary tree leaf node. In other words, the number of final sub-blocks in <FIG> is the same as the number of leaf nodes of the binary tree.

The first few partition steps are shown in details. In the first step, the binary tree partitioning process decides to partition the initial block (i.e., the root node for the binary tree partition) using horizontal partition, which split the block into two sub-blocks corresponding to the upper half and the lower half. The first horizontal partition is indicated by a horizontal line (410a) in <FIG>. A "<NUM>" (410b) is assigned to the root node to indicate the corresponding partition process. The partition process decides not to further split the lower half (labelled as sub-block "A" in <FIG>) and the lower half is not subject to any further split. Therefore, the sub-block "A" is a final sub-block. In the next step, the upper half is partitioned by vertical partition (420a) to split the upper half into an upper-left sub-block and upper-right sub-block. A "<NUM>" (420b) is assigned to the corresponding binary tree node to indicate the vertical partition. In <FIG>, the convention has adopted to designate a left branch for a left sub-block in case of vertical partition or an upper sub-block in case of horizontal partition. As shown in <FIG>, another vertical partition (430a) is applied to the upper-left sub-block to generate sub-blocks "B" and "C". Since sub-blocks "B" and "C" are not subject to further split, sub-blocks "B" and "C" are final sub-blocks. A "<NUM>" (430b) is assigned to the corresponding binary tree node. The sub-blocks "B" and "C" correspond to two binary tree leaf nodes as indicated in <FIG> are intended to illustrate one example of binary tree partitioning process.

The binary tree structure disclosed above can be used for partitioning a block into multiple smaller blocks (i.e., sub-blocks) such as partitioning a picture into CTUs, a slice into CTUs, a CTU into CUs, a CU into PUs, a CU into TUs, or a PU into TUs, and so on. In one embodiment, the binary tree is used for partitioning a CTU into CUs, i.e., the root node of the binary tree being a CTU and the leaf nodes of the binary tree are CUs. The leaf nodes are further processed by prediction and transform coding. In one embodiment, there is no further explicit partitioning from the CU to the PU or from the CU to the TU to simplify the coding process. Therefore, the CU is also used as the PU and the TU. In other words, the leaf nodes of the binary tree are the basic units for the prediction process and transform process. In another embodiment, the leaf nodes of the binary tree are the basic units for the prediction process (i.e., the CU is also used as the PU), however it requires another partitioning from the CU to the TU. In yet another embodiment, the leaf nodes of the binary tree are the basic units for the transform process (i.e., the CU is also used as the TU), but it requires another partitioning from the CU to the PU.

The binary tree structure is more flexible than the quadtree structure since more partition shapes can be supported. Therefore, the binary tree structure has potential to achieve improved coding efficiency. However, the encoding complexity will also be increased due to the larger number of searches needed to identify the best partition shape. In order to balance the complexity and coding efficiency, an embodiment of the present invention combines the quadtree and binary tree structure, which is called as quadtree plus binary tree (QTBT) structure in this disclosure. According to the QTBT structure, a block is firstly partitioned by a quadtree process, where the quadtree splitting can be iterated until the size for a splitting block reaches the minimum allowed quadtree leaf node size or the quadtree partitioning process reaches a maximum allowed quadtree depth. If the leaf quadtree block is not larger than the maximum allowed binary tree root node size, it can be further partitioned by a binary tree partitioning process. The binary tree splitting can be iterated until the size (width or height) for a splitting block corresponding to a binary tree node reaches the minimum allowed binary tree leaf node size (width or height) or the binary tree depth reaches the maximum allowed binary tree depth.

In the QTBT structure, the minimum allowed quadtree leaf node size, the maximum allowed binary tree root node size, the minimum allowed binary tree leaf node width and height, and the maximum allowed binary tree depth can be indicated in the high level syntax such as SPS, PPS or slice header. However, the present invention is not limited thereto.

<FIG> illustrates an example of block partitioning and <FIG> illustrates the corresponding QTBT. The solid lines indicate quadtree splitting and dotted lines indicate binary tree splitting. In each splitting (i.e., non-leaf) node of the binary tree, one flag is signaled to indicate which splitting type (i.e., horizontal or vertical) is used, where <NUM> indicates horizontal splitting and <NUM> indicates vertical splitting. For the quadtree splitting, there is no need to indicate the splitting type since it always split a block horizontally and vertically into <NUM> sub-blocks with an equal size. It is noted that a binary tree partitioning process may result in a same partitioning result as the QTBT process, the two processes are different. The binary tree partitioning process allows more flexible partitioning to better match the local characteristics of underlying video data for coding process comprising prediction process, transform process or both.

The QTBT structure as disclosed above can be used for partitioning a block into multiple smaller blocks (i.e., final sub-blocks) such as partitioning a picture into CTUs, a slice into CTUs, a CTU into CUs, a CU into PUs, a CU into TUs, or a PU into TUs, and so on. For example, the QTBT partitioning process can be applied to partition a CTU into CUs, i.e., the root node of the QTBT is a CTU and the leaf nodes of the QTBT are CUs. The CUs are further processed by prediction and transform coding. In one embodiment, there is no further explicit partitioning from the CU to the PU or from the CU to the TU to simplify the coding process. In other words, the CU is also used as the PU and the TU. Therefore, the leaf nodes of the QTBT are the basic units for the prediction process and transform process. In another embodiment, the leaf nodes of the QTBT are the basic units for the prediction process (i.e., the CU is also used as the PU), however it requires another partitioning from the CU to the TU. In yet another embodiment, the leaf nodes of the QTBT are the basic units for the transform process (i.e., the CU is also used as the TU), but it requires another partitioning from the CU to the PU, in one example, there is only one partition type for partitioning a CU to PUs, so no PU partition information is needed to be signaled to the decoder.

In one example of the QTBT partitioning process, the CTU size is set to 128x128, the minimum allowed quadtree leaf node size is set to <NUM>×<NUM>, the maximum allowed binary tree root node size is set to 64x64, the minimum allowed binary tree leaf node width and height both are set to <NUM>, and the maximum allowed binary tree depth is set to <NUM>. The quadtree partitioning process is applied to the CTU first to generate quadtree leaf nodes. The quadtree leaf nodes may have a size from 16x16 (i.e., the minimum allowed quadtree leaf node size) to <NUM>×<NUM> (i.e., the CTU size). If the leaf quadtree node is 128x128, it will not be further split by the binary tree since the size exceeds the maximum allowed binary tree root node size (i.e., 64x64). Otherwise, the leaf quadtree node will be further split by the binary tree. The quadtree leaf node is also the root node for the binary tree partitioning process having the binary tree depth as <NUM>. When the binary tree depth reaches <NUM>, which is the maximum allowed binary tree depth, it implies that no further splitting. When the binary tree node has width equal to <NUM>, it implies no further vertical splitting. Similarly, when the binary tree node has height equal to <NUM>, it implies no further horizontal splitting. The leaf nodes of the QTBT are further processed by prediction (e.g. intra-picture or inter-picture prediction) and transform coding.

In one embodiment of the present invention, the partitioning process combining the quadtree and binary tree structure firstly partitions a block by a binary tree partitioning process, where the binary tree partitioning process can be iterated until a termination criterion is met. If the size of the leaf binary tree block complies with a size constraint, it can be further partitioned by a quadtree partitioning process. The quadtree partitioning process can be iterated until another termination criterion is met. The foregoing termination criteria can be associated with the splitting block size and/or the corresponding tree depth.

In another embodiment, a block of video data is partitioned into final sub-blocks by a multi-level block partitioning process. For example, a first level block partitioning process is a quadtree partitioning process, a second level block partitioning process is a binary tree partitioning process, and a third level block partitioning process is another quadtree partitioning process. Each level of the block partitioning process will be terminated while the splitting block size and/or the corresponding tree depth met a predetermined threshold. The second partitioning processes can be applied if the leaf block generated by the first level block partitioning processes is not larger than a first maximum allowed root node size, while the third partitioning processes can be applied if the leaf block generated by the second level block partitioning processes is not larger than a second maximum allowed root node size.

When the partitioning process disclosed above (e.g. binary tree or QTBT partitioning process) is applied to color video, separate partitioning process can be applied to luma and chroma components for an I-slice. The same partitioning process can be applied to both luma and chroma components for a P and B slice except when certain minimum sizes are reached for the chroma components. In other words, in an I-slice, the luma CTB may use its QTBT partitioning process, and the two chroma CTBs may have a separate QTBT partitioning process. In another example, the two chroma CTBs may also have separate QTBT partitioning process.

The coding performance for a system incorporating an embodiment of the present invention is compared to a conventional HEVC. As mentioned before, the conventional HEVC uses quadtree partitioning process to split a CTU into one or more CUs and a CU into one or more TUs recursively until a termination condition is reached. Also the conventional HEVC uses block partitioning process including to symmetric horizontal or vertical partition to split a CU into one or more PUs. The system incorporating an embodiment of the present system uses the QTBT partitioning process to split a CTU into one or more CUs. The CUs are used for prediction process and transform process without further explicit partitioning. The performance measurement is in terms of BD-rate, which is well known performance measurement in the field of video coding. Based on various text data, the system incorporating an embodiment of the present invention has demonstrated significant improvement over the convention HEVC. The improvement for the luma (i.e., Y component) chroma component (i.e., U and V components) under the All Intra and Random Access coding configuration is over <NUM>% and <NUM>% respectively in term of BD-Rate. However, the encoding running time also increases noticeably while the decoding time only increase slightly.

<FIG> illustrates an exemplary flowchart for a decoding system using block partitioning process incorporating an embodiment of the present invention. The system receives a video bitstream in step <NUM>. The video bitstream may be retrieved from storage such as a computer memory of buffer (RAM or DRAM). The video bitstream may also be received from a processor such as a processing unit or a digital signal. A partitioning structure corresponding to a block partitioning process including a binary tree partitioning process is derived for the block of video data from the video bitstream in step <NUM>. The partitioning structure represents partitioning the block of video data into final sub-blocks, and when the binary tree partitioning process decides to apply binary tree partition to one given block, said one given block is always split into two sub-blocks. The final sub-blocks are decoded based on the video bitstream in step <NUM>. The block of video data is decoded based on the final sub-blocks decoded according to the partitioning structure derived as shown in step <NUM>.

The flowchart shown above is intended to illustrate examples of video coding incorporating an embodiment of the present invention.

The above description is presented to enable a person of ordinary skill in the art to practice the present invention as provided in the context of a particular application and its requirement. Various modifications to the described embodiments will be apparent to those with skill in the art, within the scope of the appended claims.

Claim 1:
A method of video decoding, the method comprising:
receiving (<NUM>) a video bitstream including coded data of a current slice;
determining a slice type of the current slice;
if the slice type of the current slice is I-slice:
deriving a first partitioning structure generated by using a first partitioning process for luma component of the current slice;
deriving a second partitioning structure generated by using a separate second partitioning process for chroma component of the current slice;
decoding the luma component of the current slice based on the first partitioning structure; and
decoding the chroma component of the current slice based on the second partitioning structure; and
if the slice type of the current slice is P-slice or B-slice:
deriving a third partitioning structure generated by using a third partitioning process for both of the luma component and the chroma component of the current slice; and
decoding the luma component and the chroma component of the current slice based on the third partitioning structure,
wherein each of the first partitioning process, second partitioning process and third partitioning process combines a recursive quadtree partitioning and a recursive binary tree partitioning,
wherein the recursive quadtree partitioning is performed before the recursive binary tree partitioning, and no recursive quadtree partitioning is performed after the recursive binary tree partitioning.