倒数交叉熵和改进图割结合的河流目标检测

吴一全，宋昱

（1.南京航空航天大学电子信息工程学院，江苏南京210016；2.黄河水利委员会黄河水利科学研究院水利部黄河泥沙重点实验室，河南郑州450003；3.长江水利委员会长江科学院武汉市智慧流域工程技术研究中心，湖北武汉430010；4.哈尔滨工业大学城市水资源与水环境国家重点实验室，黑龙江哈尔滨150090；5.南京水利科学研究院港口航道泥沙工程交通行业重点实验室，江苏南京210024）

倒数交叉熵和改进图割结合的河流目标检测

吴一全1，2，3，4，5，宋昱1

（1.南京航空航天大学电子信息工程学院，江苏南京210016；2.黄河水利委员会黄河水利科学研究院水利部黄河泥沙重点实验室，河南郑州450003；3.长江水利委员会长江科学院武汉市智慧流域工程技术研究中心，湖北武汉430010；4.哈尔滨工业大学城市水资源与水环境国家重点实验室，黑龙江哈尔滨150090；5.南京水利科学研究院港口航道泥沙工程交通行业重点实验室，江苏南京210024）

为了克服交互式图割方法选取种子点的随意性和由此导致的分割结果的不准确性，提出了使用倒数交叉熵阈值分割和改进图割结合的河流目标自动提取方法。先利用倒数交叉熵阈值选取准则对河流图像进行初始分割，从初始分割结果中自动选取种子点。然后利用改进图割方法对河流遥感图像进行分割。改进图割中利用高斯混合模型对种子点区域进行建模，并利用结构张量矩阵计算平滑项。最后使用连通域检测方法去除小的连通域并得到最终结果图像。与交互式图割、基于倒数交叉熵和图割等4种方法进行了比较，实验结果表明提出方法得到的分割图像最为精确，分割效果最好。

遥感图像；河流提取；倒数交叉熵；图割；高斯混合模型；结构张量

河流是一种重要的地理目标，有效提取河道信息对于水利规划及船舶导航等方面具有重要意义［1⁃2］。遥感成像周期短、实时性强、分辨率高、技术门槛低，已逐渐成为提取河道信息的重要手段。随着数字图像处理技术的发展，从遥感图像中自动提取河流目标信息逐渐成为可能。现有的遥感图像中河流目标自动提取方法主要分为以下4类。1）利用河流固有的特征［3］。河流的固有特征主要包括梯度特征、灰度和几何特征以及波谱或光谱特征。2）基于边缘检测的方法［4］。3）基于特征提取和分类的方法［5］。4）其他方法。主要包括频域滤波方法等［6］。图割是一种基于能量最小化方法的图像分割方法［7⁃8］。但是图割算法是一种交互式图像分割方法，需要在分割之前由用户选取目标种子点和背景种子点。由于用户选取种子点时往往带有随意性，会导致最后的分割结果具有很大的不确定性，而且交互式图像分割方法也限制了其应用范围。阈值分割是一类简单有效、应用广泛且易于实现的图像分割方法［9］。利用阈值分割方法可以对图像进行预分割，并从预分割结果中自动选取种子点。本文提出了一种基于倒数交叉熵阈值分割和改进图割的河流目标自动提取方法。利用阈值分割对图像进行预分割并由此选取种子点，然后利用改进图割方法对河流图像进行分割，实现河流目标的自动提取，并与4种相近方法进行了比较。

1 倒数交叉熵阈值选取准则

一幅大小为M×N的数字图像可以表示为F＝｛f（m，n）｜（m，n）∈Ω｝，其中f（m，n）表示图像中像素（m，n）处的灰度级，Ω⊂ℤ2表示图像定义域。用h（g）表示图像中灰度级为g的像素出现的次数，g＝0，1，…，L-1，L表示灰度级总数。用p（g）表示图像中灰度级为g的像素出现的概率，则有p（g）＝h（g）／（M×N）。设阈值t将图像F分为目标和背景两类，其先验概率和均值分别为P1（t）、P2（t）和

Shannon交叉熵的运算中使用了对数，其含义是原始图像F与阈值分割后图像之间的偏差，倒数交叉熵是对Shannon交叉熵的一种改进，采用了倒数运算取代了对数运算，不仅避免了Shannon交叉熵方法因涉及对数运算而存在无定义值和零值的问题，而且使得计算量大大减小。倒数交叉熵定义如下［9］：

