logo标签列表

使用Python NumPy在3D空间中找到一个点的k个最近邻居。

pythonnumpyknn
4

我有一个包含n个点的三维点云，格式为np.array((n,3))。例如：

P = [[x1,y1,z1],[x2,y2,z2],[x3,y3,z3],[x4,y4,z4],[x5,y5,z5],.....[xn,yn,zn]]

我希望能够获取每个点的K近邻。例如，P1的K近邻可能是P2、P3、P4、P5、P6，P2的KNN可能是P100、P150、P2等等。
在Python中如何实现呢？请提供帮助。
2
可能是最快的最近邻算法的重复问题。 - Amadan
1
numpy.linalg.norm和numpy.argsort可能会有所帮助。请参见https://dev59.com/I3M_5IYBdhLWcg3wXyHZ - dkato
2个回答
15

可以使用 scipy.spatial.distance.pdist 来解决这个问题。

首先，让我们创建一个示例数组，存储在三维空间中的点：

import numpy as np
N = 10  # The number of points
points = np.random.rand(N, 3)
print(points)

输出:

array([[ 0.23087546,  0.56051787,  0.52412935],
       [ 0.42379506,  0.19105237,  0.51566572],
       [ 0.21961949,  0.14250733,  0.61098618],
       [ 0.18798019,  0.39126363,  0.44501143],
       [ 0.24576538,  0.08229354,  0.73466956],
       [ 0.26736447,  0.78367342,  0.91844028],
       [ 0.76650234,  0.40901879,  0.61249828],
       [ 0.68905082,  0.45289896,  0.69096152],
       [ 0.8358694 ,  0.61297944,  0.51879837],
       [ 0.80963247,  0.1680279 ,  0.87744732]])

我们为每个点计算到所有其他点的距离：
from scipy.spatial import distance
D = distance.squareform(distance.pdist(points))
print(np.round(D, 1))  # Rounding to fit the array on screen

输出：

array([[ 0. ,  0.4,  0.4,  0.2,  0.5,  0.5,  0.6,  0.5,  0.6,  0.8],
       [ 0.4,  0. ,  0.2,  0.3,  0.3,  0.7,  0.4,  0.4,  0.6,  0.5],
       [ 0.4,  0.2,  0. ,  0.3,  0.1,  0.7,  0.6,  0.6,  0.8,  0.6],
       [ 0.2,  0.3,  0.3,  0. ,  0.4,  0.6,  0.6,  0.6,  0.7,  0.8],
       [ 0.5,  0.3,  0.1,  0.4,  0. ,  0.7,  0.6,  0.6,  0.8,  0.6],
       [ 0.5,  0.7,  0.7,  0.6,  0.7,  0. ,  0.7,  0.6,  0.7,  0.8],
       [ 0.6,  0.4,  0.6,  0.6,  0.6,  0.7,  0. ,  0.1,  0.2,  0.4],
       [ 0.5,  0.4,  0.6,  0.6,  0.6,  0.6,  0.1,  0. ,  0.3,  0.4],
       [ 0.6,  0.6,  0.8,  0.7,  0.8,  0.7,  0.2,  0.3,  0. ,  0.6],
       [ 0.8,  0.5,  0.6,  0.8,  0.6,  0.8,  0.4,  0.4,  0.6,  0. ]])

您可以像这样阅读此距离矩阵：点1和点5之间的距离为distance[0, 4]。您还可以看到每个点与自身之间的距离为0，例如distance[6, 6] == 0。

我们对距离矩阵的每一行进行argsort处理，以获取每个点最近的点列表：

closest = np.argsort(D, axis=1)
print(closest)

输出：

[[0 3 1 2 5 7 4 6 8 9]
 [1 2 4 3 7 0 6 9 8 5]
 [2 4 1 3 0 7 6 9 5 8]
 [3 0 2 1 4 7 6 5 8 9]
 [4 2 1 3 0 7 9 6 5 8]
 [5 0 7 3 6 2 8 4 1 9]
 [6 7 8 9 1 0 3 2 4 5]
 [7 6 8 9 1 0 3 2 4 5]
 [8 6 7 9 1 0 3 5 2 4]
 [9 6 7 1 8 4 2 0 3 5]]

同样地，我们可以看到每个点都离自己最近。因此，除此之外，我们现在可以选择k个最接近的点：

k = 3  # For each point, find the 3 closest points
print(closest[:, 1:k+1])

输出:

[[3 1 2]
 [2 4 3]
 [4 1 3]
 [0 2 1]
 [2 1 3]
 [0 7 3]
 [7 8 9]
 [6 8 9]
 [6 7 9]
 [6 7 1]]

例如，我们看到对于点4，k=3个最近的点是1、3和2。
请注意，随着矩阵维度的增加，此解决方案将不可行。 - eduardokapp
10
@marijn-van-vliet的解决方案适用于大多数场景。然而，它被称为暴力方法，如果点云相对较大或者有计算/时间限制，您可能需要考虑构建KD-Tree以快速检索点的K近邻。
在Python中，sklearn库提供了一个易于使用的实现，链接如下：sklearn.neighbors.KDTree。
from sklearn.neighbors import KDTree
tree = KDTree(pcloud)

# For finding K neighbors of P1 with shape (1, 3)
indices, distances = tree.query(P1, K)

（另外在另一篇文章中，请查看以下答案以获取更详细的使用和输出：https://dev59.com/E6jja4cB1Zd3GeqP4QQh#48127117）
许多其他库都有基于KD-Tree的KNN检索实现，包括Open3D（基于FLANN）和scipy。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接