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
+0
-0
-1
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 the base colors of the map as a palette to the image renderer 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 as they are not know at this place. Therefore adjacent map tiles might use different colors for map areas crossing tile boundaries. This is very obvious and disturbing to the human eye.

Ticket #813 PNG8 Compression isn't preserving fill colors

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 by using the median-cut algorithm as used in the mapserver code base in the function msImageCopyForcePaletteGD.

/
 * 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);
/// create an empty paletted gdImage of size (x,y) using the base colors provided in the baseColorPalette
/// the original truecolor image img24 is used to fill up the remaining slots of the palette if needed
gdImagePtr CreateGdImageWithPalette( gdImagePtr img24, RSCOLORLIST* baseColorPalette, int sx, int sy) 

server code integration

The interesting task is how to feed the base colors of the map to the Image Renderer making the image. The base colors of a map can be extracted most efficiently during map generation in MapingUtil::StylizeLayers(). To do this the VectorLayerDefiniton gets an additional method called VectorLayerDefiniton::ComputeUsedColors(scaleRange). At the end of the stylization this method is called and the resulting color list is stored in the runtime map object MgMap. (Map->SetColorPalette(pStringColorList))

The RenderingService reads the color list from the map object, sorts and uniquifies it, and converts it into a more appropriate Colortype. This color palette is then passed down via the AGGRenderer to the AGGImageIO objects Save method. Here the png color quantification algorithm is included to force the provided palette into the rendered image - this way making sure that the correct base colors survive the compression and/or color quantization.

Implications

No Implications are intended as this behaviour is desired by default. We just get better looking maps. The cost of extracting the colors from the in-memory representation of the XML data describing the map are presumed to be negligable.

Test Plan

Currently an Australian map showing good test cases in a certain zoom level is used to verify the algorithm. Since the underlying map requires a certain complexity to expose the mapping error in the color quantization, setting up a unit test seems excessively complex. Any ideas are most welcome.

So far some debugging code has been included to verify the collection of the colors within the rendering service. The success is then evaluated on visually inspecting the map and testing if the base colors made it through using IrfanView.

Any suggestions are most welcome.

Funding/Resources

Some funding is to be provided by Explore Australia.

closed Issues

No user stored palettes are used in this approach as the colors are defined in the map & layer definitions. The whole idea of providing the colors in an external file has been dropped as its more consistent and also fairly easy to create another version of the map having other colors defined within. Supplying an user specified color palette to override the colors specified in the map fails at the missing mapping from a linear color list to the complex hierarchical structure of the map definition.

open Issues

The quantization algorithm uses lots of resources. 3 different memory allocation schemes have been provided. Selecting those is supposedly too specific to warrant a server option entry. However, the correct approach needs to be decided by a system architect with deeper insight into the MapGuide architecture.