倒數(shù)交叉熵和改進圖割結合的河流目標檢測

吳一全，宋昱

（1.南京航空航天大學電子信息工程學院，江蘇南京210016；2.黃河水利委員會黃河水利科學研究院水利部黃河泥沙重點實驗室，河南鄭州450003；3.長江水利委員會長江科學院武漢市智慧流域工程技術研究中心，湖北武漢430010；4.哈爾濱工業(yè)大學城市水資源與水環(huán)境國家重點實驗室，黑龍江哈爾濱150090；5.南京水利科學研究院港口航道泥沙工程交通行業(yè)重點實驗室，江蘇南京210024）

倒數(shù)交叉熵和改進圖割結合的河流目標檢測

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

（1.南京航空航天大學電子信息工程學院，江蘇南京210016；2.黃河水利委員會黃河水利科學研究院水利部黃河泥沙重點實驗室，河南鄭州450003；3.長江水利委員會長江科學院武漢市智慧流域工程技術研究中心，湖北武漢430010；4.哈爾濱工業(yè)大學城市水資源與水環(huán)境國家重點實驗室，黑龍江哈爾濱150090；5.南京水利科學研究院港口航道泥沙工程交通行業(yè)重點實驗室，江蘇南京210024）

為了克服交互式圖割方法選取種子點的隨意性和由此導致的分割結果的不準確性，提出了使用倒數(shù)交叉熵閾值分割和改進圖割結合的河流目標自動提取方法。先利用倒數(shù)交叉熵閾值選取準則對河流圖像進行初始分割，從初始分割結果中自動選取種子點。然后利用改進圖割方法對河流遙感圖像進行分割。改進圖割中利用高斯混合模型對種子點區(qū)域進行建模，并利用結構張量矩陣計算平滑項。最后使用連通域檢測方法去除小的連通域并得到最終結果圖像。與交互式圖割、基于倒數(shù)交叉熵和圖割等4種方法進行了比較，實驗結果表明提出方法得到的分割圖像最為精確，分割效果最好。

遙感圖像；河流提取；倒數(shù)交叉熵；圖割；高斯混合模型；結構張量

河流是一種重要的地理目標，有效提取河道信息對于水利規(guī)劃及船舶導航等方面具有重要意義［1?2］。遙感成像周期短、實時性強、分辨率高、技術門檻低，已逐漸成為提取河道信息的重要手段。隨著數(shù)字圖像處理技術的發(fā)展，從遙感圖像中自動提取河流目標信息逐漸成為可能。現(xiàn)有的遙感圖像中河流目標自動提取方法主要分為以下4類。1）利用河流固有的特征［3］。河流的固有特征主要包括梯度特征、灰度和幾何特征以及波譜或光譜特征。2）基于邊緣檢測的方法［4］。3）基于特征提取和分類的方法［5］。4）其他方法。主要包括頻域濾波方法等［6］。圖割是一種基于能量最小化方法的圖像分割方法［7?8］。但是圖割算法是一種交互式圖像分割方法，需要在分割之前由用戶選取目標種子點和背景種子點。由于用戶選取種子點時往往帶有隨意性，會導致最后的分割結果具有很大的不確定性，而且交互式圖像分割方法也限制了其應用范圍。閾值分割是一類簡單有效、應用廣泛且易于實現(xiàn)的圖像分割方法［9］。利用閾值分割方法可以對圖像進行預分割，并從預分割結果中自動選取種子點。本文提出了一種基于倒數(shù)交叉熵閾值分割和改進圖割的河流目標自動提取方法。利用閾值分割對圖像進行預分割并由此選取種子點，然后利用改進圖割方法對河流圖像進行分割，實現(xiàn)河流目標的自動提取，并與4種相近方法進行了比較。

1 倒數(shù)交叉熵閾值選取準則

一幅大小為M×N的數(shù)字圖像可以表示為F＝｛f（m，n）｜（m，n）∈Ω｝，其中f（m，n）表示圖像中像素（m，n）處的灰度級，Ω??2表示圖像定義域。用h（g）表示圖像中灰度級為g的像素出現(xiàn)的次數(shù)，g＝0，1，…，L-1，L表示灰度級總數(shù)。用p（g）表示圖像中灰度級為g的像素出現(xiàn)的概率，則有p（g）＝h（g）／（M×N）。設閾值t將圖像F分為目標和背景兩類，其先驗概率和均值分別為P1（t）、P2（t）和

