Existe-t-il un moyen efficace de calculer le chevauchement entre plusieurs limites dans MATLAB?

Question

J'ai deux listes de régions (regionsA, regionsB) définies avec des limites (coordonnées sur une image de taille 1024x1024) (.mat fichier available here). Je veux calculer le chevauchement de chaque paire possible de régions entre ces deux listes. Et je m'attendais à ce que ce soit lent, mais pas si lent.

Actuellement, je suis en utilisant le code ci-dessous et il prend 20 - 40 secondes pour 50x60 objets pour moi:

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; 

Avant, je me suis approché d'abord le problème avec les opérations de polygone. C'était encore lent (12 sec) mais beaucoup mieux. Cependant, j'ai dû changer cela au code ci-dessus, puisque dans certains cas, j'ai obtenu NaN valeurs, comme polybool/polyarea/... ont des problèmes avec les zones non connectées. L'utilisation de masques de pixels est robuste à ces problèmes. Cette remplace le contenu des boucles for:

% 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: Y at-il des moyens plus efficaces/plus rapides à mettre en œuvre ce?

Answer 1

La plupart des polygones ne se croisent pas du tout, donc la plupart des calculs sont redondants. J'ai utilisé rectint pour tester les intersections des rectangles englobants des polygones, donc je vais avoir un avant sur lequel les polygones pourraient se croiser. Il m'a donné beaucoup moins de calculs et donc beaucoup plus rapide 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