Patent Description:
As the size of raw images tends to increase continuously over the last years, it is necessary to provide more efficient data compression techniques in order to allow the storage and transmission of these images. For example, it is today commonplace to download and view images on mobile equipment where data compression is relevant to save bandwidth and local storage.

Compression of images is known in the field, where the compression can be either lossy, e.g., in the case of JPEG images or can be lossless, e.g., for GIF pictures. Compression of an image or a video sequence typically consists of a frequency transform followed by quantization and coding.

Compression of an image or a video sequence typically consists of a frequency transform, followed by quantization and entropy coding. However, transform coding does not perform well for some image content, especially for screen content. Such content typically features only few distinct colors and sharp edges between differently colored regions, e. black text on white background. Such content can be efficiently compressed using a list of the distinct colors, called a palette, and indices into this palette per pixel.

Palette coding is a well-known technique for image coding. An early use of palettes was indexed image formats like the graphics interchange format, better known as GIF format. The GIF format uses one palette for the entire image with up to <NUM> distinct colors. The palette indexes can be compressed using run length coding.

The HEVC standard, also known as H. <NUM>, introduces a palette mode with the screen coding extensions. In the HEVC palette mode a palette is transmitted per coding unit, CU. The palette entries for a CU can be predicted from neighboring CUs. Palette indices are run length coded and multiple scan patterns are possible. Escape coding can be used to encode single pixels that are not well represented by the palette entries. Finally all syntax elements are entropy coded using context-adaptive binary arithmetic coding, CABAC.

<CIT>, for example, describes video coding using a palette mode. In accordance with this mode, a block of a picture is coded by establishing a palette of colors, i.e. a color table, for the respective block. Each entry comprises a color in the color domain used. The encoder encodes such a block in palette mode by associating each pixel with one of the entries in the palette. In particular, each pixel is associated with that palette entry which is nearest to the pixel's color. The palette is coded and inserted into the data stream. For a palette construction on the encoder side, a certain scanning order is used. According to this document, for each currently traversed pixel, the color of the respective pixel is sequentially compared with the palette colors according to a preliminary order among the currently established palette colors. As soon as the color difference falls below a certain threshold TH, a pixel count (counter) for the respective palette color is increased. If none of the currently established palette colors are mirrored to the color of the currently traversed pixel, the current set of palette colors is increased by one palette color entry, namely the color of the currently traversed pixel. After having traversed all pixels of the current block, a palette reordering takes place. This document suggests improving this palette construction by finding that palette color among the currently established palette colors instead of some first one meeting a certain threshold criterion, and updating a certain palette color entry whose palette colors found to be the best for a currently traversed pixel, by computing a color average among all pixels' colors associated with that palette color entry so far.

Another document (<NPL>) is also concerned with a palette mode of a video codec and suggests with respect to color table derivation, first collecting the pixel histogram according to the frequency of the occurrence in descending order. Then, certain entries in this histogram are grouped together, whereinafter a certain number of most frequently visited group colors are selected for forming the palette. Reordering is performed in order to yield a palette with frequency descending.

Nevertheless, the known techniques are complex, having certain memory and CPU requirements what makes it difficult to implement these for mobile devices which in most cases have limited resources, e.g. regarding battery or CPU power.

It is hence the object of the present invention to provide a technique for image coding with increased efficiency while having a low complexity.

This object is solved by the subject-matter of the independent claims.

It is a basic aspect of the present application how to efficiently create a suitable palette for low complexity image and video coding. A combination of the palette coding with transform coding is feasible.

Basis for the claimed invention can be found particularly in the accompanying drawing <NUM> in combination with the associated description restricted to the rank order adaptation shown in drawing <NUM>.

The references in the claims refer to <FIG> (the reference <NUM> refers to the encoder <NUM>, the reference <NUM> refers to the scan order <NUM>, the reference <NUM> refers to the color palette <NUM> and the reference <NUM> refers to the palette color values <NUM>).

