程慧　林梦兰　董振鑫　黄希宁　兰子洋　洪荣耀　张泽均

摘 要：针对移动平台计算资源匮乏问题，提出一种适用于移动平台的交互式图像边缘删除快速算法。利用通用图像边缘检测算法提取图像中的边缘，将图像的连续边缘存储成链表格式，再将链表格式边缘重映射成二维图像边缘。因移动平台触摸屏刷新频率低与图像离散化，导致手画删除边缘标记线间断及标记线与需要删除的边缘之间无交点，为克服该问题，利用线性插值与形态学膨胀运算估算出删除边缘标记线的间断点与加粗删除标记线，从而增加算法的鲁棒性。结果表明，图像边缘删除算法的时间复杂度与图像边缘像素点数无关，能够胜任移动平台的实时操作。

关键词：边缘检测；边缘删除；边缘重映射；移动平台

DOI：10.11907/rjdk.172445

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2017）009-0038-04

Abstract：Because of the lack of computing resources in mobile platforms， a fast interactive image edge delete algorithm that apply to mobile platform is proposed. This algorithm extracts the edge of an image by using a general image edge detection algorithm， the continuous boundary of the image are saved in a chain table， then information of edge in the chain table is remapped into two-dimensional image. In order to overcome problems， which of low refresh frequency of touch screen in mobile platform， the hand drawn marker line is interrupted by the image discrimination and no intersection between the marker line and the edge that needs to be removed， linear interpolation and morphology dilate operation are used to estimate discontinuity points and broaden the of the hand drawn marker line respectively， which increasing the robustness of the proposed algorithm. The time complexity of the proposed algorithm is free to the number of pixels in the detected edge， so it can be competent for real-time operation in the mobile platform.

Key Words：edge detection； edge deletion； edge remapping； mobile platform

0 引言

图像边缘、轮廓的检测与提取是计算机视觉、机器视觉的基础，在对象检测、无人驾驶与工业自动化控制中，对于图像采集、设备采集的图像数据，检测、提取出图像中感兴趣对象的边缘轮廓是最基础的步骤[1-3]。图像边缘定义为图像中不同区域之间的过渡。常用的边缘检测方法是基于一阶微分算子的方法[4-7]。

基于一阶微分算子的边缘检测算法基本思想是：首先，利用平滑算子对原始图像进行平滑处理，目的是降低原始图像中噪声对边缘检测算法的影响；其次，利用一阶算子模板对平滑后的图像进行计算，获得原始图像的边缘强度映射图；第三，采用阈值处理与形态学方法，从边缘强度映射图中提取出原始图像的边缘轮廓。

最经典的基于一阶微分算子的边缘检测算法是Canny边缘检测算法[6]。首先，利用某一尺度的高斯核平滑算子对原始图像进行平滑处理；其次，用一阶算子提取平滑图像的边缘强度映射图；第三，用双阈值方法提取边缘强度映射结果中的图像边缘，为了提取单像素宽度边缘，在Canny边缘检测算法中对提取的边缘二值图进行形态学腐蚀处理。

文献[8，9]中，首先利用各向异性高斯核对原始图像进行平滑处理；其次，对平滑处理的图像进行与各向异性高斯核主方向垂直方向的导数计算，获得平滑图像在某一方向上的边缘映射强度；第三，将提取的不同方向的边缘强度映射图组合成一幅边缘强度映射图；第四，采用与Canny边缘检测中类似的阈值化处理与形态学方法，从最终获得的边缘强度映射图中提取原始图像的边缘轮廓。

以上方法所提取的边缘二值图中，存在大量实际应用中不需要的边缘与轮廓，从而影响了实际应用效果。同时，随着移动平台的广泛应用，如何在移动平台上实现图像中有用边缘与轮廓的快速提取，显得越来越有价值[10]。针对以上问题，提出一种交互式图像边缘删除快速算法，该算法由两部分组成：利用经典的边缘检测算法提取原始图像的边缘二值图；利用交互式的方式标记出需要删除的边缘与轮廓。

