python - 在 sklearn NearestNeighbor 中使用每个邻居一次

Question

我正在比较两个不同大小的点云。我不想切断较大的点云 pc1 中的最后一点。对于 pc1 中的点，我想在 pc2 中找到最近的邻居。在 pc1 和 pc2 中使用该点后，它应该不再次用于任何其他比较。计算从 pc1 到 pc2 的距离:从最小距离开始。获取 pc1 和 pc2 中的两个点并将这些点标记为已使用(或删除)。获取下一个更高距离的下一对……直到 pc2 中的所有点都被使用。返回距离列表。

到目前为止，这是我尝试过的:

from sklearn.neighbors import NearestNeighbors
import numpy as np

pc1 = np.array([[-1, -1], [-2, -1], [1, 1], [2, 2], [3, 5]])
pc2 = np.array([[0, 0], [0, 0], [6,6]])

nbrs = NearestNeighbors(n_neighbors=1, algorithm='kd_tree', metric='euclidean').fit(pc2)
distances, indices = nbrs.kneighbors(pc1)

这是输出:

indices = [[0],[0],[0],[0],[2]]

但我想要:

indices_wanted = [[0],[1],[2]]

应该指pc1中的点:[[-1, -1], [1, 1], [3, 5]]

有没有一种有效的方法来做到这一点？我的点云是 3D 的，每个点云大约有 8000 个点。它应该非常快，因为我需要为某些 200 帧的“电影”中的每一帧重复此过程。在 3D 中创建一些示例数据:

    pc1 = np.random.randn(8000,3)
    pc2 = np.random.randn(7990,3)

这是一张图片来说明情况:

红色点是pc1，绿色点是pc2。最终，我得到了 3D 点。

---

编辑:

我并不局限于sklearn，我只知道它非常高效。所以KDTree也是一种选择。我可能必须包括两个节点的最大距离以加快这种方法。我正在使用的立方体大小为 4m(在运行邻居搜索之前我已经删除了太远的点)

---

问题:@user2874583 提供的代码对于一组 8000 点大约需要 0.8s。那太慢了。我需要不到 0.2 秒。有没有办法修改代码以利用结构:没有外部点的立方体？也许对数组进行排序？

Answer 1

您可以使用 scipy 库来计算两点之间的距离。

from scipy.spatial.distance import cdist

def closest_node_index(node, nodes):
    index = cdist([node], nodes).argmin()
    return index

final = []
for arr in pc2:
    i = closest_node_index(arr, pc1)
    final.append(pc1[i])
    pc1 = np.delete(pc1, i, axis=0)