Low complexity image video coding is the challenge of achieving good compression efficiency while limiting the computational effort. Typically, targeted compression ratios range from <NUM>:<NUM> to <NUM>:<NUM>. Key requirements for low complexity image video coding are simple implementation, e.g. on FPGA, SW and GPU as well as high throughput capability.

Compression of image data can either be lossy or lossless. In the case of lossless data compression, also referred as "byte packing", the compression is performed such that an exact copy of the input data is obtained when decompressing the compressed data. This property is advantageous in particular when compressing computer programs or databases wherein exact replication of the original data is necessary. Lossy compression, which in many cases has a better compression ratio than the lossless compression has the drawback that the original information cannot be exactly obtained upon decompression, in other words, there is a loss of information during this kind of compression.

<FIG> shows a block diagram of an encoder <NUM> according to an exemplary embodiment of the present invention, the encoder uses a palette mode in combination with a transform based block coder.

The encoder <NUM> comprises a block former module <NUM> which partitions an input image into transform blocks for further processing. These blocks are output both to color transformation, CT, module <NUM> and workgroup, WG, palette builder module <NUM>.

The color transformation, CT, module <NUM> may transform the color values of the pixels of the input image block according to a color scheme. In embodiments, the CT module <NUM> may form a color space transformation between, for instance, RGB and YCC or vice versa or the like. The CT module <NUM> outputs the transformed image block to the adaptive block frequency transformation, FT, module <NUM>.

The adaptive block FT module <NUM> may transform the color transformed image block into the frequency domain, helping to facilitate compression, and outputs the transformed image block such as in form of a transform coefficient block to the pre-quantization transformation, Pre-QT, module <NUM>.

The Pre-QT module <NUM> quantizes the values of the color and frequency transformed image block, i.e. the transform coefficients. The result is output to the entropy pre-processing module <NUM>.

The entropy pre-processing module <NUM> may translate the data received from the pre-QT module <NUM> into symbols that may facilitate the processing of the information by the workgroup entropy coder <NUM>. The pre-processing includes, for instance, a binarization in order to map inbound syntax elements including, for instance, the transform coefficients, and, optionally, a quantization parameter describing the pre-quantization onto binary symbols so as to be suitable for a binary arithmetic coding, for instance, which is used, for instance, in the entropy coder <NUM>. The output, i.e. the entropy coded bitstream, is sent to the rate control module <NUM> and is also buffered in the rate control buffer module <NUM>.

The rate control module <NUM> may control the rate by sending control signals to both the packetizer module <NUM> and also to a workgroup entropy coder module <NUM>.

The workgroup entropy encoder module <NUM> receives its input from the rate control buffer module <NUM> and performs entropy coding, like an arithmetic coding, on the received data. The entropy coded data is output to packetizer module <NUM>.

The packetizer module <NUM> receives a further input from the workgroup palette encoder <NUM> which is described further below.

The encoding technique described above and performed by color transformation, CT, module <NUM>, adaptive block frequency transformation, FT, module <NUM>, pre-quantization transformation, Pre-QT, module <NUM>, entropy pre-processing module <NUM>, rate control buffer module <NUM> and workgroup entropy encoder module <NUM> is referred to as 'transform mode' coding, as opposed to 'palette mode' coding described in the following. In other words, block former <NUM> subjects the blocks of the picture to be coded to two types of coding modes among which, finally, one is chosen according to some criterion such as rate/distortion criterion, and the selection is signaled in the data stream. Further details are set out below. The following paragraphs concentrate on the other coding mode. Later on, an embodiment is described based on which it gets clear that the latter coding mode may be, according to an alternative embodiment, the only coding mode or a coding mode offered along with a different coding mode other than described above as the transform mode.

As mentioned above, the transform block formed by the block former module <NUM> is also received by the workgroup, WG, palette builder module <NUM>. The WG palette builder module <NUM> may create a color palette according to an embodiment of the present invention. The generation of the palette is described in further detail below. The WG palette builder module <NUM> outputs the created palette as well as the received transform block to workgroup palette encoder module <NUM>. The WG palette encoder module <NUM> encodes the transform block of the image pixel-wise using the palette created by the WG palette builder module <NUM> and outputs the result, together with information about the palette used, to the packetizer module <NUM>.

