基于余弦相似度的Graph Cuts序列圖像分割算法

劉璐

（沈陽航空航天大學計算機學院，沈陽 110000）

基于余弦相似度的Graph Cuts序列圖像分割算法

劉璐

（沈陽航空航天大學計算機學院，沈陽 110000）

傳統Graph Cuts算法容易出現漏分割、誤分割現象，分割效果有待提高，且需要人工交互分割效率不高。針對傳統算法的不足，提出基于余弦相似度的Graph Cuts序列分割圖像算法。使用最大余弦相似度構造能量函數的區域項，計算超像素與種子聚類區域的最大余弦相似度。使用余弦相似度和顏色相似度來構造邊界項，計算鄰域超像素的顏色和相對距離特征相似度。將該算法與傳統Graph Cuts算法進行分割結果比較精確率和召回率等均有提高，漏報率降和虛報率明顯降低。算法應用于序列圖像分割，減少人工交互，提高分割效率。

Graph Cuts算法；圖像分割；余弦相似度；序列圖像

0 引言

圖像分割這一技術自從發展以來，有很多系統的、科學的分割方法。20世紀90年代首次成功應用圖論理論在圖像分割的研究中，引起了學者們對于圖論理論及其應用的熱烈關注，目前在圖像分割、紋理合成、圖像恢復、圖像去噪、三維重構、運動目標檢測和立體匹配等圖像處理技術中都有廣泛應用。

1 基于圖論的分割算法研究現狀

Boykov等人[1]首次在圖像分割領域應用 Graph Cuts算法，構造出S/T圖，并用區域項和邊界項計算S/ T圖的邊的權值，最后通過最小化能量函數得到最小割，即得到分割結果。該算法優點是對噪聲不敏感，不容易出現過分割。不足之處是當前后背景顏色相近時，趨于較短分割，而且由于需要人工交互，所以對于多幅圖像分割處理起來效率不高，不能實現實時性。從Graph Cuts算法的出現就引起了研究人員對圖論分割的關注，對以后的圖論算法產生重要影響。

Rother等人[2]提出的基于高斯混合模型的Grab Cut算法，就是在Graph Cuts算法進行的改進，它通過不斷迭代的方式提高了參數估計的準確性，并且簡化了交互改善了用戶體驗。但是當選取的種子在區域外時，分割效果較差。2004年，Li Y等人[3]提出了Lazy snap?ping方法，利用Graph Cuts算法對圖像分割得到粗分割，然后通過邊界上的多邊形頂點進行調整編輯得到細分割，缺點是對于大規模圖像處理速度較慢，需要大量人工交互。文獻[4]描述了GCBAC算法，它結合了主動輪廓算法與Graph Cuts算法，分割效果要比單獨應用Graph Cuts算法好，但是該方法需要大量的訓練模板，算法復雜度高，而且過于依賴初始輪廓。Rother等人[5]提出的co-segmentation方法，將Grab Cut算法和SVM算法相結合，該方法在每一層迭代經過SVM算法學習特征后得到超像素，將超像素的相似特征作為Grab Cut算法的分割約束進行圖像分割，好處是只需要較少的交互，實現了無監督學習，但是算法復雜度高，時間消耗大。

本文對Graph Cuts算法進行研究并提出使用余弦相似度構造能量函數的區域項和邊界項，分別描述原始Graph Cuts算法和本文算法的基本原理，通過實驗對比驗證本文算法分割結果更準確，誤分割和漏分割的現象明顯減少，并且應用于多幅序列圖像分割，減少交互和算法時間。

2 Graph Cuts算法

Graph Cuts算法核心思想是，用戶通過人機交互對圖像中的目標和背景標記不同的標號，作為分割圖像的硬約束條件，然后建立相應的S/T圖，根據邊的權值構造合適的能量函數，利用最大流/最小割算法來計算最優化的全局代價函數，即求解S/T圖的最小割，從而實現圖像分割。

首先把圖像映射為S/T圖，除了有普通頂點還包含兩個終端頂點，分別為S源點和T匯點。S/T圖中有兩種邊，一種邊是n-links，由相鄰像素連接組成，另一種邊是t-links，由普通像素分別S源點和T匯點連接組成的邊。其中鄰域像素可以采用四鄰域或八鄰域方法。能量函數包含了兩個約束項，區域項R（A）與邊界項B（A），充分利用圖像的區域屬性和邊界屬性的信息，可以得到準確性更高的分割結果。邊的權值由能量函數的區域項和邊界項計算，能量函數通常有如下形式：

