Apparatus and method for encoding or decoding using a subband dependent prediction adaptation for GCLI entropy coding

An apparatus for encoding image data, the image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein a precinct has different sets of coefficients from different subbands, wherein two sets of coefficients of a first precinct belong to a first spatial region of an image represented by the image data, the apparatus having: a processor for determining, for each group of coefficients within a set, a greatest coded line index (GCLI); an encoder for encoding the greatest coded line indices associated with a first set of the first precinct in accordance with a first encoding mode, and for encoding the greatest coded line indices associated with a second set of the first precinct in accordance with a second encoding mode, the second encoding mode being different from the first encoding mode; and an output interface for outputting an encoded image signal having data on the encoded greatest coded line indices and data on the coefficients.

CROSS-REFERENCE TO RELATED APPLICATIONS

This is a continuation of copending International Application No. PCT/EP2017/083334, filed Dec. 18, 2017, which is incorporated herein by reference in its entirety, and additionally claims priority from European Application No. 16205187.4, filed Dec. 19, 2016, which is also incorporated herein by reference in its entirety.

BACKGROUND OF THE INVENTION

The present invention is related to image coding and, particularly, to image coding relying on a greatest common line index (GCLI) entropy coding.

1.1 Image Transform

Image and video compression typically applies a transform before running entropy coding. Reference [5], for instance, uses a block based prediction, while references [1][2][3][4] advocate for wavelet transforms.

Such a wavelet transform is depicted inFIG. 1. It decomposes an image into a number of subbands. As depicted inFIG. 1, the number of horizontal decompositions might be different from the number of vertical decompositions. In each decomposition step, the lowpass subband of the previous decomposition is further decomposed. The L5 subband represents a subsampled version of the image, while the other subbands contain the detail-information.

After the frequency transform, the coefficients of the subbands are entropy-coded. In other words, g>1 coefficients of a subband ABm, with A,B ∈ {L, H}, m ∈are formed to a coefficient group. Then the number of remaining bit-planes is signaled, followed by the raw data bits. More details on the coding technique are explained in the following section.

FIG. 1illustrates a specific exemplary wavelet transform of an image. In this example, two vertical and four horizontal decompositions are assumed.

Particularly, a first subband is subband HL1101that results from a high pass filtering in the vertical or y direction and a low pass filtering in the horizontal or x direction. Subband102indicated as HH1 results from high pass filtering actions in both the vertical and the horizontal directions. Furthermore, subband LH1 indicated at103results from vertical low pass filtering and horizontal high pass filtering of the subband resulting from lowpass filtering of the image. Furthermore, subband105indicated at HH2 results from vertical and horizontal high pass filtering actions of the subband resulting from lowpass filtering of the image.

Furthermore, subband104indicated at HL2 results from vertical high pass filtering and horizontal low pass filtering of the subband resulting from lowpass filtering of the image. Subband106indicated at LH2 results from vertical low pass filtering and horizontal high pass filtering of the subband resulting from lowpass filtering of the image. Analogously, subband107results from horizontal high pass filtering of a subband generated by two low pass filterings in both horizontal and vertical directions, and subband108indicated at H4 results from vertical high pass filtering of a subband generated by two low pass filterings in vertical direction and three low pass filterings in horizontal direction, and subband109illustrates the approximated low pass image.

FIG. 2aillustrates the principle of GCLI coding where a group of coefficients is formed by four values, where each value is represented by a certain number of bit-planes such as eight bit-planes and a sign bit indicated at s0, s1, s2, s3. Naturally, any other group of coefficients can be formed such as a group having only two or only three or even more than four coefficients. Furthermore, there does exist a single coefficient for each position in each subband101to109for each color. Thus, since a three-color representation is used, three coefficients exist for each position in each of the subbands illustrated inFIG. 1.

FIG. 2aillustrates the principle of the GCLI coding. A number of coefficients (being larger than one), belonging to the same subband of a frequency transform, are combined to a group. These coefficients are represented in sign-magnitude representation. The largest coefficient in the group determines the number of active bit-planes. A bit-plane is called active, if at least one coefficient bit of the bit-plane itself or any previous—that is more significant—bit-plane is unequal to zero. The number of active bit-planes is given by the so-called GCLI value (greatest coded line index). A GCLI value of zero means that no bit-planes are active, and hence the complete coefficient group is zero.

For lossy encoding, some of the bit-planes might be truncated. This corresponds to a quantization with a factor being a power of two. The quantization is specified by the so-called GTLI (Greatest Trimmed Line Index). A GTLI of zero corresponds to no quantization. The active bit-planes remaining after quantization are called remaining bit-planes in the following. Moreover, the GTLI is also called truncation point in the following.

These remaining bit-planes are then transmitted as raw bits to the decoder. In order to enable correct decoding, the decoder needs to know the number of remaining/transmitted bit-planes for every group of coefficients. Consequently, they need to be signaled to the decoder as well. This is done by a variable length code that represents the difference to the number of remaining bit-planes of a previous coefficient group. This previous coefficient group can in principle be any coefficient group that the encoder has already encoded before. Hence, it can for instance be a horizontal or a vertical neighbor group.

The method described below is agnostic to the transmission order of the different bit-stream parts. For instance, it is possible to first place the GCLI coefficients of all subbands into the bitstream, followed by the data bits of all subbands. Alternatively, GCLI and data bits might be interleaved.

1.3 Coefficient Organization

The coefficients of the frequency transform depicted inFIG. 1are organized in so-called precincts as depicted inFIG. 3. Precincts group coefficients of different subbands belonging to the same spatial region in the input image.