Finally, the packetizer module <NUM> may packetize the inputs received from the WG entropy encoder module <NUM> or the WG palette encoder module <NUM> and outputs it to smoothing buffer module <NUM>. The smoothing buffer module <NUM> may buffer the received compressed transform blocks and may output these continuously at a constant data rate, thereby smoothing the output bitstream.

Even though the encoder has been decribed as comprising constituent modules like color transformation, CT, module <NUM>, adaptive block frequency transformation, FT, module <NUM>, pre-quantization transformation, Pre-QT, module <NUM> and entropy pre-processing module <NUM>, it is clear to the person skilled in the field of image compression that some or all of these modules are optional and that embodiments of the invention may be performed without or a subset of these modules.

<FIG> shows in a conceptual drawing how the image is subdivided into workgroups and then how the workgroups are subdivided into transform blocks according to an embodiment. The image <NUM> may be subdivided into horizontal 'stripes', in this example each stripe comprises four pixels in the vertical dimension. Each of the stripes may be subdivided into workgroups <NUM>, wherein in this example each workgroup comprises <NUM> pixels in horizontal direction and <NUM> pixels in vertical direction. Each workgroup is further subdivided into transform blocks <NUM>, which in this case, comprises <NUM> x <NUM> pixels. Such a transform block may be a predetermined region of the pixel array being the representation of the picture to be encoded.

Even though a block has the size of <NUM> x <NUM> pixels in this example, it is possible, in other embodiments, that the block sizes are <NUM> x <NUM>, <NUM> x <NUM>, or <NUM> x <NUM>. Even though it is shown that a workgroup comprises four blocks, it is possible that also eight or sixteen blocks form one workgroup. In an even more general case, there is no need that the block size or workgroup size is restricted to powers of two, i.e. the block size can be m x n pixels and a workgroup can comprise k blocks with k, n and m being any natural number.

According to an embodiment, the encoding mode, a palette mode or a transform coding mode, is selected per workgroup, i.e. an entire workgroup is coded either in the palette mode or in the transform coding mode.

The palette mode encoding is performed in two steps, described in detail below. First a palette is generated based on the colors of the pixels in a workgroup. In a second step, the palette index for each pixel in a workgroup is determined and the palette entries and indices are written the byte stream, if the palette mode is selected.

When the transform blocks of a workgroup are received, the palette generation process starts with an empty palette. The color of the first pixel in a workgroup is then added as the first palette entry. Then the color values of all pixels of a workgroup are compared to the already existing palette entries, the comparison is performed in the order from the first palette entry to the last. If the difference of the color value of a pixel to a color value in the palette is less than a threshold then the color value of this pixel is deemed as already present in the palette and the comparison to the palette entries is stopped for this pixel. If the matching palette entry is not the first palette entry, this palette entry is moved one position to the front of the palette. If the color value of a pixel is not present in the palette, then this color value is appended to the palette as long as the maximum palette size is not exceeded.

The measure for the difference between the color value of a pixel and a color value in the palette is computed as a weighted sum of the absolute differences of the color components. Usually the green color component is weighted most and the red and blue components are weighted less.

The threshold used to determine if a color value is already present in the palette may not be fixed but may be dependent on the position in the palette. In an embodiment, the threshold is smaller at the front of the list and larger at the end. This adaptive threshold, in conjunction with the process of moving palette entries to the front of the palette if a color value of a pixel matches this palette entry, has the effect that pixel color values that occur frequently in a workgroup are represented with a higher precision than color values that occur less frequently. This optimizes the palette both for a small number of entries and for low distortion.

The last two paragraphs can be implemented by the following formula: <MAT>.

Where dr, dg and db are the absolute differences of the red, green and blue components of the color values of the pixel and the palette entry and i is the index of the palette entry in the palette with i=<NUM> being the frontmost palette entry. As mentioned before, the green component is weighted most while red and blue are weighted less, and it is clear that the individual weighing factors are merely examples.

