# Non overlapping Clustering/ Segmentation of image points

I have this simple image from map building that I wish to cluster to extract the black dots as points in image co-ordinates (ie. the x,y coordinates of the cluster centers). I have tried many functions in opencv, sklean and ndimage. These manage to cluster well but I cannot get any to have non overlapping clusters ie. one for each black dot, there are either too many or they're not all covered.

I have tried playing with parameters but feel like there must be a good way of doing this since after thresholding the black points are extremely clear, the problem is that they are not actually together but lots of smaller points which means clustering finds them as many clusters. Wondering if anyone has any insight.

Many thanks

## 1 Answer

Approach 1: Threshold the image such that only the black pixels remain on a white background. Smooth the image with a gaussian kernel/filter, which will have the effect of blurring the scattered pixels together within each cluster. The kernel width should be wide enough that points in each cluster merge into a single bump, but not so wide that multiple clusters blur together. Each cluster now corresponds to a blurry spot in the image. Find cluster centers as the local extrema or centers-of-mass of these spots. For example, this could be done using image processing functions to find connected groups of non-white pixels (each group corresponds to a cluster). Find the center of each cluster as the blackest pixel, or take the average pixel location weighted by blackness. This method is essentially performing density-based clustering on a kernel density estimator of black pixel locations.

Approach 2: Threshold the image such that only the black pixels remain on a white background. Extract the xy location of each black pixel. The $(x,y)$ pair for each black pixel is a point in 2d space. Cluster these points using a standard statistical clustering method like k-means, Gaussian mixture models, DBSCAN, etc. You may have to select hyperparameters of the algorithm to obtain a good clustering. For example, some methods require you to specify the number of clusters (there are also automated procedures for choosing this; search this site for details). Cluster centroids are returned by the clustering algorithm (or can otherwise be computed from the points assigned to each cluster).