基于交互式图论的目标边缘检测算法*

林选伟，吴 谨

(武汉科技大学信息科学与工程学院，湖北 武汉 430081)

基于交互式图论的目标边缘检测算法*

林选伟，吴 谨

(武汉科技大学信息科学与工程学院，湖北 武汉 430081)

针对传统边缘检测算法无法准确提取目标及其边缘的问题，基于交互式图论的最大流/最小割理论提出了一种新的边缘检测算法，设计了一种新的代价函数OE_COST--目标边缘代价函数；通过建立图割模型，能够在分割出目标的同时提取出目标边缘。算法通过交互式选择背景及目标像素集合作为硬性约束，通过图像特征(如灰度级、空间信息等)建立代价函数作为软性约束，同时施加软硬约束达到提取目标边缘的目的。实验结果表明，本算法可以准确提取出目标及其边缘轮廓。

边缘检测；交互式；图论；最大流/最小割；代价函数

1 引言

传统的边缘检测算法大多基于图像一阶导数(梯度)、二阶导数及分数阶微分[1]的过零点信息来判断整幅图像的边缘点，为全自动分割。实际应用及数据分析中，需要的往往是感兴趣目标的边缘而不是整幅图像的边缘，因此，一些干扰点或背景的边缘成为无用信息。交互式图论广泛应用于图像处理，如图像分割、计算最小代价问题等,但将交互式图论的算法尤其是基于代价函数的算法应用于图像边缘检测的却很少。

文献[2]针对医学多普勒超声心动图提出了一种基于区域的动态轮廓模型，可以快速地提取出心室的轮廓[2]，鲁棒性强，但对于其他类型数字图像则不适用；文献[3]提出了一种利用非线性偏导的方法，以解决离散的边缘检测问题[3]，其突出优点是用很小的代价并无需归一化便可以得到较高的信噪比，其缺点是无法提取出所需目标；文献[4]对Canny算子进行了调整，模拟了以边缘梯度作为高斯分布结合Canny算子的混合模型[4]，对摄像机3D场景或视频的边缘检测及跟踪有比较理想的效果，但需要已知的3D场景模型；文献[5]提出了新最大流/最小割的算法，并应用于N维(尤其是三维)图像分割[5]，在分割上具有良好效果，但并未涉及边缘检测;文献[6]用图论方法针对人体目标进行检测，能准确提取出含有人物图像的目标[6]，但同样未涉及边缘检测；文献[7]利用小波变换结合传统的检测算子对X射线的医学图像进行边缘检测[7]，效果较理想，但受检测范围的约束；文献[8]提出了一种阈值算法，减少了图割理论的函数代价[8]，能够用较少的计算代价提取出目标，但并未结合边缘检测；文献[9]中结合不同尺度的小波系数提出了一种新的鲁棒、无人监督的边缘检测及增强的算法[9]，针对SAR图像检测效果理想，而对其他类型图像不具有普适性。

本文将最大流/最小割算法应用于目标的边缘检测，结合传统的梯度算子重新设计代价函数(目标边缘代价函数)，通过建立数学模型，将边缘问题转化成数学寻优问题，清楚地描述了要解决的问题。用户手动选取感兴趣区域ROI(Region of Interest)作为种子点进行建模，并选择目标种子点(Object Seeds)集合及背景/干扰种子点(Background Seeds)集合，建模后形成边缘检测的硬性约束；将图像自身的空间特性和灰度特性作为软性约束，本文的软性约束根据步骤的不同分为目标提取时的软性约束和目标轮廓提取时的软性约束，并将这两种软性约束设计为两种代价函数。经过目标提取后，目标的轮廓会依稀可见，此时再对目标进行边缘代价函数建模便可以精确地提取出目标的边缘。

2 边缘检测的Ford-Fulkerson算法

2.1 基础算法

本节将Ford-Fulkerson思想引入到边缘检测，并对其进行改进，其主要内容基于三个定义：残留网络、增广路径和割；主要定理为：最大流等于最小割[10]，定理证明详见文献[10]。

文中用图的顶点为图像的每个像素建模，用图的边对像素灰度及空间关系建模，用边的权值为像素相关性建模。由此，产生两种类型的边：t-links和n-links。t-links表示与源点S及汇点T相连的边；n-links表示普通像素之间的边。

