RU2820857C2 - Entropy coding of motion vector differences - Google Patents

Abstract

FIELD: physics.

SUBSTANCE: invention relates to video encoding means. Video prediction is encoded by motion-compensated prediction using motion vectors. Motion vectors are predictively encoded by motion vector prediction and motion vector differences generation, wherein motion vector differences represent prediction error with respect to motion vectors. Differences of motion vectors are binarized, so that each binarization includes two binary codes of fixed length based on cutoff value equal to two, and a suffix bin string including an exponential Golomb code having a fixed order, given as one. Each binary code of a fixed length of the prefix bin string indicates whether the absolute value of the difference of the motion vectors is greater than the corresponding fixed value. Binarized values of motion vector differences are encoded into a data stream.

EFFECT: high efficiency of video encoding.

25 cl, 22 dwg

Description

The present invention relates to an entropy coding principle for encoding video data.

Many video codecs are known in the art. Typically, these codecs reduce the amount of data required to represent video content, i.e. they compress data. In the context of video encoding, it is known that video compression is advantageously achieved by sequentially applying different encoding techniques: motion-compensated prediction is used to predict the content of the image. The motion vectors determined by the motion-compensated prediction, as well as the remainder of the prediction, are subject to lossless entropy encoding. To further reduce the amount of data, the motion vectors themselves are subject to prediction, so that only the motion vector differences representing the remainder of the motion vector prediction need to be entropy encoded. H.264, for example, uses the procedure just outlined to convey motion vector difference information. In particular, the motion vector differences are binarized into strings of bins (containers) corresponding to a combination of a truncated unary code and, from some cutoff value, an exponential Golomb code. While exponential Golomb code bins are easily encoded using the equiprobable walk mode with a fixed probability of 0.5, multiple contexts are provided for the first bins. The cutoff value is chosen to be nine. Therefore, a large number of contexts are provided for encoding motion vector differences.

Providing a large number of contexts, however, not only increases encoding complexity, but can also have a negative impact on encoding efficiency: if the context is visited very rarely, probabilistic adaptation is not performed effectively, i.e. adapting the probability estimate associated with the corresponding context during entropy encoding reason. Consequently, probability estimates that are not properly applied estimate the actual symbol statistics. Additionally, if multiple contexts are provided for a given binarization bin, choosing between them may require inspecting the values of adjacent bins/syntactic elements, which may interfere with the decoding process. On the other hand, if the number of contexts is provided too small, bins with highly varying actual character statistics are grouped together in one context and, therefore, the probability estimate associated with that context does not effectively encode the bins associated with it.

There is a current need to further improve the coding efficiency of entropy coding of motion vector differences.

Therefore, it is an object of the present invention to provide such a coding principle.

This object is achieved by the subject of the independent claims appended to this document.

The main solution of the present invention is that the coding efficiency of entropy encoding of motion vector differences can be further improved by reducing the cutoff value to which the truncated unary code is used to binarize the motion vector differences to two, so that there are only two bin positions of the truncated unary code , and, if the order of one is used for the exponential Golomb code to binarize the motion vector differences from the cutoff value, and if, additionally, exactly one context is provided for the two bin positions of the truncated unary code, respectively, so that it is not necessary to select a context based on values of a bin or syntactic element of adjacent image blocks, and over-fine classification of bins at these bin positions into contexts is avoided, so that probabilistic adaptation works as expected, and if the same contexts are used for horizontal and vertical components, thereby further reducing the negative effects of over-fine divisions of context.

In addition, it has been found that the just mentioned techniques for entropy encoding of motion vector differences are particularly valuable when combined with improved methods for predicting motion vectors and reducing the required number of motion vector differences to be transmitted. For example, multiple motion vector predictors may be provided to obtain an ordered list of motion vector predictors, and an index of this list of motion vector predictors may be used to determine the actual motion vector predictor whose prediction remainder is represented by the motion vector difference under consideration. Although information about the used list index must be inferred from the data stream at the decoding side, the overall quality of motion vector prediction is improved, and therefore the magnitude of motion vector differences is further reduced, so that overall coding efficiency is further improved, and the cutoff value and overall context utilization are reduced for the horizontal and vertical components of the motion vector differences correspond to this improved motion vector prediction. On the other hand, fusion may be used to reduce the number of motion vector differences to be transmitted in the data stream: to this end, fusion information may be transmitted in the data stream, signaling the decoder blocks to subdivide the blocks, which are grouped into a group of blocks. The motion vector differences can then be transmitted in the data stream in units of these combined groups instead of individual blocks, thereby reducing the number of motion vector differences that need to be transmitted. Since this clustering of blocks reduces the cross-correlation between adjacent motion vector differences, the just mentioned exception of providing multiple contexts for a single bin position prevents the entropy encoding scheme from very fine-grained classification into contexts depending on adjacent motion vector differences. Instead, the fusion principle already exploits the cross-correlation between the motion vector differences of adjacent blocks, and therefore one context for one bin position is sufficient - the same for the horizontal and vertical components.

Preferred embodiments of the present application are described below with respect to the figures, including:

fig. 1 is a block diagram of an encoder according to an embodiment;

fig. 2a-2c schematically depict various subdivisions of a bin array, such as an image, into blocks;

fig. 3 is a block diagram of a decoder according to an embodiment;

fig. 4 is a block diagram of an encoder according to an embodiment in more detail;

fig. 5 shows in more detail a block diagram of a decoder according to an embodiment;

fig. 6 schematically illustrates the transformation of a block from the spatial domain to the spectral domain, the resulting transform block, and its reconversion;

fig. 7 is a block diagram of an encoder according to an embodiment;

fig. 8 is a block diagram of a decoder suitable for decoding a bit stream generated by the encoder of FIG. 8, according to an embodiment;

fig. 9 is a schematic diagram illustrating a data packet with multiplexed partial bit streams according to an embodiment;

fig. 10 is a schematic diagram illustrating a data packet with alternative segmentation using fixed size segments, according to another embodiment;

fig. 11 shows a decoder supporting mode switching according to an embodiment;

fig. 12 shows a decoder supporting mode switching according to another embodiment;

fig. 13 shows an encoder corresponding to the decoder of FIG. 11, according to an embodiment;

fig. 14 shows an encoder corresponding to the decoder of FIG. 12, according to an embodiment;

fig. 15 shows the display of pStateCtx and fullCtxState/256**E**;

fig. 16 shows a decoder according to an embodiment of the present invention; And

fig. 17 depicts an encoder according to an embodiment of the present invention.

Fig. 18 schematically shows a binarization of a motion vector difference according to an embodiment of the present invention;

fig. 19 schematically illustrates the merging principle according to the embodiment; And

fig. 20 schematically illustrates a motion vector prediction circuit according to an embodiment.

It is noted that in describing the figures, elements appearing in more than one of these figures are designated by the same reference numeral in each of these figures, and repeated description of these elements with respect to functionality is avoided so as to avoid unnecessary repetition. However, functionality and descriptions provided with respect to one figure also apply to other figures, unless expressly stated to the contrary.

Below, embodiments of the general video encoding principle will first be described with respect to FIGS. 1-10. Fig. 1-6 refer to the part of the video codec that operates at the syntax level. Subsequent figs. 8-10 relate to embodiments for a portion of code related to converting a stream of syntax elements to a stream of data and vice versa. Specific aspects and embodiments of the present invention are then described in terms of possible implementations of the general principle briefly outlined in relation to FIG. 1-10.

Fig. 1 depicts an example encoder 10 in which aspects of the present application may be implemented.

The encoder encodes the array of information sampling elements 20 into a data stream. The information sampling element array may represent information sampling elements corresponding to, for example, illuminance values, chrominance values, luminance values, chroma values, or the like. However, the information bins may also represent depth values in the case of the bin array 20 representing a depth map generated from, for example, light sensor time or the like.

Encoder 10 is a block-based encoder. Those. encoder 10 encodes the array 20 of samples into a data stream 30 in units of blocks 40. Encoding in units of blocks 40 does not necessarily mean that encoder 10 encodes these blocks 40 completely independently of one another. Instead, encoder 10 may use reconstructions of previously encoded blocks to extrapolate or internally predict remaining blocks, and may use the degree of block partitioning to set encoding parameters, i.e. to set the method by which each bin array region corresponding to the corresponding block is encoded.

In addition, the encoder 10 is a transform encoder. Those. encoder 10 encodes blocks 40 by using a transform to transfer bins of information in each block 40 from the spatial domain to the spectral domain. A two-dimensional transform such as discrete cosine transform (DCT), fast Fourier transform (FFT) or the like may be used. Preferably, the blocks 40 are square or rectangular in shape.

The subdivision of the sample array 20 into blocks 40 shown in FIG. 1 is merely for illustration purposes. Fig. 1 depicts an array 20 of bins subdivided into a conventional two-dimensional arrangement of square or rectangular blocks 40 that are adjacent to each other in a non-overlapping manner. The size of the blocks 40 may be determined in advance. Those. The encoder 10 may not transfer the block size information of the blocks 40 in the data stream 30 to the decoding side. For example, the decoder may expect a given block size.

However, several alternatives are possible. For example, blocks can overlap each other. The overlap, however, may be limited to such an extent that each block has a portion not overlapped by any neighboring block, or such that each block bin is overlapped by at most one block from among the neighboring blocks adjacent to each other with the current block for a given direction. The latter means that the left and right neighboring blocks may overlap the current block to completely cover the current block, but they may not overlap each other, and the same applies to neighbors in the vertical and diagonal direction.

As another alternative, subdividing the bin array 20 into blocks 40 may be adapted to the contents of the bin array 20 by the encoder 10, with subdivision information about the subdivision used being sent to the decoder side via bitstream 30.

Fig. 2a-2c depict various examples for subdividing the sample array 20 into blocks 40. FIG. 2a depicts a quadtree subdivision of the sample array 20 into blocks 40 of different sizes, with typical blocks designated 40a, 40b, 40c and 40d in increasing size. According to the division in FIG. 2a, the bin array 20 is first divided into a conventional two-dimensional arrangement of tree blocks 40d, which in turn have individual subdivision information associated with it, whereby a certain tree block 40d may or may not be further subdivided according to the quadtree structure. The tree block to the left of block 40d, as an example, is subdivided into smaller blocks according to the quadtree structure. Encoder 10 may perform one two-dimensional transform for each of the blocks shown in solid and dotted lines in FIG. 2a. In other words, encoder 10 may transform array 20 in block subdivision units.

Instead of a quadtree subdivision, a more general multi-tree subdivision may be used, and the number of child nodes per hierarchy level may differ between different hierarchy levels.

Fig. 2b depicts another example for a subdivision. According to FIG. 2b, the bin array 20 is first divided into macroblocks 40b arranged in a conventional two-dimensional arrangement in a non-overlapping, mutually adjacent manner, with each macroblock 40b having subdivision information associated with it such that the macroblock is not subdivided, or, if subdivided, is subdivided in a conventional two-dimensional manner. into equally sized subblocks to achieve different degrees of subdivision for different macroblocks. The result is a subdivision of the sample array 20 into blocks 40 of different sizes, with representatives of the different sizes designated by positions 40a, 40b and 40a'. As in fig. 2a, encoder 10 performs a two-dimensional transform on each of the blocks shown in solid and dotted lines in FIG. 2b. Fig. 2c is described below.

Fig. 3 depicts a decoder 50 capable of decoding a data stream 30 generated by an encoder 10 to reconstruct a reconstructed version 60 of a sample array 20. Decoder 50 extracts from data stream 30 a block of transform coefficients for each of the blocks 40 and reconstructs the reconstructed version 60 by performing an inverse transform on each of the blocks of transform coefficients.

Encoder 10 and decoder 50 may be configured to perform entropy encoding/decoding to insert transform coefficient block information into and extract information from the data stream, respectively. Details in this regard are described below in accordance with various embodiments. It should be noted that data stream 30 does not necessarily contain information about transform coefficient blocks for all blocks 40 of sample array 20. Instead, as a subset of blocks 40 may be encoded into bitstream 30 in a different manner. For example, encoder 10 may instead decide to refrain from inserting a block of transform coefficients for some block of blocks 40, inserting into bitstream 30 alternative encoding parameters that allow decoder 50 to predict or otherwise populate the corresponding block in the reconstructed version 60. For example, , the encoder 10 may perform texture analysis to determine the arrangement of blocks in the bin array 20, which may be populated at the decoder side by the decoder through texture synthesis, and indicate this in the bitstream accordingly.

As described in relation to the following figures, the transform coefficient blocks do not necessarily represent a spectral domain representation of the original bins of information of the corresponding block 40 of the bin array 20. Instead, such a block of transform coefficients may represent a spectral domain representation of the prediction residual of the corresponding block 40. FIG. 4 depicts an embodiment for such an encoder. The encoder according to FIG. 4 contains a transformation stage (cascade) 100, an entropy encoder 102, an inverse transformation stage 104, a predictor (predictor) 106 and a subtractor 108, as well as an adder 110. The subtractor 108, the transformation stage 100 and the entropy encoder 102 are connected in series in the above order between the input 112 and encoder output 114 in FIG. 4. The inverse conversion stage 104, the adder 110 and the predictor 106 are connected in the above order between the output of the conversion stage 100 and the inverting input of the subtractor 108, and the output of the predictor 106 is also connected to the other input of the adder 110.

The encoder according to FIG. 4 is a block encoder based on predictive transform. Those. blocks of sample array 20 arriving at input 112 are predicted from previously encoded and reconstructed portions of the same sample array 20 or previously encoded and reconstructed other sample arrays that may precede or follow the current sample array 20 in presentation time. The prediction is performed by predictor 106. Subtractor 108 subtracts the prediction from such source block, and transformation stage 100 performs a two-dimensional transformation of the prediction residuals. The two-dimensional transform itself or a subsequent measure in transform stage 100 may result in quantization of transform coefficients in transform coefficient blocks. The quantized blocks of transform coefficients are losslessly encoded, for example, by entropy encoding in entropy encoder 102, with the resulting data stream output at output 114. Inverse transform stage 104 reconstructs the quantized remainder, and adder 110 in turn combines the reconstructed residual with the corresponding prediction for obtaining reconstructed information samples based on which the predictor 106 can predict the aforementioned currently encoded prediction blocks. The predictor 106 may use different prediction modes, such as intra prediction modes and inter prediction modes, to predict blocks, and the prediction parameters are sent to the entropy encoder 102 for insertion into the data stream. For each inter-prediction block, corresponding motion data is inserted into the bitstream by the entropy encoder 114 to enable the decoding side to re-predict. The motion data for an image prediction block may include a syntax portion including a syntax element representing a motion vector difference differentially encoding a motion vector for the current prediction block relative to a motion vector predictor obtained, for example, by a predetermined method from the motion vectors of adjacent, already coded prediction blocks.

Those. according to the embodiment of FIG. 4, the transform coefficient blocks represent the spectral representation of the remainder of the sample array, rather than its actual information samples. Those. according to the embodiment of FIG. 4, a sequence of syntax elements may be provided to entropy encoder 102 for entropy encoding into data stream 114. The sequence of syntactic elements may comprise syntactic elements of motion vector differences for the inter-prediction blocks and syntactic elements relating to a saliency map indicating the positions of the significant levels of the transform coefficients, as well as syntactic elements defining the significant levels of the transform coefficients themselves for the transform blocks.

It should be noted that several alternatives exist for the embodiment of FIG. 4, some of which were described in the introductory part of the description of the invention, the description of which is included in the description of FIG. 4 of this document.

Fig. 5 depicts a decoder capable of decoding the data stream generated by the encoder of FIG. 4. Decoder according to FIG. 5 includes an entropy decoder 150, an inverse transform stage 152, an adder 154, and a predictor 156. The entropy decoder 150, an inverse transform stage 152, and an adder 154 are connected in series between an input 158 and an output 160 of the decoder of FIG. 5 in the order mentioned. Another output of the entropy decoder 150 is connected to a predictor 156, which in turn is connected between the output of the adder 154 and its other input. Entropy decoder 150 extracts from the data stream entering the decoder of FIG. 5 at input 158, transform coefficient blocks, with an inverse transform applied to the transform coefficient blocks in stage 152 to produce a remainder signal. The residual signal is combined with the prediction from predictor 156 in adder 154 to produce a reconstructed block of the reconstructed version of the bin array at output 160. Based on the reconstructed versions, predictor 156 generates predictions, thereby reconstructing the predictions performed by encoder-side predictor 106. To obtain the same predictions as those used on the encoder side, predictor 156 uses prediction parameters that entropy decoder 150 also receives from the data stream at input 158.

It should be noted that in the above-described embodiments, the spatial degree of partitioning with which prediction and transformation of the remainder are performed need not be equal to each other. This is shown in Fig. 2C. This figure depicts the subdivision for prediction blocks of the degree of prediction partitioning with solid lines and the degree of partitioning of the remainder with dashed lines. As can be seen, the divisions can be selected independently of each other by the encoder. More precisely, the data flow syntax may respect the definition of the remainder division independently of the prediction division. Alternatively, the remainder division may be an extension of the prediction division such that each residue block is either equal to or a proper subset of the prediction block. This is shown in Fig. 2a and fig. 2b, for example, where again the degree of prediction partitioning is shown by solid lines and the degree of partitioning of the remainder by dotted lines. Those. in fig. 2a-2c, all blocks having a reference position associated with them will be residual blocks for which one 2D transform will be performed, while larger solid line blocks enclosing dotted line blocks 40a, for example, will be prediction blocks for which Prediction parameters are set individually.

The above embodiments have in general that a block (of residual bins or original bins) must be converted at the encoder side into a block of transform coefficients, which in turn must be converted back into a reconstructed block of bins at the decoder side. This is shown in FIG. 6. Fig. 6 depicts a block 200 of bins. In the case of FIG. 6, this example block 200 is square and has 4×4 sampling elements 202 in size. The sampling elements 202 are regularly arranged along the horizontal x direction and vertical y direction. Through the above two-dimensional transform T, the block 200 is transformed into the spectral domain, namely, into a block 204 of transform coefficients 206, the transform block 204 having the same size as the block 200. That is, the transform block 204 has as many transform coefficients 206 as the block 200 has bins in both the horizontal direction and the vertical direction. However, since the transform T is a spectral transform, the positions of the transform coefficients 206 in the transform block 204 do not correspond to spatial positions, but rather to the spectral components of the contents of the block 200. In particular, the horizontal axis of the transform block 204 corresponds to the axis along which the spectral frequency in the horizontal direction monotonically increases, while the vertical axis corresponds to the axis along which the spatial frequency in the vertical direction increases monotonically, with the conversion coefficient of the direct current (DC) component located in the corner - here, as an example, the upper left corner - of block 204, so that in In the lower right corner is a conversion factor 206 corresponding to the highest frequency in both the horizontal and vertical directions. Neglecting spatial direction, the spatial frequency to which a certain transform coefficient 206 belongs generally increases from the upper left corner to the lower right corner. By inversely transforming T ^-1 , transform block 204 is transferred from the spectral domain to the spatial domain to reacquire a copy 208 of block 200. In the absence of introducing quantization loss in the transform, the reconstruction will be perfect.

As noted above, it can be seen in FIG. 6 that the larger block sizes of block 200 increase the spectral resolution of the resulting spectral representation 204. On the other hand, quantization noise tends to propagate throughout block 208, and thus sharp and highly localized objects in blocks 200 tend to cause deviations in the re-converted block relative to the original block 200 due to quantization noise. The main advantage of using large blocks, however, is that the ratio between the number of significant ones, i.e. non-zero (quantized) conversion coefficients, i.e. levels on the one hand, and the number of insignificant transform coefficients on the other hand, can be reduced in larger blocks compared to smaller blocks, thereby allowing better coding efficiency to be obtained. In other words, often significant levels of conversion coefficients, i.e. transform coefficients not quantized to zero are rarely distributed across transform block 204. Consequently, according to embodiments described in more detail below, the positions of significant levels of transform coefficients are signaled in the data stream by means of a significance map. Separately from it, the values of the significant conversion coefficient, i.e. levels of conversion coefficients in the case when the conversion coefficients are quantized and transmitted in the data stream.

All encoders and decoders described above are thus configured to operate with some syntax of syntax elements. Those. the above-mentioned syntax elements such as transform coefficient levels, syntax elements relating to the significance map of transform blocks, motion data syntax elements relating to inter prediction blocks, and the like are assumed to be arranged sequentially in the data stream in a predetermined manner. Such a given image can be represented as pseudocode, as, for example, is done in the H.264 standard or other video codecs.

