應用耦合對象相似度的閾值分割方法研究

武玉坤

（浙江郵電職業技術學院管理與信息學院紹興312016）

應用耦合對象相似度的閾值分割方法研究

武玉坤

（浙江郵電職業技術學院管理與信息學院紹興312016）

傳統Otsu算法及其改進算法將類間方差設定成最優閾值，從而使得針對直方圖分布區別的圖像分割效果產生較大區別，論文提出應用耦合對象相似度來進行閾值分割的改進方法來解決。首先，構建模型描述耦合對象相似度，模型能夠綜合考慮各種對象屬性及屬性之間關聯，以高準確度和低復雜度來描述耦合對象關系；其次，應用耦合對象相似度來替代傳統Otsu算法的類間方差作為新條件，將所選閾值劃分成每個類看成是耦合對象相似度模型中的對象，每個類都有概率和灰度均值兩種屬性，通過計算類間相似度并在類間相似度最小時獲取最優閾值。實驗結果表明，應用耦合對象相似度執行閾值分割算法能夠有效提高描述類間差異精確度和圖像分割效果，對于單分布與雙峰顯著且底部平坦的特征圖像具有較強適應能力。

圖像分割；類間方差；耦合對象相似度；類間相似度；最優閾值

Class NumberTP391

1 引言

圖像分割思想是將圖像描述成一些連通區域集合，圖像特征在不同連通區域中表現出不同差異性，在相同連接區域表現出相似性，可以把圖像中具有特殊涵義的不同區域區分出來。圖像分割結果是從圖像處理到圖像分析的關鍵中間步驟，也是特征提取和目標識別的前提［1］。現有圖像分割主要有基于區域、閾值、邊緣以及特定理論的方法。其中，閾值法由于實現簡單且計算速度快等特點，在圖像分割應用中處于核心地位［2］。閾值分割方法已有多種類型，如：雙峰法、最大類間方差法（Otsu）、最小誤差法，最大熵法等。

傳統Otsu算法應用閾值把像素點分為目標與背景，用類間方差來描述類間差異，通過計算目標與背景之間的最大類間方差獲取分割閾值。在Otsu基礎上，國內外學者提出改進算法（如：二維Otsu［3］、三維Otsu［4］）。但是，這些新算法仍然是以類間方差作為確定最優閾值的唯一依據，這使得它針對直方圖分布不同的圖像分割效果區別較大。因此，研究一種有效描繪類間差異的衡量標準是值得深究的重要問題。

目前，耦合對象相似度（Coupled Object Similarity，COS）作為相似性度量方法，逐漸成為研究熱點，并且多數集中在聚類與分類研究領域［5～6］。基于非獨立同分布的耦合關系分析已經成功應用于耦合聚類、耦合行為信息、項目推薦、推薦系統［5～9］。

本文采用耦合對象相似度代替類間方差作為最優閾值的確認依據。最優閾值通過求解最小耦合對象相似度獲得。耦合對象相似度作為相似性度量方法有其優點，它能將非獨立同分布的個體關聯起來，兼顧同一特征內部耦合屬性值相似度（Intra-coupled Attribute Value Similarity，IaAVS）和特征間耦合屬性值相似度（Inter-coupled Attribute Value Similarity，IeAVS）［5］。耦合對象相似度能夠充分考慮類屬性之間關系，以較高準確度和較低算法復雜度來獲取對象間關聯關系。這種新的閾值分割方法將能夠更好地描繪兩個類間差異性，有利于找到更加合適的最優閾值，提高圖像閾值分割的準確率。

2 耦合對象相似度

如今應用最廣泛的相似度度量方法是皮爾遜相關系數法（Pearson's Correlation Coefficient），它以變量之間存在線性相關性作為前提條件［10］，并沒有考慮屬性間關聯性。實際上，數據屬性間存在一定關聯性，它們不是相互獨立的。在描繪兩個對象之間相似度時，要充分考慮到對象的各種屬性自身以及屬性之間的關系，本文引入耦合對象相似度度量方法，它由同一特征內部耦合屬性值相似度和特征間耦合屬性值相似度構成。它能夠相對準確地描述對象屬性之間的非線性關系，全面地獲取對象之間的關聯關系［7～8］。

2.1 特征內耦合相似度

將屬性值aj擴展成E-1個屬性值：2，3，…，E，其中，p表示屬性值aj的p次冪。

則數值型屬性aj的內耦合關系可表示為E×E的內耦合矩陣RIa() aj，式（1）表述如下：

其中，θpq(j)=Cor(＜aj＞p，＜aj＞q)是屬性＜aj＞p和＜aj＞q的皮爾遜相關系數。

設兩個屬性aj和ak的皮爾遜相關系數為

其中，fj(ui)，fk(ui)分別表示對象ui在屬性j和k上的屬性值，μj和μk分別表示屬性aj和ak的均值。