本文对Ford-Fulkerson算法进行了改进，Ford-Fulkerson算法通过计算流网络的最大流得到图像的最小割集，以图中边的权值最小者为单位，向每条边增加流量，直至图中流量无法再增加为止。本文进行了两次最大流的计算，得到两个最小割集，在本文中分别称为：目标割及边缘割。目标割为分割出用户需要的目标集；边缘割为分割出目标的边缘集。其算法流程如图1所示。

Figure 1 Flow chart of Ford-Fulkerson algorithm图1 Ford-Fulkerson算法流图

2.2 简单图像边缘检测实例

本节以人为构建的简单图像为例引出本文的基本算法，如图2步骤：

Figure 2 Edge detection based on graph theory for image图2 图像图论边缘检测

图2a为选种后的原图，O(obj)为目标种子，B(bkg)为背景种子，O(obj)和B(bkg)形成了边缘检测的硬性约束；图2b为经过图论的图像建模，每个像素对应图中的顶点，并增加了两个特殊的虚拟顶点：源点S和汇点T，然后建立了t-links和n-links，其中粗线边代表高能量代价，细线边代表低能量代价；图2c为经过目标割后的图论模型，虚线为目标割的痕迹；图2d为目标割后的图像；图2e为经过边缘割的图论模型，虚线右下方粗线为边缘割的痕迹；图2f为最终的边缘检测图像。

3 代价函数及权值模型

本节将详细介绍本文基于最大流/最小割边缘检测的算法核心：代价函数和权值模型设计。代价函数及权重模型均分为目标提取部分和边缘检测部分的设计，在后续章节中，我们将通过实验分别给出这些中间结果的分析。

3.1 建立图像的图论模型

设用户选取的种子点集合为US，图像剩余像素点集合为M，选择O为目标种子，选择B为背景及干扰种子，使得O和B满足下列条件：

(1)O∩B=∅;

(2)O∪B=US。

根据已存储好的种子点，我们建立图论模型，设n-links集合为En，t-links集合为Et。其中n-links可以按照4邻域、8邻域或m邻域建立[5]，m越大检测越精确，但计算量亦随之提高，本文使用8邻域系统。定义图为G=(V，E)，并人为地设定假想点：源点S及汇点T，使得S和T满足下列条件：

(1)V=Us∪M∪S∪T;

(2)E=En∪Et;

(3)Et={(p,S),(p,T)|p∈(US∪M)}。

这样，我们便将一副图像映射为一个无权图，后续亟待解决的问题便是代价函数和权值的设计。

3.2 代价函数设计

无论是目标提取还是边缘提取，大方向上都可以分为高频(边缘)和低频(平滑区域)，也可以分为目标区域和背景区域。按上述方法，本文设计了二进制双割向量Z=(Z1,Z2,Z3,…,Zi,…,Zn)，Zi对应于图中像素的向量(i为像素在图论模型中的序号)，在目标割中为目标或背景，在边缘割中为边缘或非边缘，因而，沿着Z可以产生一条痕迹(称为“裂痕”更为形象，文中均称为“裂痕”)，该“裂痕”可将目标及边缘提取出来。

通过以上分析，定义目标边缘代价函数OE_COST(Z)：

OE_COST(Z)=α·Obj(Z)+

Bkg(Z)+β·Edge(Z)

(1)

其中，

(2)

(3)

(4)

(5)

其中，Sign(p,q)为符号函数，当Zp≠Zq时，函数取值1；否则函数取值0。Obj(Z)反映目标特性，Bkg(Z)反映背景(许多情况下也包括边界)特性，其取值仅与n-links相关，Edge(Z)反映边缘特性。前两者结合可以产生目标的裂痕，后两者结合产生边缘的裂痕，三者相结合产生最终的边缘检测结果。α≥0和0≤β≤1是相关系数，其取值取决于背景、目标、边缘特性的相关程度，α为目标相关系数，β为边缘相关系数。Objp为像素p对应于已知背景或目标模型(如直方图、频谱图)的强度；Bkg{p,q}一般与p、q之间的距离成反比，反映了局部亮度梯度、拉普拉斯算子、梯度方向等特征；Bdge(Z)以像素偏导的极值反映了图像的边缘信息，位于图像平滑或平坦区域，相邻像素间的变化不大，其梯度趋于0，而在图像的边缘地带，像素灰度变化剧烈，梯度幅值较大，呈现一个尖峰，边缘处为高频连续信号，且在二阶导数处会出现过零点，本文正是利用此特性设计了Edge(Z)。

