在一组点中识别矩阵

Question

我有一张图片,我用我的程序详细说明,以获得坐标列表.

在图像中表示有一个矩阵.在一个理想的测试中,我只得到矩阵每个方格的十六个中心点.但在实际测试中,我需要相当多的噪点.

我想使用一种算法从坐标列表中推断出来,该坐标由最能代表矩阵的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个点,这可能是一个矩阵.

还有更好的建议吗？

谢谢

Answer 1

这是我想到的算法：

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。