版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/keith_bb/article/details/70194073
1.概述
凸包(Convex Hull)是一个计算几何(图形学)中的概念,在一个实数向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X的凸包。
X的凸包可以用X内所有点(x1, x2….xn)的线性组合来构造。在二维欧几里得空间中,凸包可以想象为一条刚好包着所有点的橡皮圈,用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边形,它能包含点集中所有的点。常见的有Graham’s Scan法和Jarvis步进法
1.1 凸包的作用
凸包可以想象成一条刚好包住所有点的橡皮圈,对于二维的图像,凸包就是将最外层的点连接起来构成凸多边形,它能包含点集中所有的点。物体的凸包检测常常用于物体识别、手势识别及边界检测等领域。
OpenCV提供了函数convexHull()用于对物体轮廓凸包进行检测,对形状凸包缺陷分析时使用convexityDefects()函数,每个缺陷区包含四个特征量:起始点,结束点,距离及最远点。
2.原理
2.1Graham’s Scan法
Graham扫描法通过不断在凸壳中加入新的点和去除影响凸性的点,最后形成凸包。算法的主体由两部分组成,先是排序,然后扫描。
(1)点集排序
为了得到加入新点的顺序,Graham扫描法的第一步是对点集排序,对杂乱的点集进行梳理,这也是这种算法能够得到更高效的根本原因。排序的方法有极角坐标排序(极角序)和直角坐标排序(水平序)两种方法。在实现的时候,直角坐标排序比较方便。
对于极角序,首先选取一个参考点,一般选取横坐标最小的点作为参考点,如果有多个这样的点就从这些点钟选取纵坐标最小的点。如下图:
这样就决定了参考点的性质:点集中任意两点和参考点锁成的倒角为锐角。
极角排序以参考点为极角坐标系原点,根据上述参考点性质,可以设所有点的极角均在(-90,90]之间,排序完成后如下图所示:
(2)栈扫描
Graham扫描用的栈,其核心思想是按照拍好的序一次加入新点得到的边,边的寻找符合左旋判定。如果和上一条边成左转关系就压栈继续,如果右转就出栈直到和栈顶两点的边成左转关系,压栈继续。其栈扫描过程如下图所示:
2.2Jarvis步进法
其算法流程如下:
1.照横坐标最小的点(如有一样则取相同点纵坐标更小的点)
2.从这点开始卷包裹,照最靠近外侧的点(通过叉积比较)
3.遍历所有点,直到重新找到起点,退出。
3.OpenCV API函数
opencv提供了convexHull()函数来查找图像中物体的凸包,起函数定义如下:
void cv::convexHull ( InputArray points,
OutputArray hull,
bool clockwise = false,
bool returnPoints = true
)
参数解释
points:输入的二维点集,Mat类型数据即可
hull:输出参数,用于输出函数调用后找到的凸包
clockwise:操作方向,当标识符为真时,输出凸包为顺时针方向,否则为逆时针方向。
returnPoints:操作标识符,默认值为true,此时返回各凸包的各个点,否则返回凸包各点的指数,当输出数组时std::vector时,此标识被忽略。
代码实例:
- 转灰度
- canny得到二值图像(或者阈值转换)
- findcontours(寻找轮廓,找到候选点)
- convexhull(实现凸包api)
- 绘制显示
#include<opencv2\opencv.hpp>
#include<iostream>
using namespace std;
using namespace cv;
Mat src1, src2, gray_img, dst;
int value = 100;
int max_value = 255;
void demo(int, void*);
int main()
{
//发现轮廓-->凸包 -->: cvtcolor-->canny得到二值图像(或者阈值转换)-->findcontours(寻找轮廓,找到候选点)-->凸包api调用(convex hull)-->绘制显示
src1 = imread("C:\\Users\\马迎伟\\Desktop\\heibao.jpg");
//src2 = imread("C:\\Users\\马迎伟\\Desktop\\heibao1.png");
if (src1.empty())
{
printf("cannot load!!\n");
system("pause");
return -1;
}
namedWindow("input", CV_WINDOW_AUTOSIZE);
imshow("input", src1);
namedWindow("output", CV_WINDOW_AUTOSIZE);
cvtColor(src1, gray_img, CV_BGR2GRAY);
createTrackbar("creattrackbar", "output", &value, max_value, demo);
demo(0, 0);
waitKey(0);
return 0;
}
void demo(int, void*)
{
//将图像表现在src3上
Mat src3 = Mat::zeros(src1.size(), CV_8UC3);
vector<vector<Point>>contours;
vector<Vec4i>hierarchy;
Canny(gray_img, src2, value, value * 2, 3, false);
findContours(src2, contours, RETR_TREE, CHAIN_APPROX_SIMPLE, Point(0, 0));
vector<vector<Point>>convexhull(contours.size());
for (size_t i = 0; i < contours.size(); i++)
{
convexHull(contours[i],convexhull[i],true,false);
}
RNG rng(12345);
for (size_t i = 0; i < contours.size(); i++)
{
Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
//drawContours(src3, contours, i, color, 1, LINE_AA, hierarchy, 0, Point(0, 0));
drawContours(src3, convexhull, i, Scalar(255,255,255), 1, LINE_AA, hierarchy, 0, Point(0, 0));
}
imshow("output", src3);
}