3.3 权值设计

根据上节的代价函数，本节我们对图G每条边的权值(Weight)进行赋值，从代价函数的角度看，权值也可以作为边的一种代价。因此，利用代价函数设计了如表1所示的权值规则。

Table 1 Weight rules表1 权值(Weight)规则表

表1中，

(6)

Objp(obj)=-lnP(Lp|O)

(7)

Objp(bkg)=-lnP(Lp|B)

(8)

(9)

(10)

其中，H为像素间距离系数，Li表示像素i的灰度级。

实际编程中，我们将优先建立n-links，然后再建立t-links，最后计算最大流并将其转换为最小割，得到所需的“裂痕”。至此，一个完整的图模型便全部构建完成。

4 实验结果

本节结合具体的实验，对本文的算法做最后的诠释。本文实验采用基于STL的C++编程实现，操作系统为Windows7旗舰x86平台，CPU3.20GHz，内存3GB，编译器MicrosoftVisualStudio2010，计算机视觉库OpenCV2.3.1，目标边缘检测数据分析使用MATLABR2008a，实验结果按照算法的编程步骤列出。

实验中，由于具有目标检测，所以摒弃了传统的峰值信噪比(PSNR)评价方法，而改用F值、漏检率、误检率、定位错误等方法对边缘检测效果进行评价，运用先验概率对目标边缘检测效果做进一步分析，实验以整幅图像像素点数为单位1，通过实际测试图像的边缘点集合为标准边缘点，详见表2和表3。

Table 2 Data analysis of edge detection for cells表2 细胞图目标边缘检测数据分析

Table 3 Data analysis of edge detection for Lena表3 Lena图像目标边缘检测数据分析

文中F值即Abdou-Pratt品质因数，F值大小跟边缘检测的精度成正比：

(11)

其中，Na、Nd分别表示实际边缘数和检测到的边缘个数；d表示实际边缘与检测到的边缘的距离，本文使用欧氏距离；A为常系数，本文取A=0.1。

漏检为将图像应该检测出来的边缘遗漏；误检为将本来不是边缘的像素点检测为边缘像素；定位错误为误检与漏检之和。检测方法为在实际边缘图中进行逐边缘逐像素扫描，扫描到边缘遗漏点则将其选入漏检集合，扫描到误检像素则将其选入误检集合。本文对图像边界点进行单独扫描。设漏检点数为n，误检点数为m，边界漏检点数为ne，边界误检点数为me；漏检率为Pn，误检率为Pm，定位错误为P。

(12)

(13)

(14)

上例中，α=65，β=0.32，H=1 020，图3a给出了标准测试图片；图3b为用户选取的种子点，其中，细胞线标记的为目标种子点，细胞周围线标记的为背景及干扰像素种子点；图3c为实验中间结果，提取出了原图中的目标，并剔除了相关背景点，从图3c中可以发现这时细胞的薄薄的轮廓已经依稀可见了(这也是本文算法最初的灵感来源)；图3d和图3e分别为Canny算子和文献[4]算法的效果图，图3f为本文算法最后提取到的目标边缘,可以看出本文算法可以清晰地提取出目标边缘，并且去除了细胞周围的无用杂点，而Canny算子及文献[4]算法对标准图像处理效果相差不大，细胞周围无用杂点依然存在。

Figure 3 Edge detection for cells图3 细胞图边缘检测

表2中本文算法F值高于Canny算子，略低于文献[4]算法，是由部分细胞内部出现一点虚边缘导致的。在误检率、漏检率及定位错误上本文算法都明显低于另外两种算法，准确率较高。

Figure 4 Edge detection for Lena图4 Lena图边缘检测

上例中，α=63，β=0.56，H=1 020；图4a为Lena原始图像，图4b～图4d分别为Canny算子、文献[4]算法、本文算法(原图镜子中的部分同样作为干扰背景点处理)的效果图，可以看出本文算法可以去除原图中镜子及周围栏杆的干扰背景，并准确地将目标边缘提取出来，而前两种算法不能去除干扰像素。

由表3可知，前两种算法F值均低于本文算法，本文算法目标边缘检测的准确度更高。且由于本文算法以硬性约束作为先验知识，所以在误检率、漏检率、定位错误上均低于前两种算法。