In other words, the above description deals primarily with the transformation of multimedia data, here video data as an example, into a sequence of syntactic elements in accordance with a predefined syntactic structure specifying certain types of syntactic elements, its semantics and the order among them. The entropy encoder and entropy decoder of FIG. 4 and 5 may be operable, and may be structured as summarized below. They are responsible for performing the transformation between a sequence of syntax elements and a data stream, i.e. a stream of characters or bits.

An entropy encoder according to an embodiment is shown in FIG. 7. The lossless encoder converts the syntax element stream 301 into a plurality of two or more partial bit streams 312.

In a preferred embodiment of the invention, each syntax element 301 is associated with a category of a set of one or more categories, i.e. type of syntactic element. As an example, categories can specify the type of syntactic element. In the context of hybrid video coding, a separate category may be associated with macroblock coding modes, block coding modes, reference picture indices, motion vector differences, subdivision flags, coded block flags, quantization parameters, transform coefficient levels, etc. In other application domains, such as audio, speech, text, document, or general data encoding, different categorizations of syntactic elements are possible.

Typically, each syntactic element can take on a finite or countably infinite set of values, where the set of possible values for a syntactic element may vary for different categories of syntactic elements. For example, there are binary syntax elements as well as integer ones.

To reduce the complexity of the encoding and decoding algorithm and to enable general encoding and decoding design for different syntax elements and categories of syntax elements, syntax elements 301 are converted into ordered sets of binary solutions, and these binary solutions are then processed by simple binary encoding algorithms. Therefore, binarizer 302 bijectively (one-to-one) maps the value of each syntax element 301 to a sequence (either string or word) of bins 303. The sequence of bins 303 represents a set of ordered binary solutions. Each bin 303 or binary decision may take one value from a set of two values, for example, one of the values 0 and 1. The binarization scheme may be different for different categories of syntactic elements. The binarization scheme for a particular category of syntactic elements may depend on the set of possible values of the syntactic element and/or other properties of the syntactic element for a particular category.

Table 1 illustrates three example binarization schemes for countably infinite sets. Binarization schemes for countably infinite sets can also be applied to finite sets of values of syntactic elements. Particularly for large finite sets of syntactic element values, there may be little inefficiency (resulting from unused bin sequences), but the generality of such binarization schemes provides an advantage in terms of complexity and memory requirements. For small finite sets of syntactic element values, it is often preferable (in terms of encoding efficiency) to adapt the binarization scheme to the number of possible symbol values.

Table 2 illustrates three example binarization schemes for finite sets of 8 values. Binarization schemes for finite sets can be derived from universal binarization schemes for countably infinite sets by modifying some sequences of bins such that finite sets of sequences of bins represent code without redundancy (and potentially a reordering of the sequences of bins). As an example, the truncated unary binarization scheme in Table 2 was created by modifying the sequence of bins for syntax element 7 of the universal unary binarization (see Table 1). The truncated and reordered Golomb exponential binarization of order 0 in Table 2 was created by modifying the bin sequence for syntax element 7 of the universal exponential Golomb binarization of order 0 (see Table 1) and by reordering the bin sequences (the truncated bin sequence for character 7 was assigned to character 1) . For finite sets of syntactic elements, it is also possible to use non-systematic/non-universal binarization schemes, as exemplified in the last column of Table 2.

Each bin 303 of the sequence of bins produced by the binarizer 302 is supplied to the parameter assigner 304 in sequential order. The parameter assigner assigns a set of one or more parameters to each bin 303 and outputs a bin with an associated set of parameters 305. The set of parameters is determined in exactly the same way in the encoder and decoder. The set of parameters may consist of one or more of the following parameters:

In particular, the parameter assigner 304 may be configured to assign the current bean 303 a context model. For example, the parameter assigner 304 may select one of the available context indexes for the current bean 303. The available set of contexts for the current bean 303 may depend on the type of the bean, which in turn may be determined by the type/category of the syntax element 301 that the current bean is binarizing. 303 is the part and position of the current bin 303 in the last binarization. The choice of context from among the available set of contexts may depend on previous bins and syntactic elements associated with the latter. Each of these contexts has a probabilistic model associated with it, i.e. a measure to estimate the probability for one of two possible bin values for the current bin. The probabilistic model, in particular, may be a measure for estimating the probability of a less likely or more likely bin value for the current bin, wherein the probabilistic model is further defined by an identifier specifying an estimate of which of two possible bin values represents the less likely or more likely bin value for current bean 303. In the case where only one context is available for the current bean, context selection may be omitted. As discussed in more detail below, the parameter assigner 304 may also perform probabilistic model adaptation to adapt the probabilistic models associated with various contexts with the actual bin statistics of the corresponding bins belonging to the respective contexts.

As also described in more detail below, the parameter assigner 304 may operate differently depending on whether the High Efficiency (HE) mode or the Low Complexity (LC) mode is activated. In both modes, the probabilistic model associates the current bin 303 with any of the bin encoders 310, as set forth below, but the mode of operation of the parameter assigner 304 tends to be less complex in the LC mode, however, the encoding efficiency is improved in the high efficiency mode because that the parameter assigner 304 causes the association of individual bins 310 with individual encoders 310 to be more accurately adapted to the bin statistics, thereby optimizing entropy relative to the LC mode.

Each bin with an associated set of parameters 305, which is the output of the parameter assigner 304, is supplied to a bin buffer selector 306. The bin buffer selector 306 potentially modifies the value of the input bin 305 based on the value of the input bin and associated parameters 305, and supplies the output bin 307—with the potentially modified value—to one of two or more bin buffers 308. The bin buffer 308 to which output bin 307 is sent is determined based on the value of input bin 305 and/or the value of associated parameters 305.

In the preferred embodiment of the invention, the bin buffer selector 306 does not modify the value of the bin, i.e. the output bin 307 always has the same value as the input bin 305. In another preferred embodiment of the invention, the bin buffer selector 306 determines the output bin value 307 based on the input bin value 305 and the associated probability estimate for one of the two possible values. bin for the current bin. In a preferred embodiment of the invention, the output bin value 307 is set equal to the input bin value 305 if the measure for the probability for one of the two possible bin values for the current bin is less than (or less than or equal to) a particular threshold; if the measure for the probability for one of the two possible bin values for the current bin is greater than or equal to (or greater than) a particular threshold, the output bin value 307 is modified (ie, set to the opposite value of the input bin value). In another preferred embodiment of the invention, the output bin value 307 is set equal to the input bin value 305 if the measure for the probability for one of the two possible bin values for the current bin is greater than (or greater than or equal to) a particular threshold; if the measure for the probability for one of the two possible bin values for the current bin is less than or equal to (or less than) a particular threshold, the output bin value 307 is modified (ie, set to the opposite value of the input bin value). In a preferred embodiment of the invention, the threshold value corresponds to a value of 0.5 for the estimated probability for both possible bin values.

