发现最近的非黑色像素的图像快速 [英] 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树的像素想出的唯一方法。但我真的想避免这种昂贵的preprocessing。同时，如同一个kd树给了我比我更需要。我只需要一些距离，我不关心这是什么东西。

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.

推荐答案

由于火焰兵说，搜索一个正方形的周长，你不断从原始点移动了一个像素时间（即由两个增加的宽度和高度像素在一段时间）。当你打非黑色像素，则计算出的距离（这是你第一次昂贵的计算），然后继续寻找向外，直到你的框的宽度是两次第一个找到的点的距离（超出此的任何点不可能接近比你原来发现像素）。保存任何非黑点，你会发现这部分中，然后计算每个它们的距离，以查看是否有任何人比你原来的点更近。

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.

更新：因为你计算像素到像素的距离在这里（而不是任意的precision浮点运算单元），你可以在此算法大大使用$ P $加速对计算的查找表（只是高度由宽阵列）给你的距离为的 X 的功能和是的。 100×100阵列的成本你基本上是40K的内存和占地约原点一个200x200的正方形，备件你做一个昂贵的距离计算（不论是毕达哥拉斯或矩阵代数），对每个彩色像素找到的成本。该数组甚至可以是pre计算并嵌入到你的应用程序作为一种资源，饶你最初的计算时间（这可能是严重的矫枉过正）。

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.

如果最近的像素内的200×200盒（或任何大小为您的数据的工作），你将只能由像素包围的圈子内进行搜索，只能做查询和＆lt;>比较

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屋！