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

Question

我有一些图像,包括凸多边形和非凸多边形.每个图像只包含一个多边形.我需要检测角坐标,并需要按顺时针或逆时针顺序对它们进行排序.对于凸多边形,我使用Harris角点检测来检测角点和凸包线以对点进行排序.但我对如何排序非凸多边形没有任何想法.由于我的输入是图像,我认为一些图像处理技术可能有助于通过沿多边形边缘移动来对它们进行排序.有没有办法最简单？

示例图片:

我随机命名了角落.

预期产量:

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

编辑1:

在对所有凸多边形以及一些非凸多边形起作用的rayryeng解之后,有一些非凸多边形与他的算法不相符.

这是一个例子

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

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

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

Answer 2

这是图像处理中的常见问题.典型的答案是找到形状的质心,并找到质心和每个角点之间的角度.您将确保表示角度,使它们在[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之后,您会看到它以顺时针顺序扫过,直到我们用完了角点.