2 改进图割的图像分割方法

2.1 图割

图像分割问题可以表示为对图像中像素进行二元标记的组合优化过程，这一问题可以通过图割方法解决［8］。输入图像可以用一个无向图g＝｛V，ε｝表示，其中V表示一组节点，ε表示一组连接这些节点的无向边。无向图中的每一节点对应于图像中的每一个像素点，并且无向图中还包含2个终端，目标终端S和背景终端T。无向图中的边分为2类。连接相邻节点的边称为n⁃links，其中n表示“相邻”，连接节点和终端的边称为t⁃links，其中t表示“终端”。图中的所有n⁃links和t⁃links都被赋予了非负的权值。若用P表示图像中所有的像素，N表示P中所有相邻像素对组成的集合，那么节点集合V和边集合ε可以表示为

式中：所有的n⁃links都包含在N中，而（p，S）和（p，T）则分别表示与S和T相连的t⁃links。目标终端或背景终端事先是标记好的，也称作目标和背景种子点，不属于目标终端或背景终端的点是未标记像素点。

一个割定义为边集合ε的一个子集，C⊂ε，图中的节点由这组边C分割开来。图割算法通过最小化如下形式的能量函数得到像素的最优标记

式中：L＝｛Lp｝是一个二值向量，表示对图像中所有像素可能的二值标记，对于背景Lp可以标记为“bkg”，对于目标则可以标记为“obj”，Kronecker算子定义为

式中：Rp（Lp）是基于标记Lp的数据项，B（p，q）是由相邻像素（p，q）决定的平滑项，λ是控制数据项和平滑项各自权重的平衡系数。数据项Rp（Lp）描述了对像素点进行对应标号的合理性，平滑项B（p，q）描述了相邻像素（p，q）标号的不连续性。图的最小割可以通过最大流算法有效的解决［10］，并且对应的二值标号可以用来表示图像中的河流区域。

2.2 利用高斯混合模型改进数据项

目标终端S和背景终端T分别由图像中的一组像素点组成，其对应的灰度直方图可以采用高斯混合模型进行建模。设目标终端或背景终端中某一像素点的灰度值为xi，1≤i≤n，其中n表示目标终端或背景终端包含的像素数目，这组像素点组成数据集合Xn＝｛x1，x2，…，xn｝。像素点xi对于GMM中第j个高斯函数的概率计算如下：

式中：θj由均值μj和方差组成，xi的GMM由一组加权的高斯函数组合而成，由下式定义：

式中：πj表示第j个高斯函数的混合权重，并且满足，k是分量个数。一种估计式（7）中参数的方法是EM算法。为了计算由各参数θj组成的最优参数向量θ，EM算法采用迭代计算的方式估计θ中的3k个参数直到式（8）中的对数似然函数达到最大：

EM算法可以描述如下：

式中：P（j｜xi）表示后验概率。上述EM算法可以进行的条件是必须首先知道高斯函数分量个数k，但是对于目标终端或背景终端中的像素集合Xn，分量个数无法预先得到，此时必须采用可以自动估计分量个数的EM算法来求解上述GMM。这里采用文献［11］中提出的贪婪学习算法，该算法步骤如下：

1）计算最优单分量混合模型f1，令k＝1。

2）找到最优的新分量φ（x；θ∗）和其对应的混合权重α）fk（xi）+αφ（xi；θ）］，同时保持fk固定。

3）令fk+1（x）＝（1-α∗）fk（x）+α∗φ（x；θ∗），k＝k+1。

4）使用EM算法更新fk直至收敛。

5）如果达到终止条件则停止，否则转到第2）步。

原始图割算法中［8］计算数据项Rp（Lp）的方式如表1所示。

表1 原始图割算法中计算数据项的方式Table 1 The computation method of data term in original graph cut algorithm

