| synopsis || arguments || prev |
void rearrange( kdu_byte * map)
[Declared in "../apps/image/kdu_image.h"]
Searches for a permutation of the palette entries which will optimize neighbourhood properties. Specifically, tries to minimize the sum of the distances between adjacent palette entries where distance is assessed as the sum of the absolute values of the colour component differences.
The task is nothing other than the well-known travelling salesman problem, which is known to be NP-complete. Consequently, the solution will generally be sub-optimal. The algorithm deliberately starts with the original palette order and tries to incrementally improve upon it, so that in the event that the palette already has good neighbourhood properties (e.g., a previously optimized palette, a "heat" map or something like that), the function will execute quickly and without damaging the original palette's neighbourhood properties.
The permutation is written into the supplied map array, which is understood as a lookup table whose inputs are the original palette indices and whose outputs are the new palette indices.