I am trying to implement a system for extracting colour palettes from an image in C++. I basically want something exactly like the way Adobe Color's 'Extract Theme' function works.

I have tried implementing a version of median cut, but the averaging of the colours ultimately produces an unpleasing selection of final colours (though I may have implemented it wrong, I'm not sure).

I have tried k-means clustering (using this header library) but it doesn't seem to pick up a good selection of colours.

For example, here are the five colours that Adobe Color picks out of an example image: Adobe Color version

And here are the five colours selected by the k-means approach: K-Means version

Does anyone have any idea what's going on for the colour selection in the Adobe Color version? I'm trying to implement this inside Unreal Engine using C++, if that makes any difference.

Thanks.