performance - 快速找到图像中最接近的非黑色像素

Question

我有一个2D图像，随机且稀疏地散布着像素。
给定图像上的一个点，我需要找到距背景颜色(黑色)以外的最近像素的距离。
最快的方法是什么？

我唯一能想到的方法是为像素构建一个kd树。但我真的想避免这种昂贵的预处理。同样，似乎kd树给了我更多的需求。我只需要到某个东西的距离，而我不在乎这是什么东西。

Answer 1

就像Pyro所说的那样，搜索一个正方形的周界，使您每次都从原始点移出一个像素(即，将宽度和高度一次增加两个像素)。当您碰到非黑色像素时，您将计算距离(这是您的第一个昂贵的计算)，然后继续向外搜索，直到框的宽度是到第一个找到的点的距离的两倍(超出此范围的任何点都不可能更接近)比您原来找到的像素)。保存在此部分中找到的所有非黑点，然后计算它们的每个距离，以查看它们是否都比原始点更近。

在理想的发现中，您只需要进行一次昂贵的距离计算即可。

更新:由于您是在这里计算像素到像素的距离(而不是任意的精度浮点位置)，因此可以通过使用预先计算的查找表(仅按宽度排列的宽度)来显着提高此算法的速度。 )来给你距离作为x和y的函数。 100x100阵列实际上要花费您40K的内存，并在原始点周围占据200x200平方的空间，并且可以节省您发现的每个彩色像素进行昂贵的距离计算(Pythagorean或矩阵代数)的成本。甚至可以预先计算该数组并将其作为资源嵌入到您的应用程序中，以节省您的初始计算时间(这可能是严重的过大杀伤力)。

更新2 :另外，还有一些方法可以优化对正方形周长的搜索。您的搜索应从与轴相交的四个点开始，并一次向一个角移动一个像素(您有8个移动的搜索点，根据您的应用程序的需求，这很容易造成超出其​​值(value)的麻烦)。一旦找到彩色像素，就无需继续向拐角移动，因为其余的点都离原点较远。

找到第一个像素后，可以通过使用查找表进一步确保将所需的额外搜索区域限制为最小，以确保每个搜索点都比找到的点更近(再次从轴开始，并在达到距离限制时停止)。如果必须实时计算每个距离，那么采用第二种优化方法可能会过于昂贵。

如果最近的像素在200x200框内(或任何适合您数据的大小)，则您将仅在以像素为界的圆内进行搜索，仅进行查找和<>比较。