快速查找图像中最接近的非黑色像素

Question

我有一个随机的2D图像和稀疏的像素分散.
给定图像上的一个点,我需要找到距离背景颜色最近的像素的距离(黑色).
最快的方法是什么？

我能想出的唯一方法是为像素构建一个kd树.但我真的想避免这种昂贵的预处理.而且,似乎一棵kd树给了我超过我需要的东西.我只需要与某种东西的距离,我不关心这是什么东西.

Answer 1

就个人而言,我忽略了MusiGenesis对查询表的建议.

计算像素之间的距离并不昂贵,特别是对于这个初始测试,您不需要实际距离,因此不需要采用平方根.你可以使用距离^ 2,即:

r^2 = dx^2 + dy^2

此外,如果你一次向外走一个像素,请记住:

(n + 1)^2 = n^2 + 2n + 1

或者如果nx是当前值而ox是先前的值:

    nx^2  = ox^2 + 2ox + 1
          = ox^2 + 2(nx - 1) + 1
          = ox^2 + 2nx - 1
=>  nx^2 += 2nx - 1 

很容易看出它是如何工作的:

1^2 =  0 + 2*1 - 1 =  1
2^2 =  1 + 2*2 - 1 =  4
3^2 =  4 + 2*3 - 1 =  9
4^2 =  9 + 2*4 - 1 = 16
5^2 = 16 + 2*5 - 1 = 25
etc...

因此,在每次迭代中,您只需要保留一些中间变量:

int dx2 = 0, dy2, r2;
for (dx = 1; dx < w; ++dx) {  // ignoring bounds checks
   dx2 += (dx << 1) - 1;
   dy2 = 0;
   for (dy = 1; dy < h; ++dy) {
       dy2 += (dy << 1) - 1;
       r2 = dx2 + dy2;
       // do tests here
   }
}

田田!r ^ 2计算只有位移,加法和减去:)

当然,在任何体面的现代CPU上计算r ^ 2 = dx*dx + dy*dy可能与此一样快......

Answer 2

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

在理想的发现中,您只需进行一次昂贵的距离计算.

更新:因为您在这里计算像素到像素的距离(而不是任意精度浮点位置),您可以通过使用预先计算的查找表(只是逐个宽度的数组)来大大加速此算法给你距离作为x和y的函数.100x100阵列基本上花费40K内存,并且在原始点周围覆盖200x200平方,并且可以节省为找到的每个彩色像素进行昂贵的距离计算(无论是毕达哥拉斯算法还是矩阵代数)的成本.这个数组甚至可以预先计算并作为资源嵌入到您的应用程序中,以免您初始计算时间(这可能是严重的过度杀伤).

更新2:此外,还有一些方法可以优化搜索方形周长.您的搜索应该从与轴相交的四个点开始,一次向角落移动一个像素(您有8个移动的搜索点,这可能很容易让它比它的价值更麻烦,具体取决于您的应用程序的要求).一旦找到彩色像素,就不需要继续朝向角落,因为其余的点都离原点更远.

在第一个找到的像素之后,您可以使用查找表进一步将所需的附加搜索区域限制为最小值,以确保每个搜索点比找到的点更近(再次从轴开始,并在达到距离限制时停止) ).如果你必须在飞行中计算每个距离,那么第二次优化可能会非常昂贵.

如果最近的像素在200x200框内(或适用于您的数据的任何大小),则只能在由像素限定的圆内搜索,仅进行查找和<>比较.