1 总体框架

本文提出该算法的目的是，通过交互式方式，删除在通用图像边缘检测算法中获得的边缘二值图像于实际应用中不需要的边缘与轮廓。同时，为了满足该算法在移动平台上的应用要求，针对移动平台计算与存储资源匮乏的特点，边缘删除过程中，利用链表表示图像中的边缘，进而将边缘二值图像进行重映射，减少了在边缘二值图像中搜索需要删除边缘轮廓的过程，这使得边缘删除算法的时间复杂度不受图像中边缘数量的影响。同时，由于移动平台刷新频率与离散像素点的原因，使得删除标记线出现间断的点，从而不能正确地找到需要删除的边缘与轮廓，为了克服这个问题，本文利用线性插值方法连接删除标记线的间断段点，同时加粗删除标记线，进而增加删除算法的鲁棒性。本文算法的总体框架如圖1所示。图1中，首先利用边缘检测算法提取原始图像的边缘二值图，然后在边缘二值图上标记出需要删除的边缘与轮廓，最后通过边缘删除算法删除被删除标记线划过的边缘与轮廓。endprint

2 图像边缘存储与重映射

为了满足移动平台的要求与降低算法的时间复杂度，将边缘检测算法获得边缘二值图表示成链表格式，同时，将链表格式的边缘重映射成二维边缘图，以加快删除边缘轮廓的搜索过程。

2.1 边缘二值图链表表示

在标记为0或1的离散二值图像中，假设8邻域内相邻的标记为1的像素点是连续边缘或轮廓，如图2（a）所示，其中存在4条连续边缘。在计算机系统中，可以将如图2（a）所示的离散二值边缘图像存储成二维矩阵，很显然，该矩阵是一个稀疏的矩阵，因为它的元素中绝大部分是0。所以，本文采用更高效的链表存储方法存储离散二值边缘图像中的连续边缘，如图2（b）所示，建立一个一维链表结构，该一维链表中，每个元素都指向一条连续边缘，由于图2（a）中只有4条连续边缘，因此，图2（b）中的一维链表只有4个元素。图2（b）中，链表指针指向的一维数组，存储了一条连续边缘的每个像素点（x， y）坐标值。从图2（a）和图2（b）中可明显看出，链表表示的图像边缘所需要的存储空间远远少于矩阵表示的存储空间。

2.2 边缘重映射

边缘像素值重映射的思想是，将图2（a）中的二值边缘图像b（x， y）的边缘像素值重新赋值，将其转换成图2（c）所示的边缘重映射后的图像rm（x， y），其目的是降低搜索删除连续边缘时的时间复杂度。假设存储连续边缘的一维链表为{<1，P1>，<2，P2>，…，}，其中，表示第i条连续边缘，Pi={（xi，1，yi，1），（xi，2，yi，2），…，（xi，ni，yi，ni）}表示第i条连续边缘的边缘像素坐标值。边缘重映射图像rm（x， y）的构造方法为：

for 每一条连续边缘Pi

if （x，y）∈Pi

rm（x，y）=i

end_if

end_for

从图2（c）中的边缘重映射结果可以看出，原始边缘二值图（图2（a））中连续边缘的每个边缘像素点值被重新标记为不同的值，而该值即为所对应的连续边缘存储在一维链表中的位置。通过边缘像素值重映射，可以在常数时间内找到某条边缘的所有边缘像素点坐标在一维链表中的位置，从而有助于快速从连续边缘的一维链表存储空间中找到需要删除的边缘，进而将需要删除的边缘从链表中移去。

3 删除标记线连接与加粗

由于原始图像中存在大量噪声与背景纹理信息，使得自动化的边缘检测结果中存在大量在实际运用中不需要的边缘，需要使用交互式的方式删除。实现交互式删除边缘的思想是：在边缘检测结果上，手动标记出需要删除的边缘，将手动画的删除标记成删除标记线，然后在连续边缘链表结构中搜索被删除标记线标记过的边缘，将其从链表结构中删除。

