基于超像素的點互信息邊界檢測算法

劉勝男　寧紀鋒

摘要：點互信息（PMI）邊界檢測算法能準確檢測圖像中的邊界，但算法效率受制于采樣點的提取。針對采樣過程中存在隨機性和信息冗余的問題，提出一種利用超像素分割提供的中層結(jié)構(gòu)信息來指導點對選取的方法。首先使用超像素算法對圖像進行初始分割，將圖像劃分成大小形狀近似的像素塊；然后選取落在相鄰超像素中的像素點對，從而使樣本點的選取更有目的性，在采樣點數(shù)目較少時，保證樣本點仍能有效完整地獲取圖像信息。實驗通過與原始的PMI邊界檢測算法在伯克利分割數(shù)據(jù)庫（BSDS）上進行比對驗證得出，基于超像素的PMI邊界檢測算法在采樣點對為3500時，平均精準度（AP）達到0.7917，而原始算法則需要6000個同樣環(huán)境下的采樣點對。基于超像素的PMI邊界檢測算法在保證了檢測精度的同時減少了所需的采樣點數(shù)目，從而能有效提高算法的實時性。

關(guān)鍵詞：邊界檢測； 超像素； 點互信息； 相似度衡量； 樣點選取

中圖分類號：TP391.41

文獻標志碼：A

0引言

圖像的邊界是圖像的重要特征之一，準確的邊界檢測是圖像分割、目標區(qū)域識別、區(qū)域形狀提取等圖像分析工作的基礎(chǔ)[1-2]，是計算機視覺系統(tǒng)中必不可少的重要環(huán)節(jié)[3-5]。邊界檢測的實質(zhì)是采用某種算法提取圖像中目標與背景間的邊界線[6-8]。邊界檢測算法根據(jù)是否需要訓練先驗知識可分為有監(jiān)督的和無監(jiān)督的檢測方法。其中，在無監(jiān)督的邊界檢測算法中根據(jù)所基于的理論不同可大致分為四類：基于聚類的方法，如均值偏移（Mean Shift， MS）算法、快速偏移（Quick Shift， QS）算法等；基于圖論的方法，如歸一化切割算法、Felz-Hutt（Felzenswalb-Huttenlocher）算法等；基于區(qū)域合并的方法，如分層分割算法[9-10]和受壓紋理（Compression-based Texture Merging， CTM）算法等；基于種子增長的方法，如全變分算法（Total Variation， TV）等。這些算法不需要提供圖像的先驗知識，是當前研究范圍最廣的主流邊界檢測算法。無監(jiān)督的邊界檢測現(xiàn)已形成一個體系，且有公開的庫和統(tǒng)一的評價方法。與此同時，有監(jiān)督的邊界檢測算法利用其所構(gòu)造的邊界訓練集，結(jié)合機器學習方法進行邊界檢測也受到了一定的關(guān)注，如稀疏編碼梯度算法（Sparse Coding Gradient， SCG）、結(jié)構(gòu)化森林邊緣算法（Structured Forest Edge，SE）[11]和素描令牌算法（Sketch Tokens， ST）[12]等，都取得了良好的檢測結(jié)果。

在無監(jiān)督邊界檢測算法研究中，基于點互信息（Pointwise Mutual Information， PMI）的邊界檢測算法[13]利用圖像中的像素點對信息構(gòu)建相似度矩陣獲得邊界，其性能超過了有監(jiān)督的邊界檢測算法，成為當前該領(lǐng)域的研究熱點。PMI是信息論和數(shù)理統(tǒng)計中的概念，常被用來衡量兩個獨立事件間的相關(guān)性。在邊界檢測算法中，將其概念引申為圖像中兩個特征之間聯(lián)系的緊密程度，若兩個特征聯(lián)系十分緊密，則可認為在該圖像中從屬這兩個特征的像素相似度很高，應(yīng)包含在同一個目標中。然而在檢測圖像邊界時，PMI值的計算需要隨機地選取足夠多的點才能保證圖像的特征信息不被遺漏，算法的實時性受到了制約。與此同時，完全隨機的選點方式也造成了一部分采樣點的冗余。

