CODEWITHSUNDEEP
matlaboverlap
Honeybear
Honeybear

Reputation: 3148

Is there an efficient way to calculate overlap between several boundaries in matlab?

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

Answers (1)

user2999345
user2999345

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

Related Questions