基于形狀先驗(yàn)和圖割的彩色圖像分割

牛文斐，汪西莉

陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710062

圖像分割是利用圖像的某些特性，如灰度、顏色、紋理、形狀等信息將圖像劃分成若干個(gè)獨(dú)立的有意義的連續(xù)區(qū)域或?qū)ο?，在每個(gè)區(qū)域內(nèi)部具有同質(zhì)的特性。圖像的分割結(jié)果直接影響到后期的圖像分析理解。利用圖割理論進(jìn)行圖像分割是近年來(lái)基于能量最小化框架的一個(gè)研究熱點(diǎn)。該理論的新穎之處在于它的全局最優(yōu)求解能力及結(jié)合多種知識(shí)的統(tǒng)一圖像分割框架。1989年，Greig等人[1]為了驗(yàn)證模擬退火算法解決全局優(yōu)化問(wèn)題的不足，首次將圖割理論引入計(jì)算機(jī)視覺(jué)領(lǐng)域。2001年，Boykov和Jolly[2]首次提出了基于圖割的圖像分割方法Interactive Graph Cuts，它有著獲取全局最優(yōu)解以及融合多種先驗(yàn)知識(shí)的能力，奠定了運(yùn)用圖割理論進(jìn)行圖像分割的基本架構(gòu)。

傳統(tǒng)的圖割方法對(duì)簡(jiǎn)單圖像的分割是成功的，但是對(duì)于含有噪聲或遮擋物的復(fù)雜圖像的分割效果并不好。針對(duì)該缺陷，本文提出以圖割算法為基礎(chǔ)，增加形狀先驗(yàn)知識(shí)，運(yùn)用形狀先驗(yàn)信息和組合圖割優(yōu)化的方法進(jìn)行圖像分割，可以有效改善這些問(wèn)題。

1 基于圖割的圖像分割

1.1 圖割理論

圖割是一種基于圖論的組合優(yōu)化方法，它將一幅圖像映射成一個(gè)網(wǎng)絡(luò)圖，其中像素點(diǎn)對(duì)應(yīng)圖中的節(jié)點(diǎn)，相鄰像素點(diǎn)之間的關(guān)系對(duì)應(yīng)圖中節(jié)點(diǎn)之間邊，并建立關(guān)于標(biāo)號(hào)的能量函數(shù)，割的容量對(duì)應(yīng)能量函數(shù)。運(yùn)用最大流/最小割算法對(duì)網(wǎng)絡(luò)圖進(jìn)行切割，得到網(wǎng)絡(luò)圖的最小割，即對(duì)應(yīng)于待分割的目標(biāo)邊界。

1.2 圖割方法解決圖像分割的一般框架

（1）構(gòu)造能量函數(shù)，從而將分割問(wèn)題轉(zhuǎn)化為能量函數(shù)最小化問(wèn)題，該能量函數(shù)反映了圖像分割結(jié)果的好壞。

（2）根據(jù)圖像構(gòu)造s-t網(wǎng)絡(luò)圖，這個(gè)圖將能量函數(shù)視為其中邊的集合，使能量與網(wǎng)絡(luò)圖的割相對(duì)應(yīng)，從而將能量最小化問(wèn)題轉(zhuǎn)化為求網(wǎng)絡(luò)圖最小割問(wèn)題。

（3）根據(jù)最大流/最小割定理，將網(wǎng)絡(luò)圖最小割問(wèn)題轉(zhuǎn)化為最大流問(wèn)題。

（4）求得網(wǎng)絡(luò)圖的最大流，即對(duì)應(yīng)著圖的最小割，從而得到能量函數(shù)的全局最優(yōu)解，最終得到圖像分割結(jié)果[4]。

圖割理論的核心思想是構(gòu)造一個(gè)能量函數(shù)，能量函數(shù)一般由兩項(xiàng)組成[5]：

其中，數(shù)據(jù)項(xiàng)Edata(f)用來(lái)衡量像素p所分配的標(biāo)號(hào)fp與觀察到的數(shù)據(jù)不一致性；光滑項(xiàng)Esmooth(f)用于約束鄰接像素間具有一致視差，它體現(xiàn)了區(qū)域內(nèi)部的連續(xù)性和邊界的不連續(xù)性。不同的能量函數(shù)對(duì)應(yīng)網(wǎng)絡(luò)圖中的邊所賦權(quán)值的方法是不同的，但能量函數(shù)最終是解決標(biāo)號(hào)問(wèn)題的。運(yùn)用圖割算法求解能得到該能量函數(shù)的全局最優(yōu)解。

