霍夫（圆）变换(hough Transform/hough cirlce Transform)原理和实现 一、霍夫（圆）变换的广泛使用和简要历史 2.3.3OpenCV圆变换函数 HoughCircles 3.2、霍夫圆变换原理 4.1 标准霍夫线变换算法流程读取原始图像，并转换成灰度图，利用阈值分割或者边缘检测算子转换成二值化边缘图像初始化霍夫空间， 令所有Num(θ,p)=0Num(θ,p)=0对于每一个像素点(x,y)(x,y)，在参数空间中找出所有满足xcosθ+ysinθ=pxcosθ+ysinθ=p的(θ,p)(θ,p)对,然后令Num(θ,p)=Num(θ,p)+1Num(θ,p)=Num(θ,p)+1统计所有Num(θ,p)Num(θ,p)的大小，取出Num(θ,p)>τNum(θ,p)>τ的参数（ττ是所设的阈值），从而得到一条直线。将上述流程取出的直线，确定与其相关线段的起始点与终止点（有一些算法，如蝴蝶形状宽度，峰值走廊之类）static voidHoughLinesStan

分类: IT文章 • 2022-03-31 20:08:01

霍夫变换是一种特征提取方法，被广泛应用在图像处理和计算机视觉应用中。霍夫变换是用来辨别找出物件中的特征，例如：线条。他的算法流程大致如下，给定一个物件、要辨别的形状的种类，算法会在参数空间中执行投票来决定物体的形状，而这是由累加空间（accumulator space）里的局部最大值来决定。

现在广泛使用的霍夫变换是由 Richard Duda 和 Peter Hart 在公元1972年发明，并称之为广义霍夫变换，广义霍夫变换和更早前1962年的Paul Hough 的专利有关，这也是其名称的又来 。 经典的霍夫变换是侦测图片中的直线，之后，霍夫变换不仅能识别直线，也能够识别任何形状，常见的有圆形、椭圆形。霍夫变换在1962年申请为专利U.S. Patent 3,069,654，其专利名为"辨识复杂图案的方法及手段"(Method and Means for Recognizing Complex Patterns)。 任一条直线可以由斜率和截距来表示，在该专利中，利用斜率和截距来将一条直线参数化，然而这会导致*的转换空间(unbounded transform space)，因为斜率有可能是无限大。1981年，因为Dana H. Ballard 的一篇期刊论文 "Generalizing the Hough transform to detect arbitrary shapes"，让霍夫变换开始流行于电脑视觉界。

“Hough transform”即使在今天进行搜索，其引用次数也远大于其他经典计算机视觉发现运算符，例如Sobel filter或canny edge detection。

二、调用方法

2.1标准霍夫线变换和统计概率霍夫线变换

OpenCV实现了以下两种霍夫线变换:

1. 标准霍夫线变换

• 原理在上面的部分已经说明了. 它能给我们提供一组参数对  的集合来表示检测到的直线
• 在OpenCV 中通过函数 HoughLines 来实现

2. 统计概率霍夫线变换

• 这是执行起来效率更高的霍夫线变换. 它输出检测到的直线的端点 
• 在OpenCV 中它通过函数 HoughLinesP 来实现

代码

1. 这个程序是用来做什么的?
   • 加载一幅图片
   • 对图片进行 标准霍夫线变换 或是 统计概率霍夫线变换.
   • 分别在两个窗口显示原图像和绘出检测到直线的图像.
2. 我们将要说明的例程能从 这里 下载。 一个更高级的版本 (能同时演示标准霍夫线变换和统计概率霍夫线变换并带有活动条来改变变换的阈值) 能从 这里 下载。

#include "opencv2/highgui/highgui.hpp"

#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
using namespace cv;

