matlab - 按顺时针顺序检测非凸多边形的角坐标 MATLAB

Question

我有一些图像，其中包括凸多边形和非凸多边形。每个图像只包含一个多边形。我需要检测角坐标并需要按顺时针或逆时针顺序对它们进行排序。对于凸多边形，我使用 Harris corner detection用于检测角和convexhull用于对点进行排序。但我不知道如何对非凸多边形进行排序。由于我的输入是图像，我认为一些图像处理技术可能有助于通过沿着多边形的边缘移动来对它们进行分类。有没有复杂度最低的方法？

示例图片:

我随机命名了角。

预期输出:

我希望角坐标按此顺序1 3 5 9 4 2 8 7 6 10 或 1 10 6 7 8 2 4 9 5 3。你可以从任何一点开始，不一定是1

编辑 1:

在 rayryeng's 之后解决方案适用于所有凸多边形以及一些非凸多边形，但有一些非凸多边形不适合他的算法。

这是一个例子

Answer 1

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

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

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

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

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

让我们想象一下我们检测到的边缘

figure; imshow(A_edges);

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

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

让我们想象一下我们的初始角排序

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

您可能没有注意到的另一件事是，它们并不直接位于边缘上。我将从找到沿边到每个角点的最近点开始，然后我将可视化红色的角和绿色的最近的边缘点。

[~, 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;

为了计算每个拐角围绕边缘的距离，我们将使用拐角点近似，即边缘上的A_edge_corners(绿点)而不是拐角点本身A_corners(红点)。

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

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

我们从最右边的角开始，远离角的像素值增加。但这并不是我们想要的。如果我们使用这些值对角进行排序，我们最终会按照距初始点的距离进行排序。

[~, 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

要解决这个问题，我们只需要打断边，使排序只从初始点开始一个方向。如果您对顺时针或逆时针顺序感兴趣，则需要根据边的方向根据一组规则断开边。如果方向无关紧要，您可以简单地找到与初始角相邻的像素，并在那里断开边缘。

%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;

现在沿边到初始点的距离只能走一条路

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

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

[~, 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

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

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