这篇文章讲的是如何寻找给出的点集的凸包（Convex Hull），先简单介绍算法原理，之后利用OpenCV实现一个找凸包的程序。
什么是凸包（Convex Hull）？
这个问题可以分成两个概念理解，Convex 和 Hull
凸形状（Convex object）就是没有大于180°的内角的形状。不是凸形状的称为非凸（Non-Convex）或者凹的（Concave）。下图就是凸形状图像和凹形状图像的例子。
Convex-Concave.png
包（Hull）可以理解为一个物体的外形。
因此，凸包就是围绕点或形状的紧密拟合的凸边界。
上图中两个图像的凸包如下图所示。一个凸形状的凸包就是其边界，而一个凹边形的凸包就是一个能紧密包围该凹边形的凸边界。
convex-hull.jpg
Gift Wrapping Algorithms
给定一个点集，如何找出该点集的凸包？找凸包的算法称为Gift Wrapping Algorithms。有个YOUTUbe视频（打不开的话进原文观看）通过动画形式讲述了几个寻找凸包的算法。
表面看起来简单的算法，如果考虑上一些约束的话，事情就会变得不那么简单了。比如考虑算法的时间复杂度。
拿Jarvis March算法来说,时间复杂度为O(nh)，其中n是输入的点集总数，h是凸包上的点的个数。另外一个算法Chan's algorithm复杂度为O(nlogh)。
是否有复杂度为O(n)的算法？答案是有的。但是在这些算法的发展历史中有些尴尬的事情。
第一个O(n)算法是Sklansky在1972年发表。之后被证明是错的。在1972-1989几年中，有16个O(n)算法发表，但是有7个被证明是错的。更令人尴尬的是OpenCV实现的寻找凸包算法（Sklansky (1982))。也被证明是错的。
但是不要方。OpenCV实现的这个算法仍是一个很流行的算法而且在绝大多数情况下输出是正确的。下面来看看如何使用OpenCV来寻找凸包。
利用OpenCV寻找凸包
通过上面描述我们知道Gift Wrapping algorithms的目的是寻找点集的凸包。
那么我们如何将这个算法在图像中使用呢？
方法如下：先将一张图片二值化，然后找到图像中的轮廓，最后找出各个轮廓的凸包。下面一步一步通过代码来讲解：
Step 1：读入图片
Python
src = cv2.imread("sample.jpg", 1) # read input image
C++
Mat src;
src = imread("sample.jpg", 1); // read input image
Step 2: 二值化图像
二值化图像有下面三步：
- 讲图片转化为灰度图像
- 通过blur函数去除一些噪点
- 将灰度图像二值化
代码如下：
Python
gray = cv2.cvtColor(src, cv2.COLOR_BGR2GRAY) # convert to grayscale
blur = cv2.blur(gray, (3, 3)) # blur the image
ret, thresh = cv2.threshold(blur, 50, 255, cv2.THRESH_BINARY)
C++
Mat gray, blur_image, threshold_output;
cvtColor(src, gray, COLOR_BGR2GRAY); //convert to grayscale
blur(gray, blur_image, Size(3, 3)); // apply blur to grayscaled image
threshold(blur_image, threshold_output, 50, 255, THRESH_BINARY); //apply binary thresholding
三步的输出分别如下图所示
preprocessing-operations-1.png
Step 3: 使用findContour寻找轮廓
下面我们使用OpenCV的findContour函数找到二值图像中的所有轮廓。你可能会问为什么不适用边缘检测，边缘检测出的只是每个边缘的位置，而findContour函数返回的是每个轮廓为集合的一个列表，这是我们需要的。
Python
# Finding contours for the threshold image
im2, contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
C++
vector<vector<Point> > contours; // list of contours points
vector<Vec4i> hierarchy;
// find contours
findContours(threshold_output, contours, hierarchy, RETR_TREE, CHAIN_APPROX_SIMPLE, Point(0, 0))
结果如下
contours.png
Step 4：使用convexHull函数找轮廓的凸包
找凸包的函数使用方法如下
Python
# create hull array for convex hull points
hull = []
#calculate points for each contour
for i in range(len(contours)):
#creating convex hull object for each contour
hull.append(cv2.convexHull(contours[i], False))
C++
// create hull array for convex hull points
vector<vector<Point> > hull(contours.size());
for(int i = 0; i < contours.size(); i++)
convexHull(Mat(contours[i]), hull[i], False);
Step 5：显示凸包
因为凸包也是一种轮廓，所以可以使用OpenCV中的drawContours函数画出来。
Python
# create an empty black image
drawing = np.zeros((thresh.shape[0], thresh.shape[1], 3), np.uint8)
# draw contours and hull points
for i in range(len(contours)):
color_contours = (0, 255, 0) # green - color for contours
color = (255, 0, 0) # blue - color for convex hull
# draw ith contour
cv2.drawContours(drawing, contours, i, color_contours, 1, 8, hierarchy)
# draw ith convex hull object
cv2.drawContours(drawing, hull, i, color, 1, 8)
C++
// create a blank image (black image)
Mat drawing = Mat::zeros(threhold_output.size(), CV_8UC3)
for(int i = 0; i < contours.size(); i++){
Scalar color_contours = Scalar(0, 255, 0); // green - color for contours
Scalar color = Scalar(255, 0, 0); // blue - color for convex hull
// draw ith contour
drawContours(drawing, contours, i, colot_contours, 1, 8, vector<Vec4i>(), 0, Point());
// draw ith contour
drawContours(drawing, hull, i, color, 1, 8, vector<Vec4i>(), 0, Point());
}
最终输入如下图所示
output-convex-hull.png
关于凸包的应用
下面举几个凸包应用的例子
给一个点集找边界
比如之前的换脸的应用。通过Dlib库检测出人脸特征点后需要提取出人脸，这时候可以用寻找凸包的方法，如下图所示
convex-hull-example.jpg
这方面还有其他应用，比如Kinect，灰度深度图像就是一个点集，我们需要利用凸包来定位物体在场景中的位置等等。
防止发生碰撞（Collision Avoidance）
想象一辆汽车由一个点集构成的，如下图所示，如果想防止这辆汽车与其他障碍物发生碰撞，求任意轮廓之间的交比求两个凸多边形之间的冲突在计算量上要大多，这时候更应该使用凸包来代替轮廓。
convex-hull-car.png
参考文献
1.Applications and Algorithms of Convex Hull : Brilliant
2.Series of Convex Hull Algorithms and their Implementations: GeeksForGeeks
3.ConvexHull Documentation: OpenCV Docs
4.Sklansky’s Algorithm (1982)
网友评论