因此如何減少該邊界檢測算法中采樣點選取的隨機性，對提高其性能有重要的影響。本文將超像素圖像分割與PMI相結(jié)合，利用超像素分割獲得的圖像中層結(jié)構(gòu)信息來指導PMI算法中像素點的選取。

超像素算法可利用像素之間特征的相似程度將像素分組，如圖1所示。超像素可提取圖像中感知有意義的區(qū)域，或用來取代剛性結(jié)構(gòu)的像素網(wǎng)格，從而可以通過提升圖像處理底層算法加快高層認知算法。文中超像素分割獲得的分割結(jié)果將用以約束PMI算法的采樣過程，使得原本無序隨機的采樣變得有序且能摒棄冗余信息，尤其在采樣點數(shù)目較少的情況下，仍能有效地獲取圖像的特征，使算法的精度得以提升[14-16]。

1基于PMI的邊界檢測算法

1.1PMI

PMI[13]是信息論和數(shù)理統(tǒng)計中被用作衡量關(guān)聯(lián)性的一個可計算量。假設(shè)x和y是兩個相互獨立的離散型隨機變量，而x、y的聯(lián)合分布概率（joint distribution）和各自的獨立分布概率（individual distribution）可得到，則PMI通過量化聯(lián)合分布和獨立分布之間的差異來衡量x事件和y事件的關(guān)聯(lián)性，其數(shù)學表示為式（1）：

1.2PMI在圖像處理中的應(yīng)用

將PMI概念應(yīng)用到圖像處理過程中，則可理解為對于任意一幅圖像，隨機地取出N個點對，則每一個點對中的點，如圖2所示，都可以看成是一個隨機變量。每一個點對都可映射到特征域成為一個特征對，即點對中的一個點可以抽取特征成為特征A，另一個點可抽取特征為特征B。

其中ρ參數(shù)可以為整數(shù)，也可以為非整數(shù)，此時PMI能更貼合實際地提取特征，因此在PMI邊界檢測算法中經(jīng)訓練數(shù)據(jù)得到當ρ參數(shù)取值為1.25時，PMI模型的表現(xiàn)最好。

對每一幅待測圖像都可以得到如圖3（b）所示的PMI模型圖，其中灰度較淺的區(qū)域PMI值較高。對于圖3（a）中所示的待測圖像，其中1號圈代表斑馬身上的條紋特征對的PMI值高于2號圈代表草地特征與斑馬身上的條紋特征的PMI值，則表示斑馬的身體條紋特征應(yīng)該融合成為一個整體。

對于每一幅圖像提取N個點對就可以得到N個特征對和N個PMI值，利用特征對和PMI信息生成隨機森林決策樹，以獲得圖像中任何特征對的PMI值，即可對整張圖像構(gòu)建相似度矩陣。為圖像中的每個像素定義一個特征向量f，則像素點i和點j間的相似度可通過代入式（3）得到式（4）表示為：

其中：k表示當前特征，M表示共有M個特征域。生成相似度矩陣后可以通過區(qū)域融合的方法完成后續(xù)邊界檢測或圖像分割的工作[10]。

2基于超像素的PMI邊界檢測算法

PMI邊界檢測算法概念簡單，直觀地描述了像素點組成圖像時的規(guī)律，即若兩個特征頻繁同時出現(xiàn)，則屬于這兩個特征的像素點相似度越高，屬于同一個目標的概率越高。

PMI提取了像素點的統(tǒng)計學特征，這種全局特征突破了一些經(jīng)典算法的局限性。當一個目標物體由多個特征值不同的像素塊（如不同顏色或不同紋理等）組合而成時，若只憑特征值的突變來判斷邊界則會出現(xiàn)誤判，而PMI算法可以通過判斷特征間的PMI值將看似特征完全不同但實屬于同一個目標的像素點融合，從而獲得數(shù)字圖像中目標物體的真實邊界信息。

