Patent Description:
In high efficiency video coding (HEVC), a coding unit (CU) may have variable sizes depending on video content toward achieving a desired coding efficiency. CUs typically include a luminance component, Y, and two chroma components, U and V. The size of U and V components relate to the number of samples, and can be the same or different from that of the Y component, as depends upon the video sampling format. These coding units may be split into smaller blocks for prediction or transform. In particular, each coding unit may be further partitioned into prediction units (PUs) and transform units (TUs). Prediction units (PU) can be thought of similarly to partitions described in other video coding standards, such as the H. <NUM> standard. Transform units (TU) generally refer to a block of residual data to which a transform is applied when generating transform coefficients.

Transform unit (TU) coding within high efficiency video coding (HEVC), requires complex coding steps with significant processing overhead and generally comprise several steps including: mode dependent coefficient scan (MDCS), last non-zero coefficient coding, significance map coding and non-zero coefficient level coding. These components vary at different transform unit (TU) sizes.

Accordingly, a need exists for simplifying the design of HEVC coding. The present invention fulfills that need as well as others, toward improving HEVC coding operations.

Coefficient coding for transform units (TUs) is described which enhances and harmonizes overall operation across 4x4, 8x8, 16x16 and 32x32 TUs. In a first portion, coefficient coding for TUs with up-right diagonal scans is modified, and a second portion applies a multi-level significance map coding. Both of these inventive elements apply to TUs with a size of 4x4 or 8x8.

Previously proposed arrangements are disclosed by<NPL>; and <NPL>.

Further aspects of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.

Various respective aspects and features of the invention are defined in the appended claims. In accordance with the invention, an encoding device is provided as set out in claim <NUM>, and an encoding method is provided as set out in claim <NUM>.

Embodiments of the invention will now be described with reference to the accompanying drawings, throughout which like parts are referred to by like references, and in which:
The invention will be more fully understood by reference to the following drawings which are for illustrative purposes only:.

During high efficiency video coding (HEVC), in particular HEVC test model HM5. <NUM>, coefficient coding consists of several steps which vary at different transform unit (TU) sizes.

To enhance the operation of HEVC coding, a more unified solution to coefficient coding is taught herein that harmonizes coefficient coding, such as for the up-right diagonal scan, so that all TUs with up-right diagonal scan will have the same coefficient coding.

Table <NUM> and Table <NUM> compare elements from existing coefficient coding in HEVC test model HM5. <NUM> (Table <NUM>) with changes according to the invention seen in Table <NUM>. The column marked scan is the transform coefficient scanning order, and the Multi-level Sig Map represents how Multi-level significance map coding first encodes a CG flag. It will be noted that in moving from Table <NUM> to Table <NUM> that scanning is enhanced in certain instances with 4x4 and <NUM> × <NUM> TU sizes with sub-block up-right diagonal scanning (sub-D), while additional application of multi-level significance mapping is applied.

<FIG> illustrates an example embodiment of a coding apparatus comprising an encoder <NUM> according to the invention for performing replacement of up-right diagonal scan (RDS), and for applying multi-level significance map coding (MLSMC). The invention is implemented within the entropy encoding block <NUM>, shown containing generalized RDS and MLSMC, but otherwise can rely on conventional video coding which maximizes compatibility with coding systems.

The encoder <NUM> is shown with encoding elements <NUM> executed by one or more processors <NUM>. In the example, video frame input <NUM> is shown along with reference frames <NUM> and frame output <NUM>. Inter-prediction <NUM> is depicted with motion estimation (ME) <NUM> and motion compensation (MC) <NUM>. Intra prediction <NUM> is shown and switching is depicted between inter prediction and intra prediction. A sum junction <NUM> is shown with output to a forward transform <NUM> which is performed based on the predictions to generate transform coefficients of residual data. Quantization of the transform coefficients is performed at quantization stage <NUM>, which is followed by entropy encoding <NUM>. Inverse quantization <NUM> and inverse transform <NUM> operations are shown coupled to a summing junction <NUM> followed by a filter <NUM>, such as a deblocking and / or loop filter and / or sample adaptive offset.

