Cluster growing of blobs

问题:

Consider the following image which is from Mathworks:

I have labelled the blobs with

 [L, num]= bwlabel(I);

How do I connect all the blobs iteratively,i.e.start with one blob and find the nearest one to it.Consider the left-most two blobs, there can be many lines that can be drawn from many points of a blob to connect to the other blob, but the shortest one would be obtained by finding the pixel of a blob that is nearest to the other blob, find a similar pixel in the other blob and connect these two pixels.I would like connect them in this manner.After connecting them, which makes them a single blob, find the blob closest to this new blob connect them, and so on, until all the whole image has a single closed structure? Also, the blobs aren't always circular,they are of random shapes.

Similar questions have been asked here:

How to find the shortest path between two blobs(contours/closed curves) using MATLAB?
and http://in.mathworks.com/matlabcentral/newsreader/view_thread/270149

Using bwdist(), I could separate two blobs and use brute force approach to find the shortest distance by testing on all pairs of pixels in the two blobs as mentioned in the second link but it takes a really long time.Is there a better way to approach this so that the results can be obtained faster?

Edit:

This is another image:

Required image:

回答1:

Approach #1 : Connecting with the centroid points

%// Read image, convert to binary and remove some whitish border across it
im = im2bw(imread('http://i.stack.imgur.com/vUsrl.png'));
BW = im(3:end-2,3:end-2);
figure, imshow(BW), title('Starting/Original Image')

%// Find centroid points for each blob
cpts = reshape(round(struct2array(regionprops(BW,'Centroid'))),2,[])'; %//'

%// Initialize 2 groups- "hungry" & "feeder" groups, naming them as grp1 & grp2
grp1 = []; grp2 = cpts;

%// Initialize the blob index matching IDs
R = 1; C = 1;

while ~isempty(grp2)

    %// Get one from Group-2 into Group 1 based on the closest one that was
    %//obtained from the previous iteration. Remove that from Group -2.
    grp1 = [grp1 ; grp2(C,:)];
    grp2(C,:) = [];

    %// Find squared distances between those two groups
    sq_distmat = squared_dist(grp1,grp2);

    %// Find the IDs minimum one across row and column which would be the
    %IDs for group 1 and 2 respectively, calling them as R and C
    [~,idx] = min(sq_distmat(:));
    [R,C] = ind2sub(size(sq_distmat),idx);

    %// Draw the connecting line
    BW = linept(BW, grp1(R,2), grp1(R,1), grp2(C,2), grp2(C,1));

end
figure, imshow(BW), title('Final Connected Image')

Associated function -

function sq_distmat = squared_dist(A,B)

[nA,dim] = size(A);
nB = size(B,1);

A_ext = ones(nA,dim*3);
A_ext(:,2:3:end) = -2*A;
A_ext(:,3:3:end) = A.^2;

B_ext = ones(nB,dim*3);
B_ext(:,1:3:end) = B.^2;
B_ext(:,2:3:end) = B;

sq_distmat = A_ext * B_ext.';

return;

Animation fun -

---

Approach #2 : Connecting with the contour points

%// Read image, convert to binary and remove some whitish border across it
im = im2bw(imread('http://i.stack.imgur.com/vUsrl.png'));
BW = im(3:end-2,3:end-2);

%// Find boundary points as a cell array
bpts_cell = bwboundaries(BW);

%// Initialize 2 groups- "hungry" & "feeder" groups, naming them as grp1 & grp2
grp1c = []; grp2c = bpts_cell;

ID = 1;
for iter = 1:numel(bpts_cell)-1

    %// Get one from Group-2 into Group 1 based on the closest one that was
    %obtained from the previous iteration. Remove that from Group -2.
    grp1c = [grp1c ; grp2c(ID)];
    grp2c(ID,:) = [];
    grp1 = vertcat(grp1c{:});
    grp2 = vertcat(grp2c{:});

    %// Find squared distances between those two groups
    sq_distmat = squared_dist(grp1,grp2);

    %// Find the IDs minimum one across row and column which would be the
    %IDs for group 1 and 2 respectively, calling them as R and C
    [~,idx] = min(sq_distmat(:));
    [R,C] = ind2sub(size(sq_distmat),idx);

    %// Draw the connecting line
    BW = linept(BW, grp1(R,1), grp1(R,2), grp2(C,1), grp2(C,2));

    lens = cellfun('length',grp2c);
    clens = cumsum(lens);    
    ID = find(C<=clens,1);
end

Animation fun -

Animated output with the Edit image -