式中：Pr（xp｜'obj'）和Pr（xp｜'bkg'）分别表示灰度值为xp的像素点在目标终端和背景终端的灰度直方图中出现的概率。采用原始图割算法中的公式计算数据项时，会有以下一些缺点。首先，目标终端和背景终端往往只包含了图像中很少部分的像素点，这部分像素点的灰度范围很可能不能涵盖全部灰度范围，当未标记像素点p的灰度值xp不在目标终端或背景终端的灰度涵盖范围中时，就无法定义灰度值为xp的像素点在其灰度直方图中出现的概率。其次，仅利用概率的负对数来定义数据项不够准确，不能够完整反映未标记像素点和目标终端及背景终端的所属关系。从而本文采用GMM改进原始图割算法中数据项的计算方式。

利用上述贪婪学习算法得到目标终端或背景终端的GMM后，本文改进的数据项Rp（Lp）计算方法如表2所示。

表2 本文改进的数据项计算方法Table 2 The improved computation method of data term proposed in the paper

kobj和kbkg分别是目标终端和背景终端的高斯函数分量个数，θj，obj和θj，bkg分别表示目标终端和背景终端的第j个高斯函数的参数。采用GMM改进数据项后，就能避免原始图割算法中计算数据项的缺点。首先，任何未标记像素点灰度值xp在上表计算式中都有定义；其次，利用GMM对目标终端和背景终端灰度分布进行建模，然后将未标记像素点灰度值xp带入混合模型计算式，能够完整的反映未标记像素点和目标终端及背景终端的所属关系。

2.3 利用结构张量矩阵改进平滑项

原始图割算法中［9］计算平滑项时采用如下公式

式中：Ip和Iq分别表示像素点p和像素点q的灰度值，σ是全局参数。采用上述计算方式计算平滑项时，存在一些缺点。这里平滑项仅决定于相邻两点灰度值之差，而并未考虑相邻两点的边缘方向结构。当相邻两点处在平滑区域内部而仅仅是灰度值具有差异时，应给予平滑项较大的值，而当相邻两点处在不同区域之间的边缘时，则给予平滑项较小的值，这样能够更加准确地描述边缘处相邻两点的关系。如果在计算平滑项时引入结构张量，则能达到上述目地。

本文采用结构张量矩阵改进平滑项的计算方式。考虑图像中一个大小为3×3的窗口Q（x，y），Q（x，y）也可以被看作是一个曲面。该窗口在图像中相近的两点（x，y）和（x+Δx，y+Δy）处的差值可以表示为

上述差值的平方表示如下：

式中：

式中：S是一个对称和半正定的矩阵，叫做结构张量矩阵，该矩阵表示了图像局部区域的几何结构。用λ+和λ-分别表示S的最大和最小特征值。可以用结构张量矩阵来定义式（4）中的平滑项［12］。给出一对相邻像素vij和vkl，定义ws（vij，vkl）＝（λ+（i，j）-vkl）对于像素点vij和vkl不是对称的，所以引入下式：

式中：κ是全局参数。式（4）中的平滑项可以写成：

式中：p＝ij，q＝kl。

3 实验结果与分析

为了验证本文方法的有效性和不同改进方式对分割结果的影响，针对大量河流遥感图像进行了实验，将原始图割方法［8］（方法1），基于倒数交叉熵和原始图割的方法（方法2），基于倒数交叉熵和改进平滑项的图割方法（本文方法1），基于倒数交叉熵和改进数据项的图割方法（本文方法2），基于倒数交叉熵和改进数据项及改进平滑项的方法（本文方法3）等5种方法进行了比较。实验环境是Intel Atom（TM）CPU D2700 2.13GHz主频／2.00GB内存／Matlab R2012a。使用图割算法时，平衡系数λ＝1，改进平滑项计算时，取全局参数κ＝20。因篇幅限制，现以其中2幅河流遥感图像（图像1，图像2）为例加以说明，这里只列出了图像1的分割结果。

图1给出了该幅原始河流遥感图像（a）及采用方法1（b），基于倒数交叉熵阈值分割后选取的目标种子点和背景种子点（c）、方法2（d）、本文方法1（e）、本文方法2（f）、本文方法3（g）及采用本文方法3后并利用连通域检测并去除小的连通域（h）的结果图像。

