图像处理之计算任意点与轮廓点集中距离最近的点坐标
程序员文章站
2022-05-20 22:30:09
...
opencv中计算任意一点P与轮廓C的距离很简单，可以直接调用pointPolygonTest函数获取，但是想要知道轮廓C中哪个点与点P的距离最近却没有现成的函数可用。
思路一：一个最朴实的想法就是获取以点P为中心，半径为r的圆的坐标点集，一步步增大半径r，直到圆上某一点Q在轮廓C上，即点Q就是我们需要找的点。考虑到效率问题，有两个地方可以优化一下：1>把轮廓C的点集额外保存成x坐标和y坐标作为键值的map结构中，在通过判断y坐标和x坐标是否相等快速查找；2>可以直接调用pointPolygonTest获取点P到轮廓C的距离d，然后直接让半径r从d开始增大，避免不必要的迭代。
其中一个需要解决的问题是怎么通过中心点P和半径r获取圆上所有点的集合？这个问题并不像表面上看起来那么简单，我自己写了个getCirclePts函数(参考了opencv的circle函数)，代码如下：
vector<Point> getCirclePts(Point center, int radius)
{
vector<Point> ret;
int err = 0, dx = radius, dy = 0, plus = 1, minus = (radius << 1) - 1;
while(dx >= dy)
{
int mask;
int y11 = center.y - dy, y12 = center.y + dy, y21 = center.y - dx, y22 = center.y + dx;
int x11 = center.x - dx, x12 = center.x + dx, x21 = center.x - dy, x22 = center.x + dy;
ret.push_back(Point(x11,y11));
ret.push_back(Point(x11,y12));
ret.push_back(Point(x12,y11));
ret.push_back(Point(x12,y12));
ret.push_back(Point(x21,y21));
ret.push_back(Point(x21,y22));
ret.push_back(Point(x22,y21));
ret.push_back(Point(x22,y22));
dy++;
err += plus;
plus += 2;
mask = (err <= 0) - 1;
err -= minus & mask;
dx += mask;
minus -= mask & 2;
}
return ret;
}根据思路一写了份测试代码如下，把显示部分注释掉打印了在我笔记本上的每计算一次的执行时间大概200us。这个方法一个隐藏的缺点在于当点P与轮廓C距离较远时，需要获取以点P为中心的圆上点集数量比较多，再去遍历这些点判断是否在轮廓C上较为耗时。
void demo1()
{
Mat srcImg = imread("/home/gk/program/C++/CalcDistance/test1.png", IMREAD_GRAYSCALE);
Mat binaryImg;
threshold(srcImg, binaryImg, 128, 255, CV_THRESH_BINARY);
vector<vector<Point>> contours;
findContours(binaryImg, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE);
vector<Point>& pts = contours[0];
map<int,vector<Point>> pts_x,pts_y;
for(auto pt : pts)
{
//将轮廓坐标保存成键值对的形式，便于查找
pts_x[pt.x].push_back(pt);
pts_y[pt.y].push_back(pt);
}
for(int x=0,y=0; x<srcImg.cols&&y<srcImg.rows; x+=2,y++)
{
Mat showImg;
cvtColor(binaryImg, showImg, CV_GRAY2BGR);
Point nearestPt;
bool flag = false;
int min_d = static_cast<int>(abs(pointPolygonTest(pts, Point(x,y), true)));
int d = min_d;
while(true)
{
vector<Point> points = getCirclePts(Point(x,y), d);
//遍历圆上的点
for(auto curPt : points)
{
//判断该点是否也在轮廓上
for(auto pt : pts_x[curPt.x])
{
if(pt.y == curPt.y)
{
nearestPt = pt;
flag = true;
break;
}
}
if(flag) break;
}
if(flag) break;
d++;
}
if(flag)
{
circle(showImg, nearestPt, 2, Scalar(0,0,255), 2);
}
circle(showImg, Point(x,y), 2, Scalar(0,255,0), 2);
imshow("show", showImg);
waitKey(50);
}
}思路二：将思路一中以点P为中心以圆的方式扩张改成以矩形的方式扩张，好处在于要描述圆的点集必须遍历圆上每一个点，而描述一个矩形只需要4个顶点就可以了。同样调用pointPolygonTest获取点P到轮廓C的距离d(需要找的点Q与给定点P的距离为d)，当点Q在矩形顶点时，此时矩形边长为(d/0.707)*2即可覆盖点Q，当点Q在矩形边长中心时，矩形边长d*2才能覆盖点Q，因此矩形的边长迭代范围确定好了，只需要在迭代过程中找到距离点P最小的轮廓C上的点即可。
代码如下，把显示部分注释掉打印了在我笔记本上的每计算一次的执行时间大概40us。
void demo2()
{
Mat srcImg = imread("/home/gk/program/C++/CalcDistance/test1.png", IMREAD_GRAYSCALE);
Mat binaryImg;
threshold(srcImg, binaryImg, 128, 255, CV_THRESH_BINARY);
vector<vector<Point>> contours;
findContours(binaryImg, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE);
vector<Point>& pts = contours[0];
map<int,vector<Point>> pts_x,pts_y;
for(auto pt : pts)
{
pts_x[pt.x].push_back(pt);
pts_y[pt.y].push_back(pt);
}
for(int x=0,y=0; x<srcImg.cols&&y<srcImg.rows; x+=2,y++)
{
Mat showImg;
cvtColor(binaryImg, showImg, CV_GRAY2BGR);
bool rectFlag = false;
bool findFlag = false;
Point nearestPt;
int max_d = INT_MAX;
double min_dist = DBL_MAX;
double v = pointPolygonTest(pts, Point(x,y), true);
int min_d = static_cast<int>(abs(0.707*distance));
for(int d=min_d; d<max_d; d++)
{
//矩形的上下左右边界，分别判断这四条边界的情况
int minx=x-d,maxx=x+d,miny=y-d,maxy=y+d;
for(auto pt : pts_x[minx])
{
if(pt.y>=miny && pt.y<=maxy)
{
double temp_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2));
if(abs(temp_d-abs(distance)) < 0.01)
{
//当找到的点与点P的距离与distance基本一致时直接结束迭代
nearestPt = pt;
findFlag = true;
break;
}
if(!rectFlag)
{
//当矩形框首次覆盖到轮廓上的点时，确定max_d
rectFlag = true;
max_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2))+0.5;
}
if(temp_d < min_dist)
{
min_dist = temp_d;
nearestPt = pt;
}
}
}
if(findFlag) break;
for(auto pt : pts_y[miny])
{
if(pt.x>=minx && pt.x<=maxx)
{
double temp_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2));
if(abs(temp_d-abs(distance)) < 0.01)
{
nearestPt = pt;
findFlag = true;
break;
}
if(!rectFlag)
{
rectFlag = true;
max_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2))+0.5;
}
if(temp_d < min_dist)
{
min_dist = temp_d;
nearestPt = pt;
}
}
}
if(findFlag) break;
for(auto pt : pts_x[maxx])
{
if(pt.y>=miny && pt.y<=maxy)
{
double temp_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2));
if(abs(temp_d-abs(distance)) < 0.01)
{
nearestPt = pt;
findFlag = true;
break;
}
if(!rectFlag)
{
rectFlag = true;
max_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2))+0.5;
}
if(temp_d < min_dist)
{
min_dist = temp_d;
nearestPt = pt;
}
}
}
if(findFlag) break;
for(auto pt : pts_y[maxy])
{
if(pt.x>=minx && pt.x<=maxx)
{
double temp_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2));
if(abs(temp_d-abs(distance)) < 0.01)
{
nearestPt = pt;
findFlag = true;
break;
}
if(!rectFlag)
{
rectFlag = true;
max_d = sqrt(pow(pt.x-x,2)+pow(pt.y-y,2))+0.5;
}
if(temp_d < min_dist)
{
min_dist = temp_d;
nearestPt = pt;
}
}
}
if(findFlag) break;
}
if(findFlag || rectFlag)
{
circle(showImg, nearestPt, 2, Scalar(0,0,255), 2);
}
circle(showImg, Point(x,y), 2, Scalar(0,255,0), 2);
imshow("show", showImg);
waitKey(50);
}
}效果如下所示，红点表示任意点P，绿点表示找到的轮廓上最近的点Q
上一篇： RadioButton右上角添加红点提醒