algorithm - 我如何检测一组点是菱形或方格

Question

假设我有一个包含点的 2D 图像，我可以大致检测到点的每个中心点，我如何检测它是方格(方形网格)还是菱形(旋转 45 度)？

幸运的是我的图像是规则的，没有变形。菱形的情况实际上类似于正方形，但它只旋转了 45 度。唯一的问题是:

1. 我可以使用霍夫变换检测圆，但中心点当然是近似值。
2. 点不一定填满整个图像(见下图)

我一直在想类似于OpenCV中棋盘图案校准的东西(但当然没有相机参数)，

Answer 1

一种方法可能如下所示:

1. 使用 Hough 变换检测圆，当然圆心是近似的；

2. 选择任意数量的点进行测试。点数取决于您必须有多准确/处理图像需要多快。需要多个点来实现投票以减少错误的影响。您可以使用任何方法来选择点 - 完全随机或半随机(在图像中随机分布某些点)；

3. 要检测所选每个点的网格方向，请执行最近邻搜索并找到 4 个最近邻。这些邻居将位于穿过特定点的网格线的边缘。根据数据集的大小，您可以使用两个 for 循环自己找到邻居，或者您可以使用 FLANN 库(Fast Library for Approximate Nearest Neighbors)中的 OpenCV knnSearch 方法；

4. 当每个点有 4 个最近邻点时，您需要确定指定点的晶格方向。为此，您需要计算每个采样点与其相邻点之间的垂直和水平距离。如果格子是正方形的，那么 Min(deltaX, deltaY) 应该接近于 0。如果它是菱形的，那么它大约是每两点之间距离的一半。处理所有的邻居并在此时决定格子是正方形还是菱形。对每个测试点都这样做并收集结果；

5. 处理结果并根据每个测试点的投票对晶格方向做出最终决定。