2 基于形狀先驗(yàn)和圖割的圖像分割

傳統(tǒng)圖割方法可以獲取全局最優(yōu)解或者是帶有很強(qiáng)特征的局部最優(yōu)解，但是對(duì)含有噪聲或遮擋物等復(fù)雜圖像，算法會(huì)受圖像中噪聲、遮擋等的影響，分割得到的目標(biāo)不完整或者包含一些雜質(zhì)。而目前提出的很多在已有算法中加入形狀先驗(yàn)的思想，使算法包含更多約束信息，限制了感興趣區(qū)域的搜尋空間，從而更好地分割出完整目標(biāo)。如Slabaugh[6]等提出了基于橢圓形狀先驗(yàn)和圖割的圖像分割方法；Veksler[7]提出一種融合星形形狀先驗(yàn)到圖割算法中的圖像分割方法。引入形狀先驗(yàn)的思想，關(guān)鍵要考慮如何將形狀先驗(yàn)懲罰添加到傳統(tǒng)圖割算法中，從而進(jìn)行有效的分割。形狀先驗(yàn)?zāi)０蹇梢赃x用一個(gè)簡(jiǎn)單的模板，也可以選用多個(gè)形狀先驗(yàn)?zāi)０宓挠?xùn)練集，后者更為靈活，適用于變形的形狀，但計(jì)算是復(fù)雜而耗時(shí)的。因此本文在圖割算法的基礎(chǔ)上，加入了簡(jiǎn)單的形狀先驗(yàn)知識(shí)，有效提高了圖割的分割精度，使圖割方法更具有魯棒性。若給定形狀先驗(yàn)?zāi)０迮c待分割目標(biāo)存在平移、旋轉(zhuǎn)、尺度縮放等剛性變換，則運(yùn)用（Scale Invariant Feature Transform，SIFT）算法進(jìn)行特征匹配，通過(guò)仿射變換將給定模板與分割目標(biāo)進(jìn)行對(duì)齊，解決形狀先驗(yàn)?zāi)０迮c待分割目標(biāo)存在的仿射不同，使該算法更靈活。

2.1 形狀先驗(yàn)?zāi)Ｐ?/h3>

首先定義形狀先驗(yàn)?zāi)芰?，根?jù)文獻(xiàn)[8]中提到的運(yùn)用Chan和Zhu[9]提出的形狀距離的描述形式，將形狀先驗(yàn)?zāi)芰客ㄟ^(guò)終端邊緣權(quán)值合并到圖中。該方法中的形狀距離是對(duì)稱的，而且遵循了三角不等式，其使用的形狀模板是和待分割目標(biāo)相同的二值形狀模板。

對(duì)于給定的一個(gè)形狀模板φ0，定義二值標(biāo)簽f的能量：

由上述思想可以得到，形狀先驗(yàn)懲罰為：

其中f表示未含形狀先驗(yàn)得到的分類標(biāo)記，φ0表示已知的二值形狀模板。

加入形狀懲罰的思想：如果分類得到的標(biāo)記模板和已知形狀的二值模板在某點(diǎn)的標(biāo)記不一致，如p點(diǎn)的標(biāo)記fp=0，而模板=1，或p點(diǎn)的標(biāo)記fp=1，而模板=0，則表示分割有誤，需要加入形狀懲罰1；如果分割得到的標(biāo)記模板和已知二值模板的像素點(diǎn)的標(biāo)記一致，則形狀懲罰為0，即不需要加入任何懲罰。

2.2 模板仿射變換