2.1原始PMI邊界檢測算法存在的缺點

PMI描述了像素點級別的圖像特征，其概念簡單、實現(xiàn)容易、結(jié)果精準，然而利用PMI處理圖像時，為了使圖像的信息盡可能地被收集、采納，采樣點的數(shù)目必須要足夠多，以保證選取到的樣本點能夠完整地表示圖像的特征。然而，樣本點越多就意味著計算時間越長、運行效率越低，因此算法的性能受到制約。

另一方面，在獲取圖像特征時，提取的像素點隨機無序地散落在圖像各處，當某一個特征區(qū)域越大時，像素點落在其上的概率就越高，如圖3（b）所示，坐標系對角線上的高亮部分就是落在相同特征上的點對，即特征A近似于特征B。然而除開對角線外的高頻區(qū)域才是算法所關(guān)注的特征對，即特征值不同卻頻繁同時出現(xiàn)，這些點對就指向那些從屬同一個目標物體，卻擁有不同特征值的像素點。

2.2基于超像素的樣本點選取方法

為了使PMI邊界檢測算法的采樣過程更高效、更有目的性，避免采樣點過多地落在具有相同特征的區(qū)域，更大概率地落在算法關(guān)注的區(qū)域，避免樣點資源被隨機分配，使采樣點的選取更具有代表性，本文引入超像素的概念，利用超像素分割提供的圖像中層結(jié)構(gòu)信息，約束采樣點的提取，即隨機抽取的采樣點對中的兩個點必須分別落在相鄰的超像素中，即對式（3）中的A、B特征作了限制，使提取的A、B特征必須位于相鄰的超像素中，如式（6）：

其中SLabel是指超像素分割后位于不同超像素的像素點擁有不同的標簽。如圖4（b）中可看到，原本位于同一個超像素內(nèi)的像素點對近似屬于相同特征，利用提出的基于超像素的PMI檢測算法規(guī)定位置信息后，采樣點對中的兩個像素點必須分別位于相鄰不同超像素內(nèi)，如圖4（c）中所示，可知這些點有時候仍具有相同特征，有時會取到不同特征。

這樣一來，就把本應(yīng)落在同一超像素中的點對均勻地分布在了像素塊之間，克服了采樣點過程中的隨機性，降低了具有相同特征的采樣點對的超高頻率（即PMI模型對角線上高占比部分），增加了非相同特征點對的總占比，也就是將采樣點資源重新分配，適當減少了分配給相同特征的采樣點，同時把這部分樣點資源平均分配給了其他不相同特征間的候選區(qū)域。這種采樣方式當降低總采樣點數(shù)目時，由于樣點資源少，所以樣點的分布對邊界檢測的結(jié)果影響更大。

2.3基于超像素的PMI邊界檢測算法流程

上述邊界檢測算法在具體實現(xiàn)時，需要利用超像素分割作為圖像的預處理步驟，分割結(jié)果是給圖像中的每一個像素點分配一個標簽（Label）用來標識當前像素應(yīng)屬于哪一個超像素。算法中利用隨機森林決策樹提供數(shù)值預測，隨機森林具有訓練速度快、能夠處理高維數(shù)據(jù)、并行化容易、實現(xiàn)簡單等優(yōu)點為PMI邊界檢測算法提供了高效準確的分類決策。

基于超像素的PMI邊界檢測算法實現(xiàn)流程如下：

輸入圖像I；

輸出圖像I的邊界概率圖。

步驟1初始化SLIC超像素分割[14]環(huán)境，利用該算法對圖像I進行預處理，為圖像中每一個像素點賦一個超像素標簽（Label）。

步驟2在不同特征域中對圖像進行特征提取，即在LAB顏色空間和其對角協(xié)方差矩陣域中提取每個像素點的相應(yīng)特征值，該值是一個三維向量。

