【从零学习OpenCV 4】霍夫变换原理及直线检测
| 经过几个月的努力，小白终于完成了市面上第一本OpenCV 4入门书籍《OpenCV 4开发详解》。为了更让小伙伴更早的了解最新版的OpenCV 4，小白与出版社沟通，提前在公众号上连载部分内容，请持续关注小白。 |
霍夫变换（Hough Transform）是图像处理中检测是否存在直线的重要算法，该算法是由Paul Hough在1962年首次提出，最开始只能检测图像中的直线，但是霍夫变换经过不断的扩展和完善已经可以检测多种规则形状，例如圆形、椭圆等。霍夫变换通过将图像中的像素在一个空间坐标系中变换到另一个坐标空间坐标系中，使得在原空间中具有形同特性的曲线或者直线映射到另一个空间中形成峰值，从而把检测任意形状的问题转化为统计峰值的问题。
霍夫变换通过构建检测形状的数学解析式将图像中像素点映射到参数空间中，例如我们想检测两个像素点所在的直线，需要构建直线的数学解析式。在图像空间x-y直角坐标系中，对于直线可以用式(7.1)所示的解析式来表示。
其中是直线的斜率，是直线的截距。假设图像中存在一像素点，所有经过这个像素点直线可以用式(7.2)表示。
在图像空间x-y直角坐标系中，由于变量是x和y，因此式(7.2)表示的是经过点像素点的直线，但是经过一点的直线有无数条，因此式(7.2)中的 和 具有无数个可以选择的值，如果将和看作是变量， 和 表示定值，那么式(7.2)可以表示在k-b空间的一条直线，映射过程示意图如图7-1所示。用式(7.1)的形式表示映射的结果如式(7.3)所示，即霍夫变换将x-y直角坐标系中经过一点的所有直线映射成了k-b空间中的一条直线，直线上的每个点都对应着x-y直角坐标系中的一条直线。
当图像中存在另一个像素点时，在图像空间x-y直角坐标系中所有经过像素点的直线也会在参数空间中映射出一条直线。由于参数空间中每一个点都表示图像空间x-y直角坐标系中直线的斜率和截距，因此如果有一条直线经过像素点和像素点时，这条直线所映射在参数空间中的坐标点应该既在像素点映射的直线上又在像素点映射的直线上。在平面内一个点同时在两条直线上，那么这个点一定是两条直线的交点，因此这条同时经过和的直线所对应的斜率和截距就是参数空间中两条直线的交点。
图7-1 霍夫变换空间映射
根据前面的分析可以得到霍夫变换中存在两个重要的结论：（1）图像空间中的每条直线在参数空间中都对应着单独一个点来表示；（2）图像空间中的直线上任何像素点在参数空间对应的直线相交于同一个点。图7-2给出了第二条结论的示意图。因此通过霍夫变换寻找图像中的直线就是寻找参数空间中大量直线相交的一点。
图7-2 霍夫变换中同一直线上不同点在参数空间中对应的直线交于一点示意图
利用式(7.1)形式进行霍夫变换可以寻找到图像中绝大多数直线，但是当图像中存在垂直直线时，即所有的像素点的x坐标相同时，直线上的像素点利用上述霍夫变换方法得到的参数空间中多条直线互相平行，无法相交于一点。例如在图像上存在3个像素点 、和 ，利用式(7.3)可以求得参数空间中3条直线解析式如式中所示，这些直线具有相同的斜率，因此无法交于一点，具体形式如图7-3所示。
图7-3 垂直直线霍夫变换映射示意图
为了解决垂直直线在参数空间没有交点的问题，一般采用极坐标方式表示图像空间x-y直角坐标系中的直线，具体形式如式(7.5)所示。
其中 为坐标原点到直线的距离， 为坐标原点到直线的垂线与x轴的夹角，这两个参数的含义如图7-4所示。
图7-4 图像空间中极坐标表示直线示意图
根据霍夫变换原理，利用极坐标形式表示直线时，在图像空间中经过某一点的所有直线映射到参数空间中是一个正弦曲线。图像空间中直线上的两个点在参数空间中映射的两条正弦曲线相交于一点，图7-5中给出了用极坐标形式表示直线的霍夫变换的示意图。
图7-5 极坐标表示直线的霍夫变换示意图
通过上述的变换过程，将图像中的直线检测转换成了在参数空间中寻找某个点 通过的正线曲线最多的问题。由于在参数空间内的曲线是连续的，而在实际情况中图像的像素是离散的，因此我们需要将参数空间的 轴和 轴进行离散化，用离散后的方格表示每一条正弦曲线。首先寻找符合条件的网格，之后寻找该网格对应的图像空间中所有的点，这些点共同组成了原图像中的直线。
总结上面所有的原理和步骤，霍夫变换算法检测图像中的直线主要分为4个步骤：
Step1：将参数空间的坐标轴离散化，例如 ， 。 Step2：将图像中每个非0像素通过映射关系求取在参数空间通过的方格。 Step3：统计参数空间内每个方格出现的次数，选取次数大于某一阈值的方格作为表示直线的方格。 Step4：将参数空间中表示直线的方格的参数作为图像中直线的参数。
霍夫检测具有抗干扰能力强，对图像中直线的残缺部分、噪声以及其它共存的非直线结构不敏感，能容忍特征边界描述中的间隙，并且相对不受图像噪声影响等优点，但是霍夫变换的时间复杂度和空间复杂度都很高，并且检测精度受参数离散间隔制约。离散间隔较大时会降低检测精度，离散间隔较小时虽然能提高精度，但是会增加计算负担，导致计算时间边长。
OpenCV 4提供了两种用于检测图像中直线的相关函数，分别是标准霍夫变换和多尺度霍夫变换函数HoughLins()和渐进概率式霍夫变换函数HoughLinesP()。首先将介绍标准霍夫变换函数HoughLins()，该函数的函数原型在代码清单7-1中给出。
代码清单7-1 HoughLines()函数原型void cv::HoughLines(InputArray image, OutputArray lines, double rho, double theta, int threshold, double srn = 0, double stn = 0, double min_theta = 0, double max_theta = CV_PI )image：待检测直线的原图像，必须是CV_8U的单通道二值图像。 lines：霍夫变换检测到的直线输出量，每一条直线都由两个参数表示，分别表示直线距离坐标原点的距离 和坐标原点到直线的垂线与x轴的夹角 。 rho：以像素为单位的距离分辨率，即距离 离散化时的单位长度。 theta：以弧度为单位的角度分辨率，即夹角 离散化时的单位角度。 threshold：累加器的阈值，即参数空间中离散化后每个方格被通过的累计次数大于该阈值时将被识别为直线，否则不被识别为直线。 srn：对于多尺度霍夫变换算法中，该参数表示距离分辨率的除数，粗略的累加器距离分辨率是第三个参数rho，精确的累加器分辨率是rho/srn。这个参数必须是非负数，默认参数为0。 stn：对于多尺度霍夫变换算法中，该参数表示角度分辨率的除数，粗略的累加器距离分辨率是第四个参数rho，精确的累加器分辨率是rho/stn。这个参数必须是非负数，默认参数为0。当这个参数与第六个参数srn同时为0时，此函数表示的是标准霍夫变换。 min_theta：检测直线的最小角度，默认参数为0。 max_theta：检测直线的最大角度，默认参数为CV_PI，是OpenCV 4中的默认数值具体为3.1415926535897932384626433832795。
该函数用于寻找图像中的直线，并以极坐标的形式将图像中直线的极坐标参数输出。该函数的第一个参数为输入图像，必须是CV_8U的单通道二值图像，如果需要检测彩色图像或者灰度图像中是否存在直线，可以通过Canny()函数计算图像的边缘，并将边缘检测结果二值化后的图像作为输入图像赋值给该参数。函数的第二个参数是霍夫变换检测到的图像中直线极坐标描述的系数，是一个N×2的vector矩阵，每一行中的第一个元素是直线距离坐标原点的距离，第二个元素是该直线过坐标原点的垂线与x轴的夹角，这里需要注意的是图像中的坐标原点在图像的左上角。函数第三个和第四个参数是霍夫变换中对参数空间坐标轴进行离散化后单位长度，这两个参数的大小直接影响到检测图像中直线的精度，数值越小精度越高。第三个参数表示参数空间 轴的单位长度，单位为像素，该参数常设置为1；第四个参数表示参数空间 轴的单位长度，单位为弧度，该函数常设置为CV_PI/180。函数第五个参数是累加器的阈值，表示参数空间中某个方格是否被认定为直线的判定标准，这个数值越大，对应在原图像中构成直线的像素点越多，反之则越少。第六个和第七个参数起到选择标准霍夫变换和多尺度霍夫变换的作用，当两个参数全为0时，该函数使用标准霍夫变换算法，否则该函数使用多尺度霍夫变换算法，当函数使用多尺度霍夫变换算法时，这两个函数分别表示第三个参数单位距离长度的除数和第四个参数角度单位角度的除数。函数最后两个参数是检测直线的最小角度和最大角度，两个参数必须大于等于0小于等于CV_PI（3.1415926535897932384626433832795），并且最小角度的数值要小于最大角度的数值。
该函数只能输出直线的极坐标表示形式的参数，如果想在图像中绘制该直线需要进一步得到直线两端的坐标，通过line()函数在原图像中绘制直线，由于该函数只能判断图像中是否有直线，而不能判断直线的起始位置，因此使用line()函数绘制直线时常绘制尽可能长的直线。在代码清单7-2中给出了利用HoughLines()函数检测图像中直线的示例程序，程序中根据直线的参数计算出直线与经过坐标原点的垂线的交点的坐标，之后利用直线的线性关系计算出直线两端尽可能远的端点坐标，最后利用line()函数在原图像中绘制直线。程序首先利用Canny()函数对灰度图像进行边缘提取，然后对边缘经过进行二值化处理，之后检测图像中的直线，为了验证第五个参数累加器阈值对检测直线长短的影响，分别设置较小和较大的两个累加器，程序运行结果在图7-6、图7-7给出，通过结果可以看出累加器较小时较短的直线也可以被检测出来，累加器较大时只能检测出图像中较长的直线。
#include <opencv2/opencv.hpp>#include <iostream>
using namespace cv;using namespace std;
void drawLine(Mat &img, //要标记直线的图像 vector<Vec2f> lines, //检测的直线数据 double rows, //原图像的行数（高） double cols, //原图像的列数（宽） Scalar scalar, //绘制直线的颜色 int n //绘制直线的线宽){ Point pt1, pt2; for (size_t i = 0; i < lines.size(); i++) { float rho = lines[i][0]; //直线距离坐标原点的距离 float theta = lines[i][1]; //直线过坐标原点垂线与x轴夹角 double a = cos(theta); //夹角的余弦值 double b = sin(theta); //夹角的正弦值 double x0 = a*rho, y0 = b*rho; //直线与过坐标原点的垂线的交点 double length = max(rows, cols); //图像高宽的最大值 //计算直线上的一点 pt1.x = cvRound(x0 + length * (-b)); pt1.y = cvRound(y0 + length * (a)); //计算直线上另一点 pt2.x = cvRound(x0 - length * (-b)); pt2.y = cvRound(y0 - length * (a)); //两点绘制一条直线 line(img, pt1, pt2, scalar, n); }}
int main(){ Mat img = imread("HoughLines.jpg", IMREAD_GRAYSCALE); if (img.empty()) { cout << "请确认图像文件名称是否正确" << endl; return -1; } Mat edge;
//检测边缘图像，并二值化 Canny(img, edge, 80, 180, 3, false); threshold(edge, edge, 170, 255, THRESH_BINARY);
//用不同的累加器进行检测直线 vector<Vec2f> lines1, lines2; HoughLines(edge, lines1, 1, CV_PI / 180, 50, 0, 0); HoughLines(edge, lines2, 1, CV_PI / 180, 150, 0, 0);
//在原图像中绘制直线 Mat img1, img2; img.copyTo(img1); img.copyTo(img2); drawLine(img1, lines1, edge.rows, edge.cols, Scalar(255), 2); drawLine(img2, lines2, edge.rows, edge.cols, Scalar(255), 2);
//显示图像 imshow("edge", edge); imshow("img", img); imshow("img1", img1); imshow("img2", img2); waitKey(0); return 0;}图7-6 myHoughLines.cpp程序中原图像和边缘检测结果
图7-7 myHoughLines.cpp程序中累加器较小阈值和较大阈值的直线检测结果
使用标准霍夫变换和多尺度霍夫变换函数HoughLins()提取直线时无法准确知道图像中直线或者线段的长度，只能得到图像中是否存在符合要求的直线以及直线的极坐标解析式。如果需要准确的定位图像中线段的位置，HoughLins()函数便无法满足需求，但是OpenCV 4提供的渐进概率式霍夫变换函数HoughLinesP()可以得到图像中满足条件的直线或者线段两个端点的坐标，进而确定直线或者线段的位置，该函数的函数原型在代码清单7-3中给出。
代码清单7-3 HoughLinesP()函数原型void cv::HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLength = 0, double maxLineGap = 0 )image：待检测直线的原图像，必须是CV_8C的单通道二值图像。 lines：霍夫变换检测到的直线输出量，每一条直线都由4个参数进行描述，分别是直线两个端点的坐标 rho：以像素为单位的距离分辨率，即距离 离散化时的单位长度。 theta：以弧度为单位的角度分辨率，即夹角 离散化时的单位角度。 threshold：累加器的阈值，即参数空间中离散化后每个方格被通过的累计次数大于阈值时则被识别为直线，否则不被识别为直线。 minLineLength：直线的最小长度，当检测直线的长度小于该数值时将会被剔除。 maxLineGap：允许将同一行两个点连接起来的最大距离。
该函数用于寻找图像中满足条件的直线或者线段两个端点的坐标。该函数的第一个参数为输入图像，必须是CV_8U的单通道二值图像，如果需要检测彩色图像或者灰度图像中是否存在直线，可以通过Canny()函数计算图像的边缘，并将边缘检测结果二值化后的图像作为输入图像赋值给该参数。函数的第二个参数是图像中直线或者线段两个端点的坐标，是一个N×4的vector矩阵。Vec4i中前两个元素分别是直线或者线段一个端点的x坐标和y坐标，后两个元素分别是直线或者线段另一个端点的x坐标和y坐标。函数第三个和第四个参数含义与HoughLines()函数的参数含义相同，都是霍夫变换中对参数空间坐标轴进行离散化后的单位长度，这两个参数的大小直接影响到检测图像中直线的精度，数值越小精度越高。第三个参数表示参数空间 轴的单位长度，单位为像素，该参数常设置为1；第四个参数表示参数空间 轴的单位角度，单位为弧度，该函数常设置为CV_PI/180。函数第五个参数是累加器的阈值，表示参数空间中某个方格是否被认定为直线的判定标准，这个数值越大，对应在原图像中的直线越长，反之则越短。第六个参数是检测直线或者线段的长度，如果图像中直线的长度小于这个阈值，即使是直线也不会作为最终结果输出。函数最后一个参数是邻近两个点连接的最大距离，这个参数主要能够控制倾斜直线的检测长度，当提取较长的倾斜直线时该参数应该具有较大取值。
该函数的最大特点是能够直接给出图像中直线或者线段两个端点的像素坐标，因此可较精确的定位到图像中直线的位置。为了了解该函数的使用方式，在代码清单7-4中给出了利用HoughLinesP()函数提取图像直线的示例程序，程序中使用的原图像与代码清单7-2中相同，程序的输出结果在图7-8给出，程序结果说明HoughLinesP()函数确实可以实现图像中直线或者线段的定位任务，并且结果也说明函数最后一个参数较大时倾斜直线检测的完整度较高。
#include <opencv2/opencv.hpp>#include <iostream>
using namespace cv;using namespace std;
int main(){ Mat img = imread("HoughLines.jpg", IMREAD_GRAYSCALE); if (img.empty()) { cout << "请确认图像文件名称是否正确" << endl; return -1; } Mat edge;
//检测边缘图像，并二值化 Canny(img, edge, 80, 180, 3, false); threshold(edge, edge, 170, 255, THRESH_BINARY);
//利用渐进概率式霍夫变换提取直线 vector<Vec4i> linesP1, linesP2; HoughLinesP(edge, linesP1, 1, CV_PI / 180, 150, 30, 10); //两个点连接最大距离10 HoughLinesP(edge, linesP2, 1, CV_PI / 180, 150, 30, 30); //两个点连接最大距离30
//绘制两个点连接最大距离10直线检测结果 Mat img1; img.copyTo(img1); for (size_t i = 0; i < linesP1.size(); i++) { line(img1, Point(linesP1[i][0], linesP1[i][1]), Point(linesP1[i][2], linesP1[i][3]), Scalar(255), 3); }
//绘制两个点连接最大距离30直线检测结果 Mat img2; img.copyTo(img2); for (size_t i = 0; i < linesP2.size(); i++) { line(img2, Point(linesP2[i][0], linesP2[i][1]), Point(linesP2[i][2], linesP2[i][3]), Scalar(255), 3); }
//显示图像 imshow("img1", img1); imshow("img2", img2); waitKey(0); return 0;}图7-8 myHoughLinesP.cpp程序直线检测结果
前面两个函数都是检测图像中是否存在直线，但是在实际工程或者任务需求中我们可能得到的是图像中一些点的坐标而不是一副完整的图像，因此OpenCV 4中提供了能够在含有坐标的众多点中寻找是否存在直线的HoughLinesPointSet()函数，该函数的函数原型在代码清单7-5中给出。
代码清单7-5 HoughLinesPointSet()函数原型void cv::HoughLinesPointSet(InputArray _point, OutputArray _lines, int lines_max, int threshold, double min_rho, double max_rho, double rho_step, double min_theta, double max_theta, double theta_step )_point：输入点的集合，必须是平面内的2D坐标，数据类型必须是CV_32FC2或CV_32SC2。 _lines：在输入点集合中可能存在的直线，每一条直线都具有三个参数，分别是权重、直线距离坐标原点的距离 和坐标原点到直线的垂线与x轴的夹角 。 lines_max：检测直线的最大数目。 threshold：累加器的阈值，即参数空间中离散化后每个方格被通过的累计次数大于阈值时则被识别为直线，否则不被识别为直线。 min_rho：检测直线长度的最小距离，以像素为单位。 max_rho：检测直线长度的最大距离，以像素为单位。 rho_step：：以像素为单位的距离分辨率，即距离 离散化时的单位长度。 min_theta：检测直线的最小角度值，以弧度为单位。 max_theta：检测直线的最大角度值，以弧度为单位。 theta_step：以弧度为单位的角度分辨率，即夹角 离散化时的单位角度。
该函数用于在含有坐标的2D点的集合中寻找直线，函数检测直线使用的方法是标准霍夫变换法。函数第一个参数是2D点集合中每个点的坐标，由于坐标必须是CV_32F或者CV_32S类型，因此可以将点集定义成vector< Point2f>或者vector< Point2f>类型。函数的第二个参数是检测到的输入点集合中可能存在的直线，是一个1×N的矩阵，数据类型为CV_64FC3，其中第1个数据表示该直线的权重，权重越大表示是直线的可靠性越高，第2个数据和第3个数据分别表示直线距离坐标原点的距离 和坐标原点到直线的垂线与x轴的夹角 ，矩阵中数据的顺序是按照权重由大到小依次存放。函数第三个参数是检测直线的数目，如果数目过大，检测到的直线可能存在权重较小的情况。函数第四个参数是累加器的阈值，表示参数空间中某个方格是否被认定为直线的判定标准，这个数值越大，表示检测的直线需要通过的点的数目越多。函数第五个、第六个参数是检测直线长度的取值范围，单位为像素。函数第七个参数是霍夫变换算法中离散化时距离分辨率的大小，单位为像素。函数第八个、第九个参数是检测直线经过坐标原点的垂线与x轴夹角的范围，单位为弧度。函数第七个参数是霍夫变换算法中离散化时角度分辨率的大小，单位为弧度。
为了了解该函数的使用方法，在代码清单7-6中给出了利用该函数检测2D点集合中直线的示例程序。程序中首先生成2D点集，之后利用HoughLinesPointSet()函数检测其中可能存在的直线，并将检测的直线权重和距离坐标原点的距离 和坐标原点到直线的垂线与x轴的夹角 输出，程序的输出结果在图7-9给出。
#include <opencv2/opencv.hpp>#include <iostream>#include <vector>
using namespace cv;using namespace std;
int main(){ system("color F0"); //更改输出界面颜色 Mat lines; //存放检测直线结果的矩阵 vector<Vec3d> line3d; //换一种结果存放形式 vector<Point2f> point; //待检测是否存在直线的所有点 const static float Points[20][2] = { { 0.0f, 369.0f },{ 10.0f, 364.0f },{ 20.0f, 358.0f },{ 30.0f, 352.0f }, { 40.0f, 346.0f },{ 50.0f, 341.0f },{ 60.0f, 335.0f },{ 70.0f, 329.0f }, { 80.0f, 323.0f },{ 90.0f, 318.0f },{ 100.0f, 312.0f },{ 110.0f, 306.0f }, { 120.0f, 300.0f },{ 130.0f, 295.0f },{ 140.0f, 289.0f },{ 150.0f, 284.0f }, { 160.0f, 277.0f },{ 170.0f, 271.0f },{ 180.0f, 266.0f },{ 190.0f, 260.0f } }; //将所有点存放在vector中，用于输入函数中 for (int i = 0; i < 20; i++) { point.push_back(Point2f(Points[i][0], Points[i][1])); } //参数设置 double rhoMin = 0.0f; //最小长度 double rhoMax = 360.0f; //最大长度 double rhoStep = 1; //离散化单位距离长度 double thetaMin = 0.0f; //最小角度 double thetaMax = CV_PI / 2.0f; //最大角度 double thetaStep = CV_PI / 180.0f; ////离散化单位角度弧度 HoughLinesPointSet(point, lines, 20, 1, rhoMin, rhoMax, rhoStep, thetaMin, thetaMax, thetaStep); lines.copyTo(line3d);
//输出结果 for (int i = 0; i < line3d.size(); i++) { cout << "votes:" << (int)line3d.at(i).val[0] << ", " << "rho:" << line3d.at(i).val[1] << ", " << "theta:" << line3d.at(i).val[2] << endl; } return 0;}图7-9 myHoughLinesPointSet.cpp程序运行结果