The aspect that a palette entry for a color that is already present in the palette is moved in direction to the front of the palette, e.g. by one position, each time the color occurs, and appending colors to the end of the palette when they occur for the first time provides a ranking concept for color entries. This ranking represents the frequency of occurrence of a certain color. An advantage is that each time the palette is scanned through starting at the beginning of the palette, this scanning will first come across color values that were more frequently found and the likelihood that the color of a new pixel is one of the first entries is expected to be larger and the scanning can then stop earlier, thereby saving time. In embodiments, in oder to optimize throughput, a comparison to all palette entries may be performed in parallel; this may be done by an implementation in hardware or software.

As neighboring pixels very likely have similar color values it is beneficial to perform the palette generation not in raster scan order but in another scan pattern to populate the palette with different color values early in the palette generation process. A suitable scan pattern is shown in <FIG>.

<FIG> gives examples for two possible scan patterns for palette generation. The two scan patterns are rather similar; the difference between these two examples is that the position of the <NUM>th and <NUM>th scanning position are exchanged. The scanning is performed in the order starting with the pixel at position <NUM>, then pixel at position <NUM>, position <NUM> and so on, ending with position <NUM>. These two scan patterns are mere examples, and it is clear that any possible scan order can be applied, some orders being more advantageous than others.

As mentioned before, the encoder may decide which coding mode, either the palette mode or the transform coding mode, is to be applied to the presently processed workgroup. The coding mode is decided on the following conditions:.

The above mentioned decision criteria are optimized for low implementation complexity. If higher implementation complexity is acceptable or intended, more complex decision criteria may be employed, e. full rate distortion optimization, RDO, or a criterion based on just noticeable differences, JND.

The creation of the palette to be used as well as the decision which kind of coding will be applied have been described before, in the following details on the coding process are discussed.

For coding of the transform blocks of the workgroup in palette mode, the following syntax elements are employed:.

Simple fixed length coding may be used for the palette indices because this yields the lowest implementation complexity, especially for hardware implementations. If higher implementation complexity is acceptable, variable length coding for the palette indices may be easily applied as the palette generation process already orders the palette entries according to the frequency of occurrence of the color values.

Summarizing the above, according to a first aspect of the present application, a pixel array encoder for encoding a pixel array by palette coding is made more efficient in terms of a less complex implementation by populating the color palette during traversing the pixels of a predetermined region of the pixel array, associating a currently traversed pixel with a palette color value of highest rank among one or more of the sequence of palette color values currently contained in the color palette and increasing a rank of the palette color value thus associated with the currently traversed pixel by one. By this measure, the adaptation of the rank order among the palette color values within their color palette is, in a manner corresponding to very low complexity, adapted to substantially mirror a significance of the palette color values contained in the color palette in terms of "representative characteristic", i.e. in terms of the capability of the respective palette color value to efficiently represent the color values of the pixels within the predetermined region. A capability to efficiently represent color values of pixels within the predetermined region means, for instance, that the respective palette color value is similar to, i.e. representative of, a high number of color values of pixels within the predetermined region. The higher this number is, the higher its capability of efficiently representing is. No count of associations with a certain palette color value within the color palette has to be monitored during traversing the pixels of the predetermined region. Rather, it suffices to adapt the rank order simply by changing the palette color value associated with a currently traversed pixel with the rank of a palette color value of immediately higher rank.

Thus, the first aspect concerns, for instance, an encoder like encoder <NUM> depicted in <FIG> which encodes a pixel array <NUM> by palette coding. The encoder <NUM> traverses pixels <NUM> of the pixel array <NUM> within a predetermined region <NUM> of the pixel array along a scan order <NUM> while, during the traversal, populating an internally logged color palette <NUM> with representative color values of pixels traversed, adapting a rank order among palette color values, PCV, <NUM> stored in color palette <NUM> and associating the pixels <NUM> within region <NUM> to palette color values <NUM> in color palette <NUM>.

