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	adopted
Implementation Status	completed
Proposed Milestone	2.1
Assigned PSC guide(s)	Bruce Dechant
Voting History	May 7, 2009
+1	Andy, Bruce, Haris, Jason, Kenneth, Paul, Tom
+0
-0
-1
no vote	Bob

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 ImageCopyForcePaletteGD.

/
 * 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
 */
int ImageCopyForcePaletteGD(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 MappingUtil::StylizeLayers(). To do this the VectorScaleRange gets an additional method called VectorScaleRange::GetUsedColorList(). This is a computed property implemented as a singleton which creates the list upon access. Subsequent requests from other threads read the same list. The singleton is not protected with a mutex as a second thread would recreate the same datastructure....in the worst case I can imagine a few kBytes of memory leak with a very low probability.... less costly than a mutex I suppose.

At the end of the stylization GetUsedColorList is called and the resulting color list is stored in the runtime map object MgMap (Map->SetColorPalette(pStringColorList)). This method sorts and uniquifies the color list upon storage.

The colors from the MdfModel are MdfStrings and the algorithm simply collects all different strings. So in order to support expressions for those colors the list simply needs to be interpreted when read from the MgMap object.

The RenderingService reads the color list from the map object, and converts it into a list of !RS_Color objects. This color palette is then passed down via the AGGRenderer to the AGGImageIO object's 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. See also the sequence ​http://trac.osgeo.org/mapguide/attachment/wiki/MapGuideRfc60/GetTile2.png

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 negligible. However, the color quantification is a bit more costly.

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

1. No user stored palettes are used in this approach as the colors are defined in the map and layer definitions. The whole idea of providing the colors in an external file has been dropped as it's more consistent and also fairly easy to create another version of the map having other colors defined within. Supplying a 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.

2. The quantization algorithm can use quite some memory. Three different memory allocation schemes have been provided. Due to recent problems in low memory situations a choice has been made to use the most memory conservative stack based allocation scheme.

3. In this phase only the colors from the VectorLayerDefinitions and in there the Area, Line, and Point Symbolizations are parsed as cleartext. Any further evaluation requires resource lookups which are a higher order of complexity and should not be permanently enabled.

4. No more memory issues. After some problems the code has been changed to duplicate any data from the MdfModel. Now the objects are created after stylization and destroyed after the tile has been created.

5. The algorithm parsing the MdfModel collects all different MdfStrings from the color fields. In order to support expressions for those colors the list simply needs to be reinterpreted when read from the MgMap object. Like the resource lookup this can be added at a later point in time when test cases and clearer specs have been established.