OpenCV——霍夫变换

一、霍夫变换原理

霍夫变换（Hough TRansform）是从图像中识别几何图形的基本方法，由Paul Hough于1962年提出。最初霍夫变换只能用来检测直线，经过不断的改进，霍夫变换能识别任意形状（多为圆和椭圆等几何图形）。

在笛卡尔坐标系下，一条直线可以用斜率k和截距q表示，其公式如下：

y = kx + q

把k和q放到一个坐标空间表示时这个坐标空间就称为霍夫空间，如下：

关于霍夫空间有一下两条重要定理：

1. 笛卡尔空间中的一条直线，对应于霍夫空间的一个点，反过来也成立
2. 如果笛卡尔坐标中有若干个点共线，则这些点在霍夫空间中对应的直线相交于一点

这样，在笛卡尔空间寻找直线的问题，就可以转换为在霍夫空间寻找相交点的问题。但是，在将杂乱的点连接成直线时，会有许多种连接方法。此时应该如何选择呢？霍夫变换的基本方式是选择由尽可能多的直线汇成的点，(a)所示，笛卡儿坐标系中有4、B、C、D、E共5个点，如果按照每两点构成一条直线来画线，则会有很多线。现在将这5个点转换成霍夫空间的直线，如图 (b)所示。可以看出，最多直线形成的交点是 M点和N点，相交直线有3条，其余交点都只有2条直线相交，因此，最后检测到的直线就是 M点和N点在笛卡儿坐标中对应的直线，即 ACE和 BCD，如图©所示。

上述方法简洁明了，但是有一个缺陷:当直线平行于y轴时斜率为无穷大，此时霍夫变换就遇到问题了。解决这个问题的方法是将笛卡儿坐标转换为极坐标。

在极坐标系中，任何直线可用p和0两个参数表示，公式如下:

p= xcos0 + ysin0

其中，p为原点到直线的垂直距离，0为直线垂线与x轴的夹角，如图所示。

这样，极坐标中的点也能对应于霍夫空间的线，只不过这时霍夫空间的参数不再是斜率k和截距 q，而是p和 0。极坐标中一条直线上的点，在霍夫空间中仍然交于一点，如图 10-5所示。

二、霍夫线检测

基于上述原理，霍夫线检测算法需要创建一个二维数组,称为累加器,如图 所示。检测结果的准确度取决于累加器的大小;如果希望角度精确到1°，则数组需要 180 列;p 的最大值为图片的对角线距离，如果希望 p精确度达到像素级别，则行数需要与对角线像素数一样。累加器统计直线交点次数的过程称为“投票”。投票开始后，对于图像中直线上的每像素(x，y)，将其代入极坐标公式中，然后分别计算日各个值(如精度为 1°,则0为 0°,1°,2°,3°,…,180°)时的p值，如果累加器中有这个值，则给这个值投一票，对所有像素投完票后，找到累加器中的最大值对应的p和0，这两个参数对应的直线就是检测结果。

OpenCV 中的霍夫变换函数不止一个，下面介绍标准霍夫变换函数(SHT)和概率霍夫变换函数(PPHT)。

2.1、标准霍夫变换

//用标准霍夫变换在二值图像中寻找直线
void Imgproc.HoughLines(Mat image, Mat lines, double rho, double theta, int threshold)

• image：8位单通道二值图像
• lines：检测到的直线（二维数组），每条直线由p和0表示
• rho：累加器中距离的精度，单位为像素
• theta：累加器中角度的精度，单位为弧度
• threshold：累加器中的阈值参数，只有获得足够多投票的直线才出现在结果集中

public class HoughLines {
    static {
        OpenCV.loadLocally(); // 自动下载并加载本地库
    }

