我有一张二维图像，其中的像素随机而稀疏地分布。
给定图像上的一个点，我需要找到离它最近的非背景颜色（黑色）像素的距离。
如何以最快的方式实现这个目标？
给定图像上的一个点，我需要找到离它最近的非背景颜色（黑色）像素的距离。
如何以最快的方式实现这个目标？
我能想到的唯一方法是为像素建立kd树。但我真的想避免这样昂贵的预处理。此外，似乎kd树给了我比我需要的更多信息。我只需要知道与某些东西的距离，并且不关心这个东西是什么。
10个回答
7
个人而言，我会忽略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可能与此一样快...
- Alnitak
3
你能将这个转化为一个真正的C函数吗？它接受一个输入的x、y位置和矩阵，并返回该位置。 - eri0o
@eri0o 不是的 - StackOverflow不是一个编写代码的服务。 - Alnitak
嘿，冠军，我进行了分析，我的结论是你的策略太慢了。我会坚持自己的方法。我只是想要一段代码，看看是否在我的实现中有问题。 - eri0o
6
正如Pyro所说，搜索一个正方形的周长，你可以从原始点开始每次移动一个像素（即每次增加两个像素的宽度和高度）。当你碰到一个非黑色像素时，你就计算距离（这是你第一次昂贵的计算），然后继续向外搜索，直到你的框的宽度是第一个找到的点的距离的两倍（任何超出此范围的点都不可能比你最初找到的像素更接近）。保存在此过程中发现的任何非黑色点，然后计算它们各自的距离，看看它们中是否有比你最初的点更接近的点。
在理想的情况下，你只需要进行一次昂贵的距离计算。
更新：因为你在这里计算的是像素之间的距离（而不是任意精度浮点位置），所以你可以通过使用预先计算的查找表（只是一个高度乘宽度的数组）来大大加快这个算法，以给出距离作为x和y的函数。一个100x100的数组基本上花费你40K的内存，并覆盖了原始点周围200x200的正方形，并节省了执行每个找到的有颜色像素的昂贵距离计算的成本（无论是勾股定理还是矩阵代数）。这个数组甚至可以预先计算并嵌入到你的应用程序中作为资源，以节省你的初始计算时间（这可能是严重过度）。
更新2：此外，有优化搜索正方形周长的方法。你的搜索应该从与坐标轴相交的四个点开始，每次向角落移动一个像素（你有8个移动搜索点，这可能会让它比它值得的麻烦，具体取决于你的应用程序的要求）。一旦你找到了一个彩色像素，就没有必要继续朝角落方向前进，因为剩下的点都离原点更远。
在找到第一个像素后，你可以通过使用查找表来确保每个搜索点都比找到的点更接近来进一步限制所需的附加搜索区域（再次从坐标轴开始，当达到距离限制时停止）。如果你必须即时计算每个距离，这第二个优化可能会非常昂贵。
如果最近的像素在200x200的框内（或适合你数据的任何大小），你只会在由像素限定的圆内进行搜索，只需要做查找和比较。
在理想的情况下，你只需要进行一次昂贵的距离计算。
更新：因为你在这里计算的是像素之间的距离（而不是任意精度浮点位置），所以你可以通过使用预先计算的查找表（只是一个高度乘宽度的数组）来大大加快这个算法，以给出距离作为x和y的函数。一个100x100的数组基本上花费你40K的内存，并覆盖了原始点周围200x200的正方形，并节省了执行每个找到的有颜色像素的昂贵距离计算的成本（无论是勾股定理还是矩阵代数）。这个数组甚至可以预先计算并嵌入到你的应用程序中作为资源，以节省你的初始计算时间（这可能是严重过度）。
更新2：此外，有优化搜索正方形周长的方法。你的搜索应该从与坐标轴相交的四个点开始，每次向角落移动一个像素（你有8个移动搜索点，这可能会让它比它值得的麻烦，具体取决于你的应用程序的要求）。一旦你找到了一个彩色像素，就没有必要继续朝角落方向前进，因为剩下的点都离原点更远。
在找到第一个像素后，你可以通过使用查找表来确保每个搜索点都比找到的点更接近来进一步限制所需的附加搜索区域（再次从坐标轴开始，当达到距离限制时停止）。如果你必须即时计算每个距离，这第二个优化可能会非常昂贵。
如果最近的像素在200x200的框内（或适合你数据的任何大小），你只会在由像素限定的圆内进行搜索，只需要做查找和比较。
- MusiGenesis
1
1我们真的需要将盒子大小扩大到两倍才能确保没有更近的点吗？我认为将盒子大小增加到 ceil(d * sqrt(2)) 应该就足够了。因为在大小为 d 的盒子中，距离最远的点是 d * sqrt(2)。所以，任何大于此值的盒子都不需要被检查。 - Punit Soni
2
好的，听起来很有趣。 我做了一个C++版本的解决方案，不知道这是否对你有帮助。我认为它的速度足够快，因为在800*600矩阵上几乎是瞬间完成的。如果你有任何问题，请随时问我。
对于我可能犯的任何错误，我表示抱歉，这只是10分钟的代码...... 这是一个迭代版本（我原本计划还要做一个递归版本，但我改变了主意）。 该算法可以通过不将任何距离起始点大于min_dist的点添加到点数组中来进行改进，但这需要计算每个像素（无论其颜色）与起始点之间的距离。
希望这有所帮助。
//(c++ version)
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
//ITERATIVE VERSION
//picture witdh&height
#define width 800
#define height 600
//indexex
int i,j;
//initial point coordinates
int x,y;
//variables to work with the array
int p,u;
//minimum dist
double min_dist=2000000000;
//array for memorising the points added
struct point{
int x;
int y;
} points[width*height];
double dist;
bool viz[width][height];
// direction vectors, used for adding adjacent points in the "points" array.
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int k,nX,nY;
//we will generate an image with white&black pixels (0&1)
bool image[width-1][height-1];
int main(){
srand(time(0));
//generate the random pic
for(i=1;i<=width-1;i++)
for(j=1;j<=height-1;j++)
if(rand()%10001<=9999) //9999/10000 chances of generating a black pixel
image[i][j]=0;
else image[i][j]=1;
//random coordinates for starting x&y
x=rand()%width;
y=rand()%height;
p=1;u=1;
points[1].x=x;
points[1].y=y;
while(p<=u){
for(k=0;k<=7;k++){
nX=points[p].x+dx[k];
nY=points[p].y+dy[k];
//nX&nY are the coordinates for the next point
//if we haven't added the point yet
//also check if the point is valid
if(nX>0&&nY>0&&nX<width&&nY<height)
if(viz[nX][nY] == 0 ){
//mark it as added
viz[nX][nY]=1;
//add it in the array
u++;
points[u].x=nX;
points[u].y=nY;
//if it's not black
if(image[nX][nY]!=0){
//calculate the distance
dist=(x-nX)*(x-nX) + (y-nY)*(y-nY);
dist=sqrt(dist);
//if the dist is shorter than the minimum, we save it
if(dist<min_dist)
min_dist=dist;
//you could save the coordinates of the point that has
//the minimum distance too, like sX=nX;, sY=nY;
}
}
}
p++;
}
cout<<"Minimum dist:"<<min_dist<<"\n";
return 0;
}
- XCS
1
我研究过的另一种方法，也很可能会坚持使用：利用Bresenham圆算法。 它非常快速，因为它不需要进行任何距离比较！ 你只需在目标点周围画出越来越大的圆，这样当你第一次遇到非黑色像素时，就自动知道它是最接近的，从而节省了进一步的检查。 我还没有验证Bresenham圆是否能捕捉到每个像素，但对于我的情况，这并不是一个问题，因为我的像素将以某种形式出现。
- DragonGamer
1
是的，最近邻搜索很好，但不能保证你会找到“最近”的像素。每次移动一个像素将产生一个正方形搜索 - 对角线距离比水平/垂直距离更远。如果这很重要，您需要验证 - 继续扩展，直到绝对水平距离大于“找到”的像素，然后计算所有定位的非黑色像素的距离。
- Kieveli
1
您没有说明您希望如何测量距离。我将假定使用L1（直线距离），因为它更容易；也许这些想法可以修改为L2（欧几里得距离）。
如果您只是对相对较少的像素进行操作，那么就从源像素向外螺旋搜索，直到找到一个非黑色像素。
如果您要对许多/所有像素进行操作，可以这样做：构建一个与图像大小相同的二维数组，其中每个单元格存储到最近的非黑色像素的距离（如果必要，还包括该像素的坐标）。进行四次线性扫描：从左到右、从右到左、从下到上和从上到下。考虑从左到右的扫描；在扫描时，保留一个包含每行中最后一个非黑色像素的一维列，并将2-D数组中的每个单元格标记为该像素的距离和/或坐标。O(n^2)。
另外，k-d树过于复杂；您可以使用四叉树。编码比我的线性扫描略微困难，需要更多的内存（但不到两倍），并且可能更快。
如果您只是对相对较少的像素进行操作，那么就从源像素向外螺旋搜索，直到找到一个非黑色像素。
如果您要对许多/所有像素进行操作，可以这样做：构建一个与图像大小相同的二维数组，其中每个单元格存储到最近的非黑色像素的距离（如果必要，还包括该像素的坐标）。进行四次线性扫描：从左到右、从右到左、从下到上和从上到下。考虑从左到右的扫描；在扫描时，保留一个包含每行中最后一个非黑色像素的一维列，并将2-D数组中的每个单元格标记为该像素的距离和/或坐标。O(n^2)。
另外，k-d树过于复杂；您可以使用四叉树。编码比我的线性扫描略微困难，需要更多的内存（但不到两倍），并且可能更快。
- Joe Ganley
1
我不认为扫描算法是正确的。如果最近的像素在某个对角线方向上，那么这种方法就无法找到它。它只会找到从该点出发的两个轴上的像素。 - shoosh
0
搜索“最近邻搜索”，谷歌的前两个链接应该会有所帮助。
如果您只是针对每张图像中的1个像素进行此操作，我认为您最好的选择就是进行线性搜索，一次一个像素宽度的框向外搜索。如果您的搜索框是正方形的，则不能仅取第一个找到的点，必须小心处理。
- Pyrolistical
0
你可以结合多种方法来加速它。
- 加速像素查找的一种方法是使用我所谓的空间查找映射。它基本上是该块中像素的降采样地图（例如8x8像素，但这是一个权衡）。值可以是“未设置像素”、“部分像素设置”、“所有像素设置”。这样，一次读取就可以告诉我们一个块/单元是完全满的、部分满的还是空的。
- 在中心周围扫描一个框/矩形可能不是理想的，因为有许多像素/单元离得很远。我使用圆形绘制算法（Bresenham）来减少开销。
- 原始像素值的读取可以按水平批次进行，例如一个字节（对于8x8或其倍数的单元大小），双字或长字。这应该再次给您带来严重的加速。
- 您还可以使用多个级别的“空间查找映射”，这又是一个权衡。
对于距离计算，可以使用上述提到的查找表，但这是一个（缓存）带宽与计算速度之间的权衡（例如，我不知道它在GPU上的表现如何）。
- Quonux
0
我相信这段代码还有改进的空间，但是这里提供一份代码，它会在中心像素周围的正方形范围内搜索，首先检查中心点，然后向角落移动。如果找不到像素，则扩大周长（半径），直到达到半径限制或找到像素为止。最初的实现是一个循环，在中心点周围简单地螺旋，但是如注所述，这并不能找到绝对最近的像素。在循环内创建SomeBigObjCStruct非常慢-将其从循环中删除后，效率就足够好了，使用了螺旋方法。但不管怎样，这里也提供这个实现-请注意，几乎没有测试。
这一切都是通过整数加减完成的。
- (SomeBigObjCStruct *)nearestWalkablePoint:(SomeBigObjCStruct)point {
typedef struct _testPoint { // using the IYMapPoint object here is very slow
int x;
int y;
} testPoint;
// see if the point supplied is walkable
testPoint centre;
centre.x = point.x;
centre.y = point.y;
NSMutableData *map = [self getWalkingMapDataForLevelId:point.levelId];
// check point for walkable (case radius = 0)
if(testThePoint(centre.x, centre.y, map) != 0) // bullseye
return point;
// radius is the distance from the location of point. A square is checked on each iteration, radius units from point.
// The point with y=0 or x=0 distance is checked first, i.e. the centre of the side of the square. A cursor variable
// is used to move along the side of the square looking for a walkable point. This proceeds until a walkable point
// is found or the side is exhausted. Sides are checked until radius is exhausted at which point the search fails.
int radius = 1;
BOOL leftWithinMap = YES, rightWithinMap = YES, upWithinMap = YES, downWithinMap = YES;
testPoint leftCentre, upCentre, rightCentre, downCentre;
testPoint leftUp, leftDown, rightUp, rightDown;
testPoint upLeft, upRight, downLeft, downRight;
leftCentre = rightCentre = upCentre = downCentre = centre;
int foundX = -1;
int foundY = -1;
while(radius < 1000) {
// radius increases. move centres outward
if(leftWithinMap == YES) {
leftCentre.x -= 1; // move left
if(leftCentre.x < 0) {
leftWithinMap = NO;
}
}
if(rightWithinMap == YES) {
rightCentre.x += 1; // move right
if(!(rightCentre.x < kIYMapWidth)) {
rightWithinMap = NO;
}
}
if(upWithinMap == YES) {
upCentre.y -= 1; // move up
if(upCentre.y < 0) {
upWithinMap = NO;
}
}
if(downWithinMap == YES) {
downCentre.y += 1; // move down
if(!(downCentre.y < kIYMapHeight)) {
downWithinMap = NO;
}
}
// set up cursor values for checking along the sides of the square
leftUp = leftDown = leftCentre;
leftUp.y -= 1;
leftDown.y += 1;
rightUp = rightDown = rightCentre;
rightUp.y -= 1;
rightDown.y += 1;
upRight = upLeft = upCentre;
upRight.x += 1;
upLeft.x -= 1;
downRight = downLeft = downCentre;
downRight.x += 1;
downLeft.x -= 1;
// check centres
if(testThePoint(leftCentre.x, leftCentre.y, map) != 0) {
foundX = leftCentre.x;
foundY = leftCentre.y;
break;
}
if(testThePoint(rightCentre.x, rightCentre.y, map) != 0) {
foundX = rightCentre.x;
foundY = rightCentre.y;
break;
}
if(testThePoint(upCentre.x, upCentre.y, map) != 0) {
foundX = upCentre.x;
foundY = upCentre.y;
break;
}
if(testThePoint(downCentre.x, downCentre.y, map) != 0) {
foundX = downCentre.x;
foundY = downCentre.y;
break;
}
int i;
for(i = 0; i < radius; i++) {
if(leftWithinMap == YES) {
// LEFT Side - stop short of top/bottom rows because up/down horizontal cursors check that line
// if cursor position is within map
if(i < radius - 1) {
if(leftUp.y > 0) {
// check it
if(testThePoint(leftUp.x, leftUp.y, map) != 0) {
foundX = leftUp.x;
foundY = leftUp.y;
break;
}
leftUp.y -= 1; // moving up
}
if(leftDown.y < kIYMapHeight) {
// check it
if(testThePoint(leftDown.x, leftDown.y, map) != 0) {
foundX = leftDown.x;
foundY = leftDown.y;
break;
}
leftDown.y += 1; // moving down
}
}
}
if(rightWithinMap == YES) {
// RIGHT Side
if(i < radius - 1) {
if(rightUp.y > 0) {
if(testThePoint(rightUp.x, rightUp.y, map) != 0) {
foundX = rightUp.x;
foundY = rightUp.y;
break;
}
rightUp.y -= 1; // moving up
}
if(rightDown.y < kIYMapHeight) {
if(testThePoint(rightDown.x, rightDown.y, map) != 0) {
foundX = rightDown.x;
foundY = rightDown.y;
break;
}
rightDown.y += 1; // moving down
}
}
}
if(upWithinMap == YES) {
// UP Side
if(upRight.x < kIYMapWidth) {
if(testThePoint(upRight.x, upRight.y, map) != 0) {
foundX = upRight.x;
foundY = upRight.y;
break;
}
upRight.x += 1; // moving right
}
if(upLeft.x > 0) {
if(testThePoint(upLeft.x, upLeft.y, map) != 0) {
foundX = upLeft.x;
foundY = upLeft.y;
break;
}
upLeft.y -= 1; // moving left
}
}
if(downWithinMap == YES) {
// DOWN Side
if(downRight.x < kIYMapWidth) {
if(testThePoint(downRight.x, downRight.y, map) != 0) {
foundX = downRight.x;
foundY = downRight.y;
break;
}
downRight.x += 1; // moving right
}
if(downLeft.x > 0) {
if(testThePoint(upLeft.x, upLeft.y, map) != 0) {
foundX = downLeft.x;
foundY = downLeft.y;
break;
}
downLeft.y -= 1; // moving left
}
}
}
if(foundX != -1 && foundY != -1) {
break;
}
radius++;
}
// build the return object
if(foundX != -1 && foundY != -1) {
SomeBigObjCStruct *foundPoint = [SomeBigObjCStruct mapPointWithX:foundX Y:foundY levelId:point.levelId];
foundPoint.z = [self zWithLevelId:point.levelId];
return foundPoint;
}
return nil;
}
- Adam Eberbach
-1
我会做一个简单的查找表 - 对于每个像素，预先计算到最近的非黑色像素的距离，并将该值存储在与相应像素相同偏移量的位置。当然，这样你需要更多的内存。
- Geee
2
重点是要避免O（点数）的长时间处理操作。 - shoosh
好的，我认为预处理与查找距离相比会更少进行。 - Geee
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接