Reputation: 3148
I have two lists of regions (regionsA
, regionsB
) defined with boundaries (coordinates over an image of size 1024x1024) (.mat
file available here). I want to calculate the overlap of each possible pair of regions between those two lists. And I expected it to be slow, but not that slow.
Currently I am using below code and it takes 20 - 40 seconds for 50x60 objects for me:
intersect_matrix = zeros(length(regionsA), length(regionsB)); % for storing true/false
intersect_matrix_iou = zeros(size(intersect_matrix_iou)); % for storing IoU (intersect over union)
for i = 1:length(regionsA)
for j = 1:length(regionsB)
% get coordinates
x1 = regionsA{i}(:,1);
y1 = regionsA{i}(:,2);
x2 = regionsB{j}(:,1);
y2 = regionsB{j}(:,2);
% move coordinates to origin (start at zero)
% this is not necessary but reduces the size of the mask created by poly2mask(), hence reduces consumed memory is
minX = min([x1(:); x2(:)]);
minY = min([y1(:); y2(:)]);
x1 = x1 - minX;
x2 = x2 - minX;
y1 = y1 - minY;
y2 = y2 - minY;
% create object masks in n x m window
m = max([x1(:); x2(:)]);
n = max([y1(:); y2(:)]);
objMask1 = poly2mask(y1,x1,m,n);
objMask2 = poly2mask(y2,x2,m,n);
save('regionsAB','regionsA', 'regionsB');
intersection = objMask1 & objMask2;
union = objMask1 | objMask2;
% store info
intersect_matrix(i,j) = (bwarea(intersection) ~= 0); % store true/false
if (bwarea(intersection) ~= 0)
intersect_matrix_iou(i,j) = bwarea(intersection) / bwarea(union);
else
intersect_matrix_iou(i,j) = 0; % avoid division by zero
end
end; clear j;
end; clear i;
Before, I approached the problem with polygon operations first. That was still slow (12 sec) but much better. However I had to change that to above code, since for some cases I got NaN
values, as polybool
/ polyarea
/ ... have problems with unconnected areas. Using pixel masks is robust to those problems. This replaced the content of the for-loops:
% polygonal overlap
x1 = regionsA{i}(:,1);
y1 = regionsA{i}(:,2);
x2 = regionsB{j}(:,1);
y2 = regionsB{j}(:,2);
[x_i,y_i] = polybool('intersection',x1,y1,x2,y2);
[x_u,y_u] = polybool('union',x1,y1,x2,y2);
% store info
%intersect_matrix_geo{i, j} = [x_i,y_i];
intersect_matrix(i,j) = ~isempty([x_i,y_i]);
if ~isempty([x_i,y_i])
intersect_matrix_iou(i,j) = polyarea(x_i, y_i) / polyarea(x_u, y_u);
else
intersect_matrix_iou(i,j) = 0;
end
Question: Are there more efficient / faster ways to implement this ? (and still be robust to disconnected intersect regions and such things...)
Upvotes: 1
Views: 593
Reputation: 4195
most of the polygons don't intersect at all so most of the computations are redundant. I used rectint
to test the intersections of the enclosing rectangles of the polygons so I'll have a prior on which polygons might intersect. It gave me much less computations and thus much faster code:
load regionsAB.mat
% get enclosing rectangle for each polygon
poly2rect = @(x) [min(x(:,1)),min(x(:,2)),...
1+max(x(:,1))-min(x(:,1)),1+max(x(:,2))-min(x(:,2))];
rectsA = cell2mat(cellfun(poly2rect,regionsA,'UniformOutput',0)');
rectsB = cell2mat(cellfun(poly2rect,regionsB,'UniformOutput',0)');
% compute rectangle intersections
ar = rectint(rectsA,rectsB);
[ii,jj] = find(ar > 0);
idx = numel(ii);
% test only for intersecting rectangles
intersect_matrix_iou = zeros(numel(rectsA),numel(rectsB)); % for storing IoU (intersect over union)
tic
for idx = 1:numel(ii)
i = ii(idx);
j = jj(idx);
x1 = regionsA{i}(:,1);
y1 = regionsA{i}(:,2);
x2 = regionsB{j}(:,1);
y2 = regionsB{j}(:,2);
% move coordinates to origin (start at zero)
% this is not necessary but reduces the size of the mask created by poly2mask(), hence reduces consumed memory is
minX = min([x1(:); x2(:)]);
minY = min([y1(:); y2(:)]);
% because set x1,y1 outside inner loop
x1 = x1 - minX;
y1 = y1 - minY;
x2 = x2 - minX;
y2 = y2 - minY;
% create object masks in n x m window
m = max([x1(:); x2(:)]);
n = max([y1(:); y2(:)]);
objMask1 = poly2mask(y1,x1,m,n);
objMask2 = poly2mask(y2,x2,m,n);
intersection = objMask1 & objMask2;
union = objMask1 | objMask2;
% store info
intersect_matrix_iou(i,j) = bwarea(intersection) / bwarea(union);
end
intersect_matrix = intersect_matrix_iou > 0;
toc
Upvotes: 1