摘  要：提出了基于边缘提取的交互式图像分割算法，该算法将图像映射为无向图，使用拉普拉斯零交叉点、边缘强度和动态轨迹长度构造能量模型，并为无向图中的边赋予能量代价。根据能量代价，引入角点信息，在交互得到的控制点间搜索最优路径，迭代此过程，实现分割。实验结果表明，该算法具有较高的精度和效率，能较好地克服噪声影响，适用于灰度及彩色图像。
关键词： 图像分割; 交互; 边缘; 能量模型

    图像分割是依据图像的某种属性特征将图像分成若干区域，并在这些区域中提取出感兴趣的物或景的技术和过程，这些特征既可以是图像的固有属性特征，也可以是在空间频域中构造的特征(如灰度值、边缘轮廓、颜色和纹理等)。图像分割是从图像处理到图像解析的关键步骤。手动分割过于繁琐，需要消耗大量的人力与时间；自动分割常基于图像的某种特性进行分割，在实际应用中，由于需求的不同，感兴趣的目标也不尽相同，自动图像分割很难有效分割；与前两者相比，交互式分割综合了两者的优点，在人的干预下能准确高效地分割图像，得到广泛重视。
    对于图像分割技术的研究，其代表性工作包括：基于特征聚类的方法[1-2]、基于边缘检测的方法[3-4]和基于图切的分割方法[5]等。上述方法中，未能充分借助交互所提供的信息,并且过多依靠图像边缘特征进行分割，使算法执行效率低，鲁棒性差，分割效果不理想。为保证分割效果准确的同时提高图像分割的效率，本文提出一种基于边缘提取的交互式分割算法。首先,将全局范围的搜索精简到局部范围，减少搜索节点的数目，提高了算法的执行效率；其次,引入图像的角点特征，以应对弯曲度显著变化的边缘；最后,引入动态轨迹长度，克服伪轮廓的干扰并且可以平滑所得到的边缘。
1 基于边缘提取的交互式图像分割算法
    通过在目标区域边缘附近移动鼠标得到控制点信息后，构造能量模型，并将二维图像映射到无向图。其中，像素点被映射为无向图中的节点，像素点与其8邻域内的点均构成一条边，根据能量模型，每条边被赋予一个能量代价。在无向图上，使用Dljkstra’s的最优路径算法求得控制点间的最优路径。迭代上述过程，最终实现分割。其中，能量模型包括拉普拉斯零交叉点、边缘强度和动态轨迹长度3部分。
1.1 交互方式
    交互式的分割方法需要利用用户实时提供的“准边缘”信息，在二维图上迭代计算最优路径，并且在满足算法收敛条件时锁定轨迹路线，直至分割完成。“准边缘”信息由用户鼠标在目标区域边缘附近游走提供，并且可以控制轨迹的锁定。算法执行过程中可根据收敛条件进行轨迹路线的锁定，但对于复杂图像或含有大量噪声的图像，借助用户控制锁定轨迹则更为准确。

