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

(海軍陸戰學院 廣州 510430)

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

徐清華魏小磊李中良

(海軍陸戰學院 廣州 510430)

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

對象分割;圖割;模板;能量函數

ClassNumberTP391.4

1 引言

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

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

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

2 圖像對象分割問題數學建模

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

(1)

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

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

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

(2)

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

(3)

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

(4)

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

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

Eapp(Ai;D,ΘX)=

(5)

其中,ρ為控制參數。

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

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

(6)

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

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

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范數;δ為縮放系數,β為控制閾值,取為β=2〈‖di-dj‖2〉,其中〈·〉表示數學期望。最終,在給定圖像D且已知匹配模板X的情況下,對象分割問題的能量函數為

(8)

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

對于基于模板庫的自動對象分割而言,先驗知識已經由已知的匹配模板變為了包含眾多模板的模板庫,設模板庫中肯定有與待分割對象大致匹配的模板,那么當前已知的信息僅是匹配模板的存在性,但并不知道具體哪個或哪些模板能匹配圖像中的待分割對象,匹配程度也未知,這也進一步導致了對象和背景外觀信息無法獲取。因此,無法直接建立式(8)來求解,需要尋求其他途徑。

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

(9)

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

(10)

即若已知隱變量X的取值空間Τ,對象分割問題就可轉為求解使邊緣概率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關于D和X的后驗概率,而P(X|D)則是X在給定D的條件下的先驗概率,又可視為X在Τ中的權重,簡記作wX=P(X|D)。則:

(12)

(13)

(14)

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

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

(15)

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

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

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

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

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

步驟3:構造相應的圖拓撲,利用圖割方法進行求解。

4 基于模板庫的自動對象分割方法關鍵技術實現

4.1 模板庫的建立

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

圖1 模板庫中模板示例

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

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

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

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

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

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

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

2)邊緣特征的距離映射

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

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

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

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

(16)

其中

(17)

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

(18)

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

(19)

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

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

(20)

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

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

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

5 實驗與討論

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

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

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

圖5 自動分割結果

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

圖6 圖像含多個匹配對象的分割結果

圖7 自動分割失敗示例

6 結語

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

[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].紅外技術,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