High-Color GIF Images en

By Soultaker on Wednesday 20 February 2013 07:00 - Comments (5)
Category: -, Views: 9.842

In the nineties the prevalent image format used on the world wide web was the GIF file format (full spec), which is reasonably efficient, widely portable, and supports animation and transparency. Mainly inspired by concerns over patent claims by Unisys on the LZW compression algorithm used to create GIF files, proponents of open web standards designed the PNG file format (based on the DEFLATE compression algorithm, which is believed to be unencumbered by patents) as a replacement. PNG does have several advantages over GIF, but some of the PNG-advocacy from the time was misleading.

One common reason suggested to prefer PNG over GIF, was that GIF files are limited to using 256-color palettes, and therefore unsuitable for rendering color images faithfully. It turns out this isn't quite true! GIF files can, in fact, contain an arbitrary number of colors, and in this post I will show how such high-color GIF images can be constructed that are quite suitable for web use.

Technical details


Althought it's true that GIF files are limited to an 8-bit pixel format (each pixel value indexing a table of at most 256 colors) a single GIF image may contain multiple graphic rendering blocks, each of which may include its own local color table of 256 colors drawn from a 24-bit color space.

Since a single image can display multiple graphic rendering blocks at once (either by rendering separate blocks into separate regions of the canvas, or by using transparency to overlap blocks without overwriting all previous pixels) the final image can contain an arbitrary number of different colors.

An easy approach to generating high-color GIF images is to partition the set of colors used over multiple frames which are then rendered on top of each other. The first frame contains the pixels with the 256 most-commonly used colors, while each next frame adds 255 new colors (reserving one palette index for transparency).

http://tweakers.net/ext/f/Izh4xRAT3RRl5vGtZpJfBYta/full.pnghttp://tweakers.net/ext/f/uVmGud5zr8bULuo1e4YxxEv2/full.gifhttp://tweakers.net/ext/f/QPI1xAja4vBoRHRTZwgpvN0r/full.gif
170x240 pixels, 36330 colors,
24-bit PNG, 88 KB
170x240 pixels, 36330 colors,
143 frames GIF, 242 KB
170x240 pixels, 36330 colors,
143 frames GIF, 337 KB

In the table above, the image on the left is a full-color (and rather colorful) PNG image. The middle image is a GIF file encoded using the technique described above. Some problems with the approach are apparent. The first is that modern browsers insert an artificial rendering delay between frames (refresh the page if you missed it while reading the introduction!) As a consequence, it takes a while for the picture to take shape, because each frame only contains a small fraction of the total image. And finally, because there are so many frames, the resulting file is rather large!

The awkwardness of incremental rendering can be ameliorated by encoding more image information into the first few frames. Instead of rendering only the pixels with exactly matching colors on each frame, we can approximate the other pixels with the nearest available color too. This means the first frame already contains an approximation of the full image, and that subsequent frames improve on (part of) the image by rendering additional details. Besides looking better when rendered incrementally, this has the advantage that GIF renderers that fail to render all frames will still display a reasonable approximation of the final image. The image on the right in the table above is the result of approximating the first few frames this way.

The table below shows the result of this approximate encoding of frames. The first row contains the first few frames of the GIF file. Note that the first image contains an approximation of all the pixels, while subsequent frames use transparency on pixels that cannot be better approximated using the frame-local palette. The second row shows the composite of the frames rendered so far, while the third row shows the symmetric difference with the final image (which should fade to black eventually).

http://tweakers.net/ext/f/faXgaXnJBj2fIiw63d9zcyqv/full.png

This approximation technique, unfortunately, creates somewhat larger files, because frames tend to contain fewer transparent pixels and therefore aren't compressed as much.

However, the more important cause of the large file size of these GIF files, is that they span a lot of frames (143 for just this small image!) despite the fact (as the image above shows) that after a few frames, the end result is already approximated relatively well. It seems dubious whether the last hundred frames or so really add much information to the image, even though they are required to reproduce all pixels exactly.

In a GIF file ony pixel data is compressed while color tables are not. Therefore, every additional color requires at least three more bytes in the file (one byte for each component: red, green and blue) and using a large number of distinct colors isn't particularly efficient.

From a practical point of view, it makes more sense to reduce the number of different colors in the image. For example, if we want to use just 10 frames, we can still render 2551 different colors, which is certainly a big improvement over the 256 color palette GIF files typically use. This seems like a good compromise between image quality and file size.

To show how well this works, here is a 2551-color high-resolution version of the image shown before:
http://tweakers.net/ext/f/L9kEhvvZMizHQ5SE4rDoyh9P/full.gif

Yes, that is really a GIF image you're looking at! The table below summarizes the results for various image formats. Note that the simple 10-frame GIF image is actually smaller than the PNG image after quantization.

