丁陳梅 王 濤 孫權(quán)森

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

交互式圖像分割是指在用戶提供的先驗(yàn)知識(shí)下，基于一定的相似性準(zhǔn)則將用戶感興趣的目標(biāo)從復(fù)雜的圖像背景環(huán)境中分離出來(lái)。根據(jù)用戶交互方式的不同，交互式分割方法一般可以分為基于邊界交互［1～3］的方法和基于區(qū)域交互［4～6］的方法?；谶吔缃换サ姆椒ㄐ枰脩粼诖指钅繕?biāo)邊界附近提供一條初始的輪廓，然后算法將自動(dòng)地由初始輪廓向著目標(biāo)輪廓進(jìn)行迭代的演化。此類方法易陷入局部極值，且對(duì)用戶初始化輪廓較為敏感。基于區(qū)域交互的方法需要用戶在目標(biāo)和背景區(qū)域標(biāo)記一些像素作為種子點(diǎn)，然后算法基于標(biāo)記的種子點(diǎn)自動(dòng)完成未標(biāo)記像素的分割。相較于基于邊界交互的方法，此類方法更加簡(jiǎn)單和方便。上述方法大都基于像素層關(guān)系分割圖像，忽略了圖像長(zhǎng)范圍的區(qū)域連通性約束，導(dǎo)致它們易獲得欠分割的結(jié)果。近年來(lái)，基于超像素的方法在圖像分割、目標(biāo)跟蹤等［7］領(lǐng)域得到了廣泛的應(yīng)用。然而，單一的分割結(jié)果往往不能準(zhǔn)確地描述物體邊界，易獲得過(guò)分割的結(jié)果。因此，許多基于多層超像素的方法相繼被提出［8～11］，通過(guò)對(duì)圖像進(jìn)行多次預(yù)分割，利用獲得的多層信息以克制過(guò)分割。但此類方法中信息過(guò)于冗余，增加了算法開(kāi)銷(xiāo)。

針對(duì)上述問(wèn)題，本文提出一種基于多尺度超像素和圖割的交互式圖像分割算法，使用多尺度預(yù)分割獲得的超像素替代像素構(gòu)建加權(quán)圖，通過(guò)提取超像素內(nèi)所有像素特征的均值和協(xié)方差來(lái)獲取該超像素的結(jié)構(gòu)信息；利用分量形式的期望最大化混合高斯算法對(duì)用戶交互進(jìn)行聚類，相較于EM算法，CEMGM算法可以自動(dòng)精煉數(shù)據(jù)結(jié)構(gòu)，在保證高聚類精度的同時(shí)減小后續(xù)計(jì)算的復(fù)雜度；通過(guò)融合多尺度超像素信息，基于小尺度超像素的局部近鄰性約束克服過(guò)分割，基于大尺度超像素的長(zhǎng)范圍連通性約束克服欠分割，進(jìn)一步提高圖像分割質(zhì)量。

2 基于圖割的圖像分割模型

在基于圖割的分割框架中，圖像分割問(wèn)題可以看作一種二值標(biāo)簽問(wèn)題［4］。給定一個(gè)圖像像素集合I，圖像分割的目標(biāo)就是為圖像中的每個(gè)像素點(diǎn)i∈I分配一個(gè)標(biāo)簽 fi∈{0，1}，其中0代表背景，1代表前景?；趫D割的圖像分割模型的能量函數(shù)一般可以表示為

其中，區(qū)域項(xiàng)Er(f)用來(lái)懲罰每個(gè)像素特征與前景和背景模型的不匹配程度，邊界項(xiàng)Eb(f)用來(lái)懲罰鄰域像素對(duì)的不連續(xù)性。平衡參數(shù)λ＞0用來(lái)控制區(qū)域項(xiàng)和邊界項(xiàng)的影響。

圖1 圖割模型中圖的構(gòu)建和割集示意圖

基于該能量函數(shù)構(gòu)建圖G=(V，E)，其中V代表頂點(diǎn)集，E代表邊集。頂點(diǎn)集由圖像中所有像素和兩個(gè)額外的終端點(diǎn)（終端點(diǎn)S和 T分別代表前景和背景）組成。邊集分為兩種，一種為所有像素與兩個(gè)終端點(diǎn)之間的連接，用來(lái)表示像素與圖像前景和背景模型的匹配程度；一種為圖像所有鄰域像素對(duì)之間的連接，用來(lái)表示局部相鄰像素之間的梯度變化程度。圖1（a）為一幅3×3圖像的構(gòu)圖示意圖?；跇?gòu)建的圖，將圖像分割問(wèn)題轉(zhuǎn)化為在圖中尋找最小割集的問(wèn)題，并采用最大流/最小割算法［12］求解圖的最小割集，以獲得全局最優(yōu)的分割結(jié)果。圖1（b）顯示了割集示意圖，將圖像像素劃分為兩個(gè)類別，與終端點(diǎn)S相連接的像素被分割為前景，與終端點(diǎn)T相連接的像素則被分割為背景。

3 本文算法