using namespace std;
void help(){
cout << " This program demonstrates line finding with the Hough transform. "
"Usage: "
"./houghlines <image_name>, Default is pic1.jpg " << endl;}
int main(int argc, char** argv){
const char* filename = argc >= 2 ? argv[1] : "pic1.jpg";
Mat src = imread(filename, 0);
if(src.empty())
{
help();
cout << "can not open " << filename << endl;
return -1;
}
Mat dst, cdst;
Canny(src, dst, 50, 200, 3);
cvtColor(dst, cdst, CV_GRAY2BGR);

#if 0
  vector<Vec2f> lines;
  HoughLines(dst, lines, 1, CV_PI/180, 100, 0, 0 );
  for( size_t i = 0; i < lines.size(); i++ )
  {
     float rho = lines[i][0], theta = lines[i][1];
     Point pt1, pt2;
     double a = cos(theta), b = sin(theta);
     double x0 = a*rho, y0 = b*rho;
     pt1.x = cvRound(x0 + 1000*(-b));
     pt1.y = cvRound(y0 + 1000*(a));
     pt2.x = cvRound(x0 - 1000*(-b));
     pt2.y = cvRound(y0 - 1000*(a));
     line( cdst, pt1, pt2, Scalar(0,0,255), 3, CV_AA);
  }
 #else
  vector<Vec4i> lines;
  HoughLinesP(dst, lines, 1, CV_PI/180, 50, 50, 10 );
  for( size_t i = 0; i < lines.size(); i++ )
  {
    Vec4i l = lines[i];
    line( cdst, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, CV_AA);
  }
 #endif

imshow("source", src);
imshow("detected lines", cdst);
waitKey();
return 0;}

代码说明

1. 加载图片

   Mat src = imread(filename, 0);if(src.empty()){
   help();
   cout << "can not open " << filename << endl;
   return -1;}

2. 用Canny算子对图像进行边缘检测

   Canny(src, dst, 50, 200, 3);

   现在我们将要执行霍夫线变换. 我们将会说明怎样使用OpenCV的函数做到这一点:

3. 标准霍夫线变换

   1. 首先, 你要执行变换:

      vector<Vec2f> lines;
      HoughLines(dst, lines, 1, CV_PI/180, 100, 0, 0 );

      带有以下自变量:

      • dst: 边缘检测的输出图像. 它应该是个灰度图 (但事实上是个二值化图)
      • lines: 储存着检测到的直线的参数对  的容器 * rho : 参数极径  以像素值为单位的分辨率. 我们使用 1 像素.
      • theta: 参数极角  以弧度为单位的分辨率. 我们使用 1度 (即CV_PI/180)
      • threshold: 要”检测” 一条直线所需最少的的曲线交点
      • srn and stn: 参数默认为0. 查缺OpenCV参考文献来获取更多信息.

   2. 通过画出检测到的直线来显示结果.

      for( size_t i = 0; i < lines.size(); i++ ){
      float rho = lines[i][0], theta = lines[i][1];
      Point pt1, pt2;
      double a = cos(theta), b = sin(theta);
      double x0 = a*rho, y0 = b*rho;
      pt1.x = cvRound(x0 + 1000*(-b));
      pt1.y = cvRound(y0 + 1000*(a));
      pt2.x = cvRound(x0 - 1000*(-b));
      pt2.y = cvRound(y0 - 1000*(a));
      line( cdst, pt1, pt2, Scalar(0,0,255), 3, CV_AA);}

4. 统计概率霍夫线变换

   1.首先, 你要执行变换:

   1. vector<Vec4i> lines;
HoughLinesP(dst, lines, 1, CV_PI/180, 50, 50, 10 );

      带有以下自变量:

      • dst: 边缘检测的输出图像. 它应该是个灰度图 (但事实上是个二值化图) * lines: 储存着检测到的直线的参数对  的容器
      • rho : 参数极径  以像素值为单位的分辨率. 我们使用 1 像素.
      • theta: 参数极角  以弧度为单位的分辨率. 我们使用 1度 (即CV_PI/180)
      • threshold: 要”检测” 一条直线所需最少的的曲线交点 * minLinLength: 能组成一条直线的最少点的数量. 点数量不足的直线将被抛弃.
      • maxLineGap: 能被认为在一条直线上的亮点的最大距离.

   2. 通过画出检测到的直线来显示结果.

      for( size_t i = 0; i < lines.size(); i++ ){
      Vec4i l = lines[i];
      line( cdst, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, CV_AA);}

5. 显示原始图像和检测到的直线:

   imshow("source", src);imshow("detected lines", cdst);

6. 等待用户按键推出程序

   waitKey();

结果

2.2霍夫圆变换  

代码： 

#include <opencv2/imgproc.hpp>
#include <opencv2/highgui.hpp>
#include <math.h>
using namespace cv;
using namespace std;
int main(int argc, char** argv)
{
    Mat img, gray;
    if( argc != 2 || !(img=imread(argv[1], 1)).data)
        return -1;
    cvtColor(img, gray, COLOR_BGR2GRAY);
    // smooth it, otherwise a lot of false circles may be detected
    GaussianBlur( gray, gray, Size(9, 9), 2, 2 );
    vector<Vec3f> circles;
    HoughCircles(gray, circles, HOUGH_GRADIENT,2, gray.rows/4, 200, 100 );
    for( size_t i = 0; i < circles.size(); i++ )
    {
         Point center(cvRound(circles[i][0]), cvRound(circles[i][1]));
         int radius = cvRound(circles[i][2]);
         // draw the circle center
         circle( img, center, 3, Scalar(0,255,0), -1, 8, 0 );
         // draw the circle outline
         circle( img, center, radius, Scalar(0,0,255), 3, 8, 0 );
    }
    namedWindow( "circles", 1 );
    imshow( "circles", img );
    waitKey(0);
    return 0;
}

