python – 从可能不完整的候选列表构建2D网格

前端之家收集整理的这篇文章主要介绍了python – 从可能不完整的候选列表构建2D网格前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

问题

我需要使用一组候选位置(X和Y中的值)构建2D网格.然而,可能存在应该被过滤掉的假阳性候选者,以及假阴性(其中需要针对给定周围位置值的预期位置创建位置).可以预期网格的行和列是直的,并且旋转(如果小的话).

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

  1. grid_size = (4,4)
  2. expected_distance = 105

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

示例数据

这是理想的数据,没有误报,也没有漏报.该算法需要能够处理删除多个数据点并添加错误的数据点.

  1. 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])
  2. 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])

以下函数评估候选项并返回两个词典.

第一个具有每个候选位置(作为2长度元组)作为键和值是位于右侧和下方的位置的2长度元组(使用来自图像如何显示的逻辑).这些邻居本身要么是2长度的元组坐标,要么是无.

第二个字典是第一个字典的反向查找,使得每个候选者(位置)具有支持它的其他候选者位置的列表.

  1. import numpy as np
  2. from collections import defaultdict
  3. def get_neighbour_grid(X,Y,expect_dist=(105,105)):
  4. t1 = (expect_dist[0] + expect_dist[1]) / 2.0 * 0.9
  5. t2 = t1 * 1.222
  6. def neighbours(x,y):
  7. nRight = None
  8. ideal = x + expect_dist[0]
  9. D = np.sqrt((X - ideal)**2 + (Y - y)**2)
  10. candidate = (X[D.argmin()],Y[D.argmin()])
  11. if candidate != (x,y) and x + t2 > candidate[0] > x + t1:
  12. nRight = candidate
  13. nBelow = None
  14. ideal = y + expect_dist[0]
  15. D = np.sqrt((X - x)**2 + (Y - ideal)**2)
  16. candidate = (X[D.argmin()],y) and y + t2 > candidate[1] > y + t1:
  17. nBelow = candidate
  18. return nRight,nBelow
  19. right_below_neighbours = dict()
  20. def _default_val(*args):
  21. return list()
  22. reverse_lookup = defaultdict(_default_val)
  23. for pos in np.arange(X.size):
  24. pos_tuple = (X[pos],Y[pos])
  25. n = neighbours(*pos_tuple)
  26. right_below_neighbours[pos_tuple] = n
  27. reverse_lookup[n[0]].append(pos_tuple)
  28. reverse_lookup[n[1]].append(pos_tuple)
  29. return right_below_neighbours,reverse_lookup

这是我被卡住的地方:

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

我有一个想法,从2个邻居支持的较低的,最右边的候选者开始,并使用reverse_lookup字典迭代地创建网格.但是这种设计有几个缺陷,最明显的是我不能指望找到较低的,最右边的候选人和它的支持邻居.

代码,虽然它没有运行,因为当我意识到它有多么困难时我放弃了它(pre_grid = right_below_neighbours):

  1. def build_grid(pre_grid,reverse_lookup,grid_shape=(4,4)):
  2. def _default_val(*args):
  3. return 0
  4. grid_pos_support = defaultdict(_default_val)
  5. unsupported = 0
  6. for l,b in pre_grid.values():
  7. if l is not None:
  8. grid_pos_support[l] += 1
  9. else:
  10. unsupported += 1
  11. if b is not None:
  12. grid_pos_support[b] += 1
  13. else:
  14. unsupported += 1
  15. well_supported = list()
  16. for pos in grid_pos_support:
  17. if grid_pos_support[pos] >= 2:
  18. well_supported.append(pos)
  19. well_A = np.asarray(well_supported)
  20. ur_pos = well_A[well_A.sum(axis=1).argmax()]
  21. grid = np.zeros(grid_shape + (2,),dtype=np.float)
  22. grid[-1,-1,:] = ur_pos
  23. def _iter_build_grid(pos,ref_pos=None):
  24. isX = pre_grid[tuple(pos)][0] == ref_pos
  25. if ref_pos is not None:
  26. oldCoord = map(lambda x: x[0],np.where(grid == ref_pos)[:-1])
  27. myCoord = (oldCoord[0] - int(isX),oldCoord[1] - int(not isiX))
  28. for p in reverse_lookup[tuple(pos)]:
  29. _iter_build_grid(p,pos)
  30. _iter_build_grid(ur_pos)
  31. return grid

第一部分可能很有用,因为它总结了对每个职位的支持.它还显示了我需要的最终输出(网格):

具有2个第一维度的3D阵列,网格的形状和具有长度2的第3维度(对于每个位置的x坐标和y坐标).

概括

