Slow Find Loop no vectorisation

1 view (last 30 days)
I have a 3d image where each colour is a unique labelled cell. I'm trying to find the centre of mass of each of these individual colours.
for colour = 1:2^16
coords = find(image == colour);
[y_pos,x_pos,z_pos] = ind2sub(size(image),coords);
data(colour,:) = mean([x_pos,y_pos,z_pos]);
This loop does the job but it is incredible slow across all 2^16 colours. Is there a way of vectorising this problem?

Accepted Answer

Andrei Bobrov
Andrei Bobrov on 20 Apr 2016
Please try it:
co = (1:2^16)';
[l0,i0] = ismember(image1(:),co);
s = size(image1);
[ii jj k] = ndgrid(1:s(1),1:s(2),1:s(3));
coor = [ii(:),jj(:),k(:)];
i1 = (1:numel(image1))';
v = accumarray(i0(l0),i1(l0),[numel(co) 1],@(x){mean(coor(x,:),1)});
out = [co(~cellfun(@isempty,v)), cell2mat(v)];
  1 Comment
Craig Russell
Craig Russell on 20 Apr 2016
This works! I don't understand how, but it works.

Sign in to comment.

More Answers (2)

Teja Muppirala
Teja Muppirala on 20 Apr 2016
FOR loops are not necessarily slow. This is in R2016a.
%%Make some data...
image = randi(2^16,[30 40 50]);
%% 1. Original method takes 7 seconds. (By the way, it should be MEAN([...],1) not just MEAN([...])
numColors = 2^16;
data = zeros(numColors,3);
for colour = 1:numColors
coords = find(image == colour);
[y_pos,x_pos,z_pos] = ind2sub(size(image),coords);
data(colour,:) = mean([x_pos,y_pos,z_pos],1);
% Elapsed time is 7.447380 seconds
%% Using a for loop more efficiently takes less than 0.1 seconds.
data2 = zeros(numColors,4);
for n1 = 1:size(image,1)
for n2 = 1:size(image,2)
for n3 = 1:size(image,3)
data2(image(n1,n2,n3),:) = data2(image(n1,n2,n3),:) + [1 n2 n1 n3];
data2 = bsxfun(@rdivide,data2(:,2:4),data2(:,1));
% Elapsed time is 0.091517 seconds
%% Show they are the same.
% ans =
% 1

Guillaume on 20 Apr 2016
Edited: Guillaume on 20 Apr 2016
I don't think you can get rid of the colour loop, but you can speed up the loop code with:
[y_pos, x_pos, z_pos] = ndgrid(1:size(image, 2), 1:size(image, 1), 1:size(image, 3));
for colour = 1 : pow2(16)
iscolour = image == colour; %use logical instead of find
data(colour, :) = mean([x_pos(iscolour), y_pos(iscolour), z_pos(iscolour)]);
edit: I've just thought that you can replace the loop with accumarray and I see that Andrei answered with that in the meantime.
edit-edit: Here is a (more readable?) alternative to andrei's answer:
[y_pos, x_pos, z_pos] = ndgrid(1:size(image, 2), 1:size(image, 1), 1:size(image, 3));
datarows = [pow2(16), 1];
data = [accumarray(image(:), x_pos(:), datarows, @mean), ...
accumarray(image(:), y_pos(:), datarows, @mean), ...
accumarray(image(:), z_pos(:), datarows, @mean)];

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by