按顺时针顺序检测非凸多边形的角坐标 MATLAB
Detect corner coordinates of a non-convex polygon in clockwise order MATLAB
我有一些图像，其中包括凸多边形和非凸多边形。每个图像只包含一个多边形。我需要检测角坐标并需要按顺时针或逆时针顺序对它们进行排序。对于凸多边形，我使用 Harris corner detection for detecting corners and 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 解决方案适用于所有凸多边形以及一些非凸多边形之后，有一些非凸多边形不适合他的算法。
举个例子
这是图像处理中的常见问题。典型的答案是找到形状的质心，并找到质心与每个角点之间的角度。您将确保所表示的角度在 [0,360) 度之间。一旦你有了这个，你就可以排序角度，然后使用结果顺序来确定点的顺序。
您提供的图像需要一些预处理，以便我可以开始处理它。我直接从 Whosebug 读取图像，然后反转图像，使黑星变成白星。我还需要删除数字，所以我使用 bwareaopen to remove any small areas of text. Once that's done, I perform a corner detection on this image via corner，并将 QualityFactor 设置为 0.3，这样我就可以检测到 10 个角。非常具体：
%// Read image from Whosebug
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 之后，您会看到它按顺时针顺序扫描，直到我们 运行 超出角点。
另一种方法是使用 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
此方法也适用于相对于质心不平衡的多边形，例如第二个演示图像。
为了好玩，我展示了第三张图片，它在质心的另一侧有一个顶点，作为不平衡多边形的更清晰的例子。我的方法也正确地解析了这张图片。
我有一些图像，其中包括凸多边形和非凸多边形。每个图像只包含一个多边形。我需要检测角坐标并需要按顺时针或逆时针顺序对它们进行排序。对于凸多边形，我使用 Harris corner detection for detecting corners and 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 解决方案适用于所有凸多边形以及一些非凸多边形之后，有一些非凸多边形不适合他的算法。
举个例子
这是图像处理中的常见问题。典型的答案是找到形状的质心，并找到质心与每个角点之间的角度。您将确保所表示的角度在 [0,360) 度之间。一旦你有了这个，你就可以排序角度，然后使用结果顺序来确定点的顺序。
您提供的图像需要一些预处理，以便我可以开始处理它。我直接从 Whosebug 读取图像，然后反转图像，使黑星变成白星。我还需要删除数字，所以我使用 bwareaopen to remove any small areas of text. Once that's done, I perform a corner detection on this image via corner，并将 QualityFactor 设置为 0.3，这样我就可以检测到 10 个角。非常具体：
%// Read image from Whosebug
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 之后，您会看到它按顺时针顺序扫描，直到我们 运行 超出角点。
另一种方法是使用 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
此方法也适用于相对于质心不平衡的多边形，例如第二个演示图像。
为了好玩，我展示了第三张图片，它在质心的另一侧有一个顶点，作为不平衡多边形的更清晰的例子。我的方法也正确地解析了这张图片。