How to: pixel packs in an image to representative point coordinates (x,y)

Question

Let's have an image (gray-scale or even binary) as shown on the following figure at the left hand side, the goal is to generate a list of points i.e., coordinates in the form of (x,y) for each pack of the dark pixels in the image.
What are the proper image processing tools to do this and where are they available?

---

Updates:
1) Here you may find some more details about the problem. (Note the variation in the size of packs)

I may suggest having packs detected to compute the convex-hull boundary for each and then find the representative centroid {see this for details}.

---

2)
Here is the result produced by application of Distance Transform (suggested by "Libor"). Note my annotations on the figure. The method does not work as it was promising!

3)
Erosion eliminates small packs!

from __future__ import division
from scipy import zeros, ndimage as dsp
from pylab import subplot,plot,matshow,show

img = zeros((30,30))
img[10:14,10:14] = 1
img[16:17,16:17] = 1
img[19:23,19] = 1
img[19,19:23] = 1

subplot(221)
matshow(img,0)

subplot(222)
y = dsp.binary_erosion(img,[[1,1],[1,1]])
matshow(y,0)

subplot(223)
y = dsp.binary_erosion(img,[[0,1,0],[1,1,1],[0,1,0]])
matshow(y,0)

subplot(224)
y = dsp.binary_erosion(img,[[1,1,1],[1,1,1],[1,1,1]])
matshow(y,0)

show()

4)
Well here is a Python (i.e., the language of love :) ) implementation of the labeling idea (also proposed by "Jean-Yves" below):

subplot(221)
l,n = dsp.label(img)
sl = dsp.find_objects(l)
for s in sl:
    x = (s[1].start+s[1].stop-1)/2
    y = (s[0].start+s[0].stop-1)/2
    plot(x,y,'wo')

and the result:

Note that although it is done in Python so quick due to Scipy performance, the background procedure in label function should be an exhausting iteration. This may be considered as a trade-off. So for a while I keep being eager to seek more efficient algorithms. And also note that in the given code above I found the center of geometry so simply while for complex or asymmetric shapes this may cause positioning to be biased. That is it is a work in progress ;).

5)
Here is a complex case (a real image) captured from here on which the labelling proposal applied and you see the results. Note that it took only 0.015 s for whole procedure including labelling and finding the objects. Scipy guys, did very well job, I think. Wow! {right-click on image, click on view image for full resolution}

Answer 1

Just a naive suggestion: do you know about component labeling?

The technique is about finding chunks of "touching" pixels and assigning them a label, e.g. an integer number. You can then interrogate each chink separately, looking for the pixel that share the same label.

In MATLAB, here is the function that does it trivially: bwlabel

Answer 2

You can also run a distance transform on the image, then detect local maxima (searching for pixels with highest/lowest value of all pixels in 3x3 pixel patch - can be larger depending on expected minimum distance between the original blobs).

Note that for detecting features of size 1-3 pixels, you need to double your sampling frequency (either upscale the source image or perform distance transform/erosion with sub-pixel accuracy).

UPDATE:

Both distance transform and erosion approaches assumes that the features you are detecting are convex. Something with U shape, for example, may fire in your detector several times.

A more elaborate method for such segmentation is based on level sets and active contours. It starts with a large closed curve which is iteratively adapted to your features. This method has been used on my university for counting cells and detecting chromosomes in microscope images.

Answer 3

I am afraid that whatever way you pick to do this, it is not going to be straightforward because to assign the targets to clusters you are going to have to go through the image (at least once).

I suppose that getting the points is the easier problem of the two (you are probably already applying some form of thresholding for example).

To recover the clusters that points are grouped into and do it fast, you could create a quad-tree structure that holds "chains of connected pixels" that are somewhere around the area of the quad-tree cell.

In this way, you could iterate through the image and once you come across a pixel that is a target, "push" it in your quad-tree structure.

This "push" operation would start an iterative process which would return the cell (in other words the specific area of the image) where the particular pixel lies in. You could then iterate through all the pixel chains that are assigned to that cell and try to "push" (again) the pixel to the pixel chain. A pixel chain accepts a new pixel if it is at least 1-pixel near to any of its already assigned pixels. If no pixel chain "accepts" the new pixel, then create a new pixel chain into this cell and assign the new pixel to it.

The quad-tree here is a way to limit your search for the nearest pixel-chain and it would be required if your image is big and the targets numerous so that the pixel-chain push operations are done fast. If you know that you are not going to be dealing with a large number of targets then you could even skip the quad-tree and maintain a simple "list of pixel chains". Every time you come across a "target" you could iterate through the lists and try "pushing" the pixel on them. If no list "admits" the pixel then create a new list and assign the pixel in.

Whichever way you choose to do it, at the end of this process you are going to have a set of connected "pixel-chains" (your clusters) which you can then pass to another part of your program that will be dealing with estimating their location. This can be convex-hull, model fitting (for example ellipsoid or other) or simply the mean / median of the x,y coordinates.

I hope this helps.

Answer 4

One option would be to apply repeated morphological erosion to the image until it is fully eroded. At that point, each of the blobs shown above would be reduced down to a single pixel; you could take the locations of those pixels to be the list of points that you're looking for.