一种改进的图谱阈值分割算法

　　摘 要：针对图像分割是典型的结构不良问题，将图谱划分理论作为一种新型的模式分析工具应用到图像分割并引起广大学者关注。考虑到现有的图谱阈值法中图权计算方法采用基于欧氏距离的幂指数函数导致其计算量过大的不足，首先采用基于欧氏距离的分式型柯西函数代替基于欧氏距离的幂指数函数提出图权计算的新方法，其次将其应用基于图谱划分测度的图像阈值分割算法中并得到一种改进的图谱阈值分割方法。实验结果表明，该方法的计算量小且对目标和背景相差比例较大的图像能获得满意的结果。
　　关键词：图像分割；阈值法；图谱测度；图权
　　中图分类号：TP391 文献标识码：B 文章编号：1004373X(2008)1612505
　　
　　Improved Segmentation Algorithm Based on Graph Spectral Threshold
　　TIAN Xiaoping,WU Chengmao
　　(Xi′an Institute of Posts and Telecommunications,Xi′an,710121,China)
　　Abstract：Aiming at the problem of image segmentation with badness structure,the graph cut measure theory is a kind of new type tool of pattern analysis,and it has been applied in the image segmentation field and brings the attention of a lot of scholars.Considering the shortage of graph spectral thresholding method with a great deal of computation because of graph weight computation method adopting power exponential function based on Euclidean distance,the new computation method of graph weights are proposed by mean of replacing power exponential function with fractional Cauchy function based on Euclidean distance,and there are applied in the image thresholding segmentation algorithm based on the measure of graph spectral.The experimental results show that the new method has a small deal of computation and is more suitable to segment the image with the bigger proportition between goal and background.
　　Keywords：image segmentation;thresholding method;measure of graph spectral;graph weight
　　
　　1 引 言
　　
　　图像分割是图像处理和前期视觉中的基本技术，是大多数图像分析及视觉系统的重要组成部分，也是成功进行图像分析、理解与描述的关键步骤，历来受到国内外有关学者的高度重视。
　　在很多图像处理应用中，图像中目标和背景灰度值的差异使得采用某一合理的门限值可有效地将目标和背景区分开。事实上，由于阈值分割方法实现简单、实时性好，在许多图像处理问题中均得到广泛应用，如文档处理、细胞运动估计以及自动目标识别等，阈值分割的基本原理是通过将图像中的每个像素与某一门限值进行比较从而将图像区分为背景和目标，其关键问题在于寻找一个合适的门限值来区分目标和背景而且不损害目标的完整性，但是自动选择最佳阈值一直都是图像处理中的一个悬而未解的问题，虽然近几十年来各种方法不断出现^［15］，但根本问题仍未解决，应用各种新的思想和理论来解决这一难题仍然是一个具有挑战性的研究领域。
　　近年来，图谱划分理论作为一种新型的工具被应用到图像分割^［69］，但这种图像分割方法通常具有较高的复杂性，实时性较差，因而在很多实时视觉处理场合无法采用。针对图像划分的图像分割方法存在的不足，文献［10］提出一种基于图谱划分的阈值分割方法，采用图谱划分测度作为阈值分割的准则来区分目标和背景。该方法的最大优点是避免了复杂的特征系统求解问题，因而极大减少了算法所需的存储空间以及计算的复杂度，大大提高了算法的实时性；同时，该方法的性能优于其他类型的阈值分割方法，特别是针对具有明显目标和背景的实际图像，文献［10］中的方法相对文献［8］中的方法更为有效。本文针对文献［10］提出的图谱阈值法在计算图顶点之间的边权值采用指数函数导致其计算量很大且对有些图像无法获得满意分割效果的不足，提出了采用距离倒数的计算方式能降低其计算复杂性，以及对目标和背景比例相差很大的图像获得更加满意的分割效果。
　　
　　2 基于图谱理论的图像分割方法
　　
　　任意特征空间的点集都可以采用一个无向图G=(V,E)来表示，其中V是节点的集合；E是连接节点的边的集合。V的基为N=|V|，连接每2个节点的边均赋予权值w(u,v)，该权值衡量节点u和v的相似程度。如果将节点集V分成两个独立的子集A和B，其中B=V-A，那么通过移去连接A和B中所有节点的边就可以得到点集A和B之间的分离度，称为划分(cut)^［6］:cut(A,B)=∑u∈A∑v∈Bw(u,v)(1) Wu和Leahy^［6］基于最小划分准则提出一种聚类方法,但是该方法容易划分出图中孤立点。为了克服这种现象，Shi和Malik^［8］提出采用归一化的划分准则来描述两类间的分离度,定义如下:Ncut(A,B)=cut(A,B)asso(A,V)+cut(A,B)assov(B,V)(2)其中，asso(A,V)=∑u∈A∑v∈Vw(u,v)为A中的节点与图中所有节点总的连接权值之和。采用Ncut准则就可以克服划分孤立点的问题，最小的Ncut值对应的划分即为图G的最优划分。在这种情况下，最小化Ncut可以转化为如下的标准特征系统^［8］：D.-12(D-W)D.-12z=λz(3)其中，D是N×N的对角矩阵，其对角线上的元素为di=∑jw(i,j)，W是对称矩阵，其元素为w(i,j)，λ和z分别为相应的特征值和特征矢量。
　　特征系统(3)的第二个最小的特征值对应的特征矢量可以用来完成全图的最优划分^［8］，从而得到对应图像的一个分割结果。可以采用递归算法以相同的方式进一步对分割得到的子图进行划分，直至满足终止条件为止。由于计算特征值和特征矢量十分耗时，一般采用近似的Lanczos方法来求解。
　　
　　当图像的尺度较大时，采用Ncut方法其对应的邻接权值矩阵W的维数也相应较大。如果采用基于像素的邻接权值矩阵，则必须求解一个如式(3)的N×N维的特征系统，即使采用近似算法来优化实现，对于大尺度的图像而言其计算复杂性仍然非常高。而且划分的稳定性极大地依赖于参数的选择。另外，特征系统的次小特征值一般非常小，所以特征值计算的微小误差也会对相应特征矢量划分点的选择造成影响，从而影响分割的结果。所有的这些因素都限制了Ncut方法的应用。
　　
　　3 基于图谱测度的阈值法
　　
　　设P=\M×N表示大小为M×N的数字图像,其灰度级为L，K={0,1,…,L-1}表示所有灰度的集合，f(x,y)∈K是图像任意位置(x,y)处的像素。将图像P中的每个位置(x,y)(i=1,2,…,M;j=1,2,…,N)看成无向图G的节点，则V和(x,y)满足如下条件：
　　f(x,y)∈K，(x,y)∈V={(i,j)|i=1,2,…,M;
　　j=1,2,…,N}
　　Vi={(x,y)|f(x,y)=i,(x,y)∈V}
　　i=0,1,…,L-1
　　∪L-1i=0Vi=V，Vj∩Vk=Φ, j,k∈K
　　将图像P中的每个位置看作无向图的一个节点，每对节点均用一条边连接起来，边的权值反映这两个位置所对应的像素属于相同目标的可能性，那么就可以构建一个带权的无向图G=(V,E)，可以定义图G中连接2个节点u=(x1,y1)和v=(x2,y2)的边的权值如下： w(u,v)=e.-‖X(u)-X(v)‖.22dX+‖F(u)-F(v)‖.22dL〗, ‖X(u)-X(v)‖2　　0，其他(4) 其中,X(u)为节点u在图像P中的位置坐标(x1,y1)；F(u)为节点u在图像P中位置坐标(x1,y1)的灰度值f(x1,y1)；‖·‖2表示一个矢量的二范数。
　　另外，dL和dX分别是正的尺度因子，分别控制权值w(u,v)对2个节点u和v的灰度差异及空间位置差异的敏感程度。
　　r是一个正数，决定参与计算权值的邻域节点的个数，随着r的增加，参与计算权值的节点个数也增加，同时计算量也相应地增大。因此，可将w(u,v)具体展开写成如下形式： w(u,v)=e.-(x1-x2).2+(y1-y2).2dX+(f(x1,y1)-f(x2,y2)).2dL〗， (x1-x2).2+(y1-y2).2　　0，其他(5) 假设图像中只有一个目标和背景，阈值化图像分割只需要选取一个阈值，对图像选取某一给定阈值t(0　　=∑ti=0 ∑L-1j=t+1 ∑u∈Vi ∑v∈Vjw(u,v) 同样可得:asso(A,V)=∑ti=0∑L-1j=0∑u∈Vi ∑v∈Vjw(u,v)
　　asso(B,V)=∑L-1i=t+1∑L-1j=0∑u∈Vi∑v∈Vjw(u,v) 因此，基于归一化的图谱划分测度的图像阈值化分割准则可表示为:t.*1(dX,dL,r)=argmin0　　
　　4 改进图谱边权的阈值法
　　
　　针对图谱阈值法中图顶点之间的边权计算公式(4)或(5)因采用幂指数运算，导致给定图像构造其图顶点之间边权的计算量很大,其原因在于计算e.-x是采用下列近似公式:e.-x1-x+x.22!-x.33!+…+(-x).nn!这就导致直接利用指数函数其计算量。因此，本文采用如下的计算办法来降低其计算量：
　　给定大小为M×N的灰度图像P，构建一个带权的无向图G.*=(V.*,E.*)，可以定义图G.*中连接两个节点u=(x1,y1)和v=(x2,y2)的边的权值如下：
　　w.*(u,v)=1/1+α.*‖X(u)-X(v)‖.22d.*X+‖F(u)-F(v)‖.22d.*L〗, ‖X(u)-X(v)‖2　　0，其他(7)
　　其中,α.*>0，X(u)为节点u在图像P中的位置坐标(x1,y1)；F(u)为节点u在图像P中位置坐标(x1,y1)的灰度值f(x1,y1)；‖·‖2表示一个矢量的二范数。另外，d.*L和d.*X分别是正的尺度因子，分别控制权值w.*(u,v)对2个节点u和v的灰度差异及空间位置差异的敏感程度。
　　r.*是一个正数，决定参与计算权值的邻域节点的个数，随着r.*的增加，参与计算权值的节点个数也增加，同时计算量也相应地增大。因此，可将w.*(u,v)具体展开写成如下形式：
　　w.*(u,v)=11+α.*(x1-x2).2+(y1-y2).2d.*X+(f(x1,y1)-f(x2,y2)).2d.*L〗,(x1-x2).2+(y1-y2).2　　0，其他(8) 因此,基于图顶点边权计算的新公式来构造图谱分割新方法为:t.*2(α,d.*X,d.*L,r.*)=argmin0　　为了验证本文方法的有效性，采用本文方法对3幅图片进行分割实验，算法采用Matlab语言实现。在实验过程中，为了客观地比较算法的性能，在文献［8］方法和本文方法涉及到构造图节点的边权值表达式中的参数均采用文献［10］中的设置为dX=d.*X=4，dL=d.*L=625以及r=r.*=2，以及参数α.*针对不同图片选取大于零的值。本文方法与文献［8］方法所需时间差异仅在于计算图谱权值所利用函数不同导致的，其具体差异值大小也与图像的大小有紧密关系。
　　图1 辣椒图片及两种权方法的分割结果本文方法比文献［10］方法要少，CPU时间
　　0.250 0 s。
　　图2 摄影师图片及两种权方法的分割结果本文方法比文献［10］方法要少，CPU时间
　　0.078 1 s。
　　图3 Lena图片及两种权方法的分割结果本文方法比文献［10］方法，要少CPU时间
　　0.078 1 s。
　　从图1~图3的典型标准图片的实验结果来看，本文方法和文献［10］方法的分割效果基本一致，说明本文方法是可行的；但是，从图4~图7的小目标图片的分割结果来看，当图像中的目标和背景比例相差比较悬殊时，本文所建议的图权计算方法就显得更有效。
　　
　　图4 坦克图片及两种权方法的分割结果本文方法比文献［10］方法要少，CPU时间
　　0.312 5 s。
　　图5 沙漠图片及两种权方法的分割结果本文方法比文献［10］方法要少，CPU时间
　　0.328 1 s。
　　图6 沙漠图片及两种权方法的分割结果本文方法比文献［10］方法少，CPU时间0.328 1 s。
　　图7 细菌图片及两种权方法的分割结果本文方法比文献［10］方法少，CPU时间0.031 3 s。
　　
　　6 结 语
　　
　　面对图像来源千差万别，其直方图分布具有多样性。本文对崭新的图谱分割方法中的图权计算函数进行改进，使其图谱分割方法的时间消耗降低，同时其分割性能有所改善，特别是对图像中目标和背景比例相差比较悬殊的图像，本文方法表现出更好的性能。本文不足之处在于图权计算函数参数选择还不能自动选取，这是更进一步要探讨的重要问题。
　　
　　参 考 文 献
　　［1］Sahoo P K.A Survey of Thresholding Techniques Computer Vision\.Graphics and Image Processing,1988,41:233260.
　　［2］Pal N R,Pal S K.A Review on Image Segmentation Techniques\.Pattern Recognition Letters,1993,26(9):1 2771 294.
　　［3］Glasbey C A.An Analysis of Histogrambased Thresholding Algorithm\.Graphical Models and Image Processing,1993,55:532537.
　　［4］Sezgin M,Sankur B.Survey over Image Thresholding Techniques and Quantitative Performance Evaluation\.Journal of Electronic Image,2004,13(1):145165.
　　［5］Saha P K,Udupa J.Optimum Image Thresholding via Class Uncertainty and Region Homogeneity\.IEEE Transactions on Pattern Analysis Machine Intelligence,2001,23(7):689706.
　　［6］Wu Z Y,Leahy R.An Optimal Graph Theories Approach to Data Clustering:Theory and Its Application to Image Segmentation\.IEEE Transations on Pattern Analysis and Machine Intelligence,1993,15(11):1 1011 113.
　　［7］Sarkar S,Soundararajan P.Supervised Learning of Large Percetual Organization: Graph Spectral Partitioning and Learning Automata\.IEEE Transations on Pattern Analysis and Machine Intelligence,2000,22(5):504525.
　　［8］Shi J,Malik J.Normalized Cuts and Image Segmentation\.IEEE Transations on Pattern Analysis and Machine Intelligence,2000,22(8):888905.
　　［9］Wang S,Siskind J M.Image Segmentation with Ratio Cut\.IEEE Transations on Pattern Recognition and Machine Intelligence,2003,25(6):675690.
　　［10］陶文兵,金海.一种新的基于图谱理论的图像阈值分割方法\.计算机学报,2007,30(1):110119.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文