The upper portion ofFIG. 3illustrates the distribution of the individual precincts 1, 2, . . . within the individual subbands101to109illustrated inFIG. 1. Typically, a precinct defines a spatial area that has, for example, a height of two lines that has the same width as the image and consists of, for example, 3840 columns. Naturally, a precinct can also include other heights of lines such as three or four or even more line heights and more or less columns. A number of lines that can be divided by two is, however, of advantage.

Particularly, the precinct has the first two lines of HH1 indicated at301and302and the first two lines of LH1 indicated at303,304. Furthermore, the precinct has the first two lines of HL1 indicated at305and306and a single line of HL2 indicated at309, a single line of HH2 indicated at307, a single line of LH2 indicated at308, a single line of H3 indicated at310, a single line of H4 indicated at311and a single line of L5 indicated at312. The final number of precincts that are used for a picture depends on the number of lines of the picture and how many lines are included within a precinct.

In order to enable the decoder to recover the signal, it needs to know the GCLI value for every coefficient group. Different methods are available in the state of the art [2] to signal them efficiently.

1.4.1 RAW Mode

In the RAW mode, the GCLI value is transmitted without any prediction or by predicting it from zero. Hence, let F1be the coefficient group to be encoded next. Then the GCLI value can be encoded by a the following prediction residual:
δ=max(GCLI(F1)−GTLI(F1), 0)

For this value, two different codes can be used. The first one is transmitting the S value as a fixed length binary code where one example is illustrated in the following table.

The second code is a variable length unsigned unary code depicted in the following table and also described in [7] as GCLI unsigned unary coding without prediction.

In an alternative embodiment, an alternative code can be constructed by replacing 0 with 1 and vice versa in the above table.

Let F1and F2be two horizontally neighbored coefficient groups, consisting of g>1 coefficients. Let F2be the coefficient group to be currently coded. Then GCLI(F2) can be signaled to the decoder by transmitting

The decoder recovers GCLI(F2) by computing

In horizontal prediction, typically GTLI(F1)=GTLI(F2) is valid, and δ is typically transmitted as a variable length code.

Essentially, this means that
δ=max(GCLI(F2),GTLI(F2))−max(GCLI(Fi),GTLI(F2))

Let F1and F2be two vertically neighbored coefficient groups, consisting of g>1 coefficients. Let F2be the coefficient group to be currently coded.

The GCLI(F2) can be encoded in the same way than in Section 1.4.2.

In an alternative embodiment, the following prediction formula can be used for vertical prediction:
δ=max(GCLI(F2),GTLI(F2))−max(GCLI(F1), max(GTLI(F1),GTLI(F2)))

The decoder then recovers GCLI(F2) by computing

In addition to the prediction modes, different coding modes can be used. Reference [6], for instances proposes a method to compress zero GCLIs more efficiently. To this end, for every group of eight GCLIs a single bit flag indicates whether the GCLI group is zero or not. Zero GCLI groups are not further encoded, while non-zero GCLI groups are encoded as described in Section 1.4.2.

In the following, coding modes are simply considered as additional prediction modes for reasons of simplicity.

Exemplary equations for the calculation of the different coding modes are illustrated inFIG. 2bfor the horizontal or vertical prediction mode with respect to the encoder-side. Furthermore,FIG. 2cillustrates exemplary equations for the horizontal/vertical prediction mode performed at the decoder-side, andFIG. 2dillustrates the functionality of the raw mode.

In the state of the art [2], the prediction method to use is selected on a precinct base. In other words, the GCLI values of all subbands of the precinct are predicted by the same scheme. This, however, does not leverage the full potential of the codec.

SUMMARY

According to an embodiment, an apparatus for encoding image data, the image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein a first subband of the plurality of different subbands has a first set of coefficients, wherein a different second subband of the plurality of different subbands has a different second set of coefficients, wherein a precinct has the first and the second sets of coefficients from the first and the second subbands of the plurality of different subbands, wherein the first and the second sets of coefficients of the precinct belong to a spatial region of an image represented by the image data, may have: a processor for determining, for each group of coefficients within a set, a greatest coded line index (GCLI); an encoder for encoding the greatest coded line indices associated with the first set of coefficients of the precinct in accordance with a first encoding mode, and for encoding the greatest coded line indices associated with the second set of coefficients of the precinct in accordance with a second encoding mode, the second encoding mode being different from the first encoding mode; and an output interface for outputting an encoded image signal having data on the encoded greatest coded line indices and data on the coefficients, wherein the first encoding mode and the second encoding mode are selected from a set of encoding modes having at least two of: a vertical prediction encoding mode, a horizontal prediction encoding mode, and a raw encoding mode.

According to another embodiment, an apparatus for decoding an encoded image signal having data on encoded greatest coded line indices and data on coefficients may have: a decoding mode determiner for determining different decoding modes for the data on the encoded greatest coded line indices for different subbands within a precinct, wherein the data on the coefficients represent image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein the precinct has different sets of coefficients from different subbands, wherein two sets of coefficients of a precinct belong to a spatial region of an image represented by the image data; and a decoder for decoding the data on the encoded greatest coded line indices for the first set in the precinct using the first decoding mode and for decoding the data on the encoded greatest coded line indices for the second set in the precinct using a second decoding mode as determined by the decoding mode determiner, and for decoding the data on the coefficients using decoded greatest coded line index data, wherein the first decoding mode and the second decoding mode are selected from a group of decoding modes having at least two of a vertical inverse prediction decoding mode, a horizontal inverse prediction decoding mode, and a raw decoding mode.

