HK1226572B - Multiple sign bit hiding within a transform unit - Google Patents

Description

Multiple sign bit hiding within transform units

The present application is a divisional application of Chinese patent application No. 201310019680.7 filed on January 18, 2013, entitled “Multiple-sign bit hiding within a transform unit”.

Copyright Notice

A portion of the disclosure of this document and accompanying material contains material for which copyright is claimed. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office files or records, but otherwise reserves all other copyright rights whatsoever.

Technical Field

The present application relates generally to data compression, and more particularly to methods and apparatus for sign bit hiding when encoding and decoding residual video data.

Background Art

Data compression occurs in many contexts. Data compression is very commonly used in communications and computer networking to efficiently store, transmit and copy information. It finds particular application in the encoding of images, audio and video. Video presents considerable challenges for data compression due to the large amount of data required for each video frame and the speed at which encoding and decoding often need to occur. The current state-of-the-art in video coding is the ITU-T H.264/AVC video coding standard. This standard defines a number of different profiles for different applications, including a main profile, a baseline profile, and so on. A next generation video coding standard called "High Efficiency Video Coding (HEVC)" is currently under development through a joint initiative of MPEG-ITU.

Several standards exist for encoding and decoding images and video, including H.264, which uses a block-based coding process. In these processes, images or frames are divided into blocks, typically 4×4 or 8×8, and the blocks are spectrally transformed into coefficients, quantized, and entropy coded. In many cases, the transformed data is not actual pixel data, but rather residual data after a prediction operation. Prediction can be either intra-frame, i.e., block-by-block within a frame/image; or inter-frame, i.e., between frames (also known as motion prediction). MPEG-H is expected to incorporate these features.

When performing a spectral transform on the residual data, many of these standards specify the use of a discrete cosine transform (DCT) or some variation thereof. The resulting DCT coefficients are then quantized using a quantizer to produce quantized transform domain coefficients or indices.

The block or matrix of quantized transform-domain coefficients (sometimes called a "transform unit") is then entropy coded using a specific context model. In H.264/AVC and in current development work for MPEG-H, the quantized transform coefficients are encoded by: (a) encoding the last significant coefficient position, which indicates the position of the last non-zero coefficient in the transform unit; (b) encoding a significance map, which indicates the positions in the transform unit that contain non-zero coefficients (except the last significant coefficient position); (c) encoding the magnitudes of the non-zero coefficients; and (d) encoding the signs of the non-zero coefficients. Coding the quantized transform coefficients often accounts for 30-80% of the coded data in the bitstream.

Transform units are typically N x N. Common sizes include 4 x 4, 8 x 8, 16 x 16, and 32 x 32, but other sizes are possible, including non-square sizes such as 8 x 32 or 32 x 8 in some embodiments. The sign of each non-zero coefficient in the block is encoded using one sign bit per non-zero coefficient.

Summary of the Invention

This application describes methods and encoders/decoders for encoding and decoding video data using sign bit hiding. In some embodiments, the encoder and decoder may use multi-level significance maps to encode significant coefficient flags. Using parity checking techniques, for each coefficient subset in a transform unit (TU), the sign bit of at least one coefficient may be hidden. In some cases, the coefficient subsets correspond to coefficient groups used in multi-level maps, such as those used in significance map encoding and decoding. In at least one case, multi-level maps are used with larger transform units (TUs), such as 16×16 and 32×32 TUs. In some cases, multi-level maps are used with 8×8 TUs, non-square TUs, and other TU sizes. Sign bit hiding techniques may be used for coefficient subsets that contain more than a threshold number of non-zero coefficients. In some embodiments, subset-based sign bit hiding techniques may be used for TUs even if they do not use multi-level significance map encoding, particularly when the encoding of the significant coefficients of the TUs is implemented modularly for the subsets of significant coefficient flags.

In one aspect, the present application describes a method for decoding a bitstream of encoded video by reconstructing coefficients of a transform unit, the bitstream encoding two or more sets of sign bits for the transform unit, each set corresponding to a respective set of coefficients for the transform unit, wherein each sign bit indicates a sign of a corresponding non-zero coefficient within the respective set. The method includes: for each of the two or more sets of sign bits, summing the absolute values of the coefficients in the respective set corresponding to the sign bit set to obtain a parity value; and assigning a sign to one of the coefficients in the respective set based on whether the parity value is even or odd.

In another aspect, the present application describes a method for encoding a bitstream of video by encoding sign bits of coefficients of a transform unit. The method includes: for each of two or more sets of coefficients of the transform unit, summing the absolute values of the coefficients in the set to obtain a parity value; determining that the sign of one of the coefficients in the set does not correspond to the parity value; and adjusting the levels of the coefficients in the set by 1 to change the parity value to correspond to the sign of the one of the coefficients.

In yet another aspect, the present application describes encoders and decoders configured to perform such encoding and decoding methods.

In yet another aspect, the present application describes a non-transitory computer-readable medium storing computer-executable program instructions that, when executed, configure a processor to perform the described encoding and/or decoding methods.

Those skilled in the art will understand other aspects and features of the present application by reading the following description of examples in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Reference is now made to the accompanying drawings, which illustrate example embodiments of the present application, in which:

FIG1 shows, in block diagram form, an encoder for encoding a video;

