OpenCV 凸包查找,Graham详解

简介: OpenCV 凸包查找,Graham详解

凸包介绍


什么是凸包?


什么是凸包(Convex Hull),在一个多变形边缘或者内部任意两个点的连线都包含在多边形边界或者内部。


例如下图左侧为凸包,右侧因为有两个点的连线不包含在多边形边界或者内部,所以不是凸包



正式定义:


包含点集合S中所有点的最小凸多边形称为凸包


凸包查找——Graham扫描算法


首先选择Y方向最低的点作为起始点p0


从p0开始极坐标扫描,依次添加p1….pn(排序顺序是根据极坐标的角度大小,逆时针方向),添加的思想是:先找到凸包上的一个点,然后从那个点开始按逆时针方向逐个找凸包上的点,实际上就是进行极角排序,然后对其查询使用。


对每个点pi来说,如果添加pi点到凸包中导致一个左转向(逆时针方法)则添加该点到凸包, 反之如果导致一个右转向(顺时针方向)删除该点从凸包中


Graham算法例题


例如下图:下面点找到凸包



步骤:


1.把所有点放在二维坐标系中,则纵坐标最小的点一定是凸包上的点,如图中的P0。


2.把所有点的坐标平移一下,使 P0 作为原点,如下图。



3.计算各个点相对于 P0 的幅角 α ,按从小到大的顺序对各个点排序。当 α 相同时,距离 P0 比较近的排在前面。例如上图得到的结果为 P1,P2,P3,P4,P5,P6,P7,P8。我们由几何知识可以知道,结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。


(以上是准备步骤:找点,排号,以下开始求凸包)


以上,我们已经知道了凸包上的第一个点 P0 和第二个点 P1,我们把它们放在栈里面。现在从步骤3求得的那个结果里,把 P1 后面的那个点拿出来做当前点,即 P2 。接下来开始找第三个点:


4.连接P0和栈顶的那个点,得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5;如果在直线上,或者在直线的左边就执行步骤6。


5.如果在右边,则栈顶的那个元素不是凸包上的点,把栈顶元素出栈。执行步骤4。


6.当前点是凸包上的点,把它压入栈,执行步骤7。


7.检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点,返回步骤4。


最后,栈中的元素就是凸包上的点了。


以下为用Graham扫描法动态求解的过程:



下面静态求解过程








当然,这么负责不要担心,我们只是需要了解,OpenCV已经实现了凸包发现算法和API提供我们使用。


相关API


convexHull


函数作用:


  • opencv提供了convexHull()函数来查找图像中物体的凸包


函数原型:


void cv::convexHull (  
  InputArray  points,
  OutputArray     hull,
  bool    clockwise = false,
  bool    returnPoints = true 
)


函数参数:


  • points:输入的二维点集,Mat类型数据即可


  • hull:输出参数,用于输出函数调用后找到的凸包


  • clockwise:操作方向,当标识符为真时,输出凸包为顺时针方向,否则为逆时针方向。


  • returnPoints:操作标识符,默认值为true,此时返回各凸包的各个点,否则返回凸包各点的指数,当输出数组时std::vector时,此标识被忽略。


找到凸包步骤


  • 首先把图像从RGB转为灰度


  • 然后再转为二值图像


  • 在通过发现轮廓得到候选点


  • 凸包API调用


  • 绘制显示。


代码示例



