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

劉璐

（沈陽(yáng)航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽(yáng) 110000）

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

劉璐

（沈陽(yáng)航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽(yáng) 110000）

傳統(tǒng)Graph Cuts算法容易出現(xiàn)漏分割、誤分割現(xiàn)象，分割效果有待提高，且需要人工交互分割效率不高。針對(duì)傳統(tǒng)算法的不足，提出基于余弦相似度的Graph Cuts序列分割圖像算法。使用最大余弦相似度構(gòu)造能量函數(shù)的區(qū)域項(xiàng)，計(jì)算超像素與種子聚類區(qū)域的最大余弦相似度。使用余弦相似度和顏色相似度來(lái)構(gòu)造邊界項(xiàng)，計(jì)算鄰域超像素的顏色和相對(duì)距離特征相似度。將該算法與傳統(tǒng)Graph Cuts算法進(jìn)行分割結(jié)果比較精確率和召回率等均有提高，漏報(bào)率降和虛報(bào)率明顯降低。算法應(yīng)用于序列圖像分割，減少人工交互，提高分割效率。

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

0 引言

圖像分割這一技術(shù)自從發(fā)展以來(lái)，有很多系統(tǒng)的、科學(xué)的分割方法。20世紀(jì)90年代首次成功應(yīng)用圖論理論在圖像分割的研究中，引起了學(xué)者們對(duì)于圖論理論及其應(yīng)用的熱烈關(guān)注，目前在圖像分割、紋理合成、圖像恢復(fù)、圖像去噪、三維重構(gòu)、運(yùn)動(dòng)目標(biāo)檢測(cè)和立體匹配等圖像處理技術(shù)中都有廣泛應(yīng)用。

1 基于圖論的分割算法研究現(xiàn)狀

Boykov等人[1]首次在圖像分割領(lǐng)域應(yīng)用 Graph Cuts算法，構(gòu)造出S/T圖，并用區(qū)域項(xiàng)和邊界項(xiàng)計(jì)算S/ T圖的邊的權(quán)值，最后通過最小化能量函數(shù)得到最小割，即得到分割結(jié)果。該算法優(yōu)點(diǎn)是對(duì)噪聲不敏感，不容易出現(xiàn)過分割。不足之處是當(dāng)前后背景顏色相近時(shí)，趨于較短分割，而且由于需要人工交互，所以對(duì)于多幅圖像分割處理起來(lái)效率不高，不能實(shí)現(xiàn)實(shí)時(shí)性。從Graph Cuts算法的出現(xiàn)就引起了研究人員對(duì)圖論分割的關(guān)注，對(duì)以后的圖論算法產(chǎn)生重要影響。

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

本文對(duì)Graph Cuts算法進(jìn)行研究并提出使用余弦相似度構(gòu)造能量函數(shù)的區(qū)域項(xiàng)和邊界項(xiàng)，分別描述原始Graph Cuts算法和本文算法的基本原理，通過實(shí)驗(yàn)對(duì)比驗(yàn)證本文算法分割結(jié)果更準(zhǔn)確，誤分割和漏分割的現(xiàn)象明顯減少，并且應(yīng)用于多幅序列圖像分割，減少交互和算法時(shí)間。

2 Graph Cuts算法

Graph Cuts算法核心思想是，用戶通過人機(jī)交互對(duì)圖像中的目標(biāo)和背景標(biāo)記不同的標(biāo)號(hào)，作為分割圖像的硬約束條件，然后建立相應(yīng)的S/T圖，根據(jù)邊的權(quán)值構(gòu)造合適的能量函數(shù)，利用最大流/最小割算法來(lái)計(jì)算最優(yōu)化的全局代價(jià)函數(shù)，即求解S/T圖的最小割，從而實(shí)現(xiàn)圖像分割。

首先把圖像映射為S/T圖，除了有普通頂點(diǎn)還包含兩個(gè)終端頂點(diǎn)，分別為S源點(diǎn)和T匯點(diǎn)。S/T圖中有兩種邊，一種邊是n-links，由相鄰像素連接組成，另一種邊是t-links，由普通像素分別S源點(diǎn)和T匯點(diǎn)連接組成的邊。其中鄰域像素可以采用四鄰域或八鄰域方法。能量函數(shù)包含了兩個(gè)約束項(xiàng)，區(qū)域項(xiàng)R（A）與邊界項(xiàng)B（A），充分利用圖像的區(qū)域?qū)傩院瓦吔鐚傩缘男畔?，可以得到?zhǔn)確性更高的分割結(jié)果。邊的權(quán)值由能量函數(shù)的區(qū)域項(xiàng)和邊界項(xiàng)計(jì)算，能量函數(shù)通常有如下形式：