    public static void main(String[] args) {
        //读取图像并显示
        Mat src = Imgcodecs.imread("/Users/acton_zhang/J2EE/MavenWorkSpace/opencv_demo/src/main/java/demo2/board.jpg");
        HighGui.imshow("src", src);
        HighGui.waitKey(0);
        //Canny边缘检测并将结果存储为BGR图像
        Mat canny = new Mat();
        Mat dst = new Mat();
        Imgproc.Canny(src, canny, 50, 200, 3, false);
        Imgproc.cvtColor(canny, dst, Imgproc.COLOR_GRAY2BGR);

        //进行霍夫线检测，结果在lines中
        Mat lines = new Mat();
        Imgproc.HoughLines(canny, lines, 1, Math.PI / 180, 150);
        //将检测结果用红线画出
        for (int n = 0; n < lines.rows(); n++) {
            double rho = lines.get(n, 0)[0];//极坐标中的p
            double theta = lines.get(n, 0)[1];//极坐标中的θ
            double cos = Math.cos(theta);
            double sin = Math.sin(theta);
            double x0 = cos * rho;
            double y0 = sin * rho;
            double len = 800;//所画直线长度
            Point pt1 = new Point(Math.round(x0 + len * (-sin)), Math.round(y0 + len * (cos)));
            Point pt2 = new Point(Math.round(x0 - len * (-sin)), Math.round(y0 - len * (cos)));
            Imgproc.line(dst, pt1, pt2, new Scalar(0, 0, 255), 3);
        }
        //显示
        HighGui.imshow("Detected Lines", dst);
        HighGui.waitKey(0);
        System.exit(0);
    }
}

原图：

霍夫线检测结果：

程序中有一个变量len 是指画线的长度,因为标准霍夫变换中输出的是直线的p和0，而根据这两个参数得到的是直线(没有起始点和终止点)而不是线段，所以需要指定线的长度。由于原图像的宽和高都低于 800 像素，所以将长度设为800。如果检测图像的分辨率较高，则需要调整直线的长度。

上述程序中由于用的图像相对简单,所以结果也比较完美,但是如果更换一下输入图像,则结果可能会出人意料。接下来把输入图像换成稍微复杂点的图像:有黑白棋子的棋盘。这样的结果似乎很不理想，主要问题有两个。一是棋盘上有的地方明明只有一条线，但检测结果却变成了一组线，而且角度相差很小。另一个问题是有几条斜线是原图像中没有的。如果仔细检査一下代码，则可以发现问题的根源所在。

