Method and apparatus for scan order selection

Abstract

The disclosure proposes a decoder for decoding coefficients of blocks of a video sequence from a bitstream. The decoder comprises a scan pattern list module for providing one or more pre-defined scan orders, a scan order generator for generating one or more scan orders, a scan order selector for selecting a scan order for each block from the pre-defined and generated scan orders on the basis of scan order information contained in the bitstream, a decoding module for decoding one or more coefficient vectors of each block from the bitstream, a deserializer for inverse scanning, for each block, the one or more coefficient vectors of that block according to the scan order selected for that block so as to obtain a coefficient matrix. The scan order generator generates the one or more scan orders depending on one or more previously obtained coefficient matrices of blocks of the video sequence.

Claims

1. A decoder for decoding coefficients of blocks of a video sequence from a bitstream, the decoder comprising: a scan order generator configured to generate one or more scan orders and initialize a scan order list that includes scan orders generated by the scan order generator; a scan order selector configured to select a scan order for each block from the scan orders by determining a coding parameter set of that block, wherein the coding parameter set corresponds to prediction mode; a decoding module configured to decode one or more coefficient vectors of each block from the bitstream; a deserializer configured to inverse scan, for each block, the one or more coefficient vectors of that block according to the scan order selected for that block so as to obtain a coefficient matrix; wherein the scan order generator is configured to generate the one or more scan orders for the transform coefficients of the block according to block size, wherein the one or more coefficient vectors of the block comprise at least one hiding coefficient vector, and the at least one hiding coefficient vector comprises hidden information, and wherein the one or more coefficient vectors of the block correspond to a respective coefficient group, and the at least one hiding coefficient vector corresponds to the coefficient group in which data hiding is performed.

2. The decoder according to claim 1, further comprising a scan pattern list module configured to provide one or more pre-defined scan orders for each of a plurality of coding parameter sets, wherein the scan order generator is configured to generate a scan order for each of the plurality of coding parameter sets according to one or more previously obtained coefficient matrices associated with that coding parameter set, and wherein the scan order selector is configured to select a scan order for each block by: determining a coding parameter set of that block, and selecting the scan order for the coefficient matrix obtained for that block from the scan orders for the determined coding parameter set.

3. The decoder according to claim 2 further comprising: a coefficient distribution estimator configured to provide, for each of the plurality of coding parameter sets, a distribution statistics of one or more previously obtained coefficient matrices associated with that coding parameter set, wherein the scan order generator is configured to generate the scan order for each of the plurality of coding parameter sets according to the distribution statistics for that coding parameter set.

4. The decoder according to claim 3, wherein, if the scan order selected for a given block is pre-defined, the coefficient distribution estimator is configured not to update or is configured to reset the distribution statistics for the coding parameter set of the given block.

5. The decoder according to claim 2, wherein the decoding module is configured to parse, for each block, coding parameter information from the bitstream, and the scan order selector is configured to determine the coding parameter set of a given block according to the parsed coding parameter information for that given block.

6. The decoder according to claim 1, wherein the decoding module is configured to parse scan order information identifying the selected scan order from the bitstream.

7. A method for decoding coefficients of blocks of a video sequence from a bitstream, the method comprising: generating one or more scan orders; initialize a scan order list that includes the one or more scan orders; selecting a scan order for each block from the scan orders by determining a coding parameter set of that block, wherein the coding parameter set corresponds to prediction mode; decoding one or more coefficient vectors of each block from the bitstream; and inverse scanning, for each block, the one or more coefficient vectors of that block according to the scan order selected for that block so as to obtain a coefficient matrix, wherein generating one or more scan orders comprises generating the one or more scan orders for the transform coefficients of the block according to block size, wherein the one or more coefficient vectors of the block comprise at least one hiding coefficient vector, and the at least one hiding coefficient vector comprises hidden information, and wherein the one or more coefficient vectors of the block correspond to a respective coefficient group, and the at least one hiding coefficient vector corresponds to the coefficient group in which data hiding is performed.

8. The method according to claim 7, further comprising: reconstructing, for at least one block, hidden information from one or more coefficients of that block, the hidden information forming part of scan order information associated with that block.

9. An encoder for encoding coefficients of blocks of a video sequence into a bitstream, the coefficients of each block being contained in a respective coefficient matrix, the encoder comprising: a scan order generator configured to generate one or more scan orders and initialize a scan order list that includes scan orders generated by the scan order generator; a scan order selector configured to select a scan order for each block from the scan orders by determining a coding parameter set of that block, wherein the coding parameter set corresponds to prediction mode; a serializer configured to scan, for each block, the coefficient matrix of that block according to the scan order selected for that block so as to obtain one or more coefficient vectors; and a coding module configured to code the coefficient vectors into the bitstream, wherein the scan order generator is configured to generate the one or more scan orders for the transform coefficients of the block according to block size, wherein the one or more coefficient vectors of the block comprise at least one hiding coefficient vector, and the at least one hiding coefficient vector comprises hidden information, and wherein the one or more coefficient vectors of the block correspond to a respective coefficient group, and the at least one hiding coefficient vector corresponds to the coefficient group in which data hiding is performed.

10. The encoder according to claim 9, further comprising a scan pattern list module configured to provide one or more pre-defined scan orders for each of a plurality of coding parameter sets, wherein the scan order generator is configured to generate a scan order for each of the plurality of coding parameter sets according to one or more previously scanned coefficient matrices associated with that coding parameter set, and wherein the scan order selector is configured to select a scan order for each block by: determining a coding parameter set of that block, and selecting the scan order for the coefficient matrix of that block from the scan orders for the determined coding parameter set.

