I am not sure about pixelwise distance but what I could help is on applying KMeans on this picture. Let's say I give you this picture (I cannot get your original image so I'll just use mine).
Implementing KMeans on image is actually quite straightforward. What you might want to pay attention to is to the size of the image since big image like I what I am giving you here might cause many problems, such as big memory consumption.
The trick here is to resize image during training, you can use full image during prediction. You can think of it like this, scaling the image will roughly preserve how colors are distributed over the whole image so scaling down first will not change much on the cluster centres found by KMeans.
To do clustering, simply stack the image to 2D array and fit KMeans over this since we only cluster with pixel values. To get the segmented (clustered image) simply extract the cluster centres, replace the cluster with its respective centre and then rearrange back to the original shape. The code to do that is provided below.
img = cv2.imread('photo-1436891436013-5965265af5fc.jpg') ## Simply replace with your image file
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
img = cv2.resize(img, (int(img.shape/6),int(img.shape/6)))
km = KMeans(n_clust, n_jobs=-1)
clust = km.fit_predict(img_scaled)
ctrs = km.cluster_centers_
ctrs_map = dict(zip(np.arange(n_clust),ctrs))
segmented = np.array([ctrs_map[t] for t in clust]).reshape(img.shape,img.shape,3) * 255.0
segmented = segmented.astype(int)
Now you can also visualize for different K (I am not providing the code as it is quite trivial given the code above).