Full imageFull imageFull imageFull imageFull image
679x960 pixels,
436186 colors,
24-bit PNG,
1235 KB
679x960 pixels,
2551 colors,
24-bit PNG,
1194 KB
679x960 pixels,
2551 colors,
10-frame GIF,
1109 KB
679x960 pixels,
2551 colors,
10-frame GIF,
1483 KB
679x960 pixels,
256 colors,
1-frame GIF,
415 KB


Conclusion


Although the PNG file format is arguably superior to GIF in many ways, it is possible to render colorful images from GIF files. Even so, it makes sense to reduce the color palette somewhat to avoid creating excessively large files. One practical problem with this approach is web browsers' failure to render multiple blocks without delay; this is arguably a bug that ought to be fixed.

Tools used


In case you want to perform similar experiments, I will list the tools I've used to create the images in this post (mostly written in Python). Feel free to use them however you like.These scripts use the Python Imaging Library which unfortunately doesn't support creating GIF files with multiple frames, so I used Gifsicle to combine the single-frame images.

Since I couldn't find a good color quantization tool that works with more than 256 colors, I implemented my own using K-means clustering:
  • quantize-kmeans2.py is simple and works well, but rather slow (especially for large images and color palettes).
  • quantize-kmeans.c is my own implementation of Lloyd's algorithm in C instead, which is what I used to create the 2551 color image above.
Finally, the sample image used in this post I stole from *muju's DeviantArt page. It's a fan's rendition of the character *Mute from Christine Love's visual novel Analogue: A Hate Story.

Volgende: Cyber Crime Challenge 0xFFD 03-'13 Cyber Crime Challenge 0xFFD
Volgende: Facebook Hacker Cup 2013: round 1 problem analysis 02-'13 Facebook Hacker Cup 2013: round 1 problem analysis

Comments


By Tweakers user Sp3ci3s8472, Wednesday 20 February 2013 08:50

Doesn't the OpenCV library deliver some kmeans functions that could be used for this?
When I compare the high color png to the medium and high color gif it is indeed hard to see any real difference (at least on my crappy laptop screen :D).
The area that still does catch my eye is around the nose, there it's clear that png is superior.

If you continue on your topic of comparing file formats, you could look into the fact that small size (80x80 for example) images look a lot better with gif than with jpeg. It first occurred to me when I was trying to create a suitable thumbnail for tweakers :P.
I couldn't get the file under 29kb with jpeg while gif easily created 3kb files, this has obviously to do with the amount of color information available.

By Tweakers user RoadRunner84, Wednesday 20 February 2013 10:13

I think you could have a third option in between:
  • Render 255 colours at a time
  • Render a full image and continue approximating
  • Render a full image and then add 255 colours at a time
The third option allows you to have a larger number of transparent pixels in each frame than the approximating approach, since you only add exact pixel matches.

By Tweakers user Infant, Wednesday 20 February 2013 15:10

Is PNG also capable of palleted images? Because your original file has 436186 different colors, which would fit in an 18-bit palette. (The original JPG has 469298 different colors)

If you'd want to save it lossles, saving it as a 24-bit bmp and then RAR-ing it gives you a 1130kb file. Which is smaller than the 24bit PNG.

Isn't that interesting?

By Tweakers user Soultaker, Wednesday 20 February 2013 16:06

@RoadRunner84: this is already what happens; the 337 KB GIF only approximates in the first four frames, and the final 1,4 MB GIF only in the first frame.

I think an even better option that I failed to explore before, would be to approximate pixels in every frame, but only if the new approximation is better than the previous one by at least some constant factor. For example, applying this idea to the large 2551-color image (at least halving the Euclidean distance) yields this 1617 KB GIF. However, since this only improves the combined image for the middle frames of the GIF, I find it hard to justify the increase in file size.

[Comment edited on Wednesday 20 February 2013 16:07]


By Tweakers user Soultaker, Wednesday 20 February 2013 16:12

Infant wrote on Wednesday 20 February 2013 @ 15:10:
Is PNG also capable of palleted images?
Yes, but not with more than 256 colors.
If you'd want to save it lossles, saving it as a 24-bit bmp and then RAR-ing it gives you a 1130kb file. Which is smaller than the 24bit PNG.
I'm not surprised — PNG is basically Paeth-filtering followed by DEFLATE compression (the same method used in ZIP files) and RAR is a comparatively much more powerful compression algorithm.

I've experimented with simple yet efficient lossless image compression before, and I got the best results by separating the image by color channel, then Paeth-filtering, then LZMA compression. This would beat PNG almost every time, mainly due to the fact that LZMA is a superior compression algorithm.

Comments are closed