2.2 特征間耦合相似度

設共有n個屬性值，將每個屬性值aj都擴展成E-1個屬性值：2、3、…、E，其中，p表示屬性值aj的p次冪。

則數值型屬性aj與屬性ak及屬性（pk≠j）的間耦合關系可表示為大小為E×（E×（n-1））的矩

其中，{ak}k≠j={ak1，…akn-1}是除屬性aj以外的其他屬性集合；ηpq(j|ki)=Cor(＜aj＞p，＜aki＞q)即屬性＜aj＞p和＜aki＞q的皮爾遜相關系數。

2.3 耦合對象相似度

設fn，E(um)表示對象um在屬性＜an＞E上的屬性值。設初始屬性列集合為A={a1，…，an}，擴展屬性列集合為A?={＜a1＞1，…，＜a1＞E，…，＜an＞1，…，＜an＞E}。

利用式（4）求得一個1×E大小的向量：

其中，w=［1（/1！），1（/2！），…1（/E！）］是一個1×E的向量，[w，w，…，w]是由n-1個w組成的1×（E×（n-1））的向量，⊙是矩陣的Hadamard積，?即簡

集合為

用得到的1×E的向量um(aj|A?，E)更新對象um在屬性＜aj＞E上的屬性值，um(aj|A?，E)=[f′j，1(um)，f’′j，2(um)，…，f′j，E(um)]，f′n，E(um)表示對象um在屬性＜an＞E上的新屬性值。

利用耦合關系公式已重構出樣本值便可在重構出的耦合表示數據基礎上，計算得到不同樣本之間的歸一化歐氏距離來衡量樣本的相似性。

3 基于耦合對象相似度的閾值分割方法

假設閾值為k，圖像被閾值分為C1和C2兩個類型，本文將每個類看作是耦合對象相似度模型中的對象，每個類都有類的概率和灰度均值兩種屬性，最優閾值在類間差異最大時得到，也可以看成是在類間相似度最小時得到，故本文采用耦合對象相似度來替代類間方差，作為最優閾值確定的依據具有合理性，并通過提高類間差異的描繪精度來尋找更為匹配的最優閾值。

基于耦合對象相似度的閾值分割算法流程圖如圖1所示。

3.1 類的概率和灰度均值的計算

在待處理圖像灰度范圍G={0，1，2，…，L-1}內選擇閾值k，將圖像分為兩類C1和C2。其中，灰度值在范圍［0，k］內的所有像素歸為C1，灰度值在范圍［k+1，L-1］內所有像素歸為C2。灰度值為i的像素出現的概率pi為

圖1 基于耦合對象相似度的閾值分割算法流程圖

其中，ni表示灰度級為i(i∈G)的像素數目，n表示像素總數。

根據式（6）和式（7）計算類C1和C2的概率w1，w2和灰度均值x1，x2。

類C1和C2的概率公式：類C1和C2的灰度均值公式：

3.2 類的屬性的設定和擴展

將類C1和類C2作為兩個對象，類的概率（W）和灰度均值（X）作為對象的屬性。類的屬性信息表如表1所示。

表1 類的屬性信息表

根據文獻［10］，將每個原屬性值擴展出E-1個屬性值，參數E越大相似性的衡量效果越精確，當E>3之后趨于穩定，故本文取E=3。擴展屬性信息表如表2所示。

表2 類的擴展屬性信息表

3.3 皮爾遜相關系數矩陣、內耦合矩陣和間耦合矩陣的求解

根據式（2）求出屬性W，W2，W3，X，X2，X3中任意兩個屬性之間的皮爾遜相關系數，構成皮爾遜相關系數矩陣（Correlation Matrix），如表3所示。

表3 皮爾遜相關系數矩陣

根據式（1）和式（3）分析特征內耦合相似度和間耦合相似度與皮爾遜相關系數矩陣的關系，用矩陣形式對內耦合矩陣和間耦合矩陣加以理解，可知在皮爾遜相關系數矩陣中即可取到內耦合矩陣和間耦合矩陣，如圖2所示。對角線上的2個3×3的矩陣分別是類的概率屬性W和類的灰度均值屬性X的內耦合矩陣RIa(W)和RIa(X)。由屬性W，W2，W3對應的三行和X，X2，X3對應的三列構成W的間耦合矩陣RIe(W)，由屬性X，X2，X3對應的三行和W，W2，W3對應的三列構成X的間耦合矩陣RIa(X)。綜上，由皮爾遜相關系數矩陣可得到2個內耦合矩陣（圖中深灰色部分）和2個間耦合矩陣（圖中淺灰色部分）。

圖2 皮爾遜相關系數矩陣與內耦合和間耦合矩陣的關系

3.4 耦合表示數據的重構