第1 个问题出在 HoughLines(函数的第 4 个参数 theta 上。程序中将其设为 Math.P/180，换算成角度就是 1°。由于霍夫线检测是根据阈值判断是否是直线的，水平方向的棋盘线自然毫无问题地被判断成直线，但在测试稍许倾斜的直线时，也能符合阈值要求，因而也被判断为直线。

第2个问题和霍夫线检测的原理有关。霍夫线检测实际上是统计霍夫空间中交点的数量而不管相关像素是否连续，因而即使是肉眼看上去相隔很远的像素，只要交点数量超过阈值仍然会被判断为直线。观察原图像可以看出，斜线出现处都是棋子比较密集的地方，这些斜线无一例外地都经过多枚棋子的边缘像素。这些像素虽然并不连续，但在投票时无疑会被统计在内，最后因为超过阈值而被检测为直线。解决这个问题的方法是把阈值提高，这样不连续的像素就不会构成直线了。

public class HoughLines2 {
    static {
        OpenCV.loadLocally(); // 自动下载并加载本地库
    }

    public static void main(String[] args) {
        //读取图像并显示
        Mat src = Imgcodecs.imread("/Users/acton_zhang/J2EE/MavenWorkSpace/opencv_demo/src/main/java/demo2/chess.jpg");
        HighGui.imshow("src", src);
        HighGui.waitKey(0);
        //Canny边缘检测并将结果存储为BGR图像
        Mat canny = new Mat();
        Mat dst = new Mat();
        Imgproc.Canny(src, canny, 50, 200, 3, false);
        Imgproc.cvtColor(canny, dst, Imgproc.COLOR_GRAY2BGR);

        //进行霍夫线检测，结果在lines中
        Mat lines = new Mat();
        Imgproc.HoughLines(canny, lines, 1, Math.PI / 30, 300);
        //将检测结果用红线画出
        for (int n = 0; n < lines.rows(); n++) {
            double rho = lines.get(n, 0)[0];//极坐标中的p
            double theta = lines.get(n, 0)[1];//极坐标中的θ
            double cos = Math.cos(theta);
            double sin = Math.sin(theta);
            double x0 = cos * rho;
            double y0 = sin * rho;
            double len = 800;//所画直线长度
            Point pt1 = new Point(Math.round(x0 + len * (-sin)), Math.round(y0 + len * (cos)));
            Point pt2 = new Point(Math.round(x0 - len * (-sin)), Math.round(y0 - len * (cos)));
            Imgproc.line(dst, pt1, pt2, new Scalar(0, 0, 255), 3);
        }
        //显示
        HighGui.imshow("Detected Lines", dst);
        HighGui.waitKey(0);
        System.exit(0);
    }
}

将阈值提高到300，theta参数调整为 PI/30，最后检测结果符合预期：

2.2、概率霍夫变换

概率霍夫变换是标准霍夫变换的改进版。标准霍夫变换中输出的是直线的p和0，根据这两个参数得到的是直线(没有起始点和终止点)而不是线段，而概率霍夫变换则输出线段的起始点和终止点。也就是说,标准霍夫变换只输出方向,而概率霍夫变换则不仅输出方向,还输出范围。之所以称为“概率”霍夫变换，是因为这个算法并没有累加平面内的所有可能的点，而是随机选取一个点集进行计算。其理论依据是如果峰值足够高，则只用一小部分时间去寻找它就足够了，这样可以大大节省时间。

//用概率霍夫变换在二值图像中寻找直线
void Imgproc.HoughLinesP(Mat image, Mat lines, double rho, double theta, int rhreshold)

• image：8位单通道二值图像
• lines：检测到的直线（二维数组），每条直线由p和0表示
• rho：累加器中距离的精度，单位为像素
• theta：累加器中角度的精度，单位为弧度
• threshold：累加器中的阈值参数，只有获得足够多投票的直线才出现在结果集中。这个值越大，所判断的直线越少，反之越多

public class HoughLinesP {
    static {
        OpenCV.loadLocally(); // 自动下载并加载本地库
    }

    public static void main(String[] args) {
        //读取图像并显示
        Mat src = Imgcodecs.imread("/Users/acton_zhang/J2EE/MavenWorkSpace/opencv_demo/src/main/java/demo2/chess.jpg");
        HighGui.imshow("src", src);
        HighGui.waitKey(0);
        //Canny边缘检测并将结果存储为BGR图像
        Mat canny = new Mat();
        Mat dst = new Mat();
        Imgproc.Canny(src, canny, 50, 200, 3, false);
        Imgproc.cvtColor(canny, dst, Imgproc.COLOR_GRAY2BGR);

        //进行霍夫线检测，结果在lines中
        Mat lines = new Mat();
        Imgproc.HoughLinesP(canny, lines, 1, Math.PI / 180, 250);
        //将检测结果用红线画出
        for (int n = 0; n < lines.rows(); n++) {
            double[] vec = lines.get(n, 0);
            double x1 = vec[0], y1 = vec[1];//线段的端点1
            double x2 = vec[2], y2 = vec[3];//线段的端点2
            Point pt1 = new Point(x1, y1);
            Point pt2 = new Point(x2, y2);
            Imgproc.line(dst, pt1, pt2, new Scalar(0, 255, 255), 5);
        }
        //显示
        HighGui.imshow("Detected Lines", dst);
        HighGui.waitKey(0);
        System.exit(0);
    }
}

原图：

概率霍夫变换检测：

可以看出，概率霍夫变换与标准霍夫变换的结果有较大的不同。首先，概率霍夫变换检测的结果是线段，而不是直线。另外，概率霍夫变换只检测出了部分直线（线段），有相当一部分直线（线段）并未检测出来，因为它只是随机选择了一个点集进行计算，而没有计算所有像素。

三、霍夫圆检测

3.1、霍夫圆检测的原理

霍夫圆检测的原理和霍夫线检测类似，只是从霍夫线的二维变成了三维。在笛卡儿坐标系中圆的方程如下:

(x-a)^2 + (y-b)^2 = r^2

其中，(a，6)为圆心坐标，r为圆的半径，如图所示

由此可见，要表示一个圆需要 a、b、r 三个参数。在 a、b、r组成的三维坐标系中，一个点可以唯一确定一个圆。笛卡儿坐标系中经过某一点的所有圆映射到 abr 坐标系中是一条三维的曲线，如图 10-12 所示。

霍夫圆检测的过程和直线差不多，但三维空间的计算量比二维空间增加了很多倍，标准霍夫圆检测效率很低，所以 OpenCv 中使用霍夫梯度法进行圆形的检测。

3.2、霍夫梯度法

霍夫梯度法的原理并不复杂，如图 10-13 所示，圆心是圆周上众多法线的交汇点,霍夫梯度法就是据此来寻找圆心的。

霍夫梯度法检测圆的原理可用下面的例子说明。

假设图像上有4个点，分别为 A、B、C、D，已知这些点的梯度方向，求这些点构成的圆，如图 10-14(a)所示。
求解的过程如下:

1. 沿4个点的梯度方向画出法线,发现它们相交于 O 点,那么 O点就是可能的圆心,如图 10-14(b)所示。
2. 下一步是寻找半径,或者说验证各种半径的支持度。4 个点与O点的连线距离 OA、OB、OC、OD 分别为4种候选的半径，记为r、r2、r3、r4。
3. 经计算发现r~r4中只有两种半径，其中r=r2=r3，统一记为r，而r比n要长。
4. 现在统计各半径的支持度:r的支持度为 3,r的支持度为 1。
5. 假设 3 超过累加器中设定的阈值，那么点 O 和半径, 就是要求解的圆的圆心和半径
6. 根据点O和,画出的圆，如图 10-14(b)所示。

由上可知，霍夫梯度法大体分为两步，第1步是寻找候选圆心，第2步是根据非零像素对候选圆心的支持度来确定半径。在寻找圆心时,霍夫梯度法需要先对图像进行 Canny 边缘检测，然后用 Sobel函数求出局部梯度并画出法线，并通过累加器投票得出候选的圆心。接着，对每个候选圆心选择非零像素最支持的一条半径。如果一个候选圆心获得边缘图像非零像素最充分的支持，并且离其他圆心有足够的距离，则该圆心及半径所构成的圆成立。OpenCy 中霍夫圆检测的函数原型如下:

//用霍夫变换寻找圆
Imgproc.HoughCircles(Mat image, Mat circles, int method, double dp, double minDist, double param1, double param2, int minRadius, int maxRadius)

• image：输入图像，要求是8位单通道灰度图
• circles：检测到的圆
• method：检测算法，目前只支持Imgproc.HOUGH_GRADIENT霍夫梯度算法
• dp：霍夫空间的分辨率。当dp=1时，累加器的分辨率与输入图像相同；当dp=2时，累加器的分辨率（宽和高）是输入图像的一半
• minDist：圆心之间的最小距离，如果检测到两个圆心距离小于该值，则认为它们是同一个圆心
• param1：Canny边缘检测时的高阈值，低阈值是高阈值的一半
• param2：检测圆心和确定半径时的累加器计数阈值
• minRadius：检测到的圆半径的最小值
• maxRadius：检测到的原半径的最大值。当MaxRadius<=0时表示采用图像的最大尺寸

夫梯度法解决了标准霍夫圆检测效率过低的问题，但是它存在如下缺陷:

1. 霍夫梯度法中使用 Sobel 导数来计算局部梯度，但这并不是一个数值稳定的方法在某些情况下会产生噪声。
2. 在边缘图像中的每个非零像素都是很多可能的圆上的点，如果累加阈值设置得过低，则会导致算法耗时过多。
3. 霍夫梯度法中每个圆心只选择一个圆，这意味着如果有同心圆，就只能选择其中一个。

public class HoughCircle {
    static {
        OpenCV.loadLocally(); // 自动下载并加载本地库
    }

    public static void main(String[] args) {
        //读取图像并显示
        // Mat src = Imgcodecs.imread("/Users/acton_zhang/J2EE/MavenWorkSpace/opencv_demo/src/main/java/demo2/chess.jpg");
        Mat src = Imgcodecs.imread("/Users/acton_zhang/J2EE/MavenWorkSpace/opencv_demo/src/main/java/demo2/seeds.png");
        HighGui.imshow("src", src);
        HighGui.waitKey(0);
        //预处理
        Mat gray = new Mat();
        Imgproc.cvtColor(src, gray, Imgproc.COLOR_BGR2GRAY);
        Imgproc.GaussianBlur(gray, gray, new Size(9, 9), 2);
        //霍夫圆检测
        Mat circles = new Mat();
        Imgproc.HoughCircles(gray, circles, Imgproc.HOUGH_GRADIENT, 1, 10, 100, 30, 5, 30);
        //将检测出的圆画出
        for (int n = 0; n < circles.cols(); n++) {
            double[] c = circles.get(0, n);
            Point center = new Point(Math.round(c[0]), Math.round(c[1]));//圆心
            int radius = (int)Math.round(c[2]);//半径
            Imgproc.circle(src, center, radius, new Scalar(0, 0, 255), 5);
        }
        //显示
        HighGui.imshow("Circles", src);
        HighGui.waitKey(0);
        System.exit(0);
    }
}

原图1：

霍夫圆检测1：

原图2：

霍夫圆检测2：

鉴于霍夫梯度法的原理，最后检测出的圆可能和直观感觉有较大区别。有时图像中明明有较多的圆却无法检测出来;有时检测出的圆在我们看来根本就不是圆，因此，在利用霍夫梯度法检测圆时，应根据其原理选择合适的场景，否则结果往往不尽人意。