In another preferred embodiment of the invention, the bin buffer selector 306 determines the output bin value 307 based on the input bin value 305 and an associated identifier specifying an estimate of which of two possible bin values represents the less likely or more likely bin value for the current bin. In a preferred embodiment of the invention, the output bin value 307 is set equal to the input bin value 305 if the identifier specifies that the first of two possible bin values represents a less likely (or more likely) bin value for the current bin, and the output bin value 307 is modified (i.e., e. is set to the opposite value of the input bin's value) if the identifier specifies that the second of two possible bin values represents the less likely (or more likely) bin value for the current bin.

In a preferred embodiment of the invention, bin buffer selector 306 determines bin buffer 308 to which output bin 307 is sent based on an associated measure for estimating the probability for one of two possible bin values for the current bin. In a preferred embodiment of the invention, the set of possible values for the probability estimate measure for one of the two possible bin values is finite, and the bin buffer selector 306 contains a table that associates exactly one bin buffer 308 with each possible probability estimate value for one of the two possible values. bin values, where different values for the probability estimate measure for one of two possible bin values may be associated with the same bin buffer 308. In another preferred embodiment of the invention, the range of possible values for the probability measure for one of two possible bin values is divided into several bins, the bin buffer selector 306 determines the bin index for the current probability measure for one of the two possible bin values, and the selector 306 The bin buffer contains a table that associates exactly one bin buffer 308 with each possible value for the bin index, where different values for the bin index may be associated with the same bin buffer 308. In a preferred embodiment of the invention, the input bins 305 with opposing measures for estimating the probability for one of two possible bin values (the opposing measures being those representing P and 1-P probability estimates) are fed into the same bin buffer 308. In another preferred embodiment of the invention, associating a measure for estimating the probability for one of two possible bin values for the current bin with a particular bin buffer is time-adapted, for example, to ensure that the generated partial bitstreams have similar bit rates. In addition, the interval index is also called the pipe index (entropy of division of the probability interval), while the pipe index, together with the refinement index, and the flag indicating the more likely value of the bin, indexes the actual probability model, i.e. probability assessment.

In another preferred embodiment of the invention, bin buffer selector 306 determines bin buffer 308 to which output bin 307 is sent based on an associated measure for estimating the likelihood of a less likely or more likely bin value for the current bin. In a preferred embodiment of the invention, the set of possible values for the probability estimate measure for a less likely or more likely bin value is finite, and the bin buffer selector 306 contains a table that associates exactly one bin buffer 308 with each possible probability estimate value for the less likely or more likely value. probable bin value, where different values for the probability measure for a less likely or more likely bin value may be associated with the same bin buffer 308. In another preferred embodiment of the invention, the range of possible values for the probability measure for a less likely or more likely bin value is divided into several bins, the bin buffer selector 306 determines the bin index for the current probability measure for the less likely or more likely bin value, and The bin buffer selector 306 contains a table that associates exactly one bin buffer 308 with each possible value for the bin index, where different values for the bin index may be associated with the same bin buffer 308. In another preferred embodiment, associating a measure for estimating the probability of a less likely or more likely bin value for the current bin with a particular bin buffer is time-adapted, for example, to ensure that the partial bitstreams produced have similar bit rates.

Each of two or more bin buffers 308 is connected to exactly one bin encoder 310, and each bin encoder is connected to exactly one bin buffer 308. Each bin encoder 310 reads bins from an associated bin buffer 308 and converts the sequence of bins 309 into a codeword 311 that represents the sequence of bits. Bin buffers 308 represent first-in, first-out buffers; bins that are fed later (in sequential order) into bin buffer 308 are not encoded before bins that are fed earlier (in sequential order) into the bin buffer. Codewords 311, which are the output of a particular bin encoder 310, are written to a particular partial bitstream 312. The general encoding algorithm converts syntax elements 301 into two or more partial bitstreams 312, where the number of partial bitstreams is equal to the number of bin buffers and bin encoders . In a preferred embodiment of the invention, bin encoder 310 converts the variable number of bins 309 into a variable number of bits codeword 311. One advantage of the above and below summarized embodiments of the invention is that bin encoding can be performed in parallel (eg, for different groups of probability measures), which reduces processing time for multiple implementations.

Another advantage of embodiments of the invention is that the bin encoding that is performed by the bin encoders 310 can be specifically designed for different parameter sets 305. In particular, the bin encoding and encoding can be optimized (in terms of encoding efficiency and/or complexity) for different groups of estimated probabilities. On the one hand, this makes it possible to reduce the complexity of encoding/decoding, and on the other hand, it makes it possible to obtain an increase in encoding efficiency. In a preferred embodiment of the invention, bin encoders 310 implement different encoding algorithms (ie, mapping sequences of bins to codewords) for different groups of measures to estimate the probability for one of two possible bin values 305 for the current bin. In another preferred embodiment of the invention, bin encoders 310 implement different encoding algorithms for different groups of measures to estimate the probability for a less likely or more likely bin value for the current bin.

In a preferred embodiment of the invention, bin encoders 310—or one or more of the bin encoders—are entropy encoders that directly map sequences of input bins 309 to codewords 310. Such mapping can be implemented efficiently and does not require a complex arithmetic encoding mechanism. The reverse mapping of codewords to a sequence of bins (which is done at the decoder) must be unique to ensure perfect decoding of the input sequence, but the mapping of bin sequences 309 to codewords 310 need not be unique, i.e. it is possible that a particular sequence of bins may map to more than one sequence of codewords. In a preferred embodiment of the invention, the mapping of sequences of input bins 309 to codewords 310 is bijective. In another preferred embodiment of the invention, bin encoders 310—or one or more of the bin encoders—are entropy encoders that directly map variable-length sequences of input bins 309 to variable-length codewords 310. In a preferred embodiment of the invention, the output codewords represent non-redundancy codes, such as general Huffman codes or canonical Huffman codes.

Table 3 shows two examples for bijectively mapping sequences of bins into codes without redundancy. In another preferred embodiment of the invention, the output codewords represent redundant codes useful for error detection and error recovery. In another preferred embodiment of the invention, the output codewords represent encryption codes suitable for encrypting syntax elements.

In another preferred embodiment of the invention, bin encoders 310—or one or more of the bin encoders—are entropy encoders that directly map variable-length sequences of input bins 309 to fixed-length codewords 310. In another preferred embodiment of the invention, bin encoders 310—or one or more of the bin encoders—are entropy encoders that directly map fixed-length sequences of input bins 309 to variable-length codewords 310.

A decoder according to an embodiment of the invention is shown in FIG. 8. The decoder performs essentially the inverse of the encoder such that the (previously encoded) sequence of syntax elements 327 is decoded from a plurality of two or more partial bitstreams 324. The decoder includes two different processing threads: a thread for requesting data, which repeats the encoder data stream, and a data stream that represents the reverse of the encoder data stream. In the illustration in FIG. 8, the dotted arrows represent the data request flow, while the solid arrows represent the data flow. The decoder building blocks are basically the same as the encoder building blocks, but implement the reverse operations.

Decoding of a syntax element is triggered by a request for a new decodable syntax element 313, which is sent to the binarizer 314. In a preferred embodiment of the invention, each request for a new decodable syntax element 313 is associated with a category of the set of one or more categories. The category that is associated with a syntactic element query is the same as the category that was associated with the corresponding syntactic element at encoding time.

The binarizer 314 maps the request of the syntax element 313 to one or more bean requests that are sent to the parameter assigner 316. As a final response to the bean request that is sent to the parameter assigner 316 by the binarizer 314, the binarizer 314 receives the decoded bean 326 from the bean buffer selector 318. The binarizer 314 compares the received sequence of decodable bins 326 with the binarizations of a particular binarization scheme for the requested syntax element, and if the received sequence of decodable bins 26 matches the binarization of the syntax element, the binarizer frees its bin buffer and outputs the decodable syntax element as the final response to the request for a new one. decoded symbol. If the already received sequence of decodable bins does not match any of the bean sequences for the binarization scheme for the requested syntax element, the binarizer sends another bean request to the parameter assigner until the sequence of decoded bins matches one of the sequence of binarization schemes for the requested syntax element. syntactic element. For each syntax element request, the decoder uses the same binarization scheme that was used to encode the corresponding syntax element. The binarization scheme may be different for different categories of syntactic elements. The binarization scheme for a particular category of syntactic elements may depend on the set of possible meanings of the syntactic element and/or other properties of the syntactic elements for a particular category.

The parameter assigner 316 assigns a set of one or more parameters to each bean request and sends the bean request with the associated set of parameters to the bean buffer selector. The set of parameters that is assigned to the requested bean by the parameter assigner is the same one that was assigned to the corresponding bean during encoding. The plurality of parameters may be composed of one or more parameters that are mentioned in the description of the encoder in FIG. 7.

In the preferred embodiment of the invention, the parameter assigner 316 associates each bean request with the same parameters as the assigner 304 did, i.e. context and its associated measure for estimating the probability for one of two possible bin values for the current queried bin, such as a measure for estimating the probability for the less likely or more likely bin value for the current queried bin, and an identifier specifying an estimate of which of the two possible bin values represents the less likely or more likely bin value for the currently requested bin.

The parameter assigner 316 may define one or more of the above probability measures (a measure for estimating the probability for one of two possible bin values for the current queried bin, a measure for estimating the probability for the less likely or more likely bin value for the current queried bin, an identifier specifying an estimate of which of two possible bin values represents the less likely or more likely bin value for the currently requested bin) based on a set of one or more symbols already decoded. Determining probability measures for a particular bin query repeats the process in the encoder for the corresponding bin. The decoded symbols that are used to determine the probability measures may include one or more already decoded symbols of the same symbol category, one or more already decoded symbols of the same symbol category that corresponds to data sets (such as blocks or bin groups) of adjacent spatial and/or temporal locations (with respect to the data set associated with the current syntactic element request), or one or more already decoded symbols of different symbol categories that correspond to data sets of the same and/or neighboring spatial and/or temporal locations (with respect to to the data set associated with the current syntax element request).

Each bean request with an associated set of parameters 317, which is the output of the parameter assigner 316, is supplied to a bean buffer selector 318. Based on the associated set of parameters 317, the bin buffer selector 318 sends a bin request 319 to one of two or more bin buffers 320 and receives a decoded bin 325 from the selected bin buffer 320. The decoded input bin 325 is potentially modified, and the decoded output bin 326—with the potentially modified value—is sent to binarizer 314 as a final response to the bean request with an associated set of parameters 317.

The bin buffer 320 to which the bin request is sent is selected in the same manner as the bin buffer to which the encoder-side bin buffer selector output bin was sent.

In a preferred embodiment of the invention, bin buffer selector 318 determines bin buffer 320 to which bin request 319 is sent based on an associated measure for estimating the probability for one of two possible bin values for the currently requested bin. In a preferred embodiment of the invention, the set of possible values for a probability estimate measure for one of the two possible bin values is finite, and the bin buffer selector 318 contains a table that associates exactly one bin buffer 320 with each possible probability estimate value for one of the two possible values. bin, where different values for the probability measure for one of two possible bin values may be associated with the same bin buffer 320. In another preferred embodiment of the invention, the range of possible values for the probability measure for one of two possible bin values is divided into several bins, the bin buffer selector 318 determines the bin index for the current probability measure for one of the two possible bin values, and the selector 318 The bin buffer contains a table that associates exactly one bin buffer 320 with each possible value for the bin index, where different values for the bin index can be associated with the same bin buffer 320. In a preferred embodiment of the invention, requests for bins 317 with opposing measures to estimate the probability for one of two possible bin values (the opposing measures being those representing P and 1-P probability estimates) are sent to the same bin buffer 320. In another preferred embodiment of the invention, associating a measure for estimating the probability for one of two possible bin values for the current bin request with a particular bin buffer is time-adapted.

In another preferred embodiment of the invention, bin buffer selector 318 determines bin buffer 320 to which bin request 319 is sent based on an associated measure for assessing the likelihood of a less likely or more likely bin value for the currently requested bin. In a preferred embodiment of the invention, the set of possible values for the probability estimate measure for a less likely or more likely bin value is finite, and the bin buffer selector 318 contains a table that associates exactly one bin buffer 320 with each possible probability estimate value for the less likely or more likely value. probable bin value, where different values for the probability measure for a less likely or more likely bin value may be associated with the same bin buffer 320. In another preferred embodiment of the invention, the range of possible values for the probability measure for a less likely or more likely bin value is divided into several bins, the bin buffer selector 318 determines the bin index for the current probability measure for the less likely or more likely bin value, and The bin buffer selector 318 contains a table that associates exactly one bin buffer 320 with each possible value for the bin index, where different values for the bin index may be associated with the same bin buffer 320. In another preferred embodiment of the invention, associating a measure for estimating the probability of a less likely or more likely bin value for the current bin request with a particular bin buffer is time-adapted.

Upon receiving the decoded bin 325 from the selected bin buffer 320, the bin buffer selector 318 potentially modifies the input bin 325 and sends the output bin 326—with the potentially modified value—to the binarizer 314. The input/output bin mapping of the bin buffer selector 318 is the inverse of the input/output bin mapping. bin buffer selector on the encoder side.

In the preferred embodiment of the invention, the bin buffer selector 318 does not modify the value of the bin, i.e. the output bin 326 always has the same value as the input bin 325. In another preferred embodiment of the invention, the bin buffer selector 318 determines the output bin value 326 based on the input bin value 325 and a measure for assessing the probability for one of two possible bin values for the current requested bin that is associated with the bin request 317. In a preferred embodiment of the invention, the output bin value 326 is set equal to the input bin value 325 if the measure for the probability for one of the two possible bin values for the current bin request is less than (or less than or equal to) specific threshold; if the measure for the probability for one of the two possible bin values for the current bin query is greater than or equal to (or greater than) a particular threshold, the output bin value 326 is modified (ie, set to the opposite value of the input bin value). In another preferred embodiment of the invention, the output bin value 326 is set equal to the input bin value 325 if the measure for the probability for one of the two possible bin values for the current bin request is greater than (or greater than or equal to) a particular threshold; if the measure for the probability for one of the two possible bin values for the current bin request is less than or equal to (or less than) a particular threshold, the output bin value 326 is modified (ie, set to the opposite value of the input bin value). In a preferred embodiment of the invention, the threshold value corresponds to a value of 0.5 for the estimated probability for both possible bin values.

In another preferred embodiment of the invention, the bean buffer selector 318 determines the output bean value 326 based on the input bean value 325 and an identifier specifying an estimate of which of two possible bean values represents the less likely or more likely bean value for the current bean request that is associated with request of bean 317. In the preferred embodiment of the invention, the output bean value 326 is set equal to the input bean value 325 if the identifier specifies that the first of two possible bean values represents the less likely (or more likely) bean value for the current bean request, and the output value 326 A bean is modified (that is, set to the opposite value of the input bean) if the identifier specifies that the second of two possible bean values represents the less likely (or more likely) bean value for the current bean request.

As described above, the bin buffer selector sends a bin request 319 to one of two or more bin buffers 320. Bin buffers 20 represent a first-in, first-out buffer into which sequences of decoded bins 321 from connected bin decoders 322 are supplied. In response to a request for bean 319 that is sent to bean buffer 320 from bean buffer selector 318, bean buffer 320 removes the bean from its contents that was first supplied to bean buffer 320 and sends it to bean buffer selector 318. Bins that were previously sent to bin buffer 320 are previously removed and sent to bin buffer selector 318.

Each of two or more bin buffers 320 is connected to exactly one bin decoder 322, and each bin decoder is connected to exactly one bin buffer 320. Each bin decoder 322 reads codewords 323, which represent sequences of bits, from a separate partial bit stream 324. The bin decoder converts the codeword 323 into a sequence of bins 321, which is sent to an attached bin buffer 320. A general decoding algorithm converts two or more partial bitstreams 324 into multiple decoded syntax elements, where the number of partial bitstreams is equal to the number of bin buffers and bin decoders, and decoding of syntax elements is triggered by requests for new syntax elements. In a preferred embodiment of the invention, bin decoder 322 converts variable-bit codewords 323 into a variable-bin sequence 321. One advantage of embodiments of the invention is that decoding bins from two or more partial bitstreams can be performed in parallel (e.g., for different groups probability measures), which reduces processing time for multiple implementations.

Another advantage of embodiments of the invention is that the bin decoding that is performed by bin decoders 322 can be specifically designed for different sets of parameters 317. In particular, bin encoding and decoding can be optimized (in terms of encoding efficiency and/or complexity) for different groups estimated probabilities. On the one hand, this makes it possible to reduce the complexity of encoding/decoding relative to modern entropy coding algorithms with similar coding efficiency. On the other hand, this makes it possible to improve the coding efficiency relative to modern entropy coding algorithms with similar encoding/decoding complexity. In a preferred embodiment of the invention, bin decoders 322 implement different decoding algorithms (ie, mapping bin sequences to codewords) for different groups of measures to estimate the probability for one of two possible bin values 317 for the current bin request. In another preferred embodiment of the invention, bin decoders 322 implement different decoding algorithms for different groups of measures to estimate the probability for a less likely or more likely bin value for the currently requested bin.

The bin decoders 322 perform the inverse mapping to the corresponding bin encoders on the encoder side.

In a preferred embodiment of the invention, bin decoders 322—or one or more of the bin decoders—are entropy decoders that directly map codewords 323 to a sequence of bins 321. Such mapping can be efficiently implemented and does not require a complex arithmetic encoding mechanism. The mapping of codewords in a sequence of bins must be unique. In a preferred embodiment of the invention, the mapping of codewords 323 to a sequence of bins 321 is bijective. In another preferred embodiment of the invention, the bin decoders 310—or one or more of the bin decoders—are entropy decoders that directly map variable-length codewords 323 into a sequence of variable-length bins 321. In a preferred embodiment of the invention, the input codewords represent non-redundant codes, such as general Huffman codes or canonical Huffman codes. Two examples for bijectively mapping non-redundant codes into a sequence of bins are given in Table 3.

In another preferred embodiment, the bin decoders 322—or one or more of the bin decoders—are entropy decoders that directly map fixed-length codewords 323 onto a variable-length sequence of bins 321. In another preferred embodiment, the bin decoders 322 are either one or Several of the bin decoders are entropy decoders that directly map variable-length codewords 323 onto a fixed-length sequence of bins 321.

Thus, FIG. 7 and 8 depict an embodiment for an encoder for encoding a sequence of symbols 3 and a decoder for reconstructing them. The encoder includes an assigner 304 configured to assign multiple parameters 305 to each symbol of the symbol sequence. The assignment is based on information contained in the previous characters of the character sequence, such as the category of syntax element 1 for representation - such as binarization - to which the current character belongs, and which, according to the syntax structure of syntax elements 1, is currently expected to be the expectation, in turn, is inferred from the history of previous syntax elements 1 and symbols 3. In addition, the encoder includes a plurality of entropy encoders 10, each of which is configured to convert symbols 3 sent to a corresponding entropy encoder into a corresponding bit stream 312. and a selector 306 configured to route each symbol 3 to a selected one of a plurality of entropy encoders 10, the choice depending on the number of parameters 305 assigned to the corresponding symbol 3. The assigner 304 can be viewed as being integrated into the selector 206 to obtain a corresponding selector 502.

The symbol decoder includes a plurality of entropy decoders 322, each of which is configured to convert a corresponding bit stream 323 into symbols 321; an assignment means 316 configured to assign multiple parameters 317 to each symbol 315 of the symbol sequence to be restored based on information contained in the previously restored symbols of the symbol sequence (see numerals 326 and 327 in FIG. 8); and a selector 318 configured to extract each symbol from the symbol sequence to be recovered from a selected one of a plurality of entropy decoders 322, the selection depending on the number of parameters defined for the corresponding symbol. The assigner 316 may be configured such that the number of parameters assigned to each symbol comprises, or represents, a measure for assessing the probability of distribution among the possible symbol values that the corresponding symbol can take. Again, the assignor 316 and the selector 318 may be considered to be integrated into a single block, the selector 402. The sequence of symbols to be recovered may be a binary alphabet, and the assignor 316 may be configured such that the probability distribution estimate consists of a measure for the probability estimate the less likely or more likely bin value of two possible binary alphabet bin values, and an identifier indicating which of the two possible bin values represents the less likely or more likely bin value. The assigner 316 may be further configured to internally assign a context to each symbol of the symbol sequence 315 to be recovered based on information contained in previously restored symbols of the symbol sequence to be recovered, each context having a corresponding probability distribution estimate associated with it, and adapting the probability distribution estimate for each context to the actual symbol statistics based on the symbol values of previously reconstructed symbols to which the corresponding context is assigned. Context may take into account the spatial dependence or proximity of positions to which syntactic elements belong, such as in video or image encoding, or even in tables, in the case of financial applications. A measure for estimating the probability distribution for each symbol can then be determined based on the estimate of the probability distribution associated with the context assigned to the corresponding symbol, for example, by quantization, or using as an index in the corresponding table, the estimate of the probability distribution associated with the context assigned to the corresponding a symbol (in subsequent embodiments, indexed by the pipe index along with the refinement index) to one of a plurality of representatives of the probability distribution estimate (cutting off the refinement index) to obtain a measure for the probability distribution estimate (the pipe index indexes the partial bitstream 312). The selector may be configured to define a bijective association between a plurality of entropy encoders and a plurality of probability distribution estimate representatives. The selector 18 may be configured to change over time the quantization mapping from a range of probability distribution estimates to a set of representatives of the probability distribution estimate in a predetermined deterministic manner depending on the previously reconstructed symbols of the symbol sequence. Those. selector 318 can change the quantization step size, i.e. intervals of probability distributions mapped onto individual probability indices bijectively associated with individual entropy decoders. The plurality of entropy decoders 322, in turn, may be configured to adapt their method of converting symbols to bitstreams in response to a change in the quantization mapping. For example, each entropy decoder 322 may be optimized, i.e. may have an optimal compression ratio, for some probability distribution estimate, within a corresponding probability distribution estimate quantization interval, and may change the mapping of its codewords/symbol sequence to adapt the position of that certain probability distribution estimate within a corresponding probability distribution estimate quantization interval as the latter changes so that it is optimized. The selector may be configured to change the quantization mapping such that the rates at which symbols are extracted from the plurality of entropy decoders are made less spread out. With regard to the binarizer 314, it is noted that it may be omitted if the syntax elements are already binary. In addition, depending on the type of decoder 322, the existence of buffers 320 is not necessary. In addition, buffers can be integrated into decoders.

Completion of finite sequences of syntactic elements

In a preferred embodiment of the invention, encoding and decoding is performed on a finite set of syntactic elements. Often a quantity of data is encoded, such as a still image, a frame or field of a video sequence, a slice of an image, a slice of a frame or field of a video sequence, or a plurality of sequential audio sampling units, etc. For finite sets of syntax elements, as a rule, partial bitstreams that are created on the encoder side must be terminated, i.e. it is necessary to ensure that all syntax elements can be decoded from transmitted or stored partial bitstreams. After the last bin is inserted into the corresponding bin buffer 308, the bin encoder 310 must ensure that the complete codeword is written to the partial bitstream 312. If the bin encoder 310 represents an entropy encoder that implements a direct mapping of sequences of bins to codewords, the sequence of bins , which is stored in the bean buffer after the last bin is written to the bean buffer, may not represent a sequence of bins that is associated with a codeword (ie, it may represent a prefix of two or more sequences of bins that are associated with codewords). In such a case, any of the codewords associated with a sequence of bins that contains the sequence of bins in the bin buffer as a prefix must be written to the partial bitstream (the bin buffer must be cleared). This can be done by inserting bins with a specific or arbitrary value into the bin buffer until the codeword is written. In a preferred embodiment of the invention, the bin encoder selects one of the codewords with the minimum length (in addition to the property that the associated bin sequence must contain the bin sequence in the bin buffer as a prefix). On the decoder side, bin decoder 322 can decode more bins than required for the last codeword in the partial bitstream; these beans are not requested by the bean buffer selector 318 and are discarded and ignored. The decoding of a finite set of symbols is controlled by queries on the syntax elements being decoded; if no further syntax element is requested for the amount of data, decoding is completed.

Transmission and multiplexing of partial bit streams

The partial bitstreams 312 that are created by the encoder may be transmitted separately, or they may be multiplexed into a single bitstream, or the codewords of the partial bitstreams may be interleaved into a single bitstream.

In an embodiment of the invention, each partial bitstream for a certain amount of data is written into one data packet. The amount of data may be an arbitrary plurality of syntactic elements, such as a still image, a field or frame of a video sequence, a slice of a still image, a slice of a field or frame of a video sequence, or a frame of audio sampling units, etc.

In another preferred embodiment of the invention, two or more partial bitstreams for an amount of data, or all partial bitstreams for an amount of data, are multiplexed into one data packet. The structure of a data packet that contains multiplexed partial bit streams is shown in FIG. 9.

Data packet 400 consists of a header and one data section for each partial bitstream (for the amount of data in question). The data packet header 400 contains instructions for dividing the (remainder of) the data packet into bitstream data segments 402. In addition to instructions for separation, the header may contain additional information. In a preferred embodiment of the invention, the indications for dividing a data packet are the locations of the beginning of the data segments in units of bits or bytes or multiples of bits or multiples of bytes. In a preferred embodiment of the invention, the locations of the beginnings of data segments are encoded as absolute values in the data packet header, either relative to the start of the data packet, or relative to the end of the header, or relative to the beginning of the previous data packet. In another preferred embodiment of the invention, the start locations of the data segments are encoded differentially, i.e. Only the difference between the actual start of the data segment and the prediction for the start of the data segment is encoded. The prediction may be derived based on information already known or transmitted, such as the total size of the data packet, the size of the header, the number of data segments in the data packet, the location of the beginning of previous data segments. In a preferred embodiment of the invention, the location of the start of the first data packet is not encoded, but is inferred based on the size of the data packet header. On the decoder side, the passed section instructions are used to infer the beginning of the data segments. The data segments are then used as partial bitstreams, and the data contained in the data segments is supplied to the corresponding bin decoders in sequential order.

There are several alternatives for multiplexing partial bit streams into a data packet. One alternative that may reduce the required additional information, particularly for cases in which the sizes of the partial streams are very similar, is depicted in FIG. 10. Data packet payload, i.e. data packet 410 without header 411 is divided into segments 412 in a predetermined manner. As an example, the payload of a data packet may be divided into equally sized segments. Each segment is then associated with a partial bitstream or a first portion of the partial bitstream 413. If the partial bitstream is larger than the associated data segment, the remainder of it 414 is allocated to unused space at the end of the other data segments. This can be done in such a way that the remainder of the bit stream is inserted in reverse order (starting from the end of the data segment), thereby reducing additional information. Associate the remaining portions of the partial bitstreams with data segments, and when more than one remaining portion is added to a data segment, the starting point for one or more remaining portions must be signaled within the bitstream, for example in a data packet header.

Variable Length Codeword Interleaving

For some applications, the above-described multiplexing of partial bit streams (for a certain number of syntax elements) in one data packet may have the following disadvantages: On the one hand, for small data packets, the number of bits for additional information that is required for split signaling can become significant relative to the actual data in partial bit streams, which ultimately reduces encoding efficiency. On the other hand, multiplexing may not be suitable for applications that require low latency (for example, videoconferencing applications). With the multiplexing described, the encoder cannot begin transmitting a data packet before the partial bitstreams have been completely created, since the locations of the start of the sections are previously unknown. Additionally, the decoder typically has to wait until it receives the beginning of the last data segment before it can begin decoding the data packet. For applications such as videoconferencing systems, these delays can add to the additional overall latency of a multi-image system (particularly for bit rates that are close to the bit rate and for encoders/decoders that require almost the time interval between two images to encode / image decoding), which is critical for such applications. To overcome the disadvantages for some applications, the encoder of a preferred embodiment of the invention may be configured such that codewords that are generated by two or more bin encoders are interleaved into a single bit stream. The bitstream with interleaved codewords can be sent directly to the decoder (ignoring the low buffer latency, see below). On the decoder side, two or more bin decoders read codewords directly from the bitstream in decoding order; decoding may begin with the first bit received. In addition, no additional information is required to signal the multiplexing (or interleaving) of the partial bit streams. Another way to reduce decoder complexity can be achieved when the bin decoders 322 do not read variable-length codewords from the global bit buffer, but instead, they always read fixed-length bit sequences from the global bit buffer and add these fixed-length bit sequences to the local buffer. bits, where each 322 bin decoder is connected to a separate local bit buffer. The variable length codewords are then read from the local bit buffer. Therefore, parsing of variable-length codewords can be done in parallel, only access to fixed-bit-length sequences must be done in a synchronized manner, but such access to fixed-bit-length sequences is typically very fast, so the overall decoding complexity can be reduced for some architectures. The fixed number of bins that are sent to a particular local bit buffer may be different for different local bit buffers, and it may also vary over time depending on some parameters such as events in the bin decoder, bin buffer, or bit buffer. However, the number of bits that are read by a particular access is independent of the actual bits that are read during a particular access, which is an important difference from reading variable-length codewords. Reading of fixed bit length sequences is triggered by some events in bin buffers, bin decoders, or local bit buffers. As an example, it is possible to issue a read request for a new sequence of fixed bit lengths when the number of bits that are present in the connected bit buffer falls below a given threshold, where different thresholds may be used for different bit buffers. The encoder needs to ensure that fixed-length bin sequences are inserted in the same order into the bitstream in which they are read from the decoder-side bitstream. It is also possible to combine this fixed length sequence interleaving with low latency control, like those described above. A preferred embodiment for interleaving fixed bit length sequences is described below. For further details regarding the latest interleaving schemes, reference is made to WO2011/128268A1.

After describing embodiments in which even earlier encoding is used to compress video data, another embodiment for implementing embodiments of the present invention is described, which depicts an implementation that is particularly effective in the sense of a good compromise between the compression ratio on the one hand and the lookup table and computational overhead, on the other hand. In particular, the following embodiments allow the use of less computationally complex variable length codes for entropy encoding of individual bit streams, and effectively close off the probability estimation portions. In the embodiments described below, the symbols are of a binary nature, and the VLC codes (variable length codes) presented below effectively cover the probability estimate represented, for example, by R _{LPS (least probable symbol)} passing within [0; 0.5].

In particular, the embodiments briefly described below describe possible implementations for individual entropy encoders 310 and decoders 322 in FIG. 7-17 respectively. They are suitable for encoding bins, i.e. binary characters as they occur in image or video compression applications. Therefore, these embodiments are also applicable to image or video encoding, where such binary symbols are divided into one or more bin streams 307 to be encoded and bit streams 324 to be decoded, respectively, where each such bin stream can be considered an implementation of a Bernoulli process. The embodiments described below use one or more of the various so-called variable-to-variable codes (v2v codes) explained below to encode bin streams. A v2v code can be considered as two prefix-free codes with the same number of codewords. Primary and secondary prefix-free code. Each codeword of the primary unprefixed code is associated with one codeword of the secondary unprefixed code. In accordance with the embodiments briefly described below, at least some of the encoders 310 and decoders 322 operate as follows: To encode a particular sequence of bins 307, whenever a primary unprefixed code codeword is read from buffer 308, a corresponding secondary unprefixed codeword is written to bitstream 312. The same procedure is used to decode such bitstream 324, but the primary and secondary prefix-free code are swapped. Those. to decode bitstream 324, whenever a secondary prefix-free code codeword is read from a corresponding bitstream 324, a corresponding primary prefix-free code codeword is written to buffer 320.

Helpfully, the codes described below do not require lookup tables. The codes are implementable as finite state machines. The v2v codes presented here can be generated by simple construction rules, such as that there is no need to store large tables for codewords. Instead, a simple algorithm can be used to perform encoding or decoding. Three construction rules are described below, where two of them can be parameterized. They cover different or even non-overlapping parts of the above probability interval and are therefore particularly useful if used together, for example all three codes in parallel (each for different encoders/decoders 11 and 22) or two of them. With the construction rules described below, it is possible to design a set of v2v codes such that, for Bernoulli processes with arbitrary probability p, one of the codes performs well with respect to excess code length.

As discussed above, encoding and decoding of streams 312 and 324, respectively, may be performed either independently on a per-stream basis or in an interleaved manner. This, however, is not specific to the presented classes of v2v codes, and therefore only the encoding and decoding of a specific codeword is described for each of the three construction rules in the following. However, it is emphasized that all of the above embodiments regarding interleaved solutions are also suitable for combining with the currently described codes or encoders and decoders 310 and 322, respectively.

Construction Rule 1: Unary Bin Pipe Codes or Encoders/Decoders 310 and 322

Unary bin pipe entropy codes are a special version of the so-called “pipe bin” codes, i.e. codes suitable for encoding any of the individual bit streams 12 and 24, each carrying binary symbol statistics data belonging to some probability subinterval of the aforementioned probability range [0; 0.5]. First, the construction of pipe bean codes is described. The pipe bean code can be constructed from any prefix-free code with at least three codewords. To form a v2v code, it uses a prefix-free code as the primary and secondary code, but the two codewords of the secondary prefix-free code are swapped. This means that, with the exception of two codewords, the bins are written unchanged to the bitstream. With this method, only one prefix-free code needs to be stored along with the information which two codewords are swapped, and thus memory consumption is reduced. Note that this only makes sense for permuting codewords of different lengths, since otherwise the bitstream will be the same length as the binstream (ignoring effects that may occur at the end of the binstream).

Because of this construction rule, a known property of pipe bean codes is that if the primary and secondary unprefixed code are swapped (while the codeword mapping is preserved), the resulting v2v code is identical to the original v2v code. Therefore, the encoding algorithm and decoding algorithm are identical for pipe bin codes.

The pipe code of unary bins is composed of a special prefix-free code. This special prefix-free code is composed as follows. First, a prefix-free code consisting of n unary codewords is generated, starting with "01", "001", "0001", ..., until n codewords are obtained. n is a parameter for the pipe code of unary bins. The trailing 1 is removed from the longest codeword. This corresponds to a truncated unary code (but without the codeword "0"). Then n-1 unary codewords are generated, starting with "10", "110", "1110", ..., until n-1 codewords are obtained. The longest of these codewords is stripped of the trailing 0. The union set of these two prefix-free codewords is used as input to generate the unary bin code pipe. The two codewords that are swapped are one consisting of only 0s and one consisting of only 1s.

Example for n=4:

No. Primary Secondary

1 0000 111

2 001 0001

3 001 001

4 01 01

5 10 10

6 110 110

7 111 0000

Construction rule 2: Unary-to-Rice codes and unary-to-Rice encoders/decoders 10 and 22:

Unary-to-Rice codes use a truncated unary code as the primary code. Those. unary codewords are generated starting with "1", "01", "001", ..., until ²ⁿ +1 codewords have been generated and the trailing 1 is removed from the longest codeword. n is the unary-to-Rice parameter -code. The secondary prefix-free code is composed of the code words of the primary prefix-free code as follows. The primary codeword consisting of only 0s is assigned a codeword of "1". All other codewords consist of the concatenation of a codeword "0" with an n-bit binary representation of the number of 0s of the corresponding codeword of the primary unprefixed code.

Example for n=3:

No. Primary Secondary

1 1 0000

2 01 0001

3 001 0010

4 0001 0011

5 00001 0100

6 000001 0101

7 0000001 0110

8 00000001 0111

9 00000000 1

Note that this is identical to mapping an infinite unary code to a Rice code with a Rice parameter of 2 ⁿ .

Construction rule 3: “Three-bin” code

The three-bin code is defined as:

No. Primary Secondary

1 000 0

2,001,100

3 010 101

4 100 110

5 110 11100

6 101 11101

7 011 11110

8 111 11111

It has the property that the primary code (sequence of symbols) has a fixed length (always three bins) and the codewords are sorted in ascending numbers of 1.

An efficient implementation of three-bin code is described below. An encoder and decoder for a three-bin code can be implemented without storing tables as follows.

In the encoder (any one of 10), three bins are read from a stream of bins (i.e. 7). If these three bins contain exactly one 1, the codeword "1" is written to the bitstream, followed by two bins consisting of the binary representation of the position 1 (starting on the right with 00). If three bins contain exactly one 0, the codeword "111" is written to the bitstream, followed by two bins consisting of the binary representation of the 0 position (starting at the right with 00). The remaining code words "000" and "111" are mapped to "0" and "11111" respectively.

In a decoder (any one of 22), one bin or bit is read from the corresponding bitstream 24. If it is "0", the codeword "000" is decoded into a stream of 21 bins. If it is equal to "1", two more bins are read from bitstream 24. If these two bits are not equal to "11", they are interpreted as the binary representation of the number, and two 0s and one 1 are decoded into the bitstream, so that the position of 1 is determined by the number . If two bits are equal to "11", two more bits are read and interpreted as the binary representation of the number. If this number is less than 3, two 1s and one 0 are decoded, and the number defines the position of 0. If it is 3, "111" is decoded into a stream of bins.

The following describes an efficient implementation of pipe codes for unary beans. An encoder and decoder for pipe codes of unary bins can be efficiently implemented by using a counter. Due to the structure of pipe bean codes, encoding and decoding of pipe bean codes is easy to implement:

In an encoder (any of 10), if the first bin of a codeword is "0", the bins are processed until a "1" is encountered, or until n 0s are read (including the first "0" of the codeword). If a “1” is encountered, the read bins are written unchanged to the bitstream. Otherwise, (i.e. n 0s have been read), n-1 1s are written to the bitstream. If the first bin of a codeword is a "1", the bins are processed until a "0" is encountered or until n-1 1s are read (including the first "1" of the codeword). If a "0" is encountered, the read bins are written unchanged to the bitstream. Otherwise, (ie n-1 1s have been read), n 0 is written to the bitstream.

The decoder (any of the 322) uses the same algorithm as the encoder, since it is the same for pipe bin codes as described above.

An efficient implementation of unary-to-Rice codes is described below. An encoder and decoder for unary-to-Rice codes can be efficiently implemented by using a counter, as described below.

In an encoder (any of the 310), bins are read from a stream of bins (ie 7) until a 1 is encountered, or until 2 ⁿ 0s are read. The number of 0s is counted. If the counted quantity is ²ⁿ , the codeword "1" is written to the bitstream. Otherwise, a "0" is written, followed by the binary representation of the counted quantity, written with n bits.

In the decoder (any of 322) one bit is read. If it is "1", 2 ⁿ 0 is decoded into a string of bins. If it is "0", another n bits are read and interpreted as a binary representation of the quantity. This number of 0's is decoded into a stream of bins followed by "1's".

In other words, the embodiments just described describe an encoder for encoding a symbol sequence 303, comprising an assigner 316 configured to assign multiple parameters 305 to each symbol of the symbol sequence based on information contained in previous symbols of the symbol sequence; a plurality of entropy encoders 310, each configured to convert symbols 307 sent to a corresponding entropy encoder 310 into a corresponding bit stream 312; and a selector 6 configured to route each symbol 303 to a selected one of a plurality of entropy encoders 10, the selection depending on the number of parameters 305 assigned to the corresponding symbol 303. According to the embodiments just described, at least the first subset of entropy encoders may be a variable encoder length, configured to map sequences of variable length symbols in symbol stream 307 to variable length codewords to be inserted into bitstream 312, respectively, each of the first subset entropy encoders 310 using a bijective mapping rule whereby codewords of the primary unprefixed code with ( 2n-1)≥3 codewords are mapped to codewords of a secondary prefix-free code that is identical to the primary prefix code, such that all but two of the primary prefix-free code codewords are mapped to identical codewords of the secondary prefix-free code, whereas two codewords of the primary and secondary prefix-free codes have different lengths and map onto each other alternately, with entropy coders able to use different n to cover different parts of the above-mentioned probability interval. The first prefix-free code can be composed such that the code words of the first prefix-free code are (a,b) ₂ , (a,a,b) ₃ , ..., (a, ..., a,b) _n , (a, ..., a) _n , (b,a) ₂ , (b,b,a) ₃ , …, (b, …, b,a) _n-1 , (b, …, b) _n-1 , and two codewords displayed on each other alternately, are (a, …, a) _n and (b, …, b) _n-1 with b≠a and a,b {0,1}. However, alternatives are possible.

In other words, each of the first subset of entropy encoders may be executed by converting symbols sent to the corresponding entropy encoder to a corresponding bit stream, with the ability to examine the first symbol sent to the corresponding entropy encoder to determine whether (1) the first symbol is equal to a {0,1}, in which case the corresponding entropy encoder is executed with the ability to examine the next symbols sent to the corresponding entropy encoder to determine whether (1.1) b occurs with b≠a and b {0,1} in the next n-1 symbols following the first symbol, in which case the corresponding entropy encoder is configured to write a codeword into the corresponding bitstream, which is equal to the first symbol followed by subsequent symbols sent to the corresponding entropy encoder, before character b; (1.2) whether b occurs in the next n-1 symbols following the first symbol, in which case the corresponding entropy encoder is executed with the ability to write the codeword into the corresponding bitstream, which is equal to (b, ..., b) _n-1 ; or (2) whether the first symbol is equal to b, in which case the corresponding entropy encoder is executed with the ability to examine subsequent symbols sent to the corresponding entropy encoder to determine whether (2.1) whether a occurs in the next n-2 symbols following the first symbol, in In this case, the corresponding entropy encoder is configured to write a codeword into the corresponding bit stream, which is equal to the first symbol, followed by subsequent symbols sent to the corresponding entropy encoder, up to the symbol a; or (2.2) whether a occurs in the next n-2 symbols following the first symbol, in which case the corresponding entropy encoder is executed with the ability to write a codeword into the corresponding bitstream, which is equal to (a, ..., a) _n .

Additionally or alternatively, the second subset of entropy encoders 10 may be a variable-length encoder configured to map variable-length symbol sequences to fixed-length codewords, respectively, wherein each of the second subset of entropy encoders uses a bijective mapping rule whereby the codewords of the primary truncated unary code with 2 ⁿ +1 codewords of type {(a), (ba), (bba), …, (b…ba), (bb…b)} with b≠a and a,b {0,1} are mapped to codewords of the secondary unprefixed code, so that codeword (bb...b) of the primary truncated unary code is mapped to codeword (c) of the secondary unprefixed code, and all other codewords {(a), (ba) , (bba), …, (b…ba)} of the primary truncated unary code are mapped onto codewords having (d) with c≠d and c,d {0,1} as a prefix and an n-bit word as a suffix, with entropy encoders using different n. Each of the second subset of entropy encoders may be configured such that the n-bit word is an n-bit representation of the quantity b in the corresponding code word of the primary truncated unary code. However, alternatives are possible.

Again, in terms of the mode of operation of the corresponding encoder 10, each of the second subset of entropy encoders may be executed by converting the symbols sent to the corresponding entropy encoder into a corresponding bitstream, with the ability to count the number of b in the sequence of symbols sent to the corresponding entropy encoder until until encountered, or until the number of symbol sequences sent to the corresponding entropy encoder reaches ²ⁿ , with all ²ⁿ symbols in the sequence equal to b, and (1) if the number of b is ²ⁿ , records c with c {0,1} as a codeword of the secondary prefix-free code into the corresponding bitstream, and (2) if the number of b is less than ²ⁿ , writing the codeword of the secondary prefix-free code into the corresponding bitstream which has (d) with c≠d and d {0,1} as a prefix and an n-bit word defined depending on the number of b as a suffix.

Also additionally or alternatively, a predefined one of the entropy encoders 10 may be a variable length encoder configured to map sequences of fixed length symbols to variable length codewords, respectively, wherein the predefined entropy encoder uses a bijective mapping rule whereby 2 ^{by 3} codewords of length The 3 primary codes map to codewords of the secondary prefix-free code, so that codeword (aaa) ₃ of the primary code with a {0,1}, mapped to codeword (c) with c {0,1}, all three primary code words having exactly one b with b≠a and b {0,1}, are mapped to codewords having (d) with c≠d and d {0,1} as a prefix and the corresponding first 2-bit word of the first set of 2-bit words as a suffix, all three primary code codewords having exactly one a are mapped to codewords having (d) as prefix and concatenation of a first 2-bit word not a member of the first set and a second 2-bit word from the second set of 2-bit words as a suffix, and in which codeword (bbb) ₃ is mapped to a codeword having (d ) as a prefix and the concatenation of the first 2-bit word that is not an element of the first set and the second 2-bit word that is not an element of the second set as a suffix. The first 2-bit word of the primary code codewords having exactly one b may be the 2-bit representation of the position of b in the corresponding primary code codeword, and the second 2-bit word of the primary code codewords having exactly one a may be 2 -bit representation of position a in the corresponding codeword of the primary code. However, alternatives are possible.

Again, a predefined one of the entropy encoders can be performed by converting the symbols sent to the predefined entropy encoder into the corresponding bitstream, with the ability to examine the symbols per predefined entropy encoder in triplets, (1) whether the triplet consists of a, in which case a predefined entropy encoder is executable to write a codeword (c) into the corresponding bit stream, (2) whether the triple contains exactly one b, in which case the predefined entropy encoder is executable to write a codeword having (d) as a prefix, and a 2-bit representation of the position of b in the triple as a suffix, into the corresponding bitstream; (3) whether the triple contains exactly one a, in which case a predefined entropy encoder is executed with the ability to write a codeword having (d) as a prefix and the concatenation of the first 2-bit word not an element of the first set and the 2-bit representation the position of a in the triple as a suffix, into the corresponding bitstream; or (4) whether the triple consists of b, in which case a predefined entropy encoder is executed with the ability to write a codeword having (d) as a prefix and the concatenation of the first 2-bit word not an element of the first set and the first 2-bit a word that is not an element of the second set as a suffix into the corresponding bit stream.

On the decoding side, the embodiments just described describe a symbol sequence recovery decoder 326 comprising a plurality of entropy decoders 322, each configured to convert a corresponding bitstream 324 into symbols 321; an assignment means 316 configured to assign multiple parameters to each character 326 of the character sequence to be recovered based on information contained in the previously recovered symbols of the character sequence; and a selector 318 configured to extract each symbol 325 of the symbol sequence to be recovered from a selected one of a plurality of entropy decoders, the selection depending on the number of parameters defined for the corresponding symbol. According to the embodiments just described, at least the first subset of entropy decoders 322 are variable length decoders configured to map variable length codewords onto variable length symbol sequences, respectively, wherein each of the first subset entropy decoders 22 uses a bijective mapping rule, according to with which codewords of a primary prefix-free code with (2n-1)≥3 codewords are mapped onto codewords of a secondary prefix-free code that is identical to the primary prefix code, such that all but two of the primary prefix-free code codewords are mapped to identical codewords of the secondary prefix-free code , while the two codewords of the primary and secondary prefix-free codes have different lengths and are mapped onto each other alternately, with entropy coders using different n. The first prefix-free code can be constructed so that the code words of the first prefix-free code are (a,b) ₂ , (a,a,b) ₃ , ..., (a, ..., a,b) _n , (a, ..., a ) _n , (b,a) ₂ , (b,b,a) ₃ , …, (b, …, b,a) _n-1 , (b, …, b) _n-1 , and two codewords, mapped onto each other alternately, there can be (a, …, a) _n and (b, …, b) _n-1 with b≠a and a,b {0,1}. However, alternatives are possible.

Each of the first subset of entropy encoders may be implemented, when converting the corresponding bit stream into symbols, with the ability to examine the first bit of the corresponding bit stream to determine (1) whether the first bit a 0 {0,1}, in which case the corresponding entropy the encoder is executed with the ability to examine the next bits of the corresponding bitstream to determine whether (1.1) b occurs with b≠a and b 0 {0,1} in the next n-1 bits following the first bit, in which case the corresponding entropy decoder is executed with the ability to restore a sequence of symbols that is equal to the first bit followed by subsequent bits of the corresponding bit stream, up to bit b; or (1.2) whether b occurs in the next n-1 bits following the first bit, in which case the corresponding entropy decoder is executed with the ability to recover a sequence of symbols that is equal to (b, ..., b) _n-1 ; or (2) whether the first bit is equal to b, in which case the corresponding entropy decoder is executed with the ability to examine subsequent bits of the corresponding bitstream to determine whether (2.1) whether a occurs in the next n-2 bits following the first bit, in which case the corresponding the entropy decoder is configured to recover a sequence of symbols that is equal to the first bit followed by subsequent bits of the corresponding bit stream up to symbol a; or (2.2) whether a does not occur in the next n-2 bits following the first bit, in which case the corresponding entropy decoder is executed with the ability to recover a sequence of symbols that is equal to (a, ..., a) _n .

Additionally or alternatively, at least the second subset of entropy decoders 322 may be a variable-length decoder configured to map fixed-length codewords onto variable-length symbol sequences, respectively, wherein each of the second subset of entropy decoders uses a bijective mapping rule whereby the codewords secondary prefix-free code are mapped onto codewords of a primary truncated unary code with 2 ⁿ +1 codewords of type {(a), (ba), (bba), …, (b…ba), (bb…b)} with b≠a and a,b {0,1}, so that codeword (c) of the secondary prefix-free code is mapped to codeword (bb...b) of the primary truncated unary code, and codewords having (d) with c≠d and c,d {0,1} as a prefix and an n-bit word as a suffix, are mapped to the corresponding one of the other codewords {(a), (ba), (bba), …, (b…ba))} of the primary truncated unary code, and entropy decoders use different n. Each of the second subset of entropy decoders may be configured such that the n-bit word is an n-bit representation of the quantity b in the corresponding primary truncated unary code word. However, alternatives are possible.