所以我意识到我的尝试是如何无用的,但我不知道如何对所有候选人进行全局评估,并在任何适合的地方使用候选人的x和y值放置最受支持的网格.我希望这是一个非常复杂的问题,我真的不希望任何人给出一个完整的解决方案(尽管它会很棒),但任何类型的算法或numpy / scipy函数都可以使用的暗示非常感谢.

最后,抱歉这是一个有点冗长的问题.

编辑

绘制我想要发生的事情:

星/点是X和Y绘制的两个修改,我删除了第一个位置并添加了一个假的,以使其成为所搜索算法的完整示例.

换句话说,我想要的是映射红圈位置的新坐标值(在它们旁边写的那些),以便我可以从新坐标值获得旧坐标(例如(1,1) – >(170.82191781),162.67123288)).我还想要一些不接近真实点所描述的理想网格的点(如图所示),最后使用理想网格参数(大约为0)填充空理想网格位置(蓝色圆圈).,0) – >(55,55)).

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

  1. def build_grid(X,x_offset,y_offset,dx,dy,grid_shape=(16,24),square_distance_threshold=None):
  2. if square_distance_threshold is None:
  3. square_distance_threshold = ((dx + dy) / 2.0 * 0.05) ** 2
  4. grid = np.zeros(grid_shape + (2,dtype=np.float)
  5. D = np.zeros(grid_shape)
  6. for i in range(grid_shape[0]):
  7. for j in range(grid_shape[1]):
  8. D[i,j] = i * (1 + 1.0 / (grid_shape[0] + 1)) + j
  9. rD = D.ravel().copy()
  10. rD.sort()
  11. def find_valid(x,y):
  12. d = (X - x) ** 2 + (Y - y) ** 2
  13. valid = d < square_distance_threshold
  14. if valid.any():
  15. pos = d == d[valid].min()
  16. if pos.sum() == 1:
  17. return X[pos],Y[pos]
  18. return x,y
  19. x = x_offset
  20. y = y_offset
  21. first_loop = True
  22. for v in rD:
  23. #get new position
  24. coord = np.where(D == v)
  25. #generate a reference position already passed
  26. if coord[0][0] > 0:
  27. old_coord = (coord[0] - 1,coord[1])
  28. elif coord[1][0] > 0:
  29. old_coord = (coord[0],coord[1] - 1)
  30. if not first_loop:
  31. #calculate ideal step
  32. x,y = grid[old_coord].ravel()
  33. x += (coord[0] - old_coord[0]) * dx
  34. y += (coord[1] - old_coord[1]) * dy
  35. #modify with observed point close to ideal if exists
  36. x,y = find_valid(x,y)
  37. #put in grid
  38. #print coord,grid[coord].shape
  39. grid[coord] = np.array((x,y)).reshape(grid[coord].shape)
  40. first_loop = False
  41. return grid

它提出了另一个问题:如何很好地迭代2D阵列的对角线,但我认为这值得一个自己的问题:More numpy way of iterating through the ‘orthogonal’ diagonals of a 2D array

编辑

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

最佳答案
这是一个相当简单和廉价的解决方案,但我不知道它有多强大.

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

  1. leeway = 1.10
  2. XX = X.reshape((1,X.size))
  3. dX = np.abs(XX - XX.T).reshape((1,X.size ** 2))
  4. dxs = dX[np.where(np.logical_and(dX > expected_distance / leeway,dX < expected_distance * leeway))]
  5. dx = dxs.mean()
  6. YY = Y.reshape((1,Y.size))
  7. dY = np.abs(YY - YY.T).reshape((1,Y.size ** 2))
  8. dys = dY[np.where(np.logical_and(dY > expected_distance / leeway,dY < expected_distance * leeway))]
  9. dy = dys.mean()

代码计算X和Y的内部差异,并取得所需间距的10%以内的平均值.

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

  1. Ndx = np.array([np.arange(grid_size[0])]) * dx
  2. x_offsets = XX - Ndx.T
  3. x_offset = np.median(x_offsets)
  4. Ndy = np.array([np.arange(grid_size[1])]) * dy
  5. y_offsets = YY - Ndy.T
  6. y_offset = np.median(y_offsets)

基本上,这样做是为了让X中的每个位置“投票”NX = grid_size [0]位置,其中左下角可能是,基于X – n * dx,其中n = 0是对点本身的投票,n = 1是对左边的点dx的投票等.这样,真实原点附近的点将得到最多的投票,并且可以使用中值找到偏移.

我认为这种方法在所需的原点周围足够对称,中位数可以用于大多数(如果不是全部)情况.然而,如果存在许多误报,使得中位数由于某种原因不起作用,则可以使用例如“真实”来找到“真实”原点.直方图方法.

猜你在找的Python相关文章