版权声明:本文为博主原创文章,未经博主允许不得转载。 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);
}