I am trying to make a script that counts the number of regions with similar colour on an image. The idea is to count the number of regions in which a colour is used. For instance, if the image contains two colours, it should output 2 but if the image is made of one colour and a line of a different colour passing through the middle it should output 3. An important point is that the images could contain gradients of a similar colour and that should not be counted as a region.
This should output 3 regions 
This should output 5 regions 
I have tried a couple of implementations. Initially, by brute forcing it with k means and finding the right k which takes for ever with images with even a discrete amount of hue (from HSV). I also tried with watershed algorithm but found that is not very reliable. Thresholding was not very useful either.
Is there a more efficient way to compute it?