11. The encoder according to claim 10 further comprising: a coefficient distribution estimator configured to provide, for each of the plurality of coding parameter sets, a distribution statistics of one or more previously scanned coefficient matrices associated with that coding parameter set, wherein the scan order generator is configured to generate the scan order for each of the plurality of coding parameter sets according to the distribution statistics for that coding parameter set.

12. The encoder according to claim 11, wherein, if the scan order selected for a given coefficient matrix is pre-defined, the coefficient distribution estimator is configured not to update or is configured to reset the distribution statistics for the coding parameter set of the given block.

13. The encoder according to claim 9, further comprising a signaling module configured to add scan order information identifying the selected scan order in the bitstream.

14. The encoder according to claim 9, wherein the scan order selector is configured to select the scan order from the scan orders based on a cost function.

15. A method for encoding coefficients of blocks of a video sequence into a bitstream, the coefficients of each block being contained in a respective coefficient matrix, the method comprising: generating one or more scan orders; initialize a scan order list that includes the one or more scan orders; selecting a scan order for each block from the scan orders by determining a coding parameter set of that block, wherein the coding parameter set corresponds to prediction mode; scanning, for each block, the coefficients of that block according to the scan order selected for that block so as to obtain one or more coefficient vectors; and coding the coefficient vectors into the bitstream, wherein generating one or more scan orders comprises generating the one or more scan orders for the transform coefficients of the block according to block size, wherein the one or more coefficient vectors of the block comprise at least one hiding coefficient vector, and the at least one hiding coefficient vector comprises hidden information, and wherein the one or more coefficient vectors of the block correspond to a respective coefficient group, and the at least one hiding coefficient vector corresponds to the coefficient group in which data hiding is performed.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) The above aspects and implementation forms of the present disclosure will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which

(2) FIG. 1 shows a video encoder according to an embodiment of the present disclosure.

(3) FIG. 2 shows a video decoder according to an embodiment of the present disclosure.

(4) FIG. 3 shows a flowchart of coefficient distribution estimation at the video decoder according to an embodiment of the present disclosure.

(5) FIG. 4 shows a flowchart of coefficient distribution estimation at the video encoder according to an embodiment of the present disclosure.

(6) FIG. 5 shows a flowchart of an initialization of a scan order list according to an embodiment of the present disclosure.

(7) FIG. 6 shows a flowchart of implicit and explicit signaling of selected scan order according to an embodiment of the present disclosure.

(8) FIGS. 7 and 8 show a hiding condition according to an embodiment of the present disclosure.

(9) FIG. 9 shows an entropy decoding of coefficients according to the prior art.

(10) FIG. 10 shows an embodiment of the present disclosure for improving the coding efficiency by reducing the signaling overhead in the bitstream.

(11) FIG. 11 shows a coefficient reorder according to the present disclosure.

(12) FIG. 12 shows an example of hiding conditions defined for scan orders.

DETAILED DESCRIPTION OF EMBODIMENTS

(13) FIG. 1 shows a video encoder according to an embodiment of the present disclosure, and particularly shows an encoder 100 for encoding coefficients of blocks of a video sequence into a bitstream 107, the coefficients of each block being contained in a respective coefficient matrix.

(14) The encoder comprises a scan pattern list module 110 configured to provide one or more pre-defined scan orders.

(15) The encoder comprises a scan order generator 111 configured to generate one or more scan orders.

(16) The encoder comprises a scan order selector 109 configured to select a scan order for each block from the pre-defined and generated scan orders.

(17) The encoder comprises a serializer 104 configured to scan, for each block, the coefficient matrix of that block according to the scan order selected for that block so as to obtain one or more coefficient vectors.

(18) The encoder comprises a coding module 106 configured to code the coefficient vectors into the bitstream 107.

(19) The scan order generator 111 is configured to generate the one or more scan orders depending on one or more previously scanned coefficient matrices of blocks of the video sequence.

(20) FIG. 2 shows a video decoder according to an embodiment of the present disclosure, and particularly a decoder 200 for decoding coefficients of blocks of a video sequence from a bitstream 207.

(21) The decoder comprises a scan pattern list module 210 configured to provide one or more pre-defined scan orders.

(22) The decoder comprises a scan order generator 211 configured to generate one or more scan orders.

(23) The decoder comprises a scan order selector 209 configured to select a scan order for each block from the pre-defined and generated scan orders on the basis of scan order information SCAN_IDX contained in the bitstream.

(24) The decoder comprises a decoding module 206 configured to decode one or more coefficient vectors of each block from the bitstream 207.

(25) The decoder comprises a deserializer 204 configured to inverse scan, for each block, the one or more coefficient vectors of that block according to the scan order selected for that block so as to obtain a coefficient matrix.

(26) The scan order generator 211 is configured to generate the one or more scan orders depending on one or more previously obtained coefficient matrices of blocks of the video sequence.

(27) Particularly, FIG. 1 shows an example of an encoder-side residual coding part with content-adaptive scan order selection. In the example, the encoder 100 is configured to apply inter- or intra-prediction to each block of each picture of the video sequence. An intra-prediction mode uses pixels of the same picture to generate reference samples to calculate the prediction values for the pixels of the block being reconstructed. An inter-prediction mode is designed for temporal prediction and uses reference samples of previous or next pictures to predict pixels of the block of the current picture. The result of the prediction stage may be a residual signal 101 that is the difference between an original signal of a block and its prediction signal obtained via inter- or intra-prediction.

