(海軍陸戰(zhàn)學(xué)院 廣州 510430)

基于模板庫的自動圖像對象分割方法研究*

徐清華魏小磊李中良

(海軍陸戰(zhàn)學(xué)院 廣州 510430)

針對現(xiàn)實世界中外觀不一,而形態(tài)上有模式可循的對象,提出了一種基于模板庫的自動對象分割方法。采用模板描述對象形態(tài),構(gòu)建模板庫作為對象的先驗知識,將未知的匹配模板視為隱變量,采用由按位編碼方式組成的復(fù)合模板與圖像特征進行匹配確定隱變量的取值空間;然后,對隱變量求積分得到圖像中對象的邊緣概率。最后,求解邊緣概率所對應(yīng)的能量函數(shù),實現(xiàn)基于模板庫的自動對象分割。實驗結(jié)果驗證了論文方法的正確性和有效性。

對象分割;圖割;模板;能量函數(shù)

ClassNumberTP391.4

1 引言

計算機對不同場景下的任意對象進行自動分割一直以來都是研究者所致力追求的目標,要實現(xiàn)這一目標,必須先讓計算機掌握關(guān)于對象的知識,它是以圖像中對象的特征所表現(xiàn)的,這種特征是它區(qū)別于其他的獨特屬性。

由于對象本身可能就不是一個內(nèi)部特征均勻的整體,其內(nèi)部差異會導(dǎo)致它形成不同的區(qū)域,而更復(fù)雜的情況如對象與背景的邊界模糊,對象與背景的顏色相似或重疊,或者出現(xiàn)遮擋等等,僅依靠圖像顏色、梯度等低層特征就希望得到好的結(jié)果是不切實際的。高層特征是與對象所屬的類相關(guān)的,是對其形狀、輪廓、外觀等特征所具有的共性的提取和學(xué)習,通常由對象識別領(lǐng)域引入,通過圖像中的角點、線、邊緣、圖像塊等形式[1～6]給出。但是,現(xiàn)實世界中的對象類別豐富,特定的知識只適用于特定的對象,因此,自動分割方法往往僅針對某一類或幾類特定對象,而且知識往往需要預(yù)先根據(jù)一定數(shù)量的訓(xùn)練數(shù)據(jù)經(jīng)過復(fù)雜的機器學(xué)習過程得到,導(dǎo)致這些方法的應(yīng)用范圍受到很大限制。

通過模板來描述對象的特征,關(guān)于對象類的知識模型采用模板庫形式,避免了訓(xùn)練知識模型的復(fù)雜過程,使得知識可以非常方便地補充。由于事先并不知曉具體哪個模板能與圖像中的待分割對象匹配,無法直接構(gòu)建包含先驗信息的能量函數(shù)進行求解,因此,將未知的匹配模板視為隱變量,采用由按位編碼方式組成的復(fù)合模板與圖像特征進行匹配確定隱變量的取值空間;然后,對隱變量求積分得到圖像中對象的邊緣概率。最后,求解邊緣概率所對應(yīng)的能量函數(shù),實現(xiàn)基于模板庫的自動對象分割。

2 圖像對象分割問題數(shù)學(xué)建模

對于給定圖像D,設(shè)S={si|i=1,…,n}為一隨機變量集合,其中,變量si與圖像元素di(D={di|i=1,…,n})對應(yīng),用A來表示對S的標記,A={A1,A2,…,An},其中,Ai∈L,L為標簽集合,在本文的圖像對象分割問題中,L={obj=1,back=0}。A可看作是S～L的映射,它的不同取值對應(yīng)了對S的不同標記即對圖像D分割的結(jié)果,A的取值空間即所有可能的標記,取決于變量和標簽集合的大小,可表示為笛卡爾積:Γ=L×L×…×L=Ln,則圖像對象分割問題就是在?？臻g中尋找最佳標記A*的問題。然而,圖像對象分割的實質(zhì)是對圖像內(nèi)容的視覺感知組織,它是由圖像數(shù)據(jù)本身和先驗知識所共同決定,用Ψ表示先驗知識,則根據(jù)最大后驗概率準則,圖像對象分割問題的最佳標記解A*可表示為