Each of the second subset of entropy decoders may be a variable-length decoder configured to map fixed-length codewords onto variable-length symbol sequences, respectively, and configured, when converting the bit stream of the corresponding entropy decoder into symbols, to examine the first bit of the corresponding bit stream for determining (1) whether it is equal to c with c {0,1}, in this case the corresponding entropy decoder is executed with the ability to restore a sequence of symbols that is equal to (bb...b) ₂ ⁿ with b {0,1}; or (2) is it equal to d with c≠d and c,d {0,1}, in which case the corresponding entropy decoder is configured to determine an n-bit word from the n additional bits of the corresponding bit stream following the first bit, and recover from them a sequence of symbols that is of the type {(a), (ba ), (bba), …, (b…ba), (bb…b)} with b≠a and b {0,1}, and the number of b depends on the n-bit word.

Additionally or alternatively, a predefined one of the entropy decoders 322 may be a variable length decoder configured to map variable length codewords onto a fixed length symbol sequence, respectively, wherein the predefined entropy decoder uses a bijective mapping rule whereby codewords of a secondary prefix-free code are mapped by 2 ³ codewords of length 3 primary code, so codeword (c) with c {0,1} maps to codeword (aaa) ₃ of the primary code with a {0,1}, codewords having (d) with c≠d and d {0,1} as a prefix and the corresponding first 2-bit word from the first set of three 2-bit words as a suffix, map to all three primary code codewords having exactly one b with b≠a and b {0,1}, codewords having (d) as a prefix and the concatenation of the first 2-bit word not a member of the first set and the second 2-bit word from the second set of three 2-bit words as a suffix, are mapped to all three codewords of the primary code having exactly one a, and a codeword having (d) as a prefix and the concatenation of the first 2-bit word not an element of the first set and the second 2-bit word not an element of the second sets, as a suffix, is mapped to the code word (bbb) ₃ . The first 2-bit word of the primary code codewords having exactly one b can be a 2-bit representation of the position of b in the corresponding primary code codeword, and the second 2-bit word of the primary code codewords having exactly one a can be a 2-bit representation of position a in the corresponding primary code word. However, alternatives are possible.

A predetermined one of the entropy decoders may be a variable length decoder, configured to map variable length codewords onto a symbol sequence of three symbols each, respectively, and configured, when converting the bitstream of the corresponding entropy decoder into symbols, to examine the first bit of the corresponding bitstream stream to determine whether (1) the first bit of the corresponding bitstream c is equal to c {0,1}, in this case the given entropy decoder is executed with the ability to recover a sequence of symbols that is equal to (aaa) ₃ with a 0 {0,1}; or (2) whether the first bit of the corresponding bitstream is equal to d with c≠d and d {0,1}, in this case the predefined entropy decoder is executed with the ability to determine the first 2-bit word of the 2 additional bits of the corresponding bitstream that follows the first bit, and with the ability to examine the first 2-bit word to determine, (2.1 ) whether the first 2-bit word is an element of the first set of three 2-bit words, in which case a predefined entropy decoder is executed with the ability to recover a sequence of symbols that has exactly one b with b≠a and b 0 {0,1} , where the position of b in the corresponding symbol sequence depends on the first 2-bit word, or (2.2) whether the first 2-bit word is an element of the first set, in which case a predefined entropy decoder is executed with the ability to determine the second 2-bit word from 2 additional bits of the corresponding bit stream following the two bits from which the first 2-bit word was defined, and with the possibility of examining the second 2-bit word to determine whether the second 2-bit word is an element of the second set of three 2-bits bit words, in which case the predefined entropy decoder is executed with the ability to recover a symbol sequence that has exactly one a, where the position of a in the corresponding symbol sequence depends on the second 2-bit word, or (3.2) whether the second 2-bit word is an element a second set of three 2-bit words, in which case a predefined entropy decoder is executed with the ability to recover a sequence of symbols that is equal to (bbb) ₃ .

Now that the general principle of a video coding scheme has been described, embodiments of the present invention will be described with respect to the above-mentioned embodiments. In other words, the embodiments briefly described below can be implemented by using the above-mentioned circuits, and conversely, the above encoding schemes can be implemented using and using the embodiments briefly described below.

In the above embodiments described with respect to FIGS. 7-9, the entropy encoder and decoders of FIG. 1-6 were implemented in accordance with the PIPE principle. One particular embodiment used arithmetic single-probability state encoders/decoders 310 and 322. As described below, according to an alternative embodiment, objects 306-310 and corresponding objects 318-322 can be replaced by a conventional entropy encoding mechanism. As an example, imagine an arithmetic encoding mechanism that manages only one common state R and L and encodes all symbols into one common bitstream, thus abandoning the beneficial parallel processing aspects of the present PIPE principle, but eliminating the need for interleaving partial bitstreams. as further described below. By doing so, the number of probabilistic states by which context probabilities are estimated through an update (such as a table lookup) may be higher than the number of probabilistic states by which subdivision of the probability interval is performed. Those. Similar to quantizing the probability interval width value before indexing into the Rtab table, the probability state index can also be quantized. The above description for a possible implementation for single encoders/decoders 310 and 322 can thus be extended to an example implementation of entropy encoders/decoders 318-322/306-310 as context-adaptive binary arithmetic encoding/decoding engines.

