有没有一种有效的方法来计算 matlab 中几个边界之间的重叠？

Question

我有两个区域列表（regionsA、regionsB）定义了边界（在尺寸为 1024x1024 的图像上的坐标）（.mat 文件 available here）。我想计算这两个列表之间每对可能的区域的重叠。我预计它会很慢，但不会那么慢。

目前我正在使用以下代码，50x60 对象对我来说需要 20 - 40 秒：

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;

之前，我都是先从多边形操作着手处理问题。那仍然很慢（12 秒）但好多了。但是我不得不将其更改为上面的代码，因为在某些情况下我得到了 NaN 值，因为 polybool / polyarea / ... 未连接区域存在问题。使用像素蒙版可以解决这些问题。这替换了 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

问题：有没有更有效/更快速的方法来实现这个？（和对于断开连接的交叉区域和类似的东西仍然很稳健......）

Answer 1

大部分多边形根本不相交，因此大部分计算都是多余的。我使用 rectint 来测试多边形的封闭矩形的交点，因此我将先验确定多边形可能相交。它给了我更少的计算和更快的代码：

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

有没有一种有效的方法来计算 matlab 中几个边界之间的重叠？

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

matlab

overlap