Shannon交叉熵的運算中使用了對數(shù)，其含義是原始圖像F與閾值分割后圖像之間的偏差，倒數(shù)交叉熵是對Shannon交叉熵的一種改進，采用了倒數(shù)運算取代了對數(shù)運算，不僅避免了Shannon交叉熵方法因涉及對數(shù)運算而存在無定義值和零值的問題，而且使得計算量大大減小。倒數(shù)交叉熵定義如下［9］：

2 改進圖割的圖像分割方法

2.1 圖割

圖像分割問題可以表示為對圖像中像素進行二元標記的組合優(yōu)化過程，這一問題可以通過圖割方法解決［8］。輸入圖像可以用一個無向圖g＝｛V，ε｝表示，其中V表示一組節(jié)點，ε表示一組連接這些節(jié)點的無向邊。無向圖中的每一節(jié)點對應于圖像中的每一個像素點，并且無向圖中還包含2個終端，目標終端S和背景終端T。無向圖中的邊分為2類。連接相鄰節(jié)點的邊稱為n?links，其中n表示“相鄰”，連接節(jié)點和終端的邊稱為t?links，其中t表示“終端”。圖中的所有n?links和t?links都被賦予了非負的權值。若用P表示圖像中所有的像素，N表示P中所有相鄰像素對組成的集合，那么節(jié)點集合V和邊集合ε可以表示為

式中：所有的n?links都包含在N中，而（p，S）和（p，T）則分別表示與S和T相連的t?links。目標終端或背景終端事先是標記好的，也稱作目標和背景種子點，不屬于目標終端或背景終端的點是未標記像素點。

一個割定義為邊集合ε的一個子集，C?ε，圖中的節(jié)點由這組邊C分割開來。圖割算法通過最小化如下形式的能量函數(shù)得到像素的最優(yōu)標記

式中：L＝｛Lp｝是一個二值向量，表示對圖像中所有像素可能的二值標記，對于背景Lp可以標記為“bkg”，對于目標則可以標記為“obj”，Kronecker算子定義為

式中：Rp（Lp）是基于標記Lp的數(shù)據(jù)項，B（p，q）是由相鄰像素（p，q）決定的平滑項，λ是控制數(shù)據(jù)項和平滑項各自權重的平衡系數(shù)。數(shù)據(jù)項Rp（Lp）描述了對像素點進行對應標號的合理性，平滑項B（p，q）描述了相鄰像素（p，q）標號的不連續(xù)性。圖的最小割可以通過最大流算法有效的解決［10］，并且對應的二值標號可以用來表示圖像中的河流區(qū)域。

2.2 利用高斯混合模型改進數(shù)據(jù)項

目標終端S和背景終端T分別由圖像中的一組像素點組成，其對應的灰度直方圖可以采用高斯混合模型進行建模。設目標終端或背景終端中某一像素點的灰度值為xi，1≤i≤n，其中n表示目標終端或背景終端包含的像素數(shù)目，這組像素點組成數(shù)據(jù)集合Xn＝｛x1，x2，…，xn｝。像素點xi對于GMM中第j個高斯函數(shù)的概率計算如下：

式中：θj由均值μj和方差組成，xi的GMM由一組加權的高斯函數(shù)組合而成，由下式定義：

式中：πj表示第j個高斯函數(shù)的混合權重，并且滿足，k是分量個數(shù)。一種估計式（7）中參數(shù)的方法是EM算法。為了計算由各參數(shù)θj組成的最優(yōu)參數(shù)向量θ，EM算法采用迭代計算的方式估計θ中的3k個參數(shù)直到式（8）中的對數(shù)似然函數(shù)達到最大：

EM算法可以描述如下：

式中：P（j｜xi）表示后驗概率。上述EM算法可以進行的條件是必須首先知道高斯函數(shù)分量個數(shù)k，但是對于目標終端或背景終端中的像素集合Xn，分量個數(shù)無法預先得到，此時必須采用可以自動估計分量個數(shù)的EM算法來求解上述GMM。這里采用文獻［11］中提出的貪婪學習算法，該算法步驟如下：

1）計算最優(yōu)單分量混合模型f1，令k＝1。

2）找到最優(yōu)的新分量φ（x；θ?）和其對應的混合權重α）fk（xi）+αφ（xi；θ）］，同時保持fk固定。

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

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

