What specifically about this paper caught your eye that you wanted to implement that, what does it do better than other methods? Can you give a quick primer on what it does, and what the optional kmeans refinement does?
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.