## Color quantization, minimizing variance, and k-d trees

Saturday, May 26th, 2018

A recent question on Stack Overflow really stroke my curiosity. The question was about why MATLAB’s `rgb2ind`

function is so much faster at finding a color table than k-means clustering. It turns out that the algorithm in `rgb2ind`

, which they call “Minimum Variance Quantization”, is not documented anywhere. A different page in the MATLAB documentation does give away a little bit about this algorithm: it shows a partitioning of the RGB cube with what looks like a k-d tree.

So I ended up thinking quite a bit about how a k-d tree, minimizing variance, and color quantization could intersect. I ended up devising an algorithm that works quite well. It is implemented in DIPlib 3.0 as `dip::MinimumVariancePartitioning`

(source code). I’d like to describe the algorithm here in a bit of detail.