二维网格拟合：检测二维网格中的孔
2D Grid Fitting: detecting holes in a 2d grid
我有一个映射到网格的二维坐标列表（按行）。但是那里可能有一些缺失的节点。我正在尝试检测和计算缺失节点的估计位置。
在下面的示例中，第 2、3 和 4 行的最后一个节点缺失。见红色箭头。
如果可能的话，我正在寻找对 numpy 友好的解决方案。我查看了 other potential ways 和 RectBivariateSpline (scipy.interpolate)，但它们不起作用，因为我的网格可能倾斜了。
nodes = [[(194, 146), (311, 146), (427, 146), (545, 146), (662, 146), (780, 146), (904, 146), (1014, 146), (1130, 146), (1248, 146), (1365, 146), (1483, 146), (1602, 146), (1719, 146), (1842, 146)],
[(159, 196), (278, 196), (401, 196), (524, 196), (643, 197), (766, 197), (887, 196), (1011, 196), (1135, 196), (1258, 196), (1381, 197), (1503, 196), (1624, 196), (1750, 196)],
[(117, 251), (242, 251), (370, 251), (496, 251), (627, 251), (752, 251), (880, 251), (1010, 251), (1137, 251), (1266, 251), (1395, 251), (1522, 251), (1653, 252), (1780, 251)],
[(73, 311), (203, 311), (336, 311), (473, 311), (604, 311), (735, 312), (872, 312), (1006, 312), (1141, 312), (1277, 312), (1412, 312), (1549, 312), (1681, 312), (1824, 312)],
[(163, 377), (299, 378), (442, 378), (580, 378), (719, 378), (864, 378), (1005, 378), (1147, 378), (1289, 378), (1433, 379), (1571, 378), (1716, 379), (1856, 379), (1998, 378)],
[(110, 451), (260, 451), (408, 451), (554, 451), (702, 452), (853, 452), (1001, 452), (1151, 452), (1301, 452), (1453, 452), (1600, 452), (1751, 452), (1899, 453), (2052, 453)],
[(59, 532), (212, 534), (372, 533), (529, 533), (684, 534), (843, 534), (998, 534), (1158, 534), (1314, 535), (1474, 535), (1631, 535), (1793, 535), (1949, 535)],
[(163, 624), (329, 624), (496, 625), (663, 625), (830, 626), (996, 626), (1163, 627), (1334, 627), (1496, 627), (1667, 627), (1834, 627), (2002, 627)],
[(115, 728), (284, 728), (459, 729), (639, 729), (814, 730), (992, 730), (1174, 731), (1347, 730), (1528, 731), (1707, 731), (1883, 731)],
[(40, 846), (233, 846), (422, 846), (611, 848), (799, 848), (992, 848), (1183, 849), (1369, 849), (1559, 849), (1752, 850), (1942, 851)],
[(172, 982), (372, 982), (580, 982), (782, 984), (983, 984), (1186, 984), (1394, 985), (1598, 986), (1803, 987), (2013, 989)],
[(98, 1141), (323, 1140), (540, 1141), (759, 1141), (978, 1142), (1203, 1142), (1419, 1144), (1641, 1144), (1865, 1147)]]
由于这些点是以某种方式投影的，并不是真正意义上的“对齐”，因此您的方法受到限制。我会尝试 对称和计数 和 连续行的规则 。
对称性和计数：利用中间有一条（几乎）垂直线的事实，因此你必须有奇数个点在每一行。
连续行的规则： 因为行是对齐的，所以每行的点数必须相同，或者少 2，或者 2更多的。不允许少于或多于 1。
但是，如果数据没有这样的结构，这并不能解决问题。
我最终以“迭代方式”完成了它。这是伪代码：
- 找出最垂直的线
- 找到离那条线最近的上节点。 centerline_x 是起始搜索条件
- 列出与centerline_x
垂直对齐的所有节点
- 向左移动。 line_offset -= 1
- 计算每条线的平均水平距离并在该偏移量内搜索
- 当没有节点满足条件时停止，对右侧重复。
- 如果发现少于 3 个点，则丢弃垂直线
代码如下：
def bin_vertical_grid_nodes(grid_nodes, image_width, centerline_x):
# return the list of vertical nodes
vertically_aligned_nodes = list()
# go from center to the left hand-side
vnodes_left = find_vlines_from_offset(grid_nodes, image_width, centerline_x, 0, -1) # -1 is "go to the left"
# go from center+1 to the right hand-side
vnodes_right = self.find_vlines_from_offset(grid_nodes, image_width, centerline_x, 1, +1) # +1 is "go to the right"
# store the nodes from left to right
vertically_aligned_nodes = [vline for vline in reversed(vnodes_left)]
vertically_aligned_nodes.extend(vnodes_right)
return vertically_aligned_nodes
def find_vlines_from_offset(grid_nodes, image_width, centerline_x, offset_x_start, direction):
# bin all the vertical lines from a given offset from the center vertical line
vertically_aligned_nodes = list()
# select the upper node that is the closest to the centerline_x
upper_nodes_x = numpy.asarray(grid_nodes[0])[:, 0]
closest_point_idx = (numpy.abs(upper_nodes_x - centerline_x)).argmin()
centerline_x = upper_nodes_x[closest_point_idx]
line_offset_x = offset_x_start
while True:
lines_pos = list() # list of nodes aligned with found_x
# go through each horizontal line and find the node that is the closest to found_x
for row in grid_nodes:
closest_pt = self.get_closest_node_from(row, centerline_x, line_offset_x, image_width)
if closest_pt is not None:
lines_pos.append(closest_pt) # keep point that belongs to this vertical line
# nothing else to add
if len(lines_pos) == 0:
break
# store the nodes and shift to the adjacent vertical line
if len(lines_pos) >= 3:
vertically_aligned_nodes.append(lines_pos)
line_offset_x += direction # go left or right
return vertically_aligned_nodes
def get_closest_node_from(list_horiz_nodes, centerline_x, line_offset_x, image_width, leeway=0.5):
# return the node that is closest to posx, given the leeway
row = numpy.asarray(list_horiz_nodes)
row_x = row[:, 0] # x coordinates of row
# compute the mean distance between each nodes in this line
nodes_distance = numpy.ediff1d(row_x) # compute pair-wise distance between nodes
median_spacing = int(round(numpy.median(nodes_distance))) # get the median distance
posx = centerline_x + (line_offset_x * median_spacing)
if posx < 0 or posx >= image_width:
return None
# get the point closest from posx
closest_point_idx = (numpy.abs(row_x - posx)).argmin()
distance_from_pt = abs(row[closest_point_idx][0] - posx)
if distance_from_pt > median_spacing * leeway:
return None # this point was too far
return list_horiz_nodes[closest_point_idx]
以下是一些结果：
我有一个映射到网格的二维坐标列表（按行）。但是那里可能有一些缺失的节点。我正在尝试检测和计算缺失节点的估计位置。
在下面的示例中，第 2、3 和 4 行的最后一个节点缺失。见红色箭头。
如果可能的话，我正在寻找对 numpy 友好的解决方案。我查看了 other potential ways 和 RectBivariateSpline (scipy.interpolate)，但它们不起作用，因为我的网格可能倾斜了。
nodes = [[(194, 146), (311, 146), (427, 146), (545, 146), (662, 146), (780, 146), (904, 146), (1014, 146), (1130, 146), (1248, 146), (1365, 146), (1483, 146), (1602, 146), (1719, 146), (1842, 146)],
[(159, 196), (278, 196), (401, 196), (524, 196), (643, 197), (766, 197), (887, 196), (1011, 196), (1135, 196), (1258, 196), (1381, 197), (1503, 196), (1624, 196), (1750, 196)],
[(117, 251), (242, 251), (370, 251), (496, 251), (627, 251), (752, 251), (880, 251), (1010, 251), (1137, 251), (1266, 251), (1395, 251), (1522, 251), (1653, 252), (1780, 251)],
[(73, 311), (203, 311), (336, 311), (473, 311), (604, 311), (735, 312), (872, 312), (1006, 312), (1141, 312), (1277, 312), (1412, 312), (1549, 312), (1681, 312), (1824, 312)],
[(163, 377), (299, 378), (442, 378), (580, 378), (719, 378), (864, 378), (1005, 378), (1147, 378), (1289, 378), (1433, 379), (1571, 378), (1716, 379), (1856, 379), (1998, 378)],
[(110, 451), (260, 451), (408, 451), (554, 451), (702, 452), (853, 452), (1001, 452), (1151, 452), (1301, 452), (1453, 452), (1600, 452), (1751, 452), (1899, 453), (2052, 453)],
[(59, 532), (212, 534), (372, 533), (529, 533), (684, 534), (843, 534), (998, 534), (1158, 534), (1314, 535), (1474, 535), (1631, 535), (1793, 535), (1949, 535)],
[(163, 624), (329, 624), (496, 625), (663, 625), (830, 626), (996, 626), (1163, 627), (1334, 627), (1496, 627), (1667, 627), (1834, 627), (2002, 627)],
[(115, 728), (284, 728), (459, 729), (639, 729), (814, 730), (992, 730), (1174, 731), (1347, 730), (1528, 731), (1707, 731), (1883, 731)],
[(40, 846), (233, 846), (422, 846), (611, 848), (799, 848), (992, 848), (1183, 849), (1369, 849), (1559, 849), (1752, 850), (1942, 851)],
[(172, 982), (372, 982), (580, 982), (782, 984), (983, 984), (1186, 984), (1394, 985), (1598, 986), (1803, 987), (2013, 989)],
[(98, 1141), (323, 1140), (540, 1141), (759, 1141), (978, 1142), (1203, 1142), (1419, 1144), (1641, 1144), (1865, 1147)]]
由于这些点是以某种方式投影的，并不是真正意义上的“对齐”，因此您的方法受到限制。我会尝试 对称和计数 和 连续行的规则 。
对称性和计数：利用中间有一条（几乎）垂直线的事实，因此你必须有奇数个点在每一行。
连续行的规则： 因为行是对齐的，所以每行的点数必须相同，或者少 2，或者 2更多的。不允许少于或多于 1。
但是，如果数据没有这样的结构，这并不能解决问题。
我最终以“迭代方式”完成了它。这是伪代码：
- 找出最垂直的线
- 找到离那条线最近的上节点。 centerline_x 是起始搜索条件
- 列出与centerline_x 垂直对齐的所有节点
- 向左移动。 line_offset -= 1
- 计算每条线的平均水平距离并在该偏移量内搜索
- 当没有节点满足条件时停止，对右侧重复。
- 如果发现少于 3 个点，则丢弃垂直线
代码如下：
def bin_vertical_grid_nodes(grid_nodes, image_width, centerline_x):
# return the list of vertical nodes
vertically_aligned_nodes = list()
# go from center to the left hand-side
vnodes_left = find_vlines_from_offset(grid_nodes, image_width, centerline_x, 0, -1) # -1 is "go to the left"
# go from center+1 to the right hand-side
vnodes_right = self.find_vlines_from_offset(grid_nodes, image_width, centerline_x, 1, +1) # +1 is "go to the right"
# store the nodes from left to right
vertically_aligned_nodes = [vline for vline in reversed(vnodes_left)]
vertically_aligned_nodes.extend(vnodes_right)
return vertically_aligned_nodes
def find_vlines_from_offset(grid_nodes, image_width, centerline_x, offset_x_start, direction):
# bin all the vertical lines from a given offset from the center vertical line
vertically_aligned_nodes = list()
# select the upper node that is the closest to the centerline_x
upper_nodes_x = numpy.asarray(grid_nodes[0])[:, 0]
closest_point_idx = (numpy.abs(upper_nodes_x - centerline_x)).argmin()
centerline_x = upper_nodes_x[closest_point_idx]
line_offset_x = offset_x_start
while True:
lines_pos = list() # list of nodes aligned with found_x
# go through each horizontal line and find the node that is the closest to found_x
for row in grid_nodes:
closest_pt = self.get_closest_node_from(row, centerline_x, line_offset_x, image_width)
if closest_pt is not None:
lines_pos.append(closest_pt) # keep point that belongs to this vertical line
# nothing else to add
if len(lines_pos) == 0:
break
# store the nodes and shift to the adjacent vertical line
if len(lines_pos) >= 3:
vertically_aligned_nodes.append(lines_pos)
line_offset_x += direction # go left or right
return vertically_aligned_nodes
def get_closest_node_from(list_horiz_nodes, centerline_x, line_offset_x, image_width, leeway=0.5):
# return the node that is closest to posx, given the leeway
row = numpy.asarray(list_horiz_nodes)
row_x = row[:, 0] # x coordinates of row
# compute the mean distance between each nodes in this line
nodes_distance = numpy.ediff1d(row_x) # compute pair-wise distance between nodes
median_spacing = int(round(numpy.median(nodes_distance))) # get the median distance
posx = centerline_x + (line_offset_x * median_spacing)
if posx < 0 or posx >= image_width:
return None
# get the point closest from posx
closest_point_idx = (numpy.abs(row_x - posx)).argmin()
distance_from_pt = abs(row[closest_point_idx][0] - posx)
if distance_from_pt > median_spacing * leeway:
return None # this point was too far
return list_horiz_nodes[closest_point_idx]
以下是一些结果：