區域項R（A）用來評價給所有像素分配標號的情況，其定義如公式（2）所示。其中，Rp（Ap）表示為單個像素點p分配標號Ap的能量消耗。

邊界項B（A）反應的是圖像的光滑性約束，表示不同標號的相鄰像素點之間的代價，其定義如公式（3）所示。其中，B（p,q）可以看作為像素p和像素q之間不連續的懲罰項，δ（Ap,Aq）表示當相鄰像素p和q的標號相同時為1，相鄰像素的標號不同時為0。

在給所有邊賦權值后，構建出一個完整的S/T圖，然后通過最大流/最小割算法計算能量函數E（A）的最小值，得到最小割，割集將把S/T圖分割成兩個子圖S圖和T圖，即把圖像分割成目標和背景。

3 本文算法描述

3.1 預處理步驟

（1）讀入序列圖像文件，并保存序列圖像的編號；

（2）利用雙線性插值對圖像重采樣，調整圖像到統一大小，便于整理和分割序列圖像；

（3）對圖像進行高斯濾波平滑、亮度變換操作，使圖像的對比度增強，使待分割的目標更加突出；

（4）最后以序列編號來命名保存圖像，為序列圖像分割做準備。

3.2 余弦相似度

Graph cuts是一種把圖像分割問題看成像素標記問題的基于圖論算法。能量函數的區域項用于反映像素點分配標簽的特征相似度，邊界項用于反映相鄰像素間的特征相似度。像素的顏色特征和相鄰像素間的距離特征相結合，共同對能量函數的特征相似度產生影響。

傳統的Graph Cuts算法在建立邊界項B（A）時，用基于歐氏距離的懲罰項B（p,q）來表示相鄰像素的相似性的差異。歐氏距離（Euclidean distance）是距離度量，用于衡量向量在空間上存在的絕對距離，沒有考慮維度方向上的相似性。

余弦相似度（Cosine similarity）[6]衡量的是向量的相對距離，體現的是一個空間三維的概念。余弦相似度是一種相似度度量（Similarity measure），更注重維度之間的差異。本文采用余弦相似度構造能量函數的區域項和邊界項，從相對距離上衡量像素間的特征相似度。余弦相似度的值在[0,1]之間，也使得算法簡單高效。||?||表示向量的二范數，則兩個向量p和q的余弦相似度C定義為：

向量a與向量集B的最大余弦相似度（Max Co?sine similarity），其含義是取向量a與向量集B的每一個向量Bi的余弦相似度的最大值。最大余弦相似度MCS定義為：

3.3 基于余弦相似度的能量函數

利用分水嶺方法對圖像進行預分割，得到的圖像由許多個小區域組成。小區域內像素相鄰且特征相似，又稱為超像素。這些小區域大多保留了圖像分割的有效信息，且一般不會破壞圖像中物體的邊界信息。利用基于超像素的計算，在不損壞圖像特征信息的同時，達到降低算法的復雜度的目的。其中，Sp表示分水嶺后超像素的平均像素值。Lp∈{“obj”,”bkg”}表示超像素p被分為的標簽是目標或背景。

用戶對目標和背景交互后，使用FCM聚類算法，對目標和背景種子點集分別聚類，得到目標和背景種子點集的聚類區域的平均顏色。目標種子點集經過聚類后得到n個區域，每個聚類區域的平均像素值記作{Oi}，i=1，…，n。背景種子點集經過聚類后得到m個區域，每個聚類區域的平均像素值記作{Bj}，j=1，…，m。

本文使用最大余弦相似度MCS來構造區域項Rp，用來反映像素點分配標簽的特征相似度。當為像素點分配的標簽差異性越小，區域項的值越小。區域項Rp定義為：

其中，MCS（Sp,Oi）表示超像素與目標種子點聚類區域的最大余弦相似度，MCS（Sp,Bj）表示超像素與背景種子點聚類區域的最大余弦相似度，計算公式如下：

為像素分配為“obj”0標簽時，Rp（“obj”）表示該像素與背景種子區域的最大余弦相似度占全部種子區域的最大余弦相似度的值，反映的是被分配為目標的像素與背景種子區域的相似程度，即被分配為目標的像素的懲罰項。為像素分配為“bkg”標簽時，Rp（“bkg”）表示該像素與目標種子區域的最大余弦相似度占全部種子區域的最大余弦相似度的值，反映的是被分配為背景的像素與目標種子區域的相似程度，即被分配為背景的像素的懲罰項。

由公式表明，若當前像素屬于“obj”的概率更大時，Rp（“obj”）的值會更小；同理像素屬于“bkg”的概率更大時，Rp（“bkg”）的值會更小。