步驟3計算圖像中所有相距在一定像素距離內(nèi)，且Label值不同的像素點對，并從中隨機選取N對。

步驟4N個像素對共有2N個像素點，根據(jù)這些像素點及其特征向量利用核密度估計分別計算出每一種特征的概率P（x），根據(jù)式（2）計算任意兩個特征間的聯(lián)合分布概率P（A，B）。

步驟5根據(jù)式（3）和步驟4的結(jié)果，計算任意兩個特征間的PMI（A，B）值。

步驟6根據(jù)步驟4中獲得的所有特征以及步驟5中獲得的任意兩個特征間的PMI值構(gòu)建隨機森林決策樹，用以決策在當前圖像I中，任意兩個特征間的PMI值。

步驟7將圖像中任意兩個像素點的特征向量輸入決策樹，輸出當前兩個像素點間的PMI值用以衡量兩個像素的相似度，該值越大說明當前兩像素越相似，并以此構(gòu)建相似度矩陣。

步驟8將相似度矩陣輸入分層分割算法[10]框架（OWT-UCM）獲得邊界概率圖。分層分割算法框架是指將相似度矩陣利用有向分水嶺變換（Oriented Watershed Transform，OWT）算法先分成若干區(qū)域，再利用超度量輪廓圖（Ultrametric Contour Map，UCM）算法進行區(qū)域合并，得到最終結(jié)果。

在PMI邊界檢測算法中需要利用采樣點的特征和相應(yīng)的PMI值訓練隨機森林決策樹，因此采樣點的數(shù)目和覆蓋范圍會影響其提取的特征數(shù)，需要足夠多的采樣點才能保證圖像中的特征都被提取出來。原始的PMI邊界檢測算法采樣點完全隨機分配，當某一特征占比很大時，落入其中的采樣點概率會出現(xiàn)飽和，而小概率特征則可能出現(xiàn)被忽略的情況。

3實驗結(jié)果與分析

3.1實驗數(shù)據(jù)集及邊界檢測評價標準

實驗數(shù)據(jù)集為伯克利分割數(shù)據(jù)庫（Berkeley Segmentation Data Set，BSDS）[17]，該數(shù)據(jù)庫是無監(jiān)督的圖像處理領(lǐng)域中唯一的一個可針對邊界檢測結(jié)果進行統(tǒng)計且有真值（ground truth）的圖像庫，因此常被當作該領(lǐng)域的基準。該數(shù)據(jù)庫發(fā)展至今為BSDS500，有訓練數(shù)據(jù)集200張圖片，驗證數(shù)據(jù)集100張圖片，測試數(shù)據(jù)集200張圖片，對于每一張圖片都附有人工繪制的相應(yīng)真值。

該數(shù)據(jù)集通過遍歷盡量多的閾值計算出三個統(tǒng)計結(jié)果：全局最佳（Optimal Dataset Scale，ODS）、單圖最佳（Optimal Image Scale，OIS）和平均精準度（Average Precision，AP）。其中：ODS指數(shù)據(jù)庫所有圖像使用固定同一閾值時的最佳結(jié)果；OIS是對每一幅圖像使用針對當前圖像最佳閾值時的結(jié)果；AP表示查準率/查全率（Precision/Recall， PR）曲線（坐標軸縱為Precision，橫軸為Recall）下的面積。Precision指待測算法檢測出來的邊界是真邊界的占比，Recall指真正的邊界被檢測出來的部分占比。查準率和查全率必須同時考慮才能判定算法的優(yōu)劣，所以AP值是考慮兩個參數(shù)后給出的綜合評定標準，通常以該值為主要判定依據(jù)。該值越大說明算法的平均表現(xiàn)越好，真值的驗證結(jié)果為0.8，即AP值越接近0.8說明當前算法的運算結(jié)果越接近人工識別的結(jié)果。PMI邊緣檢測算法在該數(shù)據(jù)集上與近年來其他算法的比較如表1所示，其中分層分割算法（gPb-owt-ucm）[9-10]和結(jié)構(gòu)化森林邊界檢測算法（Structured Forests Edge，SE）[11]分別是目前無監(jiān)督邊界檢測和有監(jiān)督邊界檢測算法的最高水平。從表1可以看出，PMI邊界檢測算法作為無監(jiān)督的邊界檢測高于分層分割算法6個百分點，比當前最好的有監(jiān)督邊界檢測算法結(jié)構(gòu)化森林邊界檢測算法在AP值上仍高出1個百分點，達到0.79，非常逼近真值。