More specifically, according to an embodiment, an entropy encoder connected to the output of the parameter assigner (which here serves as the context assigner) may operate as follows:

0. The assignor 304 forwards the bin value along with the probability parameter. The probability is pState_current[bin].

1. Thus, the entropy encoding mechanism takes: 1) valLPS, 2) bin, and 3) probability distribution estimate pState_current[bin]. pState_current[bin] can have more states than the number of distinguishable probabilistic state indices Rtab. If this is the case, pState_current[bin] may be quantized so that, for example, by ignoring m least significant bits (LSB), with m greater than or equal to 1 or preferably 2 or 3 to obtain p_state, i.e. an index which is then used to access the Rtab table. Quantization, however, can be excluded, i.e. p_state can be pState_current[bin].

2. R quantization is then performed (As mentioned above: either one R (and corresponding L with one shared bitstream) is used/managed for all distinguishable p_state values, or one R (and corresponding L with associated partial bitstream per R/L pair ) to a distinguishable p_state value, this latter case would correspond to the fact that there is one 310 bin encoder for such a value)

q_index=Qtab[R>>q] (or some other kind of quantization)

3. Then the determination of R _LPS and R is performed:

R _LPS =Rtab[p_state][q_index]; Rtab stored pre-calculated values for p[p_state]∙Q[q_index] in it

R=RR _LPS [i.e. R is pre-updated as if the "bin" were MPS (most probable symbol)]

4. Calculate the new preliminary interval:

if (bin=1-valMPS) then

L ¬ L+R

R ¬ R _LPS

5. L and R renormalization, bit recording,

Likewise, an entropy decoder connected to the output of the parameter assigner (which serves here as the context assigner) can operate as follows:

0. The assignor 304 forwards the bin value along with the probability parameter. The probability is pState_current[bin].

1. Thus, the entropy decoding engine accepts a bin request along with: 1) valLPS, and 2) an estimate of the probability distribution pState_current[bin]. pState_current[bin] can have more states than the number of distinguishable probabilistic state indices Rtab. If so, pState_current[bin] can be quantized like this, for example neglecting m LSB, with m greater than or equal to 1 and preferably 2 or 3 to obtain p_state, i.e. index, which is then used to access the Rtab table. Quantization, however, can be excluded, i.e. p_state can be pState_current[bin].

2. R quantization is then performed (As mentioned above: either one R (and corresponding V with one shared bitstream) is used/managed for all distinguishable p_state values, or one R (and corresponding V with associated partial bitstream per R/L pair ) to a distinguishable value of p_state, this last case corresponds to the fact that there is one encoder of 310 bins for such a value)

q_index=Qtab[R>>q] (or some other kind of quantization)

3. Then the determination of R _LPS and R is performed:

R _LPS =Rtab[p_state][q_index]; Rtab stored pre-calculated values for p[p_state]∙Q[q_index]

R=RR _LPS [i.e. R is pre-updated as if the "bin" were MPS]

4. Definition of a bin depending on the position of the partial interval:

if(V ³ R) then

bin ¬ 1 - valMPS (bin is decoded as LPS; bin buffer selector 18 obtains the actual value of the bin by using this bin information and valMPS)

V ¬ V-R

R ¬ R _LPS

else

bin ¬ valMPS (the bin is decoded as MPS; the actual value of the bin is obtained by using this bin information and valMPS)

5. Renormalize R, read one bit and update V,

As described above, the assigner 4 assigns pState_current[bin] to each bin. The association may be performed based on the selection of the context. Those. the destination engine 4 may select a context using the context index ctxIdx, which in turn has a corresponding pState_current associated with it. A probability update can be performed each time the probability pState_current[bin] has been applied to the current bin. The probability state update pState_current[bin] is performed depending on the value of the encoded bit:

If more than one context is provided, adaptation is performed by context, i.e. pState_current[ctxIdx] is used to encode and then update using the current value of the bin (encoded or decoded respectively).

As discussed in more detail below, according to the embodiments now described, the encoder and decoder may optionally be implemented to operate in different modes, namely, a low complexity (LC) mode and a high efficiency (HE) mode. This is depicted primarily in relation to PIPE encoding in the following (mentioning then the LC and HE PIPE modes), but the description of the complexity scalability details easily transfers to other implementations of entropy encoding/decoding mechanisms, such as the embodiment of using a single general context-adaptive arithmetic encoder/ decoder

According to the embodiments summarized below, both entropy encoding modes can share

the same syntax and semantics (for a sequence of 301 and 327 syntactic elements, respectively)

same binarization schemes for all syntactic elements (currently defined for CABAC (Context-Adaptive Binary Arithmetic Coding)) (i.e. binarizers can operate regardless of the activated mode)

application of the same PIPE codes (i.e. bin encoders/decoders can operate regardless of the activated mode)

using 8-bit probabilistic model initialization values (instead of the 16-bit initialization values currently defined for CABAC)

Generally speaking, LC-PIPE differs from HE-PIPE in processing complexity, such as the complexity of selecting the PIPE path 312 for each bin.

For example, LC mode can work under the following restrictions: For each bin (binIdx) there can be exactly one probabilistic model, i.e. one ctxIdx. Those. LC PIPE cannot provide context selection/adaptation. Specific syntactic elements, such as those used to encode a remainder, may, however, be encoded using contexts, as further outlined below. In addition, all probabilistic models can be non-adaptive, i.e. all models can be initialized at the beginning of each slice with corresponding model probabilities (depending on the choice of slice type and QP (quantization parameter) of the slice) and can be kept fixed during slice processing. For example, only 8 different probabilities can be supported models corresponding to 8 different 310/322 PIPE codes for both modeling and context encoding. The specific syntactic elements for encoding the remainder, i.e. significance_coeff_flag and coeff_abs_level_greaterX (with X=1,2), the semantics of which are explained in more detail below, can be assigned to probabilistic models, such that (at least) groups of, for example, 4 syntactic elements are encoded/decoded with the same probability of the model. Compared to CAVLC (Context Adaptive Variable Length Code), LC-PIPE mode achieves roughly the same R-D performance and performance.

HE-PIPE can be implemented conceptually similar to CABAC in the H.264 standard with the following differences: Binary Arithmetic Coding (BAC) is replaced by PIPE coding (same as LC-PIPE). Each probabilistic model, i.e. each ctxIdx can be represented by pipeIdx and refineIdx, where pipeIdx with values in the range 0-7 represents the probability of a model of 8 different PIPE codes. This change only affects the internal representation of states, and not the behavior of the state machine itself (i.e., probability estimation). As discussed in more detail below, initialization of probabilistic models may use 8-bit initialization values as outlined above. The backward scan of the syntactic elements coeff_abs_level_greaterX (with X=1,2), coeff_abs_level_minus3 and coeff_sign_flag (the semantics of which will become clear from the description below) can be performed along the same scan path as the forward scan (used, for example, when encoding a saliency map). The derivation of the context for encoding coeff_abs_level_greaterX (with X=1,2) can also be simplified. Compared with CABAC, the proposed HE-PIPE achieves roughly the same R-D performance characteristics with better performance.

It is easy to see that the modes just mentioned are easily generated by rendering, for example, the aforementioned context-adaptive binary arithmetic encoding/decoding engine, since it operates in different modes.

Thus, according to an embodiment according to the first aspect of the present invention, a decoder for decoding a data stream can be configured as shown in FIG. 11. The decoder is configured to decode data stream 401, such as interleaved bitstream 340, into what media data, such as video data, is encoded. The decoder includes a mode switch 400 configured to activate a low complexity mode or a high efficiency mode depending on the data stream 401. To this end, data stream 401 may contain a syntax element, such as a binary syntax element, having a binary value of 1 in the case of a low complexity mode being the one to be activated, and having a binary value of 0 in the case of a high performance mode being the one that needs to be activated. It will be appreciated that the association between the binary value and the encoding mode may be switched, and a non-binary syntax element having more than two possible values may also be used. Since the actual choice between the two modes is not yet clear before receiving the corresponding syntax element, the syntax element may be contained in some front header of the data stream 401, encoded, for example, with a fixed probability estimate or probabilistic model, or written to the data stream 401 as is, i.e. .e. using bypass mode.

Moreover, the decoder of FIG. 11 includes a plurality of entropy decoders 322, each of which is configured to convert codewords in data stream 401 into partial symbol sequences 321. As described above, a deinterleaver 404 may be connected between the inputs of the entropy decoders 322 on the one hand and the input of the decoder of FIG. 11, where data stream 401 is supplied, on the other hand. In addition, as already described above, each of the entropy decoders 322 may be associated with a corresponding probability interval, with the probability intervals of the various entropy decoders together covering the entire probability interval from 0 to 1 - or 0 to 0.5 in the case of entropy decoders 322 dealing with MPS and LPS rather than absolute character values. Details regarding this issue have been described above. It is later assumed that the number of decoders 322 is 8, with a PIPE index assigned to each decoder, but any other number is also possible. In addition, one of these encoders, below as an example, the one that has a pipe_id equal to 0, is optimized for bins having equally likely statistics, i.e. their bin value is equal to 1 and 0. This decoder can simply skip bins. The corresponding encoder 310 operates in a similar manner. Even any bin manipulation may be excluded depending on the value of the most probable bin value valMPS by selectors 402 and 502, respectively. In other words, the entropy of the corresponding partial flow is already optimal.

In addition, the decoder in FIG. 11 includes a selector 402 configured to extract each symbol of the symbol sequence 326 from a selected one of a plurality of entropy decoders 322. As mentioned above, the selector 402 may be divided into a parameter assigner 316 and a selector 318. The desymbolizer 314 is configured to desymbolize the symbol sequence 326 to obtain a sequence of 327 syntactic elements. The restorer 404 is configured to restore the media data 405 based on the sequence of syntax elements 327. The selector 402 is configured to make a selection depending on whether one of the low complexity mode and the high efficiency mode is activated, as indicated by arrow 406.

As mentioned above, the restorer 404 may be part of a video decoder based on prediction blocks that operates with a fixed syntax and semantics of syntax elements, i.e. fixed relative to the mode selection by the mode switch 400. Those. The design of the 404 reducer does not allow mode switching. More specifically, restorer 404 does not increase implementation overhead due to the mode switching offered by mode switch 400, and at least the functionality with respect to residual data and prediction data remains the same regardless of the mode selected by switch 400. This also applies, however, with respect to entropy decoders 322. All of these decoders 322 are reused in both modes, and therefore there is no additional implementation overhead, although the decoder of FIG. 11 is compatible with both modes, low complexity and high efficiency modes.

As a further aspect, it should be noted that the decoder of FIG. 11 is not only capable of working with autonomous data streams either in one mode or in another mode. Instead, the decoder of FIG. 11 as well as the data stream 401 may be designed such that switching between both modes will even be possible during one chunk of media data, for example during a video or some chunk of audio, to, for example, control the encoding complexity on the decoding side depending on external or environmental conditions such as battery condition or the like. using a feedback channel from the decoder to the encoder to appropriately control closed-loop mode selection.

Thus, the decoder of FIG. 11 works the same in both cases, when LC mode is selected or when HE mode is selected. Restorer 404 performs recovery using syntax elements and queries the current syntax element of a given syntax element type by processing or subjecting to some syntax structure prescription. The desymbolizer 314 requests multiple bins to provide a valid binarization for the syntax element requested by the restorer 404. Obviously, in the case of a binary alphabet, the binarization performed by the desymbolizer 314 is reduced to simply passing the corresponding bin/symbol 326 to the restorer 404 as the currently requested binary syntax element.

The selector 402, however, operates regardless of the mode selected by the mode switch 400. The mode of operation of selector 402 tends to be more complex in the case of a high efficiency mode and less complex in the case of a low complexity mode. In addition, the following description shows that operating selector 402 in low complexity mode also tends to reduce the frequency with which selector 402 changes selection among entropy decoders 322 when extracting consecutive symbols from entropy decoders 322. In other words, in low complexity mode there is increased the probability that immediately subsequent symbols are extracted from the same entropy decoder from among a plurality of entropy decoders 322. This in turn allows for faster extraction of symbols from entropy decoders 322. In high efficiency mode, in turn, the selector mode of operation 402 seeks to result in a selection from among entropy decoders 322, where the probability interval associated with the corresponding selected entropy decoder 322 more closely matches the actual symbol statistics of the symbol currently extracted by selector 402, thereby obtaining a better encoder-side compression ratio when generating the corresponding data flow according to high efficiency mode.

For example, the different behavior of selector 402 in both modes could be implemented as follows. For example, the selector 402 may be configured to select, for a given symbol, from among a plurality of entropy decoders 322 depending on previously extracted symbols of the symbol sequence 326 in the case of a high efficiency mode activated, and independently of any previously extracted symbols of the symbol sequence in the case of a low complexity mode activated. . The dependence on previously extracted symbols of the symbol sequence 326 may come from context adaptivity and/or probabilistic adaptivity. Both adaptivities may be disabled during a low complexity mode in selector 402.

According to another embodiment, data stream 401 may be structured into sequential portions, such as slices, frames, groups of pictures, sequences of frames, or the like, and each symbol of the symbol sequence may be associated with a corresponding one of a variety of symbol types. In this case, the selector 402 may be configured to change, for symbols of a given character type in the current portion, to select, depending on previously extracted symbols, a sequence of symbols of a given symbol type in the current portion in the case of the high performance mode being activated, and leaving the selection constant in the current portion. in case of activated low difficulty mode. Those. selector 402 may be allowed to change the selection among entropy decoders 322 for a given symbol type, but these changes are limited to occurring between transitions between successive parts. By this measure, estimates of actual symbol statistics are limited to rare transient cases, while encoding complexity is reduced most of the time.

In addition, each character of the character sequence 326 may be associated with a corresponding one of a plurality of character types, and the selector 402 may be executed, for a given character of a given character type, to select one of a plurality of contexts depending on the previously retrieved characters of the character sequence 326 and execution selecting among entropy decoders 322 depending on the probabilistic model associated with the selected context together with updating the probabilistic model associated with the selected context depending on the given symbol in the case of the activated high performance mode, and selecting one of the plurality of contexts depending on the previously retrieved symbols sequence 326 of symbols and making a selection among entropy decoders 322 depending on the probabilistic model associated with the selected context together with leaving the probabilistic model associated with the selected context constant in the case of the low complexity mode activated. Those. selector 402 may use context adaptivity on some type of syntactic element in both modes, while suppressing probabilistic adaptation in the case of LC mode.

Alternatively, instead of completely suppressing probabilistic adaptation, selector 402 may simply reduce the update rate of the LC mode probabilistic adaptation relative to the HE mode.

Additionally, in other words, possible aspects specific to LC-PIPE, e.g. aspects of the LC mode can be described as follows. In particular, non-adaptive probabilistic models can be used in LC mode. A non-adaptive probabilistic model can either be hard-coded, i.e. full constant probability, or its probability is kept fixed only during slice processing and thus can be set depending on the slice type and QP, i.e. quantization parameter, which, for example, is signaled in data stream 401 for each slice. Assuming that successive bins assigned to the same context adhere to a fixed probabilistic model, it is possible to decode several of these bins in one step when they are encoded using the same pipe code, i.e. using the same entropy decoder, and omitting the probability update after each decoded bin. Omitting probability updates saves operations during the encoding and decoding process and thus also leads to reduced complexity and significant simplification of the hardware design.

The non-adaptive constraint can be relaxed for all or some selected probability models such that probability updates are allowed after a number of bins have been encoded/decoded using that model. The corresponding update interval allows probabilistic adaptation, while at the same time being able to simultaneously decode multiple bins.

Below is a more detailed description of possible common and scalable complexity aspects of LC-pipe and HE-pipe. In particular, aspects that can be used for LC-pipe mode and HE-pipe mode in the same manner or with scalable complexity are described below. Scalable complexity means that the LC case is derived from the HE case by removing specific parts or by replacing them with slightly less complex ones. However, before proceeding with them, it should be mentioned that the embodiment of FIG. 11 is easily transferable to the above-mentioned context-adaptive binary arithmetic encoding/decoding embodiment: selector 402 and entropy decoders 322 are concentrated into a context-adaptive binary arithmetic decoder that directly receives the stream 401 data and selects the context for the bean currently to be retrieved from the data stream. This is especially true for contextual adaptivity and/or probabilistic adaptivity. Both functionality/adaptivity can be disabled, or designed to be weakened, during low difficulty mode.

For example, when implementing the embodiment of FIG. 11, the entropy encoding pipe stage including entropy decoders 322 may use eight systematic variable-to-variable codes, i.e. each entropy decoder 322 may be of type v2v, which was described above. The PIPE coding principle, which uses systematic v2v codes, is simplified by limiting the number of v2v codes. In the case of a context-adaptive binary arithmetic decoder, it can manipulate its probabilistic states for different contexts and use it - or a quantized version of it - to subdivide the probability. Display of CABAC or probabilistic model states, i.e. states used to update the probability in PIPE id or probability indexes for lookup in Rtab may be as shown in Table A.

Table A: Mapping CABAC States to PIPE Indexes

This modified coding scheme can be used as the basis for a complexity-scalable video coding approach. When performing probabilistic mode adaptation, selector 402 or context-adaptive binary arithmetic decoder respectively selects PIPE decoder 322, i.e. output the pipe index to be used and the probability index in Rtab, respectively, based on the probability state index - here as an example, the range is from 0 to 62 - associated with the current symbol to be decoded - for example, using the context - using the mapping shown in table A, and updates this probability state index depending on the symbol currently being decoded, using, for example, specific table walk transition values indicating the next probability state index to be visited in the case of MPS and LPS, respectively. In the case of LC mode, updating the latter may be excluded. Even mapping can be eliminated in the case of globally fixed probabilistic models.

However, arbitrary entropy encoding may be used, and the methods in this document can also be used with minor adaptation.

The above description of FIG. 11 rather referred in general terms to syntactic elements and types of syntactic elements. Encoding with configurable complexity levels of transform coefficients is described below.

For example, the restorer 404 may be configured to reconstruct the transform block 200 of the transform coefficient levels 202 based on a portion of the sequence of syntax elements regardless of whether a high performance mode or a low complexity mode is activated, wherein the portion of the sequence of syntax elements 327 contains, without interleaving, syntax elements of the significance map. , defining a saliency map indicating the positions of non-zero levels of transform coefficients in transform block 200, and then (followed by) defining level syntactic elements defining non-zero levels of transform coefficients. In particular, the following elements may be included: final position syntax elements (last_significant_pos_x, last_significant_pos_y) indicating the position of the last non-zero level of transform coefficients in the transform block; first syntactic elements (coeff_significant_flag) defining together a significance map and indicating, for each position along a one-dimensional path (274) leading from the DC position to the position of the last non-zero level of transform coefficients in the transform block (200), regarding whether whether the level of the transformation coefficients at the corresponding position is non-zero or not; second syntax elements (coeff_abs_greater1) indicating, for each position of the one-dimensional path (274), where, according to the first binary syntax elements, a non-zero level of transform coefficients is located, regarding whether the level of transform coefficients at the corresponding position is greater than one; and third syntax elements (coeff_abs_greater2, coeff_abs_minus3) indicating, for each position of the one-dimensional path where, according to the first binary syntax elements, a level of transform coefficients greater than one is located, the amount by which the corresponding level of transform coefficients at the corresponding position exceeds one.

The order among the final position syntax elements, the first, second and third syntax elements may be the same for the high efficiency mode and the low complexity mode, and the selector 402 may be configured to select from among the entropy decoders 322 for the symbols from which the desymbolizer 314 obtains the syntax final position elements, first syntactic elements, second syntactic elements, and/or third syntactic elements, varying depending on whether the low complexity mode or the high efficiency mode is activated.