The encoder of <FIG> traverses pixels <NUM> within the predetermined region <NUM> and checks, as illustrated in <FIG>, whether a currently traversed pixel's color value does not fulfill a predetermined similarity criterion with respect to any of the sequence of palette color values <NUM> currently contained in the color palette <NUM> or if the currently traversed pixel's color value fulfills a predetermined similarity criterion with respect to at least one of the sequence of palette color values <NUM>. For example, <FIG> illustrates a predetermined color space, here exemplarily spanned by three axes which may, for instance, be red, green and blue. The color value of a currently traversed pixel is illustrated by a cross <NUM>. The palette color values are depicted by dots and indicated using PCV. With respect to a certain palette color value, the predetermined similarity criterion is fulfilled, for instance, if a distance <NUM> between the currently traversed pixel's color value <NUM> and the respective palette color value succeeds a predetermined threshold which, as illustrated in <FIG>, might be thought of spanning a certain region <NUM> surrounding the respective palette color value. The distance <NUM> is, for instance, measured using the left hand part of the inequality discussed above, i.e. <NUM>·dr + <NUM>·dg + <NUM>·db. The respective weight factors of <NUM>, <NUM> and <NUM> are merely examples; it is evident that any other choice of weights may be appropriate. The threshold may be, but according to the present application does not necessarily have to be, dependent on the rank of the respective palette color value within the color palette <NUM>. In particular, the palette color value <NUM> currently contained in color palette <NUM> form a list or sequence ordering the palette color values <NUM> along a rank order <NUM>. If a certain currently traversed pixel value does not fulfill a predetermined similarity criterion with respect to any of the palette color values <NUM> currently stored in the color palette <NUM>, same is appended at the end of the list of palette color values <NUM>, thus then corresponding to the lowest rank of the color palette <NUM>. The appending may be performed conditionally only then if a maximum number of palette color values <NUM> within color palette <NUM> has not yet been reached.

If a currently traversed pixel's color value <NUM> fulfills the predetermined similarity criterion with respect to a certain palette color value <NUM>, then encoder <NUM> associates this currently traversed pixel with this palette color value. If there are more palette color values in the color palette <NUM> with respect to which the predetermined similarity criterion is fulfilled by the currently traversed pixel's color value, then encoder <NUM> associates the currently traversed pixel with a color value of highest rank among these palette color values.

The adaptation of the rank order <NUM> is performed as depicted in <FIG>. The left-hand side of <FIG> shows the content of color palette <NUM> at the time of encountering a certain pixel <NUM> within region <NUM>. As shown, the color palette <NUM> contains at that time N palette color values PCV i, with i indicating the rank. At the right-hand side, <FIG> illustrates the case that the currently traversed pixel has been determined to be similar to palette color value PCV N-<NUM>. The currently traversed pixel's color value might have been similar to palette color values <NUM> of lower rank <NUM>, but encoder <NUM> may not even have checked this circumstance. Rather, encoder <NUM> has checked that the currently traversed pixel's color value is not similar to any palette color value <NUM> of higher rank, i.e. here neither to PCV N-<NUM> and PCV N. As a result, encoder <NUM> increases the rank of palette color value N-<NUM> so that the latter palette color value becomes palette color value at rank N-<NUM>, while the palette color value formerly positioned at rank N-<NUM> now becomes palette color value at rank N-<NUM>. Index i indexes the palette color values in a direction contrary to rank order <NUM>, i.e. from the palette color value of highest rank to palette color value to lowest rank, i.e. i = <NUM> is associated to PCV N.

Finally, the encoder encodes into a data stream <NUM> color palette information on the color palette <NUM> manifesting itself at the end of traversing the pixels <NUM> within region <NUM> as well as information indicating for each pixel <NUM> within region <NUM> as to which palette color value the respective pixel has been associated with. In this regard, please note that each pixel which had been associated with palette color value N-<NUM> before encountering the pixel discussed with respect to <FIG>, remain associated with this palette color value even though same changes its rank within the color palette <NUM> due to the adaptation of the rank order responsive to the currently traversed pixel.