1.3 最优路径搜索
    在基于图论的交互式分割方法中，用户实时地提供控制点，算法针对整幅图像在两控制点间搜索最优路径。搜索的效率受图像的大小影响，因此，算法在处理大图像时运算效率降低。但是，由于交互的作用，两控制点间存在着空间上的相互联系，借助这种关系可以将整幅图从全局搜索缩小至两控制点某范围尺寸内局部搜索。局部图的建立是根据p、q(p、q为两控制点,其中p为前点、q为后点）两点的坐标确定的。其计算方法如下。
 
　基于对搜索范围以及搜索方向的控制，使得算法在执行效率上得到提高。搜索过程如图1所示。其中，左上部分为初始图，右上部分为搜索结果图，箭头线连接经过的边缘节点。下侧为搜索执行前3步的结果，圆圈区域为搜索经过的节点，深色区域为扩展的节点。图1上侧居中部分表示搜索方向控制图，其中p为起始点，q为终止点，根据q点位置确定扩展的节点：若q在A区，扩展节点1、2、3；若q在B区，扩展节点3、4、5；若q在C区，扩展节点5、6、7；若q在D区，扩展节点7、8、1。若q在a线，扩展节点2、3、4；若q在b线，扩展节点4、5、6；若q在c线，扩展节点6、7、8；若q在d线，则扩展节点1、2、8。
1.4 角点信息
    “角点”是稳定的图像边缘信息。引入图像的角点特征可以更加准确定位图像的边缘。借助角点的稳定性可以消除伪轮廓的干扰，提高抗噪能力。
    Harris角点[6]定义的基础是图像灰度强度的二阶导数(?坠2x，?坠2y，?坠x?坠y)矩阵。对于图像中的所有像素点，其二阶导数形成Hessian图像。此术语源自于一个点的二维Hessian矩阵如式(10)定义:
　   
　    Harris算法取以目标像素点为中心的小窗口，将窗口沿任意方向移动并计算窗口内灰度的变化，取其中最小值为该目标像素点的角点响应函数值，若该值大于阈值，则为角点。对于Harris角点，使用每点周围小窗口的二阶导数图像的自相关矩阵，此矩阵定义为：
    
其中，ωi,j是可以归一化的权重比例。Harris定义的角点能定位周围存在多个方向的边缘或纹理的点。矩阵H(p)的行列式值和H(p)的迹(带权重系数)这两个特征值中，若较小的一个大于最小阈值，则得到角点。将整幅图像中的角点保存起来，当动态规划时，将当前点与所有角点进行匹配，若在一定范围内匹配成功，则当前点定位至角点位置。由起点到当前点采用动态规划的算法获得路径，并进行锁定。
1.5 算法流程
    首先，载入图像对原始图像进行预处理，得到算法执行中所需特征值：灰度图像Ig、梯度图像Id、拉普拉斯算子卷积图Il以及图像的角点序列。然后，根据算法中所需特征值，采用Dljkstra’s的动态规划最优路径的算法，搜索用户输入的起始点与终止点间的最优路径，这条路径即为所求边缘。动态路径规划算法如下。
　    数据结构：
　    S               {起始点}
　    E               {终止点}
　    Cost(p,q)        {p、q两点间的权值代价}
　    List             {已扩展节点链表}
　　Map            {图像节点扩展标记矩阵}
　    N(p)            {p点的相邻节点（已精简）}
　    T(p)            {从S点到p点的累积权值代价}
　    输出：
　    O                {保存搜索路径上的节点}
　    算法：
　        T(S)=0; Insert(S,List) {初始化链表，压入S点}
　        While (List)      {仍然有可扩展的节点}
　        P=First(List);  {取权值代价最小的节点}
　　        Map(P)=1；   {标记已扩展节点}
　        Get N(S,E,P);  {求与P相邻的节点}
　        For each q in N(p) and Map(q)=0 do begin
　            C=T(p)+Cost(p,q);  {计算累积代价}
　            If q in List and C<T(q)
　                Delete(List, q);   {删除高代价节点}
　            If q in List then begin
　                T(q)=C;     {设定权值}
　                Path(q);     {添加q到S的路径}
　                Insert(q,List);
　            End
　        End
　    End
2 实验结果
　    实验结果如图2所示。其中，原始图像lenna图是一幅具有光照干扰的彩色图，并且所分割区域在视觉角度上像素值相差较小。在canny算子图像中可以看到所分割区域边界存在干扰，尤其是在光照部分产生了伪轮廓。而本算法则克服了干扰，取得了比较准确的效果。

    对于数据库中的图像选择人物、动物、交通工具、家电和陈设物品5类进行对比分析，每类选取30张图像。实验中分别采用人工标记、分水岭、二维图动态切分方法以及本文算法对上述5类图像集进行分割，其平均准确率如表1所示。

    由于交互式分割方法受人为交互作用的影响较大，进行算法对比分析比较困难，实验中尽可能保证所提供交互信息相同。从实验数据可以看出，本算法准确率高于其他3种方法，并且在实际中，随着提供交互信息可靠性的提高，准确率也会随之提高。
    虽然二维图动态切分算法在图像分割中有较好的结果，但由于该算法最优路径搜索基于全图扩展，使得算法在应对大图像时出现执行效率低的缺点，并且难以应对边缘弯曲度较大的区域。本文针对以上不足，在最优路径搜索中对搜索区域的范围及方向进行了控制，并且引入了图像的角点信息和动态轨迹长度，提高了算法的执行效率以及鲁棒性,并通过实验验证了算法的有效性。
参考文献
[1] Li Chunming, Xu Chenyang, Gui Changfeng,et al. Distance  regularized level set evolution and its application to image segmentation [J]. IEEE Transactions on Image Processing, 2010,19(12):3243-3254.
[2] NUZHNAYA T, Cheng Erkang, Ling Haibin,et al.Segmentation of anatomical branching structures based on texture  features and graph cut [C]. IEEE International Symposium  on Biomedical Imaging: From Nano to Macro, Chicago, 2011: 673-676.
[3] Wang Hongrui, Yang Jianli, Sun Haijun, et al. An improved region growing method for medical image selection and evaluation based on canny edge detection[C]. International Conference on Management and Service Science, Wuhan, 2011:1-4.
[4] KHAN N M,RAAHEMIFAR K. A novel accelerated greedy  snake algorithm for active contours[C]. Canadian Conference on Electrical and Computer Engineering,Niagara Falls,2011:186-190.
[5] Zheng Shuxian,Li Jia,Sun Qingfeng.Extraction of the borderline in prepared tooth cavity based on intelligent scissors[C].International Conference on Bioinformatics and Biomedical Engineering, Shanghai, 2008:680-683.
[6] HARRIS C, STEPHENS M. A combined corner and edge detector[C]. Proceedings of the 4th Alvey Vision Conference, Manchester, 1988:147-151.