MapGuide RFC 60 - improvement of color palette quantization for PNG8 tiles

This page contains an change request (RFC) for the MapGuide Open Source project. More MapGuide RFCs can be found on the RFCs page.

Status

RFC Template Version	(1.0)
Submission Date	(27.02.2009)
Last Modified	(UV Wildner) Timestamp
Author	(UV Wildner)
RFC Status	(draft)
Implementation Status	(under development)
Proposed Milestone	(2.1)
Assigned PSC guide(s)	(when determined)
Voting History	(vote date)
+1	Bob, Andy, Haris
+0	Paul
-0	Tom, Bruce
-1	Jason (troublemaker)
no vote

Overview

The color quantization for PNG8 tiles does not preserve the base colors of the map. This leads to visible color differences in adjacent map tiles. By providing color hints of the base colors of the map in a palette file the visual appearance of the map can be significantly improved.

Motivation

The color palette for PNG8 tiles is computed in the AGG renderer from truecolor tiles (AGGImageIO.cpp) on a one by one basis. The used quantization algorithm in the gd library (gd_topal.c) does not preserve the base colors of the map. Therefore adjacent map tiles might use different colors for map areas crossing tile boundaries. This is easily visible to the human eye.

Proposed Solution

By providing the base colors of the map in a palette file and using an improved color quantification algorithm which adds a forced palette to the image the resulting map can be significantly improved. This can be done easily by adding borrowing the function msImageCopyForcePaletteGD from the mapserver code base which does exactly that.

/
 * copy src to dst using dst's palette
 * src must be a truecolor image
 * dst must be a paletted image
 * method is to fine tune the caching used to lookup color values in the palette:
 *  -0 is the default method, which allocates cache memory when needed
 *  -1 is a memory conservative method, that uses very little caching but is much slower
 *  -2 is a memory hungry caching method (allocates 32MB on the heap) but is the fastest for large images
 * 
 * see bug #2422 for some benchmark timings of these methods
 */
static int msImageCopyForcePaletteGD(gdImagePtr src, gdImagePtr dst, int method);
gdImagePtr msImageCreateWithPaletteGD( gdImagePtr img24, const char *palette, int sx, int sy);

To further improve this approach some runtime test code needs be added to make sure that important colors are part of the used palette. In the simplest case an exception is thrown if the color of a single color tile is missing in the provided palette creating an error message.

As a next improvement for such run time testing some histogram based heuristics can be used to detect important colors (e.g. n% pixels of a tile with n TBD).

Furthermore the base color palette should stored as a resource in the map definition. To disburden the administrator from having to compute the base colors and add them as a resource manually, some code in the TilingService should extract the map colors from the map and layer definitions upon startup. This method should also be hooked into the code that deletes the tile cache after a change in the map definition. The correct place to add such code should be discussed further.

The desired mode UseBaseColorMap should be controlled with a configuration entry in the [TileServiceProperties] section of the serverconfig.ini file.

Implications

No Implications as the additional behaviour is off by default.

Test Plan

A few different approaches have been suggested above. Testing depends on which one will be chosen. Currently an Australian map showing good test cases in a certain zoom level is used to verify the algorithm. As the underlying map requires a certain complexity to expose the mapping error in the color quantization automated testing seems excessively expensive. If the Sheybogan map exposes this problem seems questionable.

However, some tunrime tests should be included. One such runtime test is to check for the existence of important colors in the provided color map. This verifies that no base color has been missed in the provided color map. If similar code is used to incrementally create the color map the only test I can think of is a visual examination of a map with known problems as any color histogram

Funding/Resources

Some funding is supposed to be provided by Explore Australia.