In particular, selector 402 may be configured for characters of a given character type from among the sequence of characters from which desymbolizer 314 obtains first syntax elements and second syntax elements, with the ability to select, for each character of a given character type, one of a plurality of contexts depending on previously extracted symbols of a given character type from among a sequence of symbols and making a selection depending on the probabilistic model associated with the selected context in the case of the high performance mode activated, and making the selection in a piecewise constant manner such that the selection is constant across successive contiguous subparts of the sequence in the case of the activated mode low complexity. As described above, subparts may be measured by the number of positions over which the corresponding subpart extends when measured along a one-dimensional path 274, or by the number of syntactic elements of the corresponding type already encoded with the current context. Those. the binary syntax elements coeff_significant_flag, coeff_abs_greater1 and coeff_abs_greater2, for example, are context adaptively encoded with decoder selection 322 based on a probabilistic model of the selected context in HE mode. Probabilistic adaptation is also used. In LC mode there are also different contexts that are used for each of the binary syntax elements coeff_significant_flag, coeff_abs_greater1 and coeff_abs_greater2. However, for each of these syntactic elements, the context is kept static for the first part along path 274, with the context changing only when moving to the next immediately subsequent part along path 274. For example, each part may be defined by a length equal to 4, 8, 16 positions of block 200, independently on whether or not the corresponding syntactic element is present for the corresponding position. For example, coeff_abs_greater1 and coeff_abs_greater2 are simply present for significant positions, i.e. positions where - or for which - coeff_significant_flag is equal to 1. Alternatively, each part may be defined by a length equal to 4, 8, 16 syntax elements, regardless of whether the corresponding part thus resulting extends over more block positions. For example, coeff_abs_greater1 and coeff_abs_greater2 are simply present for significant positions, and thus parts of each of the four syntax elements may pass over more than 4 block positions due to positions between them along path 274 for which no such syntax element such as coeff_abs_greater1 is passed , nor coeff_abs_greater2, since the corresponding level at this position is zero.

Selector 402 may be configured for characters of a given character type in a sequence of characters from which the desymbolizer obtains first syntax elements and second syntax elements, with the ability to select, for each character of a given character type, one of a plurality of contexts depending on the number of previously extracted symbols of a given character type. in a sequence of characters that have a given character value and belongs to the same subpart, or the number of previously extracted characters of a given character type in a sequence of characters that belong to the same subpart. The first alternative was true for coeff_abs_greater1, and the second alternative was true for coeff_abs_greater2 in accordance with the above-mentioned specific embodiments.

In addition, third syntactic elements indicating, for each position of the one-dimensional path where, according to the first binary syntactic elements, a level of transform coefficients greater than one is located, the amount by which the corresponding level of transform coefficients at the corresponding position exceeds one, may contain integer syntactic elements, those. coeff_abs_minus3, and the desymbolizer 314 may be configured to use a mapping function controlled by a control parameter to map the definition domain of the symbol sequence words to the value domain of the integer syntax elements, and set the control parameter to the integer syntax element depending on the integer syntax elements of the previous third syntax elements, if the high efficiency mode is activated, and performing the establishment in a piecewise constant manner such that the establishment is constant across successive contiguous subparts of the sequence in the case of the low complexity mode activated, wherein the selector 402 may be configured to select a given one of the entropy decoders (322) for the symbols words are a sequence of symbols mapped to integer syntactic elements that is associated with an equally likely distribution in both the high efficiency and low complexity modes. Those. even though the desymbolizer may operate depending on the mode selected by switch 400, as depicted by dotted line 407. Instead of setting the control parameter piecewise constant, the desymbolizer 314 may keep the control parameter constant during the current slice, for example, or constant globally over time.

Modeling context with scalable complexity is described below.

Evaluating the same top and left neighbor syntactic element to infer the context model index is a common approach and is often used in the case of HE, for example, for the motion vector differences syntactic element. However, this evaluation requires more buffer storage and does not allow direct encoding of the syntactic element. Also, more accessible neighbors can be evaluated to achieve better coding performance.

In a preferred embodiment, all context modeling stage evaluation syntactic elements of adjacent square or rectangular blocks or prediction units are fixed to one context model. This is equivalent to prohibiting adaptability at the stage of choosing a context model. For this preferred embodiment, the selection of the context model depending on the bin index of the bin string after binarization is not modified compared to the current design for CABAC. In another preferred embodiment, in addition to the fixed context model for syntactic elements, neighbor estimation is applied, and the context model for another bin index is also fixed. Note that the description does not include binarization and context model selection for motion vector differences and syntactic elements related to encoding transform coefficient levels.

In the preferred embodiment, only the left neighbor is allowed to be evaluated. This results in a reduced buffer in the processing chain, since the last block or line of encoding units no longer has to be stored. In another preferred embodiment, only neighbors lying in the same coding unit are evaluated.

In a preferred embodiment, all available neighbors are evaluated. For example, in addition to the top and left neighbor, the top left, top right, and bottom left neighbors are evaluated if available.

Those. selector 402 of FIG. 11 may be configured to use, for a given symbol related to a given media block, previously extracted symbols of a sequence of symbols related to a larger number of different adjacent media blocks in the case of a high efficiency mode activated, to select one of a plurality of contexts and select between entropy decoders 322 depending on the probabilistic model associated with the selected context. Those. adjacent blocks may be neighbors in the temporal and/or spatial domain. Spatially adjacent blocks are visible, for example in FIG. 1-3. Then selector 402 can respond to mode selection by mode switch 400 and perform pin adaptation based on previously retrieved symbols or syntax elements related to more adjacent blocks in the case of HE mode compared to LC mode, thereby reducing storage overhead as just described .

The following describes the reduced complexity coding of motion vector differences according to an embodiment.

In the H.264/AVC video codec standard, the motion vector associated with a macroblock is transmitted by signaling a difference (motion vector difference - mvd) between the motion vector of the current macroblock and the average motion vector predictor. When CABAC is used as an entropy encoder, mvd is encoded as follows. The integer mvd is divided into an absolute and a signed part. The absolute part is binarized using a combination of truncated unary code and 3rd order exponential Golomb code, referred to as the prefix and suffix of the resulting string of bins. Bins related to truncated unary binarization are encoded using context models, while bins related to exponential Golomb binarization are encoded using traversal mode, i.e. with a fixed probability of 0.5 s CABAC. Unary binarization works as follows. Let the absolute integer value of mvd be n , then the resulting string of bins consists of n "1s" and one trailing "0". As an example, let n=4, then the bin string is "11110". In the case of a truncated unary, there is a limit, and if the value exceeds this limit, the string of bins consists of n+1 "1s". For the mvd case, the limit is 9. This means that if an absolute mvd equal to or greater than 9 is encoded, resulting in 9 "1", the bin string consists of a prefix and a suffix with Golomb exponential binarization. Contextual modeling for the truncated unary part is performed as follows. For the first bin of a row of bins, the absolute mvd values from the top and left adjacent macroblocks are taken, if available (if not available, the value is assumed to be 0). If the sum for a particular component (horizontal or vertical direction) is greater than 2, the second context model is selected, if the absolute sum is greater than 32, the third context model is selected, otherwise (absolute sum less than 3) the first context model is selected. In addition, the context models are different for each component. The fourth context model is used for the second bin of the bin string, and the fifth context model is used for the remaining bins of the unary part. When the absolute mvd is equal to or greater than 9, for example, all bins of the truncated unary part are "1", the difference between the absolute value of mvd and 9 is traversed using 3rd order Golomb exponential binarization. At the last stage, the mvd character is encoded in bypass mode.

The most recent encoding method for mvd using CABAC as the entropy encoder is specified in the current benchmark model (HM) of the High Efficiency Video Coding (HEVC) project. In HEVC, block sizes are variable and the shape given by the motion vector is referred to as prediction unit (PU). The size of the top and left neighbor PU may have different shapes and sizes than the current PU. Therefore, where appropriate, the definition of the top-left neighbor is now referred to as the top-left neighbor of the top-left corner of the current PU. For the encoding itself, the derivation process for the first bin may vary according to an embodiment. Instead of estimating the absolute sum of MVs from neighbors, each neighbor can be estimated separately. If the neighbor's absolute MV is available and is greater than 16, the context model index can be increased, resulting in the same number of context models for the first bin, while the remaining absolute MVD and sign level encodings are exactly the same as in H.264/AVC .

In the mvd encoding method briefly described above, up to 9 bins must be encoded with the context model, while the rest of the mvd value can be encoded in a low complexity bypass mode along with the sign information. This present embodiment describes a method for reducing the number of bins encoded with context models, resulting in an increased number of traversals, and reduces the number of context models required for mvd encoding. To do this, the cutoff value is reduced from 9 to 1 or 2. This means that only the first bin specifying whether the absolute mvd is greater than zero is encoded using the context model, or the first and second bins specifying whether the absolute mvd is greater than zero and ones are encoded using the context model, while the remaining value is encoded in bypass mode and/or using VLC code (variable length code). All bins resulting from binarization using VLC code - not using unary or truncated unary - are encoded using low complexity traversal mode. With PIPE, direct insertion into and out of a bitstream is possible. Additionally, if present, a different definition of top and left neighbor can be used to infer the best choice of context model for the first bin.

In the preferred embodiment, exponential Golomb codes are used to binarize the remainder of the absolute components of the MVD. For this purpose, the order of the exponential Golomb code is variable. The order of the exponential Golomb code is derived as follows. Once the context model for the first bin has been inferred and encoded, and therefore the index of that context model, the index is used as the order for the Golomb exponential binarization portion. In this preferred embodiment, the context model for the first bin is in the range 1-3, resulting in an index of 0-2, which are used as the order of the exponential Golomb code. This preferred embodiment can be used for the case of HE.

An alternative to the briefly described above method of using two times five contexts when encoding an absolute MVD to encode 9 binarization bins with a unary code, 14 context models (7 for each component) can also be used. For example, while the first and second bins of the unary part may be encoded using four different contexts as described earlier, the fifth context may be used for the third bin, and the sixth context may be used with respect to the fourth bin, while the fifth through ninth bins are encoded with using the seventh context. Thus, in this case, even 14 contexts will be required, and simply the remaining value can be encoded in low complexity bypass mode. A method to reduce the number of bins encoded using context models, resulting in an increased number of traversals and a reduction in the number of context models required for MVD encoding, is to reduce the cutoff value, for example from 9 to 1 or 2. This means that only the first bin specifying whether the absolute MVD is greater than zero will be encoded using the context model, or the first and second bins specifying whether the absolute MVD is greater than zero and one will be encoded using the corresponding context model, while the remaining value is encoded using VLC code . All bins resulting from binarization using VLC code are encoded using low complexity traversal mode. In the case of PIPE, direct insertion into and out of a bitstream is possible. In addition, the presented embodiment uses a different definition of top and left neighbor to infer the selection of the best context model for the first bin. In addition to this, the context modeling is modified such that the number of context models required for the first or first and second bins is reduced, resulting in a further reduction in memory footprint. Also, evaluation of neighbors such as the above neighbor may be inhibited, resulting in saving the amount of memory/row buffer required to store the neighbors' mvd values. Finally, the encoding order of the constituents can be split in a manner that allows prefix bin encoding for both constituents (i.e., context model-encoded bins) followed by traversal bin encoding.

In the preferred embodiment, exponential Golomb codes are used to binarize the remainder of the absolute components of mvd. For this purpose, the order of the exponential Golomb code is variable. The order of the exponential Golomb code can be derived as follows. Once the context model for the first bin is obtained, and therefore the index of that context model, the index is used as the order for the Golomb exponential binarization. In this preferred embodiment, the context model for the first bin is in the range 1-3, resulting in an index of 0-2, which is used as the order of the exponential Golomb code. This preferred embodiment can be used for the HE case and the number of context models is reduced to 6. To further reduce the number of context models and therefore save memory, the horizontal and vertical components can share the same context models in another preferred embodiment. In this case, only 3 context models are required. Moreover, only the left neighbor may be considered for evaluation in another preferred embodiment of the invention. In this preferred embodiment, the threshold may not be modified (eg, only a single threshold 16, resulting in an exponential Golomb code parameter of 0 or 1, or a single threshold 32, resulting in an exponential Golomb code parameter of 0 or 2). This preferred embodiment saves the row buffer required to store the mvd. In another preferred embodiment, the threshold is modified to be 2 and 16. This preferred embodiment requires a total of 3 context models to encode the mvd, and the possible exponential Golomb code parameter is in the range of 0-2. In another preferred embodiment, the threshold is 16 and 32. Again, the described embodiment is suitable for the HE case.

In another preferred embodiment of the invention, the cutoff value is reduced from 9 to 2. In this preferred embodiment, the first bin and the second bin may be encoded using context models. The selection of the context model for the first bin can be performed as is in the state of the art or in a modified form in the manner described in the preferred embodiment above. For the second bin, a separate context model is selected as in the current state of the art. In another preferred embodiment, the context model for the second bin is selected by estimating the mvd of the left neighbor. For this case, the context model index is the same as for the first bin, while the available context models are different than for the first bin. In total, 6 context models are required (note that the components share context models). Again, the exponential Golomb code parameter may depend on the index of the selected context model of the first bin. In another preferred embodiment of the invention, the exponential Golomb code parameter depends on the context model index of the second bin. The described embodiments of the invention can be used for the case of HE.

In another preferred embodiment of the invention, the context models for both bins are fixed and are not inferred by estimating either the left or top neighbors. For this preferred embodiment, the total number of context models is 2. In another preferred embodiment of the invention, the first bin and the second bin share the same context model. As a result, only one context model is required to encode mvd. In both preferred embodiments of the invention, the exponential Golomb code parameter may be fixed to 1. The described preferred embodiment is suitable for both HE and LC configurations.

In another preferred embodiment, the order of the exponential part of the Golomb code is derived independently from the context model index of the first bin. In this case, the absolute sum of the conventional H.264/AVC context model selection is used to derive the order for the exponential part of the Golomb code. This preferred embodiment can be used for the case of HE.

In another preferred embodiment, the order of exponential Golomb codes is fixed and is set to 0. In another preferred embodiment, the order of exponential Golomb codes is fixed and is set to 1. In a preferred embodiment, the order of exponential Golomb codes is fixed to 2. In another embodiment, the order of exponential Golomb codes are fixed to 3. In another embodiment, the order of exponential Golomb codes is fixed according to the shape and size of the current PU. The preferred embodiments presented may be used for the LC case. Note that the fixed order portion of the exponential Golomb code is considered with a reduced number of bins encoded with context models.

In a preferred embodiment, neighbors are defined as follows. For the above PU, all PUs that cover the current PU are taken into account and the PU with the largest MV is used. This also applies to the left neighbor. All PUs that cover the current PU are evaluated and the PU with the highest MV is used. In another preferred embodiment, the average absolute value of the motion vector from all PUs that cover the top and left border of the current PU is used to derive the first bin.

For the above preferred embodiments, it is possible to change the encoding order as follows. mvd must be set for horizontal and vertical direction one after the other (or vice versa). Thus, two strings of beans must be encoded. To minimize the number of mode switches for the entropy encoding mechanism (i.e., switching between bypass mode and normal mode), it is possible to encode bins encoded with context models for both components in the first stage, followed by bins encoded in bypass mode in the second stage. Note that this represents only a reordering.

It should be noted that bins resulting from a unary or truncated unary binarization can also be represented by an equivalent fixed-length binarization of one flag per bin index specifying whether the value is greater than the index of the current bin. As an example, the cutoff value for the truncated unary binarization mvd is set to 2, resulting in codewords 0, 10, 11 for values 0, 1, 2. For a corresponding fixed-length binarization with one flag per bin index, one flag for bin index 0 (i.e. the first bin) specifies whether the absolute value of mvd is greater than 0 or not, and one flag for the second bin with bin index 1 specifies whether the absolute value of mvd is greater than 1 or not. When the second flag is only encoded when the first flag is 1, it results in the same codewords 0, 10, 11.

The following describes a scalable complexity representation of the internal state of probabilistic models according to an embodiment.

When setting HE-PIPE, the internal state of the probabilistic model is updated after encoding a bin with it. The updated state is inferred through a state transition table lookup using the old state and the value of the encoded bin. In the case of CABAC, the probabilistic model can assume 63 different states, where each state corresponds to a model probability in the interval (0.0, 0.5). Each of these states is used to implement two model probabilities. In addition to the probability assigned to the state, 1.0 minus probability is also used, and a flag called valMps stores information whether probability or 1.0 minus probability is used. This results in a total of 126 states. To use such a probabilistic model with the PIPE encoding principle, each of the 126 states must be mapped to one of the available PIPE encoders. Current implementations of PIPE encoders accomplish this by using a lookup table. An example of such a mapping is described in Table A.

The following describes an embodiment of how the internal state of a probabilistic model can be represented to eliminate the use of a lookup table to transform the internal state into a PIPE index. All that is needed is some simple bit masking operations to extract the PIPE index from the internal state variable of the probabilistic model. This new representation with scalable internal state complexity of the probabilistic model is developed in a two-level manner. For applications where low complexity operation is mandatory, only the first level is used. It describes only the pipe index and the valMps flag, which is used to encode or decode associated bins. In the case of the described PIPE entropy encoding scheme, the first layer can be used to distinguish between 8 different model probabilities. Thus, the first layer will need 3 bits for pipeIdx, and one additional bit for the valMps flag. With the second level, each of the first level's crude probability ranges is refined into slightly smaller intervals that support the representation of probabilities at higher resolutions. This more detailed view allows for more accurate performance of probability estimators. In general, it is suitable for coding applications that strive for high RD performance. As an example, this scalable internal state complexity representation of probabilistic models using PIPE is depicted as follows:

The first and second levels are stored in a single 8-bit memory. 4 bits are required to store the first level - the index that defines the PIPE index with the MPS value on the most significant bit - and the other 4 bits are used to store the second level. To implement the CABAC probability estimator behavior, each PIPE index has a specific number of refinement indexes allowed depending on how many CABAC states have been mapped to the PIPE index. For example, to display in table A, the number of CABAC states per PIPE index is depicted in table B.

Table B: Number of CABAC states per PIPE index for example table A.

During the encoding or decoding process of a bin, the PIPE index and valMps can be accessed directly through the use of a simple bit mask or bit shift operations. Low complexity encoding processes require 4 bits of the first level, and high efficiency encoding processes can additionally use 4 bits of the second level to perform an update of the probabilistic model of the CABAC probability estimator. To perform this update, a state transition lookup table can be designed that makes the same state transitions as the original table, but using a two-level representation with scalable state complexity. The original state transition table consists of two elements multiplied by 63. For each input state, it contains two output states. When using a scalable complexity representation, the size of the state transition table does not exceed 2 times 128 elements, which is an acceptable increase in table size. This increase depends on how many bits are used to represent the refinement index and accurately simulate the behavior of the CABAC probability estimator, four bits are needed. However, other probability estimators can be used that can operate on a reduced set of CABAC states such that no more than 8 states are allowed for each pipe index. Therefore, memory consumption can be matched to a given level of complexity of the encoding process by adapting the number of bits used to represent the refinement index. Compared to the internal state of model probabilities with CABAC - where there are 64 probability state indices - the use of table lookups to map model probabilities to a specific PIPE code is eliminated, and no additional transformation is required.

The following describes updating the context model with scalable complexity according to an embodiment.

To update the context model, its probability state index may be updated based on one or more previously encoded bins. In a HE-PIPE setup, this update is performed after each bin is encoded or decoded. Conversely, in an LC-PIPE installation, this update may never be performed.

However, it is possible to update context models with scalable complexity. Those. The decision whether to update the context model or not can be based on various aspects. For example, an encoder installation may not perform updates only for specific context models, like, for example, the context models of the coeff_significant_flag syntax element, and always perform updates for all other context models.

In other words, the selector 402 may be configured for symbols of each of several given symbol types, with the ability to select among the entropy decoders 322 depending on the corresponding probability model associated with the corresponding given symbol, such that the number of given symbol types is less in the low complexity mode compared to high efficiency mode.

In addition, the criteria for controlling whether to update the context model or not may be, for example, the size of the bitstream packet, the number of bins decoded so far, or the update is performed only after encoding a specific fixed or variable number of bins for the context model.

With this scheme for deciding whether to update context models or not, context model updating with scalable complexity can be realized. This allows you to increase or decrease the proportion of bins in the bitstream for which context model updates are performed. The higher the number of context model updates, the better the coding efficiency and the higher the computational complexity. Thus, context model updating with scalable complexity can be achieved with the described scheme.

In the preferred embodiment, the context model update is performed on the bins of all syntax elements except the syntax elements coeff_significant_flag, coeff_abs_greater1 and coeff_abs_greater2.

In another preferred embodiment, the context model update is performed only on the coeff_significant_flag, coeff_abs_greater1, and coeff_abs_greater2 syntax element bins.

In another preferred embodiment, a context model update is performed for all context models when encoding or decoding of a slice begins. Once a specific specified number of transformation blocks have been processed, updating the context model is disabled for all context models until the end of the slice is reached.

For example, selector 402 may be configured, for symbols of a given symbol type, to select from among entropy decoders 322 depending on the probabilistic model associated with the given symbol type, with or without updating the associated probabilistic model, such that the duration of the training phase of the symbol sequence , which selects symbols of a given symbol type along with updating, is shorter in low complexity mode compared to high efficiency mode.

