Reducing Local Neighbourhood of pixels

Question

I have recently come across a problem that I cannot seem to solve. I have a processed image that contains a number of pixels spread out across the entire image in small 'local' groups. I would like to find the 'centre' as it were of each group and place a single pixel in the output image as a representative of each group. The groupings can either be a closely knit group with no pixel zero spacing between them or a smaller spread out group with only a few (less than 4~5 pixels) between them. My first thought was to use something along the lines of morphological erosion but this doesn't account for the case of slightly more spread out groups of pixels. I would just like to know if someone can point me in the right direction. The following is an example of what I would like to do: The left hand side image shows the input (the big black dot represents a group of pixels with no zeroes between them) and the right hand side image is an example of the type of output or processed image I would like to have. Finally I am using MATLAB and it can be assumed that the input image is a binary image (either with black being 1 or 0 either way the logic should be the same).

Thanks so much for your help!

EDIT: Thanks everyone for their input - I will be trying out the different solutions over the next day or so and I will try to reply to everyone whence I'm done. Thank you all so much for your insightful inputs - it is greatly appreciated.

Answer 1

The problem you are describing is generally referred to as clustering or cluster analysis. Its can be quite difficult depending on your data set and your analysis constraints. However, in your case it is simple because you have a hard threshold (5 pixels) to use.

Aardvarkk has already put out a great solution but it doesn't really demonstrate the process of clustering. Here is a very simple way you could cluster your data and get more or less the same result.

1. Compute the pairwise distance between your points. For N points this results in an NxN matrix
2. Threshold that matrix
3. Iterate through the rows of the matrix

Each iteration would look like the following:

• if i is already clustered, continue
• if i isn't in a cluster, create a new cluster and assign i to it
• find all other points that are close to i (columns in row i that are equal to 1)
• Check to see if any of those points are already in a cluster
• If yes set i and all points close to i to the minimum cluster id
• If no set i and all points close to i to i's cluster

Here is a quick example I whipped up:

%Generate random points
nPts = 300;
clustId = zeros(nPts,1);
clusterCount = 0;
x = randi(3, [1, nPts])*10+ randn(1, nPts);
y = randi(3, [1, nPts])*10 + randn(1, nPts);

%Compute the distance matrix  from http://goo.gl/8mAoC
dist = distance([x;y], [x;y]);

maxDist = 5;
binDist = dist <= maxDist;


for i = 1:nPts
    % if this point is already clustered skip it
    if clustId(i) ~= 0
        continue;
    end

    %if the current point isn't in a cluster, create a new cluster and add
    %the point to that cluster
    if clustId(i) == 0
        clusterCount = clusterCount+1;
        clustId(i) = clusterCount;
        fprintf('New point, creating cluster:%d\n', clusterCount);
    end

    % get the indices of the points that collide with the i
    idx = binDist(:,i);

    % check to see if idx contains points that already belong to another clustered
    % if it doesn't collisionIdx will be equal to i
    collisionIdx = idx & clustId>0;

    %get the smallest cluster from collisionIdx
    mergeClustId = min(clustId(collisionIdx));

    %assing all the original points to that cluster
    clustId(idx) = mergeClustId;
end

Simply iterate through the cluster Ids to calculate the centroids:

cx = [];
cy = [];
for i = 1:clusterCount
    idx = clustId == i;
    cx(i) = mean(x(idx));
    cy(i) = mean(y(idx));
end

Then plot the results with:

figure; 
plot(cx,cy,'c.', 'markersize', 50); hold on;
plot(x,y,'.');

Answer 2

As pointed out by slayton, this is a clustering problem.

As the separation of your clusters is very clear you could use a simple graph-based approach. If you have access to a graph algorithm library (such as boost::graph, for which many bindings exist) the following approach should be pretty straightforward:

1. Build a complete graph of your points with edge weights as distances.
2. Compute a minimum spanning tree, for example with Prims algorithm
3. Eliminate edges exceeding a length threshold from the tree
4. Find the remaining connected components

Answer 3

I'd recommend an approach involving morphological closing followed by connected component analysis. Note that I've inverted the problem so the "good dots" are high-valued and the "bad background" is black. This fits more closely with the expected definition of the morphological operations.

path = 'yourimage.png'
space = 5; % you can change this to make it accept bigger spacings

input = imcomplement(rgb2gray(imread(path))) > 0;
input = imclose(input, strel('disk', space));
[labels, num] = bwlabel(input, 8);
output = logical(zeros(size(input)));
for i = 1:num
   [r, c] = find(labels==i); 
   x = round(mean(c))
   y = round(mean(r))
   output(y,x) = 1;
end

imshow(output)

The results look like this:

Seems to me to be what you're looking for!

Answer 4

In this case you could use a region growing method first to joing the clstered pixels and then use erosion. That would work, if you know, that the distances between the clusters are larger than the clusters themselves. Maybe use center of gravity to determine the middle of each blob after the region growing.