书名：OpenCV计算机视觉编程攻略（第3版）
作者：[加]罗伯特·拉戈尼尔
译者：相银初
出版社：人民邮电出版社
出版时间：2018-05
ISBN：9787115480934

一、实现原理

1、累加器

• 霍夫变换的目的是在二值图像中找出全部直线，并且这些直线必须穿过足够多的像素点。
  它的处理方法是，检查输入的二值分布图中每个独立的像素点，识别出穿过该像素点的所有可能直线。
  如果同一条直线穿过很多像素点，就说明这条直线明显到足以被认定。

• 为了统计某条直线被标识的次数，霍夫变换使用了一个二维累加器。
  累加器的大小依据（ρ, θ）的步长确定，其中（ρ, θ）参数用来表示一条直线。
  为了说明霍夫变换的功能，我们建立一个180×200的矩阵（对应θ的步长为π/180, ρ的步长为1）：

        // 创建霍夫累加器
        // 这里的图像类型为uchar；实际使用时应该用int
        cv::Mat acc(200,180, CV_8U, cv::Scalar(0));

• 累加器是不同于（ρ, θ）值的映射表。
  因此，矩阵的每个入口都对应一条特定的直线。
  现在假定某个像素点的坐标为（50,30），这样就能通过循环遍历所有可能的θ值（步长π/180），并计算对应的（四舍五入）ρ值，标识出穿过这个像素点的全部直线：

        // 选取一个像素点
        int x=50, y=30;
        // 循环遍历所有角度
        for (int i=0; i<180; i++) {
          double theta= i＊PI/180.;
          // 找到对应的rho值
          double rho= x＊std::cos(theta)+y＊std::sin(theta);
          // j对应-100～100 的rho
          int j= static_cast<int>(rho+100.5);
          std::cout << i << ", " << j << std::endl;
          // 增值累加器
          acc.at<uchar>(j, i)++;
        }

• 每次计算得到（ρ, θ）对后，其对应的累加器入口的数值就会增加，表示对应的直线穿过了图像中的某个像素点（或者说每个像素点为一批候选直线投票）。
  如果把累加器作为图像显示（翻转过来，并乘以100，以便数字1能显示），结果如下所示。

  

• 上面的曲线表示穿过这个点的所有直线的集合。现在用像素点（30, 10）重复上述过程，得到的累加器如下所示。

  

• 可以看到，这两条曲线在一个位置相交，这个位置表示对应的直线通过了这两个像素点。累加器的对应入口收到了两次投票，表明有两个像素点在这条直线上。

• 如果对二值分布图中的所有像素点重复上述过程，那么同一条直线上的像素点会使累加器的同一个入口增长很多次。
  最后，为了检测图像中的直线（即像素点对齐的位置），只需要标识出累加器中的局部限值，该累加器用于接收大量投票数。
  cv::HoughLines函数的最后一个参数表示最低投票数，只有不低于这个数的直线才会被检测到。这表明最低投票数越小，检测到的直线数量就越多。

• 如果把例子中的数值降为50，检测到的直线就如下图所示。

  

2、概率霍夫变换

• 概率霍夫变换对基本算法做了一些修正。
  首先，概率霍夫变换在二值分布图上随机选择像素点，而不是系统性地逐行扫描图像。一旦累加器的某个入口达到了预设的最小值，就沿着对应的直线扫描图像，并移除在这条直线上的所有像素点（包括还没投票的像素点）。
  这个扫描过程还检测可以接受的线段长度。
  为此，算法定义了两个额外的参数：一个是允许的线段最小长度，另一个是组成连续线段时允许的最大像素间距。
  这个额外的步骤增加了算法的复杂度，但也得到了一定的补偿——由于在扫描直线的过程中已经清除了部分像素点，因此减少了投票过程中用到的像素点。