点云Voxel指数的有效计算

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

实际上，您正在将作为浮动的点值与-1到1之间的一系列其他浮点数进行比较。

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

理想情况下，这个简单的函数将是numpy可以分布在点值的列上的东西。

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

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

1. 首先，减去将范围的开始移动到零所需的金额。在这种情况下，由于您的范围是[ -1，1)，您将把-1(或add +1)减去点值，使它们从0开始。
2. 接下来，将点值“缩放”到范围[0，1]。你可以乘以范围的长度的倒数(高-低的== 1 -1 == 2)，所以乘以1/2 == 0.5。
3. 此时，您的中间值是发生点的范围的一部分。所以把它们映射到体素空间，把这个分数乘以体素范围(3)的大小。并将结果值显式(通过函数)或隐式(通过数据类型)转换为整数。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，它们不能很好地转换为整数。因此，您可能应该预处理您的点，以某种方式过滤这些值(用一个哨兵值替换它们，或者从数据集中删除它们，或者.？)

Answer 2

我的方法是：

N, k = 3, 10
np.random.seed(1)
X = np.random.normal(-1,1, (100,3))

# X:
# [[ 0.62434536 -1.61175641 -1.52817175]
# [-2.07296862 -0.13459237 -3.3015387 ]
# [ 0.74481176 -1.7612069  -0.6809609 ]]

# output:
np.argmax(X[:,:,None] < np.linspace(-1,1,k)[None, None, :], axis=-1)

输出：

array([[8, 0, 0],
       [0, 4, 0],
       [8, 0, 2]])