It should be appreciated that the encoder is shown implemented with a processing means <NUM>, such as comprising at least one processing device (e.g., CPU) <NUM> and at least one memory <NUM> for executing programming associated with the encoding. In addition, it will be appreciated that elements of the present invention can be implemented as programming stored on a media, which can be accessed for execution by a CPU for the encoder <NUM> and / or decoder <NUM>.

<FIG> illustrates an example embodiment <NUM> of a decoder, shown with process blocks <NUM> and an associated processing means <NUM>. It will be noted that the decoder is substantially a subset of the elements contained in encoder <NUM> of <FIG>, operating on reference frames <NUM> and outputting video <NUM>. The decoder blocks receive an encoded video signal <NUM> which is processed through entropy decoder <NUM> which performs decoding of the one dimensional TUs based on the mode dependent scan and decoding of the last non-zero transform position as determined by the encoder. The TUs are processed: (<NUM>) during mode dependent coefficient scanning (MDCS) with TUs that are 4x4 or 8x8 horizontal or vertical subject to horizontal or vertical scanning and the remaining TUs, including the up-right diagonal 4x4 and 8x8 TUs subject to 4x4 sub-block up-right diagonal scanning; or (<NUM>) using multi-level significance maps for both large TUs, and 4x4 and 8x8 TUs with up-right diagonal scans. During using the multi-level significance maps the programming of the decoder decodes a flag from the encoder which determines if a coefficient group is all zero or not, and selects an individual significance map if the coefficient group has any non-zero coefficients.

Following entropy decoding is inverse quantization <NUM>, inverse transform <NUM>, and summing <NUM> between the inverse transform <NUM> output and the selection between inter prediction <NUM> shown with motion compensation <NUM>, and a separate intra prediction block <NUM>. Output from summing junction <NUM> is received by filter <NUM>, which can be configured as a loop filter, a deblocking filter, sample adaptive offset or any combination thereof. It should be appreciated that the decoder can be implemented with a processing means <NUM> which comprises at least one processing device <NUM> and at least one memory <NUM> for executing programming associated with the decoding. In addition, it will be noted that elements of the present invention can be implemented as programming stored on a media, wherein said media can be accessed for execution by processing device (CPU) <NUM>.

It will be recognized that elements of the present invention <NUM> and <NUM> are implemented for execution by a processing means <NUM> and <NUM>, such as in response to programming resident in memory <NUM> and <NUM> which is executable on computer processor (CPU) <NUM> and <NUM>. In addition, it will be appreciated that elements of the present invention can be implemented as programming stored on a media, wherein said media can be accessed for execution by CPU <NUM> and <NUM>.

It should be appreciated that the programming is executable from the memory which is a tangible (physical) computer readable media that is non-transitory in that it does not merely constitute a transitory propagating signal, but is actually capable of retaining programming, such as within any desired form and number of static or dynamic memory devices. These memory devices need not be implemented to maintain data under all conditions (e.g., power fail) to be considered herein as non-transitory media.

<FIG> illustrates general TU coding steps in an encoder which are followed by both conventional TU coding and TU coding according to the present invention. These general steps comprise converting two dimensional (2D) TU into a one dimensional (1D) TU based on a mode dependent coefficient scan (MDCS) <NUM>. The last non-zero coefficient position is identified and encoded <NUM>. A significance map coding <NUM> encodes whether a coefficient is zero or non-zero. Then the values of non-zero coefficients are encoded <NUM> to complete the TU coding.

<FIG> illustrates general TU coding steps in a decoder which are followed by both conventional TU coding and TU coding according to the present invention. These general steps comprise converting two dimensional (2D) TU into a one dimensional (1D) TU based on a mode dependent coefficient scan (MDCS) <NUM>. The last non-zero coefficient position is decoded <NUM>. A significance map coding <NUM> decodes whether a coefficient is zero or non-zero. Then the values of non-zero coefficients are decoded <NUM> to complete the TU coding in the decoder.