(28) A prediction mode for obtaining the residual signal 101 may correspondingly refer to either intra- or inter-prediction mode. Further on, the prediction mode may correspond to any of a plurality of available prediction modes or directions. For example, the plurality of available prediction modes may comprise up to 35 intra prediction modes, which may include 33 directional modes and 2 non-directional modes, such as a direct current (DC) prediction mode and a planar prediction mode. The 33 directional modes may cover a π-radian or 180-degree angular range. If the direction of a vertical mode is regarded as zero degree, the 33 directional modes may be symmetrical about the −45 degrees axis. With respect to the prediction mode, the encoder may be configured to determine, for a given block, one of the plurality of available prediction modes based on a Rate-Distortion Optimization (RDO).

(29) A Coding Tree Unit (CTU) is the root of a coding a structure of the video sequence of a pre-defined size, containing a part of a picture (e.g. 64×64 pixels). A CTU can be partitioned into Coding Units (CUs). A CU is a basic coding structure of the video sequence of a pre-defined size, containing a part of a picture which belongs to a CTU. A CU can be partitioned into further CUs. A Prediction Unit (PU) is a coding structure which is the result of the partitioning of a CU. A PU can be partitioned to several Transform Unit (TUs) or coincide with a single TU. A PU can be intra- or inter-predicted according to the type of processing applied for the pixels of PU. In case of inter-prediction, a PU represents an area of pixels that is processed by motion compensation using a motion vector specified for a PU.

(30) In this respect, a partition mode may depend on the PU, and particularly on the size and/or the orientation of the PU. The partition mode may correspond to any of a plurality of available partition modes. The encoder may be configured to determine, for a block or PU, one of the plurality of available partition modes based on an RDO method. For example, the partition mode may correspond to a horizontally oriented shape, in which a CU may be partitioned into 2N×N PUs or blocks. Also, the partition mode may correspond to a vertically oriented shape, in which a CU may be partitioned into N×2N PUs or blocks, or to a square shape, in which a CU may be partitioned into 2N×2N PUs or blocks.

(31) The residual signal 101 may be provided to a transform module 102 for transform coding the residual signal 101 so as to obtain transform coefficients. Particularly, for intra prediction a PU may specify a prediction mode for a set of TUs. A TU can have different sizes—e.g., 4×4, 8×8, 16×16 and 32×32 pixels—and can be processed in different ways. Examples of transforms that may be applied to a residual signal comprise for example Discrete Cosine Transform (DCT) and Discrete Sine Transform (DST).

(32) In this respect, a transform parameter may be the size or the shape of the TU, or both size and shape. A further transform parameter may be the transform being applied, e.g. DCT or DST among others.

(33) The residual signal 101 calculated for a block of the source picture is transformed by the transform module 102 and then quantized by a quantization module 103. The quantization module 103 processes the transform coefficients so as to obtain quantized transform coefficients (QTCs) in the form of a coefficient matrix.

(34) In this respect, a quantization parameter may correspond to the number of significant coefficients of the coefficient matrix, i.e. the number of coefficients of the coefficient matrix that have a non-zero value.

(35) The coefficient matrix is serialized by means of the serializer 104 by scanning in an order determined by the scan order selector 109. The scan order can be either selected from the pre-defined scan orders provided by the scan pattern list 110 or from the generated scan orders provided by the scan order generator 111. The scan orders provided by the scan pattern list 110 are pre-defined for both the encoder 100 and the decoder 200 sides and thus a scan order selected from the scan pattern list 110 is static, i.e. is not modified throughout the whole encoding or decoding process. The scan orders provided by the scan order generator 111 are dynamic, i.e. are generated depending on one or more previously obtained coefficient matrices of blocks of the video sequence. Particularly, the generated scan orders may be generated according to distribution statistics of coefficients matrices during the encoding or decoding process.

(36) The one or more coefficient vectors obtained by the serializer 104 from a coefficients matrix are stored in a quantized coefficients buffer 105. The coding module 106 may be in form of an entropy coding module for entropy coding the coefficient vectors into the bitstream 107. The scan order that is selected by the scan order selector 109 may be identified by means of a scan index or scan order information SCAN_IDX.

(37) This scan index information may be explicitly added to the bitstream 107, i.e. the value of the scan order information SCAN_IDX may be stored in the bitstream 107 by means of a dedicated variable or parameter. Alternatively, a hiding module 112 may be configured to hide at least partially the scan order information SCAN_IDX in the coefficient vectors, i.e. in the values of the coefficient matrix after serialization. For example, the hiding module 112 may correspondingly perform adjustments of the coefficients stored in the quantized coefficients buffer 105 so that a corresponding check module located in a check module 212 of the decoder 200 can derive the scan order information SCAN_IDX by applying a check function to them. The resulting adjusted coefficients or coefficient vectors stored in the quantized coefficients buffer 105 may then be entropy encoded and transmitted to the decoder 200 in the bitstream 107.

(38) The coefficients of the one or more coefficient vectors stored in the quantized coefficients buffer 105 may then be adjusted or not, depending on whether the scan order information SCAN_IDX is explicitly or implicitly transmitted in the bitstream 107, i.e. depending on whether the scan order information is hidden or not.

(39) Particularly, the scan pattern list module 110 is configured to provide one or more pre-defined scan orders for each of a plurality of coding parameter sets. The scan order generator 111 is configured to generate a scan order for each of the coding parameter sets depending on one or more previously scanned coefficient matrices associated with that coding parameter set. The scan order selector 109 is configured to select a scan order for each block by: determining a coding parameter set of that block, and selecting the scan order for the coefficient matrix of that block from the pre-defined and generated scan orders for the determined coding parameter set.

