如何从连续的单元格的外部单元格中创建多边形 [英] How to create a polygon out of the outer cells of a contiguous patch of cells

问题描述

我在Matlab下绘制了连续的单元格片。

必须确定红色补丁的外部单元，然后加入一个多边形，这些细胞会给我一个多边形。如何计算连续修补程序的外部单元格？

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

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

每个元素（例如64）对应于图像中的一个单元格，它是属于红色补丁。

解决问题的动机是处理边数最少的多边形，而不是很多单元。它会减慢计算速度。凸面船体不够好。我不想让生成的多边形与棕色区域重叠。

我在暗示的情况是左下图，但它看起来很丑。所以更好的方法就是跳过只与外部棕色区域共享单个点的单元格。我希望我的外层细胞只能是那些与褐色区域外的细胞共享更多的细胞。

由此产生的多边形！

解决方案<尽管@ rahnema1的答案非常酷，但我认为OP会问如何根据描述的规则提取边集。

这是我的方法，确定包含边缘的所有10个2x2像素图案。假设矩阵 A 的图像为 1 s且 0 s（ A =零（ny，nx）; A（a）= 1 ）：

 ％我们用2x2贴图上的边来识别模式，用
％描述前四个二进制值设置了哪些像素，并用下一个2 
％ 2x2补丁
 patterns = [
 0,1,0,1，3,4％垂直边缘在右边
 1,0,1,0，1,2％垂直边缘在最左边的
 0,0,1,1,2,4％底部的水平边缘
 1,1,0,0，顶部的水平边缘
 1， 0,0,1,1,4％对角线边缘
 0,1,1,0,2,3％对角线边缘
 1,0,1,1,4,4％对角线边缘，额外像素集
 1,1,0,1,4,4％对角线边缘，额外像素集
 1,1,1,0,2,3％对角线边缘，额外像素集
 0,1,1,1,2,3％对角线边缘，额外像素集
]; 
 
％2x2补丁（矩阵形式）
 P00 = A（1：end-1,1：end-1）; 
 P10 = A（2：结束，1：结束-1）; 
 P01 = A（1：end-1,2：end）; 
 P11 = A（2：结束，2：结束）; 
 
％使用2的幂的边唯一标识符
 id = @（p00，p01，p10，p11）1 * p00 + 2 * p10 + 4 * p01 + 8 * p11; 
 P = id（P00，P01，P10，P11）; ％向量化模式识别
 
％边缘
 e0 = []; ％来自（i，j）
 e1 = []; ％（i，j）
 for i = 1：size（patterns，1）％10个模式的小循环
 p = patterns（i，:); 
 E =（P == id（p（1），p（2），p（3），p（4）））; ％模式搜索，向量化
 [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'，'.-'）
  

我假设获得描述多边形（或多边形）的边的有序序列在这里不是主要问题上述设置。

I have below a contiguous patch of cells plotted in Matlab.

The outer cells of the red patch have to be determined and then a polygon joining the centers of these cells will give me a polygon. How do i compute the outer cells of the contiguous patch?

I have an array of integers whose elements denote the cell in the red patch, for example,

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

Each element , say 64 corresponds to a cell in the image, and it is the cell belonging to the red patch.

The motivation to solve the problem is to deal with a polygon with minimal number of edges rather than so many cells. it slows down computation. Convex hull is not good enough. I don't want the resulting polygon to overlap with the brown area at all.

What i am suggesting is the case on the left in image below but it seems ugly. So a better way would be as in right to just skip the cells only sharing a single point with the outer brown area. I would like my outer cells to then be only those that share more than just a single point with the outer brown area.

But we want to avoid large number of edges in the resultant polygon!

解决方案

Although the answer by @rahnema1 is really cool, I think the OP is asking more how to extract the set of edges according to the described rules.

Here is my approach identifying all the 10 patterns of 2x2 pixels that contain edges. Assuming the matrix A has the image with 1s and 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

And here the result applying it to your image (I used GIMP for capture, resize and filter, so maybe the image is not exactly the same):

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

I am assuming that obtaining an ordered sequence of edges describing the polygon (or polygons) is not the main problem here once you have the aforementioned set.

这篇关于如何从连续的单元格的外部单元格中创建多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！