(1)

式中,P(A|D,Ψ)表示給定圖像數(shù)據(jù)D與先驗知識Ψ的條件下標記A的概率。

圖像本身所具備的局部相關(guān)性,使得可采用條件隨機場對其建模,又根據(jù)MRF與Gibbs分布的等價性原理[7]可以導(dǎo)出:

P(A|D,Ψ)=Z-1×e-E(A;D,Ψ)

(2)

式中,Z=∑A∈Γe-E(A;D,Ψ)為歸一化常數(shù);E(A;D,Ψ)=∑c∈CVc(A;D,Ψ)為隨機場中所有子團勢能之和。子團是S中元素的子集,其中的元素必互相鄰,即對任意si,sj∈c,i≠j有sj∈Neighbor(si),子團勢能Vc(A;D,Ψ)則是定義在子團上的函數(shù)。通常采用大小不超過2的低階子團,相應(yīng)的能量函數(shù)表達為

(3)

即式(1)的對象分割問題可轉(zhuǎn)化為能量函數(shù)最小化問題:

(4)

由此,在處理對象分割問題時,只需關(guān)注隨機變量對應(yīng)的圖像元素、標簽選定、能量函數(shù)定義以及能量函數(shù)最小化方法。

3 基于模板庫的自動對象分割方法原理

Eapp(Ai;D,ΘX)=

(5)

其中,ρ為控制參數(shù)。

此外,匹配的模板可以視為對象的形狀先驗信息,為了保證分割結(jié)果具有模板的外形輪廓,可以定義包含模板信息的能量項:

Etemp(Ai,Aj,X)=ω×dist(si,sj,X)

(6)

其中,dist(si,sj,X)為兩相鄰像素中點到模板輪廓的最短歐式距離。對象和背景交界處的兩相鄰像素其中一個必屬于對象而另一個必屬于背景,因此兩相鄰像素的中點即可視為對象和背景交界上的點,而匹配的模板輪廓指示了對象和背景的交界,因此相鄰像素中點到模板輪廓的距離就可以用來表示該相鄰像素落在交界上可能性,即距離越遠可能性越小而相應(yīng)的在能量值上的反映則越大,反之亦然。ω決定了能量值隨距離變化的程度。

同時為了保證分割結(jié)果能較好地保持圖像邊緣,可以定義包含對比信息的能量項,即鼓勵相似的相鄰像素取相同標簽,而相異的相鄰像素取不同標簽:

Econ(Ai,Aj;D)=δ·dist-1(si,sj)·exp(-β-1·‖di-dj‖2)

(7)

其中,dist(si,sj)為si和sj之間的歐幾里德距離;‖di-dj‖2度量了變量si和sj間在顏色空間的L2范數(shù);δ為縮放系數(shù),β為控制閾值,取為β=2〈‖di-dj‖2〉,其中〈·〉表示數(shù)學(xué)期望。最終,在給定圖像D且已知匹配模板X的情況下,對象分割問題的能量函數(shù)為

(8)

其中,U為定義在S上的鄰域系統(tǒng)中所有相鄰像素對的集合。這里,|Ai-Aj|保證了二階子團勢能函數(shù)具有子模性條件,從而使得求解式(8)的能量函數(shù)最小化解,可以采用圖割方法[8]進行快速、精確地求解。

對于基于模板庫的自動對象分割而言,先驗知識已經(jīng)由已知的匹配模板變?yōu)榱税姸嗄０宓哪０鍘?設(shè)模板庫中肯定有與待分割對象大致匹配的模板,那么當前已知的信息僅是匹配模板的存在性,但并不知道具體哪個或哪些模板能匹配圖像中的待分割對象,匹配程度也未知,這也進一步導(dǎo)致了對象和背景外觀信息無法獲取。因此,無法直接建立式(8)來求解,需要尋求其他途徑。

若將未知的匹配模板X視為隱變量,根據(jù)貝葉斯規(guī)則,可得A關(guān)于D的邊緣概率:

(9)

其中,Τ?Φ為隱變量X的取值空間,則對象分割問題可以表示為

(10)

即若已知隱變量X的取值空間Τ,對象分割問題就可轉(zhuǎn)為求解使邊緣概率P(A|D)最大的A*。其中,P(A,X|D)又可以分解為

P(A,X|D)=P(A|D,X)·P(X|D)

(11)

P(A|D,X)為A關(guān)于D和X的后驗概率,而P(X|D)則是X在給定D的條件下的先驗概率,又可視為X在Τ中的權(quán)重,簡記作wX=P(X|D)。則:

(12)

(13)

(14)

即基于模板庫的對象分割問題可以表示為最小化下面的能量函數(shù):

·(Etemp(Ai,Aj;D,X)+Econ(Ai,Aj;D))

(15)

求解的關(guān)鍵在于確定未知匹配模板的取值空間Τ,以及該空間中各模板的權(quán)值。

基于模板庫的自動對象分割方法框架可描述為:

設(shè)模板庫為Φ,Φ={Φ1,Φ2,…,Φk}包含k個模板,待分割圖像為D。

步驟1:根據(jù)圖像的低層特征判斷模板庫Φ中匹配模板X的取值空間Τ={Τi}以及各模板的權(quán)值wΤi。

步驟2:根據(jù)Τi∈Τ所給出的對象和背景區(qū)域信息,進行采樣,構(gòu)建Τi的對象和背景的外觀顏色模型。

步驟3:構(gòu)造相應(yīng)的圖拓撲,利用圖割方法進行求解。

4 基于模板庫的自動對象分割方法關(guān)鍵技術(shù)實現(xiàn)

4.1 模板庫的建立

為了實現(xiàn)對圖像中目標對象的自動分割,必須首先建立關(guān)于目標對象的模板庫。其中,模板由二值圖像表示,其像素的灰度值表示該像素是否為模板中的特征像素。本節(jié)模板庫中的模板分為基模板和衍生模板,基模板為原始模板,通常由用戶從圖像中提取對象輪廓得到,而衍生模板由基模板變換得到,這里,對于非鉸鏈式剛體對象,僅考慮縮放和旋轉(zhuǎn)變換,縮放比例范圍為基模板大小的0.7～1.3,間隔為0.1,而旋轉(zhuǎn)角度范圍為-15°～15°,間隔5°,因此,一個基模板就可以衍生出7×7個衍生模板。如圖1所示為兩個基模板與由其衍生而得的衍生模板的例子,黑色表示模板特征像素,白色為非特征像素。

圖1 模板庫中模板示例

4.2 基于邊緣特征的匹配模板取值空間確定

本文依托重慶市華巖隧道西延伸段項目體外預(yù)應(yīng)力連續(xù)梁橋設(shè)計施工過程，采用ABAQUS有限元軟件建立體外預(yù)應(yīng)力錨固塊有限元模型，對錨固塊進行仿真分析，得出如下結(jié)論：

模板取值空間的確定利用了圖像的邊緣特征,它是對象形狀在圖像空間的表征。本文將利用基于Hausdorff距離的特征匹配思想[9],在距離變換空間內(nèi)實現(xiàn)對待分割對象的位置和形狀的估計,用以確定模板的取值空間。如圖2所示為確定模板取值空間的過程示意圖:首先對待分割圖像進行邊緣特征提取;然后對邊緣特征圖進行距離變換得到它的距離映射圖;最后利用基于Hausdorff距離的特征匹配方法確定匹配模板的取值空間和相應(yīng)在圖像中的匹配坐標。下面將分步進行闡述。

圖2 確定模板取值空間的示意圖

1)待分割圖像的邊緣特征提取

為使提取出的邊緣特征具有較高的可信度,采用Canny邊緣算子提取圖像的邊緣特征,如圖3所示為對洗發(fā)水瓶的圖像進行邊緣提取的例子。

圖3 基于Canny算子的邊緣特征提取

2)邊緣特征的距離映射