Another preferred embodiment is identical to the previously described preferred embodiment, but it uses a complexity-scalable representation of the internal state of context models such that one table stores the "first part" (valMps and pipeIdx) of all context models, and a second table stores the "second part" (refineIdx) of all context models. Then, when updating the context model is disabled for all context models (as described in the previous preferred embodiment), the table storing the "second part" is no longer required and can be discarded.

The following describes updating the context model for a sequence of bins according to an embodiment.

In the LC-PIPE configuration, bins of syntax elements of type coeff_significant_flag, coeff_abs_greater1 and coeff_abs_greater2 are grouped into subsets. For each subset, a single context model is used to encode its bins. In this case, updating the context model can be performed after encoding a fixed number of bins of a given sequence. This is denoted by a multi-bin update in the following. However, this update may be different from an update that uses only the last encoded bin and the internal state of the context model. For example, for each bin that has been encoded, one context model update step is performed.

Below are examples for encoding an example subset of 8 bins. The letter “b” denotes bin decoding, and the letter “u” denotes updating the context model. In the case of LC-PIPE, only bin decoding is performed without performing updates to the context model:

b b b b b b b b

In the case of HE-PIPE, after decoding each bin, the context model is updated:

b u b u b u b u b u b u b u b u

To reduce complexity to some extent, an update to the context model can be performed after a sequence of beans (in this example, after every 4 beans, updates to those 4 beans are performed):

b b b b u u u u b b b b u u u u

Those. selector 402 may be configured, for symbols of a given symbol type, to select from among entropy decoders 322 depending on the probabilistic model associated with the given symbol type, with or without updating the associated probabilistic model, such that the frequency with which symbol selection is performed of a given character type along with updating is less in low difficulty mode compared to high efficiency mode.

In this case, after decoding the 4 bins, there are 4 update steps based on the 4 bins just decoded. Note that these four update steps can be performed in one single step by using a special lookup table for the lookup. This lookup table stores, for every possible combination of 4 bins and every possible internal state of the context model, the resulting new state after the normal four update steps.

In some mode, multi-bin update is used for the coeff_significant_flag syntax element. All other syntax element beans do not use context model updating. The number of bins that are encoded before the multi-bin update step is set to n. When the number of bins in a set is not a multiple of n, 1-n-1 bins remain at the end of the subset after the last multibin update. For each of these bins, a normal single-bin update is performed after encoding all of these bins. The number n can be any positive number greater than 1. Another mode can be identical to the previous mode except that a multi-bin update is performed for arbitrary combinations of coeff_significant_flag, coeff_abs_greater1 and coeff_abs_greater2 (only instead of coeff_significant_flag). So this mode will be more challenging than the other. All other syntax elements (where multi-bin update is not used) can be divided into two disjoint subsets, where one of the subsets uses single-bin update and the other subset does not use context model update. Any possible disjoint subsets are valid (including the empty subset).

In an alternative embodiment, the multi-bin update may be based only on the last m bins that are encoded immediately before the multi-bin update step. m can represent any natural number less than n. So decoding can be done like the following:

b b b b u u b b b b u u b b b b u u b b b b …

with n=4 and m=2.

Those. selector 402 may be configured, for symbols of a given symbol type, to select from among entropy decoders 322 depending on the probability model associated with the given symbol type, together with updating the associated probability model of each nth symbol of the given type based on m the most recent symbols of a given symbol type, so that the n/m ratio is higher in the low-complexity mode compared to the high-performance mode.

In another preferred embodiment, a context modeling scheme may be used for the coeff_significant_flag syntax element using a local template, as described above for the HE-PIPE configuration, to assign context models to the syntax element's bins. However, these beans do not use context model updating.

In addition, the selector 402 may be configured, for symbols of a given symbol type, to select one of several contexts depending on the number of previously extracted symbols of the symbol sequence and select from among entropy decoders 322 depending on the probabilistic model associated with the selected context. so the number of contexts, and/or the number of previously retrieved symbols, is smaller in the low complexity mode compared to the high efficiency mode.

Probabilistic model initialization using 8-bit initialization values

This section describes the process of initializing internal state with scalable complexity of probabilistic models, using a so-called 8-bit initialization value instead of two 8-bit values, as is the case with the current H.264/AVC video encoding standard. It consists of two parts, which are comparable to the initialization value pairs used for probabilistic models in CABAC in H.264/AVC. The two parts represent the two parameters of a linear equation for calculating the initial state of a probabilistic model representing a specific probability (e.g. as a PIPE index) from the QP:

The first part describes the slope, and it uses the internal state relationship with respect to the quantization parameter (QP) that is used during encoding or decoding.

The second part describes the PIPE index at a given QP, as well as valMps.

Two different modes are available for initializing a probabilistic model using a given initialization value. The first mode is designated as QP-independent initialization. It only uses the PIPE index and valMps defined in the second part of the initialization value for all QPs. This is identical to the case when the slope is 0. The second mode is denoted as QP-dependent initialization, and it additionally uses the slope of the first part of the initialization value to change the PIPE index and determine the refinement index. The two parts of the 8-bit initialization value are depicted as follows:

It consists of two 4-bit parts. The first part contains an index that points to 1 of the 16 different specified slopes that are stored in the array. The specified slopes consist of 7 negative slopes (slope index 0-6), one slope that is zero (slope index 7), and 8 positive slopes (slope index 8-15). The slopes are shown in Table C.

Table C

All values are scaled by a factor of 256 to avoid the use of floating point operations. The second part is the PIPE index, which depicts the upward probability valMps=1 between the probability interval p=0 and p=1. In other words, the n PIPE encoder must operate at a higher model probability than the n-1 PIPE encoder. There is one PIPE probability index available for each probabilistic model, and it identifies a PIPE encoder whose probability interval contains the probability p _valMPs=1 for QP=26.

Table D: Mapping of the second part of the initialization value to the PIPE and valMps encoders: UR - unary-to-Rice code; TB - three-bin code, BP - bin-pipe code, EP - equal probability (not coded)

A QP and an 8-bit initialization value are required to compute the initialization of the internal state of the probabilistic models by computing a simple linear equation of the form y=m*(QP-QPref)+256*b. Note that m specifies the slope, which is taken from table C by using the slope index (the first part of the 8-bit initialization value), and b denotes the PIPE encoder at QPref=26 (the second part of the 8-bit initialization value: "PIPE Probability Index") . Then valMPS is 1 and pipeIdx is (y-2048)>>8 if y is greater than 2047. Otherwise, valMPS is 0 and pipeIdx is (2047-y)>>8. The refinement index is (((y-2048)&255)*numStates)>>8 if valMPS is 1. Otherwise, the refinement index is (((2047-y)&255)*numStates)>>8. In both cases, numStates is equal to the number of CABAC states in pipeIdx, as depicted in Table B.

The above circuit can not only be used in combination with PIPE encoders, but also in connection with the above CABAC circuits. In the absence of PIPE, the number of CABAC states, i.e. probabilistic states between which a state transition is performed when updating the probability (pState_current[bin]) on PIPE Idx (i.e. the corresponding most significant bits of pState_current[bin]) then represent only a set of parameters that implement, in fact, piecewise linear interpolation CABAC states depending on QP. Additionally, this piecewise linear interpolation can also be virtually disabled in the case where the numStates parameter uses the same value for all PIPE Idx. For example, setting numStates to 8 for all cases results in a total of 16*8 states, and the refinement index calculation simplifies to ((y-2048)&255)>>5 for valMPS equal to 1 or ((2047-y)&255)>>5 for valMPS equal to 0. For this case, it is very simple to map the representation using valMPS, PIPE Idx and idx refiners back to the representation used by the original CABAC in H.264/AVC. The CABAC state is defined as (PIPE Idx<<3)+Idx refinement. This aspect is further described below in relation to FIG. 16.

If the slope of the 8-bit initialization value is not zero, or if the QP is not equal to 26, then it is necessary to calculate the internal state by applying a linear equation with the QP of the encoding or decoding process. In the case of a slope equal to zero, or that the QP of the current encoding process is equal to 26, the second part of the 8-bit initialization value can be used directly to initialize the internal state of the probabilistic model. Otherwise, the decimal part of the resulting internal state can be further used to determine the refinement index in high performance coding applications by linear interpolation between the limits of a particular PIPE encoder. In this preferred embodiment, linear interpolation is performed by simply multiplying the decimal part by the total number of refinement indices available for the current PIPE encoder and mapping the result to the nearest integer refinement index.

The internal state initialization process of probabilistic models can vary with respect to the number of PIPE probability index states. In particular, the double presence of the equiprobable mode using the E1 PIPE encoder, i.e. using two different PIPE indices to differentiate between an MPS of 1 or 0 can be avoided as follows. Again, a process may be called at the time parsing of the slice data begins, and the input to this process may be an 8-bit initialization value, as shown in Table E, which, for example, is passed in the bitstream for each context model to be initialized.

Table E: Setting 8 initValue bits for the probabilistic model

The first 4 bits define the slope index and are extracted by masking bits b4-b7. For each slope index, slope(m) is specified and displayed in table F.

Table F: Variable m values for slopeIdx

Bits b0-b3, the last 4 bits of the 8-bit initialization value, identify probIdx and describe the probability given the QP. probIdx 0 indicates the highest probability for symbols with a value of 0 and, correspondingly, probIdx 14 indicates the highest probability for symbols with a value of 1. Table G depicts for each probIdx the corresponding pipeCoder and its valMps.

Table G: Mapping of the last 4-bit part of the initialization value to PIPE and valMps encoders: UR - unary-to-Rice code, TB - three-bin code, BP - bin-pipe code, EP - equiprobability (not encoded)

With both values, calculation of the internal state can be performed by using a linear equation like y=m*x+256*b, where m denotes the slope, x denotes the QP of the current slice, and b is derived from probIdx, as shown in the following description. All values in this process are scaled by a factor of 256 to avoid the use of floating point operations. The output (y) of this process represents the internal state of the probabilistic model at the current QP and is stored in an 8-bit memory. As shown in G, the internal state consists of valMPs, pipeIdx and refineIdx.

Table H: Setting the internal state of the probabilistic model

The purpose of refineIdx and pipeIdx is similar to the internal state of probabilistic CABAC models (pStateCtx) and is presented in H.

Table I: Purpose of pipeIdx, refineIdx and pStateCtx

In a preferred embodiment, probIdx is determined at QP26. Based on the 8-bit initialization value, the internal state (valMps, pipeIdx and refineIdx) of the probabilistic model is processed as described in the following pseudocode:

As shown in the pseudocode, refineIdx is calculated by linear interpolation between the pipeIdx interval and quantizing the result into the corresponding refineIdx. The offset specifies the total number of refineIdx for each pipeIdx. The interval [7, 8) fullCtxState/256 is divided in half. The interval [7, 7,5) is mapped to pipeIdx=0 and valMps=0, and the interval [7,5, 8) is mapped to pipeIdx=0 and valMps=1. Fig. 16 depicts the internal state derivation process and shows the mapping of fullCtxState/256 to pStateCtx.

Note that the slope indicates the relationship between probIdx and QP. If slopeIdx of the 8-bit initialization value is 7, the resulting internal state of the probabilistic model is the same for all slice QPs - hence the internal state initialization process is independent of the current slice QP.

That is, selector 402 may initialize pipe indices to be used when decoding the next portion of the data stream, such as the full stream or the next slice, using a syntax element indicating the quantization step size QP used to quantize that portion's data, such as coefficient levels transforms the contents contained therein, using the given syntax element as an index, into a table that may be common to both modes, LC and HE. A table, such as table D, may contain pipe indexes for each character type, for the corresponding QPref reference value, or other data for each character type. Depending on the actual QP of the current part, the selector can calculate the value of the pipe index using the corresponding table element a indexed by the actual QP or the QP itself, for example by multiplying a by (QP-QPref). The only difference in LC and HE mode: The selector calculates the result only with less accuracy in the case of LC compared to HE mode. A selector, for example, could simply use the integer part of the calculation result. HE mode uses the higher precision remainder, such as the fractional part, to select one of the available refinement indices for the corresponding pipe index, as indicated by the lower precision or integer part. The refinement index is used in HE mode (potentially less rarely also in LC mode) to perform probabilistic adaptation, for example by using the table walk mentioned above. If we leave the available indexes for the current pipe index at a higher bound, then the higher pipe index is chosen next, minimizing the refinement index. If you leave available indexes for the current pipe index at a lower bound, then the next lower pipe index is chosen next, maximizing the refinement index to the maximum available for the new pipe index. The pipe index together with the refinement index determine the probability state, but to select from among partial streams, the selector simply uses the pipe index. The refinement index simply serves to track the probability more accurately, or to achieve higher precision.

The above description also showed, however, that complexity scalability can be achieved regardless of the PIPE encoding principle of FIG. 7-10 or CABAC using the decoder shown in FIG. 12. The decoder of FIG. 12 is configured to decode a data stream 601 into which media data is encoded, and includes a mode switch 600 configured to activate a low complexity mode or a high efficiency mode depending on the data stream 601, and a desymbolizer 602 configured to the ability to desymbolize a sequence 603 of symbols obtained - either directly or through entropy decoding, for example - from a data stream 601 to obtain integer syntax elements 604, using a mapping function controlled by a control parameter to map the word definition domain of the symbol sequence to the value domain of the integer syntax elements. Restorer 605 is configured to recover media data 606 based on integer syntax elements. The desymbolizer 602 is configured to perform desymbolization such that the control parameter changes in accordance with the data flow at a first rate in the case of a high efficiency mode activated, and the control parameter is constant regardless of the data flow or varies depending on the data flow but at a second rate, which is less than the first speed, in the case of a low complexity mode activated, as indicated by arrow 607. For example, a control parameter may be changed in accordance with previously desymbolized symbols.

Some of the above embodiments used an aspect of FIG. 12. The coeff_abs_minus3 and MVD syntax elements in sequence 327, for example, were binarized in the desymbolizer 314 depending on the selected mode, as indicated by 407, and the restorer 605 used these syntax elements for reconstruction. Obviously, both aspects of FIG. 11 and 19 are easily combined, but the aspect of FIG. 12 can also be combined with other encoding environments.

See, for example, the coding of motion vector differences noted above. The desymbolizer 602 may be configured such that the mapping function uses a truncated unary code to perform a mapping in the first definition region bin of integer syntax elements below the cutoff value and a combination of a truncated unary code prefix for the cutoff value and a VLC codeword suffix in the second region bin. determining integer syntax elements, including and above cutoff values, wherein the decoder may comprise an entropy decoder 608 configured to derive a number of first truncated unary code bins from data stream 601 using variable probability entropy decoding, and a number of second VLC codeword bins, using the bypass mode with constant equiprobability. In HE mode, entropy encoding can be more complex than in LC encoding, as indicated by arrow 609. i.e. contextual adaptivity and/or probabilistic adaptation may be applied in the HE mode and suppressed in the LC mode, or complexity may be scaled in other terms, as discussed above with respect to various embodiments.

An encoder corresponding to the decoder of FIG. 11, for encoding media data into a data stream is shown in FIG. 13. It may include an inserter 500 configured to signal in the data stream 501 the activation of a low complexity mode or a high efficiency mode, a constructor 504 configured to pre-encode media data 505 into a sequence 506 of syntax elements, a symbolizer 507 configured to symbolize a sequence 506 syntax elements into a symbol sequence 508, a plurality of entropy encoders 310, each configured to convert partial symbol sequences into data stream codewords, and a selector 502 configured to route each character of the symbol sequence 508 to a selected one of the plurality of entropy encoders 310, wherein the selector 502 is configured to make a selection depending on whether one of the low complexity mode and the high efficiency mode is activated, as indicated by arrow 511. An interleaver 510 may optionally be provided to interleave codewords of the encoders 310.

An encoder corresponding to the decoder of FIG. 12, for encoding media data into a data stream is shown in FIG. 14, comprising an inserter 700 configured to signal in the data stream 701 the activation of a low complexity mode or a high efficiency mode, a constructor 704 configured to pre-encode media data 705 into a syntax element sequence 706 containing an integer syntax element, and a symbolizer 707 configured to the ability to symbolize an integer syntax element using a mapping function controlled by a control parameter to map a definition domain of the integer syntax elements to a word value domain of a sequence of symbols, wherein the symbolizer 707 is configured to perform symbolization such that the control parameter changes in accordance with a data stream at a first rate in the case of the high efficiency mode activated, and the control parameter is constant regardless of the data flow, or varies depending on the data flow, but at a second rate that is less than the first speed, in the case of the low complexity mode activated, as indicated by arrow 708. The result of the symbolization is encoded in data stream 701.

Again, it should be mentioned that the embodiment of FIG. 14 easily transfers to the above context-adaptive binary arithmetic encoding/decoding embodiment: selector 509 and entropy encoders 310 are put together into a context-adaptive binary arithmetic encoder that will output data stream 401 directly and select the context for the bin currently being output. from the data stream. This is especially true for contextual adaptivity and/or probabilistic adaptivity. Both functionality/adaptivity may be disabled, or may be designed to be weakened, during low difficulty mode.

It was briefly noted above that the mode switching capability described with respect to some of the above-mentioned embodiments may, according to alternative embodiments, be omitted. To make this clear, reference is made to FIG. 16, which summarizes the above description to the extent that only the elimination of the possibility of mode switching distinguishes the embodiment of FIG. 16 from the above embodiments. In addition, the following description shows the benefits resulting from initializing context probability estimates using less precise parameters for slope and offset compared to, for example, H.264.

In particular, FIG. 16 depicts a decoder for decoding video 405 from data stream 401 for which horizontal and vertical components of motion vector differences are encoded using binarizations of the horizontal and vertical components, the binarizations being equal to a truncated unary code of the horizontal and vertical components, respectively, in the first interval of the horizontal and vertical component definition region below the cutoff value, and the prefix combination in the form of a truncated unary code. The cutoff value and suffix in the form of an exponential Golomb code of the horizontal and vertical components, respectively, in the second interval of the definition domain of the horizontal and vertical components, inclusive and above the cutoff value, wherein the cutoff value is 2, and the exponential Golomb code is of order 1. The decoder includes an entropy decoder 409 configured , for the horizontal and vertical components of the motion vector differences, with the ability to derive a truncated unary code from the data stream using context-adaptive binary entropy decoding with exactly one context per bin position of the truncated unary code, which is common to the horizontal and vertical components of the motion vector differences , and the exponential Golomb code, using the constant equiprobability traversal mode to obtain binarizations of the motion vector differences. More specifically, as described above, entropy decoder 409 may be configured to derive the number of bins 326 of binarizations from data stream 401 using binary entropy decoding, such as the aforementioned CABAC scheme, or binary PIPE decoding, i.e. using a design that includes multiple entropy decoders 322 running in parallel along with a corresponding selector/assigner. The desymbolizer 314 debinarizes the binarizations of the motion vector difference syntax elements to produce integer values of the horizontal and vertical components of the motion vector differences, and the reconstructor 404 reconstructs the video based on the integer values of the horizontal and vertical components of the motion vector differences.

To explain this in more detail, reference is briefly made to FIG. 18. Position 800 represents one motion vector difference, i.e. a vector representing the prediction remainder between the predicted motion vector and the actual/recovered motion vector. The horizontal and vertical components of 802x and 802y are also shown. They can be transmitted in units of pixel positions, i.e. pixel pitch, or sub-pixel positions such as half a pixel pitch or a quarter pixel pitch or the like. The horizontal and vertical components of 802 _x,y are integers. Their area extends from zero to infinity. The meaning of the sign can be processed separately and is not discussed further here. In other words, the description summarized herein focuses on the magnitude of the motion vector differences 802x,y. The definition area is depicted at 804. On the right side of the definition area axis 804 of FIG. 19 depicts, associated with positive component values 802x,y vertically stacked on top of each other, the binarization into which the corresponding possible value is mapped (binarized). As can be seen, below the cutoff value of 2, only the truncated unary code 806 occurs, while the binarizations have, as a suffix, also an exponential Golomb code of order 808 from possible values equal to or greater than the cutoff value 2, in order to continue binarization for the remainder integer value above the cutoff value minus 1. For all bins, only two contexts are provided: one for the position of the first bin of the horizontal and vertical component binarizations 802x,y, and one for the position of the second bin of the truncated unary code 806 of both the horizontal and vertical components 802x, y. For the bin position of the exponential Golomb code 808, the equiprobability bypass mode is used by the entropy decoder 409. That is, both bin values are assumed to occur equally likely. The probability estimate for these bins is fixed. In comparison, the probability estimate associated with the just mentioned two bin contexts of the truncated unary code 806 is adapted continuously during decoding.