<FIG> depicts a conventional method of performing mode dependent coefficient scan (MDCS). TU information (e.g., size, prediction mode) is received <NUM> with and large TUs are detected in step <NUM>, with TUs that are not 4x4 or 8x8 being processed with 4x4 sub-block up-right diagonal scanning <NUM>. The 4x4 and 8x8 TUs are checked at step <NUM>, and those that are horizontal or vertical are processed at step <NUM> using horizontal or vertical scanning. For the 4x4 and 8x8 TUs which are not horizontal or vertical, processing moves from block <NUM>, to block <NUM> where a check is made to detect 4x4 TUs. The 4x4 TUs are then processed by a 4x4 up-right diagonal scan <NUM>, with 8x8 TUs processed by 8x8 up-right diagonal scanning <NUM>.

<FIG> illustrates an example embodiment of mode dependent coefficient scanning (MDCS) according to the invention. TU information is received <NUM> with large TUs detected in step <NUM>, and TUs that are not 4x4 or 8x8 being processed with 4x4 sub-block up-right diagonal scanning <NUM>. The 4x4 and 8x8 TUs are checked at step <NUM>, and those that are horizontal or vertical are processed at step <NUM> using horizontal or vertical scanning. For the remaining 4x4 and 8x8 non-horizontal, non-vertical TUs, 4x4 sub-block up-right diagonal scanning is also performed as per block <NUM>.

<FIG> illustrate scanning patterns according to the invention. In <FIG> a large TU is seen having 16x16 coefficients, which is subject to sub-block partitioning and up-right diagonal scanning. The figure shows that coefficients are scanned within each 4x4 sub-block, and then scanning moves to the next 4x4 sub-block (i.e., CG). For the sake of simplicity (and space) the scanning pattern within each of the 4x4 sub-blocks is not shown in <FIG>. In <FIG> an up-right diagonal scan is shown on a 4x4 up-right diagonal TU. It will be noted that 4x4 up-right diagonal scanning is performed on these TUs both before and after the inventive changes seen in <FIG>. In <FIG> is seen a conventional 8x8 up-right diagonal scan, which is replaced according to the invention with 4x4 up-right diagonal sub-block scanning as seen in <FIG>. In <FIG>, MDCS starts from the top-left corner of a TU and traverses through to the bottom-right corner. In the encoding processes <NUM> and <NUM> of <FIG> and the decoding processes <NUM> and <NUM> of <FIG>, the processing order is the reverse of MDCS shown in <FIG>.

<FIG> depicts conventional significance map processing in an encoder. TU information <NUM> is received and for <NUM>×<NUM> and 8x8 TUs, as determined in step <NUM>, a single level significance map encoding <NUM> is performed. Otherwise, for TUs which are not 4x4 or 8x8, then multi-level significance map encoding <NUM> is performed. The multi-level significance map encoding is shown comprising checking <NUM> if there is any more coefficient groups (CG) starting from the last nonzero CG. If no more CG, then multi-level significance map encoding is completed, and execution is seen jumping past step <NUM>. If there are more CG, then a check is made to see if we are between the first and last CGs at step <NUM>. It will be noted that: (<NUM>) flagging need not be sent for the all zero CG after the last nonzero CG (the CG containing the last nonzero coefficient), as it can be presumed these will be all zeros and CG flag is set to zero; (<NUM>) no flagging is needed the last nonzero CG, as it can be deduced that this has non zero coefficients and CG flag is set to one, and finally (<NUM>) flagging is not needed for the first CG, as in almost all cases this CG has nonzero coefficients and CG flag is set to one. Thus, if between the first and last CG as determined in step <NUM>, then (yes) flagging <NUM> is performed with CG flag encoded. If not between the first and last CGs, then CG flag is set to one <NUM> and the flagging step is bypassed and execution proceeds to the CG flag check <NUM>. In step <NUM> it is checked whether the CG flag is equal to one or not, with a return to step <NUM> if the CG is equal to zero. It will be noted that each 4x4 sub-block comprises a coefficient group (CG). If the CG flag is equal to one, as determined at step <NUM>, then an individual significance map encoding is performed <NUM>.