(40) In this respect, a coding parameter set corresponds to a particular combination of at least one or more of: a prediction mode, a partition mode, one or more transform parameters, and one or more quantization parameters.

(41) The prediction mode, partition mode, transform parameters, and quantization parameters are generally referred to by reference 108 in FIG. 1. For example, a coding parameter set can correspond to only a prediction mode (e.g. a specific directional intra prediction mode), to only a partition mode (e.g. a specific orientation of the PU), to only one or more transform parameters (e.g. a specific size and/or shape of the TU), or to only one or more quantization parameters (e.g. a specific number of significant coefficients of the coefficient matrix). Also, the coding parameter set may correspond to a particular combination of the prediction mode, partition mode, transform parameters, and/or quantization parameters.

(42) The encoder 100 may comprise a coefficient distribution estimator 113 configured to provide, for each of the coding parameter sets, a distribution statistics of one or more previously scanned coefficient matrices associated with that coding parameter set. The scan order generator 111 is configured to generate the scan order for each of the coding parameter sets depending on the distribution statistics for that coding parameter set.

(43) Particularly, the coefficients stored in the quantized coefficients buffer 105 are also a source for the coefficient distribution statistics estimation that is used by the scan order generator 111. However, before estimating the coefficients distribution, the stored coefficients are deserialized back from coefficients vector to a coefficient matrix by means of a deserializer 114.

(44) The distribution statistics of a coefficient matrix preferably comprises, as defined in US 2008/0310504, an indication of the likelihood that a coefficient value in a position of the two-dimensional coefficient matrix is zero or non-zero and may, for example, comprise a count, a probability or other statistical metric associated with each of the coefficient positions of the two-dimensional coefficient matrix. A scan order generated depending on such a distribution statistics may correspondingly be a scan order that is configured to scan with higher priority the coefficient positions with a higher likelihood of having non-zero coefficients.

(45) Particularly, if the scan order selected for a given block is a generated scan order, the coefficient distribution estimator 113 may be configured to update the distribution statistics for the coding parameter set of the given block according to distribution statistics of the coefficient matrix of the given block. The distribution statistics of the coefficient matrix of the given block may reflect whether or not the coefficient at a position in the coefficient matrix of the given block is zero or non-zero. The distribution statistics provided by the coefficient distribution estimator 113 may then for example be updated depending on said distribution statistics of the coefficient matrix of the given block.

(46) Particularly, if the scan order selected for a given coefficient matrix is pre-defined, the coefficient distribution estimator 113 may be configured not to update or may be configured to reset the distribution statistics for the coding parameter set of the given block. Resetting the distribution statistics may for example consist in resetting said count, probability or other statistical metric.

(47) This update, non-update, or reset of the distribution statistics carried out by the coefficient distribution estimator 113 depending on whether the scan order selector 109 has selected a generated or pre-defined scan order is reflected in FIG. 1 by a dashed arrow from the scan order selector 109 to the coefficient distribution estimator 113.

(48) The decoder of the proposed embodiment is shown in FIG. 2. Processing stages are similar to the ones of the encoder (see FIG. 1) and are applied in the inverse order. The most important difference is that the quantized coefficients buffer stores QTCs after they are deserialized, i.e. as a QTCs matrix but not QTCs as one ore more vectors.

(49) Particularly, FIG. 2 shows an example of a residual decoding part with content-adaptive scan order selection. In the example, the decoder 200 is configured to obtain a residual signal 201 from the bitstream 207. After generate, by the decoding module 206 (e.g., an entropy decoding module) and the deserializer 204, the coefficient matrix comprising quantized transform coefficients, a quantized coefficients buffer 205 stores said coefficient matrix. The stored coefficient matrix is then processed by an inverse quantization module 203 and by an inverse transform module 202 to obtain the residual signal 201 corresponding to the residual signal 101 in the encoder 100. Using the residual signal 201, the encoded video sequence may be reconstructed according to known techniques.

(50) The coefficient distribution estimator 213 of the decoder 200 may be similar or identical in function to the coefficient distribution estimator 113 of the encoder 100. In the example, they differ in that the coefficient distribution estimator 213 receives as input the coefficient matrix stored in the quantized coefficients buffer 205 while the coefficient distribution estimator 113 receives as input the coefficient matrix obtained from the deserializer 114.

(51) The present disclosure proposes the combined use of pre-defined scan orders and generated scan orders at both encoder 100 and decoder 200 side depending on previously scanned, respectively obtained, coefficient matrices of blocks of the video sequence. Particularly, the generated scan orders are generated by analyzing a distribution statistics of the coefficients within the coefficient matrix, i.e. by analyzing a distribution of the quantized transform coefficients.

(52) A particular feature of the proposed disclosure is that distribution statistics for quantized transform coefficients (QTCs) are estimated more precisely by taking the selected scan order into consideration, as shown for example in FIGS. 1 and 2 by the arrow between the scan order selector 109, 209 and the coefficient distribution estimator 113, 213. This more precise estimation may consist e.g. in updating, not updating, or resetting the distribution statistics as shown above.

(53) The coefficient distribution can be estimated more accurately by splitting the source data into 4 stationary periods and estimating the coefficient distribution only within these stationary periods. A stationary period is a number of blocks that have similar QTCs distribution and are spatially close to each other.

(54) In the present disclosure, it is particularly proposed to detect a stationary period by introducing a threshold on the number of processed blocks that is signaled to have adaptively generated scan order. When the scan order is selected from the pre-defined scan orders provided by the scan pattern list module, there is no need to update the distribution statistics, because for this case the fact that the scan order is a pre-defined one indicates that the currently processed block belongs to different stationary period.

