Open3D 中两个相似点云的 KD-Tree 密度计算时间存在显着差异

Question

我正在使用 Open3D 处理两个不同的点云，两者都包含 50,000,000 个点。我通过构建 KD 树然后查询最近的邻居来计算点云密度。然而，我遇到了意想不到的行为：第一个点云在 1 秒内计算密度，而第二个点云需要 2 分钟以上，尽管两者具有相同的点数。

据我了解，在构建 KD-Tree 后，查询最近点的时间复杂度应该为 O(log u2061n)，因此我预计两个点云的密度计算时间相似。然而，事实并非如此。

这是我的代码：

import open3d as o3d
import random
import time

def o3d_compute_density(point_cloud):
    print("Total number of points:", f'{len(point_cloud.points):,}'.replace(',', '.'))

    init_time = time.time()
    kdtree = o3d.geometry.KDTreeFlann(point_cloud)
    print("Time to create kdtree:", time.time() - init_time)

    random_indexes = [random.randint(0, len(point_cloud.points) - 1) for _ in range(min(len(point_cloud.points), 1_000))]

    init_time = time.time()
    sum = 0
    for i in random_indexes:
        point = point_cloud.points[i]
        [_, _, dists] = kdtree.search_knn_vector_3d(point, 2)
        sum += pow(dists[1], 1/2)

    print("Time to calculate density:", time.time() - init_time)
    return sum / len(random_indexes)

# Reading point clouds
pcd1 = o3d.io.read_point_cloud("./pcd1.ply", print_progress=True)
density1 = o3d_compute_density(pcd1)
print("Density:", density1)

pcd2 = o3d.io.read_point_cloud("./pcd2.ply", print_progress=True)
density2 = o3d_compute_density(pcd2)
print("Density:", density2)

输出：

对于第一个点云：

Total number of points: 50.000.000  
Time to create kdtree: 20.79 seconds  
Time to calculate density: 0.015 seconds  
Density: 0.0020725614732701775

对于第二个点云：

Total number of points: 50.000.000  
Time to create kdtree: 16.67 seconds  
Time to calculate density: 137.73 seconds  
Density: 0.0024792745855749337

我的问题：

1. 为什么两个点云具有相同数量的点，计算密度所需的时间却存在如此大的差异？

2. 这可能与点云本身的结构有关（例如，点的分布或点云属性）？如果是这样，分析它的好方法是什么？

3. 我可以应用任何特定于 Open3D 的优化来提高不同点云之间的性能一致性吗？

任何见解或建议将不胜感激！

您可以从以下链接

下载我正在使用的点云

Answer 1

构建 kd 树的方法不止一种，即使是相同的技术有时也会产生截然不同的树形状（深度、叶子数量、大小和到根的平均距离等）。这当然对 knn 搜索过程有影响。

Open3D 的实现依赖于 FLANN。在他们的网页上，据说“FLANN是一个用于在高维空间中执行快速近似最近邻搜索的库。它包含我们发现最适合最近邻搜索的算法集合，以及一个用于自动选择最佳算法的系统算法和最佳参数取决于数据集。”。

所以我的猜测是这与 FLANN 的 kd 树实现有关。

您可以详细查看 FLANN 网页或其 Github 页面上提供的研究论文以了解实施细节（也许可以在那里提出您的问题？）。

否则，Scipy 或 Scikit-learn 都提供可能值得尝试的 kd-tree 实现（看看行为是否存在差异）。