OpenCv--寻找凸包convexHull()

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);
}