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.