python - 高效计算点云的体素指数

Question

假设我有一个输入点云 X，由维度数组 N x 3 表示。此数组中的每一行对应于 XYZ 空间中的一个点，介于 -1 和 1 之间。现在，让 k 成为定义体素网格分辨率的参数(例如 k = 3 对应于尺寸 3 x 3 x 3) 的体素网格。 我正在寻找一种有效的方法来计算每个点对应的体素的索引。这或多或少是我目前使用 NumPy 的方式(为了清楚起见，写得更有表现力):

    # Generate some random input point cloud, 100 points
    X = np.random.randn(100, 3)
    # Define the resolution of the grid (e.g. say 3 x 3 x 3)
    k = 3
    # Iterate through points of input point cloud
    for j, point in enumerate(X):
        # Placeholder for voxel membership
        partitions = np.zeros(3,)

        for i, p in enumerate(point):
            for d in range(k):
                # Points are between -1 and 1, so the interval for each dimension is [-1, 1]
                # Length 2, "left"/"lower" end is -1
                if p <= (-1 + (d + 1) * 2 / k):
                    partitions[i] = d

        # Compute the index of the voxel this point belongs to
        # Can think of this as the base 10 representation of the base k number given by (x, y, z) in partitions
        # Voxels are indexed such that (0, 0, 0) --> index 0, (0, 0, 1) --> index 1, (0, 0, 2) --> 
        # index 2, (0, 1, 0) --> index 3, etc.
        p_reversed = np.flip(partitions)
        idx= 0
        for d in range(3):
            idx += (k ** d) * p_reversed[d]

       # Now idx corresponds to the index of the voxel to which point j belongs

随着 N 和 k 的增加，这显然很难扩展；有没有更高效的实现方式？

Answer 1

实际上，您是将您的点值作为 float 与一系列介于 -1 和 1 之间的其他 float 进行比较。

但是，您要做的是计算(一次)产生值的函数。执行简单的计算而不是迭代。

理想情况下，numpy 可以将这个简单的函数分布到您的分值列中。

更理想的是，它可以分布在整个数组中，允许您在单个操作或一系列操作中使用二维数组。

因为您使用的是固定的体素大小，并且因为您对所有维度使用相同的大小和相同的范围，所以我认为您可以通过简单的减法和乘法来实现:

1. 首先，减去将范围起点移至零所需的金额。在这种情况下，由于您的范围是 [-1, 1)，您可以将点值减去 -1(或加 +1)以使它们从 0 开始。

2. 接下来，将点值“缩放”到 [0, 1) 范围内。您可以乘以范围长度的倒数(高 - 低 == 1 - -1 == 2)，因此乘以 1/2 == 0.5。

3. 此时，您的中间值是该点所在范围的分数。因此，通过将该分数乘以体素范围 (3) 的大小，将它们映射到体素空间。并将结果值显式(通过函数)或隐式(通过数据类型)转换为整数。 Zen of Python说显式优于隐式，所以这是我的偏好。

如何编写代码？

RANGE_START = -1
RANGE_END = 1
VOXEL_K = 3

# Make up some points in the valid range
CLOUD = np.random.random((100, 3)) * (RANGE_END - RANGE_START) + RANGE_START

# shift points to 0-based:
zero_based_points = CLOUD - RANGE_START

# convert points to [0, 1) fraction of range
fractional_points = zero_based_points / (RANGE_END - RANGE_START)

# project points into voxel space: [0, k)
voxelspace_points = fractional_points * VOXEL_K

# convert voxel space to voxel indices (truncate decimals: 0.1 -> 0)
voxel_indices = voxelspace_points.astype(int)

注意: 浮点值可以是 nan 或 inf，它们不能很好地转换为整数。因此，您可能应该预处理您的点以以某种方式过滤这些值(用标记值替换它们或从数据集中消除它们或......？)