傳統(tǒng)圖割算法一般基于圖像的局部關(guān)系構(gòu)建分割模型，忽視了圖像的結(jié)構(gòu)信息和長(zhǎng)范圍區(qū)域連通性信息，而結(jié)合圖像的多尺度區(qū)域信息可以進(jìn)一步提高算法的分割精度。

3.1 多尺度圖的構(gòu)建

現(xiàn)有的基于超像素的方法大都基于單尺度超像素，易獲得過(guò)分割的結(jié)果。針對(duì)上述問(wèn)題，本文提出多尺度超像素，其中小尺度超像素保存了圖像的局部信息，可以提供局部的鄰近約束以克服過(guò)分割；大尺度超像素保存了圖像的宏觀結(jié)構(gòu)信息，可以提供圖像長(zhǎng)范圍的區(qū)域連通性約束以克服欠分割；中維尺度的超像素則可以傳遞圖像全局信息。通過(guò)融合多尺度超像素信息，可以克服單尺度超像素過(guò)分割的缺陷和局部像素關(guān)系易引起的欠分割缺陷。

由于SLIC算法［13］生成的超像素緊湊整齊，且可以靈活控制超像素?cái)?shù)量，因此，本文采用SLIC算法生成超像素。如圖2（a）所示，通過(guò)設(shè)置算法中超像素的數(shù)目為400、1000、8000個(gè)，使用SLIC算法對(duì)圖像進(jìn)行多尺度預(yù)分割得到三層尺度不同的超像素層。然后用獲取到的超像素代替像素作為圖的節(jié)點(diǎn)，如圖2（b）所示，中間層內(nèi)超像素采用全連接方式（同一層內(nèi)每對(duì)超像素之間都存在邊緣），其余層內(nèi)超像素采用相鄰連接方式（同一層內(nèi)相鄰的超像素間才存在邊緣），并將不同超像素層之間對(duì)應(yīng)的超像素相連接，從而構(gòu)建多尺度圖模型。

圖2 多尺度超像素示意圖

3.2 超像素特征提取與度量

傳統(tǒng)基于超像素的方法一般提取超像素內(nèi)所有像素的特征均值作為該超像素的特征，忽略了同一超像素內(nèi)像素之間的信息關(guān)聯(lián)，導(dǎo)致超像素之間的相似性度量往往不夠精確。具有相似均值特征的兩個(gè)超像素內(nèi)部的像素特征分布可能具有很大差異，該情況下上述基于特征均值的度量方法難以有效區(qū)分出不同超像素，嚴(yán)重影響了后續(xù)的分割結(jié)果。為了提高對(duì)超像素的區(qū)分能力，本文通過(guò)提取超像素內(nèi)所有像素特征的均值和協(xié)方差來(lái)獲取超像素的結(jié)構(gòu)信息，即超像素i的特征可以表示為Gi={μi，∑i} 。 然 后 基 于 信 息 論 中 的 KL（Kull?back-Leibler）散度距離度量不同超像素之間的關(guān)系，根據(jù)文獻(xiàn)［14］給出的計(jì)算方式，超像素m的特征 Gm={μm，∑m} 和超像素 n 的特征 Gn={μn，∑n}之間的相似性定義如下：

其中，tr(?)為矩陣的跡運(yùn)算，d為超像素特征的維數(shù)。

3.3 結(jié)合多尺度超像素信息的圖割算法

在圖割模型中引入上述圖像多尺度區(qū)域信息，定義結(jié)合多尺度超像素的能量函數(shù)如下：

其中，I表示所有超像素的集合，?表示同一超像素層內(nèi)所有鄰域超像素對(duì)的集合，C表示不同超像素層之間對(duì)應(yīng)的超像素對(duì)的集合。Di(fi)為超像素i與其標(biāo)簽 fi的匹配程度測(cè)量函數(shù)。對(duì)于彩色圖像分割，一般采用GMM對(duì)前景和背景種子的特征建模，然而，GMM不能自動(dòng)確定類別的數(shù)目，數(shù)目過(guò)大會(huì)造成信息冗余，數(shù)目過(guò)小則不能完整描述數(shù)據(jù)。因此，本文使用分量形式的期望最大化混合高斯算法對(duì)用戶交互進(jìn)行聚類，相比較于EM算法，CEMGM算法可以自動(dòng)精煉數(shù)據(jù)結(jié)構(gòu)、確定類別數(shù)目，在保證高聚類精度的同時(shí)減小后續(xù)計(jì)算的復(fù)雜度，更多細(xì)節(jié)請(qǐng)參考文獻(xiàn)［15］。使用CEMGM算法對(duì)前景種子和背景種子聚類可以得到對(duì)應(yīng)的高分別為前景和背景的類別數(shù)目。超像素i與前景和背景模型之間的相似性定義如下：

Bmn(fm，fn)為同一超像素層內(nèi)鄰域超像素m和n之間的懲罰函數(shù)，定義如下：

其中，δ(fm≠fn)=1如果 fm≠fn，否則為0。調(diào)節(jié)參數(shù)ξm是基于m和n所屬的超像素層進(jìn)行設(shè)定的，即每一超像素層都有各自的調(diào)節(jié)參數(shù)值，具體定義如下：

