一种自适应Canny边缘检测算法的并行设计与TBB实现*

孙陆鹏　肖汉

摘要：为了充分利用多核优势，提高运算图像处理速度，采用Intel线程构建模块对自适应Canny边缘检测算法的并行处理进行分析和设计，提出在自适应尺度计算、高斯滤波、自适应阈值计算、非最大抑制、边缘连接各阶段的并行解决方案，对不同分辨率图像进行实验。实验结果表明，该算法加速效果显著，对提高图像处理系统的运行效率具有实际意义。

关键词：Intel TBB 自适应高斯平滑 Canny边缘检测 自适应阈值

中图分类号：TP391 文献标识码：A 文章编号：1007-9416（2016）06-0000-00

1 引言

图像的边缘检测是进行图像分析和理解的基础，是目前机器视觉研究领域的热点之一。传统的边缘检测方法包括Roberts算子、Soble算子、Prewitt算子等一阶微分算子，以及Laplacian算子、LoG算子等二阶微分算子等[3]。Canny边缘检测算法对受白噪声影响的阶跃型边缘进行边缘检测是最优的[4]，因此，Canny算法在边缘检测中的应用最为广泛。Canny算法进行边缘检测，需要人为设定尺度和双门限值，近年来，多位学者提出了自适应确定尺度和双阈值的方法[5-8]，同时反映自适应Canny边缘检测方法运算速度较慢，无法满足实时性的需要[6-8]。本文尝试利用多核优势，提高自适应Canny边缘检测的速度。

目前，单核CPU的处理能力已达到极限状态，而对计算能力的应用需求却越来越高，市场上多核处理器已成为主流，通过多核CPU进行并行计算来提高计算性能已成为发展趋势[1]。并行编程模型将逐渐取代传统的串行编程模式。从应用程序开发层面来看，目前流行的并行编程模型主要有两类[2]：一类是共享存储模型；例如OpenMP，它是对一种语言的扩展，支持C语言和Fortran语言的并行扩展，包括编译指导语句、函数库和环境变量。另一类是消息传递模型；例如MPI，它本身不是编程语言，而是具有并行语义的编程接口。TBB（Threading Building Blocks，线程构建模块）是Intel公司针对多核平台开发的一组开源的C++的模板库， 支持可伸缩的并行编程。TBB为多核环境下采用多线程并行程序设计提供了一种解决方案。

2自适应Canny边缘检测算法简介

Canny边缘检测算法是Canny在1983年提出的，它基于以下三个标准[9，10]：（1）检测标准：不丢失重要的边缘，不应有虚假的边缘；（2）定位标准：实际边缘与检测到的边缘位置之间的偏差最小；（3）单响应标准：将多个响应降低为单个边缘响应。Canny边缘检测的一般过程如下[4]：

2）计算图像中的每个像素的梯度和梯度方向；

3）非最大化抑制（non-maximum suppression），对每一个像素点，将其梯度与其梯度方向两侧的像素的梯度进行比较，若其梯度不是最大的，则该像素不可能为边缘，将其灰度值置为0，否则将其设置为候选边缘点，其灰度用128表示。

4）使用双门限方法对边缘图像作滞后阈值化处理，消除虚假响应。设置高阈值τh和低阈值τl， τh>τl，梯度不小于τh的像素一定是边缘点，与边缘点相邻并且梯度不小于τl的像素也设置为边缘（灰度设置为255），其余像素设置为非边缘（灰度置为0）。