使用余弦相似度C、顏色相似度W來構造邊界項Bpq，用來反映相鄰像素間的特征相似度。當相鄰像素間的特征差異性越大，邊界項的值越小。邊界項Bpq的計算公式為：

其中，顏色相似度W用于衡量兩個像素的顏色特征的相似性。Sp和Sq表示鄰域超像素的平均像素值，二者差值的平方表示兩個鄰域超像素的顏色差異性。尺度因子σ用噪聲估計確定。再利用負對數exp（-x）使得鄰域超像素的顏色差異性越大，W（Sp,Sq）的值越小。顏色相似度W定義如下：

余弦相似度C用來衡量鄰域超像素的相對距離的相似程度，其定義如（12）所示。相鄰超像素的距離和方向特征的差異性越大，余弦相似度C越小。當鄰域超像素不屬于相同的區域（目標或背景）時，余弦相似度C最小。

邊界項Bpq綜合考慮了相鄰像素的顏色和相對距離特征，利用這些特征相似度，衡量相鄰像素間不連續性，體現了圖像的邊界信息。越靠近圖像的邊界部分（即相鄰像素越不連續），鄰域超像素的顏色和相對距離特征差異性越大，由公式可知顏色相似度W和余弦相似度C就越小，邊界項Bpq也就越小。

能量函數由區域項和邊界項組成，當像素都被正確分配標簽時，區域項的值最小，當邊界都被正確分割時，邊界項的值最小。能夠實現圖像被正確分割時，能量函數的值最小。

然后將圖像映射成S/T圖：圖像分水嶺預分割后的超像素映射為S/T圖的普通節點的集合P，目標種子點集和背景種子點集被FCM聚類分割后的小區域映射為S/T圖的S源點集和T匯點集。利用區域項和邊界項計算S/T圖中對應邊的權值，普通鄰域超像素的邊的權值使用邊界項Bpq計算，超像素與目標或背景種子區域的邊的權值使用區域項Rp計算。

使用最大流/最小割算法中的其中一種算法：雙向快速增廣路徑算法，該算法利用兩棵搜索樹從源點S到匯點T同時查找一條增廣路徑，算法速度快。利用雙向快速增廣路徑算法計算能量函數最小值，得到最

D（Lp,Lq）表示鄰域超像素的標簽若相同則計算邊界項，若不同邊界項就直接為0。用于判斷鄰域超像素是否屬于不同的區域。其定義如下：小割，從而實現圖像分割。

3.4 序列圖像分割算法

序列圖像的基本特點是后一張圖像與前一張圖像相似，但是有差別。基于此特點，序列圖像分割的核心思想是當前的圖像分割后的模板作為下一張圖像的種子點集。只有第一張圖像需要單獨分割，其余的序列圖像可以實現自動分割。算法流程是：

（1）對第一張圖像分割，使用本文提出的改進Graph Cuts算法得到分割后的模板，對模板腐蝕、膨脹操作得到第二張圖像的種子點集；

（2）對當前圖像分割，使用基于改進Graph Cuts算法，種子點是上一張圖像分割得到并經過形態學方法處理的模板；

（3）重復步驟（2）直到分割好全部序列圖像。

4 實驗結果及分析

本文的實驗數據的來源是LIDC-IDRI，一個公開的肺部影像數據庫，像素間距為0.6641，圖像間的序列間距為0.625。首先對多幅肺部序列圖像進行預處理，使得待分割的目標更突出，為之后的多幅序列圖像分割做準備。經過對238張圖像的預處理實驗，平均單張圖像預處理需要約0.09秒。圖1（a）表示使用鼠標對預處理后的圖像人工標記，用藍色的線標記背景種子點，紅色的線標記目標種子點。圖1（b）（c）為兩種算法的實驗結果可以看出本文算法的分割結果較好，對邊界的分割更準確，減少誤分割和漏分割的情況。

圖1

由基于區域的測度可以計算一系列的評價指標，用于評價分割結果的準確性等。評價指標有真正類率（TPR），計算的是正樣本被正確分割的概率，又稱召回率、查全率。假正類率（FPR），計算的是負樣本被錯誤分割為正樣本的概率，又稱虛報率。真負類率（TNR），計算的是負樣本被正確分割的概率，也稱特異性。假負類率（FNR），計算的是正樣本被錯誤分割為負樣本的概率，又稱漏報率。準確率（ACC），就是正負樣本分別被正確分割的概率。精確率（P），計算的是預測為正樣本占實際為正樣本的比例，又稱查準率。F1是精確率和召回率加權調和平均，當F1較高時則能說明分割算法的準確度比較高。