FIG2 shows, in block diagram form, a decoder for decoding a video;

FIG3 shows an example of a multi-level scanning order for a 16×16 transform unit.

FIG4 shows an example 16×16 transform unit partitioned into coefficient groups numbered in reverse group-level scan order;

FIG5 shows an example of a transform unit in which a group of four coefficient groups is formed for sign bit hiding;

FIG6 shows another example of coefficient grouping for sign bit hiding;

FIG7 shows yet another example of coefficient grouping for sign bit hiding;

FIG8 shows an example of dynamically forming a coefficient set for sign bit hiding;

FIG9 shows an example process of sign bit hiding in the form of a flow chart;

FIG10 shows a simplified block diagram of an example embodiment of an encoder; and

FIG11 shows a simplified block diagram of an example embodiment of a decoder.

Like reference numerals may have been used in different drawings to identify similar components.

DETAILED DESCRIPTION

In the following description, some example embodiments are described with reference to the H.264 standard for video coding and/or the developing MPEG-H standard. Those skilled in the art will appreciate that this application is not limited to H.264 or MPEG-H but is applicable to other video coding/decoding standards, including potential future standards, multi-view coding standards, scalable video coding standards, and reconfigurable video coding standards.

In the following description, when referring to a video or image, the terms frame, picture, slice, tile, and slice group are used somewhat interchangeably. Those skilled in the art will recognize that, in the context of the H.264 standard, a frame may contain one or more slices. They will also recognize that, depending on the specific requirements or terminology of the applicable image or video coding standard, some encoding/decoding operations may be performed on a frame-by-frame basis, some encoding/decoding operations may be performed on a slice-by-slice basis, some encoding/decoding operations may be performed on a picture-by-picture basis, some encoding/decoding operations may be performed on a tile-by-tile basis, and some encoding/decoding operations may be performed on a slice-by-slice basis, as appropriate. In any particular embodiment, the applicable image or video coding standard may determine whether the operations described below are performed with respect to frames and/or slices and/or pictures and/or tiles and/or slice groups. Accordingly, those skilled in the art will understand, based on this disclosure, whether specific operations or processes described herein and specific references to frames, slices, pictures, tiles, or slice groups apply to frames, slices, pictures, tiles, or slice groups, or some or all of these, for a given embodiment. This also applies to transform units, coding units, groups of coding units, etc., as will become apparent from the following description.

The present application describes example processes and apparatus for encoding and decoding the sign bits of non-zero coefficients of a transform unit. The non-zero coefficients are identified by a significance map. A significance map is a block, matrix, group, or set of flags that are mapped to or correspond to a transform unit or a defined coefficient unit (e.g., several transform units, a portion of a transform unit, or a coding unit). Each flag indicates whether the corresponding position in the transform unit or the specified unit contains a non-zero coefficient. In existing standards, these flags may be referred to as significant coefficient flags. In existing standards, there is one flag for each coefficient in scan order, from the DC coefficient to the last significant coefficient, and the flag is a bit that is 0 if the corresponding coefficient is 0, and is set to 1 if the corresponding coefficient is not 0. The term "significance map" as used herein is intended to refer to a matrix or ordered set of significant coefficient flags for a transform unit (as will be understood from the description below) or a defined coefficient unit (as will be clear from the context of the present application).

Should be understood that, according to the following description, multi-level coding and decoding structure can be applied in specific situations, and those situations can be determined according to auxiliary information such as video content type (graphics, pictures, or headers identified in normal video or sequence). For example, two levels can be used for normal video, and three levels (which are usually more sparse) can be used for graphics. Another possibility is to provide a mark in one of the sequence, picture or header, and this mark indicates whether this structure has one, two or three levels, thereby allowing the encoder to flexibly select the most suitable structure for this content. In another embodiment, the mark can represent the content type, which will be associated with the number of levels. For example, the content type "image" can be characterized by three levels.

Reference is now made to FIG1 , which shows in block diagram form an encoder 10 for encoding a video. Reference is also made to FIG2 , which shows a block diagram of a decoder 50 for decoding a video. It will be appreciated that both the encoder 10 and the decoder 50 described herein can be implemented on a dedicated or general-purpose computing device (comprising one or more processing units and memory). The operations performed by the encoder 10 or decoder 50 can be implemented, for example, by a dedicated integrated circuit or by stored program instructions executable by a general-purpose processor, as the case may be. The device may include additional software, including, for example, an operating system for controlling basic device functions. With respect to the following description, those skilled in the art will recognize the range of devices and platforms in which the encoder 10 or decoder 50 can be implemented.

The encoder 10 receives a video source 12 and generates an encoded bitstream 14. The decoder 50 receives the encoded bitstream 14 and outputs decoded video frames 16. The encoder 10 and decoder 50 can be configured to operate in accordance with a plurality of video compression standards. For example, the encoder 10 and decoder 50 can conform to H.264/AVC. In other embodiments, the encoder 10 and decoder 50 can conform to other video compression standards, including evolutions of the H.264/AVC standard such as MPEG-H.