如果給定的二值形狀模板和分類得到的標(biāo)記模板不完全相同，存在平移、旋轉(zhuǎn)、尺度縮放等差異，則需要將兩個(gè)形狀通過(guò)仿射變換進(jìn)行配準(zhǔn)。通過(guò)仿射變換實(shí)現(xiàn)圖像配準(zhǔn)有多種方法，比如歸一化算法[10]、梯度下降法[11]等，但歸一化算法是根據(jù)圖像矩來(lái)求解的，對(duì)于含有陰影等雜質(zhì)的模板處理效果不好，往往得不到正確的形式；梯度下降法求解容易陷入局部最優(yōu)，找不到最優(yōu)解。本文運(yùn)用SIFT特征匹配算法[12]，SIFT由Lowe于1999年提出，2004年完善總結(jié)，其匹配能力較強(qiáng)，可以處理兩幅圖像之間發(fā)生平移、旋轉(zhuǎn)、尺度縮放等情況下的匹配問(wèn)題。SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點(diǎn)，提取位置、尺度、旋轉(zhuǎn)不變量。極值點(diǎn)是一些十分突出的點(diǎn)，比如角點(diǎn)、邊緣點(diǎn)、暗區(qū)域的亮點(diǎn)以及亮區(qū)域的暗點(diǎn)，如果兩幅圖像中有相同的景物，那么使用某種方法分別提取各自的穩(wěn)定點(diǎn)，則這些點(diǎn)之間會(huì)有相互對(duì)應(yīng)的匹配點(diǎn)。

根據(jù)正確匹配的特征點(diǎn)，運(yùn)用仿射變換公式求得變換參數(shù)，從而使兩幅圖像正確匹配。

2.3 本文方法

2.3.1 算法設(shè)計(jì)

本文算法的思想：首先建立關(guān)于標(biāo)號(hào)的能量函數(shù)EA(f)，利用圖割方法最小化該能量函數(shù)求得最優(yōu)解，從而得到初始分割結(jié)果。在此基礎(chǔ)上，運(yùn)用上述提到的添加形狀先驗(yàn)的思想，在能量函數(shù)中添加形狀項(xiàng)，構(gòu)成新的能量函數(shù)，通過(guò)終端邊緣權(quán)值將形狀懲罰合并到圖中，運(yùn)用圖割算法求得最終分割結(jié)果。

算法流程為：

步驟1首先選取一幅彩色圖像，對(duì)圖像構(gòu)造s-t網(wǎng)絡(luò)圖，建立關(guān)于此標(biāo)號(hào)的能量函數(shù)EA(f)，根據(jù)定義好的能量函數(shù)，確定圖的邊緣之間的權(quán)值。

步驟2在該網(wǎng)絡(luò)圖上運(yùn)用最大流/最小割算法求得圖的最大流，即對(duì)應(yīng)著最小割，從而得到初始的圖像分割結(jié)果。

步驟3在上述算法的基礎(chǔ)上，結(jié)合添加形狀先驗(yàn)的思想，定義形狀先驗(yàn)?zāi)芰?，在能量函?shù)中添加形狀項(xiàng)，構(gòu)成新的能量函數(shù)E(f)，然后把這些形狀能量通過(guò)終端邊緣權(quán)值合并到圖中。

步驟4運(yùn)用圖割方法進(jìn)行分割，得到加入形狀以后的圖像分割結(jié)果。

2.3.2 能量函數(shù)的定義

算法步驟1和步驟3是建立關(guān)于標(biāo)號(hào)的能量函數(shù)，本文選擇的能量函數(shù)形式為：

該能量函數(shù)包括兩項(xiàng)：第一項(xiàng)是基于圖像信息的能量項(xiàng)；第二項(xiàng)是形狀能量項(xiàng)。算法步驟1中建立的是基于圖像的能量函數(shù)，對(duì)應(yīng)式（4）的第一項(xiàng)，這一項(xiàng)是基于圖像信息的，包含數(shù)據(jù)項(xiàng)和平滑項(xiàng)；算法步驟3建立的能量函數(shù)如式（4）所示，包括兩項(xiàng)。

能量函數(shù)中第一項(xiàng)E(A)采用文獻(xiàn)[2]定義的形式：

其中R(A)是數(shù)據(jù)項(xiàng)，B(A)是平滑項(xiàng)；系數(shù)λ≥0表示了區(qū)域項(xiàng)R(A)和邊界項(xiàng)B(A)的相對(duì)重要性。數(shù)據(jù)項(xiàng)和平滑項(xiàng)的定義如下：

式（6）中R(A)表示像素p屬于背景或者目標(biāo)的概率的代價(jià)。式（9）中系數(shù)B{p，q}≥0表示像素p和q之間的不相似性的代價(jià)，δ(Ap，Aq)表示像素點(diǎn)標(biāo)號(hào)的值，式（11）中Ip和Iq表示像素點(diǎn)的值。算法中，數(shù)據(jù)項(xiàng)選用高斯模型來(lái)建模，采用K均值算法。將圖像像素點(diǎn)聚為兩類，得到樣本的標(biāo)記并計(jì)算每類的均值和協(xié)方差，從而估計(jì)得到參數(shù)進(jìn)行建模。