為了驗證實驗的有效性，本文的實驗數據有四組序列圖像，分別對四組實驗數據經過原始Graph cuts算法和基于余弦相似度的Graph cuts算法分割后，計算每組每張圖像經過兩種算法的評價指標，然后得到平均評價指標結果并計算本文算法相對于原始算法的環比增長率，如表1所示。

由表中的四組實驗數據可知本文提出的基于改進Graph cuts算法的分割算法與基于原始Graph cuts算法的分割算法相比，在真正類率、真負類率、準確率、F1值均有所提高，在假正類率（即虛報率）和假負類率（即漏報率）均明顯降低。由實驗驗證可得本文算法比原始Graph cuts算法的分割效果好，分割結果準確性提高，漏分割、誤分割情況明顯下降。

本文記錄下兩種算法分割的時間，基于本文算法的單幅圖像分割的平均時間約為4.8782秒，而基于原始Graph Cuts算法的單幅圖像分割的平均時間約4.4536秒，前者比后者多0.4246秒。

本文記錄下人工標記所需時間，單幅圖像標記的平均時間約29.4877秒。除了第一張圖像需要標記，本文算法可以為每張序列圖像省下約29秒，節省了大量的時間和人力，并提高了序列圖像分割的效率。

5 結語

通過實驗表明基于余弦相似度的Graph Cuts序列圖像分割算法分割效果較好，誤分割和漏分割的現象明顯減少；可以實現序列圖像分割，在保持良好分割效果的同時，提高序列圖像分割算法的效率。

基于余弦相似度的Graph Cuts序列圖像分割算法，對第一張圖像的種子點選取依賴性較強，對于不同的序列圖像種子點的選取需要作出調整。對于不同類型的圖像需要調整式（1）中λ參數和式（11）中σ參數的值。后續的研究工作可以針對以上兩點改進。

[1]Boykov Y,Jolly MP.Interactive Graph Cuts For Optimal Boundary&Region Segmentation of Objects in N-D Images[C].IEEE International Conference on Computer Vision，2001：105-112.

[2]Rother C,Kolmogorov V,Blake A.“Grabcut”-Interactive Foreground Extraction Using Iterated Graph Cuts[J].ACM SIGGRAPH,2004, 23（3）:309-314.

[3]Y Li,J Sun,CKTang,HY Shum.Lazy Snapping[J].ACM SIGGRAPH,2004,23（3）:303-308.

[4]Xu N,Bansal R,Ahuja N.Object Segmentation Using Graph Cuts Based Active Contours[C].Computer Vision and Image Understanding，2007，107（3）：210-224.

[5]Rother C,Minka T P,Blake A,et al.Cosegmentation of Image Pairs by Histogram Matching-Incorporating a Global Constraint into MRFs[C].IEEE Computer Society Conference on Computer Vision&Pattern Recognition，2006，1：933-1000.

[6]HV Nguyen,Li Bai.Cosine Similarity Metric Learning for Face Verification[C].Asian Conference on Computer Vision，2010，6493:709-720.

Graph Cuts Sequence Image Segmentation Algorithm Based on Cosine Similarity

LIU Lu

（School of Computer Science,Shenyang Aerospace University，Shenyang 110000）

Traditional Graph Cuts segmentation algorithm may bring leakage segmentation and error segmentation.The segmentation effect of the algo?rithm needs to be improved,and the algorithm needs human interaction with low segmentation efficiency.In order to improve the shortcom?ings of traditional algorithms,proposes the Graph Cuts algorithm of sequence image segmentation based on cosine similarity.Constructs the region term of the energy function by using the maximum cosine similarity,and calculates the maximum cosine similarity between the su?per-pixel and the seed clustering region.Constructs the boundary term of the energy function by using the cosine similarity and color simi?larity,and calculates the color and the relative distance feature similarity of neighborhood super-pixel.This algorithm is compared with the traditional Graph Cuts algorithm,the accuracy and recall rate are improved,the false positive rate and the false negative rate is reduced ob?viously.Applies this algorithm to sequence image segmentation,which reduces the manual interaction and improves the segmentation effi?ciency.

劉璐（1992-），女，遼寧撫順人，碩士，研究方向為醫學影像處理

2017-02-22

2017-05-20

1007-1423（2017）15-0020-05

10.3969/j.issn.1007-1423.2017.15.005

Graph Cuts Algorithm;Image Segmentation;Cosine Similarity;Sequence Image