| | 1 | = !MapGuide RFC 60 - improvement for color palette quantization for PNG8 tiles = |
| | 2 | |
| | 3 | This page contains an change request (RFC) for the !MapGuide Open Source project. |
| | 4 | More !MapGuide RFCs can be found on the [wiki:MapGuideRfcs RFCs] page. |
| | 5 | |
| | 6 | |
| | 7 | == Status == |
| | 8 | |
| | 9 | ||RFC Template Version||(1.0)|| |
| | 10 | ||Submission Date||(27.02.2009)|| |
| | 11 | ||Last Modified||(UV Wildner) [[Timestamp]]|| |
| | 12 | ||Author||(UV Wildner)|| |
| | 13 | ||RFC Status||(draft)|| |
| | 14 | ||Implementation Status||(under development)|| |
| | 15 | ||Proposed Milestone||(2.1)|| |
| | 16 | ||Assigned PSC guide(s)||(when determined)|| |
| | 17 | ||'''Voting History'''||(vote date)|| |
| | 18 | ||+1||Bob, Andy, Haris|| |
| | 19 | ||+0||Paul|| |
| | 20 | ||-0||Tom, Bruce|| |
| | 21 | ||-1||Jason (troublemaker)|| |
| | 22 | ||no vote|| || |
| | 23 | |
| | 24 | == Overview == |
| | 25 | |
| | 26 | 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. |
| | 27 | 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. |
| | 28 | |
| | 29 | == Motivation == |
| | 30 | |
| | 31 | The color palette for PNG8 tiles is computed in the AGG renderer from truecolor tiles (AGGImageIO.cpp) on a one by one basis. |
| | 32 | The used quantization algorithm in the gd library (gd_topal.c) does not preserve the base colors of the map. |
| | 33 | Therefore adjacent map tiles might use different colors for map areas crossing tile boundaries. This is easily visible to the human eye. |
| | 34 | |
| | 35 | |
| | 36 | == Proposed Solution == |
| | 37 | |
| | 38 | 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 |
| | 39 | 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. |
| | 40 | |
| | 41 | {{{ |
| | 42 | / |
| | 43 | * copy src to dst using dst's palette |
| | 44 | * src must be a truecolor image |
| | 45 | * dst must be a paletted image |
| | 46 | * method is to fine tune the caching used to lookup color values in the palette: |
| | 47 | * -0 is the default method, which allocates cache memory when needed |
| | 48 | * -1 is a memory conservative method, that uses very little caching but is much slower |
| | 49 | * -2 is a memory hungry caching method (allocates 32MB on the heap) but is the fastest for large images |
| | 50 | * |
| | 51 | * see bug #2422 for some benchmark timings of these methods |
| | 52 | */ |
| | 53 | static int msImageCopyForcePaletteGD(gdImagePtr src, gdImagePtr dst, int method); |
| | 54 | gdImagePtr msImageCreateWithPaletteGD( gdImagePtr img24, const char *palette, int sx, int sy); |
| | 55 | }}} |
| | 56 | |
| | 57 | To further improve this approach some runtime test code needs be added to make sure that ''important colors'' are part of the used palette. |
| | 58 | 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. |
| | 59 | |
| | 60 | 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). |
| | 61 | |
| | 62 | Furthermore the `base color palette` should stored as a resource in the map definition. |
| | 63 | To disburden the administrator from having to compute the base colors and add them as a resource manually, |
| | 64 | some code in the TilingService should extract the map colors from the map and layer definitions upon startup. |
| | 65 | This method should also be hooked into the code that deletes the tile cache after a change in the map definition. |
| | 66 | The correct place to add such code should be discussed further. |
| | 67 | |
| | 68 | The desired mode '''''UseBaseColorMap''''' should be controlled with a configuration entry in the [TileServiceProperties] section of the serverconfig.ini file. |
| | 69 | |
| | 70 | == Implications == |
| | 71 | |
| | 72 | No Implications as the additional behaviour is off by default. |
| | 73 | |
| | 74 | == Test Plan == |
| | 75 | |
| | 76 | A few different approaches have been suggested above. Testing depends on which one will be chosen. Currently an Australian map showing good |
| | 77 | 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 |
| | 78 | error in the color quantization automated testing seems excessively expensive. If the Sheybogan map exposes this problem seems questionable. |
| | 79 | |
| | 80 | 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. |
| | 81 | 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 |
| | 82 | as any color histogram |
| | 83 | |
| | 84 | == Funding/Resources == |
| | 85 | |
| | 86 | Some funding is supposed to be provided by Explore Australia. |