According to another embodiment, a method for encoding image data, the image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein a first subband of the plurality of different subbands has a first set of coefficients, wherein a different second subband of the plurality of different subbands has a different second set of coefficients, wherein a precinct has the first and the second sets of coefficients from the first and the second subbands of the plurality of different subbands, wherein the first and the second sets of coefficients of the precinct belong to a spatial region of an image represented by the image data, my have the steps of: determining, for each group of coefficients within a set, a greatest coded line index (GCLI); encoding the greatest coded line indices associated with the first set of coefficients of the precinct in accordance with a first encoding mode, and encoding the greatest coded line indices associated with the second set of coefficients of the precinct in accordance with a second encoding mode, the second encoding mode being different from the first encoding mode; and outputting or storing an encoded image signal having data on the encoded greatest coded line indices and data on the coefficients, wherein the first encoding mode and the second encoding mode are selected from a set of encoding modes having at least two of: a vertical prediction encoding mode, a horizontal prediction encoding mode, and a raw encoding mode.

According to still another embodiment, a method for decoding an encoded image signal having data on encoded greatest coded line indices and data on coefficients may have the steps of: determining different decoding modes for the data on the encoded greatest coded line indices for different subbands within a precinct, wherein the data on the coefficients represent image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein the precinct has different sets of coefficients from different subbands, wherein two sets of coefficients of a precinct belong to a spatial region of an image represented by the image data; and decoding the data on the encoded greatest coded line indices for the first set in the precinct using the first decoding mode and decoding the data on the encoded greatest coded line indices for the second set in the precinct using a second decoding mode as determined by the determining the different decoding modes, and decoding the data on the coefficients using decoded greatest coded line index data, wherein the first decoding mode and the second decoding mode are selected from a group of decoding modes having at least two of a vertical inverse prediction decoding mode, a horizontal inverse prediction decoding mode, and a raw decoding mode.

Another embodiment may have an encoded image signal having data on encoded greatest coded line indices, data on coefficients representing image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein a first subband of the plurality of different subbands has a first set of coefficients, wherein a different second subband of the plurality of different subbands has a different second set of coefficients, wherein a precinct has the first and the second sets of coefficients from the first and the second subbands of the plurality of different subbands, wherein the first and the second sets of coefficients of the precinct belong to a spatial region of an image represented by the encoded image signal, and signaling information for signaling two different decoding modes for at least two different subbands of the precinct, wherein the first decoding mode and the second decoding mode are selected from a group of decoding modes having at least two of a vertical inverse prediction decoding mode, a horizontal inverse prediction decoding mode, and a raw decoding mode.

Still another embodiment may have a non-transitory digital storage medium having stored thereon a computer program for performing a method for encoding image data, the image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein a first subband of the plurality of different subbands has a first set of coefficients, wherein a different second subband of the plurality of different subbands has a different second set of coefficients, wherein a precinct has the first and the second sets of coefficients from the first and the second subbands of the plurality of different subbands, wherein the first and the second sets of coefficients of the precinct belong to a spatial region of an image represented by the image data, the method having the steps of: determining, for each group of coefficients within a set, a greatest coded line index (GCLI); encoding the greatest coded line indices associated with the first set of coefficients of the precinct in accordance with a first encoding mode, and encoding the greatest coded line indices associated with the second set of coefficients of the precinct in accordance with a second encoding mode, the second encoding mode being different from the first encoding mode; and outputting or storing an encoded image signal having data on the encoded greatest coded line indices and data on the coefficients, wherein the first encoding mode and the second encoding mode are selected from a set of encoding modes having at least two of: a vertical prediction encoding mode, a horizontal prediction encoding mode, and a raw encoding mode, when said computer program is run by a computer.

Another embodiment may have a non-transitory digital storage medium having stored thereon a computer program for performing a method for decoding an encoded image signal having data on encoded greatest coded line indices and data on coefficients having the steps of: determining different decoding modes for the data on the encoded greatest coded line indices for different subbands within a precinct, wherein the data on the coefficients represent image data being decomposed into a plurality of different subbands, each subband having a plurality of coefficients, wherein the precinct has different sets of coefficients from different subbands, wherein two sets of coefficients of a precinct belong to a spatial region of an image represented by the image data; and decoding the data on the encoded greatest coded line indices for the first set in the precinct using the first decoding mode and decoding the data on the encoded greatest coded line indices for the second set in the precinct using a second decoding mode as determined by the determining the different decoding modes, and decoding the data on the coefficients using decoded greatest coded line index data, wherein the first decoding mode and the second decoding mode are selected from a group of decoding modes having at least two of a vertical inverse prediction decoding mode, a horizontal inverse prediction decoding mode, and a raw decoding mode, when said computer program is run by a computer.

The present invention is based on the finding that the coding efficiency on the one hand or the encoding quality on the other hand can be enhanced by determining, for each subband within a precinct, i.e., for each plurality of coefficients from a subband within a precinct, an own encoding mode for encoding the greatest coded line index (GCLI) data.

Thus, a concept for encoding image data, where the image data is decomposed into a plurality of different subbands, where each subband comprises a plurality of coefficients, and wherein a precinct comprises different sets of coefficients from different subbands, where two sets of coefficients of a precinct belong to a certain spatial region of an image represented by the image data relies on a determination of a greatest coded line index for each group of coefficients within a set of coefficients and, additionally, relies on an encoder for encoding the greatest coded line indices associated with a certain set of a precinct in accordance with a first encoding mode and for encoding the greatest coded line indices associated with a second set of the same precinct in accordance with a second encoding mode, where the second encoding mode is different from the first encoding mode. Furthermore, the output interface of an apparatus for encoding image data outputs an encoded image signal having data on the encoded greatest coded line indices for the individual subbands/sets of coefficients and, additionally, data on the corresponding coefficients.

