以顺时针顺序检测非凸多边形的角坐标MATLAB [英] Detect corner coordinates of a non-convex polygon in clockwise order MATLAB

问题描述

我有一些图像包括凸多边形和非凸多边形。每个图像只包含一个多边形。我需要检测角坐标，并需要按顺时针或逆时针顺序对它们进行排序。对于凸多边形，我使用解决方案，适用于所有凸多边形以及对于某些非凸多边形，有一些非凸多边形与他的算法不相符。

这是一个例子

解决方案

另一种方法是使用 bwdistgeodesic 按边缘距离查找角落的顺序。这适用于任何可以检测连续边缘的多边形。

我们首先从Stack Overflow中加载图像并将其转换为黑白图像更容易找到边缘

  A = imread（'http://i.stack.imgur.com/dpbpP.jpg ）; 
 A_bw = im2bw（A，100/255）; ％二进制图像
 A_bw1 = imcomplement（A_bw）; ％反转二进制图像
  

bwmorph 函数提供很多操作黑白图像的选项。我们将使用 remove 选项来查找多边形的边缘，但如果您愿意，也可以使用另一个边缘检测器。

 ％找到边缘
 A_edges = bwmorph（A_bw，'remove'）; 
 [edge_x，edge_y] = find（A_edges'）; 
  

让我们看到我们检测到的边缘

 图。 imshow（A_edges）; 
  

好的，我们有一个很好的清晰连续边缘。现在让我们找到角落。我使用一角，但你可以替换你喜欢的角落探测器

  A_corners =角（A_bw1，'QualityLevel'，。3）; 
  

让我们想象一下我们的初始角点订购

 图。 imshow（A_bw1）; 
持有
图（A_corners（：，1），A_corners（：，2），'r。'，'MarkerSize'，18）
 text（A_corners（：，1）， A_corners（：，2），strsplit（num2str（1：length（A_corners））），'Color'，'g'，'FontSize'，24）; 
扣除
  

您可能不会注意到的另一件事是它们不是直接在边缘。我将首先找到沿着边缘到每个角点的最近点，然后我将可视化红色的角落和最接近绿色的边缘点。

  [〜，ind] = min（pdist2（A_corners，[edge_x，edge_y]），[]，2）; 
 A_edge_corners = [edge_x（ind），edge_y（ind）]; 
 
数字; imshow（A_edges）; 
持有; 
 plot（A_corners（：，1），A_corners（：，2），'r。'，'MarkerSize'，18）
 plot（A_edge_corners（：，1），A_edge_corners（：，2） ，'g。'，'MarkerSize'，18）
延迟; 
  

要计算每个角落边缘的距离，我们将使用角点近似值， A_edge_corners （绿点）在边缘而不是角点本身 A_corners （红点）。

现在我们需要使用的所有部分 bwdistgeodesic 。此函数查找黑白图像中每个非零像素到种子点的距离。我们感兴趣的是从初始角到边缘上每个点的距离。我们来试试吧。

 ％计算种子角的距离
 first_corner = A_edge_corners（1，:); 
 D = bwdistgeodesic（A_edges，first_corner（1），first_corner（2））; 
数字;于imagesc（d）; 
  

我们从最右边的角落开始，远离角落的像素值增加。但这不是我们想要的。如果我们使用这些值订购角落，我们最终会得到距离初始点的距离。

  [〜，corner_order ] = sort（D（sub2ind（size（D），A_edge_corners（：，2），A_edge_corners（：，1））））; 
 A_corners_reorder1 = A_corners（corner_order，:); 
 
数字; imshow（A_bw1）; 
持有
 plot（A_corners_reorder1（：，1），A_corners_reorder1（：，2），'r。'，'MarkerSize'，18）
 text（A_corners_reorder1（：，1）， A_corners_reorder1（：，2），strsplit（num2str（1：length（A_corners））），'Color'，'g'，'FontSize'，24）; 
扣除
  

为了解决这个问题，我们只需打破边缘，以便排序只进入从最初点开始的一个方向。如果您对顺时针或逆时针顺序感兴趣，则需要根据一组规则打破边缘，具体取决于边缘的方向。如果方向无关紧要，你可以简单地找到初始角落的相邻像素，并在那里打破边缘。

 ％通过移除第一个拐角附近的像素将边缘分成一个路径
％如果拐角靠近图像的边缘，则需要检查
％边缘条件
 window = A_edges （first_corner（2）-1：first_corner（2）+ 1，first_corner（1）-1：first_corner（1）+1）; 
 window（2,2）= 0; ％排除角本身
 [x，y] = find（window，1）; 
 A_edges（first_corner（2）+ x-2，first_corner（1）+ y-2）= 0; 
 
数字; imshow（A_edges）; 
持有; 
 plot（first_corner（1），first_corner（2），'r。'，'MarkerSize'，18）
 hold off; 
  

现在沿着边缘的初始点的距离只能沿着一条路径

 ％查找顺序沿边缘的像素
 D = bwdistgeodesic（A_edges，first_corner（1），first_corner（2））; 
数字;于imagesc（d）; 
  

这为我们提供了所需的边缘排序

  [〜，corner_order] = sort（D（sub2ind（size（D），A_edge_corners（：，2），A_edge_corners（：，1））））; 
 A_corners = A_corners（corner_order，:); 
 