(55) FIG. 3 shows a flowchart of distribution statistics estimation at the video decoder according to an embodiment of the present disclosure.

(56) At the video decoder, the estimation 301 of the distribution statistics by the coefficient distribution estimator 213 comprises several steps.

(57) In a step 302, the prediction mode, partition mode, transform parameters, and/or quantization parameters 208 for a block are parsed from the bitstream 207. Preferably, this parsing is carried out by the decoding module 206. According to the parsed information, the scan order selector 209 preferably determines the encoding mode of that block.

(58) In a step 303, the scan order information SCAN_IDX identifying the selected scan order for that block is parsed from the bitstream 207. This parsing is preferably done by the decoding module 206.

(59) In a step 304, the scan order selector 209 selects the scan order for that block from the pre-defined and generated scan orders on the basis of the parsed scan order information SCAN_IDX.

(60) In a step 305, it is determined whether the selected scan order is a pre-defined scan order provided by the scan pattern list module 210 or a generated scan order provided by the scan order generator 211.

(61) If the scan order selected for that block is a generated one (e.g., provided by the scan order generator 211), the coefficient distribution estimator 213 updates, in a step 306, the current distribution statistics. This current distribution statistics is obtained preferably from previous blocks. The current distribution statistics is updated according to a distribution statistics of the coefficient matrix obtained for that block.

(62) If, however, the scan order selected for that block is a predefined one (e.g., provided by the scan pattern list module 210), the coefficient distribution estimator 213 processes, in a step 306, the distribution statistics of that block separately from the current distribution statistics. For example, the coefficient distribution estimator 213 may not update or may reset the current distribution statistics.

(63) After step 306 or 307, the estimation 301 of the distribution statistics ends (in step 308).

(64) FIG. 4 shows a flowchart of distribution statistics estimation at the video encoder according to an embodiment of the present disclosure.

(65) At the video encoder, the estimation 401 of the distribution statistics by the coefficient distribution estimator 113 comprises several steps.

(66) In a step 402, an RDO procedure is carried out by the scan order selector 109 in order to select, from among the pre-defined scan orders provided by the scan pattern list module 110 and the generated scan orders provided by the scan order generator 111, the scan order that provides the minimal rate-distortion (RD) cost. In this step, the scan order information SCAN_IDX of the selected scan order is obtained.

(67) In a step 403, the scan order corresponding to the selected scan order information SCAN_IDX is obtained.

(68) The further steps 404 to 407 correspond to the steps 305 to 308 of FIG. 3.

(69) As shown in FIGS. 3 and 4, at both the encoder and the decoder sides a scan order list is initialized. It includes members of the scan pattern list module and scan orders generated by the scan order generator. Depending on whether the scan order selected by the scan order selector is generated or pre-defined, a decision on the distribution statistics is taken. This decision may consist in updating the current distribution statistics or not, or in resetting the current distribution statistics.

(70) One of the possible ways to initialize the scan order list is shown in FIG. 5. FIG. 5 correspondingly shows a flowchart 500 of an initialization 501 of a scan order list according to an embodiment of the present disclosure.

(71) Its initialization depends on prediction mode, partitioning mode, transform parameters and quantization parameters specified for a block being processed.

(72) In a step 502, it is determined whether the prediction mode of that block is a planar intra prediction mode. If this is true, a scan pattern list of pre-defined scan orders is defined 508 so as to comprise pre-defined Z-order and diagonal scan orders. If this is false, step 503 is carried out.

(73) In the step 503, it is determined whether the prediction mode of that block is a DC intra prediction mode. If this is true, a scan pattern list of pre-defined scan orders is defined 508 so as to comprise pre-defined Z-order and diagonal scan orders. If this is false, step 504 is carried out.

(74) In the step 504, it is determined whether the prediction mode of that block is an angular intra prediction mode close to horizontal. If this is true, a scan pattern list of pre-defined scan orders is defined 509 so as to comprise vertical, vertical-diagonal, and helix scan orders. If this is false, step 505 is carried out.

(75) In the step 505, it is determined whether the prediction mode of that block is an angular intra prediction mode close to vertical. If this is true, a scan pattern list of pre-defined scan orders is defined 510 so as to comprise horizontal, horizontal-diagonal, and helix scan orders. If this is false, step 506 is carried out.

(76) In the step 506, it is determined whether the prediction mode of that block is an angular intra prediction mode close to diagonal. If this is true, a scan pattern list of pre-defined scan orders is defined 511 so as to comprise diagonal, Z-order, and helix scan orders. If this is false, step 507 is carried out. In the step 507, a scan pattern list of pre-defined scan orders is defined so as to comprise a diagonal scan order.

(77) After defining the scan order list of pre-defined scan orders for that block, the scan order list is adjusted 512 using the portioning mode, the transform parameters and quantization parameters of that block.

(78) In a step 513, the one or more generated scan orders provided by the scan order generator are added to the pre-defined scan orders, so that for example the scan order selector 109 of the encoder may select from the pre-defined and generated scan orders, the scan order that provides the minimal RD-cost.

(79) As shown in FIG. 5, the pre-defined scan orders may depend on the prediction mode and/or partitioning mode and/or transform parameters and/or quantization parameters. For example, the most probable scan orders for the cases of DC or planar intra modes are Z-order and diagonal scan order. For angular modes, the directionality of the residual signal may be taken into account so that the pre-defined scan orders may be selected to be orthogonal to the intra-mode directionality.