5）如果達到終止條件則停止，否則轉到第2）步。

原始圖割算法中［8］計算數(shù)據(jù)項Rp（Lp）的方式如表1所示。

表1 原始圖割算法中計算數(shù)據(jù)項的方式Table 1 The computation method of data term in original graph cut algorithm

式中：Pr（xp｜'obj'）和Pr（xp｜'bkg'）分別表示灰度值為xp的像素點在目標終端和背景終端的灰度直方圖中出現(xiàn)的概率。采用原始圖割算法中的公式計算數(shù)據(jù)項時，會有以下一些缺點。首先，目標終端和背景終端往往只包含了圖像中很少部分的像素點，這部分像素點的灰度范圍很可能不能涵蓋全部灰度范圍，當未標記像素點p的灰度值xp不在目標終端或背景終端的灰度涵蓋范圍中時，就無法定義灰度值為xp的像素點在其灰度直方圖中出現(xiàn)的概率。其次，僅利用概率的負對數(shù)來定義數(shù)據(jù)項不夠準確，不能夠完整反映未標記像素點和目標終端及背景終端的所屬關系。從而本文采用GMM改進原始圖割算法中數(shù)據(jù)項的計算方式。

利用上述貪婪學習算法得到目標終端或背景終端的GMM后，本文改進的數(shù)據(jù)項Rp（Lp）計算方法如表2所示。

表2 本文改進的數(shù)據(jù)項計算方法Table 2 The improved computation method of data term proposed in the paper

kobj和kbkg分別是目標終端和背景終端的高斯函數(shù)分量個數(shù)，θj，obj和θj，bkg分別表示目標終端和背景終端的第j個高斯函數(shù)的參數(shù)。采用GMM改進數(shù)據(jù)項后，就能避免原始圖割算法中計算數(shù)據(jù)項的缺點。首先，任何未標記像素點灰度值xp在上表計算式中都有定義；其次，利用GMM對目標終端和背景終端灰度分布進行建模，然后將未標記像素點灰度值xp帶入混合模型計算式，能夠完整的反映未標記像素點和目標終端及背景終端的所屬關系。

2.3 利用結構張量矩陣改進平滑項

原始圖割算法中［9］計算平滑項時采用如下公式

式中：Ip和Iq分別表示像素點p和像素點q的灰度值，σ是全局參數(shù)。采用上述計算方式計算平滑項時，存在一些缺點。這里平滑項僅決定于相鄰兩點灰度值之差，而并未考慮相鄰兩點的邊緣方向結構。當相鄰兩點處在平滑區(qū)域內部而僅僅是灰度值具有差異時，應給予平滑項較大的值，而當相鄰兩點處在不同區(qū)域之間的邊緣時，則給予平滑項較小的值，這樣能夠更加準確地描述邊緣處相鄰兩點的關系。如果在計算平滑項時引入結構張量，則能達到上述目地。

本文采用結構張量矩陣改進平滑項的計算方式。考慮圖像中一個大小為3×3的窗口Q（x，y），Q（x，y）也可以被看作是一個曲面。該窗口在圖像中相近的兩點（x，y）和（x+Δx，y+Δy）處的差值可以表示為

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

式中：

式中：S是一個對稱和半正定的矩陣，叫做結構張量矩陣，該矩陣表示了圖像局部區(qū)域的幾何結構。用λ+和λ-分別表示S的最大和最小特征值。可以用結構張量矩陣來定義式（4）中的平滑項［12］。給出一對相鄰像素vij和vkl，定義ws（vij，vkl）＝（λ+（i，j）-vkl）對于像素點vij和vkl不是對稱的，所以引入下式：

式中：κ是全局參數(shù)。式（4）中的平滑項可以寫成：

式中：p＝ij，q＝kl。

3 實驗結果與分析

為了驗證本文方法的有效性和不同改進方式對分割結果的影響，針對大量河流遙感圖像進行了實驗，將原始圖割方法［8］（方法1），基于倒數(shù)交叉熵和原始圖割的方法（方法2），基于倒數(shù)交叉熵和改進平滑項的圖割方法（本文方法1），基于倒數(shù)交叉熵和改進數(shù)據(jù)項的圖割方法（本文方法2），基于倒數(shù)交叉熵和改進數(shù)據(jù)項及改進平滑項的方法（本文方法3）等5種方法進行了比較。實驗環(huán)境是Intel Atom（TM）CPU D2700 2.13GHz主頻／2.00GB內存／Matlab R2012a。使用圖割算法時，平衡系數(shù)λ＝1，改進平滑項計算時，取全局參數(shù)κ＝20。因篇幅限制，現(xiàn)以其中2幅河流遙感圖像（圖像1，圖像2）為例加以說明，這里只列出了圖像1的分割結果。

