Image analysis: point regrouping
Hans Müller
My problem sound pretty simple (to me), but I am not quite sure how to tackle it.
My overall goal is segmentation of 3d images (cells). I have been using a gradient flow tracking approach, which leaves a "sink" at the center of each cell. I have labeled this sink in the sink matrix. Because my images are not perfect though, I tend to have more than one sink per cell, leading to my program thinking that one object is actually multiple objects.
What I want to do is cluster all points in the sink matrix (that are over 0) that are within a certain distance from one another and relabel them as one group.
Example
1 2 0 0 0
3 0 0 0 0
0 0 0 4 5
0 0 0 6 7
turns into
1 1 0 0 0
1 0 0 0 0
0 0 0 2 2
0 0 0 2 2
I have used a masking approach (building a box around each sink pixel in the sink matrix list and checking the surroundings) for 2D images, but this approach takes forever for large 3D images, since there are lots of sinks. (up to 100'000).
My idea now is to calculate the distance from each point to all the other points and group all points within a certain range, but I don't know how to implement this, since I don't want to calculate every single point in the matrix!
Anybody got any helpful ideas, or better even, a smarter approach than me?
Thanks!
Ashray
why dont u try morphological operation
using command 'bwmorph' in matlab
de various operation u can try are majority,bridge,erode
good luck
hey man can u also help with de code to plot rectangle around detected object
thanks
Ashish Uthama
> Hi!
>
> My problem sound pretty simple (to me), but I am not quite sure how to
> tackle it.
>
> My overall goal is segmentation of 3d images (cells). I have been using
> a gradient flow tracking approach, which leaves a "sink" at the center
> of each cell. I have labeled this sink in the sink matrix. Because my
> images are not perfect though, I tend to have more than one sink per
> cell, leading to my program thinking that one object is actually
> multiple objects. What I want to do is cluster all points in the sink
> matrix (that are over 0) that are within a certain distance from one
> another and relabel them as one group.
>
> Example
>
> 1 2 0 0 0
> 3 0 0 0 0
> 0 0 0 4 5
> 0 0 0 6 7
>
> turns into
> 1 1 0 0 0
> 1 0 0 0 0
> 0 0 0 2 2
> 0 0 0 2 2
If you have the image processing toolbox:
im =
1 2 0 0 0
3 0 0 0 0
0 0 0 4 5
0 0 0 6 7
%Use BWLABELN if you have an older version
>> cc = bwconncomp(im>0); %maybe use a different threshold?
>> labelmatrix(cc)
ans =
1 1 0 0 0
1 0 0 0 0
0 0 0 2 2
0 0 0 2 2
> I have used a masking approach (building a box around each sink pixel in
> the sink matrix list and checking the surroundings) for 2D images, but
> this approach takes forever for large 3D images, since there are lots of
> sinks. (up to 100'000). My idea now is to calculate the distance from
> each point to all the other points and group all points within a certain
> range, but I don't know how to implement this, since I don't want to
> calculate every single point in the matrix!
BWDIST might be useful here (the latest version has been sped up
considerably).
Maybe even KMEANS would help? :)
Hans Müller
Hey and thanks for your tips!
1) Here's my code for building a rectangle size r around each nonzero point in matrix.
[row,col]=find(matrix);
rect_matrix = zeros(size(matrix));
disp(' Connecting sinks ...');
for k=1:length(row)
for i=(row(k)-r):(row(k)+r)
rect_matrix(i,col(k)-r:col(k)+r)=1;
end
%now there is a box in rect_matrix, multiply with original
overlay_matrix=rect_matrix .* matrix;
%all points in box are relabeled with centerpoint value
matrix(overlay_matrix>0)= matrix(row(k),col(k));
%reset rect_matrix to 0 (seems more memoryefficient than creating a whole new
%matrix but I might be wrong
rect_matrix(rect_matrix>0)=0;
end
2) BWDIST sounds interesting. I'll see how I can apply it to my code (since it calculates the whole matrix, also the non-zero points!) The nearest-neighbor thing might actually be quite useful. I'll have to think about it tomorrow.
KMEANS is not an option since I don't actually know how many clusters there are. That's exactly what I want my program to do!
3) Here comes my new approach that should be more efficient while handling large datasets and matrices (however I have not tested it on 3D images yet). It is definetely faster for 2D images.
[row,col]=find(matrix);
coord = [row col];
lgt = length(row);
for k=1:lgt
d = sqrt(sum(abs(coord - repmat(coord(k,:), [lgt 1])).^2, 2));
% distance from each point to all the others!
%here comes annoying indexing stuff- is there a more efficient way?
loc= find(d<r); %all points closer than r pixels
locations = [row(loc) col(loc)];
ind = sub2ind(size(matrix),locations(:,1),locations(:,2));
matrix(ind) = matrix(row(k),col(k));
end
However, this does not take care of the problem that occurs when pixels are spaced out - chances are that the point of an already labeled cluster will be relabeled by another cluster, although they actually belong together!
i.e. the algorithm tests first x, then z, then y - leading to two objects where there should be only one.
0 x 0 0 1 0 0 1 0
0 y 0 -> 0 1 0 -> 0 2 0
0 z 0 0 z 0 0 2 0
My idea here is to create a lookup-table matrix checking if a point has already been labeled, then relabeling all the points in that particular cluster, and bla bla bla ..... maybe there is a quicker way.
Hans Müller
0 x 0
0 y 0
0 z 0
->
0 1 0
0 1 0
0 z 0
->
0 1 0
ImageAnalyst
Just use a morphological closing operation to join nearby clusters.
Here's a demo:
clc;
clear all;
close all;
imageArray = uint8(256 * rand(80,100));
subplot(2,2,1);
imshow(imageArray, []);
title('Original Image');
set(gcf, 'Position', get(0,'Screensize')); % Maximize figure.
binaryImage = imageArray > 245;
subplot(2,2,2);
imshow(binaryImage, []);
title('Binary Image showing some clusters');
closedImage = imclose(binaryImage, strel('octagon', 3));
subplot(2,2,3);
imshow(closedImage, []);
title('Closed Image with fewer clusters');
Then you just call bwlabel to give each cluster a number. Here's
another demo on image processing that does that:
http://www.mathworks.com/matlabcentral/fileexchange/25157
Hans Müller
That works like a charm - and it's infinitely faster ... thanks a lot!