在均匀网格上找到距点云最近点的距离 [英] Finding distance to the closest point in a point cloud on an uniform grid

问题描述

我有一个大小为AxBxC的3D网格，网格中的点之间的距离为d。给定多个点，给定以下假设，找到每个网格点到最近点的距离的最佳方法是什么（每个网格点都应包含到点云中到最近点的距离）？

I have a 3D grid of size AxBxC with equal distance, d, between the points in the grid. Given a number of points, what is the best way of finding the distance to the closest point for each grid point (Every grid point should contain the distance to the closest point in the point cloud) given the assumptions below?

假定A，B和C相对于d很大，给出的网格可能为500x500x500，并且将有大约100万个点。

Assume that A, B and C are quite big in relation to d, giving a grid of maybe 500x500x500 and that there will be around 1 million points.

还假设，如果到最近点的距离超过了D的距离，我们不在乎最近点的距离，可以安全地将其设置为较大的距离数字（D可能是d的2到10倍）

Also assume that if the distance to the nearest point exceds a distance of D, we do not care about the nearest point distance, and it can safely be set to some large number (D is maybe 2 to 10 times d)

由于存在大量的网格点和要搜索的点，因此很简单：

Since there will be a great number of grid points and points to search from, a simple exhaustive:

for each grid point:
   for each point:
     if distance between points < minDistance:
       minDistance = distance between points

不是很好的选择。

我正在考虑采取以下措施：

I was thinking of doing something along the lines of:

create a container of size A*B*C where each element holds a container of points
for each point:
  define indexX = round((point position x - grid min position x)/d)
  // same for y and z
  add the point to the correct index of the container

for each grid point:
  search the container of that grid point and find the closest point
  if no points in container and D > 0.5d:
    search the 26 container indices nearest to the grid point for a closest point
  .. continue with next layer until a point is found or the distance to that layer 
        is greater than D

基本上：将点放在桶中并向外进行径向搜索，直到为每个网格找到一个点点。这是解决问题的好方法，还是有更好/更快的方法？优选对并行化有利的解决方案。

Basically: put the points in buckets and do a radial search outwards until a points is found for each grid point. Is this a good way of solving the problem, or are there better/faster ways? A solution which is good for parallelisation is preferred.

推荐答案

实际上，我认为我有更好的方法，因为网格点的数量远大于网格点的数量。采样点。让| Grid | = N，|样本| = M，则最接近的邻居搜索算法将类似于O（N lg M），因为您需要查找所有N个网格点，并且每次查找（最佳情况下）均为O（lg M）。

Actually, I think I have a better way to go, as the number of grid points is much larger than the number of sample points. Let |Grid| = N, |Samples| = M, then the nearest neighbor search algorithms will be something like O(N lg M), as you need to look up all N grid points, and each lookup is (best case) O(lg M).

相反，循环遍历采样点。为每个网格点存储到目前为止找到的最接近的采样点。对于每个样本点，只需检查样本距离D内的所有网格点，以查看当前样本是否比以前处理过的样本更近。

Instead, loop over the sample points. Store for each grid point the closest sample point found so far. For each sample point, just check all grid points within distance D of the sample to see if the current sample is closer than any previously processed samples.

运行时间为O（N +（D / d）^ 3 M），当D / d较小时应该会更好。

The running time is then O(N + (D/d)^3 M) which should be better when D/d is small.

即使D / d较大，您可能仍然会如果可以制定出一项截止策略，那就可以了。例如，如果我们正在检查距样本的栅格点距离5，并且该栅格点已被标记为距先前样本的距离1，则不需要检查该栅格点之外的所有栅格点因为可以保证先前的样本比我们正在处理的当前样本更近。您所要做的就是（我认为这并不容易，但应该可行）定义 beyond的含义，并弄清楚如何遍历网格以避免对超出网格点的区域进行任何工作

Even when D/d is larger, you might still be OK if you can work out a cutoff strategy. For example, if we're checking a grid point distance 5 from our sample, and that grid point is already marked as being distance 1 from a previous sample, then all grid points "beyond" that grid point don't need to be checked because the previous sample is guaranteed to be closer than the current sample we're processing. All you have to do is (and I don't think it is easy, but should be doable) define what "beyond" means and figure out how to iterate through the grid to avoid doing any work for areas "beyond" such grid points.

这篇关于在均匀网格上找到距点云最近点的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！