區(qū)域項(xiàng)R（A）用來(lái)評(píng)價(jià)給所有像素分配標(biāo)號(hào)的情況，其定義如公式（2）所示。其中，Rp（Ap）表示為單個(gè)像素點(diǎn)p分配標(biāo)號(hào)Ap的能量消耗。

邊界項(xiàng)B（A）反應(yīng)的是圖像的光滑性約束，表示不同標(biāo)號(hào)的相鄰像素點(diǎn)之間的代價(jià)，其定義如公式（3）所示。其中，B（p,q）可以看作為像素p和像素q之間不連續(xù)的懲罰項(xiàng)，δ（Ap,Aq）表示當(dāng)相鄰像素p和q的標(biāo)號(hào)相同時(shí)為1，相鄰像素的標(biāo)號(hào)不同時(shí)為0。

在給所有邊賦權(quán)值后，構(gòu)建出一個(gè)完整的S/T圖，然后通過最大流/最小割算法計(jì)算能量函數(shù)E（A）的最小值，得到最小割，割集將把S/T圖分割成兩個(gè)子圖S圖和T圖，即把圖像分割成目標(biāo)和背景。

3 本文算法描述

3.1 預(yù)處理步驟

（1）讀入序列圖像文件，并保存序列圖像的編號(hào)；

（2）利用雙線性插值對(duì)圖像重采樣，調(diào)整圖像到統(tǒng)一大小，便于整理和分割序列圖像；

（3）對(duì)圖像進(jìn)行高斯濾波平滑、亮度變換操作，使圖像的對(duì)比度增強(qiáng)，使待分割的目標(biāo)更加突出；

（4）最后以序列編號(hào)來(lái)命名保存圖像，為序列圖像分割做準(zhǔn)備。

3.2 余弦相似度

Graph cuts是一種把圖像分割問題看成像素標(biāo)記問題的基于圖論算法。能量函數(shù)的區(qū)域項(xiàng)用于反映像素點(diǎn)分配標(biāo)簽的特征相似度，邊界項(xiàng)用于反映相鄰像素間的特征相似度。像素的顏色特征和相鄰像素間的距離特征相結(jié)合，共同對(duì)能量函數(shù)的特征相似度產(chǎn)生影響。

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

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

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

3.3 基于余弦相似度的能量函數(shù)

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

用戶對(duì)目標(biāo)和背景交互后，使用FCM聚類算法，對(duì)目標(biāo)和背景種子點(diǎn)集分別聚類，得到目標(biāo)和背景種子點(diǎn)集的聚類區(qū)域的平均顏色。目標(biāo)種子點(diǎn)集經(jīng)過聚類后得到n個(gè)區(qū)域，每個(gè)聚類區(qū)域的平均像素值記作{Oi}，i=1，…，n。背景種子點(diǎn)集經(jīng)過聚類后得到m個(gè)區(qū)域，每個(gè)聚類區(qū)域的平均像素值記作{Bj}，j=1，…，m。

本文使用最大余弦相似度MCS來(lái)構(gòu)造區(qū)域項(xiàng)Rp，用來(lái)反映像素點(diǎn)分配標(biāo)簽的特征相似度。當(dāng)為像素點(diǎn)分配的標(biāo)簽差異性越小，區(qū)域項(xiàng)的值越小。區(qū)域項(xiàng)Rp定義為：

其中，MCS（Sp,Oi）表示超像素與目標(biāo)種子點(diǎn)聚類區(qū)域的最大余弦相似度，MCS（Sp,Bj）表示超像素與背景種子點(diǎn)聚類區(qū)域的最大余弦相似度，計(jì)算公式如下：

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

由公式表明，若當(dāng)前像素屬于“obj”的概率更大時(shí)，Rp（“obj”）的值會(huì)更?。煌硐袼貙儆凇癰kg”的概率更大時(shí)，Rp（“bkg”）的值會(huì)更小。

使用余弦相似度C、顏色相似度W來(lái)構(gòu)造邊界項(xiàng)Bpq，用來(lái)反映相鄰像素間的特征相似度。當(dāng)相鄰像素間的特征差異性越大，邊界項(xiàng)的值越小。邊界項(xiàng)Bpq的計(jì)算公式為：

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

