Something that caught my eye is that it seemed to be a kind of "controlled" K-Means. One problem with K-means is that it's too sensitive to the initial state. You can run it multiple times with different initial states or use fancy initialization techniques (or both) but even then nothing really guarantees you won't be stuck with a bad local optimum. Another thing was that the guy that wrote the paper also authored an insanely high quality method the year before and claimed this one was better. Not seeing any available implementations I wondered how good it actually was.

The optional K-Means step just grabs whatever palette the original method yielded and uses it as initial state for a final refinement step. This gives you (or gets you closer) to a local optimum. In a lot of cases it makes little difference, but it can bump up quality sometimes.