圖4 圖像邊緣特征的距離映射圖

3)基于Hausdorff距離的特征匹配

基于Hausdorff距離的特征匹配方法以特征集合之間的Hausdorff距離作為匹配質(zhì)量的測度,同大多數(shù)匹配方法不同,Hausdorff距離的計算并不基于相應(yīng)特征集合上的明確的點對點距離,即不要求圖像特征像素點與模板特征像素點之間具有一一對應(yīng)關(guān)系,它僅是一種相似程度的度量。此外,基于Hausdorff距離的方法不需要進行光流計算等復(fù)雜計算。因此,選擇它來待分割對象進行定位和匹配。

本文所采用的Hausdorff距離定義如下:假設(shè)有兩組特征集合ΗX={hX,1,hX,2,…,hX,p}和ΗI={hI,1,hI,2,…,hI,p}分別對應(yīng)模板特征和圖像特征,其中,hX,i表示了模板中的輪廓像素點,而hI,i則對應(yīng)了邊緣圖中的邊緣像素點。這兩個點集合之Hausdorff距離定義為

(16)

其中

(17)

符號‖·‖為定義在點hX,i和hI,j上的某種距離范數(shù)。式(18)表示模板X中的特征點hX,i到邊緣圖中邊緣特征點的最小距離,即距離映射圖中相應(yīng)像素的灰度值,而?(·)是距離截斷函數(shù):

(18)

其中,τ作為閾值用來消除因遮擋或漏測的邊緣特征對匹配的影響。因此,式(18)就表示了模板特征與圖像邊緣特征的截斷平均Hausdorff距離匹配度。

(19)

4.3 基于匹配模板的外觀模型建立

設(shè)X∈Τm為對象m的匹配模板空間中的一個模板,其在圖像中的參數(shù)為tX={ΦX,xX,yX},其中,ΦX為其在模板庫中對應(yīng)的模板,(xX,yX)為模板在圖像中的坐標。它的內(nèi)部和外部區(qū)域大致指示了對象和背景區(qū)域,通過對各區(qū)域中的像素進行采樣,建立對象和背景外觀的高斯混合模型ΘX。則式(5)中的P(di|Θ)為

(20)

其中,M為高斯混合模型中的成分數(shù),M=5;Θ={αm,θm|m=1,2,…,M},θm=(μm,∑m)為高斯混合模型的參數(shù)(αm為混合參數(shù),μm為均值向量,∑m為斜方差矩陣)。

4.4 基于模板庫的對象分割問題求解

在確定了圖像中各對象的匹配模板取值空間,空間中各模板的權(quán)值和在圖像中的匹配位置,以及由匹配模板所確定的對象和背景外觀模型以及輪廓信息后,就可以如建立式(15)所示的能量函數(shù),利用圖割方法求解,能量函數(shù)到圖拓撲的映射關(guān)系如表1所示。

5 實驗與討論

本文基于模板庫的自動對象分割方法的開發(fā)運行環(huán)境為普通個人計算機、Windows XP操作系統(tǒng)、Visual C++ 6.0。預(yù)設(shè)能量函數(shù)中的參數(shù)ρ=50.0,ω=6.0,δ=2.0。

表1 基于模板庫的能量函數(shù)到圖拓撲弧容量的映射表

圖5所示為圖3中的瓶子對象經(jīng)確定匹配模板空間后基于模板庫的自動分割結(jié)果。圖6為當圖像中有多于一個對象與模板庫中模板匹配時,自動分割的結(jié)果,它們根據(jù)各自匹配模板取值空間及對應(yīng)信息分別構(gòu)建圖拓撲進行求解。

圖5 自動分割結(jié)果

圖5和圖6所示的效果驗證了基于模板庫的自動對象分割方法的正確性和有效性,在建立典型的瓶管狀對象的模板庫后,本文方法可以對大部分具有相似形態(tài)的對象自動地分割出較正確的結(jié)果,且對于一般形態(tài)的對象,只需在模板庫中隨時添加相應(yīng)模板即可進行自動分割,不再需要任何人工干預(yù)。但是若存在陰影或者對象和背景外觀部分嚴重重疊等復(fù)雜情況,匹配模板不一定能較好切合待分割對象,則可能導(dǎo)致分割結(jié)果的邊界出現(xiàn)一些瑕疵,如圖7所示,從而使分割結(jié)果因沒有完整邊界而失敗。