能量函數(shù)中第二項(xiàng)形狀項(xiàng)ES(f)采用2.1節(jié)描述來(lái)定義。如果給定的形狀模板經(jīng)過(guò)了仿射變換，則采用2.2節(jié)的思想來(lái)定義。

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

運(yùn)用上述方法對(duì)彩色圖像進(jìn)行分割。程序用Matlab編寫(xiě)，其核心部分由C++語(yǔ)言實(shí)現(xiàn)，編程環(huán)境為Matlab 2009b和VC2008。選用標(biāo)準(zhǔn)圖像庫(kù)Weizmann Horse Database（msri.org/people/members/eranb/）中 的 圖 像 進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)庫(kù)中馬的顏色、大小、形態(tài)各異，而且背景也十分復(fù)雜，有些與馬的顏色很接近，不同圖像中的目標(biāo)之間、背景之間也有著明顯的差異。本文分別用傳統(tǒng)圖割算法和添加形狀先驗(yàn)后的算法對(duì)圖像進(jìn)行分割，兩種方法的能量函數(shù)定義的參數(shù)λ均設(shè)置為43。

圖1（a）是一幅加入均值為0，方差為0.01的高斯噪聲后的彩色圖像，使用傳統(tǒng)圖割方法時(shí)得到初始分割結(jié)果如圖1（b）；添加形狀先驗(yàn)?zāi)芰亢?，使用圖割方法得到分割結(jié)果和標(biāo)記如圖1（c）。從圖中可以看到，分割效果得到了優(yōu)化，錯(cuò)誤率明顯降低。圖2和圖3是加入和上圖相同大小的噪聲后得到的圖像分割結(jié)果。從這三個(gè)圖像的分割結(jié)果圖來(lái)看，加入形狀先驗(yàn)后的圖割算法，對(duì)含有噪聲的圖像具有更強(qiáng)的魯棒性，得到了更完整的目標(biāo)分割。

圖1 horse320.jpg加入高斯噪聲分割結(jié)果

圖2 horse125.jpg加入高斯噪聲分割結(jié)果

圖3 horse321.jpg加入高斯噪聲分割結(jié)果

圖4（a）是一幅在原圖上添加一部分遮擋物后得到的彩色圖像；使用傳統(tǒng)圖割方法得到初始分割結(jié)果如圖4（b）。從結(jié)果圖中可以看到，遮擋物部分沒(méi)有得到有效分割，仍然屬于一個(gè)整體被錯(cuò)分給了目標(biāo)部分。添加形狀先驗(yàn)?zāi)芰亢?，使用圖割方法得到分割結(jié)果和標(biāo)記如圖4（c）。從圖中可以看到，遮擋物部分得到了正確分割，目標(biāo)部分分割更加完整，分割效果得到了優(yōu)化，錯(cuò)誤率明顯降低。

圖4 horse002.jpg加入遮擋物分割結(jié)果

圖5（a）是一幅彩色圖像。該圖像本身就含有遮擋物，圖中人坐在馬上，人的上部分身體屬于背景，下部分身體屬于目標(biāo)，人為遮擋物。使用傳統(tǒng)圖割方法得到初始分割結(jié)果如圖5（b）。從圖中可以看出，人的部分沒(méi)有得到正確分割，目標(biāo)分割不完整。添加形狀先驗(yàn)?zāi)芰亢?，使用圖割方法得到分割結(jié)果和標(biāo)記如圖5（c）。從圖中可以看到，錯(cuò)誤部分得到了很大改善，分割效果得到了優(yōu)化。

圖5 horse097.jpg含遮擋物分割結(jié)果

圖6（a）為一幅彩色圖像。圖中人和馬都有影子，含有陰影遮擋。首先使用傳統(tǒng)圖割方法得到初始分割結(jié)果如圖6（b）。從結(jié)果圖中看出，陰影部分均還存在，沒(méi)有得到正確分割。在上述圖割算法中添加形狀先驗(yàn)懲罰后，得到分割結(jié)果如圖6（c）。從圖中可以看到，陰影部分得到正確分割，分割結(jié)果得到了優(yōu)化。

