Add Color Quantization Method

[RyanBram]

Currently ImageWorsener has the most complete dithering method available than another image processing application. But ImageWorsener currently lack of color quantizer method that can be used in conjunction with dither. Some of available color quantizer that I know are:

• Uniform
• Popularity (Tom Boyle and Andy Lippman- 1978)
• Median cut (Paul S. Heckbert - 1980). The most used method, gives usually a good results and can be used sometimes without dithering.
• Octree (Gervautz and Purgathofer - 1988). Octree algorithm is really a family of algorithms. The one included reduces the tree lowest-population first and can be used in one pass, building and pruning the tree at the same time, or in 2 passes first building the tree and then pruning it. The result of the two pass method is better.
• Xiaolin Wu v2 (Xiaolin Wu 1992). Greedy orthogonal bipartition of RGB space for variance minimization aided by inclusion-exclusion tricks. (Author's description)
• Dennis Lee v3 ( (C) Dennis Lee 1997). A 2-pass color Quantizer that uses an exhaustive search technique to minimize error introduced at each step during palData reduction. (Author's description)
• Binary Split (Orchard and Bouman 1991)
• Lloyd algorithm (K-Means) (S. Lloyd 1957)
• NeuQuant ( (C) Anthony Dekker 1994). Method using Kohonen self organizing maps. Usually the best one according to RMSE.
• SColorQ (Spatial Color Quantization - Jan Puzicha et all 1998). Method for simultaneous quantization and dithering. Very good for small palettes, 16 colors or less, when other methods even with dithering don't work well.
• Pairwise Nearest Neigbour

Please implement at least one of them (Dennis Lee or Pairwise Nearest Neigbour) to make dithering method in ImageWorsener more effective.

For source code, I recommend you for looking at MtPaint repository as it was the project that I was aware implemented those algortihm very well.

Regards,

RyanBram

[jsummers]

I'm not really opposed to palette optimization features, but I'm afraid I have no plans to try to implement them in the near future.

Some concerns: (1) It requires an architectural change that will increase memory usage or code complexity. I want to do that anyway, for other reasons, but as of now there's no clean way add such a feature. (2) There are many different ways to do color reduction, so such a feature would never truly be finished. (3) Dithering to an optimized palette requires different algorithms than the ones IW uses now, and I'm not sure I know how to do it. (4) I don't know how well it would interact with other features. It might not be too hard to do if it were limited to, say, no more than 256 colors selected from the 24-bit truecolor sRGB palette. But IW's other features don't have such limitations.