Maybe you should try 'Expectation Maximization'. If you used Kmeans already this would be simple to implement. Instead of looking at the euclidean distance when checking to which cluster a certain point belongs in the next iteration, you now look at the distances relative to the standard deviation. So if a point is closer to the center of let's say Cluster A, considering the euclidean distance, it might be closer to the Cluster B relative to the standard deviation. In this case "closer" means having a color that is similar to the one of Cluster B. The described distance which considers the standard deviations is the so called Mahalanobis distance.

you can also use Self-Organizing Maps for image compression. there are many literatures which use SOMs successfully in compressing images such as the following:

Hierarchical and dynamic SOM applied to image compression

https://ieeexplore.ieee.org/document/1223472/

A novel Kohonen SOM-based image compression architecture suitable for moderate density FPGAs

Article A novel Kohonen SOM-based image compression architecture sui...

and many more.

Best regards

Well you can try for fuzzy c means algorithm.