3.2超像素區(qū)域尺寸的選擇

基于超像素的PMI算法需要像素點落在不同的超像素上，所以超像素區(qū)域尺寸（region size）參數(shù)非常重要。若區(qū)域尺寸過大，會導致本應(yīng)落在相同特征區(qū)域的像素點被裁減得過多，相應(yīng)的PMI過低，最終相同特征的像素點不能融合；若區(qū)域尺寸過小，會導致裁減掉的冗余點太少，對其他非相同特征區(qū)域的影響不大，最終效果不佳。

利用BSDS500[17]中的訓練數(shù)據(jù)集來訓練超像素區(qū)域尺寸的取值，在采樣點數(shù)固定為4000時， 超像素區(qū)域尺寸不同對檢測結(jié)果的影響如表2所示。表2顯示，當超像素區(qū)域尺寸為4，即像素塊大小近似等于4像素×4像素時，算法取得了最優(yōu)的性能，因此本文采用該參數(shù)值進行邊界檢測。

3.3改進的方法與原始方法檢測結(jié)果比較

3.3.1定性評價

表3為原始PMI邊界檢測算法和本文算法在設(shè)置不同采樣點數(shù)目時各自的實驗結(jié)果對比。從表3中可以看出，無論輸入樣點參數(shù)為多少，本文算法的平均精準度都高于原算法，且在采樣點越少的情況下，效果越好、提升越明顯。在樣點數(shù)目僅為3500時，本文算法的AP值就已達到0.79，而原算法則需要采樣點數(shù)目為6000才能到達此結(jié)果，且改進的算法在6000點后采樣點資源已趨近飽和，測試結(jié)果變動不大，而原算法在6000點之后檢測結(jié)果仍跟隨采樣點數(shù)目的變動而浮動，魯棒性不強。

實驗使用的所有的測試圖都來自DSBS500中的檢測集，基于超像素的PMI邊界檢測算法與原始PMI邊界檢測算法的結(jié)果如圖5所示，采樣點數(shù)統(tǒng)一取1000。

當采樣點為1000時，原算法和改進算法的AP值均高于0.75，對圖像邊緣都能進行較完整地描述，且在1000采樣點時改進算法比原始算法平均精準度已高出約1.11個百分點。

從圖5可以看出，本文提出的基于超像素的PMI邊界檢測算法在采樣點數(shù)僅為1000時，仍能捕獲圖像中物體的細節(jié)信息，魯棒性更強。

4結(jié)語

針對PMI邊界檢測算法中采樣點隨機性高、存在無意義樣本的缺陷，本文提出一種結(jié)合超像素指導采樣過程的方法，在減少過多冗余點的同時，增加有效采樣點的占比，從而提升了該方法的平均精準度。實驗結(jié)果表明，在同樣的采樣條件下，本文提出的基于超像素的PMI邊界檢測算法的檢測結(jié)果始終優(yōu)于原始PMI邊界檢測算法，尤其當采樣點越少時，改進算法的提升越明顯。

本文通過對算法采樣過程的改進來提升邊界檢測的準確率和效率，而PMI抽象為圖像特征可直接提取成為圖像分割的依據(jù)，不需要預先獲得邊界信息。所以進一步的研究將融合PMI特征與其他全局幾何特征完成更高層次的圖像分割工作。