传统Canny边缘检测算法中，τh和τl一般由经验得来。文献[6]提出用两次最大类间方差法的自适应设定双门限值τh和τl。最大类间方差法（又名大津法，Otsu方法）是一种阈值自动选取的方法。其基本思想是选取一个最佳阈值使得该阈值分割得到的两类间具有最好的分离性。对经过非极大抑制后得到的所有候选边缘点，统计其梯度信息得到边缘梯度直方图。在梯度直方图上，依次将每个梯度值作为分类依据，计算该值左右两类的类间方差，选取类间方差最大的梯度值作为最佳阈值。首先得到高阈值τh，然后在区间[0， τh）再次使用该方法，得到低阈值τl。

3 并行性分析与设计

多核并行Canny自适应边缘检测方法的每一步都要用到前一步的计算结果，依赖性较强。分六个阶段进行，选择TBB的模板进行并行计算。

3.1计算各像素高斯滤波平滑系数

为了提高运算速度，高斯滤波的高斯核事先计算出来，硬编码在程序中，用一个二维double型数组存储，每行对应一个平滑系数σ。此阶段本文运用公式（1），并进行归一化处理，计算结果在区间[0，0.9]内，各像素的σ值乘以10并取整存储，为该像素滤波参数在数组中的索引。

3.3 计算梯度和方向

针对高斯滤波结果图像，使用prewitt算子分别计算：x方向的梯度P；y方向的梯度Q；梯度M；梯度方向θ。梯度 ，梯度方向 ，并由弧度转换为角度。

3.4 非最大抑制

非最大抑制阶段，逐像素检测其梯度是否不小于其梯度方向上两侧像素点的梯度值，插值计算各像素梯度方向两侧像素的梯度，进行比较，若像素的梯度是三个点中最大的，将该像素确定为为候选边缘，像素值设为128。其中根据梯度方向，分为四类进行插值运算，分别是：（1）[0o，45o），[180o，225o）；（2）[45o，90o），[225o，270o）；（3）[90o，135o），[270o，315o）；（4）[135o，180o），[315o，360o）。

3.5自适应计算双门限值

此阶段采用类间最大方差法进行两次运算，分别求出高阈值和低阈值。分为四个步骤：

（1）统计非最大抑制后的各梯度像素数，得到梯度直方图，使用parallel_for模板；

（2）统计最大梯度值M，串行计算；

（3）在梯度直方图数据基础上，对每一梯度值，用公式（4）求出不大于该梯度的梯度总质量矩；此运算属于前缀和运算，使用parallel_scan模板。

3.6 边缘检测与连接阶段

在非最大抑制后的图像上，检测各像素的梯度值，梯度大于高阈值的设为边缘，梯度在高低阈值之间又与边缘像素相邻的像素也设为边缘，其它像素为非边缘像素。分三步进行：

（1）边缘检测：对每个像素，其若高于高阈值，设置为边缘像素，并行，parallel_for模板；

（2）边缘连接：与边缘像素相邻的像素，梯度值高于低阈值的，设置为边缘像素，递归进行。串行。

（3）设置非边缘像素灰度值为0，并行，parallel_for模板。

此阶段，笔者尝试了以下方法：

使用一阶段并行，递归进行边缘检测，实验中发生冲突，因为相邻像素有共同的邻接点，如果这两个像素均为边缘，并且该邻接点梯度高于低阈值，则都要写入此邻接点的灰度值，就发生了并发冲突。

此阶段第二步笔者尝试使用TBB提供的并发容器concurrent_hash_map分两步进行：（1）考查已设置为边缘的像素，若其梯度高于低阈值，将该像素保存在一个concurrent_hash_map中；递归。（2）将位于concurrent_hash_map中的像素设置为边缘，其余像素设置为非边缘。实验结果表明，这种方法的速度比串行速度慢，因此边缘连接阶段仍采用了串行算法。

4 实验结果与分析

本文采用的实验平台是AMD A6-3670四核处理器，2.7GHz，4G内存，编程环境为Visual Studio 2010，语言采用VC10.0，TBB版本为4.1。图像分辨率从512*512到4096*4096的8bits灰度Lena图像，进行对比实验，结果见表1。其中线程数是初始化TBB的task_scheduler_init对象时指定的线程数量，在使用parallel_for模板时，指定粒度为1024，其中的运行时间包括图像读取、处理和保存的总时间。

从实验结果可以看出，并行算法在线程数设置为1时，也比串行算法要快，在实验数据范围内，随着图像的增大，加速比逐渐提高，但没有高出计算机核数。

5 结语

使用Intel TBB并行模板进行自适应Canny边缘检测，提高了边缘检测的速度，算法通用性强，对提高图像处理的实时性有一定的意义。其中边缘连接阶段的并行处理尚需进一步研究。

参考文献

[1]Cameron Hughes，Tracey Hughes著，齐宁译.C++多核高级编程[M].北京：清华大学出版社，2010：1-16.

[2]张思乾，程果，陈荦 等.多核环境下边缘提取并行算法研究[J].计算机科学，2012，39（1）：295-298.

[3]杜文亮，刘晓东，吕园园.基于C-Canny 算子与灰度空间的彩色图像边缘检测[J].微电子学与计算机，2010，27（4）：17-20.

[4]Milan Sonka，Vaclav Hlavac，Roger Boyle著，艾海舟，苏延超，兴军亮 等译.图像处理、分析与机器视觉（第3版）[M].北京：清华大学出版社，2011：100-102.

[5]赵洁，李玮，郝志鹏，彭慧卿.基于改进Canny算子与图像形态学融合的边缘检测方法[J].微型机与应用，2011，30（10）：44-47.

[6]刘超，周激流，何坤.基于Canny算法的自适应边缘检测方法[J].计算机工程与设计，2010，31（18）：4036-4039.

[7]李二森，张保明，周晓明，等.自适应Canny边缘检测算法研究[J]测绘科学，2008，33（6）：119-120.

[8]王植，贺赛先.一种基于Canny理论的自适应边缘检测方法[J].中国图象图形学报，2004，9（8）：957-961.

[9]陈宏希.基于边缘保持平滑滤波的Canny算子边缘检测[J].兰州交通大学学报（自然科学版），2006，25（1）：86-90.

[10]王小俊，刘旭敏，关永.基于改进Canny算子的图像边缘检测算法[J].计算机工程，2012，38（14）：196-198，202.

[11]陈杰，王振华，窦丽华.一种尺度自适应Canny边缘检测方法[J].光电工程，2008，35（2）：79-84.

[12]James Reinders（仁达敬）著，聂雪军译.Intel Threading Building Blocks编程指南[M].北京：机械工业出版社，2009：46-122.