假设删除标记线为L，L={（x1，y1），（x2，y2），…，（xm，ym）}，其中，（xi，yi）表示删除标记线上像素点的坐标值。为了删除被标记线标记过的边缘，首先，需要提取出删除标记线与图像边缘相交的像素坐标点集，CL={（x1，y1），（x2，y2），…，（xn，yn）}；其次，在边缘的链表存储结构中搜索与相交像素坐标点集CL相交的边缘，即是针对一维链表中的每条连续边缘Pi={（xi，1，yi，1），（xi，2，yi，2），…，（xi，ni，yi，ni）}，计算A=Pi∩CL。如果A不为空集，则将连续边缘Pi从边缘链表结构中删除；否则，保留连续边缘Pi。计算两个集合的交集所需要的循环次数是n·ni，其中n是像素坐标点集CL中的像素个数，ni是连续边缘Pi的像素个数。当图像的连续边缘条数为N时，在整个链表结构中搜索需要删除的边缘的循环次数是n·（n1+n2+…+nN）。通常情况下，手动标记的删除像素点数n很少，在这个循环次数的计算中可以忽略不计，最终的循环次数为n1+n2+…+nN，即是所有边缘的像素点数M。因此，此传统方法的时间复杂度由检测到的边缘像素点数决定，它的时间复杂度为O（M）。

传统的删除边缘算法无法应用于计算资源匮乏的移动平台，特别要求实时计算的应用场合。因此，利用下文的边缘像素重映射，可以将删除算法的时间复杂度降低到常数，即O（1）。

当在移动平台触摸屏上手动画出删除边缘标记线时，由于屏幕本身刷新频率不高与图像离散化，会导致如图3（a）和图3（b）所示的删除标记线间断及删除标记线与需要删除的边缘之间无交点的问题（☆表示手动画出删除标记线的像素点）。本文分别利用线性插值与删除标记线加粗的方法来解决以上两个问题。

3.1 删除标记线线性插值

由于移动平台触摸屏刷新频率较低，通过触摸屏手动画线时，出现图3（a）所示的不连续间断点，导致手动画的删除标记线不连续，本文利用线性插值方法估计出删除标记线中间断点的坐标位置。假设间断点两边删除标记线像素点的坐标分别为（xs，ys）和（xe，ye），估计坐标点（xs，ys）与（xe，ye）之间的坐标点（x， y）方法如下：

if |xe-xs|>|ye-ys|

for x=xs+1 to xe-1 step 1

y=ye-ysxe-xs·（x-xs）

end_for

else

for y=ys+1 toye-1 step 1

x=xe-xsye-ys·（y-ys）

end_for

end_if

利用以上算法估算，图3（a）中间断删除标记坐标如图3（b）中“△”标记所示。通过上述线性插值方法，可获得一条在8邻域内连续的删除标记线。

3.2 删除标记线加粗

手动标记需要删除边缘时，本文假设需要删除的边缘与删除标记线之间有交点。在二维数字图像中，计算两条线之间的交点是通过计算两条线上像素点之间的重合点。由于离散化影响，理论上相交的两条边缘在离散图像中没有交点，如图3（b）中圆圈标记所示，从而降低了算法的鲁棒性。针对这个问题，本文提出的解決方法是将线性插值后的连续删除标记线加粗，然后计算加粗后的删除标记线与边缘之间相交的像素点。实现删除标记线加粗的方法是利用形态学中的膨胀操作，即：DL=L⊕Eendprint

（1） 其中，L为线性插值连接后删除标记线的像素坐标集合，E为3×3的模板，⊕为形态学的膨胀运算。E=（-1，-1）（0，-1）（1，-1）

（-1，0）（0，0）（1，0）

（-1，1）（0，1）（1，1）

（2） 图3（c）给出了对图3（b）中删除标记线采用式（1）进行一次形态学膨胀之后的结果。图3（c）中“▲”为形态学加粗的删除标记线，可以看出，通过对删除标记线加粗，克服了图3（b）中需要被删除图像边缘与手画删除标记之间没有相交像素点的问题，从而有助于增强删除算法的鲁棒性。