The encoder 10 includes a spatial predictor 21, a coding mode selector 20, a transform processor 22, a quantizer 24, and an entropy encoder 24. Those skilled in the art will appreciate that the coding mode selector 20 determines the appropriate coding mode for the video source, such as whether the target frame/slice is of I, P, or B type, and whether a particular coding unit (e.g., macroblock, coding unit, etc.) within the frame/slice is inter- or intra-coded. The transform processor 22 performs a transform on the spatial domain data. Specifically, the transform processor 22 applies a block-based transform to convert the spatial domain data into spectral components. For example, in many embodiments, a discrete cosine transform (DCT) is used. In some embodiments, other transforms, such as discrete sine transforms, may be used. Depending on the size of the macroblock or coding unit, this block-based transform is performed on a coding unit, macroblock, or sub-block basis. In the H.264 standard, for example, a typical 16×16 macroblock contains 16 4×4 transform blocks, and the DCT process is performed on the 4×4 blocks. In some cases, the transform blocks may be 8×8, meaning there are four transform blocks per macroblock. In other cases, the transform blocks may be of other sizes.In some cases, a 16x16 macroblock may comprise a non-overlapping combination of 4x4 and 8x8 transform blocks.

Applying a block-based transform to a block of pixel data results in a set of transform domain coefficients. In this context, a "set" is an ordered set in which a coefficient has a coefficient position. In some examples, a set of transform domain coefficients can be considered a "block" or matrix of coefficients. In the description herein, the phrases "set of transform domain coefficients" or "block of transform domain coefficients" are used interchangeably and are used to refer to an ordered set of transform domain coefficients.

The set of transform domain coefficients is quantized by a quantizer 24. The quantized coefficients and associated information are then encoded by an entropy encoder 26.

A block or matrix of quantized transform domain coefficients may be referred to herein as a “transform unit” (TU). In some cases, a TU may be non-square, such as a non-square quadrature transform (NSQT).

Intra-coded frames/slices (i.e., Type I) are encoded without reference to other frames/slices. In other words, they do not employ temporal prediction. However, intra-coded frames rely on spatial prediction within the frame/slice, as illustrated in FIG1 by the spatial predictor 21. That is, when encoding a particular block, the data in the block can be compared with the data of neighboring pixels within the block that have already been encoded for that frame/slice. Using a prediction algorithm, the source data for the block can be converted into residual data. The transform processor 22 then encodes the residual data. For example, H.264 specifies 9 spatial prediction modes for 4×4 transform blocks. In some embodiments, each of these 9 modes can be used to process the block independently, and then rate-distortion optimization is used to select the best mode.

The H.264 standard also specifies the use of motion prediction/compensation to exploit temporal prediction. Accordingly, encoder 10 has a feedback loop comprising a dequantizer 28, an inverse transform processor 30, and a deblocking processor 32. Deblocking processor 32 may include a deblocking processor and a filtering processor. These units mirror the decoding process implemented by decoder 50 to reproduce frames/slices. Frame memory 34 is used to store reproduced frames. In this manner, motion prediction is based on what the reconstructed frame is at decoder 50, rather than on the original frame, which may differ from the reconstructed frame due to the lossy compression involved in encoding/decoding. Motion predictor 36 uses the frames/slices stored in frame memory 34 as source frames/slices to compare with the current frame to identify similar blocks. Accordingly, for macroblocks or coding units to which motion prediction is applied, the "source data" encoded by transform processor 22 is the residual data from the motion prediction process. For example, this may include information about a reference frame, a spatial permutation or "motion vector," and residual pixel data representing the difference (if any) between the reference block and the current block. Information about reference frames and/or motion vectors may not be processed by the transform processor 22 and/or the quantizer 24, but may be provided to the entropy encoder 26 and encoded as part of the bitstream along with the quantized coefficients.

Those skilled in the art will recognize the details and possible variations for implementing a video encoder.

Decoder 50 includes an entropy decoder 52, a dequantizer 54, an inverse transform processor 56, a spatial compensator 57, and a deblocking processor 60. Deblocking processor 60 may include deblocking and filtering processors. Frame buffer 58 provides reconstructed frames for use by motion compensator 62, which applies motion compensation. Spatial compensator 57 represents the operation of recovering the video data of a particular intra-frame coded block based on previously decoded blocks.

The entropy decoder 52 receives and decodes the bitstream 14 to recover the quantized coefficients. During the entropy decoding process, auxiliary information may also be recovered. If applicable, some of this auxiliary information may be provided to the motion compensation loop for use in motion compensation. For example, the entropy decoder 52 may recover motion vectors and/or reference frame information for inter-coded macroblocks.

The dequantizer 54 then dequantizes the quantized coefficients to produce transform domain coefficients, which are then inversely transformed by the inverse transform processor 56 to reconstruct the "video data." It will be appreciated that in some cases, such as for intra-coded macroblocks or coding units, the reconstructed "video data" is residual data used for spatial compensation relative to a previously decoded block within the frame. A spatial compensator 57 generates video data based on the residual data and pixel data from the previously decoded block. In other cases, such as for inter-coded macroblocks or coding units, the reconstructed "video data" from the inverse transform processor 56 is residual data used for motion compensation relative to a reference block from a different frame. Both spatial and motion compensation may be referred to herein as "prediction operations."

