【算法随记一】Canny边缘检测算法实现和优化分析。
【算法随记一】Canny边缘检测算法实现和优化分析。
以前的博文大部分都写的非常详细，有很多分析过程，不过写起来确实很累人，一般一篇好的文章要整理个三四天，但是，时间越来越紧张，后续的一些算法可能就以随记的方式，把实现过程的一些比较容易出错和有价值的细节部分加以描述，并且可能需要对算法本身有一定了解的朋友才能明白我所描述的一些过程了。
那这个系列的开篇，我们以Canny边缘检测算法为头吧。
相关参考资料：
4、Opencv 3.0\opencv\sources\modules\imgproc\src\canny.cpp
Canny边缘检测是边缘检测算法领域里最为著名的算法，其标准实现过程就是下面五个步骤：1、高斯模糊。
2、 计算梯度幅值和方向。
3、非最大值抑制。
4、 双阀值。
5、 滞后边界跟踪
个人认为，第一步可以不作为标准流程，在OpenCV的实现里，也没有他，有些文章里也说了可以用保边滤波来代替标准的高斯模糊的过程，其实，用高斯模糊，在其他参数相同的情况下，模糊后的结果线条会更少，这是因为模糊后边缘部分的细节有所丢失，这样在后续的非最大值抑制步骤里强边缘和若边缘的数据量会有所减少。
不过这个步骤带来的另外一个好处就是，算法的计算时间会减少，这主要是由于边缘信息的减少让最后一步的滞后边界跟踪计算量大为减少。在计算梯度幅值和方向时，最开始的Canny算法使用的时2领域，这个计算量要少，但能表达的边缘信息还是不够强烈，所以现在一般都采用Sobel算子的方式，计算处X和Y方向的梯度和幅值，在幅值计算过程中，可以使用L1范数（绝对值之和），也可以使用L2范数（欧式距离），两者在结果上还是稍有差异的，总体来说，L2范数的结果稍微好一点。
计算这个的过程，我们可以借助SSE图像算法优化系列九：灵活运用SIMD指令16倍提升Sobel边缘检测的速度（4000*3000的24位图像时间由480ms降低到30ms） 一文的相关技巧来加速，当我们需要使用L2范数时，这个结果是个浮点数，为了提高后续的处理速度，我们可采用 LinePMX = sqrtf((float)((Gx * Gx + Gy * Gy) << 12));这样的过程把他定点化，保存到unsigned short类型里，即可以节省内存，有能有利于后续的处理，而且在本例中计算的精度也能够保证了。
非最大值抑制过程，也就是根据当前点的梯度的方向，比较当前幅值及其周边2个位置的幅值，如果当前幅值是他们的最大值，则该点需保留，否则，该点舍弃。那么这里的实现过程可以和后面的双阈值处理放置在同一个过程中，这样可以多方面提高算法速度，因为，如果当前的幅值小于小的阈值，哪怕他是局部最大值，我们也要舍弃他，所以就根本不用计算他，而在确定某个点是改保留时，通过进一步判断其和大的阈值之间的关系，可以同时确定他是否为强边缘，或者弱边缘。
在这个过程中，我们可以像OpenCV那样采用简易的判断，把梯度分为0，22.5，22.5 67.5，67.5 90三个范围，在小于22.5度时，只需比较当前左右两个点的幅值，当大于67.5度时，比较上下两个点的幅值，否则，比较对角线上两个点的幅值。
另外一种方式就是如下图所示，进行插值比较：
这种方式理论上讲更为精确一些，但是带来主要时计算量的增加。
在采用OpenCV方法实现时，前面的幅值计算部分，我们可以考虑不用开平方，因为我们只需要比较大小，平方值大，同样也就代表原始值大，当然这个时候我们需要对用户输入的LowThreshold和HighThreshold进行同步的平方处理。 在滞后边界跟踪方面，我觉得有一篇文章讲的比较好，我直接引用他的说法： 那么问题来了，弱边缘到底是边缘，还是由于噪点导致的梯度突变。
判定依据有多种。有的人是判定弱边缘点的8邻域中是否存在强边缘，如果有则将弱边缘设置成强的。没有就认为是假边缘。
另一种方案是用搜索算法，通过强边缘点，搜索8领域是否存在弱边缘，如果有，以弱边缘点为中心继续搜索，直到搜索不到弱边缘截止。
我看大部分人用的都是第二种方案，第二种方案也有二种实现方式，一个时递归法，一个是普通的循环法，递归容易导致堆栈溢出，还是使用循环法，速度快，而且效果稳定。
整个实现过程种，除了计算梯度和幅值时，可以使用SSE加速外，其他的过程由于有太多的判断和使用不连续位置的内存等原因，是不太可能用SSE进行加速的。
在内存占用方面，只需要梯度和幅值方面的数据（分别用signed short和unsigned short类型来保存），大约用6倍大小的图像内存，另外，为了能处理边缘像素，还需要一点点额外的小内存（注意在非最大值抑制时也可以使用Sobel边缘检测算法那个文章里的那种技巧来处理边缘)。针对这个过程，我们编制了一个UI界面，比较测试各个算法的结果：
下面进行一些简单的测试：
原图 无预处理，L1Gradient, OpenCV版抑制，低阈值50，高阈值150
无预处理，L2Gradient, OpenCV版抑制，低阈值50，高阈值150 无预处理，L1Gradient, 精确版抑制，低阈值50，高阈值150
无预处理，L2Gradient, 精确版抑制，低阈值50，高阈值150 高斯模糊0.5，L2Gradient, 精确版抑制，低阈值50，高阈值150
高斯模糊1，L2Gradient, 精确版抑制，低阈值50，高阈值150 保边滤波，L2Gradient, 精确版抑制，低阈值50，高阈值150
看得出，不同的配置还是有不同的效果的。但是硬要说谁号谁坏，可能还是难以肯定。
另外，测试中发现使用精确版本的抑制在线条拐角的地方可能连续性会比OpenCV版本要好一些，不会出现断裂。
在耗时方面，其实这个函数的效果和很多参数还是有关的，正如前面所说，如果进行了预处理，耗时会短一些，如果低阈值越大，耗时也越短，选用OpenCV的抑制算法速度也能有所提高。测试2500*2000的灰度图，大概需要60ms.
测试Demo:http://files.cnblogs.com/files/Imageshop/SSE_Optimization_Demo.rar。
