5 ms·

Any method that makes axis-aligned subdivisions (which includes both standard median cut and octree), even in a space like HSV, is going to be pretty suboptimal

by derf_ 12y ago

Any method that makes axis-aligned subdivisions (which includes both standard median cut and octree), even in a space like HSV, is going to be pretty suboptimal. There's probably been more sophisticated things done since I looked at this in the 1990's, but Xiaolin Wu's 1992 approach [1] works quite a bit better than both (including the 1991 Wu v2 implementation of an octree method linked elsewhere in this thread). It's based on recursive PCA, dynamic programming to assign colors along the principal axis, and K-means refinement in CIE L* u* v* coordinates. Not the fastest algorithm, but the topic is "high quality". And you can still dither the image without completely destroying compression. You just have to use an ordered dither [2]. [1] Xiaolin Wu, "Color Quantization by Dynamic Programming and Principal Analysis", ACM Transactions on Graphics 11(4): 348-372, 1992. https://dl.acm.org/citation.cfm?id=146475 https://dl.acm.org/citation.cfm?id=146475 [2] https://xiphmont.livejournal.com/35634.html https://xiphmont.livejournal.com/35634.html

pornel 12y ago
Aligned subdivisions are not that much of a problem actually. I've tested median cut that can cut at various angles and variants that cut out spheres, and it didn't make much difference. Choice of the box to cut and the location where you cut is more important. Wu's method is nice in this case because it exactly measures variance of sets after a split, while median cut just estimates. However, Wu's method needs lookup tables for the whole color (hyper)cube, which requires either large (or for RGBA still ridiculous) amount of RAM or reduced precision, and losing bits of input is way worse than having suboptimal division. The biggest wins I've found (and implemented in libimagequant) were: • Voronoi iteration after generating palette (like a final step in LBG quantization). This shifts axis-aligned subdivisions to local optimum (I've tried applying that after every subdivision, but it didn't matter — once in postprocessing is enough!) • Adjust weights/counts in histogram from quality feedback measured from remapped image. If you're aiming to minimize MSE, then that's not too expensive and it's similar to gradient descent.
- derf_ 12y ago
  > However, Wu's method needs lookup tables for the whole color (hyper)cube, You're talking about the 1991 method. The 1992 paper I cited explicitly claims as one of its advantages that it does not require lookup tables (and thus avoids the usual step of pre-quantizing down to 5 bit color to get a reasonably-sized table). Your two big wins sound an awful lot like "K-means". I'd believe they are responsible for the bulk of the improvement (they're also the bulk of the computation), but they mean you don't have axis-aligned partitioning anymore, which was my point. The problem is that K-means is notoriously sensitive to the initial clustering. For unsupervised learning, I'd want to do as good a job there as possible, and applying PCA means you are picking the split direction that exactly minimizes variance in the orthogonal directions. Random restarts are also a nice way to escape local minima, but are even more expensive computationally.
  - pornel 12y ago
    It is similar to K-means, but with exactly the crucial difference that clusters are not random, but picked by a guided subdivision algorithm.
- maxst 12y ago
  For apng2gif I modified Wu's method to use 64x64x64 cube (instead of original 32x32x32), and the results are much better. It doesn't require too much RAM, especially compared with what was available in 1992.
vanderZwan 12y ago
Ironically, that ACM paper is a scan of a printed out paper, with half-toned images, ruining the comparison images. Is there a purely digital version of that paper out there? EDIT: Is it this color quantization algorithm that is linked on Wu's own webpage? http://www.ece.mcmaster.ca/~xwu/cq.c http://www.ece.mcmaster.ca/~xwu/cq.c

by derf_ 12y ago

pornel 12y ago

Aligned subdivisions are not that much of a problem actually. I've tested median cut that can cut at various angles and variants that cut out spheres, and it didn't make much difference. Choice of the box to cut and the location where you cut is more important. Wu's method is nice in this case because it exactly measures variance of sets after a split, while median cut just estimates. However, Wu's method needs lookup tables for the whole color (hyper)cube, which requires either large (or for RGBA still ridiculous) amount of RAM or reduced precision, and losing bits of input is way worse than having suboptimal division. The biggest wins I've found (and implemented in libimagequant) were: • Voronoi iteration after generating palette (like a final step in LBG quantization). This shifts axis-aligned subdivisions to local optimum (I've tried applying that after every subdivision, but it didn't matter — once in postprocessing is enough!) • Adjust weights/counts in histogram from quality feedback measured from remapped image. If you're aiming to minimize MSE, then that's not too expensive and it's similar to gradient descent.

derf_ 12y ago
> However, Wu's method needs lookup tables for the whole color (hyper)cube, You're talking about the 1991 method. The 1992 paper I cited explicitly claims as one of its advantages that it does not require lookup tables (and thus avoids the usual step of pre-quantizing down to 5 bit color to get a reasonably-sized table). Your two big wins sound an awful lot like "K-means". I'd believe they are responsible for the bulk of the improvement (they're also the bulk of the computation), but they mean you don't have axis-aligned partitioning anymore, which was my point. The problem is that K-means is notoriously sensitive to the initial clustering. For unsupervised learning, I'd want to do as good a job there as possible, and applying PCA means you are picking the split direction that exactly minimizes variance in the orthogonal directions. Random restarts are also a nice way to escape local minima, but are even more expensive computationally.
- pornel 12y ago
  It is similar to K-means, but with exactly the crucial difference that clusters are not random, but picked by a guided subdivision algorithm.
maxst 12y ago
For apng2gif I modified Wu's method to use 64x64x64 cube (instead of original 32x32x32), and the results are much better. It doesn't require too much RAM, especially compared with what was available in 1992.

vanderZwan 12y ago

Ironically, that ACM paper is a scan of a printed out paper, with half-toned images, ruining the comparison images. Is there a purely digital version of that paper out there? EDIT: Is it this color quantization algorithm that is linked on Wu's own webpage? http://www.ece.mcmaster.ca/~xwu/cq.c http://www.ece.mcmaster.ca/~xwu/cq.c