The motion compensator 62 locates a reference block within the frame buffer 58 that is specific to the coded macroblock or coding unit for the particular inter. The motion compensator 62 does this based on the reference frame information and the motion vectors specific to the inter-coded macroblock or coding unit. The motion compensator 62 then provides the reference block pixel data to be combined with the residual data to obtain the reconstructed video data for that coding unit/macroblock.

A deblocking/filtering process may then be applied to the reconstructed frame/slice, as shown by a deblocking processor 60. After deblocking/filtering, the frame/slice is output as a decoded video frame 16, for example, to be displayed on a display device. It will be appreciated that a video playback machine (e.g., a computer, set-top box, DVD or Blu-ray player, and/or mobile handheld device) may buffer the decoded frame in memory before displaying it on an output device.

It is expected that MPEG-H compliant encoders and decoders will have many of these same or similar features.

Encoding and decoding of quantized transform domain coefficients

As noted above, entropy encoding of a block or set of quantized transform-domain coefficients includes encoding a significance map (e.g., a set of significant-coefficient flags) for the block or set of quantized transform-domain coefficients. The significance map is a binary map of the block that indicates where non-zero coefficients occur (from the DC position to the last significant coefficient position). The significance map can be converted into a vector according to a scan order (which can be vertical, horizontal, diagonal, zigzag, or any other scan order specified by the applicable coding standard). The scan is typically performed in "reverse" order, starting with the last significant coefficient and working backwards through the significance map in the reverse direction until the significant-coefficient flag at the upper left corner [0, 0] is reached. In this description, the term "scan order" is intended to refer to the order in which flags, coefficients, or groups are processed (as appropriate), and may include an order colloquially referred to as "reverse scan order."

Each significant-coefficient flag is then entropy coded using an applicable context-adaptive coding scheme. For example, in many applications, a context-adaptive binary arithmetic coding (CABAC) scheme may be used.

With 16x16 and 32x32 significance maps, the context of a significant-coefficient flag is (in most cases) based on the values of neighboring significant-coefficient flags. Among the contexts used for 16x16 and 32x32 significance maps, there are specific contexts dedicated to bit position [0, 0] and (in some example implementations) to neighboring bit positions, but the majority of significant-coefficient flags take one of four or five contexts based on the cumulative values of neighboring significant-coefficient flags. In these examples, determining the correct context for a significant-coefficient flag depends on determining and summing the values of the significant-coefficient flags at neighboring positions (typically five positions, but in some examples, there could be more or fewer positions).

The significant coefficient levels of those non-zero coefficients can then be encoded. In one example implementation, the levels can be encoded by first encoding a map of those non-zero coefficients whose absolute value level is greater than 1. Then, another map of those non-zero coefficients whose level is greater than 2 can be encoded. Then, the value or level of any coefficient whose absolute value is greater than 2 is encoded. In some cases, the encoded value can be the actual value minus 3.

The signs of nonzero coefficients are also encoded. Each nonzero coefficient has a sign bit that indicates whether the level of the nonzero coefficient is negative or positive. A proposal has been made to hide the sign bit of the first coefficient in a transform unit: Clare, Gordon, et al., "Sign Data Hiding," JCTVC-G271, ^7th Meeting, Geneva, November 21-30, 2011. Under this proposal, the sign of the first coefficient in a transform unit is encoded by a parity check of the sum of the quantized coefficients in the transform unit. If this parity check does not correspond to the actual sign of the first coefficient, the encoder must adjust the level of one of the coefficients up or down by 1 in order to adjust the parity check. RDOQ is used to determine which coefficient to adjust and in which direction.

Previous work has focused on the use of multi-level significance maps. Referring now to FIG. 3 , FIG. 3 shows a 16x16 transform unit 100 illustrated in a multi-level diagonal scan order. The transform unit 100 is partitioned into 16 consecutive 4x4 coefficient groups or "significant-coefficient flag sets." Within each coefficient group, a diagonal scan order is applied within the group, rather than across the entire transform unit 600. The sets or coefficient groups themselves are processed in a scan order, which in this example implementation is also a diagonal scan order. It should be noted that the scan order in this example is shown as a "reverse" scan order; that is, the scan order is shown starting from the lower-right coefficient group and proceeding diagonally from the lower left to the upper-left coefficient group. In some implementations, the same scan order can be defined in the other direction; that is, proceeding diagonally from the upper right, and when applied during encoding or decoding, can be applied in a "reverse" scan order.

The use of multi-level significance maps involves encoding a significance map at level L1 or higher that indicates which coefficient groups are expected to contain non-zero significant-coefficient flags and which coefficient groups contain all-zero significant-coefficient flags. The significant-coefficient flags of coefficient groups that are expected to contain non-zero significant-coefficient flags are encoded, while coefficient groups containing all-zero significant-coefficient flags are not encoded (unless they are encoded due to the special case exception that they are assumed to contain at least one non-zero significant-coefficient flag). Each coefficient group has a significant-coefficient-group flag (unless special cases apply where a coefficient group has a flag with an assumed value, such as the group containing the last significant coefficient, the group to the top left, etc.).

For encoding and decoding, the use of multi-level significance maps facilitates modular processing of residual data.

Larger TUs provide the opportunity to hide multiple sign bits. The TU can be split or divided into sets of non-zero coefficients, and for each set of non-zero coefficients, the sign bit can be hidden using a parity check of the sum of the non-zero coefficients in the set. In one embodiment, the non-zero coefficient sets can be made to correspond to the coefficient groups defined for the multi-level significance map.