<FIG> depicts conventional significance map processing in a decoder. TU information <NUM> is received and for <NUM>×<NUM> and 8x8 TUs, as determined in step <NUM>, a single level significance map decoding <NUM> is performed. Otherwise, for TUs which are not 4x4 or 8x8, then multi-level significance map decoding <NUM> is performed. The multi-level significance map decoding is shown comprising checking <NUM> if there is any more coefficient groups (CG) starting from the last nonzero CG. If no more CG, then multi-level significance map decoding is completed, and execution is seen jumping past step <NUM>. If there are more CG, then a check is made to see if we are between the first and last CGs at step <NUM>. It will be noted that: (<NUM>) flagging need not be sent for the all zero CG after the last nonzero CG (the CG containing the last nonzero coefficient), as it can be presumed these will be all zeros and CG flag is set to zero; (<NUM>) no flagging is needed the last nonzero CG, as it can be deduced that this has non zero coefficients and CG flag is set to one, and finally (<NUM>) flagging is not needed for the first CG, as in almost all cases this CG has nonzero coefficients and CG flag is set to one. Thus, if between the first and last CG as determined in step <NUM>, then (yes) flagging <NUM> is performed. If not between the first and last CGs, then the CG flag is set to one <NUM> and the flagging step is bypassed and execution proceeds to the CG flag check <NUM>. In step <NUM> it is checked whether the CG flag is equal to one or not, with a return to step <NUM> if the CG is equal to zero. It will be noted that each 4x4 sub-block comprises a coefficient group (CG). If the CG flag is equal to one, as determined at step <NUM>, then an individual significance map decoding is performed <NUM>.

<FIG> illustrates significance map processing in an encoder according to an element of the present invention. TU information <NUM> is received and if it is a 4x4 or 8x8 TU with horizontal or vertical scan, as determined in step <NUM>, then a single level significance map encoding <NUM> is performed. Otherwise, for large TUs, and 4x4 and 8x8 up-right diagonal scan TUs, multi-level significance map encoding <NUM> is performed. The multi-level significant map encoding is shown comprising checking <NUM> if there is any more coefficient groups (CG). If no more CG, then multi-level significance map encoding is completed, and execution is seen jumping past step <NUM>. If there are more CG, then a check is made to see if we are between the first and last CGs at step <NUM>. It will be noted that: (<NUM>) flagging need not be sent for the all zero CG after the last nonzero CG (the CG containing the last nonzero coefficient), as it can be presumed these will be all zeros and CG flag is set to one; (<NUM>) no flagging is needed for the last nonzero CG, as it can be deduced that this has non zero coefficients, and finally (<NUM>) flagging is not needed for the first CG, as in almost all cases this CG has nonzero coefficients and CG flag is set to one. Thus, if between the first and last CG as determined in step <NUM>, then (yes) flagging is performed <NUM>. If not between the first and last CGs, then the CG flag is set to one <NUM> and the flagging step is bypassed with execution advancing to the CG flag check <NUM>. In step <NUM> it is checked whether CG flag is equal to one or not, with a return to step <NUM> if the CG is equal to zero. It will be noted that each 4x4 sub-block comprises a coefficient group (CG). If the CG is equal to one, as determined at step <NUM>, then an individual significance map encoding is performed <NUM>.

<FIG> illustrates significance map processing in a decoder according to an element of the present invention. TU information <NUM> is received and if it is a 4x4 or 8x8 TU with horizontal or vertical scan, as determined in step <NUM>, then a single level significance map decoding <NUM> is performed. Otherwise, for large TUs, and 4x4 and 8x8 up-right diagonal scan TUs, multi-level significance map decoding <NUM> is performed. The multi-level significant map decoding is shown comprising checking <NUM> if there is any more coefficient groups (CG). If no more CG, then multi-level significance map decoding is completed, and execution is seen jumping past step <NUM>. If there are more CG, then a check is made to see if we are between the first and last CGs at step <NUM>. It will be noted that: (<NUM>) flagging need not be sent for the all zero CG after the last nonzero CG (the CG containing the last nonzero coefficient), as it can be presumed these will be all zeros and CG flag is set to one; (<NUM>) no flagging is needed for the last nonzero CG, as it can be deduced that this has non zero coefficients, and finally (<NUM>) flagging is not needed for the first CG, as in almost all cases this CG has nonzero coefficients and CG flag is set to one. Thus, if between the first and last CG as determined in step <NUM>, then (yes) flagging is performed <NUM> with CG flag encoded. If not between the first and last CGs, then the CG flag is set to one <NUM> with the flagging step bypassed and execution proceeding to the CG flag check <NUM>. In step <NUM> it is checked whether CG flag is equal to one or not, with a return to step <NUM> if the CG is equal to zero. It will be noted that each 4x4 sub-block comprises a coefficient group (CG). If the CG is equal to one, as determined at step <NUM>, then an individual significance map decoding is performed <NUM>.