其中|?m|表示m所屬超像素層的元素?cái)?shù)目。Spq(fp，fq)為不同超像素層之間對(duì)應(yīng)超像素對(duì)的相似性測(cè)量函數(shù)，定義如下：

其中，δ(fp≠fq)=1如果 fp≠fq，否則為0。由于 p所屬超像素層的調(diào)節(jié)參數(shù)值ξp與q所屬超像素層的調(diào)節(jié)參數(shù)值ξq并不相等，因此，不同像超素層之間的調(diào)節(jié)參數(shù)ξpq定義如下：

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

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證本文算法的有效性。測(cè)試圖像分別來(lái)自Berkeley分割數(shù)據(jù)集［16］和Micro?soft GrabCut數(shù)據(jù)集［5］。本文采用分割錯(cuò)誤率指標(biāo)來(lái)定量地評(píng)價(jià)分割結(jié)果，分割錯(cuò)誤率定義為錯(cuò)誤分類像素點(diǎn)的數(shù)目與所有參與分類像素點(diǎn)數(shù)目之比，其中參與分類像素點(diǎn)數(shù)目不包括前景和背景的種子點(diǎn)。為了對(duì)比實(shí)驗(yàn)的公平性，所有比較算法都使用相同的參數(shù)并基于相同的用戶交互進(jìn)行實(shí)驗(yàn)，式（3）中的系數(shù)λ設(shè)為50，?設(shè)為40。

4.1 定性比較實(shí)驗(yàn)

圖3顯示了本文算法與傳統(tǒng)圖割算法GC、基于單尺度超像素分割算法SLSGC的定性比較結(jié)果，其中第1列為輸入的測(cè)試圖像，均來(lái)自Berkeley數(shù)據(jù)集，測(cè)試圖像中的線條為各算法公共的用戶交互，紅色線條代表前景的種子點(diǎn)，藍(lán)色線條代表背景的種子點(diǎn)。第2～4列分別為GC、SLSGC以及本文算法的分割結(jié)果。從中可以看出GC算法較難正確分割包含紋理或低對(duì)比度等背景較為復(fù)雜的圖像，易獲得欠分割的結(jié)果。由于在圖割模型中引入超像素信息，SLSGC算法的分割結(jié)果優(yōu)于GC算法，但由于單尺度超像素不夠精確，SLSGC算法出現(xiàn)了明顯的過(guò)分割現(xiàn)象。由于引入圖像多尺度區(qū)域信息，本文算法可以有效克服單尺度超像素過(guò)分割的缺陷和局部像素關(guān)系易引起的欠分割缺陷，獲得了最優(yōu)的分割結(jié)果。

圖3 GC、SLSGC和本文算法的定性比較實(shí)驗(yàn)

4.2 定量比較實(shí)驗(yàn)

本節(jié)基于Microsoft GrabCut數(shù)據(jù)集對(duì)本文算法與 GC［4］、Grabcut［5］以及 Lazy Snapping［6］算法進(jìn)行定量的比較，通過(guò)Microsoft GrabCut數(shù)據(jù)集中50幅測(cè)試圖像的平均錯(cuò)誤率來(lái)評(píng)價(jià)算法分割質(zhì)量。表1顯示了本文算法與多個(gè)交互式分割算法在Micro?soft GrabCut數(shù)據(jù)集中的平均分割錯(cuò)誤率的比較，從表中可以看出多尺度區(qū)域信息的引入較好地提高了圖割算法的分割精度，本文算法的平均錯(cuò)誤率要明顯低于GC和Lazy Snapping算法，略好于Grabcut算法。圖4顯示了這四種算法在每幅測(cè)試圖像中分割錯(cuò)誤率的比較，從中可以看出本文算法獲得了最好的結(jié)果，驗(yàn)證了結(jié)合多尺度的圖割算法的有效性。

表1 平均分割錯(cuò)誤率（%）的比較

圖4 本文算法與GC、Grabcut以及Lazy Snapping算法分割錯(cuò)誤率比較

5 結(jié)語(yǔ)

本文在圖割算法中引入圖像多尺度區(qū)域信息，提出一種基于多尺度超像素和圖割的交互式圖像分割算法。該方法利用SLIC算法對(duì)圖像進(jìn)行多尺度預(yù)分割，并基于超像素特征均值和協(xié)方差的KL距離度量不同超像素之間的相似性。通過(guò)融合多尺度超像素信息，基于小尺度超像素的局部近鄰性約束克服過(guò)分割，基于大尺度超像素的長(zhǎng)范圍連通性約束克服欠分割，進(jìn)一步提高了圖像分割質(zhì)量。最后通過(guò)多個(gè)分割算法的定性比較和定量評(píng)估證明了本文算法的有效性。本文算法還存在一些缺陷，比如對(duì)細(xì)長(zhǎng)目標(biāo)的分割需要更多的交互信息，調(diào)節(jié)參數(shù)需要憑經(jīng)驗(yàn)手動(dòng)設(shè)定等，如何克服這些缺陷將是今后的主要工作。