Delta-palettization

[mis...@google.com]

During my summer internship in Google's compression team, I tried out a new image compression approach. Traditionally, lossless image compression, such as PNG or WebP lossless, have used either a truecolor (ARGB) or palettized (256 unique colors) as the main methods for storing the data. Often spatial predictors are used for the truecolor bytes, and less often for the palette indices.

What we wanted to try is something new: to approximate the prediction residuals by 256 discretized values. This is possible in the WebP lossless format without decoder changes: we can reverse the order of palettization and spatial prediction in the stream. The prediction residual is similar to a gradient of the image, so, when we discretize the gradient, we can have unbounded error. To mitigate this we used a novel error diffusion process that propagates the error to neighboring pixels that are not yet quantized. For further improvements, we implemented a back-error-propagation method, that moves some of the anticipated error from non-quantized pixels into the pixels being currently quantized. To try out something new like this, I needed to simplify things, and this version of delta-palettization does not support the alpha channel; all pixels have to have an alpha of 255. (While alpha adds a new dimension in the discretization space, we believe that in most cases it would be possible to handle it, too -- just not implemented yet.)

The palette of deltas is relatively sensitive. Small changes there can lead to large changes in compression density. Adding a few entries resulted in a 10 % size increase in one experiment.

We are not yet completely sure of the applicability of this compression mode. It seems to produce different kinds of artefacts from other methods. The quality seems superior to the lossy mode of WebP on photographic images: there is no YUV420 mode to flatten the colors. For photographs, the decoding speed of delta-palettization is about 2x faster than that of lossy WebP or non-palettized lossless WebP. Sometimes we see artefacts. It is likely that we can remove most of them by further algorithmic improvements of this method. Nonetheless, it is a new interesting compression mode. It is fast to decode, and the delta-palettized images are smaller than those compressed with lossless coding. Typically we see a size reduction of 60 % (2.5x faster to download) for photographic images. This is somewhat similar to lossy coding with quality 100. 

I'd like to thank Dr. Jyrki Alakuijala for guidance on this project, and Dr. Pascal Massimino for the code reviews.

Please see example images here. Every .png is the lossless RGB source, and the respective .webp delta-palettized.

https://drive.google.com/folderview?id=0B7Kdi6fw_WBBMjQ2OFRlNWVfNEU&usp=sharing

We will soon push a version of WebP that will contain the delta-palettization in its experimental mode.

--

Mislav

[tesla...@gmail.com]

I am not sure I understand correctly, but is this not a bit similar to the HAM encoding used by the Amiga range of computers in the 80s and 90s? The details are different, but the basic principle was to use a (hopefully) optimal palette and encode differences from the desired image as deltas from the palette (actually from the pixel to the left).

I think the original HAM encoding intended to use HSV colour but RGB won out and it was good enough to use anyway.

[Pascal Massimino]

Hi,

On Fri, Oct 2, 2015 at 10:36 AM, <tesla...@gmail.com> wrote:

I am not sure I understand correctly, but is this not a bit similar to the HAM encoding used by the Amiga range of computers in the 80s and 90s? The details are different, but the basic principle was to use a (hopefully) optimal palette and encode differences from the desired image as deltas from the palette (actually from the pixel to the left).

I think the original HAM encoding intended to use HSV colour but RGB won out and it was good enough to use anyway.

Interesting read: https://en.wikipedia.org/wiki/Hold-And-Modify

 

On Friday, 2 October 2015 18:41:25 UTC+2, mis...@google.com wrote:

During my summer internship in Google's compression team, I tried out a new image compression approach. Traditionally, lossless image compression, such as PNG or WebP lossless, have used either a truecolor (ARGB) or palettized (256 unique colors) as the main methods for storing the data. Often spatial predictors are used for the truecolor bytes, and less often for the palette indices.

What we wanted to try is something new: to approximate the prediction residuals by 256 discretized values. This is possible in the WebP lossless format without decoder changes: we can reverse the order of palettization and spatial prediction in the stream. The prediction residual is similar to a gradient of the image, so, when we discretize the gradient, we can have unbounded error. To mitigate this we used a novel error diffusion process that propagates the error to neighboring pixels that are not yet quantized. For further improvements, we implemented a back-error-propagation method, that moves some of the anticipated error from non-quantized pixels into the pixels being currently quantized. To try out something new like this, I needed to simplify things, and this version of delta-palettization does not support the alpha channel; all pixels have to have an alpha of 255. (While alpha adds a new dimension in the discretization space, we believe that in most cases it would be possible to handle it, too -- just not implemented yet.)

The palette of deltas is relatively sensitive. Small changes there can lead to large changes in compression density. Adding a few entries resulted in a 10 % size increase in one experiment.

We are not yet completely sure of the applicability of this compression mode. It seems to produce different kinds of artefacts from other methods. The quality seems superior to the lossy mode of WebP on photographic images: there is no YUV420 mode to flatten the colors. For photographs, the decoding speed of delta-palettization is about 2x faster than that of lossy WebP or non-palettized lossless WebP. Sometimes we see artefacts. It is likely that we can remove most of them by further algorithmic improvements of this method. Nonetheless, it is a new interesting compression mode. It is fast to decode, and the delta-palettized images are smaller than those compressed with lossless coding. Typically we see a size reduction of 60 % (2.5x faster to download) for photographic images. This is somewhat similar to lossy coding with quality 100. 

I'd like to thank Dr. Jyrki Alakuijala for guidance on this project, and Dr. Pascal Massimino for the code reviews.

