图论在路面裂缝分割中的应用研究

闫 晖，鲁统伟

(1．武汉工程大学计算机科学与工程学院，湖北 武汉 430074；2．智能机器人湖北省重点实验室，湖北 武汉 430074)

0 引 言

随着社会经济的发展，全世界绝大多数国家都已经进入了一个热火朝天的和平建设发展阶段.其中为了提高国家的基础设施和交通运输的发达水平，世界各国都十分重视公路交通的建设.大量的公路建设给人们带来无限便利的同时，也带了繁重的公路养护的重担.传统的路面检测方法需要人工亲临现场进行检查、勘测、记录，耗费了大量的人力和财力，还影响了交通状况，甚至可能造成人身意外伤亡，采用这种方式进行道路检测效率低下、检测精度差等诸多弊病.随着计算机技术、数字图像技术、多源传感器技术的快速发展，公路路面破损检测正经历从人工检测向自动化检测的转变.但目前的商业化产品仍然需要人工交互来实现从图像中提取路面裂缝，其工作量巨大.因此研究全自动的路面裂缝检测方法也越来越重要.

基于图像理解与分析的路面裂缝自动检测, 其研究始于20 世纪90 年代初, 进入21 世纪后受到广泛关注, 多种裂缝检测算法相继被提出.主要可以分为“图像边缘检测”和“图像区域分割”两大类.在早期的路面裂缝检测算法中，一些经典的边缘检测的算法受到国内外学者的关注和研究，例如，刘渝采用一种连通域去噪方法实现光学字符数字的提取[1].Li L.等[2]提出了一种基于soble算子的边缘检测方法，Seung-Nam等[3]提出的方法可认为将裂缝提取问题转换成图顶点之间最小代价搜索问题.然而，由于路面表面具有高纹理特征，导致采集到的路面影像具有很强的噪声，使得基于图像边缘检测的方法应用在裂缝检测中具有一定的局限性.在最近几年里，越来越多的研究者将关注点转向了利用“图像区域分割”的方式来提取裂缝.Cheng H. D.[4]等提出了一种路面破损模糊分割方法，经差分处理后路面图像像素灰度值的隶属度函数，并利用遗传算法确定该隶属度函数的参数，接着对路面破损图像进行模糊化处理，最后根据破损区域像素连续性的特点，将破损区域像素连接起来得到路面破损图像的分割结果.该方法试验结果较好，但处理时间也较长.李晋惠[5]根据裂缝边缘在各个角度上可能存在梯度，提出了8个方向的模板对图像进行Sobel边缘检测，结合加权的邻域平均噪声滤除算法和最大类间方差法(OTSU)分割算法对裂缝进行分割，裂缝的边缘保护的较好，边缘断续的情况较少.文献[6]中，首先利用直方图分析方法将路面图像中的标线从图像中去除，然后对图像进行二值化处理，采用图像分块的方法，通过对小子块的阈值分割来实现对整体路面图像的二值化.文献[7]利用在路面图像中，裂缝的像素灰度值一般较正常像素点的灰度值要低的特点，并且裂缝像素在平面分布上具有一定的连续性，提出一种图像的新的分割方法:首先给出了经过差分处理后路面病害图像的模糊隶属度，然后对模糊隶属度中的待定参数用遗传算法确定;并进一步对路面图像进行模糊化处理;将路面中的目标利用连续性连接起来，形成完整的边缘目标.

基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热点.该方法将图像映射为带权无向图，把像素视作节点，利用最小剪切准则得到图像的最佳分割.该方法本质上将图像分割问题转化为最优化问题，是一种点对聚类方法，对数据聚类也具有很好的应用前景.

从实际出发，将这种图论阈值分割算法应用到路面裂缝检测中.

1 典型的阈值分割

1.1 NDHM 方法

NDHM(Neighboring Difference Histogram Method)[8-9]是由李清泉教授在2008年提出的一种路面裂缝影像阈值分割的方法.该方法针对每一个像素点，统计该点临域内所有像素值与目标像素值之间的差异，如果临域内像素与目标像素之间的差异越大，则目标点越接近裂缝点，该方法的基本原理如下:

设目标像素点P(x,y)，其灰度值为i[1,2,…,L].设目标点临域像素点的个数为w，以及p(x,y)与临域内像素点差异统计值为ai,p(x,y).

(1)

对于一个路面图像，所有灰度值的差异统计值之和为Ai,i∈[1,2,…,L].则

(2)

针对图像数据的离散性特征，图像可以用二维矩阵表示，用X表示图片二维矩阵的行数，Y表示图片二维矩阵的列数.则公式(2)又可表示为

(3)

其中x∈(1,2,…,X),y∈(1,2,…,Y).

NDHM方法提出的最佳分割阈值如下：

(4)

1.2 OTSU方法

OTSU法即最大类间方差法，是由大津展之[10]最先在1979年提出的一种图像处理方法.该方法是依据判决分析推导出来的，是一种无参数无监督的自动阈值分割法.其基本思想是通过灰度图像的直方图，以目标区域灰度值和背景区域灰度值的方差最大来动态的确定图像分割的阈值[10-11]，它是一种通过一维灰度直方图来进行计算的简单图象分割方法.后来Lee等学者[12]分别通过以形状、错分概率和均匀性度量为准则函数来评估了许多不同阈值分割法的性能，其结果表明，OTSU法是一种直接有效的图像阈值分割方法.它的基本原理如下：