On the decoder-side, the present invention relies on the functionality that there is a decoding mode determiner for determining different decoding modes for the data on the encoded greatest coded line indices for different subbands within a precinct, wherein the data on the coefficients represent image data being decomposed into a plurality of different subbands, each subband comprising a plurality of coefficients, where the precinct comprises different sets of coefficients from different subbands. Particularly, the decoder for decoding the data on the encoded greatest coded line indices for the first set in the first precinct uses a first decoding mode and for decoding the data on the encoded greatest coded line indices for the second set in the precinct, a second decoding mode is used as determined by the decoding mode determiner. Furthermore, the data on the coefficients is then decoded using the decoded greatest coded line index data obtained by using the different decoding modes per subband or set of coefficients.

Due to the fact that individual encoding or decoding modes are made possible for individual sets of coefficients or subbands within a precinct, the computational efficiency is enhanced, since the number of bits to encode the greatest coded line indices (GCLI) values is reduced. This is due to the fact that there is a high potential for correlated or closely related GCLI values within a subband making them useful for some kind of prediction, but the GCLI values can vary substantially within a precinct from subband to subband.

Some embodiments rely on an actual mode determination based on the individual subband. Thus, in one embodiment, a specific encoding mode can be predetermined for each subband irrespective of the actual data. Such procedure is extremely efficient, since the encoding mode does not have to be transmitted from the encoder to the decoder, but can be predetermined on the encoder side and on the decoder side.

Other embodiments rely on an actual determination of the encoding mode based on the image data. A specific embodiment relies on the calculation of the data budgets for the individual subbands or precincts in order to determine the encoding mode for each subband. This procedure can be used fully integrated within a quantization determination based on a GTLI procedure (GTLI=greatest trimmed level index or greatest trimmed line index) corresponding to a certain truncation point). However, GTLI encoding can also be used as a lossless encoding, where any truncation is not performed and, therefore, any GTLI processing is not necessary. However, it is of advantage to use, in addition to GCLI processing also GLTI processing in order adapt the bitrate to a certain target bitrate or in order to obtain a constant bitrate as the case may be.

Further embodiments rely on the mixed procedure, where, for certain subbands within a precinct, the same or different encoding modes are predetermined and where, for other, typically, the lower subbands representing the high resolution information, the encoding modes are calculated based on the used bit budgets, i.e., are calculated based on the actual image data.

Further embodiments rely on a greatest coded line index determination for a group of coefficients, where the number of coefficients within a group is greater than two and, advantageously equal to four. Furthermore, the actual lossy encoding or quantization based on the determined truncation point, i.e., the GTLI processing is performed in such a way that the same GTLI is determined for a whole precinct. However, in other embodiments, the same GTLI is determined for an individual subband. Thus, it is of advantage to use a higher granularity for the truncation point determination compared to the greatest coded line index determination.

In further embodiments, three different encoding modes are performed, i.e., a horizontal prediction mode, a vertical prediction mode or a raw mode without any prediction. However, other encoding modes can be performed as well such as a run length mode, or a prediction mode not in the horizontal or vertical direction but in a kind of a skewed direction where, for example, a prediction is not performed between GCLI values of coefficients abutting to each other vertically, but a prediction is performed between GCLIs associated with coefficients that are shifted to each other horizontally. Thus, the different encoding modes can be determined as needed and can, therefore, be determined to be five, six, or even more encoding modes. Furthermore, the encoding modes do not necessarily have to always include a horizontal or a vertical prediction mode, but the different encoding modes can also consist of, for example, the raw mode and the skew mode or any other combination of encoding modes.

In further embodiments, other procedures are performed within the encoder or the decoder. Particularly, the image data can be subjected to a color transform before being introduced into the discrete wavelet transform operation. Alternatively or additionally, a sign-magnitude transform can be performed before performing the GCLI extraction.

Furthermore, the result of the GCLI prediction can be entropy encoded such as by using an unary code while, for example, the raw data is introduced into the bitstream as it is, i.e., without further coding.

Furthermore, the result of truncation or GTLI trimming of the coefficient data can be introduced into the data stream as it is, i.e., packed into the data stream, but, alternatively, further encoding operations such as Huffman encoding or arithmetic coding or any other kind of entropy coding can be used in addition. For complexity reasons, however, it is of advantage to pack the output of the GTLI controlled trimming or truncation, i.e., to remaining bits between a GCLI indicated bit-plane and a GTLI indicated bit-plane directly into the encoded image signal, i.e., directly into a bitstream of binary data.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 6illustrates an apparatus for encoding image data, where the image data is decomposed into a plurality of different subbands, where each subband comprises a plurality of coefficients. Particularly, a precinct comprises different sets of coefficients from different subbands, and two sets of coefficients of a first precinct belong to a first spatial region of an image represented by the image data and, for example two sets of coefficients of a second precinct belong to a second spatial region of an image represented by the image data, where the first spatial region and the second spatial region are different from each other and are, advantageously, even exclusive to each other, so that the first spatial region and the second spatial region do not have any subband positions in common. In this context, the spatial region of a coefficient can either by defined directly in the domain of transform coefficients, or in the domain of the image domain, when relating the transform coefficient with its central filter coefficient.

