logo标签列表

拟合点到网格的算法

algorithm
8

我有一个在二维空间中形成一个（不完美）网格的点列表：

x     x        x         x

 x    x       x           x

                 x
x      x                x

 x     x      x           x

如何最好地将它们适配到一个刚性网格中（即创建一个二维数组，并计算每个点在该数组中的位置）？

网格中没有空洞，但我事先不知道其尺寸。

编辑：网格不一定是规则的（行/列之间的间距不均匀）。

4
为什么不将每个坐标四舍五入？ - Denys Séguret
1
你需要每行/列的大小还是只需要行/列的数量？ - bitWorking
1
看起来需要使用某种傅里叶变换。 - n. m.
1
@dystroy - 我无法对坐标进行四舍五入，因为在同一行/列中的点可能相隔超过一个单位。 - user1958735
就我所知，我只是在搜索从“点集合”中挑选出2D子网格的算法，但有点惊讶的是似乎没有这样的算法存在。我本来期望会有一些聪明的Hough变换版本，但是针对网格而不是线段。 - BjornW
显示剩余5条评论
4个回答
5
一点图像处理的思路： 如果你将所拥有的内容看作是一个二进制图像，其中X为1，其余为0，你可以对行和列进行求和，并使用峰值查找算法来识别峰值，这些峰值将对应于网格的x和y线：
您的点作为二进制图像：
[SOURCE]
行/列之和：
[SOURCE]
现在将一些平滑技术应用到信号上（例如lowess）：
[SOURCE]
我相信你能理解这个思路。
祝好运！
4
我能想到的最好解决方案是一种暴力方法，计算网格尺寸以使点与其最近网格交点之间的欧几里得距离平方误差最小。
这假设点数p恰好等于列数乘以行数，每个网格交点上恰好有一个点。同时还假设任何点的最小x/y值为零。如果最小值大于零，则只需从每个点的x坐标中减去最小x值，并从每个点的y坐标中减去最小y值即可。
思路是在给定点数的情况下创建所有可能的网格尺寸。在上面的例子中，我们将制作具有尺寸1x16、2x8、4x4、8x2和16x1的网格。对于每个网格，我们通过将点的最大宽度除以列数减1和将点的最大高度除以行数减1来计算网格交点的位置。然后，我们将每个点拟合到其最近的网格交点，并找到点与交点之间的误差（距离的平方）。（请注意，仅当每个点更接近其预期的网格交点而不是任何其他交点时，此方法才有效。）
在分别对每个网格配置求和误差之后（例如获得1x16配置的一个误差值，2x8配置的另一个误差值等等），我们选择误差最小的配置。
初始化：
  P is the set of points such that P[i][0] is the x-coordinate and
                                   P[i][1] is the y-coordinate
  Let p = |P| or the number of points in P
  Let max_x = the maximum x-coordinate in P
  Let max_y = the maximum y-coordinate in P
     (minimum values are assumed to be zero)

  Initialize min_error_dist = +infinity
  Initialize min_error_cols = -1

算法:

  for (col_count = 1; col_count <= n; col_count++) {
     // only compute for integer # of rows and cols
     if ((p % col_count) == 0) {   
        row_count = n/col_count;

        // Compute the width of the columns and height of the rows
        // If the number of columns is 1, let the column width be max_x
        // (and similarly for rows)
        if (col_count > 1) col_width = max_x/(col_count-1);
        else col_width=max_x;
        if (row_count > 1) row_height = max_y/(row_count-1);
        else row_height=max_y;

        // reset the error for the new configuration
        error_dist = 0.0;
        for (i = 0; i < n; i++) {
           // For the current point, normalize the x- and y-coordinates
           // so that it's in the range 0..(col_count-1)
           //                       and 0..(row_count-1)
           normalized_x = P[i][0]/col_width;
           normalized_y = P[i][1]/row_height;

           // Error is the sum of the squares of the distances between 
           // the current point and the nearest grid point 
           // (in both the x and y direction)
           error_dist += (normalized_x - round(normalized_x))^2 +
                         (normalized_y - round(normalized_y))^2;
        }

        if (error_dist < min_error_dist) {
           min_error_dist = error_dist;
           min_error_cols = col_count;
        }
     }
  }
  return min_error_cols;

一旦确定了列数（因此也就是行数），您可以重新计算每个点的归一化值，并将其四舍五入以获取其所属的网格交点。
谢谢！这几乎是我要找的，只是我忘了指定网格不一定是规则的（请参见其他答案）。 - user1958735
谢谢！我最终采用了这种方法，用于稍微不同的问题，其中我不能假设没有空白（但它不能太稀疏）：分别考虑x和y坐标，我尝试增加slots（即列或行）的数量，当发现超过一定比例的slots为空时停止，并返回平方误差之和最小的解决方案。 - Davide
2

最终我使用了这个算法，受到beaker的启发：

  1. 计算给定点数的情况下网格的所有可能尺寸
  2. 对于每个可能的尺寸，将点拟合到该尺寸，并计算对齐的方差：
    • 按x值对点进行排序
    • 将点分组成列：前r个点形成第一列，其中r是行数
    • 在每列中，按y值对点进行排序，以确定它们所在的行
    • 对于每行/列，计算y值/x值的范围
    • 对齐的方差是找到的最大范围
  3. 选择对齐方差最小的尺寸
1
我编写了一个算法，可以处理缺失的坐标以及带有错误的坐标。

Python代码

# Input [x, y] coordinates of a 'sparse' grid with errors
xys = [[103,101],
       [198,103],
       [300, 99],
       [ 97,205],
       [304,202],
       [102,295],
       [200,303],
       [104,405],
       [205,394],
       [298,401]]

def row_col_avgs(num_list, ratio):
    # Finds the average of each row and column. Coordinates are
    # assigned to a row and column by specifying an error ratio.
    last_num = 0
    sum_nums = 0
    count_nums = 0
    avgs = []
    num_list.sort()
    for num in num_list:
        if num > (1 + ratio) * last_num and count_nums != 0:
            avgs.append(int(round(sum_nums/count_nums,0)))
            sum_nums = num
            count_nums = 1
        else:
            sum_nums = sum_nums + num
            count_nums = count_nums + 1
        last_num = num
    avgs.append(int(round(sum_nums/count_nums,0)))
    return avgs

# Split coordinates into two lists of x's and y's
xs, ys = map(list, zip(*xys))

# Find averages of each row and column within a specified error.
x_avgs = row_col_avgs(xs, 0.1)
y_avgs = row_col_avgs(ys, 0.1)

# Return Completed Averaged Grid
avg_grid = []
for y_avg in y_avgs:
    avg_row = []
    for x_avg in x_avgs:
        avg_row.append([int(x_avg), int(y_avg)])
    avg_grid.append(avg_row)

print(avg_grid)

代码输出

[[[102, 101], [201, 101], [301, 101]], 
 [[102, 204], [201, 204], [301, 204]], 
 [[102, 299], [201, 299], [301, 299]], 
 [[102, 400], [201, 400], [301, 400]]]

我还在寻找使用线性代数的另一种解决方案。请参见我的问题这里。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接