extracted from wipo:
formulas and tables are not copied:
Entropy Coding of Transform Coefficients suitable for Dependent Scalar

Quantization

Description

The present application is concerned with entropy coding of transform coefficient levels such as for coding a picture or a video.

In setting a quantization parameter, the encoder has to make a compromise. Rendering the quantization coarse reduces the bitrate, but increases the quantization distortion, and rendering the quantization finer decreases the distortion, but increases the bitrate. It would be favorable to have a concept at hand which increases the coding efficiency for a given domain of available quantization levels. One such possibility is the usage of dependent quantization where the quantization is steadily adapted depending on previously quantized and coded data, but the dependency in quantization also influences the interrelationship between the data items to be quantized and coded and thus influences the availability of information for context adaptive entropy coding. It would be favorable to have a concept which enables coding of coefficients of a transform block in a manner suitable for dependent quantization and effectively implementable by entropy coding in terms of coding efficiency.

It is the object of the present invention to provide such a concept for coding a bock of transform coefficients.

This object is achieved by the subject-matter Of the independent claims of the present application.

Advantageous aspects are the subject of dependent claims. Preferred embodiments of the present application are described below with respect to the figures among which:

Fig. 1 shows a block diagram of an exemplary video encoder as an example for a picture encoder which may be embodied to operate in accordance with any of the embodiments described below.

Fig. 2 shows a block diagram of (a) a transform encoder; and (b) a transform decoder to illustrate a basic approach of block-based transform coding;

Fig.3 shows a histogram of a distribution illustrating a uniform reconstruction quantizer.

Fig. 4 shows a schematic diagram of (a) a transform block subdivided into subblocks and (b) a subblock in order to illustrate an example for scanning of transform coefficient levels, here exemplarily one used in H.265 | MPEG- H HEVC; in particular, (a) shows a partitioning of a 18x16 transform block into 4x4 subblocks and the coding order of subblocks; (b) shows the coding order of transform coefficient levels inside a 4x4 subblock. The sub- divisioning may exemplarily be used in embodiments of the present application, for the passes of the coefficients in decoding their flags and remainders and for the state transitioning in dequantizing same.

Fig. 5 shows a schematic diagram of a multi-dimensional output space spanned by one axis per transform coefficient, and the location of admissible reconstruction vectors for the simple case of two transform coefficients: (a) Independent scalar quantization; (b) an example for dependent scalar quantization.

Fig. 6 shows a block diagram of a transform decoder using dependent scalar quantization, thereby forming an embodiment of a media decoder according to the present application. Modifications relative to conventional transform coding (with independent scalar quantizers) are derivable by comparison to Fig. 2b. In a corresponding manner, embodiments for encoding a transform block using dependent scalar quantization, may be obtained by modifying the encoder of Fig. 2a likewise.

Fig. 7 a schematic diagram illustrating for an embodiment of dependent quantization two sets of reconstruction levels that are completely determined by a single quantization steps size D. The two available sets of reconstruction levels are highlighted denoted set 0 (top line) and set 1 (bottom line). Examples for quantization indexes that indicate a reconstruction level inside a set are given by the numbers below the circles. The hollow and filled circles indicate two different subsets inside the sets of reconstruction levels; the subsets can be used for determining the set of reconstruction levels for the next transform coefficient in reconstruction order. Both sets include the reconstruction level equal to zero, but are otherwise disjoint; both sets are symmetric around zero.

Fig. 8 shows a pseudo-code illustrating an example for the reconstruction process for transform coefficients k represents an index that specifies the reconstruction order of the current transform coefficient, the quantization index for the current transform coefficient is denoted by level[k], the quantization step size Ak that applies to the current transform coefficient is denoted by quant_step_size[k], and trec[k] represents the value of the reconstructed transform coefficient tk' . The variable setld[k] specifies the set of reconstruction levels that applies to the current transform coefficient. It is determined based on the preceding transform coefficients in reconstruction order; the possible values of setld[k] are 0 and 1. The variable n specifies the integer factor of the quantization step size; it is given by the chosen set of reconstruction levels (i.e., the value of setld[k]) and the transmitted quantization index level[k]

Fig. 9 shows a pseudo-code illustrating an alternative implementation of the pseudo-code in Fig. 8 The main change is that the multiplication with the quantization step is represented using an integer implementation using a scale and a shift parameter. Typically, the shift parameter (represented by shift) is constant for a transform block and only the scale parameter (given by scale[k]) may depend on the location of the transform coefficient. The variable add represents a rounding offset, it is typically set equal to add = (1 «(shift-1 )). With Ak being the nominal quantization step for the transform coefficient, the parameters shift and scale[k] are chosen in a way that we have Ak « scale[k] • 2~shift.

Fig. 10 shows a schematic diagram of an example for a splitting of the sets of reconstruction levels into two subsets. The two shown quantization sets are the quantization sets of the example of Fig. 7. The two subsets of the quantization set 0 are labeled using“A” and“B”, and the two subsets of quantization set 1 are labeled using“C” and“D”.

Fig. 1 1 shows a pseudo-code illustrating a example for the reconstruction process of transform coefficients for a transform block. The array level represents the transmitted transform coefficient levels (quantization indexes) for the transform block and the array tree represent the corresponding reconstructed transform coefficients. The 2d table state_trans_table specifies the state transition table and the table setld specifies the quantization set that is associated with the states.

Fig. 12 shows a schematic diagram illustrating a state transition in dependent scalar quantization as trellis structure. The horizontal exists represents different transform coefficients in reconstruction order. The vertical axis represents the different possible states in the dependent quantization and reconstruction process. The shown connections specify the available paths between the states for different transform coefficients.

Fig. 13 shows an example of a basic trellis cell.

Fig. 14 shows a schematic diagram of a transform block for illustration of signaling of the position of the first non-zero quantization index in coding order which his position is illustrated by back filling. In addition to the position of the first non-zero transform coefficients, only bins for the shaded coefficients are transmitted, the white-marked coefficients are inferred to be equal to 0.

