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

EN

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

在理想的查找中，您只需进行一次昂贵的距离计算。

更新：因为您在这里计算像素到像素的距离(而不是任意精度的浮点位置)，您可以通过使用预先计算的查找表(只是一个高度乘以宽度的数组)来提供x和y的函数，从而大大加快此算法的速度。100x100数组基本上需要40K内存，覆盖原始点周围的200x200正方形，并且使您不必为找到的每个彩色像素执行昂贵的距离计算(无论是毕达哥拉斯式还是矩阵代数)。这个数组甚至可以预先计算并作为资源嵌入到您的应用程序中，以节省初始计算时间(这可能是严重的夸大其词)。

更新2：此外，还有一些方法可以优化搜索正方形的周边。你的搜索应该从与轴相交的四个点开始，一次向角移动一个像素(你有8个移动的搜索点，这很容易造成比它更多的麻烦，这取决于你的应用程序的要求)。一旦定位到彩色像素，就不需要继续朝向角落，因为其余的点都离原点更远。

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

如果最近的像素在200x200的框内(或您的数据的任意大小)，您将只在该像素所限定的圆圈内进行搜索，仅执行查找和<>comparisons。

就我个人而言，我会忽略MusiGenesis关于查找表的建议。

计算像素之间的距离不是很昂贵，特别是对于这个初始测试，你不需要实际的距离，所以不需要取平方根( root )。您可以使用距离^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可能就像这样快……

您没有指定要如何测量距离。我将假设L1 (直线型)，因为它更容易；这些想法可能会被修改为L2 (欧几里得)。

如果您只针对相对较少的像素执行此操作，则只需从源像素开始以螺旋方式向外搜索，直到遇到非黑色像素。

如果您要对许多/所有像素执行此操作，可以这样做:构建一个与图像大小相同的二维数组，其中每个单元格存储到最近的非黑色像素的距离(如果需要，还存储该像素的坐标)。执行四次线条扫描:从左到右、从右到左、从下到上和从上到下。考虑从左到右的扫描；在扫描时，保留包含每行中最后一个非黑色像素的一维列，并使用到该像素的距离和/或该像素的坐标标记二维阵列中的每个单元格。O(n^2)。

或者，k-d树过于夸张；您可以使用四叉树。编写代码只比我的行扫描稍微困难一点，内存稍微多一点(但不到我的两倍)，而且可能更快。