5 结束语

本文利用交互式图论的方法成功解决了目标轮廓的提取问题，通过人机交互选点提高了目标提取的准确度。本文设计了新的代价函数，并结合软硬约束为整幅图像建立图论模型，可以精确地提取出目标及其边缘，此算法为本文后续研究视频中目标轮廓提取、跟踪及视觉注意机制目标研究奠定了基础。

[1] Wang Cheng-liang, Lan Li-bin.Imge interpolation algorithm based on edge detection of fractional differential[J].Journal of Beijing Institute of Technology, 2011,32(9):1086-1088.(in Chinese)

[2] Saini K, Dewal M L, Rohit M. A fast region-based active

contour model for boundary detection of echocardiographic images[J].J Digit Imaging, 2012, 25(2):271-278.

[3] Laligant O,Truchetet F. A nonlinear derivative scheme applied to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010,32(2):242-256.

[4] Park H, Mitsumine H, Fujii M. Adaptive edge detection for robust model-based camera tracking[J]. IEEE Transactions on Consumer Electronics,2011,57(4):1465-1470.

[5] Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images[C]∥Proc of International Conference on Computer Vision,2001:105-110.

[6] Li Shi-feng,Lu Hu-chuan.Arbitrary body segmentation with a novel graph cuts-based algorithm[J]. IEEE Signal Processing Letters, 2011,18(12):753-756.

[7] Harish Kumar J R, Chaturvedi A. Edge detection of femur bone-A comparative study[C]∥Proc of 2010 International Conference on Signal and Image Processing,2010:281-284．

[8] Tao Wen-bing, Jin Hai, Zhang Yi-min, et al. Image thresholding using graph cuts[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A:Systems and Humans,2008,38(5):1181-1194.

[9] Alonso M T, López-Martínez C, Mallorquí J J, et al. Edge enhancement algorithm based on the wavelet transform for automatic edge detection in SAR images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2011,49(1):222-234.

[10] Cormen T H, Leiserson C E, Ronald L, et al. Introduction to algorithms[M].Beijing:China Machine Press, 2006:651-660.

附中文参考文献：

[1] 汪成亮,兰利彬. 采用分数阶微分边缘检测的图像插值[J]. 北京理工大学学报，2011,32(9):1086-1088．

LINXuan-wei,born in 1987,MS candidate,his research interest includes multimedia communication.

吴谨(1967-),女,安徽芜湖人，博士，教授，研究方向为图像处理和模式识别。E-mail:wujin1988@163.com

WUJin,born in 1967,PhD,professor,her research interests include image processing, and pattern recognition.

Anoveltargetedgedetectionalgorithmbasedoninteractivegraphtheory

LIN Xuan-wei,WU Jin

(College of Information Science and Engineering,Wuhan University of Science and Technology,Wuhan 430081,China)

As the traditional algorithm for edge detection cannot extract the targets and edges accurately, based on the max-flow/min-cut theory of interactive graph theory, a novel edge detection method is proposed and a new cost-function, named Objects Edge Cost (OE_COST), is designed. The proposed algorithm establishes the graph cut mode to cut the objects and get their edges. The algorithm can extract the edges of targets through combining the hard constraints and soft constraints. The hard constraints can be got by selecting background seeds and object seeds interactively, while the soft constraints are based on the properties of images such as gray levels and space information. Experimental results show that the proposed algorithm can obtain the objects and edges exactly.

edge detection;interactive;graph theory;max-flow/min-cut;cost-functions

1007-130X(2014)08-1571-05

2012-12-04;

：2013-04-03

国家自然科学基金资助项目(60974012,61171160)；湖北省教育厅科研计划项目(Q20131110)；高等学校博士学科点专项科研基金(20124219120002)；武汉科技大学青年科技骨干培养计划项目(2013xz010)；国家级大学生创新创业训练计划项目(201210488062)

TP391.4

：A

10.3969/j.issn.1007-130X.2014.08.026

林选伟(1987-),男,山东栖霞人，硕士生，研究方向为多媒体通讯。E-mail:249438391@qq.com

通信地址：201103 上海市徐汇区宜山路1388号民润大厦1号楼5楼

Address:Floor 5,1 Building,Minrun Mansion,1388 Yishan Rd,Xuhui District,Shanghai 201103,P.R.China