根據式（4）計算耦合對象相似度，用得到的1× 3的向量Cj(aj|A?，3)（i=1，2且aj=W，X）構造新的信息表，如表4所示。

表4 耦合關系重構的信息表

將1×3的向量Ci(aj|A?，3)寫成如下形式：

其中f′j，1(Ci)，f′j，2(Ci)，f′j，3(Ci)是向量Ci(aj|A?，3)的3個元素。將表4中的向量Ci(aj|A?，3)展開，可以表示成表5所示的形式。

表5 耦合關系重構的信息表

3.5 歸一化歐氏距離的計算

根據重構出的耦合表示數據，在表5的基礎上，采用歸一化歐氏距離的處理方法計算出當前閾值k下類C1和C2之間的相似性。

歸一化歐氏距離的計算步驟如下：

1）計算每個屬性列的標準差std：std（W），std（W2），std（W3），std（X），std（X2），std（X3）。

2）計算類C1和C2（兩行）的歸一化歐氏距離，作為兩類之間的相似性的度量。類C1和C2的差異性、相似性以及距離之間的關系如式（9）所示。

其中，difference(C1，C2)表示類C1和C2的差異性，similarity(C1，C2)表示類C1和C2的相似性。由式（9）可知，類間距離dist(C1，C2)越大，類C1和C2之間的相似性就越小，類間差異就越大，分割效果就越好。

4 實驗結果與分析

為了驗證本文算法的有效性，分別應用本文算法、傳統Otsu算法、二維Otsu和最大熵閾值分割算法對圖像進行分割，參照手工標注分割結果比較分割效果和分割性能，進行有監督評價。算法實驗環境為：Windows 7系統，2.20 GHz處理器，4G內存，編程環境為Visual Studio 2010。圖像方面選擇分辨率為500×344的常用分割圖像。本文選取不同直方圖分布的圖像分別進行分割實驗。實驗中，根據文獻［10］參數E取3。

為了定量分析分割效果，本文以信息變化指數（variation of information，VOI）、全局一致程度誤差（Global Consistency Error，GCE）和誤分類誤差（Misclassification error，ME）作為衡量標準進行定量分析。它們從各自不同的角度反映了待評價的分割結果與手工分割結果（ground truth images）之間的相似度或距離［11～12］。

信息變化指數（variation of information，VOI）：為了衡量兩個分割結果的差異，該指標在已給定其中一個分割結果時，通過計算另一個分割結果的平均條件熵（conditional entrop）來實現。如式（10）所示。

其中，將算法分割結果圖像記為隨機變量C1，參考分割圖像記為隨機變量C2，MI()C1，C2表示兩種分割結果C1和C2之間的互信息，H()C1和H()C2分別代表聚類C1和C2的熵。VOI的取值范圍是［0，+∞），分割效果的精確程度隨VOI值的減小而增大［11］。

全局一致程度誤差（Global Consistency Error，GCE）：該指標用來衡量一個分割結果能夠被看作是由另一個分割結果細化之后得到的程度。GCE的取值范圍為［0，1］，該值越接近于0，表明待評價的分割結果越好。如式（11）所示。用來描述S1，S2分割塊在像素點pi上的差異，R(S，pi)表示S中包含像素pi的集合，|??·??|用來求該集合像素點的個數，“”表示集合差。

誤分類誤差（Misclassification error，ME）：反映了背景像素被錯誤劃分到前景區域的比例，或者是前景像素被錯分到背景區域的比例。具體公式如式（12）所示。

其中，BO和FO是手工標注分割圖像中的背景和前景，是由研究者經觀察人工制作而成，BT和FT是待評價分割結果中的背景和前景，∩為取交操作，||??·??用來統計各部分像素點的個數。ME的取值范圍為［0，1］，當ME=0時，表示沒有誤分割，當ME=1時，表示完全錯誤分割。該值越趨近于0，分割效果越好。

針對不同的直方圖分布的圖像進行了實驗。從圖3的結果可以看出：針對直方圖單一分布的圖像（a1）和（c1），Otsu有把目標當成背景現象，對目標大小敏感，不能準確地把微小的目標從背景中分割出來。二維Otsu對于（a1）中小飛機的內部也有劃分成背景的現象，對于（c1）中的背景天空處理得不好。最大熵對目標大小不敏感，但是對于（c1）中飛機邊緣處理得不清晰。而本文算法明確地分離出了目標和背景，目標內部的均勻性較好，邊緣輪廓比較清晰；針對直方圖雙峰分布的圖像（b1），Otsu和二維Otsu的分割結果中內部均勻性不是很好，有誤分割的現象。最大熵方法的背景分割效果不如其他算法。而本文算法相比之下分割效果較好。

圖3 實驗分割效果圖

對（a1）、（b1）、（c1）三幅圖像進行分割后，參照手工標注分割圖像求出信息變化指數（VOI）、全局一致程度誤差（GCE）和誤分類誤差（ME）分別如表6～表8所示。