3.3 边缘删除快速算法

整个边缘删除算法中最耗时的步骤是，从图像边缘链表结构中搜索被手画删除标记线划过需要被删除的边缘，其随着图像边缘像素点的增加而增加，当图像边缘像素点较多时，传统算法无法实现移动平台的实时处理要求。利用上文的图像边缘重映射结果，直接从边缘重映射图中找到被删除边缘在边缘链表结构中的位置。

假设加粗后删除标记线像素点与图像边缘像素点之间的交集为CL，CL={（x1，y1），（x2，y2），…，（xn，yn）}，边缘重映射图为rm（x， y），存储连续边缘的链表结构为LIST，LIST={<1，P1>，<2，P2>，…，}，快速边缘删除算法如图4所示。

从图4中快速边缘删除算法可以看出，删除边缘算法的循环次数只与加粗后的删除标记线及图像边缘之间的相交像素点数相关。在本文提出的边缘删除算法中，相交像素点数远少于图像边缘像素点数，可以忽略。因此，该算法的时间复杂度与图像边缘像素点数无关，它的时间复杂度是常数，即为O（1）。

4 实验结果

为了验证本文提出的算法，在Android系统手机平台上进行验证。图5给出了两幅图像的实验结果，对于彩色图像，首先将彩色图像转换成灰度图像，然后使用本文提出的算法进行处理。从图5中的实验结果可以看出，通过交互式的方法能有效删除不需要的边缘。由于本文的边缘删除算法具有常数时间复杂度，因此，交互式过程不需要等待，能实时返回删除边缘的结果。

5 结语

本文针对移动平台的实时图像边缘删除任务，提出一种与图像边缘像素点数无关的快速算法。该算法通过对边缘二值图像的边缘像素点进行重映射，降低删除连续边缘的时间复杂度；为了避免发生触摸屏刷新频率低、离散化图像带来手画删除标记线间断，以及删除标记线与需要删除边缘之间交点缺失的情况，对删除标记线进行线性插值与加粗操作，从而增加了算法的鲁棒性。

参考文献：

[1] QING LIU， XIAOPENG HONG， BEIJI ZOU， et. al.. Hierarchical contour closure based holistic salient object detection[J]. IEEE Transactions on Image Processing， 2017，26（9）：4537-4552.

[2] 刘涛，黄席樾，周欣，等.高速公路弯道识别算法[J].重庆大学学报，2003，26（7）：24-27.

[3] 胡智祯，万晋廷，王毓玮.论计算机视觉技术在自动化中的应用[J].南方农机， 2017，48（5）：125.

[4] ZIOU D， TABBONE S. Edge detection techniques-an overview[J]. Pattern Recognition and Image Analysis C/C of Raspoznavaniye Obrazov I Analiz Izobrazhenii， 1998，8：537-559.

[5] PAPARI G， PETKOV N. Edge and line oriented contour detection： state of the art[J]. Image and Vision Computing， 2011，29（2）：79-103.

[6] CANNY J. A computational approach to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986（6）：679-698.

[7] GONZALEZ C I， MELIN P， CASTRO J R， et al. An improved sobel edge detection method based on generalized type-2 fuzzy logic[J]. Soft Computing， 2016，20（2）：773-784.

[8] WANG FU-PING， SHUI PENG-LANG. Noise robust color edge detector using gradient matrix and anisotropic Gaussian directional derivative matrix[J]. Pattern Recognition，2016，52（2）：346-357.

[9] 王富平，水鵬朗.形状自适应各向异性微分滤波器边缘检测算法[J].系统工程与电子技术，2016，38（12）：2876-2883.

[10] 刘杰，朱铮涛，张哲，等.基于机器视觉的在线手机间隙尺寸检测技术研究[J].电脑知识与技术，2017（8）：188-191.

（责任编辑：何 丽）endprint