(80) Afterwards this list of pre-defined scan orders may be updated according to other encoding parameters, such as the portioning mode, the transform parameters and quantization parameters. Particularly, this list may be updated according to partitioning and transform sizes.

(81) For example, in the inter-prediction mode, non-square prediction modes can also indicate the directional nature of the residual signal and the list of pre-defined scan orders may be updated accordingly: if a partitioning rectangle is oriented vertically then horizontal and horizontal-diagonal scan orders are added to the scan list. The list of pre-defined scan orders is updated accordingly for horizontally oriented partitioning: in such a case, vertical and vertical-diagonal scans are added to the list of pre-defined scan orders.

(82) For example, this list of pre-defined scan orders may be updated according to transform sizes. Smaller TU sizes introduce restrictions on some scan patterns. Then, for example helix scans may be excluded from the pre-defined scan order list if TU size is smaller than 8×8 pixels.

(83) Quantization parameters (QP) may affect both the list of pre-defined scan orders and the signaling method. For high QP values, the number of scan patterns may be reduced. For example, helix scans may be skipped for all the TU sizes, because QTCs become more aligned to left, top and upper-left corner of QTCs matrix.

(84) An example of the dependency of the signaling scheme on QP is shown in FIG. 6. FIG. 6 particularly shows a flowchart 600 of implicit and explicit signaling of selected scan order according to an embodiment of the present disclosure.

(85) In a first step 601, a QP value is obtained. If that QP value is smaller or equal 602 to a QP value for high bit rates QP.sub.HBR, then the scan order information SCAN_IDX should be entropy coded 603 in the bitstream.

(86) If the QP value is above the value QP.sub.LBR and below a further QP value for low bit rates QP.sub.LBR, then the scan order information SCAN_IDX should be partially entropy coded 606 and partially hidden within the quantized transform coefficients by the hiding module 112.

(87) If the QP value is above the value QP.sub.HBR and above or equal to that further QP value for low bit rates QP.sub.LBR, then the scan order information SCAN_IDX should be hidden 605 within the quantized transform coefficients by the hiding module 112.

(88) Accordingly, hiding becomes more costly with the increase of bitrate and is totally switched off for high bit rates. For low bit rates vice versa, hiding becomes more preferable. Otherwise, i.e. for middle bit rates, both signaling mechanisms are being used. The selection of the signaling mechanism is performed for each block or TU depending on whether hiding can be performed for it.

(89) According to the present disclosure, a decoder 200 for decoding coefficients of blocks of a video sequence from a bitstream 207 is proposed. The decoder comprises: a decoding module 206 configured to decode one or more coefficient vectors of each block from the bitstream 207, a check module 212 configured to reconstruct, for at least one block, hidden information from one or more coefficients of that block, the hidden information constituting or forming part of scan order information SCAN_IDX associated with that block, a scan order selector 209 configured to select a scan order for each block from a set of scan orders, preferably from a set of pre-defined and generated scan orders, on the basis of the scan order information SCAN_IDX associated with that block, a deserializer 204 configured to inverse scan, for each block, the one or more coefficient vectors of that block according to the scan order selected for that block so as to obtain a coefficient matrix.

(90) According to the present disclosure, a corresponding encoder 100 for encoding coefficients of blocks of a video sequence into a bitstream 107 is proposed, the coefficients of each block being contained in a respective coefficient matrix. The encoder comprises: a scan order selector 109 configured to select a scan order for each block from a set of scan orders, preferably from a set of pre-defined and generated scan orders, a serializer 104 configured to scan, for each block, the coefficient matrix of that block according to the scan order selected for that block so as to obtain one or more coefficient vectors, a hiding module 112 configured to hide, for at least one block, scan order information SCAN_IDX identifying the scan order selected for that block at least partially in one or more coefficients of that block, a coding module 106 configured to code the coefficient vectors into the bitstream 107.

(91) The coding efficiency may then be improved because the signaling overhead in the bitstream 107, 207 generated by the encoder and received by the decoder may be reduced.

(92) Preferably, the check module 212 is configured to reconstruct, for at least one block, the hidden information from at least one hiding coefficient vector chosen from among the one or more coefficient vectors obtained for that block. Also, the hiding module 112 is configured to hide, for at least one block, the scan order information SCAN_IDX in at least one hiding coefficient vector chosen from among the one or more coefficient vectors obtained for that block.

(93) The reconstruction and the hiding may depend on a hiding condition. Such a hiding condition comprises a comparison of a parameter depending on the hiding coefficient vector to a threshold.

(94) The parameter may be: a number of significant, i.e. non-zero, coefficients within the hiding coefficient vector, or a distance between first and last significant coefficients within the hiding coefficient vector, or a ratio of a maximum absolute value to a minimum absolute non-zero value of the coefficients within the hiding coefficient vector,
wherein the hiding condition is true if the parameter is above the threshold, and false if the parameter is below the threshold.

(95) FIGS. 7 and 8 show a hiding condition according to an embodiment of the present disclosure. Particularly, FIG. 7 shows a block or TU which is subdivided into coefficient groups (CGs), each coefficient vector corresponding to a coefficient group. FIG. 8 shows an example of coefficient vector illustrating the case that the parameter consists in the distance N between first and last significant, i.e. non-zero, coefficients within the coefficient vector. If the value N is above a threshold TSIG, then the hiding condition is true and scan order information may be hidden in that coefficient vector.

