根据可能不完整的候选者列表构建2D网格 [英] Constructing a 2D grid from potentially incomplete list of candidates

问题描述

问题

我需要使用一组候选位置(X和Y中的值)构造2D网格.但是，可能存在应过滤掉的假阳性候选对象以及假阴性(在给定周围位置值的情况下，需要为预期位置创建位置).网格的行和列应该是笔直的，旋转应该是小的.

I need to construct a 2D grid using a set of candidate positions (values in X and Y). However, there may be false positive candidates that should be filtered out, as well as false negatives (where the position needs to be created for the expected position given the surrounding positions' values). The rows and columns of the grid can be expected to be straight, and the rotation, if any small.

此外，我没有关于(0，0)网格位置在哪里的可靠信息.但是我知道:

Further, I don't have reliable information on where the (0, 0) grid position is. However I do know:

grid_size = (4, 4)

expected_distance = 105

(距离只是网格点之间间距的粗略估计，应允许在10％的范围内变化).

(Excepted distance is just a rough estimate of the spacing between grid points, and should be allowed to vary in the range of 10%).

示例数据

这是理想的数据，没有误报，也没有误报.该算法必须能够处理删除几个数据点并添加错误的数据点.

This is the ideal data, with no false positives and no false negatives. The algorithm needs to be able to cope with removing several data-points and adding false ones as well.

X = np.array([61.43283582, 61.56626506, 62.5026738,   65.4028777, 167.03030303, 167.93965517, 170.82191781, 171.37974684, 272.02884615, 272.91089109, 274.1031746, 274.22891566, 378.81553398, 379.39534884, 380.68181818, 382.67164179])

Y = np.array([55.14427861, 160.30120482, 368.80213904, 263.12230216, 55.1030303, 263.64655172, 162.67123288, 371.36708861, 55.59615385, 264.64356436, 368.20634921, 158.37349398, 54.33980583, 160.55813953,  371.72727273,  266.68656716])

代码

以下函数评估候选对象并返回两个字典.

The following function evaluates the candidates and returns two dictionaries.

第一个具有每个候选位置(作为2个长度的元组)，作为键，值是相邻对象右下方的2个长度的元组(使用显示图像的逻辑).这些邻居本身就是2长度元组坐标或None.

The first one has each candidate position (as a 2-length tuple) as keys and values are 2-length tuples of the positions right and below neighbour (using logic from how images are displayed). Those neighbours are themselves either a 2-length tuple coordinate or a None.

第二个字典是第一个字典的反向查找，因此每个候选(位置)都有支持它的其他候选位置列表.

The second dictionary is a reverse lookup of the first, such that each candidate (position) has a list of other candidates' positions supporting it.

import numpy as np
from collections import defaultdict

def get_neighbour_grid(X, Y, expect_dist=(105, 105)):

    t1 = (expect_dist[0] + expect_dist[1]) / 2.0 * 0.9
    t2 = t1 * 1.222

    def neighbours(x, y):

        nRight = None
        ideal = x + expect_dist[0]
        D = np.sqrt((X - ideal)**2 + (Y - y)**2)
        candidate = (X[D.argmin()], Y[D.argmin()])
        if candidate != (x, y) and x + t2 > candidate[0] > x + t1:
            nRight = candidate

        nBelow = None
        ideal = y + expect_dist[0]
        D = np.sqrt((X - x)**2 + (Y - ideal)**2)
        candidate = (X[D.argmin()], Y[D.argmin()])
        if candidate != (x, y) and y + t2 > candidate[1] > y + t1:
            nBelow = candidate

        return nRight, nBelow

    right_below_neighbours = dict()
    def _default_val(*args):
        return list()
    reverse_lookup = defaultdict(_default_val)

    for pos in np.arange(X.size):

        pos_tuple = (X[pos], Y[pos])
        n  = neighbours(*pos_tuple)
        right_below_neighbours[pos_tuple] = n
        reverse_lookup[n[0]].append(pos_tuple)
        reverse_lookup[n[1]].append(pos_tuple)

    return right_below_neighbours, reverse_lookup

在这里我被困住了:

如何使用这些词典和/或X和Y来构建最受支持的网格?

How do I use these dictionaries and/or X and Y to construct the most supported grid?

我有一个想法，就是从2个邻居支持的最低的，最右边的候选者开始，然后使用reverse_lookup字典迭代地创建网格.但是该设计存在一些缺陷，最明显的是，我不能指望检测到最低，最右边的候选者及其支持的邻居.

I had an idea for starting with the lower, rightmost candidate supported by 2 neighbours and iteratively create the grid using the reverse_lookup dictionary. But that design has several flaws, the most apparent being that I cannot count on having detected the lower, rightmost candidate and both its supporting neighbours.

用于该代码的代码，尽管自从我意识到它有多麻烦(pre_grid = right_below_neighbours)以来就放弃了它，但该代码无法运行:

The code for that, though it wont run since I abandoned it when I realized how problematic it was (pre_grid = right_below_neighbours):

def build_grid(pre_grid, reverse_lookup, grid_shape=(4, 4)):

    def _default_val(*args):
        return 0

    grid_pos_support = defaultdict(_default_val)
    unsupported = 0

    for l, b in pre_grid.values():

        if l is not None:
            grid_pos_support[l] += 1
        else:
            unsupported += 1
        if b is not None:
            grid_pos_support[b] += 1
        else:
            unsupported += 1

    well_supported = list()
    for pos in grid_pos_support:
        if grid_pos_support[pos] >= 2:
            well_supported.append(pos)

    well_A = np.asarray(well_supported)
    ur_pos = well_A[well_A.sum(axis=1).argmax()]

    grid = np.zeros(grid_shape + (2,), dtype=np.float)
    grid[-1,-1,:] = ur_pos

    def _iter_build_grid(pos, ref_pos=None):

        isX = pre_grid[tuple(pos)][0] == ref_pos
        if ref_pos is not None:
            oldCoord = map(lambda x: x[0], np.where(grid == ref_pos)[:-1])
            myCoord = (oldCoord[0] - int(isX), oldCoord[1] - int(not isiX))

        for p in reverse_lookup[tuple(pos)]:

            _iter_build_grid(p, pos)

    _iter_build_grid(ur_pos)

    return grid

第一部分可能会很有用，因为它总结了对每个职位的支持.它还显示了我作为最终输出(grid)所需的内容:

The first part could be useful though, since it sums up the support for each position. It also shows what I would need as a final output (grid):

一个3D数组，其第一个维度为网格形状，第三个维度为长度2(每个位置的x坐标和y坐标).

A 3D array with the 2 first dimensions the shape of the grid and the 3rd with length 2 (for x-coordinate and y-coordinate for each position).

回顾

因此，我意识到自己的尝试是没有用的，但是我对如何对所有候选者进行全局评估并使用适合的候选者的x和y值放置最受支持的网格感到困惑.因此，我希望这是一个非常复杂的问题，我真的不希望有人提供完整的解决方案(尽管那会很棒)，但是任何有关可以使用哪种类型的算法或numpy/scipy函数的提示都会非常感谢.

So I realize how my attempt was useless, but I'm at loss as to how make a global evaluation of all candidates and place the most supported grid using the candidates' x and y values wherever fit. As this is, I expect, a quite complex question, I don't really expect anyone to give a complete solution (though it would be great), but any hint as to what type of algorithms or numpy/scipy functions could be used would be much appreciated.

最后，很抱歉，这个问题有些冗长.

Finally, sorry for this being a somewhat lengthy question.

修改

我想发生的事情的图画:

Drawing of what I want to happen:

星星/点是X和Y，作了两个修改，我删除了第一个位置并添加了一个错误的位置，以使其成为所寻求算法的完整示例.

The stars/dots are the X and Y plotted with two modifications, I removed the first position and added a false one to make this a full example of the sought algorithm.

我想要的是换句话说，绘制红色圆圈位置的新坐标值(写在它们旁边的坐标值)，以便我可以从新坐标中获得旧坐标(例如(1, 1) -> (170.82191781, 162.67123288)).我还希望舍弃那些不逼近真实点所描述的理想网格的点(如图所示)，最后要使用理想网格参数(大约).

What I want is to, in other words, map the red-circled positions' new coordinate values (the ones written beside them) so that I can obtain the old coordinate from the new (e.g. (1, 1) -> (170.82191781, 162.67123288)). I also want points that don't approximate the ideal grid that the true points describe to be discarded (as shown), and finally the empty ideal grid positions (blue circle) to be 'filled' using the ideal grid parameters (roughly (0, 0) -> (55, 55)).

解决方案

我使用提供的代码@skymandr来获取理想的参数，然后执行以下操作(不是最漂亮的代码，但它可以工作).这意味着我不再使用get_neighbour_grid功能.

I used the code @skymandr supplied to get the ideal parameters and then did the following (not the prettiest code, but it works). That means I'm not using the get_neighbour_grid-function anymore.:

def build_grid(X, Y, x_offset, y_offset, dx, dy, grid_shape=(16,24),
    square_distance_threshold=None):

    if square_distance_threshold is None:
        square_distance_threshold = ((dx + dy) / 2.0 * 0.05) ** 2

    grid = np.zeros(grid_shape + (2,), dtype=np.float)

    D = np.zeros(grid_shape)
    for i in range(grid_shape[0]):
        for j in range(grid_shape[1]):
            D[i,j] = i * (1 + 1.0 / (grid_shape[0] + 1)) + j

    rD = D.ravel().copy()
    rD.sort()

    def find_valid(x, y):

        d = (X - x) ** 2 + (Y - y) ** 2
        valid = d < square_distance_threshold
        if valid.any():
            pos = d == d[valid].min()
            if pos.sum() == 1:
                return X[pos], Y[pos]

        return x, y

    x = x_offset
    y = y_offset
    first_loop = True

    for v in rD:
        #get new position
        coord = np.where(D == v)

        #generate a reference position already passed
        if coord[0][0] > 0:
            old_coord = (coord[0] - 1, coord[1])
        elif coord[1][0] > 0:
            old_coord = (coord[0], coord[1] - 1)

        if not first_loop:
            #calculate ideal step
            x, y = grid[old_coord].ravel()
            x += (coord[0] - old_coord[0]) * dx
            y += (coord[1] - old_coord[1]) * dy

        #modify with observed point close to ideal if exists
        x, y = find_valid(x, y)

        #put in grid
        #print coord, grid[coord].shape
        grid[coord] = np.array((x, y)).reshape(grid[coord].shape)

        first_loop = False


    return grid

这提出了另一个问题:如何沿2D阵列的对角线很好地进行迭代，但是我想这是一个值得探讨的问题:

It poses another question: how to nicely iterate along the diagonals of an 2D-array, but I suppose that is worthy of a question of its own: More numpy way of iterating through the 'orthogonal' diagonals of a 2D array

修改

更新了解决方案代码，以更好地处理更大的网格尺寸，以便它使用已传递的相邻网格位置作为所有位置的理想坐标的参考.仍然必须找到一种方法来实现从链接的问题遍历网格的更好方法.

Updated the solution code to better deal with larger grid-sizes so that it uses a neighbouring grid position already passed as reference for the ideal coordinate for all positions. Still have to find a way to implement the better way of iterating through the grid from the linked question.

推荐答案

这是一个相当简单且便宜的解决方案，尽管我不知道它有多健壮.

Here is a fairly simple and cheap solution, though I don't know how robust it is.

首先，这是一种更好地估计间距的方法:

First of all, here's a way of getting a better estimate for the spacing:

leeway = 1.10

XX = X.reshape((1, X.size))
dX = np.abs(XX - XX.T).reshape((1, X.size ** 2))
dxs = dX[np.where(np.logical_and(dX > expected_distance / leeway,
                                 dX < expected_distance * leeway))]
dx = dxs.mean()

YY = Y.reshape((1, Y.size))
dY = np.abs(YY - YY.T).reshape((1, Y.size ** 2))
dys = dY[np.where(np.logical_and(dY > expected_distance / leeway,
                                 dY < expected_distance * leeway))]
dy = dys.mean()

该代码计算X和Y的内部差异，并取那些在所需间距的10％之内的平均值.

The code computes internal differences in X and Y, and takes the mean of those who are within 10% of the desired spacing.

对于第二部分，找到网格的偏移量，可以使用类似的方法:

For the second part, finding the offset of the grid, a similar method can be used:

Ndx = np.array([np.arange(grid_size[0])]) * dx
x_offsets = XX - Ndx.T
x_offset = np.median(x_offsets)

Ndy = np.array([np.arange(grid_size[1])]) * dy
y_offsets = YY - Ndy.T
y_offset = np.median(y_offsets)

从本质上讲，这是基于X - n * dx(其中n = 0是对该点本身的投票)，将X中的每个位置投票"为左下角可能所在的NX = grid_size[0]位置， n = 1是对左边的一个dx等点的投票.这样，靠近真实原点的点将获得最多的投票，并且可以使用中位数来找到偏移量.

Essentially, what this does is to let each position in X "vote" for NX = grid_size[0] positions where the bottom left point might be, based on X - n * dx where n = 0 is a vote for the point itself, n = 1 is a vote for a point one dx to the left etc. This way, the points near the true origin will get the most votes, and the offset can be found using the median.

我认为该方法在所需原点周围具有足够的对称性，因此中位数可以在大多数(如果不是全部)情况下使用.但是，如果存在许多误报，导致中位数由于某些原因而无法工作，则可以使用例如来找到真"原点.直方图法.

I think this method is sufficiently symmetric around the desired origin, that the median can be used in most (if not all) cases. If, however, there are many false positives, that make the median not work for some reason, the "true" origin can be found using e.g. a histogram-method.

这篇关于根据可能不完整的候选者列表构建2D网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！