The apparatus for encoding image data comprises a processor600for determining, for each group of coefficients within a set of coefficients, a greatest coded line index (GCLI). Furthermore, the apparatus comprises an encoder660for encoding the greatest coded line indices associated with a first set of the first precinct in accordance with a first encoding mode and for encoding the greatest coded line indices associated with a second set of the first precinct in accordance with a second encoding mode, the second encoding mode being possibly different from the first encoding mode. Furthermore, the apparatus comprises an output interface680for outputting an encoded image signal (out) having data on the encoded greatest coded line indices and data on the coefficient values. Particularly, the coefficients are encoded using an image data/coefficients encoder620also illustrated inFIG. 6. The image data/coefficients encoder620receives, as an input, advantageously the same image data as are input into the processor600. Additionally, block620also receives the GCLI data for each group, and block620outputs data on coefficients that are included into the output data signal by the output interface680as well. Advantageously used encoding modes are a vertical prediction mode, a horizontal prediction mode, a raw encoding mode or a zero run-length mode or, as stated before, a skew prediction mode or any other coding or processing mode.

FIG. 7illustrates a corresponding apparatus for decoding an encoded image signal. The encoded image signal is input into a decoder720. Additionally, the apparatus for decoding comprises a decoding mode determiner for determining different decoding modes for the data on the encoded greatest coded line indices for different subbands within a precinct. This decoding mode per subband of a precinct is forwarded via connection730from the decoding mode determiner700to the decoder720. Depending on the implementation, the decoding mode determiner700is fed by the encoded image signal in order to extract the decoding mode, when such a decoding mode indication is included in the encoded image signal. However, in other embodiments, where the decoding mode per subband is fixed or pre-determined, the decoding mode determiner only uses this predetermined decoding mode allocation per subband and does not need the encoded image signal. Therefore, the connection between the encoded image signal and the decoding mode determiner700is illustrated as a broken line in order to show the optionality. Consequently, the arrow with “predetermined subband decoding mode allocation” leading into block700is also illustrated in broken lines.

FIG. 8aillustrates an implementation of a coding mode determiner640also illustrated inFIG. 6as being connected to the encoder660for the GCLI encoding. The mode determiner640is configured for determining the first encoding mode and the second encoding mode for the sets of coefficients based on the corresponding subband, to which a set of coefficients belongs to. This procedure is illustrated inFIG. 8aat blocks802and804. An exemplary encoding mode per subband allocation is illustrated inFIG. 5for each of the exemplary nine subbands101,102,103,104,105,106,107,108,109. Particularly, subbands101,104rely on the horizontal prediction mode for the encoding of GCLI data and the other subbands102,103,105,106,107,108,109rely on the vertical prediction mode per subband.

In an alternative embodiment, the determination of the encoding mode for a subband performed by the mode determiner640is performed as illustrated inFIG. 8b.Particularly, the mode determiner640is configured for determining the first encoding mode and the second encoding mode by computing810a first bit budget for a first precinct and the first set of coefficients within the first precinct and the first encoding mode. Furthermore, the mode determiner640computes812a second bit budget for the first precinct and the first set of coefficients, but now for a second encoding mode. Both the first bit budget and the second bit budget calculated by blocks810,812are used by the mode determiner640to select814an encoding mode for the first set of coefficients of the first precinct. Then, in step816performed by the output interface680ofFIG. 6, an indication of the encoding mode selected for the first set of coefficients is included into the encoded image signal. This is also indicated by broken line660ofFIG. 6. In case of more than two encoding modes, the above steps are repeated accordingly.

FIG. 4illustrates a further implementation of a block diagram of the subband adaptive prediction scheme per subband.

FIG. 4illustrates the corresponding block diagram. The output of the frequency transform400is optionally prequantized402before being sent to a budget computation block410-414. The budget computation block410-414computes for every subband and for every possible GTLI (truncation point) and every relevant prediction method the used budget for the given subband of the precinct to encode.

Supported by this information, the prediction mode selector421-425choses for every subband and every possible truncation point the best prediction method to use. Typically, this is done by selecting the prediction method with the smallest resulting bit budget for coding the GCLIs. Alternatively, a heuristic based on previous data can be used.

This information is then forwarded to the rate control430, which combines the available rate information and selects a truncation point for every subband. Encoding is then performed using the prediction method determined by the prediction mode selector421-425for the chosen truncation point.

In order to allow the decoder to properly decode the image, corresponding signaling information (660ofFIG. 1) is included in the bitstream, informing the decoder about the chosen prediction scheme for every subband. Given that this signaling information is only used on the granularity of the precinct subband, and a small number of bits is used for this signaling, the impact on the coding efficiency can be neglected.

FIG. 8cillustrates a further implementation of the mode determiner640. The mode determiner comprises a subband budget calculator corresponding to blocks410to414ofFIG. 4, a prediction mode selector for responding to blocks421-425ofFIG. 4, a budget combiner431and a truncation point selector432, where both the budget combiner431and the truncation point selector432together form the rate control illustrated at430inFIG. 4.

Particularly, the subband budget calculator410to414calculates a bit or, generally, a data budget for (1) every subband, (2) every truncation point (GTLI), and (3) every GCLI encoding mode. Thus, when there are, for example, two subbands, five different truncation points and three different GCLI encoding modes, then block410-414, i.e., the subband budget calculator calculates 30 different data budgets. This is illustrated by the input into blocks410-414consisting of subband IDs, GCLI identifications and encoding mode identifications.

