Clustering pixel clots

I have:
1) The dark image with few groups of high-brightness pixels and some amount of noise around it.
2) Number of clusters.

Example:
1)

2) 2 clusters

And i need find centers of bright pixel groups.
Centers, in that case, should be placed like this:

Question: Which clustering alghoritm is suitable for this task?

• Do you know in advance how many clusters you have ? – BrunoLevy Dec 9 '15 at 14:38
• Yes. In initial data i have the image and number of clusters. – R95 Dec 9 '15 at 14:40

If the number of clusters is known (like here)

You may use Lloyd's clustering [1]

The idea is as follows: it optimizes a set of cluster centers $p_i$:

Initialize the p_i's with an initial guess, or randomly

For each iteration:
Compute the cluster associated with each p_i,
(the cluster is the set of points nearer to p_i than to the other p_j's)
Move each p_i to the weighted centroid of its cluster


For an image, the iteration can be implented as follows, computing the mass m_i and the centroid g_i of each cluster:

For each i
m_i = 0
g_i = (0,0)
For each pixel (x,y) of the image
let i denote the index of the center p_i nearest to (x,y)
m_i = m_i + pixel_intensity(x,y)
g_i = g_i + pixel_intensity(x,y) * (x,y)
For each i
p_i = (1/m_i)*g_i


Since the number of clusters is small, you can find the nearest p_i using a simple loop. If you have a higher number of sites, you may either use a kd-tree, or compute the Voronoi diagram of the sites and iterate on the pixels of each Voronoi cell.

I used this algorithm to cluster the colors of a rubics cube acquired by a lego color sensor, and it works reasonably well while being very easy to implement [3]

If the number of clusters is unknown then the problem is much more difficult.

You may use "mean shift clustering" [2], that will apply a filter-like operation to the image, and make the "modes" appear. It acts like the inverse of a smoothing filter.