(5)

设定图像分割阈值t，那么通过分割阈值t把图像分割为目标区域O和背景区域A两个区域，用{f(x,y)≤t}和{t

目标部分比例：

(6)

背景部分比例：

(7)

目标均值：

(8)

背景均值：

(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):

(12)

但是这种方法容易产生出孤立点，为了克服这一缺点.研究者们提出了一个归一化的划分Ncut(Normal cut)[14].

(13)

本文采用Normal cut方法来对路面图像进行分割处理.其基本思想是将图像中的每个像素看作是一个节点，而连接每两个节点的权值反映了这两个像素属于同一类的可能性.权值越大表明两个像素越可能属于同一类.采用基于图像灰度级的对称矩阵M(其大小为256 ×256) 来描述图像中各部分之间的关系, 而不是采用N×N(其中N为图中节点的个数)的对称矩阵W，也即将单个像素之间的关系转化为灰度等级之间的关系.而后对每一个可能门限t，利用矩阵M可快速地计算其对应的图谱划分值，其最小的图谱划分值对应的门限即为分割图像的最佳阈值.

如果将图像中的每个像素看作一个节点，每对节点均用一条边连接起来, 边的权值反映这两个像素属于相同目标的可能性, 那么就可以构建一个带权的无向图G= (V,E).利用像素的灰度值以及它们的空间位置,可以定义图G中连接两个节点u和v的边的权值如下:

w(u,v)=

(14)

对任意门限t(0

(15)

那么等式(12)可转换为

令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.1 Schematic diagram of symmetric matrixM = [ 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).则

而且矩阵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.2 Implement of extracting crack

图2中的4幅路面裂缝图片，采用相同的预处理方式进行前期的预处理，然后将他们分别用OTSU、NDHM、graph-cut进行分割.为了对裂缝提取效果进行量化分析和评价，本文引入完成度指数 和正确度指数[14-15].完成度指数用于描述完成裂缝提取这一任务的完成程度，正确度指数则描述完成任务的质量水平.其定义见式(16) 和式(17) .另外，为了对算法的时间效率进行分析，实验记录了算法的运行时间.

(16)

(17)

式(16)中，Lr代表提取结果是真实裂缝的长度；Lgt代表裂缝的实际长度. 通过实地测量和手工编辑得到；LN代表提取结果的总长度.

表1 裂缝提取结果评价

表2 算法效率评价Table 2 Evaluation of algorithm efficiency

4 结 语

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

参考文献：

[1] 刘渝，张彦锋，鲁统伟.OCR中一种基于最小乘法的连通域去噪方法[J].武汉工程大学学报，2011，33(1)：84-87.

[2] Li L, Chan P, Rao A,et al. Flexible pavement distress evaluation using image analysis[C]//Proceeding of the 2nd International Conference on Applications of Advanced Technologies in Transportation Engineering.1991: 473-477.

[3] Seung-Nam Yu, Jae-Ho Jang. Auto inspection system using a mobile robot for detecting concrete cracks in a tunnel[J]. Automation in Construction, 2006,16(3): 255-261.

[4] Cheng H D ，Miyojim M.Automatic Pavement Distress Detection System[J]. Journal of Irfo～afion Sciences，1998(108):204-219．

[5] 李晋惠．公路路面裂缝类病害图像处理算法研究[J]．计算机工程与应用，2003(35)：212-232．

[6] 初秀民，严新平，陈先桥，路面破损图像二值化方法研究[J].计算机工程与应用,2008，44(28):161-165.

[7] Cheng H D, Rong jim. Novel approach to pavement cracking detection based on fuzzy set theory[J].ASCE，1999(13):270-280.

[8] Li Q Q, Liu X L. Novel Approach to Pavement Image Segmentation Based on Neighboring Difference Histogram Method[C]//2008 Congress on Image and Signal Processing, Sanya：2008：792-795.

[9] 刘向龙, 李清泉. 基于金字塔结构的海量路面影像破损统计模型[J] . 武汉大学学报:信息科学版,2008, 33(4): 430-432.

[10] Otsu N.A Threshold Selection Method from Gray-level Histogram[J].IEEE Trans，1979(SMC-9):62-66.

[11] 容观澳. 计算机图像处理[M].北京：清华大学出版社，2000.

[12] 付忠良.图像阈值选取方法的构造[J].中国图像图形学报,2000,5(6)：466-469.

[13] Lee S U.A Comparative Performance Study of Several Global Thresholding Techniques for Segmention[J]. CVGIP，1900(52):171-190.

[14] Shi J, Malik J . Normalized cut s and image segmentation[J]. IEEE Transactions on Pattern Analysis Machine Intelligence,2000,22(8):888-905.

[15] Wiedemann C, Ebner H. Automatic completion and evaluation of road networks [J] . Int Arch Photogramm Remote Sens, 2000(33): 976-986.