圖7的圖像分割使用的模板是尺度縮放后的模板（a），和分割得到的標(biāo)記圖不相同，則使用上述匹配思想進(jìn)行模板匹配，在此基礎(chǔ)上加入形狀先驗(yàn)，得到結(jié)果如圖所示。圖8和圖9使用的先驗(yàn)?zāi)０宸謩e是平移以后和旋轉(zhuǎn)以后的模板。

圖6 horse099.jpg含陰影遮擋分割結(jié)果

圖7 horse129.jpg的圖像分割結(jié)果

圖8 horse008.jpg的圖像分割結(jié)果

圖9 horse182.jpg的圖像分割結(jié)果

從表1看出，添加形狀先驗(yàn)后的錯(cuò)誤率大幅度下降，圖像分割效果良好，而耗時(shí)會(huì)增加，主要是由于增加形狀懲罰部分引起的，因?yàn)樾螤顟土P是按圖像的像素點(diǎn)加進(jìn)去的，所以需要逐個(gè)像素點(diǎn)來(lái)判斷，但是并沒(méi)有增加太多的時(shí)間復(fù)雜度。實(shí)驗(yàn)數(shù)據(jù)進(jìn)一步表明了本文算法的有效性和分割效率，表明了本文算法針對(duì)含噪、有遮擋或陰影的復(fù)雜圖像可以較完整地分割出目標(biāo)，取得了較好的結(jié)果。

表1 未含形狀信息和包含形狀信息的分割錯(cuò)誤率和算法運(yùn)行時(shí)間比較

4 結(jié)束語(yǔ)

傳統(tǒng)的圖割方法對(duì)簡(jiǎn)單圖像的分割可以得到良好的效果，但是對(duì)于含有噪聲、遮擋物等的復(fù)雜的圖像，它的分割效果不能令人滿意，有的圖像目標(biāo)分割不完整，有的圖像分割結(jié)果包含雜質(zhì)或陰影等部分。本文提出的基于形狀先驗(yàn)和圖割的圖像分割算法，比傳統(tǒng)的圖割方法分割精度高，特別是對(duì)上述提到的復(fù)雜圖像也能得到良好的分割結(jié)果，為圖割融合先驗(yàn)知識(shí)提供了一種思路。文中選用一個(gè)形狀先驗(yàn)?zāi)０澹瑢?duì)一些特定的目標(biāo)分割具有局限性，只能分割和該形狀先驗(yàn)?zāi)０逡粯踊蚍律洳煌哪繕?biāo)，對(duì)于和形狀模版有非剛性變形的目標(biāo)分割則不適用。針對(duì)該局限性，可以考慮采用多個(gè)形狀先驗(yàn)?zāi)０?，以適應(yīng)局部和全局變形。

[1]Greig D，Porteous B，Seheult A.Exact maximum a posteriori estimation for binary image[J].Journal of the Royal Statistical Society：Series B，1989，51（2）：271-279.

[2]Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary®ion segmentation of objects in N-D images[C]//Proceedings of Internation Conference on Computer Vision，July 2001.

[3]Ford L，F(xiàn)ulkerson D.Flows in networks[M].Princeton，New Jersey：Princeton University Press，1962.

[4]楊建功，汪西莉.一種結(jié)合圖割與雙水平集的圖像分割方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（3）：195-197.

[5]Boykov Y，Veksler O，Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（11）：1222-1239.

[6]Slabaugh G，Unal G.Graph cuts segmentation using an elliptical shape prior[C]//Proceedings of International Conference on Image Processing，2005：1222-1225.

[7]Veksler O.Star shape prior for graph-cut image segmentation[C]//Proceedigns of ECCV 2008，2008，5304：454-467.

[8]Vu N，Manjunath B S.Shape prior segmentation of multiple objects with graph cuts[C]//Proceedings of CVPR 2008，24-26 June，2008.

[9]Chan T，Zhu W.Level set based shape prior segmentation[C]//Proceedings of CVPR 2005，June 2005，2005：1164-1170.

[10]Pei S C，Lin C N.Imagenormalization for pattern recognition[J].Image and Vision Computing，1995，13（10）.

[11]Paragios N，Rousson M，Ramesh V.Non-rigidregistration using distancefunctions[J].Computer Vision and Image Understanding，2003，89（2/3）：142-165.

[12]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.