数字; imshow（A_bw1）; 
持有
图（A_corners（：，1），A_corners（：，2），'r。'，'MarkerSize'，18）
 text（A_corners（：，1）， A_corners（：，2），strsplit（num2str（1：length（A_corners））），'Color'，'g'，'FontSize'，24）; 
扣除
  

此方法也适用于相对于质心不平衡的多边形，例如第二个演示图像。

为了好玩，我提出了第三个图像，它在质心的另一侧有一个顶点，作为不平衡多边形的一个更清晰的例子。我的方法也正确解析这个图像。

I have some images which includes both convex as well as non-convex polygons. Each image contains exactly one polygon. I need to detect the corner coordinates and need to sort them in clock-wise or counter-clockwise order. For convex polygons, I use Harris corner detection for detecting corners and convexhull for sorting the points. But i dont have any idea on how to sort non-convex polygon. As my inputs are images, i think some Image Processing Technique might help to sort them out by moving alongside the edge of the polygon. Is there any way with least complexity?

Example Image:

I have named the corners randomly.

Expected output:

I expect Corner coordinates in this order 1 3 5 9 4 2 8 7 6 10 or 1 10 6 7 8 2 4 9 5 3. You can start at any point, not necessarily 1

Edit 1:

After rayryeng's solution, which works for all convex polygons as well as for some non-convex polygon, there are some non-convex polygons which doesn't go well with his algorithm.

Here is an example

解决方案

Another approach is to use bwdistgeodesic to find order the corners by their distance along your edge. This should work for any polygon where you can detect a continuous edge.

We start by loading in the image from Stack Overflow and converting it into a black and white image to make it easier to find the edge

A = imread('http://i.stack.imgur.com/dpbpP.jpg');
A_bw = im2bw(A,100/255);  %binary image
A_bw1 = imcomplement(A_bw);   %inverted binary image

The bwmorph function provides a lot of options for manipulating black and white images. We're going to use the remove option to find the edge of our polygon, but you could also use another edge detector if you prefer.

%Find the edges
A_edges = bwmorph(A_bw, 'remove');
[edge_x, edge_y] = find(A_edges');

Let's visualize the edges we detected

figure; imshow(A_edges);

Okay, we have a nice clear continuous edge. Now let's find the corners. I use corner, but you could substitute your favorite corner detector

A_corners = corner(A_bw1, 'QualityLevel',.3);

Let's visualize our initial corner ordering

figure; imshow(A_bw1);
hold on
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18)
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

Another thing you might not notice, is that they are not directly on the edges. I'll start by finding the closest point along the edge to each corner point, and then I'll visualize corners in red and the closest edge points in green.

[~, ind] = min(pdist2(A_corners, [edge_x, edge_y]), [], 2);
A_edge_corners = [edge_x(ind), edge_y(ind)];

figure; imshow(A_edges);
hold on;
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18)
plot(A_edge_corners(:,1), A_edge_corners(:,2),'g.', 'MarkerSize', 18)
hold off;

To calculate the distance around the edge for each corner, we'll use the corner point approximation, A_edge_corners (green point) on the edge rather than the corner point itself A_corners (red point).

Now we have all the pieces we need to use bwdistgeodesic. This function finds the distance to a seed point for each non-zero pixel in a black and white image. We are interested in the distance from an initial corner to each point on the edge. Let's try it out.

% Calculate distance from seed corner
first_corner = A_edge_corners(1,:);
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2));
figure; imagesc(D);

We're starting from the right most corner and the pixels moving away from the corner increase in value. But this isn't quite what we want. If we order the corners using these values, we end up with an ordering in distance from the initial point.

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1))));
A_corners_reorder1 = A_corners(corner_order, :);

figure; imshow(A_bw1);
hold on
plot(A_corners_reorder1(:,1), A_corners_reorder1(:,2),'r.', 'MarkerSize', 18)
text(A_corners_reorder1(:,1), A_corners_reorder1(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

To solve this problem, we just have to break the edge so that the ordering only goes in one direction from the initial point. If you are interested in a clockwise or a counter-clockwise ordering, you would need to break the edge according to a set of rules depending on the orientation of the edge. If the direction doesn't matter you can simply find an adjacent pixel to the initial corner, and break the edge there.

%Break the edge into one path by removing a pixel adjacent to first corner
%If the corner is near the edge of the image, you would need to check for
%edge conditions
window = A_edges(first_corner(2)-1:first_corner(2)+1, first_corner(1)-1:first_corner(1)+1);
window(2,2) = 0; %Exclude the corner itself
[x, y] = find(window, 1);
A_edges(first_corner(2)+x-2, first_corner(1)+y-2) = 0;  

figure; imshow(A_edges);
hold on;
plot(first_corner(1), first_corner(2), 'r.', 'MarkerSize', 18)
hold off;

Now the distance from the initial point along the edge can only follow one path

%Find order the pixels along edge
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2));
figure; imagesc(D);

This gives us the desired ordering of edges

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1))));
A_corners = A_corners(corner_order, :);

figure; imshow(A_bw1);
hold on
plot(A_corners(:,1), A_corners(:,2),'r.', 'MarkerSize', 18)
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

This method also works on polygons that are unbalanced with respect to the centroid, such as the second demo image.

For fun, I present a third image, which has a vertex on the opposite side of the centroid, as a clearer example of an unbalanced polygon. My method also correctly parses this image.

这篇关于以顺时针顺序检测非凸多边形的角坐标MATLAB的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！