Regardless of the data type, a single threshold can be used to determine whether to hide the sign bit for a particular set of non-zero coefficients. In one example, the threshold test is based on the number of coefficients between the first and last non-zero coefficients in the set. That is, whether the number of coefficients between the first and last non-zero coefficients in the set is at least equal to a threshold number. In another example, the test can be based on whether the number of non-zero coefficients in the set is at least equal to a threshold number. In yet another embodiment, the test can be based on whether the sum of the absolute values of the non-zero coefficients in the set exceeds a threshold. In yet another embodiment, a combination of these tests can be applied; that is, there must be at least a minimum number of coefficients in the set and the cumulative absolute value of the coefficients must exceed a threshold. Variations of these threshold tests can also be used.

Reference is now made to Figure 4, which shows an example 16x16 transform unit 120. The transform unit 120 is partitioned into 4x4 coefficient groups, i.e., 16 coefficient sets. These coefficient groups are numbered 1, 2, 3...16 in the order in which they are processed (e.g., inverse diagonal scan order).

In a first embodiment, each coefficient group is a collection of coefficients for sign bit hiding purposes. That is, each coefficient group is tested against a threshold to determine whether the coefficient group is suitable for sign bit hiding. As mentioned above, the test can be that the coefficient group contains at least a minimum number of coefficients between the first non-zero coefficient and the last non-zero coefficient in the coefficient group.

In a second embodiment, the coefficient sets used for sign bit hiding are formed by grouping coefficient groups. FIG5 shows a 16×16 TU 140, on which an example grouping of coefficient groups into four coefficient sets is shown. In this example, each coefficient set used for sign bit hiding purposes contains four coefficient groups. The four coefficient groups in each set are consecutive groups in scan order. For example, the first coefficient set 142 contains coefficient groups 16, 15, 14, and 13. The second coefficient set 144 contains coefficient groups 12, 11, 10, and 9. The third coefficient set 146 contains coefficient groups 8, 7, 6, and 5. Finally, the fourth coefficient set 148 contains coefficient groups 4, 3, 2, and 1. In this embodiment, the sign bit can be hidden for each coefficient set. That is, up to 4 sign bits can be hidden for each TU 140.

For each coefficient set 142, 144, 146, and 148, the number of coefficients between the first and last non-zero coefficients (or the number of non-zero coefficients, or the cumulative total of those coefficients) is tested against a threshold to determine whether to hide the sign bit for that set. A parity check of the sum of the absolute values of the coefficients in the set is passed through the mechanism by which the sign bit is hidden. If the parity check does not correspond to the sign to be hidden, the parity check is adjusted by adjusting the level of one of the coefficients in the set.

FIG6 illustrates a third embodiment of coefficient sets for sign bit hiding using a 16×16 TU 150. In this embodiment, sets are also formed based on coefficient groups, but the sets do not necessarily contain the same number of coefficients or coefficient groups. For example, in this diagram, five coefficient sets are defined. A first set 152 contains coefficient groups 1 through 6. A second set 154 contains four coefficient groups 7, 8, 9, and 10. A third set 156 contains coefficient groups 11, 12, and 13. A fourth set 158 contains coefficient groups 14 and 15. A fifth set 159 contains only the upper left coefficient group 16. It should be understood that this embodiment provides larger coefficient sets in areas of the transform unit 150 where fewer non-zero coefficients are likely to exist, and smaller coefficient sets in areas of the transform unit 150 where more non-zero coefficients are typically present. Note that the above embodiment is applicable to TU sizes of 32×32 or larger, as well as TU sizes of 8×8, as long as the coefficient group structure is applicable to those TUs.

FIG7 illustrates a fourth embodiment in which coefficient sets for sign bit hiding within an 8×8 transform unit 160 are formed without adhering to a coefficient group structure. An 8×8 transform unit may or may not have coefficient group partitioning for significance map coding purposes. In any case, in this embodiment, coefficients are processed using a transform unit-based diagonal scan for sign bit coding and hiding. In this case, the coefficient sets are formed so that consecutive coefficients are grouped in scan order. For example, in this diagram, the transform unit 160 is grouped into four coefficient sets, each containing 16 consecutive coefficients in scan order. These groups are labeled 162, 164, 166, and 168 in FIG7 .

In yet another embodiment, the coefficient sets may not adhere to the scan order. That is, each set may include some coefficients from higher frequency positions in the transform unit and some coefficients from lower frequency positions in the transform unit. All coefficients in these sets may not necessarily be adjacent in the scan order.

FIG8 shows a fifth embodiment in which the coefficient sets for sign bit hiding within a 16×16 TU 170 are dynamically formed using the coefficient group structure and scan order. In this embodiment, rather than defining fixed sets of coefficients based on transform unit size and scan order, the encoder and decoder form sets by following the scan order and tracking quantities measured relative to a threshold until the threshold is reached. Once the threshold is reached, the sign bit is hidden for the coefficient group that the encoder and decoder are currently processing.

