四边形形状发现算法

Question

我想检测和COMPLETE从随机分布的线段的所有可能的四角形!

附带的照片就是一个例子,线条可能总是出现在非常不同的位置.

任何人都可以为此指出任何好的算法？

• 注意线段是使用opencv 2.4.2的Hough变换的输出

解决方案是检测和预测黄色四边形

Answer 1

对于11个线段,您有330种方式可以选择四个线段.您可以确定每个组合制作四边形的可能性,并按此方式评分.

除了线之外,可以使用霍夫变换检测形式,但是由于累加器空间需要多于两个维度,因此变得更难以可视化.圆可以在三个维度中找到(midX,midY,radius),四个椭圆(我相信).我不确定你需要多少参数来建模四边形,我相信当你得到高于三维时,霍夫变换的性能开始下降.蓄电池空间变得很大,噪声比显着增加.

这是一个相关的问题,可能会为您提供一些有趣的答案.

让我们知道您的身体情况如何!

编辑

我今天抓住了这个问题,并将我的解决方案上传到GitHub.这里发布的代码太多了.

这是显示输出的屏幕截图:

我采取的解决方案基本上就是我在编辑之前所描述的.

1. 找到四行的所有组合
2. 找到这四行的所有排列
3. 评估这四条线形成四边形的可能性
4. 采取最佳匹配

评估通过计算粗略错误分数来进行.这是两种不同类型错误的总和:

1. 每个角落的偏差为90度(我使用所有四个角的误差平方和)
2. 当线段在线段内相交时,它可能不是有效的角

第二类错误可能以更健壮的方式确定.有必要为您的样本数据集找到解决方案.

我还没有尝试过其他数据集.可能需要进行一些调整才能使其更加健壮.我试图避免使用太多参数,以便可以直接调整到特定环境.例如,控制对遮挡的敏感度,如示例图像中所示.

它在我的笔记本电脑上找到了大约160毫秒的解决方案.但是我没有进行任何性能优化.我希望,如果您需要更接近实时的情况,可以显着优化查找组合/排列的方法,这通常是计算机视觉实验的情况.

Answer 2

如果不对角度等施加约束,可以完成任意四条线以形成四边形.

具有潜在错误四边形的图像:

可能你不想包括像我的例子中所示的黄色四边形.您应该对角度,最小/最大尺寸,纵横比和允许的完成程度有约束.如果必须添加90%的线以形成完整的四边形,这可能不是一个非常好的候选者.

我担心你必须测试每个可能的线组合并在它们上应用启发式给它们分.角度接近90度的许多点(如果你想要的是矩形),为了完整性,宽高比接近预期的角度等.

UPDATE

使用点系统比仅应用严格规则具有优势.

• 点系统允许您评估四边形的质量并采用最佳的四边形或完全拒绝四边形.
• 一个房产的高质量可以帮助超过另一个房产的劣质.
• 它允许您为不同的属性赋予不同的权重.

假设您有一个严格的规则(伪代码):

(angles == 90 +/- 10 degrees) && (line_completeness>50%)

这会起作用,但可能导致像这样的情况angles == 90 +/- 1 degree) && (line_completeness == 45%).根据规则,由于线路完整性差,这个四边形不会通过; 然而,角度的质量是特殊的,仍然使它成为一个非常好的候选人.

给点数更好.对于90度正好的角度说20点,对于90 +/- 15度的角度下降到0点,对于完整线10点,朝向0点,例如线仅完成25%.这使得角度比线条完整性更重要,并且还为没有绝对规则的问题创建更柔和的条件.