0引言随着社会经济的发展，全世界绝大多数国家都已经进入了一个热火朝天的和平建设发展阶段.其中为了提高国家的基础设施和交通运输的发达水平，世界各国都十分重视公路交通的建设.大量的公路建设给人们带来无限便利的同时，也带了繁重的公路养护的重担.传统的路面检测方法需要人工亲临现场进行检查、勘测、记录，耗费了大量的人力和财力，还影响了交通状况，甚至可能造成人身意外伤亡，采用这种方式进行道路检测效率低下、检测精度差等诸多弊病.随着计算机技术、数字图像技术、多源传感器技术的快速发展，公路路面破损检测正经历从人工检测向自动化检测的转变.但目前的商业化产品仍然需要人工交互来实现从图像中提取路面裂缝，其工作量巨大.因此研究全自动的路面裂缝检测方法也越来越重要.基于图像理解与分析的路面裂缝自动检测, 其研究始于20 世纪90 年代初, 进入21 世纪后受到广泛关注, 多种裂缝检测算法相继被提出.主要可以分为“图像边缘检测”和“图像区域分割”两大类.在早期的路面裂缝检测算法中，一些经典的边缘检测的算法受到国内外学者的关注和研究，例如，刘渝采用一种连通域去噪方法实现光学字符数字的提取［1］ .Li L.等［2］提出了一种基于soble算子的边缘检测方法，Seung-Nam等［3］提出的方法可认为将裂缝提取问题转换成图顶点之间最小代价搜索问题.然而，由于路面表面具有高纹理特征，导致采集到的路面影像具有很强的噪声，使得基于图像边缘检测的方法应用在裂缝检测中具有一定的局限性.在最近几年里，越来越多的研究者将关注点转向了利用“图像区域分割”的方式来提取裂缝.Cheng H. D.［4］ 等提出了一种路面破损模糊分割方法，经差分处理后路面图像像素灰度值的隶属度函数，并利用遗传算法确定该隶属度函数的参数，接着对路面破损图像进行模糊化处理，最后根据破损区域像素连续性的特点，将破损区域像素连接起来得到路面破损图像的分割结果.该方法试验结果较好，但处理时间也较长.李晋惠［5］根据裂缝边缘在各个角度上可能存在梯度，提出了8个方向的模板对图像进行Sobel边缘检测，结合加权的邻域平均噪声滤除算法和最大类间方差法（OTSU）分割算法对裂缝进行分割，裂缝的边缘保护的较好，边缘断续的情况较少.文献［6］中，首先利用直方图分析方法将路面图像中的标线从图像中去除，然后对图像进行二值化处理，采用图像分块的方法，通过对小子块的阈值分割来实现对整体路面图像的二值化.文献［7］利用在路面图像中，裂缝的像素灰度值一般较正常像素点的灰度值要低的特点，并且裂缝像素在平面分布上具有一定的连续性，提出一种图像的新的分割方法:首先给出了经过差分处理后路面病害图像的模糊隶属度，然后对模糊隶属度中的待定参数用遗传算法确定;并进一步对路面图像进行模糊化处理;将路面中的目标利用连续性连接起来，形成完整的边缘目标.基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热点.该方法将图像映射为带权无向图，把像素视作节点，利用最小剪切准则得到图像的最佳分割.该方法本质上将图像分割问题转化为最优化问题，是一种点对聚类方法，对数据聚类也具有很好的应用前景.从实际出发，将这种图论阈值分割算法应用到路面裂缝检测中.第1期闫晖,等：图论在路面裂缝分割中的应用研究
武汉工程大学学报第34卷
1典型的阈值分割1.1NDHM 方法NDHM(Neighboring Difference Histogram Method)［8-9］是由李清泉教授在2008年提出的一种路面裂缝影像阈值分割的方法.该方法针对每一个像素点，统计该点临域内所有像素值与目标像素值之间的差异，如果临域内像素与目标像素之间的差异越大，则目标点越接近裂缝点，该方法的基本原理如下:设目标像素点P(x,y)，其灰度值为 i［1,2,…,L］.设目标点临域像素点的个数为w，以及p(x,y)与临域内像素点差异统计值为ai,p(x,y).则ai,p(x,y)=∑wj=1［pj-p(x,y)］δ(1)其中，δ=pj-p(x,y)∑wj=1|pj-p(x,y)| j∈［1,2,…,w］ 对于一个路面图像，所有灰度值的差异统计值之和为Ai, i∈［1,2,…,L］.则
Ai=∫∫ai,p(x,y)dxdy(2)针对图像数据的离散性特征，图像可以用二维矩阵表示，用X表示图片二维矩阵的行数，Y表示图片二维矩阵的列数.则公式（2）又可表示为Ai=∑Xi=1∑Yy=1ai,p(x,y)(3)其中x∈(1,2,…,X),y∈(1,2,…,Y).NDHM方法提出的最佳分割阈值如下：
t=MaxLi=1Ai（4）     1.2OTSU方法OTSU法即最大类间方差法，是由大津展之［10］最先在1979年提出的一种图像处理方法.该方法是依据判决分析推导出来的，是一种无参数无监督的自动阈值分割法.其基本思想是通过灰度图像的直方图，以目标区域灰度值和背景区域灰度值的方差最大来动态的确定图像分割的阈值［10-11］，它是一种通过一维灰度直方图来进行计算的简单图象分割方法.后来Lee等学者［12］分别通过以形状、错分概率和均匀性度量为准则函数来评估了许多不同阈值分割法的性能，其结果表明，OTSU法是一种直接有效的图像阈值分割方法.它的基本原理如下：设f(x,y)为图像M·N中的点(x,y)的灰度值，其灰度级为L，其中f(x,y)的范围为［0,L-1］，并且记GL={0,1,2,…,L-1}.规定P(i)为f(x,y)中灰度级为P（i）=1M·N ∑f（x，y）=if（x，y）i∈GL出现的频数，那么灰度级i的概率如下式：P(i)=1M·N∑f(x,y)=if(x,y)i∈GL(5)设定图像分割阈值t，那么通过分割阈值t把图像分割为目标区域O和背景区域A两个区域，用{f(x,y)≤t}和{t<f(x,y)<M}来表示，则有如下公式：目标部分比例：ω0(t)=∑0≤i≤tP(i)(6)背景部分比例：ω1(t)=∑t≤i≤MP(i)(7)目标均值：μ0(t)=∑0≤i≤tiP(i)/ω0(t)(8)背景均值：μ1(t)=∑t≤i≤L-1iP(i)/ω1(t)(9)总均值：μ=ω0(t)μ0(t)+ω1(t)μ1(t)(10)那么通过OTSU方法得到图像的最佳分割阈值公式为：Th=argmax［ω0（t）·（μ0(t)-μ）2+
ω1(t)(μ1(t)-μ)2］(11)这样由OTSU方法的公式可知，在目标区域和背景区域的临界处的灰度值的变化最明显，那么这个灰度值即为最佳分割阈值.式（11）中的Th即最大类间方差值.2基于图论的图像分割算法任意特征空间的点集都可以采用一个无向图G(V,E) 来表达,其中V 是节点的集合, E是连接节点的边的集合 连接每两个节点的边均赋予权值w(u,v),该权值衡量节点u 和v的相似程度. 如果将节点集V 分成两个独立的子集A 和B,其中B = V - A,那么通过移去连接A 和B中所有节点的边就可以得到点集A 和B 之间的分离度,称为划分(cut):cut(A,B)=∑u∈A，v∈Bw(u,v)(12)   但是这种方法容易产生出孤立点，为了克服这一缺点.研究者们提出了一个归一化的划分Ncut(Normal cut)［14］.
Ncut(A,B)=cut(A,B)asso(A,V)+cut(A,B)asso(B,V)=
cut(A,B)asso(A,A)+cut(A,B)+
cut(A,B)asso(B,B)+cut(A,B)(13)其中，asso(A,V)=∑u∈A,v∈(A+B)w(u,v)为A中节点与图中所有节点总的权值之和.这种方法较好的解决了划分孤立点的问题. 本文采用Normal cut方法来对路面图像进行分割处理.其基本思想是将图像中的每个像素看作是一个节点，而连接每两个节点的权值反映了这两个像素属于同一类的可能性.权值越大表明两个像素越可能属于同一类.采用基于图像灰度级的对称矩阵M(其大小为256 ×256) 来描述图像中各部分之间的关系, 而不是采用N ×N (其中N 为图中节点的个数)的对称矩阵W，也即将单个像素之间的关系转化为灰度等级之间的关系.而后对每一个可能门限t，利用矩阵M可快速地计算其对应的图谱划分值，其最小的图谱划分值对应的门限即为分割图像的最佳阈值.如果将图像中的每个像素看作一个节点，每对节点均用一条边连接起来, 边的权值反映这两个像素属于相同目标的可能性, 那么就可以构建一个带权的无向图G= (V, E).利用像素的灰度值以及它们的空间位置,可以定义图G 中连接两个节点u 和v 的边的权值如下:
w(u,v)=
e-‖F(u)-F(v)22‖σ21+‖x(u)-x(v)22‖σ21‖x(u)-x(v)‖≤r
0其它（14）其中，σ21为灰度高斯函数的方差 ，σ22为空间距离的方差，分别控制权值w(u,v)对两节点u和v的灰度差异以及空间位置差异的敏感程度. r决定参与计算权值的领域的节点的个数，r=1时，中心点与周围8邻阈计算权值. 对任意门限t (0 < t < 255),能够得到图像对应的图G = (V, E) 的一个二划分V = { A, B}, A和B 可分别表示为A=∪tk=0Vk,B=∪255k=t+1Vk,k∈L(15)那么等式（12）可转换为
cut(A,B)=∑v∈A,v∈Bw(u,v)=∑u∈A［∑v∈Bw(u,v)］=
∑u∈A∑255j=t+1∑v=vjw(u,v)=
∑ti=0∑u=ui∑255j=t+1∑v=vjw(u,v)=∑ti=0∑255j=t+1∑u=ui∑v=vjw(u,v)
令M 为256 ×256 的对称矩阵， mi,j = cut (Vi,Vj ) 为其( i, j) 处的元素且有mi,j = mj,i.给定一幅图像，通过计算图中所有节点间的权值就可以构建基于灰度级的权值矩阵M.矩阵M = ［ mi,j］256 ×256 如图1 所示.图1对称矩阵M=［ mi,j］256 ×256
的示意图,其中mi,j = mj,iFig.1Schematic diagram of symmetric matrix
M = ［ mi,j］ 256 ×256, mi,j= mj,i定义S1为矩阵M中区域1中的元素之和，S2为矩阵M中区域2中的元素之和,S3为矩阵M中区域3中的元素之和.显然有，S1 = asso(A,A) ， S2=asso(B,B)，S3 = asso(A,B).则Ncut(A,B)=S2S1+S3+S3S2+S3 而且矩阵M  的大小固定为256 ×256 ，与图像的大小无关，而矩阵W  的维数则为N ×N ，其中N 为图像中像素的个数. 显然采用矩阵M  使所需的存储空间得到了极大的减少.3实验结果对比与分析本文实验影像均由CCD相机拍摄的路面图片裁剪得到，图片尺寸大小为512*512像素，且都经过了预处理，如几何校正、均光、直方图均衡化等..本文算法程序基于VS2008 开发, 运行环境为Windows XP, CPU Inter Pentium( R) 2.5 GHz,RAM 2G.实验目的是测试本文方法在检测裂缝时的性能, 并和传统方法( OTSU和NDHM方法) 进行比较.图2中显示了4幅典型路面裂缝影像，以及分别用3种算法进行处理后的结果.图2裂缝提取实现Fig.2Implement of extracting crack图2中的4幅路面裂缝图片，采用相同的预处理方式进行前期的预处理，然后将他们分别用OTSU、NDHM、graph-cut进行分割.为了对裂缝提取效果进行量化分析和评价，本文引入完成度指数 和正确度指数 ［14-15］ .完成度指数用于描述完成裂缝提取这一任务的完成程度，正确度指数则描述完成任务的质量水平.其定义见式(16) 和式(17) .另外，为了对算法的时间效率进行分析，实验记录了算法的运行时间.IndexcptLrLgt(16)IndexcrtLrLN(17)
式(16)中，Lr代表提取结果是真实裂缝的长度；Lgt代表裂缝的实际长度. 通过实地测量和手工编辑得到；LN代表提取结果的总长度.表1裂缝提取结果评价Table 1Evaluation of results of extracting crack
影像编号OTSU完成度正确度NDHM完成度正确度Graph\|cut完成度正确度a0.5760.4120.7440.6080.9050.871b0.4550.4790.6760.5380.8230.790c0.4610.3480.6110.6420.6970.656d0.3920.3230.7110.7330.9330.867

表2算法效率评价
Table 2Evaluation of algorithm efficiency
影像编号算法时间/msOTSUNDHMGraph-cuta64203328b62214344c63208337d632103404结语通过表1和表2的实验结果评价，可以看出在裂缝提取的完成度和正确度方面Graph-cut比OTSU和NDHM算法优越，Graph-cut完全将裂缝分割出来，背景只含有少量的与裂缝相似的像素点，而其它两种方法则背景存在大量与裂缝相似的像素点.因此在路面裂缝分割上，Graph-cut比OTSU和NDHM具有明显的优越性.然而在算法效率方面Graph-cut存在不足，其算法时间复杂度要比其它两种算法的要高.对于算法时间复杂度将在下一步研究中改进.