我有一些图像，其中包括凸多边形和非凸多边形。每个图像都包含一个多边形。我需要检测角坐标并需要按顺时针或逆时针顺序对它们进行排序。对于凸多边形，我使用Harris 角点检测来检测角点，使用凸包对点进行排序。但我不知道如何对非凸多边形进行排序。由于我的输入是图像，我认为一些图像处理技术可能有助于通过沿着多边形边缘移动来对它们进行分类。有没有复杂度最低的方法？
示例图像：
我随机命名了角落。
预期输出：
我希望按此顺序
1 3 5 9 4 2 8 7 6 10或1 10 6 7 8 2 4 9 5 3. 你可以从任何时候开始，不一定1
编辑1：
在rayryeng 的解决方案适用于所有凸多边形以及一些非凸多边形之后，有一些非凸多边形与他的算法不匹配。
这是一个例子
另一种方法是使用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
此方法也适用于相对于质心不平衡的多边形，例如第二个演示图像。
为了好玩，我展示了第三张图像，它在质心的另一侧有一个顶点，作为不平衡多边形的更清晰示例。我的方法也正确解析了这个图像。
这是图像处理中的常见问题。典型的答案是找到形状的质心，并找到质心与每个角点之间的角度。您将确保表示角度，以便它们在[0,360)度数之间变化。一旦你有了这个，你对角度进行排序，然后使用结果顺序来确定点的顺序。
您展示的图像需要进行一些预处理，以便我开始处理它。我直接从 StackOverflow 读取图像，然后反转图像，使黑星变成白色。我还需要删除数字，所以我使用bwareaopen删除任何小的文本区域。完成后，我通过 对该图像执行角点检测corner，并将 设置QualityFactor为 0.3，以便检测 10 个角点。非常具体：
%// Read image from StackOverflow
im = rgb2gray(imread('http://i.stack.imgur.com/dpbpP.jpg'));
%// Threshold the image and area open it
im_thresh = im <= 100;
im_open = bwareaopen(im_thresh, 50);
%// Detect corner points
out = corner(im_open, 'QualityLevel', 0.3);
%// Show the image with the corner points
imshow(im_open);
hold on
plot(out(:,1), out(:,2), 'r.')
im_open包含我们最终处理的图像。这就是我得到的：
现在，让我们找到质心。这可以通过找到非零位置的坐标并找到每个维度的平均值来简单地完成：
[rows, cols] = find(im_open);
cenX = mean(cols);
cenY = mean(rows);
cenX并cenY包含(x,y)图像质心的位置。只是为了确保我们做对了：
imshow(im_open);
hold on;
plot(cenX, cenY, 'r.', 'MarkerSize', 18);
我们得到：
非常好。现在，out在前面的代码中包含(x,y)了角点的点。您所要做的就是确定从质心到每个角点的角度，然后对角度进行排序。您将使用此排序顺序重新排列角点，从而为您提供排列好的点。如果要顺时针，则需要按升序对值进行排序。如果要逆时针，则需要按降序排序。我会让你自己决定，但我会写代码让你两者都做。因此，只需这样做：
%// Determine angles (in degrees)
angles = atan2d(out(:,2) - cenY, out(:,1) - cenX);
%// Any negative angles, add 360 degrees to convert to positive
angles(angles < 0) = 360 + angles(angles < 0);
%// Sort the angles
[~,ind] = sort(angles); %// clockwise
%[~,ind] = sort(angles, 'descend'); %// counter-clockwise
%// Re-arrange the corner points to respect the order
out_reorder = out(ind,:);
现在最后的测试是绘制这些点，并在每个点旁边绘制一个数字，看看我们是否正确。这可以通过以下方式完成：
%// Show image
imshow(im_open);
hold on;
%// Show points
plot(out_reorder(:,1), out_reorder(:,2), 'r.', 'MarkerSize', 18);
%// Place a textbox at each point and show a sequence number
for idx = 1 : size(out_reorder,1)
text(out_reorder(idx,1), out_reorder(idx,2), num2str(idx), 'FontSize', 24, 'Color', 'green');
end
我们得到：
在我看来很好！因此，out_reorder为您提供角点，以便它们遵循顺时针顺序或逆时针顺序。您连续遇到的每一行都会为您提供下一个点，该点自然遵循您寻找的顺时针或逆时针顺序。
还要注意编号的开始位置。角度 0 由相对于质心指向东方的水平线定义。因此，当我们以升序开始时，最接近 0 的点是您看到数字 1 的位置。在 1 之后，您会看到它按顺时针顺序扫描，直到我们用完角点。