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.
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.
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.