As an example, Figure 8 shows the last significant coefficient in coefficient group [2, 2]. In the scan order, the encoder and decoder then move to coefficient groups [1, 3], [3, 0] and [2, 1] in sequence. When processing the coefficient in coefficient group [2, 1], the threshold is reached. Therefore, the sign bit of the last non-zero coefficient to be processed in the reverse scan order in coefficient group [2, 1] is hidden in the parity check of the cumulative value of the absolute value of the coefficients starting from the last significant coefficient (LSC) and running through and including all coefficients in the current coefficient group [2, 1]. The threshold test in this example can be based on the presence of a minimum number of non-zero coefficients, or based on the absolute value of the coefficient exceeding a certain threshold. Reference numeral 174 indicates the sign bit hiding operation with respect to the "last" or upper left-most coefficient in a particular coefficient group.

In a sixth embodiment, sign bit hiding is performed on a coefficient group basis, and the criteria for determining whether a coefficient group is suitable for sign bit hiding is dynamically adjusted based on previously decoded coefficient groups. As an example, if the coefficient group immediately to the right or the coefficient group immediately below it has non-zero coefficients, then the current coefficient group is determined to be suitable for sign bit hiding, as long as the current coefficient group contains at least two non-zero coefficients. A coefficient group can also be determined to be suitable if there are at least a minimum number of coefficients between the first and last non-zero coefficients in the coefficient group.

It should be understood that in some of the aforementioned embodiments, the sign bit hiding in one coefficient group can be implemented based on a parity check value that depends on the coefficients in another coefficient group. In other words, the sign value of the coefficients in one coefficient group can be hidden in the parity check performed by changing the level of the coefficients in another coefficient group.

Furthermore, it should be understood that in some of the aforementioned embodiments, the concealed sign bit in the coefficient set may be from a different syntax unit, such as a motion vector difference flag (eg, mvd_sign_flag).

On the encoder side, a decision is made as to which coefficient to adjust in order to hide the sign bit if the parity value does not correspond to the sign. In the event that the parity value needs to be adjusted, the coefficient level must be increased or decreased by 1 in order to change the parity.

In one embodiment, the first step in the process of adjusting the coefficient levels is to determine a search range, i.e., a start position and an end position in the scan order. The coefficients within this range are then evaluated and one is selected for change. In an exemplary embodiment, the search range can be from the first non-zero coefficient to the last coefficient in the scan order.

With multi-level significance maps, the end position of the search range for a subset can be changed to take advantage of block-level information. Specifically, if a subset contains the last non-zero coefficient in the entire TU (the so-called last or last significant coefficient in the world), the search range can be established from the first non-zero coefficient to the last non-zero coefficient. For other subsets, the search range can be extended to the range from the first non-zero coefficient to the end of the current subblock.

In one embodiment, the starting position can be expanded to conditionally include the unquantized coefficients preceding the first non-zero quantized coefficient. In particular, all coefficients before quantization are considered. Unquantized coefficients with the same sign as the sign to be hidden will be included in the search. For the unquantized coefficients from position 0 to the position of the first non-zero quantized coefficient, the cost of changing the quantized coefficient from 0 to 1 will be evaluated and tested in the search.

Another issue in the process of adjusting coefficient levels is defining a cost calculation to evaluate the impact of the adjustment. When computational complexity is a concern, the cost can be based on distortion and not rate, in which case the search is to minimize distortion. On the other hand, when computational complexity is unimportant, the cost can include both rate and distortion, minimizing the rate-distortion cost.

If RDOQ is enabled, then RDOQ can be used to adjust the level. However, in many cases, the computational complexity of RDOQ may be unfavorable, and RDOQ may not be enabled. Therefore, in some embodiments, a simplified rate-distortion analysis can be applied at the encoder to achieve sign bit hiding.

Each coefficient between the first non-zero coefficient in the set and the last non-zero coefficient in the set can be tested by roughly calculating the distortion caused by adding 1 to the coefficient and the distortion caused by subtracting 1 from the coefficient. In general, the coefficient value u has an actual value of u + δ. The distortion is given by (δq) ^2. If the coefficient u is adjusted upward to u + 1 by adding 1, the resulting distortion can be estimated as follows:

q ² (1-2δ)

If the coefficient u is scaled down to u-1 by subtracting 1, the resulting distortion can be estimated as follows:

q ² (1+2δ)

It should be appreciated that for inter-coded blocks, when RDOQ is off, the quantization distortion δ is in the range of [-1/6 to +5/6]. In the case of intra-coded blocks, when RDOQ is off, the quantization distortion δ is in the range of [-1/3 to +2/3]. When RDOQ is on, the range of δ will change. However, the calculation of distortion growth above remains valid regardless of the range of δ.

The encoder also uses a set of logical rules (i.e., a predetermined rate cost criterion) to make a rough estimate of the rate cost of each coefficient. For example, in one embodiment, the predetermined rate cost criterion may include:

u+1 (u≠0 and u≠-1) → 0.5 bits

u-1 (u≠0 and u≠+1) → -0.5 bits

u=1 or -1 and changes to 0→-1-0.5-0.5 bits

u=0 and changes to 1 or -1→1+0.5+0.5 bits

Among them, the cost of sign marking is estimated to be 1 bit, the cost of significant coefficient marking is estimated to be 0.5 bit, and the cost increase from u to u+1 is estimated to be 0.5 bit.

