Canny边缘检测算法及实现

微信公众号：幼儿园的学霸

前言

提取图片的边缘信息是底层数字图像处理的基本任务之一.边缘信息对进一步提取高层语义信息有很大的影响.

对图像提取边缘可以通过图像的二阶导数如拉普拉斯算子,或者一阶导数如Sobel,prewitt,Roberts等算子.一般情况下:
(1)一阶导数通常会产生较粗的边缘;
(2)二阶导数对精细细节,如细线、孤立点和噪声有较强的响应;
(3)二阶导数在灰度斜坡和灰度台阶过渡处会产生双边沿响应;
(4)二阶导数的符号可以确定边缘的过渡是从亮到暗还是从暗到亮;
(5)二阶导数对细节更敏感.

由于导数对噪声比较敏感,因此提取边缘之前最好先对图像进行平滑处理,以去除噪声(噪声是高频信号,通过低通滤波去除).

边缘检测是一个高通滤波的过程,因为边缘往往位于图像灰度变化剧烈的地方.
在使用拉普拉斯算子提取边缘之前,如果先使用高斯滤波平滑图像,这一过程就是Laplacian-Gauss(LoG)算子,可以参考前述SIFT系列文章.

除此之外,还可以使用Canny算子进行边缘检测.
Canny边缘检是在在1986年提出来的,到今天已经30多年过去了,但Canny算法仍然是图像边缘检测算法中最经典、先进的算法之一.在OpenCV中集成的边缘检测算法就是Canny算子.

相比Sobel、Prewitt等算子,Canny算法更为优异.
Sobel、Prewitt等算子有如下缺点:
1)没有充分利用边缘的梯度方向;
2)最后得到的二值图,只是简单地利用单阈值进行处理;
而Canny算法基于这两点做了改进,提出了:
1)基于边缘梯度方向的非极大值抑制.
2)双阈值的滞后阈值处理.

原理

Canny 边缘检测算法是John F.Canny于1986年开发出来的一个多级边缘检测算法,也被很多人认为是边缘检测的最优算法,最优边缘检测的三个主要评价标准是:

低错误率:标识出尽可能多的实际边缘,同时尽可能的减少噪声产生的误报.
高定位性:标识出的边缘要与图像中的实际边缘尽可能接近.
最小响应:图像中的边缘只能标识一次.

步骤

1.消除噪声.使用高斯平滑滤波器卷积降噪(也可以尝试使用双边滤波等算法).
2.计算梯度幅值和方向.可选用soble算子、Prewitt算子、Roberts模板等等.这样就可以得图像在x和y方向梯度.如x和y方向的Sobel算子分别为:
$\begin{aligned} S_x = \left[ \begin{array}{ccc} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{array} \right] \quad S_x = \left[ \begin{array}{ccc} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{array} \right] \end{aligned} \quad \text{(1)}$

某点的梯度 $G$ 和方向 $\theta$ 如下示意图所示:
某点梯度示意图

注意上图中梯度方向为-45°,这是由于y坐标轴方向向下的原因.

当然,对梯度幅值也可以采用近似求法:
$G_x +G_y \quad \text{(2)}$

3.非极大值抑制. 非极大值抑制是进行边缘检测的一个重要步骤,通俗意义上是指寻找像素点局部最大值.在每一点上,领域中心x与沿着其对应的梯度方向的两个像素相比,若中心像素为最大值,则保留,否则中心置0,这样可以抑制非极大值,保留局部梯度最大的点,以细化边缘.

沿着梯度方向进行比较,而非在邻域内进行比较.

梯度方向

如上图所示,需要将中心像素与其梯度方向的两个像素进行比较.但是,由于图像中的像素点是离散的二维矩阵,其梯度方向两侧并没有真实存在的像素,或者说是一个亚像素(sub pixel)点,对于这个不存在的点的位置与梯度就必须通过对其两侧的点进行插值来得到.针对利用插值计算梯度进行非极大值抑制的处理手段相关资料比较多,不赘述.

由于利用插值求解梯度,运算量比较大,在John Canny提出Canny算子的论文中,非极大值抑制时,他采用了近似处理的方法.将各点的梯度方向近似/量化到0°、90°、45°、135°四个梯度方向上进行,每个像素点梯度方向按照距离这四个方向的相近程度用这四个方向来代替.通过量化,意味着图像中各点的梯度方向只能沿着0°、90°、45°、135°四个方向中的某一个.
如下图所示为选择的4个量化方向,每个方向对应邻域内的两个点,4个方向正好将邻域内的8个点应用完毕.
梯度量化方向

量化分配

需要注意的是,如何标志方向并不重要,重要的是梯度方向的计算要和梯度算子计算的方向保持一致.

如下为非极大值抑制示意图.图中以颜色深浅表示梯度幅值大小.经过NMS后,原边缘被细化.意味着在真实边缘处是单点响应.
NMS示意图

4.滞后阈值(Hysteresis thresholding):滞后阈值需要两个阈值(高阈值和低阈值).
在施加非极大值抑制之后,剩余的像素可以更准确地表示图像中的实际边缘.然而,仍然存在由于噪声和颜色变化引起的一些边缘像素.为了解决这些杂散响应,必须用弱梯度值过滤边缘像素,并保留具有高梯度值的边缘像素,可以通过选择高低阈值来实现.