參考文獻：

[1]REN X， BO L. Discriminatively trained sparse code gradients for contour detection [C]// NIPS 2012： Proceedings of the 2012 Advances in Neural Information Processing Systems 25. Cambridge， MA： MIT Press， 2012： 593-601.

[2]張廣燕，王俊平，邢潤森，等.PSLIP新模型及在邊緣檢測和圖像增強中的應(yīng)用[J].電子學報，2015，43（2）：377-382. （ZHANG G Y， WANG J P， XING R S， et al. A new PSLIP model and its application in edge detection and image enhancement [J]. Acta Electronica Sinica， 2015， 43（2）： 377-382.）

[3]KOHLI P， LADICK L， TORR P H. Robust higher order potentials for enforcing label consistency [J]. International Journal of Computer Vision， 2009， 82（3）： 302-324.

[4]石美紅，李青，趙雪青，等.一種基于保角相位的圖像邊緣檢測新方法[J].電子與信息學報，2015，37（11）：2594-2600. （SHI M H， LI Q， ZHAO X Q， et al. A new approach for image edge detection based on conformal phase [J]. Journal of Electronics & Information Technology， 2015， 37（11）： 2594-2600.）

[5]PANTOFARU C， SCHMID C， HEBERT M. Object recognition by integrating multiple image segmentations [C]// ECCV 2008： Proceedings of the 10th European Conference on Computer Vision， LNCS 5304. Berlin： Springer-Verlag， 2008： 481-494.

[6]ROBERT L G. Machine perception of three-dimensional solids [J]. Optical and Electro-Optical Information Processing， 1965， 21（7）： 159-197.

[7]TORRE V， POGGIO T A. On edge detection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986， 8（2）： 147-163.

[8]何春，葉永強，姜斌，等.一種基于分數(shù)階次微積分模版的新型邊緣檢測方法[J].自動化學報，2012，38（5）：776-787. （HE C， YE Y Q， JIANG B， et al. A novel edge detection method based on fractional-order calculus mask [J]. Acta Automatica Sinica， 2012，38（5）：776-787.）

[9]ARBELEZ P， HARIHARAN B， GU C， et al. Semantic segmentation using regions and parts [C]// CVPR 2012： Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012： 3378-3385.

[10]ARBELEZ P， MAIRE M， FOWLKES C， et al. Contour detection and hierarchical image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（5）： 898-916.

[11]DOLLR P， ZITNICK C L. Structured forests for fast edge detection [C]// ICCV 13： Proceedings of the 2013 IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2013： 1841-1848.

[12]LIM J J， ZITNICK C L， DOLLR P. Sketch tokens： a learned mid-level representation for contour and object detection [C]// CVPR 2013： Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2013： 3158-3165.

[13]ISOLA P， ZORAN D， KRISHNAN D， et al. Crisp boundary detection using pointwise mutual information [C]// ECCV 2014： Proceedings of the 13th European Conference on Computer Vision， LNCS 8691. Berlin： Springer-Verlag， 2014： 799-814.

[14]LUCCHI A， SMITH K， RADHAKRISHNA A， et al. Supervoxel-based segmentation of mitochondria in EM image stacks with learned shape features [J]. IEEE Transactions on Medical Imaging， 2012， 31（2）： 474-486.

[15]ZHOU X， LI X， CHIN T-J， et al. Superpixel-driven level set tracking [C]//ICIP 2012： Proceedings of the 2012 IEEE International Conference on Image Processing. Piscataway， NJ： IEEE， 2012： 409-412.

[16]LIU L， XING J， AI H， et al. Semantic superpixel based vehicle tracking [C]// ICPR 2012： Proceedings of the 2012 21st International Conference Pattern Recognition. Piscataway， NJ： IEEE， 2012： 2222-2225.

[17]MARTIN D R， FOWLKES C， TAL D， et al. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics [C]// ICCV 2001： Proceedings of the 2001 8th IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2001， 2： 416-423.