查找由区域蒙版表示的多边形的角点
BW = poly2mask(x, y, m, n)计算 二元感兴趣区域 (ROI) 掩模， BW，来自 ROI 多边形，表示 由向量 x 和 y 组成。带宽大小 是 m×n。
poly2mask设置黑白像素 多边形内 (X,Y) 为 1 并将多边形外部的像素设置为 0.
问题： 给定这样一个凸四边形的二元掩码BW，确定四个角的最有效方法是什么？
例如，
迄今为止最佳解决方案： 使用 edge 查找边界线，使用霍夫变换查找边缘图像中的 4 条线，然后找到这 4 条线的交点，或者在边缘图像上使用角点检测器。看起来很复杂，我忍不住觉得有一个更简单的解决方案。
顺便说一句，convhull 并不总是返回 4 个点（也许有人可以建议 qhull 选项来防止这种情况）：它也会沿边缘返回几个点。
编辑： Amro 的回答看起来相当优雅和高效。但由于峰值不是唯一的，因此每个真正的角可能有多个“角”。我可以根据θ对它们进行聚类，并平均围绕一个真实的角的“角”，但主要问题是使用order(1:10)。
10 是否足以解释所有角点，或者这是否会排除真实角点处的“角点”？
BW = poly2mask(x, y, m, n)computes a
binary region of interest (ROI) mask,
BW, from an ROI polygon, represented
by the vectors x and y. The size of BW
is m-by-n.
poly2masksets pixels in BW
that are inside the polygon (X,Y) to 1
and sets pixels outside the polygon to
0.
Problem:
Given such a binary mask BW of a convex quadrilateral, what would be the most efficient way to determine the four corners?
E.g.,
Best Solution so far:
Use edge to find the bounding lines, the Hough transform to find the 4 lines in the edge image and then find the intersection points of those 4 lines or use a corner detector on the edge image. Seems complicated, and I can't help feeling there's a simpler solution out there.
Btw, convhull doesn't always return 4 points (maybe someone can suggest qhull options to prevent that) : it returns a few points along the edges as well.
EDIT:
Amro's answer seems quite elegant and efficient. But there could be multiple "corners" at each real corner since the peaks aren't unique. I could cluster them based on θ and average the "corners" around a real corner but the main problem is the use of order(1:10).
Is 10 enough to account for all the corners or will this exclude a "corner" at a real corner?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
这有点类似于 @AndyL 的建议。不过，我使用极坐标中的边界特征而不是切线。
请注意，我首先提取边缘，获取边界，然后将其转换为签名。最后，我们找到边界上距离质心最远的点，这些点构成了找到的角点。 （或者，我们也可以检测角点签名中的峰值）。
以下是完整的实现：
编辑：
为了回应 Jacob 的评论，我应该解释一下，我首先尝试使用一阶/二阶导数找到签名中的峰值，但最终得到了最远的 N 点。 10 只是一个临时值，很难概括（我尝试取 4 与角数相同，但它并没有涵盖所有角点）。我认为对它们进行聚类以删除重复项的想法值得研究。
据我所知，第一种方法的问题是，如果您绘制
rho而不考虑θ，您将得到不同的形状（不是相同的峰） ），因为我们追踪边界的速度是不同的并且取决于曲率。如果我们能够弄清楚如何标准化该效应，我们就可以使用导数获得更准确的结果。This is somewhat similar to what @AndyL suggested. However I'm using the boundary signature in polar coordinates instead of the tangent.
Note that I start by extracting the edges, getting the boundary, then converting it to signature. Finally we find the points on the boundary that are furthest from the centroid, those points constitute the corners found. (Alternatively we can also detect peaks in the signature for corners).
The following is a complete implementation:
EDIT:
In response to Jacob's comment, I should explain that I first tried to find the peaks in the signature using first/second derivatives, but ended up taking the furthest N-points. 10 was just an ad-hoc value, and would be difficult to generalize (I tried taking 4 same as number of corners, but it didn't cover all of them). I think the idea of clustering them to remove duplicates is worth looking into.
As far as I see it, the problem with the 1st approach was that if you plot
rhowithout takingθinto account, you will get a different shape (not the same peaks), since the speed by which we trace the boundary is different and depends on the curvature. If we could figure out how to normalize that effect, we can get more accurate results using derivatives.如果您有图像处理工具箱，则有一个名为
cornermetric可以实现 Harris 角点检测器或 Shi 和 Tomasi 的最小值特征值法。该函数自图像处理工具箱（MATLAB 版本 R2008b）6.2 版起就已存在。使用这个函数，我想出了一种与其他答案略有不同的方法。下面的解决方案基于以下想法：以每个“真实”角点为中心的圆形区域与多边形的重叠量小于以实际位于边缘的错误角点为中心的圆形区域。该解决方案还可以处理在同一角点检测到多个点的情况...
第一步是加载数据：
接下来，使用
cornermetric。请注意，我用原始多边形掩盖了角点度量，因此我们正在寻找多边形内部的角点（即尝试找到多边形的角点像素）。然后使用imregionalmax来查找局部最大值。由于您可以拥有大于 1 个像素且具有相同角点度量的簇，因此我将噪声添加到最大值并重新计算，以便在每个最大区域中仅获得 1 个像素。然后使用bwlabel：然后扩大标记区域（使用
imdilate）带有盘形结构元素（使用 < 创建code>strel)：现在标记的角区域已扩大，它们将部分重叠原始多边形。多边形边缘上的区域将具有大约 50% 的重叠，而位于角上的区域将具有大约 25% 的重叠。函数
regionprops可用于找到每个标记区域的重叠面积，因此重叠量最少的 4 个区域可以被视为真正的角点：现在我们可以使用
查找和ismember：下面是一个菱形区域的测试：
If you have the Image Processing Toolbox, there is a function called
cornermetricwhich can implement a Harris corner detector or Shi and Tomasi's minimum eigenvalue method. This function has been present since version 6.2 of the Image Processing Toolbox (MATLAB version R2008b).Using this function, I came up with a slightly different approach from the other answers. The solution below is based on the idea that a circular area centered at each "true" corner point will overlap the polygon by a smaller amount than a circular area centered over an erroneous corner point that is actually on the edge. This solution can also handle cases where multiple points are detected at the same corner...
The first step is to load the data:
Next, compute the corner metric using
cornermetric. Note that I am masking the corner metric by the original polygon, so that we are looking for corner points that are inside the polygon (i.e. trying to find the corner pixels of the polygon).imregionalmaxis then used to find the local maxima. Since you can have clusters of greater than 1 pixel with the same corner metric, I then add noise to the maxima and recompute so that I only get 1 pixel in each maximal region. Each maximal region is then labeled usingbwlabel:The labeled regions are then dilated (using
imdilate) with a disk-shaped structuring element (created usingstrel):Now that the labeled corner regions have been dilated, they will partially overlap the original polygon. Regions on an edge of the polygon will have about 50% overlap, while regions that are on a corner will have about 25% overlap. The function
regionpropscan be used to find the areas of overlap for each labeled region, and the 4 regions that have the least amount of overlap can thus be considered as the true corners:And we can now get the pixel coordinates of the corners using
findandismember:And here's a test with a diamond shaped region:
我喜欢通过边界来解决这个问题，因为它可以将这个问题从 2D 问题简化为 1D 问题。
使用图像处理工具包中的
bwtraceboundary()提取边界上的点列表。然后将边界转换为一系列切向量（有多种方法可以做到这一点，一种方法是减去沿着边界从第 i+delta 点开始的第 i 个点。）获得向量列表后，计算相邻向量的点积。点积最小的四个点就是你的角点！
如果您希望算法适用于具有任意数量顶点的多边形，则只需搜索比中值点积低一定数量标准差的点积即可。
I like to solve this problem by working with a boundary, because it reduces this from a 2D problem to a 1D problem.
Use
bwtraceboundary()from the image processing toolkit to extract a list of points on the boundary. Then convert the boundary into a series of tangent vectors (there are a number of ways to do this, one way would be to subrtact theith point along the boundary from thei+deltath point.) Once you have a list of vectors, take the dot product of adjacent vectors. The four points with the smallest dot products are your corners!If you want your algorithm to work on polygons with an abritrary number of vertices, then simply search for dot products that are a certain number of standard deviations below the median dot product.
我决定使用 Harris 角点检测器（这是一个更正式的描述）来获取角点。这可以如下实现：
这里，由于高斯窗函数平滑了强度变化，因此具有多个角的问题。下面是带有
hot颜色图的角落的缩放版本。I decided to use a Harris corner detector (here's a more formal description) to obtain the corners. This can be implemented as follows:
Here, the problem with multiple corners thanks to Gaussian windowing function which smooths the intensity change. Below, is a zoomed version of a corner with the
hotcolormap.以下是使用 Ruby 和 HornetsEye 的示例。基本上，该程序创建量化索贝尔梯度方向的直方图以找到主导方向。如果找到四个主要方向，则拟合线，并且假定相邻线之间的交点是投影矩形的角。
Here's an example using Ruby and HornetsEye. Basically the program creates a histogram of the quantised Sobel gradient orientation to find dominant orientations. If four dominant orientations are found, lines are fitted and the intersections between neighbouring lines are assumed to be the corners of the projected rectangle.