Based on the result of the subband budget calculator, the prediction mode selector generates bit or, generally, data budgets for (1) every subband and for (2) every truncation point (GTLI), and, particularly, now for the selected GCLI encoding mode. Please note that the selected GCLI encoding mode might depend on the considered truncation point. The selected GCLI encoding mode per subband and per truncation point is output by the prediction mode selector via the line660that is also illustrated inFIG. 6. Thus, from the original 30 values generated by the subband budget calculator for the above example, there now remain ten bit/data budget values that are obtained using the best prediction mode or, generally, using the selected GCLI encoding mode.

These exemplary ten values are now received by the budget combiner431that calculates a complete bit/data budget for a precinct for every truncation point by combining the individual subband-wise budget values for every truncation point. Thus, for the example here, the budget combiner431finally outputs five different budget values for the five different possible truncation points. Then, among these five different budget values, the truncation point selector432selects a truncation point associated with a budget value that is in line with an allowed budget for the precinct.

Next, the truncation points selected for each subband can be refined by reducing the truncation for visually important subbands without exceeding the available bit budget. Thus, a truncation point for every subband of a precinct is obtained that is now used by the quantizer624ofFIG. 8dto quantize or truncate the bit-plane data for each coefficient exemplarily illustrated inFIG. 2a,where this data is stored in the raw data buffer as non-truncated data. Now, based on the selected truncation point for each subband/precinct and, exemplarily, for each color, truncated or quantized raw data or bit-plane data for each color are obtained. Depending on this situation, a truncation point can be calculated for each color individually or a single truncation point can be calculated for all colors or even two truncation points for a precinct can be calculated referring to, for example, two subbands within the precinct. Thus, when a precinct has, for example, ten subbands, then there would be five different truncation points for such a precinct.

FIG. 9illustrates a further implementation of the functionality illustrated with respect toFIG. 8d.The GTLI determiner illustrated inFIG. 8cby block431and432generates a GTLI per group of coefficients or a GTLI with an advantageously higher granularity such as for a set of coefficients (subband-wise), or a single GTLI per precinct. Then, based on this data, the coefficients are quantized by the quantizer624in order to output quantized coefficients.

FIG. 10illustrates an exemplary implementation of a precinct consisting of only two subbands, where a first set of coefficients of a first subband is illustrated at1001, and a second set of coefficients of a second subband is illustrated at1002, where the first set of coefficients has, for example, the groups1011and1012, and the second set of coefficients has the groups1013and1014.

Advantageously, four coefficients are used in one group, and a GCLI value is calculated for each group of four coefficients, and a GTLI is calculated for each set of coefficients, i.e., for a whole subband or a single GTLI value is calculated for each precinct, i.e., for all coefficients in both sets1001and1002. As already outlined before, a precinct generally comprises coefficient data of a first subband, coefficient data of a second subband, coefficient data for nthsubband, where all the subbands refer to the same spatial area of an image.

FIG. 11illustrates an exemplary representation of an encoded image signal. An encoded image signal comprises a decoding mode indication1101and1102for a first subband and a second subband generally indicated as “signaling information”. Furthermore, the image data illustrated inFIG. 11comprises encoded data comprising of encoded image data and encoded GCLI data illustrated at1103. Furthermore, the encoded image signal may comprise a header comprising header data indicated at1104inFIG. 11. Although the encoded image signal is illustrated as a serial stream inFIG. 11, the encoded image signal can be in any data format.

2.1 Signaling Method

Many different possibilities exist to signal the prediction method that has been used for every subband. For instance, raw bits can be used to signal the method per subband as the bandwidth is usually negligible compared to the volume of the actual coded GCLIs. Variable bits can be therefore used when the targeted compression ratio is more important and when the budget of the signaling starts to be more significant.

2.2 Reduction of Computation Effort

On the one hand, the method presented in the previous section improves the compression efficiency. On the other hand, it slightly increases the used hardware register storage space, since a separate register per subband needs to be provided for the budget computation. If all subbands were using the same prediction method, these registers could be possibly combined to a single register.

In order to compensate this problem, it is important to notice that the coding gain resulting by the previously described method is majorly originated in a small number of subbands. In other words, it is possible to decide in advance that a subset of the precinct subbands shown inFIG. 3use the same prediction method without scarifying significant coding efficiency, and only a small subset of the subbands can choose their prediction method independently of the other ones.

By these means, the increase in hardware effort can be limited while still leveraging the increased coding efficiency of the proposed method. At the same time, the signaling overhead for selecting the correct prediction method at the decoder can be reduced.

3 Fixed Prediction Scheme for Reduced Encoder Complexity

The method described in Section 1.4.2 deviated from the state of the art [2] in that not all subbands of the precinct need to use the same prediction method. By allowing a dynamic adaption of the prediction scheme to the image content, a better coding efficiency can be achieved.

Alternatively, the prediction scheme can be fixed for every subband, while still allowing different prediction schemes between the subbands of a precinct. By these means, the search space can be reduced.

FIG. 5shows a corresponding example. It assumes that coefficients belonging to a certain subband are predicted by the same prediction scheme. Coefficients belonging to different subbands can use different prediction schemes.

Using such a method provides the advantage of a reduced search space in the encoder, since for every subband, it is clear which prediction method to use, and it is hence not necessary to compute budgets for different prediction methods and then use the one with the smallest budget.

While using such a scheme does not deliver the coding performance of the method described in Section 1.4.2 or of the fully adaptive or partly adaptive encoding mode selection, it gets close to the state of the art method selecting between horizontal and vertical prediction on a precinct granularity, without the need to compute budgets for two prediction methods. In other words, it provides similar coding efficiency with reduced complexity.

