Cool, I did something like this for an e-commerce store so that I could programmatically sort new products into color bins. Scipy handled the kmeans stuff for me though.
One problem I ran into but never solved was ignoring the background color. For example in the second picture it might be more interesting to bring out the oranges of the tail-lights and the light-blues of the street lights, rather than just the dark blues of the roads. You could ignore the largest cluster, but that's not always necessarily the background color. Have you thought about this at all?