從表中數據來看，對于圖像（a1）、（b1），Otsu與二維Otsu在三種評價指標的數值上相差不大，二維Otsu更優于Otsu。最大熵分割算法的三種指標的值都略大于Otsu和二維Otsu，分割效果有所不及，本文算法與傳統的Otsu、二維Otsu、最大熵閾值分割方法相比都有更小的VOI、GCE、ME值；對于圖像（c1），本文算法有最小的VOI、GCE、ME值，效果最好，其次是最大熵分割算法，Otsu和二維Otsu值很相近，均大于本文算法和最大熵算法。

表6 四種算法的VOI值比較

表7 四種算法的GCE值比較

表8 四種算法的ME值比較

5 結語

本文提出了一種基于耦合對象相似度的閾值分割方法。鑒于耦合對象相似度是一種有效的相似性度量方法，將其用來替換類間方差，作為最優閾值確定的依據。實驗結果表明，這種新的閾值分割方法能夠更好地刻畫兩個類間差異性，提高了圖像閾值分割的準確率。本文算法簡單有效，對于單一分布，雙峰明顯且谷底平坦的圖像具有適應能力。在實際應用中具有更好實用價值。

［1］CHARALABOPOULOS A.Face recognition approach based on rank correlation of Gabor-filtered images［J］. Pattern Recognition，2002，35（6）：1275-1289.

［2］CAO Chen，HOU Qiming，ZHOU Kun.Displaced dynamic expression regression for real-time facial tracking and animation［J］.ACM Transactions on Graphics，2014，33（4）：1-10.

［3］Tian Ye，Zhang Jin-wen，Zhao Guang-zhou.New image segmentation method based on threshold correction of two dimensional Otsu［J］.Computer&Digital Engineering，2012，40（5）：104-107.

［4］Jing X J，Li J，Liu Y.Image segmentation based on 3-D maximum between-cluster variance［J］.Acta Electronica Sinica，2003，31（9）：1281-1285.

［5］Wang C，Cao L，Wang M，et al.Coupled nominal similarity in unsupervised learning［C］//Proceedings of the 20th ACM international conference on Information and knowledge management.ACM，2011：973-978.

［6］Cao L.Nonnidness learning in behavioral and social data［J］.The Computer Journal，2014，57（9）：1358-1370.

［7］Cao L，Ou Y，Yu P S.Coupled behavior analysis with ap-plications［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（8）：1378-1392.

［8］Yu Y，Wang C，Gao Y，et al.A coupled clustering approach for items recommendation［C］//Advances in Knowledge Discovery and Data Mining.Springer Berlin Heidelberg，2013：365-376.

［9］Li F，Xu G，Cao L，et al.CGMF：coupled group-based matrix factorization for recommender system［C］//Web Information Systems Engineering-WISE 2013.Springer Berlin Heidelberg，2013：189-198.

［10］Wang C，She Z，Cao L.Coupled attribute analysis on numerical data［C］//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence.AAAI Press，2013：1736-1742.

［11］Sharma M，Chouhan V.Objective Evaluation Parameters of Image Segmentation Algorithms［J］.International Journal of Engineering and Advanced Technology，2012，24（10）：2249-8958.

［12］Sathya B，Manavalan R.Image segmentation by clustering methods：performance analysis［J］.International Journal of Computer Applications，2011，29（11）：1100-1106.

Threshold Segmentation Algorithm Research Used on Coupled Object Similarity

WU Yukun
（School of Management and Information，Zhejiang Post and Telecommunication College，Shaoxing312016）

Since the Otsu method and most of its improved methods take between-class variance as the foundation of picking threshold and the great difference of image segmentation results for different histogram distribution images，a new threshold segmentation algorithm which based on coupled object similarity is proposed in this paper.Firstly，a model of coupled object similarity is introduced，which can take both the relationship of the various attributes of the objects itself and the relationship between the properties into account，and can capture the relationships between the objects with high accuracy and low algorithm complexity.Secondly，between-class variance in the Otsu method is replaced by coupled object similarity to pick threshold，each class distinguished by the selected threshold is regarded as an object in the model of coupled object similarity，each class has two attributes，the probability of class and gray mean.Similarity between classes is calculated，and the optimal threshold value is obtained according to the minimum of similarity between classes.The experiments can prove that the proposed algorithm can measure the difference of classes at a higher accuracy and obtain better segmentation results.

image segmentation，between-class variance，coupled object similarity，between-class similarity，optimal threshold

TP391

10.3969/j.issn.1672-9722.2017.06.037

2016年12月8日，

2017年1月28日

國家自然科學基金青年項目（編號：61602059）；全國教育信息技術規劃課題（編號：126240629）資助。

武玉坤，男，碩士，講師，研究方向：模式識別與圖像處理，云計算。