Before describing in more detail how the entropy decoder 409 may be implemented in accordance with the above description to perform the tasks just mentioned, the description now focuses on a possible implementation of a restorer 404 that uses motion vector differences 800 and its integer values. obtained by desymbolizer 314 by rebinarizing code bins 106 and 108, the rebinarization being depicted in FIG. 18 using arrows 810. In particular, reconstructor 404, as described above, can extract from data stream 401 information regarding the division of the currently reconstructed image into blocks, at least some of which are subject to motion-compensated prediction. Fig. 19 depicts an image to be restored representatively at 820 and blocks of the just-mentioned subdivision of the image 120 for which motion compensated prediction is used to predict image content therein at 822. As described in relation to FIG. 2A-2C, there are different possibilities for subdivision and size of blocks 122. To avoid transmitting a motion vector difference 800 for each of these blocks 122, restorer 404 may use a merging principle whereby the data stream additionally conveys merging information in addition to subdivision information. or, in the absence of information about the division, in addition to the fact that the division is fixed. The merge information signals restorer 404 regarding which of the blocks 822 to form merge groups. By this measure, it is possible for restorer 404 to apply some motion vector difference 800 to the entire merge group of blocks 822. Of course, on the encoding side, transmission of merge information is subject to a trade-off between subdivision transmission overhead (if present), merge information transmission overhead, and transmission overhead. differences in motion vectors that decrease as the size of the merge groups increases. On the other hand, increasing the number of blocks per merge group reduces the adaptation of the motion vector differences for that merge group to the actual needs of the individual blocks of the corresponding merge group, thereby obtaining less accurate motion-compensated predictions of the motion vector differences of these blocks and necessitating higher transmission overhead for transmitting the prediction remainder in the form, for example, of the level of transformation coefficients. Therefore, a compromise is made on the encoding side accordingly. In either case, however, the merging principle results in motion vector differences for merging groups, depicting less spatial cross-correlation. See, for example, FIG. 19, which represents membership in a certain merge group by shading. Apparently, the actual movement of the image content in these blocks was so similar that the encoding party decided to merge the corresponding blocks. However, there is little correlation with the movement of image content in other merge groups. Therefore, the limitation of using just one context per bin of truncated unary code 806 does not negatively impact the efficiency of entropy encoding since the fusion principle already sufficiently ensures spatial cross-correlation between the content motion of adjacent images. The context may simply be selected based on the fact that the bin is part of a binarization of the 802 _x,y component of the motion vector difference and the bin's position, which is either 1 or 2 due to the cutoff value being two. Therefore, other already decoded _x,y mvd bins/syntactic elements/components 802 do not influence the context selection.

Likewise, restorer 404 may be configured to further reduce the information content to be forwarded by motion vector differences (other than spatial and/or temporal motion vector prediction) by using a multi-hypothesis prediction principle whereby, first, a list of motion vector predictors is generated for each block or merge group, then explicitly or implicitly transmitting in the data stream the predictor index information to be actually used for predicting the motion vector differences. See, for example, the open block 122 in FIG. 20. Restorer 404 may provide different predictors for the motion vector of a given block, for example, by predicting the motion vector spatially, such as from the left, from the top, a combination of both, etc., and temporally predicting the motion vector from the motion vector of a previously co-located part. decoded video image and additional combinations of the above predictors. These predictors are sorted by restorer 404 in a predictable manner that is predictable on the encoding side. Some information is transmitted for this purpose in the data stream and is used by the restorer. Those. some recommendation is contained in the data stream as to which predictor from a given ordered list of predictors will actually be used as a predictor for a given block's motion vector. This index may be explicitly passed in the data stream for this block. However, it is also possible that the index is first predicted and then only its prediction is transmitted. There are also other possibilities. In any case, the just mentioned prediction circuit allows a very accurate prediction of the motion vector of the current block to be obtained, and hence the information content requirement imposed on the motion vector difference is reduced. Therefore, limiting the context-adaptive entropy encoding to only two truncated unary code bins and reducing the cutoff value to 2, as described in relation to FIG. 18, as well as choosing an exponential Golomb code order of 1, does not have a negative effect on coding efficiency, since the motion vector differences show, due to high prediction efficiency, a frequency histogram whereby higher values of the 802x,y components of the motion vector difference are visited less frequently . Even omitting any difference between the horizontal and vertical components is suitable for effective prediction, since there is a high tendency for prediction to perform equally well in both directions of prediction accuracy.

It should be noted that in the above description, all the details provided with FIGS. 1-15 are also transferable to the objects shown in FIG. 16, such as, for example, which relate to the functionality of desymbolizer 314, restorer 404, and entropy decoder 409. However, for the sake of completeness, some of these details are again briefly described below.

For a better understanding of the prediction scheme just briefly outlined, see FIG. 20. As just described, constructor 404 may obtain different predictors for the current block 822 or the current block merge group, with these predictors shown as solid line vectors 824. The predictors can be obtained by spatial and/or temporal prediction, and in addition, arithmetic average operations or the like can be used, so that individual predictors can be obtained by the restorer 404 such that they are correlated with each other. Regardless of the manner in which the vectors 826 were obtained, the restorer 404 presents sequentially or sorts these predictors 126 into an ordered list. This is represented by numbers 1-4 in Fig. 21. It is preferable if the sorting process is uniquely defined so that the encoder and decoder can operate synchronously. Then the index just mentioned can be obtained by the restorer 404 for the current block, or merge group, from the data stream, either explicitly or implicitly. For example, a second predictor "2" may be selected and reconstructor 404 adds motion vector difference 800 to this selected predictor 126, thereby obtaining a final reconstructed motion vector 128, which is then used to predict, through motion compensated prediction, the contents of the current block. merger groups. In the case of a merge group, it would be possible for restorer 404 to include additional motion vector differences provided for blocks of the merge group to further refine the motion vector 128 with respect to individual blocks of the merge group.

Thus, continuing further with the description of implementations of the objects shown in FIG. 16, it may be that entropy decoder 409 is configured to derive truncated unary code 806 from data stream 401 using binary arithmetic decoding or binary PIPE encoding. Both principles have been described above. Additionally, entropy decoder 409 may be configured to use different contexts for two bin positions of truncated unary code 806 or, alternatively, even the same context for both bins. Entropy decoder 409 may be configured to perform probability state updating. Entropy decoder 409 may do this, for the bin currently output from truncated unary code 806, by transitioning from the current probability state associated with the context selected for the currently output bin to a new probability state depending on the bin output in this moment. See the Next_State_LPS and Next_State_MPS tables above, a table lookup on which is performed by the entropy decoder in addition to the other steps 0-5 listed above. In the above description, the current probability state was referred to by pState_current. It is defined for the relevant context of interest. The entropy decoder 409 may be configured to binary arithmetic decode the bin currently being derived from the truncated unary code 806 by quantizing the width value of the current probability interval, i.e. R representing the current probability interval to obtain the probability interval index, q_index, and perform interval subdivision by indexing the table element among the table elements using the probability interval index and the probability state index, i.e. p_state, which in turn depends on the current probability state associated with the context selected for the bin currently being inferred, to produce a division of the current probability interval into two partial intervals. In the above briefly described embodiments, these partial intervals were associated with the most likely and least likely symbol. As described above, entropy decoder 409 may be configured to use an eight-bit representation for the current probability interval width value R, capturing, for example, the most significant two or three bits of the eight-bit representation and quantizing the current probability interval width value. The entropy decoder 409 may further be configured to select from among two partial bins based on the offset state value from the interior of the current probability bin, namely V, update the probability bin width value R and the offset state value, and guess the value of the bin to be output to now using the selected partial interval, and performing a renormalization of the updated probability interval width value R and the offset state value V, including continuing to read bits from data stream 401. Entropy decoder 409, for example, may be configured to binary arithmetic decode a bin from an exponential Golomb code by halving the width value of the current probability interval to obtain a subdivision of the current probability interval into two partial intervals. Dividing in half corresponds to a probability estimate, which is fixed at 0.5. It can be implemented by simply shifting bits. The entropy decoder may further be configured, for each motion vector difference, to output a truncated unary code of the horizontal and vertical components of the corresponding motion vector difference from data stream 401, before an exponential Golomb code of the horizontal and vertical components of the corresponding motion vector difference. By means of this measure, entropy decoder 409 can exploit that more bins together form a series of bins for which the probability estimate is fixed, namely 0.5. This can speed up the entropy decoding procedure. On the other hand, entropy decoder 409 may choose to maintain order among the motion vector differences by first deriving the horizontal and vertical components of one motion vector difference, then simply moving on to deriving the horizontal and vertical components of the next motion vector difference. By this measure, the memory requirements imposed on the decoding object are reduced, i.e. decoder according to FIG. 16, since the desymbolizer 314 can continue to debinarize the motion vector differences directly without having to wait for other motion vector differences to be scanned. This is made possible by context selection: since only exactly one context is available per 806 code bin position, there is no need to inspect the spatial relationship.

Restorer 404, as described above, can spatially and/or temporally predict horizontal and vertical components of motion vectors to obtain predictors 126 for horizontal and vertical components of motion vectors and recover horizontal and vertical components of motion vectors by refining predictors 826 using the horizontal and vertical components motion vector differences, for example, by simply adding the motion vector difference to the corresponding predictor.

In addition, reconstructor 404 may be configured to predict the horizontal and vertical components of motion vectors in different ways to obtain an ordered list of predictors for the horizontal and vertical components of motion vectors, obtain a list index from the data stream, and recover the horizontal and vertical components of motion vectors by refining the predictor , the list predictor pointed to by the list index, using the horizontal and vertical components of the motion vector differences.

In addition, as described above, reconstructor 404 may be configured to reconstruct video using motion-compensated prediction by applying horizontal and vertical motion vector components 802x,y at a spatial degree of partitioning determined by dividing video images into blocks, where reconstructor 404 may use merge syntax elements present in data stream 401 to group blocks into merge groups and apply the integer values of the horizontal and vertical components 802x,y of the motion vector differences obtained by binarizer 314 in units of merge groups.

Reconstructor 404 may output a subdivision of video images into blocks from a portion of data stream 401 that excludes merge syntax elements. The restorer 404 may also adapt the horizontal and vertical components of the predetermined motion vector for all blocks of the associated merge group, or refine them by the horizontal and vertical components of the motion vector differences associated with the blocks of the merge group.

For completeness only, fig. 17 shows an encoder corresponding to the decoder of FIG. 16. Encoder according to FIG. 17 includes a constructor 504, a symbolizer 507, and an entropy encoder 513. The encoder includes a constructor 504 configured to predictively encode video 505 by motion compensated prediction using motion vectors, and predictively encode motion vectors by predicting motion vectors and setting integer values 506 horizontal and vertical components of the motion vector differences to represent the prediction error of the predicted motion vectors; a symbolizer 507 configured to binarize integer values to obtain binarizations 508 of the horizontal and vertical components of the motion vector differences, wherein the binarizations are equal to a truncated unary code of the horizontal and vertical components, respectively, in the first interval of the domain of definition of the horizontal and vertical components below the cutoff value and the prefix combination in the form of a truncated a unary code for the cutoff value and a suffix in the form of an exponential Golomb code of horizontal and vertical components, respectively, in the second interval of the domain of definition of the horizontal and vertical components, inclusive and above the cutoff value, wherein the cutoff value is equal to two, and the exponential Golomb code has an order equal to one; and an entropy encoder 513 configured for the horizontal and vertical components of motion vector differences, capable of encoding a truncated unary code into the data stream using context-adaptive binary entropy encoding with exactly one context per truncated unary code bin position that is common to the horizontal and the vertical components of the differences between the motion vectors, and the exponential Golomb code, using the traversal mode with constant equiprobability. Other possible implementation details are directly transferred from the description regarding the decoder of FIG. 16, into the encoder of FIG. 17.

Although some aspects have been described in the context of a device, it is clear that these aspects also represent a description of the corresponding method, where the block or device corresponds to a method step or a feature of a method step. Likewise, aspects described in the context of a method step also provide a description of a corresponding block or element or feature of a corresponding device. Some or all of the method steps may be performed by (or use) a hardware device, such as, for example, a microprocessor, a programmable computer, or an electronic circuit. In some embodiments, some one or more of the most critical steps of the method may be performed by such a device.

The inventive encoded signal may be stored on a digital storage medium or may be transmitted over a transmission medium such as a wireless transmission medium or a wired transmission medium such as the Internet.

Depending on certain implementation requirements, embodiments of the invention may be implemented in hardware or software. Implementation may be performed using a digital storage medium, such as a floppy disk, digital versatile disc (DVD), Blue-Ray disc, compact disc, read-only memory (ROM), programmable ROM (PROM), erasable programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM) or flash memory having electronically readable control signals stored thereon that interact (or are capable of interacting) with a programmable computer system such that the corresponding method is performed. Therefore, the digital storage medium can be read by a computer.

Some embodiments of the invention include a storage medium having electronically readable control signals that are capable of interfacing with a programmable computer system such that one of the methods described herein is performed.

In general, embodiments of the present invention may be implemented as a computer program product with program code, wherein the program code operates to perform one of the methods when the computer program product is executed on a computer. The program code, for example, may be stored on a machine-readable medium.

Other embodiments comprise a computer program for performing one of the methods described herein stored on a machine-readable medium.

In other words, an embodiment of the inventive method is therefore a computer program having program code for performing one of the methods described herein when the computer program is executed on a computer.

Another embodiment of the inventive methods, therefore, is a storage medium (or digital storage medium or computer readable medium) containing a computer program stored thereon for performing one of the methods described herein. A storage medium, digital storage medium, or recorded medium is typically tangible and/or intransitive.

Another embodiment of the inventive method, therefore, is a stream of data or a sequence of signals representing a computer program for executing one of the methods described herein. The data stream or signal sequence, for example, may be configured to be sent over a data connection, such as the Internet.

An additional embodiment comprises processing means, such as a computer or programmable logic device, configured or adaptable to perform one of the methods described herein.

A further embodiment comprises a computer having a computer program installed thereon for performing one of the methods described herein.

A further embodiment of the invention comprises a device or system configured to transmit (eg, electronically or optically) to a receiver a computer program to perform one of the methods described herein. The receiver, for example, may be a computer, mobile device, memory device, or the like. The device or system, for example, may include a file server for transferring a computer program to a receiver.

In some embodiments, a programmable logic device (eg, a programmable gate array) may be used to perform some or all of the functionality of the methods described herein. In some embodiments, the field programmable gate array may interface with a microprocessor to perform one of the methods described herein. In general, the methods are preferably performed by any hardware device.

The above-described embodiments are merely illustrative of the principles of the present invention. It will be appreciated that modifications and changes to the devices and parts described herein will be apparent to one skilled in the art. They are, therefore, intended to be limited only by the scope of the pending claims and not by the specific details provided by the description and explanation of the embodiments herein.

Claims (34)

1. A decoder for decoding video encoded in a data stream, containing: a desymbolizer configured to debinarize binarizations of motion vector differences, wherein the video is predictively encoded by motion compensated prediction using the motion vectors, wherein the motion vector differences represent a prediction error with respect to the motion vectors, and each of the motion vector difference binarizations includes a string of prefix bins including two fixed-length binary codes based on a cutoff value of two, and a string of suffix bins including an exponential Golomb code having a fixed order specified as one, at In this case, each fixed-length binary code of a string of prefix bins indicates whether the absolute value of the difference in motion vectors is greater than the corresponding fixed value; And a reconstructor configured to reconstruct video based on debinarized values of motion vector differences. 2. The decoder of claim 1, wherein the restorer is configured to spatially and/or temporally predict motion vectors to obtain predictors for the motion vectors, and recover the motion vectors by refining the predictors using motion vector differences. 3. The decoder of claim 1, wherein the restorer is configured to predict motion vectors in various ways to obtain an ordered list of predictors for the motion vectors, obtain a list index from the data stream, and restore the motion vectors by refining the predictor with the list predictor pointed to by the index. list using motion vector differences. 4. The decoder of claim 1, wherein the restorer is configured to reconstruct video using motion compensated prediction by applying motion vectors with a spatial degree of partitioning determined by subdividing the video images into blocks, wherein the restorer uses fusion syntactic elements present in the data stream, to group blocks into merge groups and apply the debinarized motion vector difference values obtained by the desymbolizer in units of merge groups. 5. The decoder according to claim 4, wherein the restorer is configured to derive subdivisions of video images in blocks from a portion of the data stream, excluding syntactic merge elements. 6. The decoder of claim 4, wherein the restorer is configured to accept a predetermined motion vector for all blocks of an associated merge group, or refine it by differences in motion vectors associated with blocks of the merge group. 7. The decoder of claim 1, wherein the data stream comprises at least a portion associated with color video bins. 8. The decoder of claim 1, wherein the data stream comprises at least a portion associated with depth values associated with a depth map associated with the video. 9. The decoder of claim 1, further comprising an entropy decoder configured to decode at least fixed length binary codes using binary arithmetic decoding. 10. The decoder according to claim 9, wherein the entropy decoder is configured to decode fixed-length binary codes for each motion vector difference before decoding the exponential Golomb code. 11. A method for decoding video encoded in a data stream, comprising the steps of: debinarizing binarizations of the motion vector differences, wherein the video is predictively encoded by motion compensated prediction using the motion vectors, wherein the motion vector differences represent a prediction error with respect to the motion vectors, and each of the motion vector difference binarizations includes a string of prefix bins including two fixed-length binary codes based on a cutoff value of two, and a string of suffix bins including an exponential Golomb code having a fixed order specified as one, at In this case, each fixed-length binary code of a string of prefix bins indicates whether the absolute value of the difference in motion vectors is greater than the corresponding fixed value; And reconstruct the video based on the debinarized values of the motion vector differences. 12. The method of claim 11, wherein the recovery includes spatial and/or temporal prediction of motion vectors to obtain predictors for the motion vectors, and recovery of the motion vectors by refining the predictors using motion vector differences. 13. The method of claim 11, wherein the recovery includes predicting motion vectors in various ways to obtain an ordered list of predictors for the motion vectors, obtaining a list index from the data stream, and recovering the motion vectors by refining the predictor with the list predictor pointed to by the index. list using motion vector differences. 14. The method of claim 11, wherein the restoration includes restoring the video using motion compensated prediction by applying motion vectors with a spatial degree of partitioning determined by subdividing the video images into blocks, wherein syntactic fusion elements present in the data stream are used, to group blocks into merge groups and apply debinarized values of motion vector differences in units of merge groups. 15. The method of claim 14, wherein the recovery further includes deriving the subdivision of video images into blocks from a portion of the data stream, excluding the merge syntax elements. 16. The method of claim 14, wherein the recovery further includes accepting a predetermined motion vector for all blocks of the associated merge group or refining it by differences in the motion vectors associated with the blocks of the merge group. 17. The method of claim 11, wherein the data stream comprises at least a portion associated with color video bins. 18. The method of claim 11, wherein the data stream comprises at least a portion associated with depth values associated with a depth map associated with the video. 19. The method of claim 11, further comprising the step of entropy decoding fixed-length binary codes using binary arithmetic decoding. 20. The method of claim 19, wherein the entropy decoding includes, for each motion vector difference, decoding fixed-length binary codes before decoding an exponential Golomb code. 21. A method of encoding video into a data stream containing the steps of: predictively encoding the video by motion compensated prediction using the motion vectors, and predictively encoding the motion vectors by predicting the motion vectors and generating motion vector differences, wherein the motion vector differences represent a prediction error with respect to the motion vectors; binarize the motion vector differences such that each binarization includes two fixed-length binary codes based on a cutoff value of two, and a string of suffix bins including an exponential Golomb code having a fixed order specified as one, with each binary code fixed-length string of prefix bins indicates whether the absolute value of the motion vector difference is greater than the corresponding fixed value; And encode the binarized values of the motion vector differences into the data stream. 22. The method of claim 21, wherein the data stream comprises at least a portion associated with color video bins. 23. The method of claim 21, wherein the data stream comprises at least a portion associated with depth values associated with a depth map associated with the video. 24. The method of claim 21, further comprising the step of entropy encoding fixed-length binary codes using binary arithmetic encoding. 25. The method of claim 24, wherein the entropy encoding includes, for each motion vector difference, encoding fixed-length binary codes prior to encoding exponential Golomb codes.

Images