Other rules or estimates may be used in other embodiments.

Referring now to FIG9 , there is shown an example process 200 for decoding video data with coefficient group-based sign bit hiding. The process 200 is based on the second embodiment described above. After studying this description, those skilled in the art will readily appreciate alternatives and modifications to the process 200 to implement the other embodiments described.

In operation 202, a threshold is set. In some embodiments, the threshold may be predetermined or preconfigured in the decoder. In other embodiments, the value may be extracted from the bitstream of the encoded video data. For example, the threshold may be in a picture header or elsewhere in the bitstream.

In operation 204, the decoder identifies the first non-zero position in the current coefficient group (i.e., set of coefficients) in scan order and the last non-zero position in the current coefficient group. The number of coefficients between the first and last non-zero coefficients in the coefficient group in scan order is then determined.

In operation 206, the decoder decodes the sign bit from the bitstream. A sign bit is decoded for each non-zero coefficient in the coefficient group except for the top-left non-zero coefficient in the coefficient group (the last non-zero coefficient in the reverse scan order). The sign bit is applied to its respective non-zero coefficient. For example, if the applicable convention is that a sign bit with a value of 0 represents "positive" and a sign bit with a value of 1 represents "negative", then for all sign bits set to 1, the corresponding coefficient level is "negative".

In operation 208, the decoder evaluates whether the number of coefficients between the first non-zero coefficient and the last non-zero coefficient in the coefficient group in scan order exceeds a threshold. If not, sign hiding was not used at the encoder, so in operation 210 the decoder decodes the top-left non-zero coefficient (the last one in reverse scan order) and applies it to the coefficient level. If the number of coefficients reaches the threshold, the decoder evaluates in operation 212 whether the absolute value of the sum of the coefficients in the current coefficient group is even or odd (i.e., its parity check). If it is even, the sign of the top-left non-zero coefficient is positive, and the decoder does not need to adjust it. If it is odd, the sign of the top-left non-zero coefficient is negative, so in operation 214, the coefficient is made negative.

In operation 216, the decoder determines whether it has completed processing the coefficient group. If so, the process exits 200. Otherwise, it moves to the next coefficient group in the group scan order in operation 218 and returns to operation 204.

In one embodiment, the size of the coefficient set can be reduced to a single coefficient. That is, sign bit hiding can be performed on a single coefficient basis. In this embodiment, each coefficient is tested to see if its sign information is hidden. An example test is to compare the magnitude of the coefficient level to a given threshold. For coefficients with a level greater than the threshold, their sign bit is hidden; otherwise, conventional sign bit encoding/decoding is used.

To apply sign bit hiding in the case of a single coefficient, the sign information is compared to the parity of the coefficient level. As an example, an even parity may correspond to a positive sign, while an odd parity may correspond to a negative sign. If the level does not correspond to the sign, the encoder adjusts the level. It should be understood that this technique implies that above a threshold, all negative levels are odd, and all positive levels are even. In a sense, this can be considered to actually modify the quantization step size of the coefficient by an amount greater than the threshold.

An example syntax for implementing sign bit hiding is provided below. This example syntax is just one possible implementation. In this example, sign bit hiding is applied on a coefficient group basis, and the threshold test is based on the number of coefficients from the first non-zero coefficient in the coefficient group to the last non-zero coefficient in the coefficient group. A flag labeled sign_data_hiding is sent in the picture header that indicates whether sign bit hiding is enabled. If enabled, the picture header also contains a parameter tsig, which is the threshold value. The example syntax is set forth below:

The following pseudocode shows an example implementation of coefficient group-based sign bit hiding:

Referring now to FIG. 10 , a simplified block diagram of an example embodiment of an encoder 900 is shown. The encoder 900 includes a processor 902, a memory 904, and an encoding application 906. The encoding application 906 may comprise a computer program or application stored in the memory 904 and containing instructions for configuring the processor 902 to perform the operations described herein. For example, the encoding application 906 may encode and output a bitstream encoded according to the process described herein. It will be appreciated that the encoding application 906 may be stored on a computer-readable medium, such as a compact disc, a flash memory device, random access memory, a hard drive, and the like.

Referring now also to FIG. 11 , a simplified block diagram of an example embodiment of a decoder 1000 is shown. Decoder 1000 includes a processor 1002, a memory 1004, and a decoding application 1006. Decoding application 1006 may comprise a computer program or application stored in memory 1004 and containing instructions for configuring processor 1002 to perform the operations described herein. Decoding application 1006 may comprise an entropy decoder configured to reconstruct the residual based at least in part on reconstructed significant-coefficient flags as described herein. It will be appreciated that decoding application 1006 may be stored on a computer-readable medium, such as a compact disc, a flash memory device, random access memory, a hard drive, and the like.

It will be appreciated that decoders and/or encoders according to the present application can be implemented in multiple computing devices, including but not limited to servers, general-purpose computers of suitable programming, audio/video encoding and playback equipment, television set-top boxes, television broadcasting equipment, and mobile devices. Decoders or encoders can be implemented by software comprising instructions, which are used to configure a processor to perform functions described herein. Software instructions can be stored on any suitable non-transient computer-readable storage device, including CD, RAM, ROM, flash memory, etc.