The following summarizes moving from <FIG> (encoder) and <FIG> (decoder) to the inventive teachings of <FIG> (encoder) and <FIG> (decoder). In the existing significance mapping, all 4x4 and 8x8 TUs are subject to single level significance mapping, while only larger TUs (16x16 and 32x32) are processed by multi-level significance mapping. However, as seen in <FIG> and <FIG>, 4x4 and 8x8 TUs with horizontal or vertical scans are processed with a single level significance map, while 4x4 and 8x8 TUs with up-right diagonal scans along with the large TUs (16x16 and 32x32) are processed using the multi-level significance mapping.

These solutions are summarized in the characteristics of Table <NUM>. It can be seen in the table that certain 4x4 and 8x8 TUs are processed differently than before with sub-block up-right diagonal (Sub-D) scanning. The inventive technique was implemented into HEVC HM5. <NUM>, with a simulation conducted under common test conditions.

Embodiments of the present invention may be described with reference to flowchart illustrations of methods and systems according to embodiments of the invention, and / or algorithms, formulae, or other computational depictions, which may also be implemented as computer program products. In this regard, each block or step of a flowchart, and combinations of blocks (and / or steps) in a flowchart, algorithm, formula, or computational depiction can be implemented by various means, such as hardware, firmware, and / or software including one or more computer program instructions embodied in computer-readable program code logic. As will be appreciated, any such computer program instructions may be loaded onto a computer, including without limitation a general purpose computer or special purpose computer, or other programmable processing apparatus to produce a machine, such that the computer program instructions which execute on the computer or other programmable processing apparatus create means for implementing the functions specified in the block(s) of the flowchart(s).

Accordingly, blocks of the flowcharts, algorithms, formulae, or computational depictions support combinations of means for performing the specified functions, combinations of steps for performing the specified functions, and computer program instructions, such as embodied in computer-readable program code logic means, for performing the specified functions. It will also be understood that each block of the flowchart illustrations, algorithms, formulae, or computational depictions and combinations thereof described herein, can be implemented by special purpose hardware-based computer systems which perform the specified functions or steps, or combinations of special purpose hardware and computer-readable program code logic means.

Furthermore, these computer program instructions, such as embodied in computer-readable program code logic, may also be stored in a computer-readable memory that can direct a computer or other programmable processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the block(s) of the flowchart(s). The computer program instructions may also be loaded onto a computer or other programmable processing apparatus to cause a series of operational steps to be performed on the computer or other programmable processing apparatus to produce a computer-implemented process such that the instructions which execute on the computer or other programmable processing apparatus provide steps for implementing the functions specified in the block(s) of the flowchart(s), algorithm(s), formula(e), or computational depiction(s).

Claim 1:
A encoding device, comprising:
circuitry configured to:
apply a diagonal scan to a plurality of transform blocks including a first transform and a second transform block, of a plurality of variable block sizes, in dependence upon a condition that the plurality of transform blocks are not horizontal or vertical scan transform blocks, wherein the plurality of variable block sizes includes <NUM>×<NUM>, <NUM>×<NUM>, <NUM>×<NUM>, and <NUM>×<NUM>,
wherein the first transform block is of a first block size of the plurality of variable block sizes and the second transform block is of a second block size of the plurality of variable block sizes, and
wherein <NUM>×<NUM> sub-blocks of both the first transform block and the second transform block are diagonally scanned, and the diagonal scan is applied inside each of the <NUM>×<NUM> sub-blocks; and
apply the same multi-level significance map encoding to the first transform block of the first block size and the second transform block of the second block size.