[Geoserver-devel] Presenting new work on PNG8 quantization with alpha channel

GeoServer GeoServer Developer
1

Hi,
in this mail I’ll present some work in progress I have that makes on the fly color quantization
generating a png paletted map with per entry alpha channel.
It’s a large amount of work and I’ll take my time to present it (long mail, so grab a seat :wink:

The current color quantization code available in GeoServer has some really good features:

  • it works for both png8 and gif
  • it’s so fast it can run circles around all solutions I’ve seen so far that do the same work

Unfortunately it also has a couple of severe drawbacks:

  • when the original map has many colors the output is visibly degraded color wise (the quality
    problem)
  • it cannot handle translucency, all it can do is to mark one of the palette entries as fully transparent,
    losing all translucency information

The sweet spot for the current output format is a backgroud vector map, where there are not
too many colors and, being the background one, has no need for transparency.
However if you need to do a vector overlay the output quality obtained is simply unacceptable,
so during the end of year vacations I setup to solve that problem.

Did some research on the topic, the open source tools that do a good job at this are
pngquant, pngnq and the leptonica library.
pngnq uses the nequant algorithm, makes for the best output but has a very high price
on typical vector RGBA images (it’s really, really slow)
pngquant and leptonica use the median cut algorithm, pngquant in particular produces
good looking output with good performance.

The algorithm I came up with is a mix and match of bits coming from various directions:

  • uses media- cut like pngquant and leptonica
  • does a histogram with color shifting like pngquant (that is, if there are too many colors
    it starts throwing away the least significant bit of each color component to reduce the
    number of colors, and can do that more than once), but unlike pngquant it’s single pass
    (pngquant has to read the source image multiple times if there are many colors)
  • grabs some mediant cut smarts from leptonica to avoid issues with colors that
    are not used in many pixels, but are easy to spot when not rendered right (icons)
  • does pixel subsampling like the current png8 and pngnq
    This results seems like a decent compromise between memory usage, speed and output quality.

Enough talk, let’s see some results, starting with quality comparisons.
The algorithm I’ve been working on is called “pnga” in the comparisons.

Here are some links for the classic topp:states, png with transparency=true obtained
with various tools:

All the states are filled with translucent color, you should be able to see through them,
png8 obviously fails the test coming out with an invalid result.
The pnga output is a bit larger than pngnq and pngquant, and equally pleasing to the eye.
The size is also due to the png compression level, GeoServer sets it to 25% by default,
because for full png past that there is little gain and lots of extra work, however I’ve
noticed that with pnga output if you pump it up to 50% the size goes down to 19KB
and the speed does not seem to be affected, at 100% goes down to 18KB and speed
goes down 30% (hint hint, the integrated GWC should set its own compression levels)

One case that really tests the tools is the OSM like map I’ve prepared for the FOSS4G
2011 advanced styling presentation. With the little icons, the thin and dotted lines,
and plenty of antialiased lines, it’s rather hard to get good results with just 256 colors:

The image/png8 output is the smallest, but the output is atrocious, not really usable.
The pngquant and pngnq are both good, yet they both have evident problems
at representing the library/shopping center icons, which appear visibly ruined.
pnga makes for a small image size that still represents the icons properly, though
if you look really hard you’ll notice the lakes have a color that is not quite the
original one (but imho it’s a lot harder to notice than the ruined icons in fs8/nq8
outputs).
This result is there thanks to some tricks coming from the leptonica library and
explained in this paper, http://www.leptonica.com/papers/mediancut.pdf, plus
some extras of my own, all geared towards including in the palette colors that
are less used, pixel count wise, but that are very different from the rest of the palette,
and thus would stand out visibly if the color was not included in it.

This case is really the sweet spot for this algorithm, images that have a million
little pieces requiring antialiasing, yet most of the image is solid color, and has
lots of little areas with colors that are not used anywhere else. That is, the typical
translucent vector overlay.

I’ve also investigated a case outside of the sweet spot.

Let’s consider the spearfish layer group, that has a solid color dem in the background.
In this case I can show pnga is more expensive, but generates a image that
looks better than the image/png8 one, even without transparency in the mix.

If you look at the dem shades you’ll see that the png8 output is reducing colors
too much resulting in visible jumps, pnga less so, while pngquant and pngnq get
the best results for this case

Let’s also have a look at a performance comparison over the above cases,
here is a spreadsheet:
https://docs.google.com/spreadsheet/ccc?key=0Aq3GF1EnUyHEdDlMU2dwZURMY0IwRVkxVkt4RUdmd0E

If a cell has light red color it means the output is the output is not “valid”, that
is, png8 failed to deliver the expected transluncency and quality.
There are two comparisons, speed on the localhost, and speed considering
a 4Mbit speed between the two hosts (which might mean the client has
such speed available, or that the server has many concurrent clients and the
overall output speed has to be divided among them).

Long story short, pnga delivers good results with reasonable speed loss, but
image/png8 is still the king of speed in the cases where it delivers acceptable quality.
It is also the ony one that can work against a user provided palette: while I could
expand the current work to handle that case as well, performance would
unlikely be better than the case in which we figure out the palette dynamically
(because the work done while building the palette is reused to significantly speedup
the color translation at the end), so I’m not sure it’s worth the effort.

I still need to talk with Simone about harmonizing the two code bases where
possible, but I believe we’ll keep both and use each in its own sweet spot,
with a flag to force the usage of one or the other in case the user knows
better that our internal heuristics.

For those that want to try out this new output format I’ve attached a patch
to http://jira.codehaus.org/browse/GEOS-4919
Apply then ask for maps using format=pnga, or choose “png 8bit + alpha”
in the openlayers preview.

Known issues with the patch:

  • has no tests (so far tried to get the visual aspect and performance right,
    none can be actually checked with our in-build tests)
  • the code is meant to be very separate from everything else for ease
    of testing/development, has to be integrated better
  • does not work well with the raster direct rendering path + meta-tiling

Cheers
Andrea

–

Ing. Andrea Aime
GeoSolutions S.A.S.
Tech lead

Via Poggio alle Viti 1187
55054 Massarosa (LU)
Italy

phone: +39 0584 962313
fax: +39 0584 962313
mob: +39 339 8844549

http://www.geo-solutions.it
http://geo-solutions.blogspot.com/
http://www.youtube.com/user/GeoSolutionsIT
http://www.linkedin.com/in/andreaaime
http://twitter.com/geowolf

2

Hi Andrea,

I've read it all. Congratulations, looks like an amazing piece of work.

btw, what is the problem with meta tiling?

Cheers,
Gabriel

3

On Mon, Jan 16, 2012 at 11:08 PM, Gabriel Roldan <groldan@anonymised.com1…> wrote:

Hi Andrea,

I’ve read it all. Congratulations, looks like an amazing piece of work.

btw, what is the problem with meta tiling?

The JAI operation doing the color map inversion has troubles when dealing
with the output of an image mosaic, tries to access some pixels that is
not there.
Still trying to figure out, the output of the “direct raster path” generates
sometimes funny images, non 0 based, with partial tiles and the like

Cheers
Andrea

–

Ing. Andrea Aime
GeoSolutions S.A.S.
Tech lead

Via Poggio alle Viti 1187
55054 Massarosa (LU)
Italy

phone: +39 0584 962313
fax: +39 0584 962313
mob: +39 339 8844549

http://www.geo-solutions.it
http://geo-solutions.blogspot.com/
http://www.youtube.com/user/GeoSolutionsIT
http://www.linkedin.com/in/andreaaime
http://twitter.com/geowolf