Fig. 15 shows a pseudo-code illustrating a comparison example for the coding of transform coefficient levels for a block of coefficients such as a subblock which may be easily transferred onto decoding a transform block not divided into subblocks and onto decoding of the coefficients (namely by replacing“code” by“decode”. Here, on pass is used to code all flags and remainder for the coefficients except the sign flags.

Fig. 16 shows a schematic diagram of a transform block and illustrates a template used for selecting probability models. The black square specifies the current scan position and the shaded squares represent the local neighborhood used for deriving the context models.

Fig. 17 shows a schematic diagram of an example trellis structure that can be exploited for determining sequences (or blocks) of quantization indexes that minimize a cost measures (such as an Lagrangian cost measure D + l • R). The trellis is shown for 8 transform coefficients (or quantization indexes). The first state (at the very left) -represents an initial state, which is set equal to 0.

Fig. 18 shows a pseudo-code illustrating an embodiment for the coding of transform coefficient levels for a block of coefficients such as a subblock which may be easily transferred onto decoding a transform block not divided into subblocks and onto decoding of the coefficients (namely by replacing“code” by“decode”. Here, on pass is used to code all flags and remainder for the coefficients except the sign flags. Here, the common pass of Fig. 15, is split into three passes.

Fig. 19 shows a pseudo-code illustrating an embodiment for the coding of transform coefficient levels for a block of coefficients such as a subblock which may be easily transferred onto decoding a transform block not divided into subblocks and onto decoding of the coefficients (namely by replacing“code” by“decode". Here, on pass is used to code all flags and remainder for the coefficients except the sign flags. Here, the common pass of Fig. 15, is split into two passes, one for the remainder, the other for the flags other than the sign flag.

Fig. 20 shows a pseudo-code illustrating an embodiment for the coding of transform coefficient levels for a block of coefficients such as a subblock which may be easily transferred onto decoding a transform block not divided into subblocks and onto decoding of the coefficients (namely by replacing“code” by“decode”. Here, on pass is used to code all flags and remainder for the coefficients except the sign flags. Here, the common pass

of Fig. 15, is split into several passes and the parity flags are coded before the absolute levels or coded before any other flag, respectively.

In accordance with the embodiments described next, entropy coding of transform coefficient levels is done in a manner suitable for an effective implementation along with dependent quantization and context adaptive entropy coding such as context adaptive binary arithmetic coding . The embodiments are particularly advantageous for entropy coding of transform coefficient levels in the context of transform coding with dependent scalar quantization. However, they are also useable and advantageous if used along with conventional independent scalar quantization. That is, they are also applicable for entropy coding of transform coefficient levels in the context of transform coding with conventional independent scalar quantization. Moreover, embodiments described hereinbelow are applicable for codecs that support a switch (e.g., on a sequence, picture, slice, tile, or block level) between transform coding with dependent quantization and transform coding with conventional independent quantization.

In the embodiments described below, transform coding is used to transform a set of samples. Quantization, which may be embodied as dependent scalar quantization, or, alternatively, as independent scalar quantization, is used to quantize the resulting transform coefficients, and an entropy coding of the obtained quantization indexes takes place. At the decoder side, the set of reconstructed samples is obtained by entropy decoding of the quantization indexes, a dependent reconstruction (or, alternatively, an independent reconstruction) of transform coefficients, and an inverse transform. The difference between dependent scalar quantization and conventional independent scalar quantization is that, for dependent scalar quantization, the set of admissible reconstruction levels for a transform coefficient depends on the transmitted transform coefficient levels that precede the current transform coefficient in reconstruction order. This aspect is exploited in entropy coding by using different sets of probability models for different sets of admissible reconstruction levels. In order to enable efficient hardware implementations, the binary decisions (referred to as bins) related to the transform coefficient levels of a block or subblock are coded in multiple passes. The binarization of the transform coefficient levels and the distribution of the binary decisions (also referred to as bins) over the multiple passes is chosen in a way that the data coded in the first pass uniquely determine the set of admissible reconstruction levels for the next scan position. This has the advantage that the probability models for a part of the bins in the first pass can be selected depending on set of admissible reconstruction levels (for a corresponding transform coefficient).

The description of embodiments below is mainly targeted on a lossy coding of blocks of prediction error samples in image and video codecs, but the embodiments can also be applied to other areas of lossy coding. In particular, no restriction to sets of samples that form rectangular blocks exists and there is no restriction to sets of samples that represent prediction error samples (i.e., differences between an original and a prediction signal) either.

All state-of-the-art video codecs, such as the international video coding standards H.264 j MPEG-4 AVC Fehler! Verweisquelle konnte nicht gefunden werden. and H.265 | MPEG-H HEVC Fehler! Verweisquelle konnte nicht gefunden werden. follow the basic approach of hybrid video coding. The video pictures are partitioned into blocks, the samples of a block are predicted using intra-picture prediction or inter-prediction, and the samples of the resulting prediction error signal (difference between the original samples and the samples of the prediction signal) are coded using transform coding.

Fig. 1 shows a simplified block diagram of a typical modern video encoder. The video pictures of a video sequence are coded in a certain order, which is referred to as coding order. The coding order of pictures can differ from the capture and display order. For the actual coding, each video picture is partitioned into blocks. A block comprises the samples of a rectangular area of a particular color component. The entity of the blocks of all color components that correspond to the same rectangular area is often referred to as unit. Depending on the purpose of the block partitioning, in H.265 j MPEG-H HEVC, it is distinguished between coding tree blocks (CTBs), coding blocks (CBs), prediction blocks (PBs), and transform blocks (TBs). The associated units are referred to as coding tree units (CTUs), coding units (CUs), prediction units (PUs), and transform units (TUs).

Typically, a video picture is initially partitioned into fixed sized units (i.e., aligned fixed sized blocks for all color components). In H.265 | MPEG-H HEVC, these fixed sized units are referred to as coding tree units (CTUs). Each CTU can be further split into multiple coding units (CUs). A coding unit is the entity for which a coding mode (for example, intra-or inter-picture coding) is selected. In H.265 j MPEG-H HEVC, the decomposition of a CTU into one or multiple CUs is specified by a quadtree (QT) syntax and transmitted as part of the bitstream. The CUs of a CTU are processed in the so-called z-scan order. That means, the four blocks that result from a split are processed in raster-scan order; and if any of the blocks is further partitioned, the corresponding four blocks (including the included smaller blocks) are processed before the next block of the higher splitting level is processed.

If a CU is coded in an intra-coding mode, an intra prediction mode for the luma signal and, if the video signal includes chroma components, another intra prediction mode for the chroma signals is transmitted. In ITU-T H.265 | MPEG-H HEVC, if the CU size is equal to the minimum CU size (as signaled in the sequence parameter set), the luma block can also be split into four equally sized blocks, in which case, for each of these blocks, a separate luma intra prediction mode is transmitted. The actual intra prediction and coding is done on the basis of transform blocks. For each transform block of an intra-picture coded CU, a prediction signal is derived using already reconstructed samples of the same color component. The algorithm that is used for generating the prediction signal for the transform block is determined by the transmitted intra prediction mode.

CUs that are coded in inter-picture coding mode can be further split into multiple prediction units (PUs). A prediction unit is the entity of a luma and, for color video, two associated chroma blocks (covering the same picture area), for which a single set of prediction parameters is used. A CU can be coded as a single prediction unit, or it can be split into two non-square (symmetric and asymmetric splittings are supported) or four square prediction units. For each PU, an individual set of motion parameters is transmitted. Each set of motion parameters includes the number of motion hypotheses (one or two in H.265 | MPEG-H HEVC) and, for each motion hypothesis, the reference picture (indicated via a reference picture index into a list of reference pictures) and the associated motion vector. In addition, H.265 | MPEG-H HEVC provides a so-called merged mode, in which the motion parameters are not explicitly transmitted, but derived based on motion parameters of spatial or temporal neighboring blocks. If a CU or PU is coded in merge mode, only an index into a list of motion parameter candidates (this list is derived using motion data of spatial and temporal neighboring blocks) is transmitted. The index completely determines the set of motion parameters used. The prediction signal for inter-coded PUs is formed by motion-compensated prediction. For each motion hypothesis (specified by a reference picture and a motion vector), a prediction signal is formed by a displaced block in the specified reference picture, where the displacement relative to the current PU is specified by the motion vector. The displacement is typically specified with sub-sample accuracy (in H.265 | MPEG-H HEVC, the motion vectors have

a precision of a quarter luma sample). For non-integer motion vectors, the prediction signal is generated by interpolating the reconstructed reference picture (typically, using separable FIR filters). The final prediction signal of PUs with multi-hypothesis prediction is formed by a weighted sum of the prediction signals for the individual motion hypothesis. Typically, the same set of motion parameters is used for luma and chroma blocks of a PU. Even though state-of-the-art video coding standards use translational displacement vectors for specifying the motion of a current area (block of samples) relative to a reference picture, it is also possible to employ higher-order motion models (for example, the affine motion model). In that case, additional motion parameters have to be transmitted for a motion hypothesis.

For both intra-picture and inter-picture coded CUs, the prediction error signal (also called residual signal) is typically transmitted via transform coding. In H.265 | MPEG-H HEVC, the block of luma residual samples of a CU as well as the blocks of chroma residual samples (if present) are partitioned into transform blocks (TBs). The partitioning of a CU into transform block is indicated by a quadtree syntax, which is also referred to as residual quadtree (RQT). The resulting transform blocks are coded using transform coding: A 2d transform is applied to the block of residual samples, the resulting transform coefficients are quantized using independent scalar quantization, and the resulting transform coefficient levels (quantization indexes) are entropy coded. In P and B slices, at the beginning of the CU syntax, a skip_flag is transmitted. If this flag is equal to 1 , it indicates that the corresponding CU consists of a single prediction unit coded in merge mode (i.e. , mergejlag is inferred to be equal to 1) and that all transform coefficients are equal to zero (i.e., the reconstruction signal is equal to the prediction signal). In that case, only the mergejdx is transmitted in addition to the skip_flag. If skip_flag is equal to 0, the prediction mode (inter or intra) is signaled, followed by the syntax features described above.

Since already coded pictures can be used for motion-compensated prediction of blocks in following pictures, the pictures have to be fully reconstructed in the encoder. The reconstructed prediction error signal for a block (obtained by reconstructing the transform coefficients given the quantization indexes and an inverse transform) is added to the corresponding prediction signal and the result is written to a buffer for the current picture. After all blocks of a picture are reconstructed, one or more in-loop filters can be applied (for example, a deblocking filter and a sample adaptive offset filter). The final reconstructed picture is then stored in a decoded picture buffer.

The embodiments described below present a concept for transform coding such as the transform coding of prediction error signals. The concept is applicable for both intrapicture and inter-picture coded blocks. It is also applicable to transform coding of non-rectangular sample regions. In contrast to conventional transform coding, the transform coefficients are, according to embodiments described below, not independently quantized. At least, they lend itself to be quantized using dependent quantization. According to dependent quantization, the set of available reconstruction levels for a particular transform coefficient depends on the chosen quantization indexes for other transform coefficients. Modifications for the entropy coding of quantization indexes are described below, which increase the coding efficiency and maintain capability of being combined with dependent scalar quantization.

All major video coding standards (including the state-of-the-art standard H.265 | MPEG-H HEVC) utilize the concept of transform coding for coding blocks of prediction error samples. The prediction error samples of a block represent the differences between the samples of the original signal and the samples of a prediction signal for the block. The prediction signal is either obtained by intra-picture prediction (in which case the samples of the prediction signal for a current block are derived based on already reconstructed samples of neighboring blocks inside the same picture) or by inter-picture prediction (in which case the samples of the prediction signal are derived based on samples of already reconstructed pictures). The samples of the original prediction error signal are obtained by subtracting the values of the samples of the prediction signal from the samples values of the original signal for the current block.

T ransform coding of sample blocks consists of a linear transform, scalar quantization, and entropy coding of the quantization indexes. At the encoder side (see Fig. 2a), an N*M block of original samples is transformed using a linear analysis transform A. The result is an N*M block of transform coefficients. The transform coefficients tk represent the original prediction error samples in a different signal space (or different coordinate system). The N*M transform coefficients are quantized using N*M independent scalar quantizers. Each transform coefficient tk is mapped to a quantization index qk, which is also referred to as transform coefficient level. The obtained quantization indexes qk are entropy coded and written to the bitstream.

At the decoder side, which is depicted in Fig. 2b, the transform coefficient levels qk are decoded from the received bitstream. Each transform coefficient level <¾ is mapped to a reconstructed transform coefficient t’k. The NcM block of reconstructed samples is obtained by transforming the block of reconstructed transform coefficients using a linear synthesis transform B.

Even though video coding standards only specify the synthesis transform B, it is common practice that the inverse of the synthesis transform B is used as analysis transform A in an encoder, i.e. , A = B-1. Moreover, the transforms used in practical video coding systems represent orthogonal transforms (B~1 = BT) or nearly orthogonal transforms. For orthogonal transforms, the mean squared error (MSE) distortion in the signal space is equal to the MSE distortion in the transform domain. The orthogonality has the important advantage that the MSE distortion between an original and reconstructed sample block can be minimized using independent scalar quantizers. Even if the actual quantization process used in an encoder takes dependencies between transform coefficient levels (introduced by the entropy coding description above) into account, the usage of orthogonal transforms significantly simplifies the quantization algorithm.

For typical prediction error signals, the transform has the effect that the signal energy is concentrated in a few transform coefficients. In comparison to the original prediction error samples, the statistical dependencies between the resulting transform coefficients are reduced.

In state-of-the-art video coding standards, a separable discrete cosine transform (type II) or an integer approximation thereof is used. The transform can, however, be easily replaced without modifying other aspects of the transform coding system. Examples for improvements that have been suggested in the literature or in standardization documents include:

• Usage of discrete sine transform (DST) for intra-picture predicted blocks (possibly depending on the intra prediction mode and/or the block size). Note that H.265 | MPEG-H HE VC already includes a DST for intra-picture predicted 4x4 transform blocks.

• Switched transforms: The encoder selects the actually used transform among a set of pre-defined transforms. The set of available transforms is known by both the encoder and the decoder, so that it can be efficiently signaled using an index into a list of available transforms. The set of available transforms and their ordering in a list can depend on other coding parameters for the block, such as the chosen infra prediction mode. In a special case, the used transform is completely determined by coding parameters such as the intra prediction mode, so that no syntax element for specifying the transform needs to be transmitted.

• Non-separable transforms: The transforms used in encoder and decoder represent non-separable transforms. Note that the concept of switched transforms may include one or more non-separable transforms. Due to complexity reasons, the usage of non-separable transforms can be restricted to certain block sizes.

• Multi-level transforms: The actual transform is composed of two or more transform stages. The first transform stage could consist of a computationally low-complex separable transform. And in the second stage a subset of the resulting transform coefficients is further transformed using a non-separable transform. It comparison to a non-separable transform for the entire transform block, the two-stage approach has the advantage that the more complex non-separable transform is applied to a smaller number of samples. The concept of multi-level transforms can be efficiently combined with the concept of switched transforms.

The transform coefficients are quantized using scalar quantizers. As a result of the quantization, the set of admissible values for the transform coefficients is reduced. In other words, the transform coefficients are mapped to a countable set (in practice, a finite set) of so-called reconstruction levels. The set of reconstruction levels represents a proper subset of the set of possible transform coefficient values. For simplifying the following entropy coding, the admissible reconstruction levels are represented by quantization indexes (also referred to as transform coefficient levels), which are transmitted as part of the bitstream. At the decoder side, the quantization indexes (transform coefficient levels) are mapped to reconstructed transform coefficients. The possible values for the reconstructed transform coefficients correspond to the set of reconstruction levels. At the encoder side, the result of scalar quantization is a block of transform coefficient levels (quantization indexes),

In state-of-the-art video coding standards, uniform reconstruction quantizers (URQs) are used. Their basic design is illustrated in Fig.3. URQs have the property that the reconstruction levels s are equally spaced. The distance D between two neighboring reconstruction levels is referred to as quantization step size. One of the reconstruction levels is equal to 0. Hence, the complete set of available reconstruction levels is uniquely specified by the quantization step size D. The decoder mapping of quantization indexes q to reconstructed transform coefficients V is, in principle, given by the simple formula

t' = q A

In this context, the term“independent scalar quantization” refers to the property that, given the quantization index q for any transform coefficient, the associated reconstructed transform coefficient t' can be determined independently of all quantization indexes for the other transform coefficients.

Since video decoders typically utilize integer arithmetic with standard precision (e.g., 32 bits), the actual formula used in the standard can slightly differ from the simple multiplication. When neglecting the clipping to the supported dynamic range for the transform coefficients, the reconstructed transform coefficients in H.265 | MPEG-H HEVC are obtained by

t' = (scale • q + (l « (shift - 1))) » shift,

where the operators“«" and“»” represent bit shifts to the left and right, respectively. When we ignore the integer arithmetic, the quantization step size D corresponds to the term

D = scale 2~shlft.

Older video coding standards, such as H.262 | MPEG-2 Video, also specify modified URQs for which the distances between the reconstruction level zero and the first non-zero reconstruction levels are increased relative to the nominal quantization step size (e.g., to three halves of the nominal quantization step size D).

The quantization step size (or the scale and shift parameters) for a transform coefficient is determined by two factors:

Quantization parameter QP: The quantization step size can typically be modified on a block basis. For that purpose, video coding standards provide a predefined set of quantization step sizes. The used quantization step size (or, equivalently

the parameters“scale” and“shift” introduced above) is indicated using an index into the predefined list of quantization step sizes. The index is called quantization parameter (QP). In H.265 | MPEG-H HEVC, the relationship between QP and the quantization step size is approximately given by

D « const 2 6

A slice QP is typically transmitted in the slice header. In general, it is possible to modify the quantization parameter QP on the basis of blocks. For that purpose, a DQP (delta quantization parameter) can be transmitted. The used quantization parameter is determined by the transmitted DQP and a predicted QP value, which is derived using the QPs of already coded (typically neighboring) blocks.

• Quantization weighting matrix: Video coding standards often provide the possibility to use different quantization step sizes for individual transform coefficients. This is achieved by specifying so-called quantization weighting matrices w, which can be selected by the encoder, typically on a sequence or picture level, and are transmitted as part of the bitstream. A quantization weighting matrix w has the same size as the corresponding block of transform coefficients. The quantization step size DίA for a transform coefficient tik is given by

Aik = wik ' Ablock<

where Ablock denotes the quantization step size (indicated by the block quantization parameter QP) for the considered block, i and k represent the coordinates specifying the current transform coefficient inside the transform block, and wik represents the corresponding entry in the quantization weighting matrix w.

The main intention of quantization weighting matrices is to provide a possibility for introducing the quantization noise in a perceptual meaningful way. By using appropriate weighting matrices, the spatial contrast sensitivity of human vision can be exploited for achieving a better trade-off between bit rate and subjective reconstruction quality. Nonetheless, many encoders use a so-called flat quantization matrix (which can be efficiently transmitted using high-level syntax elements). In this case, the same

quantization step size A is used for all transform coefficients in a block. The quantization step size is then completely specified by the quantization parameter QP.

The block of transform coefficient levels (quantization indexes for the transform coefficients) are entropy coded (i.e., it is transmitted in a lossless manner as part of the bitstream). Since the linear transform can only reduce linear dependencies, the entropy coding for the transform coefficient levels is typically designed in a way that remaining non-linear dependencies between transform coefficient levels in a block can be exploited for an efficient coding. Well known examples are the run-level coding in MPEG-2 Video, the run-level-last coding in H.263 and MPEG-4 Visual, the context-adaptive variable length coding (CAVLC) in H.264 | MPEG-4 AVC, and context-based adaptive binary arithmetic coding (CABAC) in H.264 | MPEG-4 AVC and H.265 | MPEG-H HEVC.

The CABAC specified in the state-of-the-art video coding standard H.265 | MPEG-H HEVC follows a generic concept that can be applied for a large variety of transform block sizes. Transform blocks that are larger than 4x4 samples are partitioned into 4x4 subblocks. The partitioning is illustrated in Fig. 4a and b for the example of a 16x16 transform block. The coding order of the 4x4 subblocks, shown in Fig. 4a, as well as the coding order of the transform coefficient levels inside a subblock, shown in Fig. 4b, are, in general, specified by the reverse diagonal scan shown in the figures. For certain intrapicture predicted blocks, a horizontal or vertical scan pattern is used (depending on the actual intra prediction mode). The coding order always starts with high-frequency locations.

In H.265 | MPEG-H HEVC, the transform coefficient levels are transmitted on the basis of 4x4 subblocks. The lossless coding of transform coefficient levels includes the following steps:

1. A syntax element coded_block_flag is transmitted, which signals whether there are any non-zero transform coefficient levels in the transform block. If coded_block_flag is equal to 0, no further data are coded for the transform block.

2. The x and y coordinates of the first non-zero transform coefficient level in coding order (e.g., the block-wise reverse diagonal scan order illustrated in Fig. 4) are transmitted. The transmission of the coordinates is split into a prefix and suffix part. The standard uses the syntax elements last_sig_coeff_x_prefix, last_sig_coeff_y_prefix, I a st_s ig_coeff_x_s uffix, and last_sig_coeff_x_suffix.

Starting with the 4x4 subblock that contains the first non-zero transform coefficient level in coding order, the 4x4 subblocks are processed in coding order, where the coding of a subblock includes the following main steps:

a. A syntax element coded_sub_block_flag is transmitted, which indicates whether the subblock contains any non-zero transform coefficient levels. For the first and last 4x4 subblock (i.e., the subblocks that contain the first non-zero transform coefficient level or the DC level), this flag is not transmitted but inferred to be equal to one.

b. For all transform coefficient levels inside a subblock with coded_sub_block_flag equal to one, the syntax element significant_coeff_flag indicates whether the corresponding transform coefficient level is not equal to zero. This flag is only transmitted if its value cannot be inferred based on already transmitted data. In particular, the flag is not transmitted for the first significant scan position (specified by the transmitted x and y coordinates) and it is not transmitted for the DC coefficient if the DC coefficient is located in a different subblock than the first non-zero coefficient (in coding order) and all other significant_coeff_flags for the last subblock are equal to zero.

c. For the first eight transform coefficient levels with significant_coeff_flag equal to one (if any), the flag coeff_a bs Je ve l_g reate r 1 _f I ag is transmitted. It indicates whether the absolute value of the transform coefficient level is greater than one.

d. For the first transform coefficient level with coeff_a bs_level_g reater 1 _f I ag equal to one (if any), the flag c0eff_abs_level_greater2_flag is transmitted. It indicates whether the absolute value of the transform coefficient level is greater than two.

e. For all levels with significant_coeff_flag equal to one (an exception is described below), the syntax element coeff_sign_flag is transmitted, which specifies the sign of the transform coefficient level.

f. For all transform coefficient levels for which the absolute value is not already completely specified by the values of significant_coeff_flag, coeff_abs_level_greater1_flag and coeff_a bsj eve l_g reate r2_f I ag (the absolute value is completely specified if any of the transmitted flags is equal to zero), the remainder of the absolute value is transmitted using the multi-level syntax element coeff_abs_Jevel_remaining

In H.265 | MPEG-H HEVC, all syntax elements are coded using context-based adaptive binary arithmetic coding (CABAC). All non-binary syntax elements are first mapped onto a series of binary decisions, which are also referred to as bins. The resulting bin sequence is coded using binary arithmetic coding. For that purpose, each bin is associated with a probability model (binary probability mass function), which is also referred to as a context. For most bins, the context represents an adaptive probability model, which means that the associated binary probability mass function is updated based on the actually coded bin values. Conditional probabilities can be exploited by switching the contexts for certain bins based on already transmitted data. CABAC also includes a so-called bypass mode, in which the fixed probability mass function (0.5, 0.5) is used.

The context that is chosen for the coding of the coded_sub_block_flag depends on the values of coded_sub_block_flag for already coded neighboring subblocks. The context for the significant_coeff_flag is selected based on the scan position (x and y coordinate) inside a subblock, the size of the transform block, and the values of coded_sub_block_flag in neighboring ' subblocks. For the flags coeff_abs_level_greater1_flag and coeff_abs_level_greater2_flag, the context selection depends on whether the current subblock includes the DC coefficient and whether any coeff_abs_level_greater1_flag equal to one has been transmitted for the neighboring subblocks. For the coeff_abs Jevel_greater1 _flag , it further depends on the number and the values of the already coded coeff_abs_level_greater1_flag’s for the subblock.

The signs coeff_sign_flag and the remainder of the absolute values coeff_abs_level_remaining are coded in the bypass mode of the binary arithmetic coder. For mapping coeff_abs_level_remaining onto a sequence of bins (binary decisions), an adaptive binarization scheme is used. The biharization is controlled by a single parameter, which is adapted based on already coded values for the subblock.

H.265 | MPEG-H HEVC also includes a so-called sign data hiding mode, in which (under certain conditions) the transmission of the sign for that last non-zero level inside a subblock is omitted. Instead, the sign for this level is embedded in the parity of the sum of the absolute values for the levels of the corresponding subblock. Note that the encoder has to consider this aspect in determining appropriate transform coefficient levels.

Video coding standards only specify the bitstream syntax and the reconstruction process. If we consider transform coding for a given block of original prediction error samples and given quantization step sizes, the encoder has a lot a freedom. Given the quantization indexes qk for a transform block, the entropy coding has to follow a uniquely defined algorithm for writing the data to the bitstream (i.e. , constructing the arithmetic codeword). But the encoder algorithm for obtaining the quantization indexes ¾ given an original block of prediction error samples is out of the scope of video coding standards. Furthermore, the encoder has the freedom to select a quantization parameter QP on a block basis. For the following description, we assume that the quantization parameter QP and the quantization weighting matrix are given. Hence, the quantization step size for each transform coefficient is known. We further assume that the encoder performs an analysis transform that is the inverse (or a very close approximation of the inverse) of the specified synthesis transform for obtaining original transform coefficients tk. Even under these conditions, the encoder has the freedom to select a quantizer index qk for each original transform coefficient tk. Since the selection of transform coefficient levels determines both the distortion (or reconstruction/approximation quality) and the bit rate, the quantization algorithm used has a substantial impact on the rate-distortion performance of the produced bitstream.

The simplest quantization method rounds the original transform coefficients tk to the nearest reconstruction levels. For the typically used URQs, the corresponding quantization index ¾ can be determined according to

% = sgn(

where sgn() is the sign function and the operator [-J returns the largest integer that is smaller or equal to its argument. This quantization methods guarantees that the MSE distortion

is minimized, but it completely ignores the bit rate that is required for transmitting the resulting transform coefficient levels qk. Typically, better results are obtained if the rounding is biased towards zero:

c|k - sgn(

The best result in rate-distortion sense is obtained if the quantization process minimizes a Lagrangian function D + A • R, where D represent the distortion (e.g., MSE distortion) of the transform block, R specifies the number of bits that are required for transmitting the transform coefficient levels of the block, and A is a Lagrange multiplier.

QP

For codecs that use the relationship D « const • 2 6 between QP and quantization step size (such as H.264 | MPEG-4 AVC or H.265 | MPEG-H HEVC), the following relationship between the Lagrange multiplier A and the block quantization parameter QP is often used

QP

A = ct • D2 = c2 • 2 3 ,

where c and c2 represent constant factors for a slice or picture.

Quantization algorithms that aim to minimize a Lagrange function D + l • R of distortion and rate are also referred to as rate-distortion optimized quantization (RDOQ). If we measure the distortion using the MSE or a weighted MSE, the quantization indexes ¾ for a transform block should be determined in a way so that the following cost measure is minimized:

At this, the transform coefficient index k specifies the coding order (or scanning order) of transform coefficient levels. The term i?(¾j¾_1, ijfc„2, ••• ) represents the number of bits (or an estimate thereof) that are required for transmitting the quantization index qk. The condition illustrates that (due to the usage of combined or conditional probabilities) the number of bits for a particular transform coefficient level qk typically depends on the chosen values for preceding transform coefficient levels qk- qk-2> etc. in coding order. The factors ak in the equation above can be used for weighting the contribution of the individual transform coefficients, e.g., for modelling the contrast sensitivity of human vision. In the following, we generally assume that all weightings factor ak are equal to 1 (but the algorithm can be straightforwardly modified in a way that different weighting factors can be taken into account).

For the transform coefficient coding in H.265 | MPEG-H HEVC, an accurate computation of the rate terms is very complicated, since most binary decisions are coded using adaptive probability models. But if we neglect some aspects of the probability model selection and ignore that the probability models are adapted inside a transform block, it is possible to design an RDOQ algorithm with reasonable complexity. The RDOQ algorithm implemented in the reference software for H.265 | MPEG-H HEVC consists of the following basic processing steps:

1. For each scanning position k, a transform coefficient level qk is selected by minimizing the Lagrangian cost Dk{qk) + l • Rk{q ) under the assumption that the level is not inferred to be equal to zero. Dk{qk) denotes the (weighted) squared error Dk(qk) = ak • (tk - Ak qk)2 and Rk{qk ) represents an estimate of the number of bits required for transmitting qk.

2. The flags coded_sub_block_flag for the 4x4 subblocks are determined by comparing the Lagrangian costs for the following two cases: (a) The transform coefficient levels selected in step Fehler! Verweisquelle konnte nicht gefunden werden. are used; (b) The syntax element coded_sub_block_flag is set equal to zero and, thus, all transform coefficient levels of the 4x4 subblock are set equal to zero.

3. The location of the first non-zero transform coefficient levels is determined by comparing the Lagrangian costs that are obtained by choosing one of the non-zero transform coefficient levels (after step Fehler! Verweisquelle konnte nicht gefunden werden.) as first non-zero transform coefficient levels in coding order (the preceding transform coefficient levels are set equal to zero).

4. The coded_block_f!ag is determined by comparing the Lagrangian costs for the sequence of transform coefficient levels obtained after step Fehler! Verweisquelle konnte nicht gefunden werden. and the case that all transform coefficient levels inside the transform block are set equal to zero.

In [3], a modified concept for transform coding is proposed, which is described in the following in more detail. The main change relative to conventional transform coding is that the transform coefficients are not independently quantized and reconstructed. Instead, the admissible reconstruction levels for a transform coefficient depend on the selected quantization indexes for the preceding transform coefficients in reconstruction order. The concept of dependent scalar quantization is combined with a modified entropy coding, in which the probability model selection (or, alternatively, the codeword table selection) for a transform coefficient depends on the set of admissible reconstruction levels.

The advantage of the dependent quantization of transform coefficients is that the admissible reconstruction vectors are denser packed in the W-dimensional signal space (where N denotes the number of samples or transform coefficients in a transform block). The reconstruction vectors for a transform block refer to the ordered reconstructed transform coefficients (or, alternatively, the ordered reconstructed samples) of a transform block. This effect is illustrated in Fig. 5a and b for the simplest case of two transform coefficients. Fig. 5a shows the admissible reconstruction vectors (which represent points in the 2d plane) for independent scalar quantization. As it can be seen, the set of admissible values for the second transform coefficient t[ does not depend on the chosen value for the first reconstructed transform coefficient t0' . Fig. 5b shows an example for dependent scalar quantization. Note that, in contrast to independent scalar quantization, the selectable reconstruction values for the second transform coefficient t depend on the chosen reconstruction level for the first transform coefficient t0' . In the example of Fig. 5b, there are two different sets of available reconstruction levels for the second transform coefficient t[ (illustrated by different colors). If the quantization index for the first transform coefficient t0' is even (... ,-2,0,2,... ), any reconstruction level of the first set (blue points) can be selected for the second transform coefficient t[. And if the quantization index for the first transform coefficient t0' is odd (... ,-3,-1 , 1 ,3,...), any reconstruction level of the second set (red points) can be selected for the second transform coefficient t . In the example, the reconstruction levels for the first and second set are shifted by half the quantization step size (any reconstruction level of the second set Is located between two reconstruction levels of the first set).

The dependent scalar quantization of transform coefficients has the effect that, for a given average number of reconstruction vectors per /V-dimensional unit volume, the expectation value of the distance between a given input vector of transform coefficients and the nearest available reconstruction vector is reduced. As a consequence, the average distortion between the input vector of transform coefficients and the vector reconstructed transform coefficients can be reduced for a given average number of bits. In vector quantization, this effect is referred to as space-filling gain. Using dependent scalar quantization for transform blocks, a major part of the potential space-filling gain for highdimensional vector quantization can be exploited. And, in contrast to vector quantization,

the implementation complexity of the reconstruction process (or decoding process) is comparable to that of conventional transform coding with independent scalar quantizers.

A block diagram of a transform decoder with dependent scalar quantization is illustrated in Fig. 6. The main change pertains to the dependent quantization leading to the arrows pointing from top to bottom. As indicated by these vertical arrows, the reconstructed transform coefficient tk, with reconstruction order index k > 0 does not only depend on the associated quantization index qk, but also on the quantization indexes q0, ί?i, ••• , ¾-i for preceding transform coefficients in reconstruction order. Note that in dependent quantization, the reconstruction order of transform coefficients has to be uniquely defined. The performance of the overall transform codec can be improved if the knowledge about the set of reconstruction levels associated with a quantization index qk is also exploited in the entropy coding. That means, it is advantageous to switch contexts (probability models) or codeword tables based on the set of reconstruction levels that applies to a transform coefficient.

As in conventional transform coding, transform encoding in accordance with embodiments outlined herein involve, besides an analysis transform, a quantization algorithm and entropy coding. As analysis transform typically the inverse of the synthesis transform (or a close approximation of the inverse) is used, and the entropy coding is usually uniquely specified given the entropy decoding process. But, similar as in conventional transform coding, there is a lot of freedom for selecting the quantization indexes given the original transform coefficients.

Dependent quantization of transform coefficients refers to a concept in which the set of available reconstruction levels for a transform coefficient depends on the chosen quantization indexes for preceding transform coefficients in reconstruction order (inside the same transform block). The set of admissible reconstruction levels for a current transform coefficient is selected (based on the quantization indexes for preceding transform coefficients in coding order) among two pre-defined sets of reconstruction levels.

Similarly as for conventional independent scalar quantization, a block-based quantization parameter (QP) determines a quantization step size D (or corresponding scale and shift parameters as described above) and all reconstruction levels (in all sets of reconstruction levels) represent integer multiples of the quantization step size D. But each set of

reconstruction levels includes only a subset of the integer multiples of the quantization step size D. Such a configuration for dependent quantization, in which all possible reconstruction levels for all sets of reconstruction levels represent integer multiples of the quantization step size, can be considered of an extension of uniform reconstruction quantizers (URQs). its basic advantage is that the reconstructed transform coefficients can be calculated by algorithms with a very low computational complexity.

The quantization step size Ak for a particular transform coefficient tk (with k indicating the reconstruction order) may not be solely determined by the block quantization parameter QP, but it is also possible that the quantization step size Ak for a particular transform coefficient tk is determined by a quantization weighting matrix and the block quantization parameter. Typically, the quantization step size Ak for a transform coefficient tk is given by the product of the weighting factor wk for the transform coefficient tk (specified by the quantization weighting matrix) and the block quantization step size Ablock (specified by the block quantization parameter),

D/c - w AMock.

It should be noted that the actual calculation of reconstructed transform coefficients tk' (or the actual calculation of reconstruction levels) may slightly deviate from an ideal multiplication due to integer implementations or other implementation aspects. Let Ak be the quantization step size for a particular transform coefficient tfcand let nk specify a nominal integer factor of the quantization step size (e.g., given by the quantization index qk). With ideal multiplication, the reconstructed transform coefficient tk is given by

tk' = nk • Ak.

Due to a restriction to integer implementations, the reconstructed transform coefficient tk' (or a corresponding reconstruction level) may be actually determined according to

tk' = (¾ ' scale + (1 « (shift - 1))) » shift, with scale • 2-shlft » A ,

or a similar procedure. If we speak of integer multiples of a quantization step size in the following description, the corresponding text also applies to integer approximations similar to the one specified above.

The dependent scalar quantization for transform coefficients proposed in [3] uses two different sets of reconstruction levels and all reconstruction levels of the two sets for a transform coefficient tk represent integer multiples of the quantization step size Ak for this transform coefficient (which is, at least partly, determined by a block-based quantization parameter). Note that the quantization step size Ak just represents a scaling factor for the admissible reconstruction values in both sets. Except of a possible individual quantization step size Ak for the different transform coefficients tk inside a transform block (and, thus, an individual scaling factor), the same two sets of reconstruction levels are used for all transform coefficients.

In Fig. 7, the preferred configuration for the two sets of reconstruction levels t is illustrated. The reconstruction levels that are contained in the first quantization set (labeled as set 0 in the figure) represent the even integer multiples of the quantization step size. The second quantization set (labeled as set 1 in the figure) contains all odd integer multiples of the quantization step size and additionally the reconstruction level equal to zero. Note that both reconstruction sets are symmetric about zero. The reconstruction level equal to zero is contained in both reconstruction sets, otherwise the reconstruction sets are disjoint. The union of both reconstruction sets contains all integer multiples of the quantization step size.

The reconstruction level that the encoder selects among the admissible reconstruction levels are transmitted inside the bitstream. As in conventional independent scalar quantization, this can be achieved using so-called quantization indexes, which are also referred to as transform coefficient levels. Quantization indexes (or transform coefficient levels) are integer numbers that uniquely identify the available reconstruction levels inside a quantization set (i.e. , inside a set of reconstruction levels). The quantization indexes are sent to the decoder as part of the bitstream (using any entropy coding technique). At the decoder side, the reconstructed transform coefficients can be uniquely calculated based on a current set of reconstruction levels (which is determined by the preceding quantization indexes in coding/reconstruction order) and the transmitted quantization index for the current transform coefficient.

The assignment of quantization indexes to reconstruction levels inside a set of reconstruction levels (or quantization set) may follow the following rule as may be seen in Fig. : The quantization index equal to 0 is assigned to the reconstruction level equal to 0. The quantization index equal to 1 is assigned to the smallest reconstruction level greater

than 0, the quantization index equal to 2 is assigned to the next reconstruction level greater than 0 (i.e., the second smallest reconstruction level greater than 0), etc. Or, in other words, the reconstruction levels greater than 0 are labeled with integer numbers greater than 0 (i.e., with 1 , 2, 3, etc.) in increasing order of their values. Similarly, the quantization index -1 is assigned to the largest reconstruction level smaller than 0, the quantization index -2 is assigned to the next (i.e., the second largest) reconstruction level smaller than 0, etc. Or, in other words, the reconstruction levels smaller than 0 are labeled with integer numbers less than 0 (i.e., -1 , -2, -3, etc.) in decreasing order of their values. The reconstruction process for a transform coefficient could be implemented similar to the algorithm specified in the pseudo-code of Fig. .

In the pseudo-code of Fig. , level[k] denotes the quantization index that is transmitted for a transform coefficient tk and setld[k] (being equal to 0 or 1 ) specifies the identifier of the current set of reconstruction levels (it is determined based on preceding quantization indexes in reconstruction order as will be described in more detail below). The variable n represents the integer multiple of the quantization step size given by the quantization index levelfk] and the set identifier setld[k]÷ If the transform coefficient is coded using the first set of reconstruction levels (setld[k] == 0), which contains the even integer multiples of the quantization step size Ak, the variable n is two times the transmitted quantization index. If the transform coefficient is coded using the second set of reconstruction levels (setld[k] == 1), we have the following three cases: (a) if level[k] is equal to 0, n is also equal to 0; (b) if level[k] is greater than 0, n is equal to two times the quantization index level[k] minus 1 ; and (c) if level[k] is less than 0, n is equal to two times the quantization index levelfk] plus 1. This can be specified using the sign function

sign(x) =

Then, if the second quantization set is used, the variable n is equal to two times the quantization index level[k] minus the sign function sign(level[k]) of the quantization index.

Once the variable n (specifying the integer factor of the quantization step size) is determined, the reconstructed transform coefficient tk' is obtained by multiplying n with the quantization step size Ak.

As mentioned above, instead of an exact multiplication with the quantization step size Ak, the reconstructed transform coefficient tk' can be obtained by an integer approximation. This is illustrated in the pseudo-code in Fig. . Here, the variable shift represents a bit shift to the right. Its value typically depends only on the quantization parameter for the block (but it is also possible that the shift parameter can be changed for different transform coefficients inside a block). The variable scale[k] represents a scaling factor for the transform coefficient tk; in addition to the block quantization parameter, it can, for example, depend on the corresponding entry of the quantization weighting matrix. The variable "add” specifies a rounding offset, it is typically set equal to add = (1 «(shift-1)). It should be noted that the integer arithmetic specified in the pseudo-code of Fig. (last line) is, with exception of the rounding, equivalent to a multiplication with a quantization step size Ak, given by

Ak = scale [fc] • 2 -shift

Another (purely cosmetic) change in Fig. relative to Fig. is that the switch between the two sets of reconstruction levels is implemented using the ternary if-then-else operator ( a ? b : c ), which is known from programming languages such as the C programming language.

Besides the selection of the sets of reconstruction levels discussed above, another task in dependent scalar quantization in transform coding is the algorithm used for switching between the defined quantization sets (sets of reconstruction levels). The used algorithm determines the“packing density” that can be achieved in the A -dimensSonal space of transform coefficients (and, thus, also in the /V-dimensional space of reconstructed samples). A higher packing density eventually results in an increased coding efficiency.

In the concept presented in [3], the set of reconstruction levels for the next transform coefficients is determined based on a partitioning of the quantization sets, as it is illustrated in Fig. . Each of the two quantization sets is partitioned into two subsets. The first quantization set (labeled as set 0) is partitioned into two subsets (which are labeled as A and B) and the second quantization set (labeled as set 1) is also partitioned into two subsets (which are labeled as C and D). In Fig. and Fig. , the partitioning of the quantization sets into subsets is indicated by hollow and filled circles. The following partitioning rules apply:

• Subset A consists of all even quantization indexes of the quantization set 0;

• Subset B consists of all odd quantization indexes of the quantization set 0;

• Subset C consists of all even quantization indexes of the quantization set 1 ;

• Subset D consists of all odd quantization indexes of the quantization set 1.

The used subset is not explicitly indicated inside the bitstream. Instead, it can be derived based on the used quantization set (e.g., set 0 or set 1) and the actually transmitted quantization index. The subset can be derived by a bit-wise “and” operation of the transmitted quantization index level and 1. Subset A consists of at! quantization indexes of set 0 for which (levels 1) is equal to 0, subset B consists of all quantization indexes of set 0 for which (level&1) is equal to 1 , subset C consists of all quantization indexes of set 1 for which (!evel&l) is equal to 0, and subset D consists of all quantization indexes of set 1 for which (level&1) is equal to 1.

The transition between the quantization sets (set 0 and set 1 ) is represented by a state variable; which has four possible values (0, 1 , 2, 3). On the one hand, the state variable specifies the quantization set that is used for the current transform coefficient. The quantization set 0 is used if and only if the state variable is equal to 0 or 1 , and the quantization set 1 is used if and only if the state variable is equal to 2 or 3. On the other hand, the state variable also specifies the possible transitions between the quantization sets. Fehler! Verweisquelle konnte nicht gefunden werden. shows the state transition table used. Given a current state, it specifies the quantization set for the current transform coefficient (second column). It further specifies the state transition based on the path that is associated with the chosen quantization index (the path specifies the used subset A, B, C, or D if the quantization set is given). In reconstructing the transform coefficients for a block, it is sufficient to update a state variable and determine the path of the used quantization index.

Table 1 : Preferred example of a state transition table for a configuration with 4 states.

The path is given by the parity of the quantization index. With level[ k ] being the current quantization index, it can be determined according to

path = ( levelf k ] & 1 ),

where the operator & represents a bit-wise“and” in two-complement integer arithmetic.

Using the concept of state transition, the current state and, thus, the current quantization set is uniquely determined by the previous state (in reconstruction order) and the previous quantization index, such as its parity in the present example. The first state for a transform block is set equal to 0.

The concept of state transition for the dependent scalar quantization allows low-complexity implementations for the reconstruction of transform coefficients in a decoder. A preferred example for the reconstruction process of transform coefficients of a single transform block is shown in Fig. 7 using C-style pseudo-code.

In the pseudo-code of Fig. 7, the index k specifies the reconstruction order of transform coefficients. It should be noted that, in the example code, the index k decreases in reconstruction order. The last transform coefficient has the index equal to k = 0. The first index kstart specifies the reconstruction index (or, more accurately, the inverse reconstruction index) of the first reconstructed transform coefficient. The variable kstart may be set equal to the number of transform coefficients in the transform block minus 1 , or it may be set equal to the index of the first non-zero quantization index (for example, if the location of the first non-zero quantization index is transmitted in the applied entropy coding method) in coding/reconstruction order. In the latter case, all preceding transform coefficients (with indexes k > kstart) are inferred to be equal to 0. The reconstruction process for each single transform coefficient is the same as in the example of Fig. . As for the example in Fig. , the quantization indexes are represent by level[k] and the associated reconstructed transform are represented by trec[k]. The state variable is represented by state. Note that in the example of Fig. 7, the state is set equal to 0 at the beginning of a transform block. The 1d table setld[] specifies the quantization sets that are associated with the different values of the state variable and the 2d table state_trans_table[][] specifies the state transition given the current state (first argument) and the path (second argument). The path is given by the parity of the quantization index (using the bit-wise and operator &).

Instead of the table setld[], a simple arithmetic operation can be used; for example, a bit-shift to the right:

setld[ state ] = state » 1

Similarly, the table state_trans_table[][] can also be implemented using simple arithmetic operations. For example,

state_trans_table[ state ][ path ] =

( 32040 » ( ( state « 2 ) + ( path « 1 ) ) ) & 3

At this, the complete state transition table is given by the 16-bit value“32040”. Note that by replacing the value“32040” with“0”, we can easily switch between dependent and independent quantization. The value“0" represents a state transition table, that always chooses the state 0 and thus the conventional uniform reconstruction quantizer Q0.

The state transition in dependent quantization can also be represented using a trellis structure, as is illustrated in Fig.2. The trellis shown in this figure corresponds to the state transitions specified in Fehler! Verweisquelle kotinte nicht gefunden werden.. For each state, there are two paths that connect the state for a current transform coefficient with two possible states for the next transform coefficient in reconstruction order. The paths are labeled with path 0 and path 1 , this number corresponds to the path variable that was introduced above (for a preferred embodiment, that path variable is equal to the parity of the quantization index). Note that each path uniquely specifies a subset (A, B, C, or D) for the quantization indexes. In Fig., the subsets are specified in parentheses. Given an initial state (the state 0), the path through the trellis is uniquely specified by the transmitted quantization indexes.

For the example in Fig., the states (0, 1 , 2, and 3) have the following properties:

• State 0: The previous quantization index level[k-1] specifies a reconstruction level of set 0 and the current quantitation index level[k] specifies a reconstruction level of set 0.

• State 1 : The previous quantization index leve![k-1] specifies a reconstruction level of set 1 and the current quantitation index level[k] specifies a reconstruction level of set 0.

• State 2: The previous quantization index level[k-1] specifies a reconstruction level of set 0 and the current quantitation index !evel[k] specifies a reconstruction level of set 1.

• State 0: The previous quantization index level[k-1] specifies a reconstruction level of set 1 and the current quantitation index level[k] specifies a reconstruction level of set 1.

The trellis consists of a concatenation of so-called basic trellis cells. The basic trellis cell is shown in Fig.

An aspect of dependent scalar quantization as outlined above is that there are different sets of admissible reconstruction levels (also called quantization sets) for the transform coefficients. The quantization set for a current transform coefficient is determined based on the values of the quantization index for preceding transform coefficients. If we compare the two quantization sets, it is obvious that the distance between the reconstruction level equal to zero and the neighboring reconstruction levels is larger in set 0 than in set 1. Hence, the probability that a quantization index is equal to 0 is larger if set 0 is used and it is smaller if set 1 is used. For an efficient coding, this aspect is exploited in the entropy coding by switching probability models based on the quantization sets (or states) that are used for a current quantization index.

Note that for a suitable switching of probability models, the path (association with a subset of the used quantization set) of all preceding quantization indexes should be known when entropy decoding a current quantization index (or a corresponding binary decision of a current quantization index). For that purpose, in the codec proposed in [3], the transform coefficients are coded in reconstruction order. The quantization indexes are coded using binary arithmetic coding similar to H.264 | MPEG-4 AVC or H.265 j MPEG-H HEVC. The non-binary quantization indexes are first mapped onto a series of binary decisions (which are commonly referred to as bins). The quantization indexes are transmitted as absolute value and, for absolute values greater than 0, a sign.

Similarly as for HEVC, the transform coefficient levels of a transform block are coded on the basis of subblocks. First, a flag coded_block_flag is transmitted, which specifies

whether or not the transform block contains any non-zero transform coefficient levels. If Goded_bIock_flag is equal to 0 (i.e., the block does not contain any non-zero levels), no further information is transmitted for the transform block. Otherwise (coded_block_flag is equal to 1), the following applies:

• The x and y coordinate of the first non-zero level in coding order. As illustrated in Fehler! Verweisquelle konnte nicht gefunden werden., the transmitted location of the first non-zero level specifies that all transform coefficients that precede the identified coefficient in coding order (marked white in Fehler! Verweisquelle konnte nicht gefunden werden.) are inferred to be equal to zero. Further data are only transmitted for the coefficient at the specified location (marked black in Fehler! Verweisquelle konnte nicht gefunden werden.) and the coefficients that follow this coefficient in coding order (marked shaded in Fehler! Verweisquelle konnte nicht gefunden werden.). The example in Fehlerl Verweisquelle konnte nicht gefunden werden. shows a 16x16 transform block with 4x4 subblocks; the used coding order is the subblock-wise diagonal scan specified in H.265 | MPEG-H HEVC.

* For the subblocks that precede that subblock containing the first non-zero level (indicated by the transmitted x and y coordinate), a flag coded_subblock_flag is transmitted, which specifies whether or not the subblock contains any non-zero transform coefficient levels. As an exception, the coded_subblock_flag is not transmitted for the subblock that contains the DC coefficient. For this subblock, the coded_subblock_flag is inferred to be equal to 1.

Finally, for all subblocks with coded_subblbck_flag equal to 1 as well as for the subblock that contains the first non-zero level in coding order, the values of the transform coefficient levels are coded as illustrated by the pseudo-code in Fehlerl Verweisquelle konnte nicht gefunden werden.. At this, firstScanldSbb represents the first scan index inside a subblock. For the subblock that contains the first non-zero level (indicated by the transmitted x and y coordinate), firstScanldSbb is equal to the scan index firstNonZero that corresponds to the transmitted (x,y) coordinate. For the other transmitted subblocks, firstScanldSbb specifies the first scan index inside the subblock. The scan index lastScanldSbb specifies the last scan index inside the subblock. Note that all coefficients inside a subblock are coded before any coefficient of the next subblock in coding order is coded.

The levels of a subblock are coded in two passes. In the first pass, the absolute values are transmitted and in the second pass, the signs are transmitted for all coefficients with absolute values not equal to zero. The absolute values are coded as follows:

• A flag sig_flag is transmitted, which specifies whether or not the absolute level is greater than zero. This flag is not transmitted if it can be inferred to be equal to 1 , i.e., when any of the following conditions applies:

o the current scan index k is equal to the scan index of the first non-zero level (as indicated by the transmitted x and y coordinates); o the current scan index is the last scan index inside a subblock, a coded_subblock_flag equal to 1 has been transmitted for the subblock, and all previous levels in the subblock are equal to 0.

• If sig_flag is equal to 1 (i.e., the absolute level is greater than 0), another flag gt1_flag is transmitted, which specifies whether or not the absolute level is greater than one.

• If sig_flag and gt1_flag are equal to 1 (i.e., the absolute level is greater than 1), another flag gt2_flag is transmitted, which specifies whether or not the absolute level is greater than two.

• If sig_flag, gt1_flag and gt2_flag are equal to 1 (i.e., the absolute level is greater than 2), another flag gt3_flag is transmitted, which specifies whether or not the absolute level is greater than three.

• If sig_f(ag, gt1_flag, gt2_flag and gt3_flag are equal to 1 (i.e., the absolute level is greater than 3), another flag gt4_flag is transmitted, which specifies whether or not the absolute level is greater than four.

• If sig_f!ag, gt1_flag, gt2_flag, gt3_flag and gt4_flag are equal to 1 (i.e., the absolute level is greater than 4), the syntax element gt3_flag is transmitted which specifies the absolute value minus 5.

After the absolute values for all levels of a subblock are transmitted, the sign bits sign_flag are transmitted for all coefficients with absolute levels not equal to zero.

The flags sig_flag, gt1_flag, gt2_flag, gt3_flag and gt4_flag coded using adaptive probability models (also referred to as contexts). For these flags, one of multiple adaptive probability models are selected as follows:

Let state be the current value of the state variable for a transform coefficient (the state variable is determined based on the parity of already coded levels in coding order). Let diag specify the diagonal position of a current scan position (diag = x+y, where x and y specify the x and y coordinate of the scan position). Furthermore, let sumAbsTemplate be the sum of already coded absolute values in a local neighborhood illustrated in Fehler! Verweisquelle konnte nicht gefunden werden., with the corresponding neighborhood being indicated by way of shading those coefficients belonging to the neighborhood of the coefficient whose bin is currently coded which is drawn black, in turn. And let numSigTemplate be the number of absolute levels greater than 0 in the same local neighborhood.

For the sig_flag, the selected probability model depends on:

• The diagonal (given by the sum of the x and y coordinate) of the current scan position;

• The quantizer (Q0 or Q1 , given by state » 1) that is used for the current transform coefficients;

• The sum of already coded absolute levels in a local neighbourhood given by sumAbsTemplate.

For the gt1_flag, the selected probability model depends on:

• The diagonal (given by the sum of the x and y coordinate) of the current scan position;

• The quantizer (Q0 or Q1 , given by state » 1 ) that is used for the current transform coefficients;
Claims

1. Apparatus for decoding a block (10) of transform coefficients (12), configured to

in one or more first passes (20) of scanning the transform coefficients,

decode (16), using context-adaptive entropy decoding, a significance flag for the transform coefficients which indicates whether a quantization index of the transform coefficients is zero,

decode (18) a parity flag for the transform coefficients which indicates a parity of the transform coefficients,

in one or more second passes (22) of scanning the transform coefficients, including or excluding one or more of the one or more first passes (20),

decode (24), using context-adaptive entropy decoding, one or more greatness flags for transform coefficients the quantization index of which is not zero,

in one or more third passes (26, 27),

decode (28, 30), using equiprobability entropy decoding,

a remainder of the quantization index of the transform coefficients the one or more greatness flags of which are positive and

a sign of the quantization index of the transform coefficients the quantization index of which is not zero.

2. Apparatus of claim 1 , configured to

in one first pass (20), for a currently scanned transform coefficient,

decode, using context-adaptive entropy decoding, the significance flag for the currently scanned transform coefficient and

if the significance flag indicates that the quantization index of the currently scanned transform coefficient is not zero, decode, for the currently scanned transform coefficient, using context-adaptive entropy decoding, the parity flag for the currently scanned transform coefficient.

3. Apparatus of claim 1 , configured to

in one of the one or more first passes, for a currently scanned transform coefficient,

decode, using context-adaptive entropy decoding, the parity flag for the currently scanned transform coefficient and

in a further one of the one or more first passes, for a currently scanned transform coefficient,

if the parity flag indicates that the quantization index of the currently scanned transform coefficient is even, decode, for the currently scanned transform coefficient, using context-adaptive entropy decoding, the significance flag for the currently scanned transform coefficient.

4. Apparatus of any of claims 1 to 3, configured to

in the one or more second passes, for a currently scanned transform coefficient,

if the quantization index of the currently scanned transform coefficient is not zero, decode, using context-adaptive entropy decoding, a first greatness flag for the currently scanned transform coefficient.

5. Apparatus of claim 4, configured to

compute, for a predetermined transform coefficient, the quantization index according to a sum, addends of which are formed by

the significance flag of the predetermined transform coefficient,

the parity flag of the predetermined transform coefficient,

two times a sum of the remainder of the predetermined transform coefficient and the first greatness flag

6. Apparatus of claim 4, configured to

in the one or more second passes, for a currently scanned transform coefficient,

if the first greatness flag of the currently scanned transform coefficient is positive, decode, using context-adaptive entropy decoding, a second greatness flag for the currently scanned transform coefficient.

7. Apparatus of claim 6, configured to

compute, for a predetermined transform coefficient, the absolute value of the quantization index according to a sum, addends of which are formed by

the significance flag of the predetermined transform coefficient,

the parity flag of the predetermined transform coefficient,

two times a sum of the remainder of the predetermined transform coefficient, the first greatness flag and the second greatness flag.

8. Apparatus of claim 6, configured to

compute, for a predetermined transform coefficient, the absolute value of the quantization index according to a sum, addends of which are formed by

the significance flag of the predetermined transform coefficient,

the parity flag of the predetermined transform coefficient,

the first greatness flag of the predetermined transform coefficient, and

two times a sum of the remainder of the predetermined transform coefficient and the second greatness flag.

9. Apparatus of any of claims 6 to 8,

configured to perform the decoding of the first greatness flag and the second greatness flag in separate second passes, and/or

wherein the one or more second passes exclude the one or more first passes.

10. Apparatus of any of claims 1 to 9, configured to perform

each of the one or more second passes after each of the one or more first passes, and

each of the one or more third passes after each of the one or more second passes.

11. Apparatus of any of claims 1 to 9, wherein the one or more first passes are included in the one or more second passes.

12. Apparatus of claim 11 , wherein the significance flag, the parity flag and the one or more greatness flags of the transform coefficients (12) are decoded in one pass.

13. Apparatus of claim 1 , configured to

in one of the one or more first passes, for a currently scanned transform coefficient,

decode, using context-adaptive entropy decoding, the significance flag for the currently scanned transform coefficient,

after the one first pass, in the one or more second passes,

decode, using context-adaptive entropy decoding, a sequence of more than one greatness flags for the transform coefficients,

after the one or more second passes, in a further one of the one or more first passes, decode, using equiprobability entropy decoding, the parity flag for the transform coefficients the quantization index of which is not zero.

14. Apparatus of any of the preceding claims, wherein the transform coefficient of the block are partitioned into subblocks (14), and the transform coefficients are decoded subblock by subblock, so that each transform coefficients of a subblock (14) is decoded before the transform coefficients of a next subblock.

15. Apparatus of any of the previous claims, wherein binary arithmetic decoding is used as entropy decoding, and the remainder is decoded by decoding bins of a binarization of an absolute value of the quantization index of the transform coefficients.

16. Apparatus of any of claims 1 to 15, configured to

dequantize the quantization index of each transform coefficient the quantization index of which is not zero by

selecting(42), for the respective transform coefficient, a set of reconstruction levels out of a plurality of reconstruction level sets depending on parities of quantization indices of transform coefficients preceding, along a scanning order (44), the respective transform coefficient, and

dequantizing the respective transform coefficient onto one level of the set (48) of reconstruction levels which is indexed by the quantization index of the respective transform coefficient.

17. Apparatus of claim 16, configured to

Perform the selecting, for the respective transform coefficient, the set (48) of reconstruction levels out of a plurality of reconstruction level sets (52) using a state transitioning by

selecting (42) the set of reconstruction levels out of the plurality of reconstruction level sets uniquely based on a state which the state transitioning assumes for the respective transform coefficient,

updating (45) the state of the state transitioning for a transform coefficient succeeding in the scanning order depending on the parity of the quantization index of the respective transform coefficient.

18. Apparatus of claim 17, configured to perform the

the one or more first passes, and/or

the one or more second passes, and/or

the one or more third passes,

along the scanning order.

19. Apparatus of claim 17 or 18, configured to perform the state transitioning transitions between four distinct states.

20. Apparatus of any of claims 16 to 19, configured to

parametrize the plurality of reconstruction level sets by way of a predetermined quantization step size and derive information on the predetermined quantization step size from the data stream.

21 . Apparatus of any of claims 17 to 20 wherein each of the plurality of reconstruction level sets consists of multiples of a predetermined quantization step size which is constant for the plurality of reconstruction level sets.

22. Apparatus of any of claims 16 to 21 , wherein the number of reconstruction level sets of the plurality of reconstruction level sets is two and the plurality of reconstruction level sets comprises

a first reconstruction level set comprising zero and even multiples of a predetermined quantization step size, and

a second reconstruction level set comprising zero and odd multiples of the predetermined quantization step size.

23. Apparatus of claim 22, configured to select the first reconstruction level set for the state values 0 and 1 , and select the second reconstruction level set for the state values 2 and 3.

24. Apparatus of any of claims 1 to 23, configured to

decode, using context-adaptive entropy decoding, the significance flag for a predetermined transform coefficient by selecting a context depending on

a coefficient position of the predetermined transform coefficient inside the transform block.

25. Apparatus of any of claims 1 to 24, configured to

decode, using context-adaptive entropy decoding, the significance flag for a predetermined transform coefficient (50) by

determining a local activity based on a set of flags decoded prior to the significance flag of the predetermined transform coefficient for a set of neighboring transform coefficients (51) within a local template (52) around the predetermined transform coefficient, and

selecting a context depending on the local activity.

26. Apparatus of claim 25, configured to

Decode, sequentially, the significance flag, the parity flag and a first of the one or more greatness flags in one first pass so that the set of flags comprises the significance flag, the parity flag and the first of the one or more greatness flags decoded for the set of neighboring transform coefficients, and to compute the activity based on a sum over an addend for each of the neighboring transform coefficients, the addends indicating a minimally assumed index or a minimally assumed reconstruction level for the neighboring transform coefficients determined based on the significance flag, the parity flag and the first of the one or more greatness flags decoded for the neighboring transform coefficients.

27. Apparatus of any of claims 1 to 26, configured to

Perform the selecting, for the respective transform coefficient, the set of reconstruction levels out of a plurality of reconstruction level sets using a state transitioning by

selecting the set of reconstruction levels out of the plurality of reconstruction level sets uniquely based on a state which the state transitioning assumes for the respective transform coefficient,

updating the state of the state transitioning a transform coefficient succeeding in the scanning order depending on the parity of the quantization index of the respective transform coefficient,

perform the one or more first passes along the scanning order, and

decode, using context-adaptive entropy decoding, the significance flag for a predetermined transform coefficient by selecting a context depending on

the state which the state transitioning assumes for the predetermined transform coefficient (13’).

28. Apparatus of claim 27, configured to

decode, using context-adaptive entropy decoding, the significance flag for a predetermined transform coefficient by selecting a context set comprising the context depending on the state and select the context out of the context set depending on a local activity around, or a coefficient position of the predetermined transform coefficient.

29. Apparatus of claim 28, configured to select a first context set for states 0 and 1 , a second context set for state 2, and a third context set for state 3.

30. Apparatus of any of claims 1 to 29, configured to

dequantize the quantization index of each transform coefficient the quantization index of which is not zero by

selecting, for the respective transform coefficient, a set of reconstruction levels out of a plurality of reconstruction level sets depending on parities of quantization indices of transform coefficients preceding, along a scanning order, the respective transform coefficient, and

dequantizing the respective transform coefficient onto one level of the set of reconstruction levels which is indexed by the quantization index of the respective transform coefficient,

perform the one or more first passes along the scanning order, and

decode, using context-adaptive entropy decoding, the significance flag for a predetermined transform coefficient by selecting a context depending on

the set of reconstruction levels selected for the predetermined transform coefficient.

31. Apparatus of any of claims 1 to 30, configured to

decode, using context-adaptive entropy decoding, the parity flag for a predetermined transform coefficient by selecting a context depending on

a coefficient position of the predetermined transform coefficient.

32. Apparatus of any of claims 1 to 31 , configured to

decode, using context-adaptive entropy decoding, the parity flag for a predetermined transform coefficient by

determining a local activity based on a set of flags decoded prior to the parity flag of the predetermined transform coefficient for a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, and/or a number of transform coefficients within the local template around the predetermined transform coefficient, the reconstruction level of which is not zero, and

selecting a context depending on the local activity and/or the number of transform coefficients.

33. Apparatus of claim 32, configured to select the context depending on a difference between the local activity and the number of transform coefficients.

34. Apparatus of claim 32 or 33, configured to

Decode, sequentially, the significance flag, the parity flag and a first of the one or more greatness flags in one first pass so that the set of flags comprises the significance flag, the parity flag and the first of the one or more greatness flags decoded for the set of neighboring transform coefficients, and to compute the activity based on a sum over an addend for each of the neighboring transform coefficients, the addends indicating a minimally assumed index or a minimally assumed reconstruction level for the neighboring transform coefficients determined based on the significance flag, the parity flag and the first of the one or more greatness flags decoded for the neighboring transform coefficients.

35. Apparatus of any of claims 1 to 34, configured to

decode, using context-adaptive entropy decoding, a first of the one or more greatness flags for a predetermined transform coefficient by selecting a context depending on

a coefficient position of the predetermined transform coefficient.

36. Apparatus of any of claims 1 to 35, configured to

decode, using context-adaptive entropy decoding, the first greatness flag for a predetermined transform coefficient by

determining a local activity based on a set of flags decoded prior to the first greatness flag of the predetermined transform coefficient for a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, and/or a number of transform coefficients within the local template around the predetermined transform coefficient, the reconstruction level of which is not zero, and

selecting a context depending on the local activity and/or the number of transform coefficients.

37. Apparatus of claim 36, configured to select the context depending on a difference between the local activity and the number of transform coefficients.

38. Apparatus of claim 36 or 37, configured to

Decode, sequentially, the significance flag, the parity flag and a first of the one or more greatness flags in one first pass so that the set of flags comprises the significance flag, the parity flag and the first of the one or more greatness flags decoded for the set of neighboring transform coefficients, and to compute the local activity based on a sum over an addend for each of the neighboring transform coefficients, the addends indicating a minimally assumed index or a minimally assumed reconstruction level for the neighboring transform coefficients determined based on the significance flag, the parity flag and the first of the one or more greatness flags decoded for the neighboring transform coefficients.

39. Apparatus of any of claims 1 to 38, configured to decode the remainder for a predetermined transform coefficient using a Golomb-Rice code and using a Rice parameter which depends on a sum over an addend for each of out of a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, the addend depending on a quantization index or a reconstruction level for the respective neighboring transform coefficient.

40. Apparatus for encoding a block of transform coefficients, configured to

in one or more first passes of scanning the transform coefficients,

encode, using context-adaptive entropy encoding, a significance flag for the current transform coefficients which indicates whether a quantization index of the current transform coefficients is zero,

encode a parity flag for the transform coefficients which indicates a parity of the transform coefficients,

in one or more second passes of scanning the transform coefficients, including or excluding one or more of the one or more first passes,

encode, using context-adaptive entropy encoding, one or more greatness flags for transform coefficients the quantization index of which is not zero,

in one or more third passes,

encode, using equiprobability entropy encoding,

a remainder of the quantization index of the transform coefficients the one or more greatness flags of which are positive and

a sign of the quantization index of the transform coefficients the quantization index of which is not zero.

41. Apparatus of claim 40, configured to

in one first pass, for a currently scanned transform coefficient,

decode, using context-adaptive entropy encoding, the significance flag for the currently scanned transform coefficient and

if the significance flag indicates that the quantization index of the currently scanned transform coefficient is not zero, encode, for the currently scanned transform coefficient, using context-adaptive entropy encoding, the parity flag for the currently scanned transform coefficient.

42. Apparatus of claim 40, configured to

in one of the one or more first passes, for a currently scanned transform coefficient,

encode, using context-adaptive entropy encoding, the parity flag for the currently scanned transform coefficient and

in a further one of the one or more first passes, for a currently scanned transform coefficient,

if the parity flag indicates that the quantization index of the currently scanned transform coefficient is even, encode, for the currently scanned transform coefficient, using context-adaptive entropy encoding, the significance flag for the currently scanned transform coefficient.

43. Apparatus of any of claims 33 to 42, configured to

in the one or more second passes, for a currently scanned transform coefficient,

if the quantization index of the currently scanned transform coefficient is not zero, encode, using context-adaptive entropy encoding, a first greatness flag for the currently scanned transform coefficient.

44. Apparatus of claim 43, configured so that

for a predetermined transform coefficient, the quantization index is obtainable according to a sum, addends of which are formed by

the significance flag of the predetermined transform coefficient,

the parity flag of the predetermined transform coefficient,

two times a sum of the remainder of the predetermined transform coefficient and the first greatness flag.

45. Apparatus of claim 44, configured to

in the one or more second passes, for a currently scanned transform coefficient,

if the first greatness flag of the currently scanned transform coefficient is positive, encode, using context-adaptive entropy encoding, a second greatness flag for the currently scanned transform coefficient.

46. Apparatus of claim 45, configured to

for a predetermined transform coefficient, the quantization index is obtainable according to a sum, addends of which are formed by

the significance flag of the predetermined transform coefficient,

the parity flag of the predetermined transform coefficient,

two times a sum of the remainder of the predetermined transform coefficient, the first greatness flag and the second greatness flag.

47. Apparatus of claim 45, configured to

for a predetermined transform coefficient, the quantization index is obtainable according to a sum, addends of which are formed by

the significance flag of the predetermined transform coefficient,

the parity flag of the predetermined transform coefficient,

the first greatness flag of the predetermined transform coefficient, and

two times a sum of the remainder of the predetermined transform coefficient and the second greatness flag.

48. Apparatus of any of claims 45 to 47, configured to

configured to perform the encoding of the first greatness flag and the second greatness flag in separate second passes, and/or

wherein the one or more second passes exclude the one or more first passes.

49. Apparatus of any of claims 33 to 48, configured to perform

each of the one or more second passes after each of the one or more first passes, and

each of the one or more third passes after each of the one or more second passes.

50. Apparatus of any of claims 40 to 49, wherein the one or more first passes are included in the one or more second passes.

51. Apparatus of claim 50, wherein the significance flag, the parity flag and the one or more greatness flags of the transform coefficients (12) are decoded in one pass.

52. Apparatus of claim 40, configured to

in one of the one or more first passes, for a currently scanned transform coefficient,

encode, using context-adaptive entropy encoding, the significance flag for the currently scanned transform coefficient,

after the one first pass, in the one or more second passes,

encode, using context-adaptive entropy decoding, a sequence of more than one greatness flags for the transform coefficients,

after the one or more second passes, in a further one of the one or more first passes,

encode, using equiprobability entropy encoding, the parity flag for the transform coefficients the quantization index of which is not zero.

53. Apparatus of any of claims 40 to 52, wherein the transform coefficient of the block are partitioned into subblocks (14), and the transform coefficients are encoded subblock by subblock, so that each transform coefficients of a subblock (14) is encoded before the transform coefficients of a next subblock.

54. Apparatus of any of claims 40 to 53, wherein binary arithmetic encoding is used as entropy encoding, and the remainder is encoded by encoding bins of a binarization of an absolute value of the quantization index of the transform coefficients.

55. Apparatus of any of claims 40 to 54, configured to

quantize the quantization index of each transform coefficient the quantization index of which is not zero by

selecting, for the respective transform coefficient, a set of reconstruction levels out of a plurality of reconstruction level sets depending on parities of quantization indices of transform coefficients preceding, along a scanning order, the respective transform coefficient, and

quantizing the respective transform coefficient onto one level of the set of reconstruction levels which is indexed by the quantization index of the respective transform coefficient.

56. Apparatus of claim 55, configured to

Perform the selecting, for the respective transform coefficient), the set of reconstruction levels out of a plurality of reconstruction level sets using a state transitioning by

selecting the set of reconstruction levels out of the plurality of reconstruction level sets uniquely based on a state which the state transitioning assumes for the respective transform coefficient,

updating the state of the state transitioning a transform coefficient succeeding in the scanning order depending on the parity of the quantization index of the respective transform coefficient.

57. Apparatus of claim 56, configured to perform the

the one or more first passes, and/or

the one or more second passes, and/or

the one or more third passes,

along the scanning order.

58. Apparatus of claim 56 or 57, configured to perform the state transitioning transitions between four distinct states.

59. Apparatus of any of claims 55 to 58, configured to

parametrize the plurality of reconstruction level sets by way of a predetermined quantization step size and derive information on the predetermined quantization step size from the data stream.

60. Apparatus of any of claims 56 to 59 wherein each of the plurality of reconstruction level sets consists of multiples of a predetermined quantization step size which is constant for the plurality of reconstruction level sets.

61. Apparatus of any of claims 55 to 60, wherein the number of reconstruction level sets of the plurality of reconstruction level sets is two and the plurality of reconstruction level sets comprises

a first reconstruction level set comprising zero and even multiples of a predetermined quantization step size, and

a second reconstruction level set comprising zero and odd multiples of the predetermined quantization step size.

62. Apparatus of claim 61 , configured to select the first reconstruction level set for the state values 0 and 1 , and select the second reconstruction level set for the state values 2 and 3.

63. Apparatus of any of claims 40 to 62, configured to

encode, using context-adaptive entropy encoding, the significance flag for a predetermined transform coefficient by selecting a context depending on

a coefficient position of the predetermined transform coefficient inside the transform block.

64. Apparatus of any of claims 40 to 63, configured to

encode, using context-adaptive entropy encoding, the significance flag for a predetermined transform coefficient by

determining a local activity based on a set of flags decoded prior to the significance flag of the predetermined transform coefficient for a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, and

selecting a context depending on the local activity.

65. Apparatus of claim 64, configured to

encode, sequentially, the significance flag, the parity flag and a first of the one or more greatness flags in one first pass so that the set of flags comprises the significance flag, the parity flag and the first of the one or more greatness flags decoded for the set of neighboring transform coefficients, and to compute the activity based on a sum over an addend for each of the neighboring transform coefficients, the addends indicating a minimally assumed index or a minimally assumed reconstruction level for the neighboring transform coefficients determined based on the significance flag, the parity flag and the first of the one or more greatness flags decoded for the neighboring transform coefficients.

66. Apparatus of any of claims 40 to 65, configured to

Perform the selecting, for the respective transform coefficient, the set of reconstruction levels out of a plurality of reconstruction level sets using a state transitioning by

selecting the set of reconstruction levels out of the plurality of reconstruction level sets uniquely based on a state which the state transitioning assumes for the respective transform coefficient,

updating the state of the state transitioning a transform coefficient succeeding in the scanning order depending on the parity of the quantization index of the respective transform coefficient,

perform the one or more first passes along the scanning order, and

encode, using context-adaptive entropy encoding, the significance flag for a predetermined transform coefficient by selecting a context depending on

the state which the state transitioning assumes for the predetermined transform coefficient (13’).

67. Apparatus of claim 66, configured to

encode, using context-adaptive entropy encoding, the significance flag for a predetermined transform coefficient by selecting a context set comprising the context depending on the state and select the context out of the context set depending on a local activity around, or a coefficient position of the predetermined transform coefficient.

68. Apparatus of claim 76, configured to select a first context set for states 0 and 1 , a second context set for state 2, and a third context set for state 3.

69 Apparatus of any of claims 40 to 68, configured to

quantize the quantization index of each transform coefficient the quantization index of which is not zero by

selecting, for the respective transform coefficient, a set of reconstruction levels out of a plurality of reconstruction level sets depending on parities of quantization indices of transform coefficients preceding, along a scanning order, the respective transform coefficient, and

dequantizing the respective transform coefficient onto one level of the set of reconstruction levels which is indexed by the quantization index of the respective transform coefficient,

perform the one or more first passes along the scanning order, and

encode, using context-adaptive entropy encoding, the significance flag for a predetermined transform coefficient by selecting a context depending on

the set of reconstruction levels selected for the predetermined transform coefficient.

70. Apparatus of any of claims 40 to 69, configured to

encode, using context-adaptive entropy encoding, the parity flag for a predetermined transform coefficient by selecting a context depending on

a coefficient position of the predetermined transform coefficient

71 Apparatus of any of claims 40 to 70, configured to

encode, using context-adaptive entropy encoding, the parity flag for a predetermined transform coefficient by

determining a local activity based on a set of flags decoded prior to the parity flag of the predetermined transform coefficient for a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, and/or a number of transform coefficients within the local template

around the predetermined transform coefficient, the reconstruction level of which is not zero, and

selecting a context depending on the local activity and/or the number of transform coefficients.

72. Apparatus of claim 71 , configured to select the context depending on a difference between the local activity and the number of transform coefficients.

73. Apparatus of claim 71 or 72, configured to

encode, sequentially, the significance flag, the parity flag and a first of the one or more greatness flags in one first pass so that the set of flags comprises the significance flag, the parity flag and the first of the one or more greatness flags decoded for the set of neighboring transform coefficients, and to compute the activity based on a sum over an addend for each of the neighboring transform coefficients, the addends indicating a minimally assumed index or a minimally assumed reconstruction level for the neighboring transform coefficients determined based on the significance flag, the parity flag and the first of the one or more greatness flags decoded for the neighboring transform coefficients.

74. Apparatus of any of claims 40 to 73, configured to

encode, using context-adaptive entropy encoding, a first of the one or more greatness flags for a predetermined transform coefficient by selecting a context depending on

a coefficient position of the predetermined transform coefficient.

75. Apparatus of any of claims 40 to 74, configured to

encode, using context-adaptive entropy encoding, the first greatness flag for a predetermined transform coefficient by

determining a local activity based on a set of flags decoded prior to the first greatness flag of the predetermined transform coefficient for a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, and/or a number of transform coefficients within the local template

around the predetermined transform coefficient, the reconstruction level of which is not zero, and

selecting a context depending on the local activity and/or the number of transform coefficients.

76. Apparatus of claim 75, configured to select the context depending on a difference between the local activity and the number of transform coefficients.

77. Apparatus of claim 75 or 76, configured to

encode, sequentially, the significance flag, the parity flag and a first of the one or more greatness flags in one first pass so that the set of flags comprises the significance flag, the parity flag and the first of the one or more greatness flags decoded for the set of neighboring transform coefficients, and to compute the local activity based on a sum over an addend for each of the neighboring transform coefficients, the addends indicating a minimally assumed index or a minimally assumed reconstruction level for the neighboring transform coefficients determined based on the significance flag, the parity flag and the first of the one or more greatness flags decoded for the neighboring transform coefficients.

78. Apparatus of any of claims 40 to 77, configured to encode the remainder for a predetermined transform coefficient using a Golomb-Rice code and using a Rice parameter which depends on a sum over an addend for each of out of a set of neighboring transform coefficients within a local template around the predetermined transform coefficient, the addend depending on a quantization index or a reconstruction level for the respective neighboring transform coefficient.

79. Method for decoding a block (10) of transform coefficients (12), configured to

in one or more first passes (20) of scanning the transform coefficients,

decode (16), using context-adaptive entropy decoding, a significance flag for the transform coefficients which indicates whether a quantization index of the transform coefficients is zero,

decode (18) a parity flag for the transform coefficients which indicates a parity of the transform coefficients,

in one or more second passes (22) of scanning the transform coefficients, including or excluding one or more of the one or more first passes (20),

decode (24), using context-adaptive entropy decoding, one or more greatness flags for transform coefficients the quantization index of which is not zero,

in one or more third passes (26, 27),

decode (28, 30), using equiprobability entropy decoding,

a remainder of the quantization index of the transform coefficients the one or more greatness flags of which are positive and

a sign of the quantization index of the transform coefficients the quantization index of which is not zero.

80. Method for encoding a block of transform coefficients, configured to

in one or more first passes of scanning the transform coefficients,

encode, using context-adaptive entropy encoding, a significance flag for the current transform coefficients which indicates whether a quantization index of the current transform coefficients is zero,

encode a parity flag for the transform coefficients which indicates a parity of the transform coefficients,

in one or more second passes of scanning the transform coefficients, including or excluding one or more of the one or more first passes,

encode, using context-adaptive entropy encoding, one or more greatness flags for transform coefficients the quantization index of which is not zero,

in one or more third passes,

encode, using equiprobability entropy encoding

a remainder of the quantization index of the transform coefficients the one or more greatness flags of which are positive and

a sign of the quantization index of the transform coefficients the quantization index of which is not zero.

81. Computer program for instructing a computer executing same to perform a method according to claim 79 or 80.

82. Data stream generated by a method of claim 80.