The approach I finally settled on was: check each pixel in the image to build up a list of (RGB) most popular colors and to memoize new colors into LAB values;

The approach I finally settled on was: check each pixel in the image to build up a list of (RGB) most popular colors and to memoize new colors into LAB values; sort the color data into commonest first; then build up the required palette from commonest downwards, excluding colors that were too close to each other based on a distance measure. Then you can go back to the original image and measure its color against the palette colors, from which you can determine the 3 palette colors closest to it. From that you can give each pixel a propensity range of the likelihood of it taking on one of those 3 colors and run it against a randomly generated value, or a set of preset values for blue noise.