FIG. 12illustrates a procedure that is in between the fixed prediction scheme ofFIG. 5or the completely adaptive prediction scheme ofFIG. 4. The procedure inFIG. 12is partly fixed and partly adaptive. In this situation, the encoded image signal only comprises signaling information for a subgroup of subbands such as only for the two lowest subbands101and102, where the decoding modes for the other subbands are determined using the predetermined rule, i.e., for the subbands103-109in line with, for example, the allocation illustrated inFIG. 5. Thus, the decoding mode determiner ofFIG. 7illustrated at block700is configured to extract1201signaling information for a subgroup from the encoded image signal and, then, determines1203the decoding mode for the subgroup of subbands of a precinct based on the extracted information. Furthermore, the decoding mode determiner700is configured to determine1205the decoding mode for other subbands not included in the subgroup processed by block1201using the predetermined rule. Thus, subsequent to the procedure of block1205, decoding mode determiner has the decoding modes for all subbands (sets of coefficients for a precinct).

In this “mixed” implementation inFIG. 12, the encoder procedure is so that the operation illustrated with respect toFIGS. 8band 8cis only performed for the subgroup of subbands, and the procedure illustrated in 8ais performed for the other subbands. Therefore, the encoder complexity is reduced with respect to the fully adaptive procedure, but, nevertheless, the adaptively is maintained at least for some subbands.

FIG. 13illustrates an implementation of an image data encoder with a schematic cooperation of certain global blocks.FIG. 14illustrates a corresponding illustration of the decoder that can cooperate with the encoder ofFIG. 13or with another encoder.

The color transform1300ofFIG. 13is a reversible integer-to-integer transform, used for lossless and lossy compressions, which de-correlates RGB color information. The forward reversible color transform RCT results in Y, U, V data or a similar color space. After this transformation, each color component can be processed independently from each other. In case of YCbCr image data, the color transform1300is bypassed because the color components are already de-correlated.

FIG. 14, block1430illustrates the inverse color transform in order to calculate Y, U, V data back into, for example, RGB color information as the output signal.

Block400inFIG. 13illustrates a discrete wavelet transform, and, correspondingly, block1420of the decoder illustrates at discrete inverse wavelet transform. The discrete wavelet transform (DWT) offers a spatial-frequency representation that ensures a good decorrelation of a signal. Typically, the output coefficients of a wavelet transform are coded in a two's complementary representation. For the purpose of entropy coding, these values are transformed to implement a sign and magnitude representation. This is illustrated by block1310inFIG. 13and the corresponding inverse operation is illustrated by block1410inFIG. 14. Positive data does not have to be modified as they are represented identically in both methods. Negative samples are to be inverted before being incremented by “one”.

The entropy coding performed by the procedures illustrated by blocks600,660,661,430,431,432,624in generally bases on block fixed length coding, on top of which some optimizations have been brought to ensure a better coding efficiency. The implementation leaves the output wavelet data untouched until packing the bit stream, and this, for example, illustrated with respect toFIG. 8dillustrating the raw data buffer622. Only a stream of indexes (GCLI) uses processing resources. Wavelet subband coefficients are grouped into subsets of four samples. Each subset is viewed in a bit-plane representation. For each subset, a greatest coded line index (GCLI) is found. It is the index of the most significant non-null bit-plane as illustrated inFIG. 2a.If there is at least one non-null bit-plane in the subset (GCLI greater than 0), the non-null bit-planes of the subset are copied as is in the output stream. Alternatively, they can be first processed for refining the quantization, before being copied in the output stream. A buffer stores all raw data before packing the output stream, allowing for the rate allocation to decide which part of the data are relevant for the output stream. GCLI indexes are further compressed and packed upstream of the raw data. A vertical prediction is performed between two subband lines of GCLIs. The result is the difference between the GCLI value and the GCLI value of the same subset of coefficients in the previously coded line.

Predicted predictive values are afterwards coded following a unary coding method illustrated inFIG. 13close to the entropy coder block661. The table shows a simple signed unary variable length code for GCLI encoding. Such an unary code associates a specific variable length code to each symbol, possibly dependent on some context information. Hence, while the unary code inFIG. 13represents one possible solution, alternative unary code schemes are possible as well, for instance by replacing the 0s by 1s and vice versa. One such alternative is described in [7] and alternatively encodes positive and negative prediction residuals. GCLIs are also predicted horizontally. The symbol coded is then the difference between the GCLI value and the value of the GCLI that was previously coded belonging to the same line and the same wavelet subband.

Other prediction modes are possible as well in addition to or instead of the raw mode. Data and GCLI predicted values are truncated by the rate allocation mechanism. The grouping of coefficients results in a trade-off between efficiency of the compression scheme and the complexity of the system. The number of coefficients in each subset has been chosen before because it provides the best trade-off between compression efficiency and hardware complexity for high throughput.

Once they are coded, the output of every coding unit is packed together. An exemplary procedure is illustrated inFIG. 15. Particularly,FIG. 15illustrates a GTLI buffer1501, a GCLI buffer1502, a horizontal prediction mode calculator1503, a vertical prediction mode calculator1504and a raw mode processor1505. Furthermore,FIG. 15illustrates an (unary) coder implementing, for example, the code illustrated inFIG. 13close to the entropy coder661andFIG. 15additionally illustrates a multiplexor/data packer1506for generating the coded GCLI data. Particularly, block1503calculates the horizontal prediction mode in order to generate a Δ value based on a “current” GCLI value and based on a “past” GCLI value from the buffer1502. Correspondingly, block1504also calculates a Δ value based on the “current” GCLI value received as an input and based on a “past” GCLI value received from the GCLI buffer1502. The terms “current” and “past” does not refer to time but to the position within a subband for a certain group of coefficients. Then, the corresponding Δ value is (unary) coded. Naturally, for a certain subband, either the result of block1503or the result of block1504or the result of block1505is input into the coded GCLI data. It is to be noted that the budget allocated to the GCLI is bonded by the raw coding meaning that there are at most four bits per GCLI in the implementation. Furthermore, the data that are generated by the unary code is coming in a continuous flow at the decoder-side, and it is, therefore, possible to pre-calculate state variables. Thus, this allows breaking feedback loops thanks to stop bits of the unary code.

