2D Grid Fitting: detecting holes in a 2d grid

Question

I have a list of 2d coordinates (by row) mapped to a grid. However there could be some missing nodes in there. I'm trying to detect and compute an estimated position for the missing nodes.

In the example below, the last nodes in the 2nd, 3rd and 4th rows are missing. See red arrows.

I'm looking for a numpy-friendly solution, if possible. I looked at other potential ways and RectBivariateSpline (scipy.interpolate) but they won't work since my grid may be tilted.

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)]]

score 0 · Answer 1 · answered Jul 30 '20 at 16:05

0

Since the points are somehow projected and not really matematically "aligned", you are limited with your methods. I would try symmetry & counting and rules for consecutive rows.

symmetry & counting: exploit the fact that you have an (almost) vertical line in the middle, therefore you have to have an odd amount of points in eah row.
rules for consecutive rows: since the rows are aligned, you must either have the same number of points per each row, or 2 less, or 2 more. 1 less or more is not allowed.

This, however doesn't solve the problem if the data has no such structure.

answered Jul 30 '20 at 16:05

Dorian

1,439
1
11
26

The points are rigorously aligned on straight lines ! This is a perspective transform of a regular grid. – Jul 31 '20 at 11:48
@YvesDaoust I can see that this is a perspective transform. however, it doesn't help a lot if you don't have the original points as data and only the approximated transformed coordinates as in this case, right? So now you have to apply an approximation to find the original data (like in your post). – Dorian Jul 31 '20 at 15:32
I am referring to the statement "not really matematically "aligned"", which is misleading. – Jul 31 '20 at 16:02

score 0 · Accepted Answer · answered Jul 31 '20 at 16:30

I ended up doing it "the iterative way". Here's the pseudo-code:

identify the most vertical line
find the upper node closest to that line. centerline_x is the starting search criteria
list all nodes that are vertically aligned with centerline_x
move to the left. line_offset -= 1
compute the mean horizontal distance for each line and search within that offset
stop when no node fills the criteria, repeat for the right hand-side.
if less than 3 points are found, discard the vertical line

Here's the code:

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]

Here are some results:

2D Grid Fitting: detecting holes in a 2d grid

2 Answers2