4 ms·
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 d
by 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 agoIt 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 agoFor 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.