In accordance with a second aspect of the present application, the encoder <NUM> of <FIG> does not necessarily perform the adaptation of the rank order <NUM> in the manner explained with respect to <FIG>. Rather, alternatively, the encoder in accordance with the second aspect the present application may, for instance, log for each palette color value <NUM> within color palette <NUM> the number of times a certain pixel's color value has been associated with the respective palette color value with adapting the rank order to correspond to the count of associated pixels: the higher the count of associated pixels is for a certain palette color value, the higher its rank in the color palette <NUM> is.

However, in accordance with a second aspect of the present application, the encoder <NUM> is configured such that the aforementioned threshold defining the similarity criterion depends on the rank of the palette color values <NUM> within color palette <NUM>. That is, whether a currently traversed pixel's color value <NUM> fulfills the similarity criterion with respect to a certain palette color value <NUM> depends on the rank of the respective palette color value within color palette: the threshold is lower or smaller the higher the rank of the respective color value is. An example has been given on the right-hand side of the inequality shown above. Here, i indexes the palette color values in a direction contrary to rank order <NUM>, i.e. from the palette color value of highest rank to palette color value to lowest rank, i.e. i = <NUM> is associated to PCV N.

By this measure, the second aspect achieves an efficient way of palette coding. As long as the number of palette color values within the color palette is relatively low, the representative palette color values within the color palette are supposed to relatively closely correspond to the color values of the pixels which are associated with these palette color values. However, as soon as the number of palette color values increases, the color palette might be in danger of running into to a situation where the color palette gets full, i.e. the maximum number of palette color values is reached, or, if such a maximum number does not exist, that the maximum number gets unreasonably large. Accordingly, a kind of "break" is implemented by relaxing the similarity criterion for palette color values of lower rank, i.e. ones having been appended but having been associated with previous pixels merely seldomly.

In accordance with the third aspect of the present application, it is optional for encoder <NUM> to perform the rank order adaptation according to <FIG> and/or to use the just-outlined rank-dependent similarity criterion. However, in accordance with the third aspect of the present application, the encoder <NUM> uses a scan order <NUM> among pixels <NUM> according to which the pixels are sequentialized in a manner such that more than a quarter, i.e. <NUM>%, of in scan order immediately consecutive pairs of pixels have pixel borders which are distant from one another by at least an inner or enclosed area of another pixel. For example, see the pair of pixels <NUM> and <NUM> in <FIG>. Their pixel borders have a distance which may be determined by the smallest distance between their borders, i.e. the one connecting the bottom right corner of pixel <NUM> with the top left corner of pixel <NUM>. The line connecting these pixels traverses to other pixels, namely pixels <NUM> and <NUM>. Contrary thereto, the immediately consecutively scanned pixels <NUM> and <NUM> have borders which abut each other, namely at one corner thereof. However, all in all, there are more than <NUM>% of immediately consecutive pixels along scan order, for which their pixel borders do not abut each other, namely pairs <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>. The overall number of immediately consecutive pairs is <NUM>.

It should have become clear from the above description of embodiments in the current section that the encoder <NUM> may or may not be operative to code other regions of image <NUM> by another coding mode, such as a transform coding mode according to which the respective region is transformed into one or more transform blocks with coding the transform coefficients into data stream <NUM>. The regions may be composed of one or more of pixel blocks which are individually transformed into a transform block.

The following should be noted with respect to the above description. The above description of embodiments assumed that palette generation and coding of the pixels by way associating them to the palette is performed in one single step. However, preferably, the process is performed twice: in a first pass, the palette is built. Then, the pixel in the predetermined region, e.g. workgroup, is scanned or traversed again. In the second scan, a different rater scan order might be used, i.e. a scan order other than the one used in the first pass concerning palette building. The color palette as determined in the first pass might remain fixed during the second pass where the pixels are associated to the palette color values. In the second pass, the threshold may be defined differently and each pixel might be associated with highest-rank candidate among the sufficiently similar palette color values. For example, the threshold might be fixed or independent from the rank of the respective palette color value. Alternatively, the most similar palette color value is associated with a respect pixel irrespective of the rank order.