(96) Particularly, the check module 212 may be configured to reconstruct the hidden information from the hiding coefficient vector by applying a check-function to the hiding coefficient vector, a result of the check-function being the hidden information. Also, the hiding module 112 is configured to hide, for at least one block, the scan order information SCAN_IDX in the hiding coefficient vector by: applying a check-function to the hiding coefficient vector so as to obtain a result of the check-function, determining whether the result of the check-function corresponds to the scan order information SCAN_IDX, if not, modifying the hiding coefficient vector so that the result of the check-function corresponds to the scan order information SCAN_IDX.

(97) It is proposed that the result of the check-function depends on coordinates (x, y), within the coefficient matrix, of the last significant coefficient of the hiding coefficient vector. The check-function may be e.g. the following function: mod(x+y+R,2)
x and y being the coordinates, and R being an integer value.

(98) For example, the check-function may also be one of the following functions or other known check-functions: a parity check-function applied to the least significant bits of some coefficient selected from the coefficient matrix using a binary pattern, and a parity check-function applied to a position index of the last or first non-zero coefficient or to a linear combination of last and first non-zero coefficient position index.

(99) In this respect, FIG. 9 shows an entropy decoding 901 of coefficients according to the prior art, and particularly according to the H.265 video coding standard. The entropy decoding 901 comprises decoding 902 X and Y coordinates of the last significant, i.e., non-zero, QTC. Then, a mask of QTCs significance values (significance mask) is signaled 903 according to a scan order, starting from the last significant QTC. Values and signs are parsed 904, 905 from the bitstream only for significant coefficient values.

(100) Hence, a length of the 1D significance mask can be derived from the scan order and coordinates of the last significant QTC. Obviously, it is not sufficient just to apply known data hiding methods to embed scan order indication data into QTCs, because QTCs are parsed from the bitstream using scan order information.

(101) FIG. 10 shows an embodiment of the present disclosure, and particularly an embodiment for improving the coding efficiency by reducing the signaling overhead in the bitstream 107, 207 generated by the encoder and received by the decoder.

(102) In the embodiment of FIG. 10, a scan order hiding within QTCs is possible. During encoding process, several different scan orders—indexed by SCAN_IDX—are applied during quantization 1001 and hiding 1002 stages. Quantization procedure 1001 may use scan information to estimate the number of bits (i.e. bit rate) to encode QTC values and to perform rate-distortion optimization by adjusting these QTC values with respect to the estimated bit rate.

(103) If the hiding has not been successful 1003, i.e. for example if the hiding condition is false, then another scan order SCAN_IDX is selected 1004. Preferably another scan order is selected until hiding is successful. If the selected scan is a default scan order, for example no hiding is performed.

(104) If hiding is successful or the selected scan order is the default on, then it is possible to reorder 1005 the QTCs according to default scan order. The next steps comprise serializing 1006 the QTCs and entropy encoding 1007. Said steps 1006 and 1007 may correspond to blocks 104 and 106 of FIG. 1. The serialization 1006 can also be inserted between 1001 and 1002 as it is the case in FIG. 1.

(105) Hiding 1002 comprises checking the hiding condition, and also modifying QTCs so that the hiding condition is met. This modification may include: altering QTCs values, setting QTCs values to zero and making insignificant (zero-valued) QTCs to be significant ones (non-zero). Obviously, it is always possible to adjust QTCs so that hiding condition is met. However, the QTCs adjustments at the encoder side is constrained by the distortion incurred by these adjustments, and reasonable adjustment constraints are applied. For example, because of quantization procedure a reasonable coefficient adjustment is plus or minus one. This constraint makes it possible that hiding operation may not be performed, i.e. there was no possible adjustments of QTCs to meet hiding condition (1003 evaluates to “no” case for non-default scans).

(106) At the decoder side, after entropy decoding 1011, hidden information is retrieved 1012 from serialized data, and therefore hiding stage also requires information on scan order that will be used at the decoder side so that it can be embedded with respect to the selected scan order. Data hiding procedure can also be performed jointly with quantization, like it is done e.g. for Sign Bit Hiding. However, hiding may fail for some of QTCs, because hiding condition is not met. For example, TU has a number of significant QTCs that is lower than a threshold. In this case further processing depends on whether a scan order is the default one. If default scan was used, decoder can derive it 1015 by applying the same hiding condition to parsed QTCs during entropy decoding stage. Otherwise, scan order is skipped and next scan order is being checked if available.

(107) If default scan order is in effect, reordering QTCs stage can be skipped, because the source and the target scans are the same ones. For non-default scan orders it is proposed to perform coefficients reorder, so that entropy encoding and entropy decoding stages can be performed without changes. A particular implementation may use remapping operation to avoid unnecessary copy operation for reordering, i.e. by redefining a match between coordinates of 2D QTC matrix and 1D position within a selected scan. At serialization/deserialization stage this remapping can provide CABAC context indices and last significant QTC coordinates for the given 1D scan position as if the QTCs were reordered.

(108) FIG. 11 shows a coefficient reorder according to the present disclosure, and particularly shows an example of QTCs reorder for a 4×4 block: reordering from diagonal to horizontal scan.

(109) In this respect, it is referred to the document “Transform Coefficient Coding in HEVC” by Joel Sole et al., IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 22, NO. 12, DECEMBER 2012, pages 1765-1777. In Section V.B of this document, it is stated that a significance flag is coded using a context model for each coefficient between the last one in scanning order (which is excluded) and the DC coefficient. For a 4×4 transform block TB, i.e. matrix of QTCs, the context depends on the position of the coefficient within the TB, as in H.264/AVC. Despite the fact that entropy encoding is performed for serialized and binarized data, context model for encoding a significance bit of a QTC is selected depending on the position of this QTC within a matrix of QTCs, and significance of spatially neighboring QTCs (right and lower). The state-of-the-art decoder parses significance bit from the bitstream using context model, that is selected according to the position of QTC for which this bit is being parsed and the positions of previously decoded significant QTCs. If the scan order is unavailable to the decoder, spatial position of QTC is undefined and hence, context model cannot be derived.