余弦相似度C用來(lái)衡量鄰域超像素的相對(duì)距離的相似程度，其定義如（12）所示。相鄰超像素的距離和方向特征的差異性越大，余弦相似度C越小。當(dāng)鄰域超像素不屬于相同的區(qū)域（目標(biāo)或背景）時(shí)，余弦相似度C最小。

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

能量函數(shù)由區(qū)域項(xiàng)和邊界項(xiàng)組成，當(dāng)像素都被正確分配標(biāo)簽時(shí)，區(qū)域項(xiàng)的值最小，當(dāng)邊界都被正確分割時(shí)，邊界項(xiàng)的值最小。能夠?qū)崿F(xiàn)圖像被正確分割時(shí)，能量函數(shù)的值最小。

然后將圖像映射成S/T圖：圖像分水嶺預(yù)分割后的超像素映射為S/T圖的普通節(jié)點(diǎn)的集合P，目標(biāo)種子點(diǎn)集和背景種子點(diǎn)集被FCM聚類分割后的小區(qū)域映射為S/T圖的S源點(diǎn)集和T匯點(diǎn)集。利用區(qū)域項(xiàng)和邊界項(xiàng)計(jì)算S/T圖中對(duì)應(yīng)邊的權(quán)值，普通鄰域超像素的邊的權(quán)值使用邊界項(xiàng)Bpq計(jì)算，超像素與目標(biāo)或背景種子區(qū)域的邊的權(quán)值使用區(qū)域項(xiàng)Rp計(jì)算。

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

D（Lp,Lq）表示鄰域超像素的標(biāo)簽若相同則計(jì)算邊界項(xiàng)，若不同邊界項(xiàng)就直接為0。用于判斷鄰域超像素是否屬于不同的區(qū)域。其定義如下：小割，從而實(shí)現(xiàn)圖像分割。

3.4 序列圖像分割算法

序列圖像的基本特點(diǎn)是后一張圖像與前一張圖像相似，但是有差別?；诖颂攸c(diǎn)，序列圖像分割的核心思想是當(dāng)前的圖像分割后的模板作為下一張圖像的種子點(diǎn)集。只有第一張圖像需要單獨(dú)分割，其余的序列圖像可以實(shí)現(xiàn)自動(dòng)分割。算法流程是：

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

（2）對(duì)當(dāng)前圖像分割，使用基于改進(jìn)Graph Cuts算法，種子點(diǎn)是上一張圖像分割得到并經(jīng)過形態(tài)學(xué)方法處理的模板；

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

4 實(shí)驗(yàn)結(jié)果及分析

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

圖1

由基于區(qū)域的測(cè)度可以計(jì)算一系列的評(píng)價(jià)指標(biāo)，用于評(píng)價(jià)分割結(jié)果的準(zhǔn)確性等。評(píng)價(jià)指標(biāo)有真正類率（TPR），計(jì)算的是正樣本被正確分割的概率，又稱召回率、查全率。假正類率（FPR），計(jì)算的是負(fù)樣本被錯(cuò)誤分割為正樣本的概率，又稱虛報(bào)率。真負(fù)類率（TNR），計(jì)算的是負(fù)樣本被正確分割的概率，也稱特異性。假負(fù)類率（FNR），計(jì)算的是正樣本被錯(cuò)誤分割為負(fù)樣本的概率，又稱漏報(bào)率。準(zhǔn)確率（ACC），就是正負(fù)樣本分別被正確分割的概率。精確率（P），計(jì)算的是預(yù)測(cè)為正樣本占實(shí)際為正樣本的比例，又稱查準(zhǔn)率。F1是精確率和召回率加權(quán)調(diào)和平均，當(dāng)F1較高時(shí)則能說(shuō)明分割算法的準(zhǔn)確度比較高。

為了驗(yàn)證實(shí)驗(yàn)的有效性，本文的實(shí)驗(yàn)數(shù)據(jù)有四組序列圖像，分別對(duì)四組實(shí)驗(yàn)數(shù)據(jù)經(jīng)過原始Graph cuts算法和基于余弦相似度的Graph cuts算法分割后，計(jì)算每組每張圖像經(jīng)過兩種算法的評(píng)價(jià)指標(biāo)，然后得到平均評(píng)價(jià)指標(biāo)結(jié)果并計(jì)算本文算法相對(duì)于原始算法的環(huán)比增長(zhǎng)率，如表1所示。

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

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

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

5 結(jié)語(yǔ)

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

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

[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-），女，遼寧撫順人，碩士，研究方向?yàn)獒t(yī)學(xué)影像處理

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