首先分析各算法的区域分割准确性，这可以从衡量图像误分割点的多少来分析。如果将非河流区域分为河流区域或者将河流区域分为非河流区域，则构成图像的误分割点。图像1的误分割点主要集中在图像左下部和图像右部。在方法1中，采用交互方式进行图像分割，由人工选取目标种子点和背景种子点，误分割的点最少。其他4种自动分割方法中，方法2和本文方法1的误分割点数多于本文方法2和本文方法3。在方法2和本文方法1中，都是采用直方图直接计算数据项，这种计算方式不够准确，所以导致误分割的点较多。为了定量衡量各算法的误分割点数量，将误分割点数统计于表3中。从表3可以看出，本文方法2和本文方法3的误分割点数明显较少。接下来分析各算法的边界分割准确性。为了定量衡量各种算法的边界分割准确性，现将各算法边缘图像的FOM值列于表4中，FOM越接近于1则边界越准确。从表4可以看出，方法1的FOM值最低，说明采用交互式图像分割方法虽然误分点较少，但边界很不准确。对于图像1，本文方法2和本文方法3的FOM值较高，对于图像2，本文方法1和本文方法3的FOM值较高。说明采用改进后的平滑项能够提高边界分割的准确性。综合误分割点数和FOM值2项指标，本文方法3的综合性能最优。

图1 河流遥感图像1及其分割结果Fig.1 Remote sensing river image 1 and its segmenta⁃tion results

表3 各算法误分割点个数比较Table 3 The comparison of number of miss classified pixels of each algorithm

表4 各算法边缘图像FOM值Table 4 The comparison of FOM value of each algorithm

4 结论

本文采用倒数交叉熵阈值选取准则对图像进行初始分割，选取背景区域和目标区域中最大的正方形作为目标种子点和背景种子点，采用这样的方法能够正确的得到目标种子点和背景种子点。在图割算法中，引入高斯混合模型改进数据项，并采用结构张量矩阵改进平滑项。将原始图割算法［8］、基于倒数交叉熵和原始图割的方法、基于倒数交叉熵和改进平滑项的方法、基于倒数交叉熵和改进数据项的方法、基于倒数交叉熵和改进数据项及改进平滑项等5种方法进行了比较，实验结果表明本文方法3误分点较少且分割结果边界精确，能够正确提取河流区域。

［1］王超，黄凤辰，汤晓斌，等.一种针对复杂背景下高分辨率SAR图像河道检测算法［J］.遥感技术与应用，2012，27（4）：516⁃522.WANG Chao，HUANG Fengchen，TANG Xiaobin，et al.A river extraction algorithm for high⁃resolution SAR images with complex backgrounds［J］.Remote Sensing Technology and Application，2012，27（4）：516⁃522.

［2］于晓升，吴成东，陈东岳，等.基于多特征融合的遥感图像河流目标检测算法［J］.东北大学学报：自然科学版，2012，33（11）：1547⁃1550.YU Xiaosheng，WU Chengdong，CHEN Dongyue，et al.River detection in remote sensing image based on multi⁃fea⁃ture fusion［J］.Journal of Northeastern University：Natural Science，2012，33（11）：1547⁃1550.

［3］陈升来，李云茹，李涛.基于合成孔径雷达图像的河流检测方法研究［J］.计算机测量与控制，2009，17（7）：1267⁃1269.CHEN Shenglai，LI Yuru，LI Tao.Study on river detection based on SAR image［J］.Computer Measurement and Con⁃ trol，2009，17（7）：1267⁃1269.

［4］王文波，孙琳，羿旭明，等.SAR图像中河流边缘检测的Wavelet snake算法［J］.工程数学学报，2007，24（6）：1075⁃1079.WANG Wenbo，SUN Lin，YI Xuming，et al.A wavelet snake method to detect boundaries between land and water in SAR images［J］.Chinese Journal of Engineering Mathemat⁃ics，2007，24（6）：1075⁃1079.

［5］TIAN Ziheng，WU Chengdong，CHEN Dongyue，et al.A novel method of river detection for high resolution remote sensing image based on corner feature and SVM［C］／／Ad⁃vances in Neural Networks⁃ISNN 2012.Berlin：Springer，2012：266⁃273.

［6］王珂，肖鹏峰，冯学智，等.基于频域滤波的高分辨率遥感图像城市河道信息提取［J］.遥感学报，2013，17（2）：269⁃285.WANG Ke，XIAO Pengfeng，FENG Xuezhi，et al.Extrac⁃tion of urban rivers from high spatial resolution remotely sensed imagery based on filtering in frequency domain［J］.Journal of Remote Sensing，2013，17（2）：269⁃285.