(110) The proposed reordering stage, as shown e.g. in FIG. 11, before entropy encoder, ensures that encoder and decoder will use the same scan order and the same context models for the encoded/decoded QTCs.

(111) FIG. 11 particularly describes a case when, after quantization, a matrix of QTCs was obtained (left-bottom part of it) with the last significant coefficient (for diagonal scan) located at (x=1,y=2). In case of diagonal scan 8 coefficient significance bits should be encoded.

(112) In order to select another scan order (e.g. by selector 109), e.g., horizontal scan instead of diagonal one, it may be beneficial to encode first two rows of QTCs bits plus two QTC bits of the third row (10 QTCs total). However, if these coefficient are reordered from diagonal scan to horizontal one (as shown in the upper part of FIG. 11), the position of the last the same 8 QTC bits should be encoded.

(113) For the entropy coding module 106, two scans are available: default one, that would be used by entropy decoding module 206 to parse the bitstream the scan selected by scan order selector 109.

(114) When the entropy coding module selects a context model according to QTCs position, it uses not just X,Y defined by scan order selector 109, but recalculate X,Y for the corresponding position of QTC after it is reordered.

(115) For example, in the example of FIG. 11, it is proposed to consider a case when scan order selector 109 has selected diagonal scan and the default scan is horizontal one. Entropy coding module 106 will encode coefficient placed at position (x=1, y=1) (marked as “E” for diagonal scan) with use context module of reordered position (x0, y=2) (also marked as “E” for horizontal scan), as well as neighboring coefficients will be defined not as “I” and “H”, but as “F” and “I”.

(116) This reordering operation can be implemented as a remap of X and Y coordinates from a selected scan to the default one, i.e. to implement this reorder it is not necessary to perform a memory copy/swap operations for QTCs but just to provide a look-up table for x an y coordinates for each of (selected scan, default scan) pair.

(117) Data hiding may use known methods to embed scan order into QTCs. However, in the present case of hiding the scan order, a further possibility consists in that a scan order may be specified by a condition applied to coordinates of the last significant QTC value (x, y), e.g:
mod(x+y,2)=scan_idx.  (C1)

(118) In this case encoder may modify position of the last significant QTC in order to indicate a scan that should be used by decoder. The hiding condition for the described hiding method is a set of coordinates specified for a scan order. In this respect, FIG. 12 shows an example of hiding conditions defined for scan orders.

(119) In FIG. 12, “X” marks indicate positions that are checked using condition (C1). It is also possible to combine this approach with data hiding within QTC values. For example, value retrieved from last significant QTC position may be used as a part of hiding condition for hiding within QTCs values.

(120) It is known that hiding is more efficient if host and target signals have a universal distribution. Another embodiment of this disclosure is the possibility to make the distribution of (C1) closer to universal by randomization. Specifically, an additional source of random noise R can be added:
mod(x+y+R,2)=scan_idx

(121) The value of R should be as uncorrelated to selected scan order as possible. For example, it may be a number of neighbor TUs, a parity value of a sum of reference sample values, or a total number of encoded bits.

(122) So, the disclosure proposes, to reduce the signaling overhead, to derive a scan order before QTCs deserialization, during entropy decoding. When hiding TU-related data (such as intra-prediction mode, filtering flag, etc.) the information being hidden is utilized after deserialization and dequantization stages. The disclosure proposes thus a possibility to use data hidden in QTCs before these coefficients are deserialized.

(123) The present disclosure describes a quantization procedure that is applicable to the residues obtained after prediction and transform processes used e.g. for moving pictures coding. The goal of the present disclosure is to improve the rate-distortion efficiency of quantization by extending the set of available scan orders selected using different coding features (e.g., intra-prediction mode, block size, partitioning mode) at the TU level. A particular implementation of this disclosure is presented as a technique that simultaneously uses mechanisms of mode-dependent and RDO-based scan selection.

(124) The present disclosure solves problems related to the RDO-based selection of scan orders. Particularly, it solves the problem that adaptive scan orders based on gathered statistics of previously encoded or decoded blocks do not always provide a better coding efficiency with respect to known pre-defined scan patterns. So, an RDO-based procedure for selecting just one scan among the content-adaptive generated scan orders and the pre-defined scan patterns is proposed as a solution.

(125) Particularly, the present disclosure solves the above-mentioned problem of increasing the coding efficiency of scan order selection in that both pre-defined scan patterns and adaptively generated scan orders are available.

(126) The present disclosure in its multimedia coding embodiments further on provides the advantage that it can be used in many potential applications in hybrid video coding framework that are compatible with Joint Exploration Model (JEM) that is the foundation for a next-generation video coding standard. A further advantage is the reduced BD-rate (Bjøntegaard Delta Rate) and subjective quality improvements in comparison with JEM1. A further advantage is that a computationally complex Adaptive Multiple Transform (AMT) also known as Enhanced Multiple Transform (EMT) may be replaced by a simpler adaptive scan order selection procedure.

(127) An aspect of the present disclosure is the combination of pre-defined scan patterns or orders with adaptively generated scan orders. Moreover, adding a signaling mechanism for a scan order selection procedure allows to significantly improve the process of generating adaptive scan orders for increasing its coding efficiency.

(128) The present disclosure has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed disclosure, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word “comprising” does not exclude other elements or steps and the indefinite article “a” or “an” does not exclude a plurality. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.