It will be appreciated that the encoders described herein and the modules, routines, processes, threads, or other software components that implement the described methods/processes for configuring the encoders can be implemented using standard computer programming techniques and languages. This application is not limited to a particular processor, computer language, computer programming conventions, data structures, or other such implementation details. Those skilled in the art will recognize that the described processes can be implemented as part of a computer executable code stored in a volatile or non-volatile memory, as part of an application specific integrated circuit (ASIC), or the like.

Certain adaptations and modifications may be made to the described embodiments.Therefore, the above embodiments are to be considered as illustrative rather than restrictive.

Claims (19)

1. A method for decoding a bitstream of encoded video by reconstructing the coefficients of transform units, wherein the transform units are divided into non-overlapping coefficient groups, each non-overlapping coefficient group contains a corresponding set of coefficients, and each non-zero coefficient has a sign bit indicating whether the coefficient is positive or negative, the method comprising: For each of at least two sets of coefficients in the transform unit: Decode the sign bits of all non-zero coefficients in the coefficient group except for one non-zero coefficient; Summing the absolute values of the coefficients in the coefficient set; and Based on whether the absolute value is even or odd, a sign is assigned to the non-zero coefficients in the coefficient group whose sign bits have not been decoded. 2. The method according to claim 1, further comprising: For each coefficient group in the transform unit, determine whether to decode the sign bits of all non-zero coefficients in that coefficient group, or whether that coefficient group is one of the at least two coefficient groups. 3. The method of claim 2, wherein determining for each coefficient group further comprises: determining whether the number of coefficients between the first non-zero coefficient and the last non-zero coefficient in the coefficient group in the scanning order exceeds a threshold. 4. The method of claim 2, wherein determining each coefficient group further comprises: determining whether adjacent coefficient groups contain at least one non-zero coefficient. 5. The method according to claim 4, wherein the adjacent coefficient group includes any one of the coefficient group to the right of the current coefficient group and the coefficient group below the current coefficient group. 6. The method of claim 2, wherein determining comprises: for each coefficient group, if the coefficient group contains at least a threshold number of coefficients between a first non-zero coefficient and a last non-zero coefficient in the coefficient group in scan order within the coefficient group, and wherein the threshold number is determined based on whether adjacent coefficient groups contain at least one non-zero coefficient, then determining that the coefficient group is one of the at least two coefficient groups. 7. The method of claim 6, wherein the adjacent coefficient group includes any one of the coefficient group to the right of the current coefficient group and the coefficient group below the current coefficient group. 8. The method of claim 1, wherein each coefficient group is square. 9. The method of claim 1, wherein each coefficient group is 4×4. 10. A decoder for decoding a bitstream of encoded video by reconstructing the coefficients of transform units, wherein the transform units are divided into non-overlapping coefficient groups, each non-overlapping coefficient group containing a corresponding set of coefficients, and each non-zero coefficient has a sign bit indicating whether the coefficient is positive or negative, the decoder comprising: processor; Memory; and The decoding application, stored in memory, contains instructions for causing the processor to perform the following actions during execution: For each of at least two sets of coefficients in the transform unit: Decode the sign bits of all non-zero coefficients in the coefficient group except for one non-zero coefficient; Summing the absolute values of the coefficients in the coefficient set; and Based on whether the absolute value is even or odd, a sign is assigned to the non-zero coefficients in the coefficient group whose sign bits have not been decoded. 11. The decoder of claim 10, wherein the instructions, when executed, further cause the processor to perform the following operations: For each coefficient group in the transform unit, determine whether to decode the sign bits of all non-zero coefficients in that coefficient group, or whether that coefficient group is one of the at least two coefficient groups. 12. The decoder of claim 11, wherein the instructions, when executed, further cause the processor to perform the following operations: For each coefficient group, it is determined whether the coefficient group is one of the at least two coefficient groups based on whether the number of coefficients between the first non-zero coefficient and the last non-zero coefficient in the coefficient group in the scanning order exceeds a threshold. 13. The decoder of claim 11, wherein the instructions, when executed, further cause the processor to perform the following operations: For each coefficient group, it is determined whether the coefficient group is one of the at least two coefficient groups based on whether adjacent coefficient groups contain at least one non-zero coefficient. 14. The decoder of claim 13, wherein the adjacent coefficient group includes any one of the coefficient group to the right of the current coefficient group and the coefficient group below the current coefficient group. 15. The decoder of claim 11, wherein the instructions, when executed, further cause the processor to perform the following operations: For each coefficient group, it is determined whether the coefficient group is one of the at least two coefficient groups based on the following: The coefficient group is determined based on whether the first non-zero coefficient in the coefficient group and the last non-zero coefficient in the coefficient group, in the scanning order, contain at least a threshold number of coefficients, and the threshold number is determined based on whether adjacent coefficient groups contain at least one non-zero coefficient. 16. The decoder of claim 15, wherein the adjacent coefficient group includes any one of the coefficient group to the right of the current coefficient group and the coefficient group below the current coefficient group. 17. The decoder of claim 10, wherein each coefficient group is square. 18. The decoder of claim 10, wherein each coefficient group is 4×4. 19. A non-transitory processor-readable medium storing processor-executable instructions, which, when executed, configure one or more processors to perform the method according to claim 1.