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

劉勝男　寧紀鋒

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

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

中圖分類號：TP391.41

文獻標志碼：A

0引言

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

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

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

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

1基于PMI的邊界檢測算法

1.1PMI

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

1.2PMI在圖像處理中的應用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入圖像I；

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

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

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

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

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

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

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

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

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

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

3實驗結果與分析

3.1實驗數據集及邊界檢測評價標準

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

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

3.2超像素區域尺寸的選擇

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

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

3.3改進的方法與原始方法檢測結果比較

3.3.1定性評價

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

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

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

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

4結語

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

本文通過對算法采樣過程的改進來提升邊界檢測的準確率和效率，而PMI抽象為圖像特征可直接提取成為圖像分割的依據，不需要預先獲得邊界信息。所以進一步的研究將融合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新模型及在邊緣檢測和圖像增強中的應用[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]何春，葉永強，姜斌，等.一種基于分數階次微積分模版的新型邊緣檢測方法[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.