如何检查四个点是否形成矩形

Question

我正在开发一个形状识别应用程序。目前，一组点（x，y）由角点检测器确定（红点，图像2）。其中四个点（在红色框架中，img。2）是一个矩形的顶点（有时是略微变形的矩形）。最好的方法是如何在其他点中找到它们？

这里是一个输入图像的例子： 角点检测后，它看起来像这样：

- sowizz

Answer 1

这不是你问题的答案，只是一个建议。

在我看来，角点检测器并不是检测矩形的好方法 - 如mathematician1975所建议的那样，计算所有点之间的距离需要很长时间。在这种情况下，你必须使用另一种技术：

1. 该印章为紫色，因此你应该首先进行颜色分割。
2. 完成步骤1后，可以在二值图像上使用霍夫变换（Houhg transform）检测线条，或者找到图像中的所有轮廓。
3. 最后一步是检测矩形。

更新:

以下是另一种在灰度图像中也应适用的解决方案。

1. 通过阈值将图片转换为1位图像(我使用了200作为阈值，范围是0-255)。
2. 在新图像中查找所有面积大于某个常数(我选择1000)的轮廓(contours)。
3. 找到每个轮廓的边界矩形，并进行检查:

ContourArea / BoundingReactangleArea > constant

我将这个constant视为0.9。

这个算法给了我下面的结果：

以下是OpenCV代码：

Mat src = imread("input.jpg"), gray, result;
vector<vector<Point> > contours;
vector<Vec4i> hierarchy;

result = Mat(src.size(), CV_8UC1);

cvtColor(src, src, CV_BGR2GRAY);
threshold(src, gray, 200, 255, THRESH_BINARY_INV);
findContours(gray, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0));

result = Scalar::all(0);
for (size_t i=0; i<contours.size(); i++)
{
    Rect rect = boundingRect(contours[i]);
    if (rect.area() > 1000)
    {
        double area = contourArea(contours[i]);
        if (area/rect.area() > 0.9)
        {
            drawContours(result, contours, i, Scalar(255), -1);
        }
    }
}

- ArtemStorozhuk

---

@HighPerformanceMark 你可以使用minAreaRect。 - ArtemStorozhuk

确实，但这并不是您的解决方案所做的事情。 - High Performance Mark

@sowizz，将阈值改为210怎么样？或者在不同情况下阈值也可以不同吗？ - ArtemStorozhuk

@HighPerformanceMark 是的，但是如果您取轮廓面积的极端点，您可以在图像上绘制线条，然后填充该区域内创建的孔。 - sowizz

@Astor，阈值的取值范围在其他文档中为80到230。 - sowizz

Answer 2

计算在4个不同点之间，每一对点之间将会有6种长度。如果这6种长度中有超过3个不同的值，则说明你没有一个矩形（2条相等的边长以及相等的对角线长度）。

- mathematician1975

---

好的解决方案，但在这个确切的问题上并不是非常有用。即使有100个点，计算所有距离也需要很长时间，而我通常会得到大约2500个点。 - sowizz

等一下。你说你有四个点，不是2500个。这个答案告诉你四个点是否构成一个矩形，并且似乎是这个任务的有效解决方案。如果你的问题与你描述的不同，那么你需要更具体地说明。 - user85109

是的，但也说这四点不是唯一的，我需要先找到合适的要点。 - sowizz

@sowizz 我明白了 - 或许你可以稍微澄清一下问题，因为问题标题本身要求从4个点中检测矩形，而不是从任意数量的点中选出4个。 - mathematician1975

你可以稍微减少一点复杂度。首先，你可以考虑只有三个点——需要是一个直角三角形（也许使用勾股定理）。其次，对于第四个点，在很多情况下计算一个距离来排除它就足够了。 - bdecaf

Answer 3

您知道通过视觉检查点云，您已经可以区分出许多矩形吗？换句话说，如果您不执行某种预选例程，可能会找到许多矩形...

无论如何，除了@mathematician1975提供的方法外，您还可以检查边是否（更或少）平行。

我们称@mathematician1975的方法为方法1，平行检查为方法2。那么：

%# method 1: 
n1 = |u1-u2|    %#  3 sub., 3 mult, 2 add. per distance
n2 = |u3-u2|    %#  total of 6 distances to compute.
n3 = |u4-u3|    %#  then max 5+4+3+2+1 = 15 comp. to find unique distances
n4 = |u1-u4|    
n5 = |u4-u2|    %#  Total:
n6 = |u3-u1|    %#  12 sub., 18 mult., 12 add, 15 comp



%# method 2:
w1 = u1-u2       %#  3 subtractions per vector
w2 = u3-u2       %#  total of 4 vectors to compute 
w3 = u3-u2
w4 = u1-u4                
                        %#  12 sub.
abs(w1-w3) == [0 0 0]   %#  3 sub., 3 comp., 1 sign.
abs(w2-w4) == [0 0 0]   %#  3 sub., 3 comp., 1 sign.

                        %# Total: 18 sub., 6 comp. 2 sign.

请注意，这两种情况都是最坏的情况；通过一些簿记，您可以大幅降低成本。

还要注意，方法2需要事先知道顶点已经按正确顺序排列。如果不是这种情况，它将使成本增加4倍，而这比方法1更多。

请问您是如何计算距离的？

- Rody Oldenhuis

---

是的，我知道拥有那么多点会形成很多矩形，但我不确定在这个阶段是否有什么我可以做的（稍后我将计算一些统计数据，以便只选择合适的矩形）。两点之间的距离计算为欧几里得距离： distance = sqrt( (x2-x1)^2 + (y2-y1)^2 ); 我不确定它是否是2500x4，因为你必须选择一个点，然后再选择另外3个点，计算距离，然后对于相同的第一个点，你选择另外3个点（与之前的不同），这远远超过了2500x4种组合。 - sowizz

@sowizz 试试使用 norm -- 这样速度应该会更快。或者，如果你愿意，可以省略平方根 -- 比较距离的平方或距离本身并没有区别。或者，使用曼哈顿距离：abs(x2-x1) + abs(y2-y1)。这将给出一个非常粗略但是更快的距离近似值，在矩形的情况下也必须相等。 - Rody Oldenhuis

Answer 4

假设你应该得到数字8，但你得到了数字7，那么你将加上数字1（称为delta或误差校正）来进行修正。

同样地，有一个delta矩形坐标来纠正矩形。检查点（坐标）是否落在delta矩形内。

矩形坐标如下所示：

x+delta,y+delta
x-delta,y+delta
x+delta,y-delta
x-delta,y-delta

如果这个方案对你来说可以正常工作，或者你找到了更好的解决方案，请告诉我。

- user1630095