6

我有一张图片，我用我的程序详细说明了获取坐标列表。

在图像中表示有一个矩阵。在一个理想的测试中，我只会得到矩阵每个正方形的十六个中心点。但在实际测试中，我拿了很多噪音点。

我想使用一种算法从坐标列表中推断出由 16 个坐标组成的组，最能代表一个矩阵。

矩阵可以有任何纵横比（在一个范围之间）并且可以产生一点旋转。但始终是 4x4 矩阵。矩阵并不总是出现在图像中，但不是问题，我只需要最佳匹配。当然，创建点总是超过 16（或者我跳过）

建立点示例：

在此处输入图像描述

预期结果示例：

在此处输入图像描述

如果有人可以建议我这样做的首选方法，那就太好了。

我在考虑点之间的欧几里得距离。

  For each point in the list:
     1. calculate the euclidean distance (D) with the others
     2. filter that points that D * 3 > image.widht (or height)
     3. see if it have at least 2 point at the same (more or less) distance,
        if not skip
     4. if yes put the point in a list and for each same-distance founded points: go to 2nd step.

最后，如果我在列表中有 16 个点，这可能是一个矩阵。

有更好的建议吗？

谢谢

4

2 回答 2

2

这是我想到的算法：

for each pair of points (p1, p2):
    let d be the distance vector (x and y) between them
    if d.x > (image.width-p1.x)/3 or d.y > (image.height-p1.y)/3:
        continue
    let d_t be d turned 90 degrees (d.y, -d.x)
    for i from 0 to 3:
        for j from 0 to 3:
            if there is no point at p1 + i*d + j*d_t:
                continue outer loop
    if you get here, you have a 4*4 grid

要将运行时间减少一半（平均），您可以只考虑 p1 右侧的 p2。

于 2013-05-24T15:05:49.387 回答
0

根据您要使用多少处理能力，并假设“小旋转”意味着很少，您可以尝试以下操作：1）仅获取点的 X 坐标，搜索大小为 4 的集群。

2）对于每个集群，查看左侧距离为 d 的每个集群，如果还有两个距离为 2*d 和 3*d 的集群。

3）如果是，比较这些集群中的每一个的 y 坐标，看看它们是否大致相等。

根据数据，您可能会在第二步之前执行第三步并使用它来修剪您考虑的选项，从而获得更好的性能。

于 2013-05-24T14:47:45.873 回答