快速找到图像中最近的非黑色像素 [英] Finding closest non-black pixel in an image fast

问题描述

我有一个随机且稀疏散布像素的 2D 图像.
给定图像上的一个点，我需要找到与背景颜色(黑色)以外的最近像素的距离.
执行此操作的最快方法是什么?

I have a 2D image randomly and sparsely scattered with pixels.
given a point on the image, I need to find the distance to the closest pixel that is not in the background color (black).
What is the fastest way to do this?

我能想到的唯一方法是为像素构建一个 kd 树.但我真的很想避免这种昂贵的预处理.此外，似乎 kd-tree 给了我比我需要的更多.我只需要到某物的距离，我不在乎这是什么东西.

The only method I could come up with is building a kd-tree for the pixels. but I would really want to avoid such expensive preprocessing. also, it seems that a kd-tree gives me more than I need. I only need the distance to something and I don't care about what this something is.

推荐答案

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

As Pyro says, search the perimeter of a square that you keep moving out one pixel at a time from your original point (i.e. increasing the width and height by two pixels at a time). When you hit a non-black pixel, you calculate the distance (this is your first expensive calculation) and then continue searching outwards until the width of your box is twice the distance to the first found point (any points beyond this cannot possibly be closer than your original found pixel). Save any non-black points you find during this part, and then calculate each of their distances to see if any of them are closer than your original point.

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

In an ideal find, you only have to make one expensive distance calculation.

更新:因为您在这里计算像素到像素的距离(而不是任意精度的浮点位置)，所以您可以通过使用预先计算的查找表(只是一个高度×宽度的数组)来给你距离作为 x 和 y 的函数.一个 100x100 的数组基本上会消耗 40K 的内存，并覆盖原始点周围 200x200 的正方形，并且为您找到的每个彩色像素省去了进行昂贵的距离计算(无论是勾股数还是矩阵代数)的成本.这个数组甚至可以预先计算并作为资源嵌入到您的应用程序中，以节省您的初始计算时间(这可能是严重的矫枉过正).

Update: Because you're calculating pixel-to-pixel distances here (instead of arbitrary precision floating point locations), you can speed up this algorithm substantially by using a pre-calculated lookup table (just a height-by-width array) to give you distance as a function of x and y. A 100x100 array costs you essentially 40K of memory and covers a 200x200 square around the original point, and spares you the cost of doing an expensive distance calculation (whether Pythagorean or matrix algebra) for every colored pixel you find. This array could even be pre-calculated and embedded in your app as a resource, to spare you the initial calculation time (this is probably serious overkill).

更新 2:此外，还有一些方法可以优化搜索正方形周长.您的搜索应该从与轴相交的四个点开始，并一次向角落移动一个像素(您有 8 个移动搜索点，这很容易使这变得更加麻烦，这取决于您的应用程序的要求).一旦找到一个有颜色的像素，就没有必要继续向角移​​动，因为其余的点都离原点更远.

Update 2: Also, there are ways to optimize searching the square perimeter. Your search should start at the four points that intersect the axes and move one pixel at a time towards the corners (you have 8 moving search points, which could easily make this more trouble than it's worth, depending on your application's requirements). As soon as you locate a colored pixel, there is no need to continue towards the corners, as the remaining points are all further from the origin.

在第一个找到的像素之后，可以进一步通过查找表将需要的额外搜索区域限制到最小，以确保每个搜索点都比找到的点更近(再次从坐标轴开始，到距离时停止)达到极限).如果您必须动态计算每个距离，那么采用第二个优化可能会太昂贵.

After the first found pixel, you can further restrict the additional search area required to the minimum by using the lookup table to ensure that each searched point is closer than the found point (again starting at the axes, and stopping when the distance limit is reached). This second optimization would probably be much too expensive to employ if you had to calculate each distance on the fly.

如果最近的像素在 200x200 框内(或适用于您的数据的任何尺寸)，您将只在以像素为界的圆圈内搜索，只进行查找和 <>比较.

If the nearest pixel is within the 200x200 box (or whatever size works for your data), you will only search within a circle bounded by the pixel, doing only lookups and <>comparisons.

这篇关于快速找到图像中最近的非黑色像素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！