计算机视觉——OpenCV C++实现凸包_凸包算法 c++实现

概述

在图像中发现和分析形式是解决大多数计算机视觉问题的技巧之一，获取轮廓是其中之一。对于新手来说，我会将轮廓描述为“仅仅是一条连接所有位于形状边缘上的点的曲线。”

假设我有下面这张手的图像，手的轮廓由绿线表示。红点代表我们将连接起来形成轮廓曲线的点。

我对轮廓的高级数学课程记忆犹新。然而，由于老师从未强调过轮廓在现实世界中的应用，所以很难理解这个主题的重要性。今天，我发现它在计算机视觉中的重要性。

什么是凸包？

一个没有大于180度的内角的物品被称为凸形的。非凸形或凹形是指不是凸形的形状。一个物体的外部或形状被称为外壳。

因此，一个形状或一组点的凸包是紧密围绕这些点或形状的凸形边界。

用外行话来说，一个物体的凸包是能够完全环绕或包裹该物体（或该物体的轮廓）的最小边界。

可以使用多种方法找到凸包。以下是一些最常见的算法及其相关的时间复杂度。输入点的数量为n，而外壳上的点的数量为h。

• Sklansky (1982) — O(nlogn) （OpenCV使用此算法）
• 礼物包装，又称Jarvis步进 — O(nh)
• Graham扫描 — O(nlogn)
• Chan算法 — O(nlogh)

使用OpenCV实现凸包

1. 读取输入图像

src = cv::imread(argv[1], cv::IMREAD_GRAYSCALE);
1

2. 将输入图像转换为二进制形式

将图像转换为灰度（在读取图像时已经完成）。

通过应用任何模糊算法从图像中去除噪声（这里我使用了高斯模糊）。

然后将图像阈值化，使其成为二进制形式。

cv::GaussianBlur(src, src, cv::Size(3,3), 0); // 应用3x3核的高斯模糊
ShowImg("Image After Applying Blur", src);
const int max_thresh = 255;
const std::string source_window = "Canny ";
cv::createTrackbar("Canny thresh:", source_window, &thresh, max_thresh, thresh_callback);
thresh_callback(0, 0);
cv::waitKey();
return 0;
}

void thresh_callback(int, void*) {
cv::Mat canny_output;
cv::Canny(src, canny_output, thresh, thresh*2);
....
1
2
3
4
5
6
7
8
9
10
11
12
13
14

接下来，我们使用OpenCV的findContour函数找到每个图像周围的轮廓。

如果你是新手，你可能会想知道为什么我们不只是使用边缘检测。边缘检测只会提供边缘的位置。

然而，我们对边缘是如何相互连接的感到好奇。findContour找到连接并返回构成轮廓的点列表。

std::vector<std::vector<cv::Point>> contours;
cv::findContours(canny_output, contours, cv::RETR_TREE, cv::CHAIN_APPROX_SIMPLE);
....
1
2
3

使用convexHull函数找到凸包

现在我们已经得到了轮廓，我们可以为每个轮廓找到凸包了。可以使用convexHull函数来实现。

std::vector<std::vector<cv::Point>> hull(contours.size());
for (size_t i = 0; i < contours.size(); i++) {
    cv::convexHull(contours[i], hull[i]);
}
....
1
2
3
4
5

绘制凸包

最后一步是可视化我们到目前为止发现的凸包。因为凸包本质上是一个轮廓，我们可以使用OpenCV的drawContours函数来创建一个。

cv::Scalar contours_color = cv::Scalar(255,0,0); // 蓝色
cv::Scalar hull_color = cv::Scalar(0,0,255); // 红色
for (size_t i = 0; i < contours.size(); i++) {
    cv::Scalar color = cv::Scalar(rng.uniform(0, 256), rng.uniform(0,256), rng.uniform(0,256));
    cv::drawContours(drawing, contours, (int)i, contours_color);
    cv::drawContours(drawing, hull, (int)i, hull_color);
}
ShowImg("Hull: ", drawing);
1
2
3
4
5
6
7
8

输出

应用

• 从一组点创建边界
• 我们的面部交换应用程序之前使用了凸包。我们使用凸包根据Dlib发现的面部标记找到面部的边界。
• 在许多其他应用中，我们可以恢复特征点信息而不是轮廓信息。我们在几种活动照明系统中，如Kinect，恢复了一个灰度深度图，这是一组点的集合。这些点的凸包可以用来找到场景中物体的边界。
• 避免碰撞
• 考虑汽车是一组点的集合，多边形（最小集）包含所有这些点。如果凸包可以避开障碍物，那么汽车也应该可以。
• 找到随机轮廓的交集比找到两个凸多边形的碰撞要计算上更复杂。因此，凸包更适合于碰撞检测和避免。

参考文献

• OpenCV计算机视觉应用程序编程手册
• OpenCV 4计算机视觉应用程序编程手册：使用OpenCV和C++构建复杂的计算机视觉应用程序，第4版
• 现代C++编程手册
• OpenCV文档

代码

#include "opencv2/imgcodecs.hpp"
#include "opencv2/highgui.hpp"
#include "opencv2/imgproc.hpp"

cv::Mat src;
int thresh = 100;
void thresh_callback(int, void);
void ErrorMsg(std::string msg) {
    std::cout << "!! Error !! n";
    std::cout << msg << std::endl;
}
void ShowImg(const std::string windowName, cv::Mat& img) {
    cv::namedWindow(windowName);
    cv::imshow(windowName, img);
}

int main(int argc, char argv[]) {
    if(argc < 1) {
        ErrorMsg("Please Provide Input Imagen");
    }
    src = cv::imread(argv[1], cv::IMREAD_GRAYSCALE);
    if (src.empty()) {
        ErrorMsg("Could not open or find the image!n");
        return -1;
    }
    cv::GaussianBlur(src, src, cv::Size(3,3), 0); // 应用3x3核的高斯模糊
    ShowImg("Image After Applying Blur", src);
    const int max_thresh = 255;
    const std::string source_window = "Canny ";
    cv::createTrackbar("Canny thresh:", source_window, &thresh, max_thresh, thresh_callback);
    thresh_callback(0, 0);
    cv::waitKey();
    return 0;
}

void thresh_callback(int, void) {
    cv::Mat canny_output;
    cv::Canny(src, canny_output, thresh, thresh*2);
    std::vector<std::vector<cv::Point>> contours;
    cv::findContours(canny_output, contours, cv::RETR_TREE, cv::CHAIN_APPROX_SIMPLE);
    std::vector<std::vector<cv::Point>> hull(contours.size());
    for (size_t i = 0; i < contours.size(); i++) {
        cv::convexHull(contours[i], hull[i]);
    }
    cv::Mat drawing = cv::Mat::zeros(canny_output.size(), CV_8UC3);
    cv::Scalar contours_color = cv::Scalar(255,0,0); // 蓝色
    cv::Scalar hull_color = cv::Scalar(0,0,255); // 红色
    for (size_t i = 0; i < contours.size(); i++) {
        cv::Scalar color = cv::Scalar(rng.uniform(0, 256), rng.uniform(0,256), rng.uniform(0,256));
        cv::drawContours(drawing, contours, (int)i, contours_color);
        cv::drawContours(drawing, hull, (int)i, hull_color);
    }
    ShowImg("Hull: ", drawing);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

这里详细介绍了凸包的概念、实现方法以及在计算机视觉中的应用，并提供了C++代码示例。凸包是计算机视觉中一个重要的概念，用于确定一组点或形状的最小凸形边界。