a.如果某一像素位置的幅值超过高阈值,该像素被保留为边缘像素.
b.如果某一像素位置的幅值小于低阈值,该像素被排除.
c.如果某一像素位置的幅值在两个阈值之间,则根据连通性来分类为边缘或者非边缘:该像素与确定为边缘的像素点邻接,则判定为边缘;否则为非边缘.

上述判断中,只要该像素与确定为边缘的像素点邻接,则判定该点为边缘点,而非该像素与大于高阈值的像素点邻接来判定该点是否为边缘点. 注意这两者的区别.

Canny 推荐的高:低阈值比在 2:1 到3:1之间.

通过滞后阈值(双阈值)能够减少伪边缘,同时对真正的边缘进行连接.如下为滞后阈值示意图,经过滞后阈值后,存在缝隙的边缘被连接起来:

一点设想:双阈值的选择可以和之前的一篇Multi Leve OTSU实现的博文进行结合,利用最大类间方差法的思想,求解出2个阈值,以实现高低阈值的自动选择.该部分应该值得探究.

实现

实现代码如下.

//
// Created by liheng on 12/21/21.
//#include <opencv2/opencv.hpp>
//#include <opencv2/core/hal/hal.hpp>/*!* 边缘连接:从确定边缘点出发,延长边缘* @param x* @param y 当前像素坐标* @param magnitude 梯度幅值.CV_32FC1* @param tUpper* @param tLower 双阈值* @param edges 边缘图 CV_8UC1*/
void followEdges(int x, int y, const cv::Mat &magnitude, int tUpper,int tLower, cv::Mat &edges);/*!* 边缘检测.通过滞后阈值,进行伪边缘去除和边缘连接* @param magnitude 梯度幅值 CV_32FC1* @param tUpper* @param tLower 双阈值* @param edges 边缘图 CV_8UC1*/void edgeDetect(const cv::Mat& magnitude, int tUpper, int tLower, cv::Mat& edges);/*!*非极大值抑制* @param magnitudeImage CV_32FC1 各点的梯度幅值* @param directionImage CV_32FC1 存储各点的梯度方向0-360°*/
void nonMaximumSuppression(cv::Mat &magnitudeImage,const cv::Mat &directionImage);/*!* 自定义Canny算法实现* @param src* @param edges* @param upperThresh* @param lowerThresh*/
void myCanny(const cv::Mat& src, cv::Mat& edges, int upperThresh, int lowerThresh)
{//Step1. 高斯滤波 Remove noise (apply gaussian)cv::Mat image;cv::GaussianBlur(src, image, cv::Size(3, 3), 1.5);//Step2. 使用sobel计算相应的梯度幅值及方向. Calculate gradient (apply sobel operator)cv::Mat magX,magY;//X,Y方向的梯度cv::Sobel(image, magX, CV_32FC1, 1, 0, 3);cv::Sobel(image, magY, CV_32FC1, 0, 1, 3);cv::Mat Mag,Ori;//梯度幅值,幅角cv::cartToPolar(magX,magY,Mag,Ori,true);//幅角0~360//Step3.Non-maximum supression 非极大值抑制// For each pixel find two neighbors (in the positive and negative gradient directions,// supposing that each neighbor occupies the angle of π/4 , and 0i s the direction straight to the right).// If the magnitude of the current pixel is greater than the magnitudes of the neighbors, nothing changes,// otherwise, the magnitude of the current pixel is set to zero.nonMaximumSuppression(Mag, Ori);//Step4. 双阈值检测和边缘连接 Double thresholdingedgeDetect(Mag, upperThresh, lowerThresh, edges);
}void followEdges(int x, int y, const cv::Mat &magnitude, int tUpper,int tLower, cv::Mat &edges)
{edges.at<uchar>(y, x) = 255;//该点与强边缘点邻接,故确定其为边缘点for (int i = -1; i < 2; i++)//8邻域: (i,j) ∈ [-1 0 1].一共8个点,因此要去掉自身{for (int j = -1; j < 2; j++){if(i==0 && j==0 )//去除自身点continue;// 边界限制if ( (x + i >= 0) && (y + j >= 0) &&(x + i < magnitude.cols) && (y + j < magnitude.rows)){// 梯度幅值边缘判断及连接if ((magnitude.at<float>(y + j, x + i) > tLower)&& (edges.at<uchar>(y + j, x + i) != 255))//大于低阈值,且该点尚未被确定为边缘点{followEdges(x + i, y + j, magnitude, tUpper, tLower, edges);}}}}
}void edgeDetect(const cv::Mat& magnitude, int tUpper, int tLower, cv::Mat& edges)
{int rows = magnitude.rows;int cols = magnitude.cols;edges = cv::Mat(magnitude.size(), CV_8UC1, cv::Scalar(0));for (int y = 0; y < rows; y++){for (int x = 0; x < cols; x++){// 梯度幅值判断.//大于高阈值，为确定边缘点if (magnitude.at<float>(y, x) >= tUpper){followEdges(x, y, magnitude, tUpper, tLower, edges);}}}
}void nonMaximumSuppression(cv::Mat &magnitudeImage,const cv::Mat &directionImage)
{cv::Mat edgeMag_noMaxsup = cv::Mat::zeros(magnitudeImage.size(), CV_32FC1);//根据输入的角度,判断该点梯度方向位于位于那个区间//[0,45,90,135]auto _judgeDir = [](float angle)->int {if( (0<=angle&&angle<22.5) || (157.5<=angle&&angle<202.5) ||(337.5<=angle&&angle<360) )//梯度方向为水平方向return 0;else if( (22.5<=angle&&angle<67.5) || (202.5<=angle&&angle<247.5) )//45°方向return 45;else if( (67.5<=angle&&angle<112.5) || ((247.5<=angle&&angle<292.5)) )return 90;else /*if( (112.5<=angle&&angle<157.5) || ((292.5<=angle&&angle<337.5)) )*/return 135;};for (int r = 1; r < magnitudeImage.rows - 1; ++r){for (int c = 1; c < magnitudeImage.cols - 1; ++c){const float mag = magnitudeImage.at<float>(r, c);//当前位置梯度幅值//将其量化到4个方向中进行计算const float angle = directionImage.at<float>(r,c);const int nDir = _judgeDir(angle);//非极大值抑制,8邻域的点进行比较,但只比较梯度方向//或者采用线性插值的方式,在亚像素层面进行比较//由于图像的y轴向下,x轴向右,因此注意这里的45°和135°switch(nDir){case 0://梯度方向为水平方向-邻域内左右比较{float left = magnitudeImage.at<float>(r, c - 1);float right = magnitudeImage.at<float>(r, c + 1);if (mag > left && mag >= right)edgeMag_noMaxsup.at<float>(r, c) = mag;break;}case 135://即我们平常认为的45°.邻域内右上 左下比较.{float right_top = magnitudeImage.at<float>(r - 1, c+1);float left_down = magnitudeImage.at<float>(r + 1, c-1);if (mag > right_top && mag >= left_down)edgeMag_noMaxsup.at<float>(r, c) = mag;break;}case 90://梯度方向为垂直方向-邻域内上下比较{float top = magnitudeImage.at<float>(r-1, c);float down = magnitudeImage.at<float>(r+1, c);if (mag > top && mag >= down)edgeMag_noMaxsup.at<float>(r, c) = mag;break;}case 45://邻域内右下 左上比较{float left_top = magnitudeImage.at<float>(r - 1, c - 1);float right_down = magnitudeImage.at<float>(r + 1, c + 1);if (mag > left_top && mag >= right_down)edgeMag_noMaxsup.at<float>(r, c) = mag;break;}default:break;}//switch}//for col}//for rowedgeMag_noMaxsup.copyTo(magnitudeImage);
}int main()
{cv::Mat srcImage = cv::imread("1.bmp", cv::IMREAD_GRAYSCALE);int highValue = 100;int lowValue = 50;cv::Mat cannyEdges;cv::Mat cvcannyEdges;myCanny(srcImage, cannyEdges, highValue, lowValue);cv::GaussianBlur(srcImage, srcImage, cv::Size(3, 3), 1.5);cv::Canny(srcImage,cvcannyEdges,highValue,lowValue,3,true);cv::Mat merged;cv::Mat t = cv::Mat::zeros(cannyEdges.size(),CV_8UC1);std::vector<cv::Mat> channels;channels.push_back(t);channels.push_back(cannyEdges);channels.push_back(cvcannyEdges);cv::merge(channels,t);cv::imshow("original", srcImage);cv::imshow("edges", cannyEdges);cv::imshow("cvedges", cvcannyEdges);cv::imshow("mergeed canny",t);cv::waitKey(0);return 0;
}

输入图像如下所示:

自定义算法的边缘检测结果如下.该结果和OpenCV源码实现结果一致.

经过对不同图像进行测试,对比,自定义实现的结果基本和OpenCV源码结果一致,偶尔存在检测结果极小区域不一致的情况.
如针对下面这幅图片:
输入图片

检测结果如下. 图中将自定义检测结果和OpenCV源码结果合并在一张图上进行展示.自定义实现检测的结果用绿色展示,OpenCV源码检测的结果用红色显示,那么对于检测结果相同的部分,在图像上将显示为黄色.可以看到图像中间有一小块显示为绿色的边缘,意味着该边缘是由自定义检测方法检测到的,而OpenCV中自带方法位检出该边缘.
检测结果叠加

参考资料

1.Canny 边缘检测
2.Canny算子边缘检测原理及实现
3.图像边缘检测算法Canny、Prewitt和sobel
4.Sobel算子的数学基础 --Sobel算子的来历
5.Canny边缘检测算法的一些改进 --探讨目前Canny算法中修改某个步骤对检测结果的影响.
6.Canny边缘检测算法原理及C语言实现详解 --非极大值抑制采用插值方法确定梯度

下面的是我的公众号二维码图片，按需关注。
图注:幼儿园的学霸