［7］刘松涛，殷福亮.基于图割的图像分割方法及其新进展［J］.自动化学报，2012，38（6）：911⁃922.LIU Songtao，YIN Fuliang.The basic principle and its new advances of image segmentation methods based on graph cuts［J］.Acta Automatica Sinica，2013，38（6）：911⁃922.

［8］BOYKOV Y，FUNKA L G.Graph cuts and efficient N⁃D im⁃age segmentation［J］.International Journal of Computer Vi⁃sion，2006，70（2）：109⁃131.

［9］吴一全，宋昱，周怀春.锅炉煤燃烧火焰图像倒数交叉熵多阈值分割［J］.燃烧科学与技术，2013，19（6）：493⁃500.WU Yiquan，SONG Yu，ZHOU Huaichun.Boiler combus⁃tion flame image multiple thresholding using reciprocal cross entropy［J］.Journal of Combustion Science and Technology，2013，19（6）：493⁃500.

［10］BOYKOV Y，KOLMOGOROV V.An experimental compar⁃ison of mincut／max⁃flow algorithms for energy minimization in vision［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（9）：1124⁃1137.

［11］VERBEEK J，VLASSIS M，KROSE B.Efficient greedy learning of Gaussian mixture models［J］.Neural Computa⁃tion，2003，15（2）：469⁃485.

［12］ZHOU Hailing，ZHENG Jianmin，WEI Lei.Texture aware image segmentation using graph cuts and active contours［J］.Pattern Recognition，2013，46（6）：1719⁃1733.

River target detection by combining reciprocal cross entropy thresholding and improved graph cuts

WU Yiquan1，2，3，4，5，SONG Yu1

（1.College of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China；2.Key Laboratory of the Yellow River Sediment of Ministry of Water Resource，Yellow River Institute of Hydraulic Research，Yellow Riv⁃er Water Resources Commission，Zhengzhou 450003，China；3.Engineering Technology Research Center of Wuhan Intelligent basin，Changjiang River Scientific Research Institute，Changjiang Water Resources Commission，Wuhan 430010，China；4.State Key Labo⁃ratory of Urban Water Resource and Environment，Harbin Institute of Technology，Harbin 150090，China；5.Key Laboratory of Port，Waterway and Sedimentation Engineering of the Ministry of Transport，Nanjing Hydraulic Research Institute，Nanjing 210024，China）

An automatic river target extraction method based on reciprocal cross entropy thresholding and improved graph cuts was proposed in order to overcome the arbitrariness of choosing seed points in interacting graph cuts method and the subsequent incorrect segmentation result.First，the river image was pre⁃segmented based on the re⁃ciprocal cross entropy threshold selection criterion and the seed points were automatically chosen from the pre⁃seg⁃mentation result.Next，the river remote sensing image was segmented by the improved graph cuts.In improved graph cuts，the seed point region was modeled by Gaussian mixture model and the smoothing terms were calculated by the structure tensor matrix.Finally，the small regions were eliminated using connected region detection method and the result was thus obtained.Comparing with the other four methods including interactive graph cuts and the method based on reciprocal cross entropy and graph cuts，the experimental results showed that the proposed method could obtain the best segmentation result.

remote sensing images；river detection；reciprocal cross entropy；graph cuts；Gaussian mixture model；structure tensor

10.3969／j.issn.1006⁃7043.201401045

TN911.73 TP751

：A

：1006⁃7043（2015）06⁃0836⁃06

http：／／www.cnki.net／kcms／detail／23.1390.u.20150428.0910.011.html

2014⁃01⁃15.网络出版时间：2015⁃04⁃28.

水利部黄河泥沙重点实验室开放基金资助项目（2014006）；长江科学院开放基金资助项目（CK⁃WV2013225／KY）；城市水资源与水环境国家重点实验室开放基金资助项目（LYPK201304）；港口航道泥沙工程交通行业重点实验室开放基金资助项目；江苏高校优势学科建设工程资助项目.

吴一全（1963⁃），男，教授，博士生导师.

吴一全，E⁃mail：nuaaimage＠163.com.