The latter aspect represents a fourth aspect of the present application. Here, the encoder merely optionally also inherits any of the previously described three aspects.

According to this fourth aspect, two different scan orders are used, a first scan order that is used to build the color palette and a second scan order to apply the build palette to the individual pixels of the transform block.

The first scan order may be chosen according to criteria that can lead to a better palette, i.e. the first scan order provides a sequence for the scanning that ensures that the average spatial distance of consecutively scanned pixels is as large as possible, or at least above a certain value. As described before, it is advantageous during palette building that the spatial distance of pixels scanned consecutively is large because two neighboring pixels are likely to have the same or very similar color what may lead to a 'distorted' palette, i.e. the palette may overemphasize a certain color. The second scan order may differ from the first scan order in that the spatial distance of consecutively scanned pixels is not taken into consideration, but that the scan order is computationally most effective, e.g. time or memory saving. Such a scan order may be a raster scan order where the pixels are scanned in ascending sequence, e.g. in the case of a 4x4 transform block in the sequence <NUM>, <NUM>, <NUM>. When choosing a color for a certain pixel from the palette, the closest color value, i.e. the color with the smallest distance computed according to the formula defined further above, may be chosen, but also the rank of the color value may be considered in the sense that the distance of the color of a pixel to a color of the color palette may not be the pure distance, e.g. according to the formula <NUM>·dr + <NUM>·dg + <NUM>·db given further above, but the rank of the color value may be considered and may be, for example, multiplied with a weight factor and subtracted from the calculated distance what can lead to a preference of colors with high rank.

According to this embodiment, a first scan order is used for traversing pixels of a predetermined region, e.g. the transform block of the current workgroup. During traversing, the color of a currently traversed pixel is compared to palette color values currently contained in the color palette, and if the currently traversed pixel's color value does not fulfill a predetermined similarity criterion, e.g. the above mentioned distance, with respect to any of the palette color values currently contained in the color palette, the currently traversed pixel's color value is appended to the sequence of palette color values (<NUM>), e.g. at the end. Appending the color value to the end corresponds to a lowest rank of the color palette. Color palette information on the color palette is coded into a data stream after traversal of the pixels along the first scan order. Then a second scan order different from the first scan orders is used to traverse the pixels of the predetermined region again, thereby associating each pixel with a corresponding color value of the sequence of palette color values contained in the color palette and coding information associating each pixel with the palette color value of the color palette (<NUM>) the respective pixel is associated with into the data stream.

The apparatus or systern may, for example, comprise a file server for transferring the computer program to the receiver.

Claim 1:
Encoder (<NUM>) configured to encode a pixel array by palette coding, configured to traverse pixels of a predetermined region of the pixel array along a scan order (<NUM>) with if the currently traversed pixel's color value does not fulfill a predetermined similarity criterion with respect to any of a sequence of palette color values (<NUM>) currently contained in the color palette (<NUM>),
update the color palette (<NUM>) by appending the currently traversed pixel's color value to an end of the sequence of palette color values (<NUM>), corresponding to a lowest rank of the color palette (<NUM>), and
if the currently traversed pixel's color value fulfills the predetermined similarity criterion with respect to at least one of the sequence of palette color values (<NUM>) currently contained in the color palette (<NUM>),
increase a rank of the palette color value of highest rank among the at least one of the sequence of palette color values (<NUM>) currently contained in the color palette (<NUM>) by one to assume an increased rank, while the palette color value formerly positioned at the increased rank becomes palette color value at the increased rank minus one; and
code into a data stream
a color palette information on the color palette (<NUM>);
an information associating each pixel with a respective palette color value of the color palette (<NUM>);
wherein the currently traversed pixel's color value fulfills the predetermined similarity criterion with respect to a predetermined palette color value among the sequence of palette color values (<NUM>) currently contained in the color palette (<NUM>) if a difference between the currently traversed pixel's color value and predetermined palette color is less than a predetermined threshold.