得益于一个新算法HOUGH_GRADIENT_ALT支持，比以前有很大程度的精度提试对比如下：

2.3相关函数具体调用

2.3.1标准霍夫变换HoughLines()函数

void HoughLines(InputArray image,OutputArray lines, double rho, double theta, int threshold, double srn=0,double stn=0 )

第一个参数，InputArray类型的image，输入图像，即源图像，需为8位的单通道二进制图像，可以将任意的源图载入进来后由函数修改成此格式后，再填在这里。

第二个参数，InputArray类型的lines，经过调用HoughLines函数后储存了霍夫线变换检测到线条的输出矢量。每一条线由具有两个元素的矢量水平线）。

第三个参数，double类型的rho，以像素为单位的距离精度。另一种形容方式是直线搜索时的进步尺寸的单位半径。PS:Latex中/rho就表示 。

第四个参数，double类型的theta，以弧度为单位的角度精度。另一种形容方式是直线搜索时的进步尺寸的单位角度。

第五个参数，int类型的threshold，累加平面的阈值参数，即识别某部分为图中的一条直线时它在累加平面中必须达到的值。大于阈值threshold的线段才可以被检测通过并返回到结果中。

第六个参数，double类型的srn，有默认值0。对于多尺度的霍夫变换，这是第三个参数进步尺寸rho的除数距离。粗略的累加器进步尺寸直接是第三个参数rho，而精确的累加器进步尺寸为rho/srn。

第七个参数，double类型的stn，有默认值0，对于多尺度霍夫变换，srn表示第四个参数进步尺寸的单位角度theta的除数距离。且如果srn和stn同时为0，就表示使用经典的霍夫变换。否则，这两个参数应该都为正数。

2.3.2 统计概率霍夫变换(HoughLinesP)

C++: void HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLength=0, double maxLineGap=0 )

第一个参数，InputArray类型的image，输入图像，即源图像，需为8位的单通道二进制图像，可以将任意的源图载入进来后由函数修改成此格式后，再填在这里。

第二个参数，InputArray类型的lines，经过调用HoughLinesP函数后后存储了检测到的线条的输出矢量，每一条线由具有四个元素的矢量是每个检测到的线段的结束点。

第三个参数，double类型的rho，以像素为单位的距离精度。另一种形容方式是直线搜索时的进步尺寸的单位半径。

第四个参数，double类型的theta，以弧度为单位的角度精度。另一种形容方式是直线搜索时的进步尺寸的单位角度。

第五个参数，int类型的threshold，累加平面的阈值参数，即识别某部分为图中的一条直线时它在累加平面中必须达到的值。大于阈值threshold的线段才可以被检测通过并返回到结果中。

第六个参数，double类型的minLineLength，有默认值0，表示最低线段的长度，比这个设定参数短的线段就不能被显现出来。

第七个参数，double类型的maxLineGap，有默认值0，允许将同一行点与点之间连接起来的最大的距离。

2.3.3OpenCV圆变换函数 HoughCircles