Please see example images here. Every .png is the lossless RGB source, and the respective .webp delta-palettized.

https://drive.google.com/folderview?id=0B7Kdi6fw_WBBMjQ2OFRlNWVfNEU&usp=sharing

We will soon push a version of WebP that will contain the delta-palettization in its experimental mode.

--

Mislav

--
You received this message because you are subscribed to the Google Groups "WebP Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to webp-discuss...@webmproject.org.
To post to this group, send email to webp-d...@webmproject.org.
Visit this group at http://groups.google.com/a/webmproject.org/group/webp-discuss/.
For more options, visit https://groups.google.com/a/webmproject.org/d/optout.

[Pascal Massimino]

Hi,

On Fri, Oct 2, 2015 at 12:48 PM, Pascal Massimino <pascal.m...@gmail.com> wrote:

Hi,

On Fri, Oct 2, 2015 at 10:36 AM, <tesla...@gmail.com> wrote:

I am not sure I understand correctly, but is this not a bit similar to the HAM encoding used by the Amiga range of computers in the 80s and 90s? The details are different, but the basic principle was to use a (hopefully) optimal palette and encode differences from the desired image as deltas from the palette (actually from the pixel to the left).

I think the original HAM encoding intended to use HSV colour but RGB won out and it was good enough to use anyway.

Interesting read: https://en.wikipedia.org/wiki/Hold-And-Modify

 

On Friday, 2 October 2015 18:41:25 UTC+2, mis...@google.com wrote:

During my summer internship in Google's compression team, I tried out a new image compression approach. Traditionally, lossless image compression, such as PNG or WebP lossless, have used either a truecolor (ARGB) or palettized (256 unique colors) as the main methods for storing the data. Often spatial predictors are used for the truecolor bytes, and less often for the palette indices.

What we wanted to try is something new: to approximate the prediction residuals by 256 discretized values. This is possible in the WebP lossless format without decoder changes: we can reverse the order of palettization and spatial prediction in the stream. The prediction residual is similar to a gradient of the image, so, when we discretize the gradient, we can have unbounded error. To mitigate this we used a novel error diffusion process that propagates the error to neighboring pixels that are not yet quantized. For further improvements, we implemented a back-error-propagation method, that moves some of the anticipated error from non-quantized pixels into the pixels being currently quantized. To try out something new like this, I needed to simplify things, and this version of delta-palettization does not support the alpha channel; all pixels have to have an alpha of 255. (While alpha adds a new dimension in the discretization space, we believe that in most cases it would be possible to handle it, too -- just not implemented yet.)

The palette of deltas is relatively sensitive. Small changes there can lead to large changes in compression density. Adding a few entries resulted in a 10 % size increase in one experiment.

We are not yet completely sure of the applicability of this compression mode. It seems to produce different kinds of artefacts from other methods. The quality seems superior to the lossy mode of WebP on photographic images: there is no YUV420 mode to flatten the colors. For photographs, the decoding speed of delta-palettization is about 2x faster than that of lossy WebP or non-palettized lossless WebP. Sometimes we see artefacts. It is likely that we can remove most of them by further algorithmic improvements of this method. Nonetheless, it is a new interesting compression mode. It is fast to decode, and the delta-palettized images are smaller than those compressed with lossless coding. Typically we see a size reduction of 60 % (2.5x faster to download) for photographic images. This is somewhat similar to lossy coding with quality 100. 

I'd like to thank Dr. Jyrki Alakuijala for guidance on this project, and Dr. Pascal Massimino for the code reviews.

Please see example images here. Every .png is the lossless RGB source, and the respective .webp delta-palettized.

https://drive.google.com/folderview?id=0B7Kdi6fw_WBBMjQ2OFRlNWVfNEU&usp=sharing

We will soon push a version of WebP that will contain the delta-palettization in its experimental mode.

This new experimental code has been pushed in HEAD here: https://chromium.googlesource.com/webm%2Flibwebp/+/48f66b6687c195c78992b45d78e2117d648c4796

along with a follow-up refinement patch. Development and exploration is not yet finished (far from!), but it's in a usable

initial state. Just git sync to HEAD.

The code is protected by the WEBP_EXPERIMENTAL_FEATURES, that you have to somehow define before full recompilation.

Best is probably to modify the existing makefile.unix and uncomment the line 55:

  EXTRA_FLAGS += -DWEBP_EXPERIMENTAL_FEATURES

and recompile all: make -f makefile.unix all

Then, you can use: 'cwebp -delta_palettization in.png -o out.webp' to test the new mode.

Note that it activates the lossless compression syntax as side effect. It also doesn't work with alpha yet.

As for the algorithm itself, here are some precisions: the term 'delta-palette' should actually be understood

as 'gradient-space vector quantization'. The idea is to perform all sort of regular transforms and predictions,

which leaves a set of 'gradient' values to be coded. They are differential pixel values, generally speaking,

made of differences between various predictors  and the actual source pixels.

Then, before coding, this set of gradients is further approximated with values from a fixed palette entries,

which forms sort of a dictionary for approximating the gradients. An iterative algorithm then tries to assign

each original gradient value to a dictionary word from the palette, trying to minimize the overall error.

This is not a new format syntax: this algo is permissible within the current lossless spec.

Right now, the palette is fixed with 'general enough' values, but we later plan on using dynamic ad-hoc palette,

using an algo similar to k-mean.

give it a try!

skal/