OpenCV学习二十九：convexHull 凸包

1.概述

凸包(Convex Hull)是一个计算几何（图形学）中的概念，在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。 
X的凸包可以用X内所有点(x1, x2….xn)的线性组合来构造。在二维欧几里得空间中，凸包可以想象为一条刚好包着所有点的橡皮圈，用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。常见的有Graham’s Scan法和Jarvis步进法

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时，此标识被忽略。

#include <opencv2/opencv.hpp>    
#include <stdio.h>    
#include <stdlib.h>    
#include <iostream>  


using namespace cv;  
using namespace std;  


int main(int argc, char** argv)  
{  
	Mat img = imread("3.jpg", -1);
	pyrDown(img, img, Size(img.cols/2, img.rows/2), 4);
	imshow("img", img);imwrite("img.jpg", img);
	
	Mat canny_out;
	Canny(img, canny_out, 45, 127, 3, false);
	imshow("canny_out", canny_out);

	vector<vector<Point>> coutours;
	vector<Vec4i> hierachy;
	Mat coutoursImg;img.copyTo(coutoursImg);
	findContours(canny_out, coutours, hierachy, RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0,0));
	drawContours(coutoursImg, coutours, -1, Scalar(0,0,255), 1, 8, hierachy);	
	imshow("drawContours", coutoursImg);imwrite("coutoursImg.jpg", coutoursImg);

	vector<vector<Point>> hull(coutours.size());
	Mat hullImg;img.copyTo(hullImg);
	for (int i=0; i<coutours.size(); i++)
	{
		convexHull(coutours[i], hull[i], false, true);
	}
	drawContours(hullImg, hull, -1, Scalar(0,255,255), 1, 8, hierachy);
	imshow("drawHull", hullImg);imwrite("hullImg.jpg", hullImg);



	waitKey();
	return 1;
}  

原图

findcontours

findHull

理论部分摘自：opencv学习(四十一)之寻找凸包convexHull()