第一个参数，InputArray类型的image，输入图像，即源图像，需为8位的灰度单通道图像。
第二个参数，InputArray类型的circles，经过调用HoughCircles函数后此参数存储了检测到的圆的输出矢量，每个矢量由包含了3个元素的浮点矢量(x, y, radius)表示。
第三个参数，int类型的method，即使用的检测方法，目前OpenCV中就霍夫梯度法一种可以使用，它的标识符为CV_HOUGH_GRADIENT，在此参数处填这个标识符即可。
第四个参数，double类型的dp，用来检测圆心的累加器图像的分辨率于输入图像之比的倒数，且此参数允许创建一个比输入图像分辨率低的累加器。上述文字不好理解的话，来看例子吧。例如，如果dp= 1时，累加器和输入图像具有相同的分辨率。如果dp=2，累加器便有输入图像一半那么大的宽度和高度。
第五个参数，double类型的minDist，为霍夫变换检测到的圆的圆心之间的最小距离，即让我们的算法能明显区分的两个不同圆之间的最小距离。这个参数如果太小的话，多个相邻的圆可能被错误地检测成了一个重合的圆。反之，这个参数设置太大的话，某些圆就不能被检测出来了。
第六个参数，double类型的param1，有默认值100。它是第三个参数method设置的检测方法的对应的参数。对当前唯一的方法霍夫梯度法CV_HOUGH_GRADIENT，它表示传递给canny边缘检测算子的高阈值，而低阈值为高阈值的一半。
第七个参数，double类型的param2，也有默认值100。它是第三个参数method设置的检测方法的对应的参数。对当前唯一的方法霍夫梯度法CV_HOUGH_GRADIENT，它表示在检测阶段圆心的累加器阈值。它越小的话，就可以检测到更多根本不存在的圆，而它越大的话，能通过检测的圆就更加接近完美的圆形了。
第八个参数，int类型的minRadius,有默认值0，表示圆半径的最小值。
第九个参数，int类型的maxRadius,也有默认值0，表示圆半径的最大值。

三、理论

在自动化分析数位图片的问题里，其中一个常有的子问题是侦测某些简单的直线、圆形、椭圆形。在多数情况下，边缘侦测器(edge detector)会先用来做图片前处理，将原本的图片变成只含有边缘的图片。 因为图片的不完美或是边缘侦测的不完美，导致有些点(point)或像素(pixel)缺漏，或是有噪声使得边缘侦测器所得的边界偏离了实际的边界。所以无法直观的将检测出的边缘分成直线、圆形、椭圆形的集合， 而霍夫变换解决上述问题，借由霍夫变换算法中的投票步骤，在复杂的参数空间中找到图形的参数，电脑可以由参数得知该边缘(edge)是哪种形状。

3.1 霍夫线变换原理。

3.1.1 在平面直角坐标系(x-y)中，一条直线可以用方程式

表示，而可以视为参数空间中的一点。当直线垂直于轴时，斜率为无限大， 若用电脑数值计算时会很不方便。

3.1.2 Duda 和 Hart 提出使用Hesse normal form来表示直线的参数，但是这个本身的原理比较繁琐，我们可以通过图像和极坐标的方法来进行简化。

一方面，x=0的时候y的值，这个点是可以确定的；r/sin(Θ)      f(0) =  r/sin(Θ) 

另一方面，这条直线的斜率（红色）是tan(PI-Θ) = tan(PI/2 + Θ),根据诱导公式： tan（π/2+α）=－cotα ,也就是斜率为：－cot(Θ)

根据2.1.1中得到的定义，这条直线可以表示为：

进行化简便可得到（简单变换）:

这里还有另一种方法，绕过定义直接使用图像作业，也应该掌握。

3.1.3 对于一个给定点我们在极坐标对极径极角平面绘出所有通过它的直线, 将得到一条正弦曲线. 

例如, 对于给定点(8,6)我们可以绘出下图 (在平面，):

 

有例如，对于给定点(3,4)情况时作图（)：会发现曲线的形状类似一条正弦曲线，通常

这个变化非常有价值，是整个Hough变化的核心！

具体的，通过将霍夫参数空间量化为有限间隔或累加器单元来实现变换。随着算法的运行，每个算法都把，所有点都如此进行计算后，可以设置一个阈值，投票大于这个阈值的可以认为是找到的直线。

那么给定一个点，通过该点的所有直线的参数的集合，会在平面上形成一个三角函数，可由下方程式证明

因此，给定很多点，判断这些点是否共线(concurrent lines)的问题，经由霍夫变换之后，变成判断一堆曲线(每一个点在平面上代表一条曲线)是否 在平面上相交于同一点的问题(concurrent curves)。继续上面那张抽象的图，如果两个不同点进行上述操作后得到的曲线在平面相交, 这就意味着它们通过同一条直线. 例如,接上面的例子我们继续绘图, 得到下图:

这三条曲线在平面相交于点 (0.925, 9.6), 坐标表示的是参数对  或者是说点, 点和点组成的平面内的的直线。

3.1.4范例：输入的图片中有两条粗直线，经过霍夫变换后的结果得到accumaltor矩阵，右图就是把accumaltor矩阵画出来，越亮值越大，越黑值越小。在右图中，有两个很明显的亮点， 这两个亮点分别代表两条不同参数的直线，与输入的图片(左图)吻合。然后读取矩阵的两个最大值就可以得出这两条线距画面中心距离以及角度。