圖1給出了該幅原始河流遙感圖像（a）及采用方法1（b），基于倒數(shù)交叉熵閾值分割后選取的目標種子點和背景種子點（c）、方法2（d）、本文方法1（e）、本文方法2（f）、本文方法3（g）及采用本文方法3后并利用連通域檢測并去除小的連通域（h）的結果圖像。

首先分析各算法的區(qū)域分割準確性，這可以從衡量圖像誤分割點的多少來分析。如果將非河流區(qū)域分為河流區(qū)域或者將河流區(qū)域分為非河流區(qū)域，則構成圖像的誤分割點。圖像1的誤分割點主要集中在圖像左下部和圖像右部。在方法1中，采用交互方式進行圖像分割，由人工選取目標種子點和背景種子點，誤分割的點最少。其他4種自動分割方法中，方法2和本文方法1的誤分割點數(shù)多于本文方法2和本文方法3。在方法2和本文方法1中，都是采用直方圖直接計算數(shù)據(jù)項，這種計算方式不夠準確，所以導致誤分割的點較多。為了定量衡量各算法的誤分割點數(shù)量，將誤分割點數(shù)統(tǒng)計于表3中。從表3可以看出，本文方法2和本文方法3的誤分割點數(shù)明顯較少。接下來分析各算法的邊界分割準確性。為了定量衡量各種算法的邊界分割準確性，現(xiàn)將各算法邊緣圖像的FOM值列于表4中，F(xiàn)OM越接近于1則邊界越準確。從表4可以看出，方法1的FOM值最低，說明采用交互式圖像分割方法雖然誤分點較少，但邊界很不準確。對于圖像1，本文方法2和本文方法3的FOM值較高，對于圖像2，本文方法1和本文方法3的FOM值較高。說明采用改進后的平滑項能夠提高邊界分割的準確性。綜合誤分割點數(shù)和FOM值2項指標，本文方法3的綜合性能最優(yōu)。

圖1 河流遙感圖像1及其分割結果Fig.1 Remote sensing river image 1 and its segmenta?tion results

表3 各算法誤分割點個數(shù)比較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 結論

本文采用倒數(shù)交叉熵閾值選取準則對圖像進行初始分割，選取背景區(qū)域和目標區(qū)域中最大的正方形作為目標種子點和背景種子點，采用這樣的方法能夠正確的得到目標種子點和背景種子點。在圖割算法中，引入高斯混合模型改進數(shù)據(jù)項，并采用結構張量矩陣改進平滑項。將原始圖割算法［8］、基于倒數(shù)交叉熵和原始圖割的方法、基于倒數(shù)交叉熵和改進平滑項的方法、基于倒數(shù)交叉熵和改進數(shù)據(jù)項的方法、基于倒數(shù)交叉熵和改進數(shù)據(jù)項及改進平滑項等5種方法進行了比較，實驗結果表明本文方法3誤分點較少且分割結果邊界精確，能夠正確提取河流區(qū)域。

［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］.工程數(shù)學學報，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，F(xiàn)ENG 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，F(xiàn)UNKA L G.Graph cuts and efficient N?D im?age segmentation［J］.International Journal of Computer Vi?sion，2006，70（2）：109?131.

［9］吳一全，宋昱，周懷春.鍋爐煤燃燒火焰圖像倒數(shù)交叉熵多閾值分割［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.網(wǎng)絡出版時間：2015?04?28.

水利部黃河泥沙重點實驗室開放基金資助項目（2014006）；長江科學院開放基金資助項目（CK?WV2013225／KY）；城市水資源與水環(huán)境國家重點實驗室開放基金資助項目（LYPK201304）；港口航道泥沙工程交通行業(yè)重點實驗室開放基金資助項目；江蘇高校優(yōu)勢學科建設工程資助項目.

吳一全（1963?），男，教授，博士生導師.

吳一全，E?mail：nuaaimage＠163.com.