#include <iostream>
#include <math.h>
#include <opencv2/opencv.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/highgui/highgui_c.h> 
using namespace std;
using namespace cv;
Mat src, src_gray, dst;
int threshold_value = 100;
int threshold_max = 255;
const char* output_win = "convex hull demo";
void Threshold_Callback(int, void*);
RNG rng(12345);
int main(int argc, char** argv) 
{
  src = imread("./test2.jpg");
  if (!src.data) {
    printf("could not load image...\n");
    return -1;
  }
  const char* input_win = "input image";
  namedWindow(input_win, CV_WINDOW_AUTOSIZE);
  namedWindow(output_win, CV_WINDOW_NORMAL);
  const char* trackbar_label = "Threshold : ";
  cvtColor(src, src_gray, CV_BGR2GRAY);
  blur(src_gray, src_gray, Size(3, 3), Point(-1, -1), BORDER_DEFAULT);
  imshow(input_win, src_gray);
  createTrackbar(trackbar_label, output_win, &threshold_value, threshold_max, Threshold_Callback);
  Threshold_Callback(0, 0);
  waitKey(0);
  return 0;
}
void Threshold_Callback(int, void*) {
  Mat bin_output;
  vector<vector<Point>> contours;
  vector<Vec4i> hierachy;
  // 设定灰度阈值
  threshold(src_gray, bin_output, threshold_value, threshold_max, THRESH_BINARY);
  findContours(bin_output, contours, hierachy, RETR_TREE, CHAIN_APPROX_SIMPLE, Point(0, 0));
  vector<vector<Point>> convexs(contours.size());
  for (size_t i = 0; i < contours.size(); i++) {
    convexHull(contours[i], convexs[i], false, true);
  }
  // 绘制凸包
  dst = Mat::zeros(src.size(), CV_8UC3);
  vector<Vec4i> empty(0);
  for (size_t k = 0; k < contours.size(); k++) {
    Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
    drawContours(dst, contours, k, color, 2, LINE_8, hierachy, 0, Point(0, 0));
    drawContours(dst, convexs, k, color, 2, LINE_8, empty, 0, Point(0, 0));
  }
  imshow(output_win, dst);
  return;
}
相关文章
|
1月前
|
计算机视觉 Python
OpenCV轮廓拟合与凸包的讲解与实战应用(附Python源码)
OpenCV轮廓拟合与凸包的讲解与实战应用(附Python源码)
79 0
|
计算机视觉
OpenCV 显示图像的凸包 Convex Hull 效果
OpenCV 显示图像的凸包 Convex Hull 效果 目的 本文将教你如何使用 OpenCV 函数 convexHull 代码 代码如下所示,可从这里 下载 #include "opencv2/highgui/highgui.hpp" #include "opencv2/imgproc/imgproc.hpp
5565 0
|
算法 计算机视觉 索引
OpenCV学习(29) 凸包(convexhull)
在opencv中,通过函数convexHulll能很容易的得到一系列点的凸包,比如由点组成的轮廓,通过convexHull函数,我们就能得到轮廓的凸包。下面的图就是一些点集的凸包。   求凸包的代码如下: int main( int /*argc*/, char** /*arg...
1229 0
|
算法 计算机视觉
【OpenCV学习】凸包的绘制
作者:gnuhpc 出处:http://www.cnblogs.com/gnuhpc/   二维凸包问题描述: 二维凸包的寻找是计算几何学的经典问题之一。 给定平面上的一些点,找出一个最小点集连成一个凸多边形,使得这若干 个点皆在此多边形内或此多边形上,这个凸多边形就是给定点的二维凸包。
1010 0
|
2天前
|
算法 计算机视觉 Python
openCV 3计算机视觉 Python语言实现 笔记 第三章 使用OpenCV 3处理图像
openCV 3计算机视觉 Python语言实现 笔记 第三章 使用OpenCV 3处理图像
|
8天前
|
存储 编解码 API
【图像文本化】Base64编解码OpenCV4中 Mat 对象
【图像文本化】Base64编解码OpenCV4中 Mat 对象
10 0
|
8天前
|
机器学习/深度学习 编解码 计算机视觉
【一秒梵高】基于OpenCV4实现图像九种风格迁移
【一秒梵高】基于OpenCV4实现图像九种风格迁移
12 0
|
9天前
|
计算机视觉
OpenCV中图像算术操作与逻辑操作
OpenCV中图像算术操作与逻辑操作
9 1
|
9天前
|
存储 计算机视觉
OpenCV3.1中读写图像与读写像素
OpenCV3.1中读写图像与读写像素
9 0
|
10天前
|
计算机视觉
OpenCV图像二值化
OpenCV图像二值化