如何从连续的单元格块的外部单元格创建多边形

Question

我在下面用 Matlab 绘制了一块连续的单元格。

必须确定红色补丁的外部单元格，然后连接这些单元格中心的多边形会给我一个多边形。我如何计算连续补丁的外部单元格？

我有一个整数数组，其元素表示红色补丁中的单元格，例如，

a=[1;64;23;456;345];

每一个元素，比如64对应图片中的一个单元格，也就是属于红色patch的单元格。

解决问题的动机是处理边数最少的多边形，而不是处理这么多单元。它减慢了计算速度。凸包不够好。我根本不希望生成的多边形与棕色区域重叠。

我的建议是下图中左边的情况，但看起来很难看。因此，更好的方法是跳过仅与外部棕色区域共享一个点的单元格。我希望我的外部细胞只是那些与外部棕色区域共享不止一个点的细胞。

但我们要避免在生成的多边形中出现大量边！

Answer 1

使用图像处理工具箱您可以在图像上应用 dilation，然后在膨胀结果和原始图像之间应用 and operator。

A = imread('bnhfm.png');
B = A & imdilate(~A, true(3));
imshow(B);
imwrite(B, 'result.png');

Answer 2

虽然@rahnema1 的回答真的很酷，但我认为 OP 正在询问更多如何根据描述的规则提取边集。

这是我识别所有 10 个包含边缘的 2x2 像素模式的方法。假设矩阵 A 具有 1s 和 0s (A = zeros(ny, nx); A(a) = 1) 的图像：

% we identify patterns with edges over 2x2 patches, describing with
% the first 4 binary values what pixels are set, and with the next 2
% the edge with 2 indices over the 2x2 patch
patterns = [
 0,1,0,1,  3,4 % vertical edge at rhe right 
 1,0,1,0,  1,2 % vertical edge at the left
 0,0,1,1,  2,4 % horizontal edge at the bottom
 1,1,0,0,  1,3 % horizontal edge at the top
 1,0,0,1,  1,4 % diagonal edge
 0,1,1,0,  2,3 % diagonal edge
 1,0,1,1,  1,4 % diagonal edge, extra pixel set
 1,1,0,1,  1,4 % diagonal edge, extra pixel set
 1,1,1,0,  2,3 % diagonal edge, extra pixel set
 0,1,1,1,  2,3 % diagonal edge, extra pixel set
];

% 2x2 patches (matrix form)
P00 = A(1:end-1,1:end-1);
P10 = A(2:end,1:end-1);
P01 = A(1:end-1,2:end);
P11 = A(2:end,2:end);

% edge unique identifier using powers of 2
id = @(p00,p01,p10,p11) 1*p00 + 2*p10 + 4*p01 + 8*p11;
P = id(P00,P01,P10,P11); % vectorized pattern identification

% edges
e0 = []; % from (i,j)
e1 = []; % to (i,j)
for i = 1:size(patterns, 1) % small loop over the 10 patterns
  p = patterns(i, :);
  E = (P == id(p(1),p(2),p(3),p(4))); % pattern search, vectorized
  [c,r] = ind2sub(size(E), find(E));
  [c0,r0] = ind2sub([2,2], p(5));
  [c1,r1] = ind2sub([2,2], p(6));
  e0 = [e0; c+c0, r+r0];
  e1 = [e1; c+c1, r+r1];
end

这是将它应用到您的图像的结果（我使用 GIMP 进行捕获、调整大小和过滤，所以图像可能完全不一样）：

X = [e0(:,2) e1(:,2)];
Y = size(A,1) - [e0(:,1) e1(:,1)];
plot(X', Y', '.-')

我假设一旦有了上述集合，获得描述多边形（或多边形）的边的有序序列就不是这里的主要问题。

Answer 3

我首先处理了您问题中的示例图像以创建一个逻辑掩码（您已经有一个如何做到这一点的示例）。

有了这个遮罩后，就可以使用 bwtraceboundary function from the Image Processing Toolbox 轻松生成所需的多边形。这将为您提供一组像素索引，以便围绕您的蒙版区域的周边排列：

[r, c] = find(mask, 1);
coords = bwtraceboundary(mask, [r c], 'N');

我们可以这样想象它：

imagesc(mask);
colormap([0.9 0.9 0.9; 0.6 0.6 0.6]);
axis equal
set(gca, 'XLim', [0.5 0.5+size(mask, 2)], 'YLim', [0.5 0.5+size(mask, 1)]);
hold on;
plot(coords(:, 2), coords(:, 1), 'r', 'LineWidth', 2);
plot(coords(1, 2), coords(1, 1), 'go', 'LineWidth', 2);

红线的坐标从绿色圆圈开始，顺时针围绕遮罩区域的周边像素移动。

如果您希望生成沿着区域的周边像素 edges 而不是周边像素 centers 的边界轮廓，您可以使用 to a 中的解决方案。这将产生以下结果：

如何从连续的单元格块的外部单元格创建多边形

How to create a polygon out of the outer cells of a contiguous patch of cells

matlab

geometry

computational-geometry