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

Question

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

这是我到目前为止尝试过的方法：

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)

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

Use each neighbor once in sklearn NearestNeighbor

python

numpy

scikit-learn

nearest-neighbor

point-clouds