[enhray]

This is a very good intro to K-D trees, big thank you to the author. However, I think that a three-dimensional lookup table would be more performant in this case. 16M (256^3) of entries are needed to cover RGB color space with 8 bits per channel, that's a lot, but lookup time is O(1) with a very small constant.

[psergeant]

I think if I was actually building this, I’d do that initial calculation, and then compress it into a linear decision tree. Potentially tiny data set, very fast lookups. There’s definitely going to be some inaccuracy there, but I suspect small

[contravariant]

I think the problem there is that if you're only looking at a few images then generating the 16M lookup table takes more time than using the K-D tree itself.

Some kind of memoisation scheme might work though.

[rndgermandude]

You can actually use the k-d table to compute the lookup table, as the lookup table is nothing more really than an image containing a "pixel" with each possible color exactly once. The author already ran the algorithm on a 12285x14550 image, which took 10x more time than running on a 256x256x256 "image".

Of course, if you want to compute the lookup table dynamically on each run, you might use memoization and hope the image is either small (and therefore uses comparatively few colors) or large with few actual colors in use.

[foota]

That might not have very good cache performance though?