During the rate allocation and the GCLI packing process, bit-plane data is stored in a buffer, before being packed in the output stream. Due to the fact that this buffer is an important resources cost of the codec system, it is of advantage to design the buffer as small as possible, and it has been found that a buffer as small as storing only up to ten lines may be sufficient.

Subsequently, the rate allocation is discussed in more detail. Particularly,FIG. 16illustrates the cooperation between the entropy encoder on the one hand and the rate allocation on the other, where the rate allocation has a data budget block1621, a GCLI budget block1622, a budget allocation unit1610and the rate allocation core as discussed before with respect to blocks431,432inFIG. 8c.Furthermore,FIG. 16also illustrates the usage of headers1600that are also packetized by the packetizer680into the output data steam as has already been discussed before with respect to header1104inFIG. 11.

The rate allocation works precinct per precinct. A precinct groups frequency contents of different subbands forming a same spatial area. Such a spatial area has, for example, a two line height and has the same width as the one of the image. It contains, for the three components, six subbands containing the results of five horizontal decompositions of the low vertical frequency and two subbands containing the result of a single horizontal decomposition of the high vertical frequency.

Rate allocation quantizes precinct data by trimming least significant bit-planes of determined subbands until the remaining bit-planes can fit in the precinct bit-plane's budget. This trimming strategy is applied iteratively, gradually trimming more and more bit-planes in each subband. Based on its use case, one can apply an appropriate “trimming strategy” the trimming strategy determines the importance of subbands relative to each other. The rate allocation chooses to trim more bit-planes in less important subbands than in more important ones. The rate allocation computes the precinct budget for a defined truncation scenario. If the budget does not fit in precinct budget, it computes the budget for a new truncation scenario, removing one more bit-plane in all subbands. Once the precinct size fits in the precinct budget, it computes a possible refinement, re-adding one bit-plane subband per subband in the order defined by a certain priority rule associating different priorities to different subbands until the budget is again exceeded. This results in the final truncation levels for each subband.

The rate allocation quantizes precinct data so that encoded precinct size does not exceed the rate budget. The average precinct budget is in a targeted code stream size divided by the number of image precincts. Advantageously, a rate allocation strategy average is the budget on a couple of precincts to smooth the truncation levels along the image. An encoded coded precinct contains three parts, i.e., the header, the encoded GCLIs and the raw bit-plane's data. The header has a defined size that cannot be adjusted. The rate allocation can reduce the size of raw bit-plane's data part and encoded GCLI part by increasing quantization. The raw bit-plane's budget is the part of the precinct budget available for storing the raw bit-plane's data. A minimum code stream size is able to produce the size of the headers and the encoded GCLIs (raw bit-plane's data size equal to 0).

The calculation of the raw bit-plane data budget for a defined scenario refinement pair uses the GCLIs of the samples which are small four bit numbers. Furthermore, using one GCLI for a group of four samples reduces the amount of numbers to process for the budget calculation by four. Once the size of each group of the precinct is calculated, a sum gives the total data size at a certain iteration. Regarding the GCLIs data budget, there are multiple ways to store the GCLI and the rate allocation will typically compute the budgets for all the methods and choose the most appropriate. As for the data, the budget of the encoded GCLI can be computed based on the output of the (unary) coder661illustrated, for example, inFIG. 15. In the raw GCLI case, the budget is the number of groups multiplied by four bits when having up to 16 data bits. Once the size of each coded GCLI of the precinct is calculated, a sum gives the total GCLI's size at a certain iteration.

The rate allocation block inFIG. 16receives, as an input, the stream of GCLI (data) values, and the block outputs the GTLI information for the packetizer. The data budget block1621and the GCLI budget block1622compute the used budget to store the data/GCLI for each possible GTLI (from 0 to 15). Advantageously, the quantizer such as the GTLI trimmer624or the quantizer624inFIG. 8dperforms an efficient center-rounding quantization. To this end, a certain quantization step is calculated and a following transform is performed. At the decoder side, a reverse transform consists of applying the quantization step on the data in a certain reverse transform operation. However, other quantizers apart from an efficient center-rounding procedure can be used as well. Then, once the rate allocation block has determined the number of bit-planes to trim in each subband of a precinct, the raw data is read from the raw data buffer622ofFIG. 8d,quantized and fed to the output stream packet to be packed in the output stream.

On the decoder-side, the GCLI data is decoded prior to data unpacking. This allows applying almost the same process in the reverse way.

It is to be noted that attached claims related to the apparatus for encoding also apply for the apparatus for decoding where appropriate.

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

A further embodiment of the inventive method is, therefore, a data stream or a sequence of signals representing the computer program for performing one of the methods described herein. The data stream or the sequence of signals may for example be configured to be transferred via a data communication connection, for example via the Internet. A further embodiment comprises a processing means, for example a computer, or a programmable logic device, configured to or adapted to perform one of the methods described herein.