圖6 圖像含多個匹配對象的分割結(jié)果

圖7 自動分割失敗示例

6 結(jié)語

首先利用隨機場模型來結(jié)合低層圖像數(shù)據(jù)和高層先驗知識對對象分割問題進行統(tǒng)一建模,并根據(jù)馬爾科夫隨機場與Gibbs分布的等價性以及貝葉斯最大后驗概率準則進一步將對象分割問題轉(zhuǎn)化為能量函數(shù)最小化問題,這樣我們只需專注于隨機變量所對應(yīng)的圖像元素和標簽的選定、能量函數(shù)的定義以及能量函數(shù)最小化方法的選擇。實驗結(jié)果表明此方法在確保分割速度的前提下,可以獲得較高的準確度,這在數(shù)字圖像處理、計算機視覺領(lǐng)域中是非常必要的。一方面,良好的對象分割效果是處理更高層的問題(如:圖像分析、圖像理解等)所不可缺少的關(guān)鍵環(huán)節(jié);另一方面,在實際生活中,它的應(yīng)用涉及影視特效、醫(yī)學(xué)影像處理、工業(yè)檢測等等,覆蓋了從工、商業(yè)到藝術(shù)、文化等各個領(lǐng)域。

[1]K. Mikolajczyk, C. Schmid. A performance evaluation of local descriptors[J]. PAMI,2005,27(10):1615-1630.

[2]N. Dalal, B. Triggs. Histograms of oriented gradients for human detection[C]. CVPR,2005(1):886-893.

[3]Matas, J., Chum, O., Urban, M., et al. Robust wide-baseline stereo from maximally stable extremal regions[J]. IVC,22(10):761-767.

[4]Per-Erik Forssen, David G. Lowe. Shape descriptors for maximally stable extremal regions[C]//Rio de Janeiro:ICCV,2007.

[5]E. Borenstein, S. Ullman. Learning to segment[C]//ECCV, Springer(LNCS),2004,3023:315-328.

[6]E. Borenstein, J. Malik. Shape guided object segmentation[C]//CVPR,2006.

[7]Li, Stan. Z. Markov Random Field Modeling in Image Analysis(3rd Edition)[M]. Berlin:Springer,2008.

[8]Boykov Y, Kolmogorov V. An experimental comparison of mincut/maxflow algorithm for energy minimization in vision[J]. PAMI,2004,26(9):1124-1137.

[9]邱志敏,李軍,葛軍,等.基于Hausdorff距離的自動目標識別算法的研究[J].紅外技術(shù),2006,28(4):199-202.

[10]Felzenszwalb P, Huttenlocher D. Distance transforms of sampled functions[R]. Cornell University, TR2004-1963,2004.

AutomaticImageObjectSegmentationApproachResearchBasedonTemplate-library

XU Qinghua WEI Xiaolei LI Zhongliang

(Naval Marine Academy, Guangzhou 510430)

For some objects with different appearance but following definite mode on contour in the real-world, a template-library-based automatic object segmentation approach is provided. First of all, template is used to describe the object contour, and build a template library as the prior knowledge of objects. Afterward, the unknown matched template is regarded as a hidden variable, and by matching the bit-encoded composited template and image features, the value space of variable is determined. Then the integral operation is utilized to get the marginal probability of the labeling given the image data. Finally the energy function is solved corresponding to the marginal probability to achieve template-library-based automatic object segmentation. Experimental results demonstrate that the approach is accurate and effective.

object segmentation, graph cut, template, energy function

2013年11月15日,

:2013年12月17日

徐清華,男,碩士,講師,研究方向:計算機仿真。

TP391.4DOI:10.3969/j.issn1672-9730.2014.05.026