基于貝葉斯模型的骨架裁剪方法

秦紅星 孫 穎

?

基于貝葉斯模型的骨架裁剪方法

秦紅星*孫 穎

(重慶郵電大學(xué)計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065)(重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 重慶 400065)

針對(duì)大部分骨架計(jì)算方法對(duì)輪廓噪聲的極端敏感性問題，該文提出一種基于貝葉斯模型的骨架裁剪方法。該方法利用貝葉斯理論對(duì)骨架及其生長過程進(jìn)行建模，進(jìn)而通過對(duì)模型的迭代優(yōu)化實(shí)現(xiàn)骨架候選分支的篩選裁剪。由于已有的重建誤差率在分析骨架時(shí)不能很好地體現(xiàn)骨架簡(jiǎn)潔程度，故該文在骨架重建誤差率的基礎(chǔ)上綜合考慮骨架簡(jiǎn)潔度，提出骨架有效率的概念來對(duì)骨架做客觀定量分析。實(shí)驗(yàn)結(jié)果表明該文算法對(duì)輪廓噪聲具有較好的魯棒性，且裁剪出的骨架相比現(xiàn)有算法得到的骨架結(jié)構(gòu)更加簡(jiǎn)單，對(duì)形狀描述更加準(zhǔn)確。

骨架；形狀；裁剪；貝葉斯；幾何處理；骨架有效率

1 引言

骨架是形狀的一種簡(jiǎn)單抽象，一個(gè)結(jié)構(gòu)簡(jiǎn)潔且能準(zhǔn)確解釋形狀的骨架能有效應(yīng)用在基于內(nèi)容的圖像檢索[1]、目標(biāo)識(shí)別和醫(yī)療診斷等形狀分析[2,3]的多個(gè)相關(guān)領(lǐng)域中，因此獲取理想的骨架十分重要。自從Blum[4]提出一種中軸變換(MAT)獲取形狀骨架的方法后，涌現(xiàn)了許多骨架提取算法：基于細(xì)化的算法[5,6]，基于Voronoi圖的離散域骨架化算法[7,8]，基于距離變換的算法[9,10]，基于數(shù)學(xué)形態(tài)學(xué)的算法[11,12]。這些方法能給出形狀物體的骨架表示，但是都表現(xiàn)出對(duì)輪廓噪聲的極端敏感性，使提取出的骨架包含大量冗余分支，無法滿足人們的直觀視覺感知。為了解決這個(gè)問題，研究者們相繼提出一些改進(jìn)方法，結(jié)果表明，這些方法能在一定程度上減少骨架對(duì)邊界噪聲的敏感性，但是都不能很好地解決假性分支問題，所以無法得到理想的骨架結(jié)構(gòu)。

目前的骨架裁剪算法主要分為兩類：一類是在物體輪廓預(yù)平滑處理的基礎(chǔ)上進(jìn)行骨架提取來實(shí)現(xiàn)骨架剪枝[17]。這種方法的平滑效果難以滿足，同時(shí)會(huì)改變物體輪廓的位置，從而引起骨架位置的移動(dòng)。另一類是從重要性度量的思想出發(fā)，通過去除重要性小于閾值的骨架枝或骨架點(diǎn)從而實(shí)現(xiàn)骨架裁剪。Ogniewicz等人[18]先提出幾種基于長度的重要性度量。隨后，Couprie等人[19]提出一種二等分角的重要性度量。然而，這些方法得到的骨架由于缺失重要部分而不符合人類的視覺感知。為了解決這個(gè)問題，Bai等人[20]采用離散曲線演化(DCE)的思想，對(duì)物體的輪廓進(jìn)行片段分割，通過去除生成點(diǎn)處于同一片段的骨架點(diǎn)來實(shí)現(xiàn)骨架裁剪。因?yàn)檫@種方法并不改變輸入骨架的拓?fù)浣Y(jié)構(gòu)，所以它擁有比上述方法更好的效果，但是在最后的骨架中仍會(huì)存在少許冗余的骨架枝。

針對(duì)上述問題，本文提出一種基于貝葉斯模型的骨架裁剪方法。這種方法在骨架與形狀的隨機(jī)生長關(guān)系上，將貝葉斯概率思想應(yīng)用到骨架建模中，通過對(duì)模型的迭代優(yōu)化不斷移除骨架冗余分支，從而得到能保留形狀拓?fù)湫畔⑶医Y(jié)構(gòu)更加簡(jiǎn)單的裁剪骨架，算法的主要過程包括骨架提取、預(yù)處理、貝葉斯建模、優(yōu)化載剪。此外，本文在綜合考慮骨架重建誤差率和簡(jiǎn)潔率的基礎(chǔ)上，提出有效率作為骨架質(zhì)量的客觀評(píng)價(jià)指標(biāo)，幫助骨架最大程度滿足實(shí)際需求。

利用構(gòu)造出的貝葉斯概率模型，本文對(duì)不同的數(shù)據(jù)做了骨架裁剪實(shí)驗(yàn)。實(shí)驗(yàn)和數(shù)據(jù)結(jié)果表明，這種概率估計(jì)方法得到的骨架簡(jiǎn)潔有效，能準(zhǔn)確表示物體在視覺上重要的部分，且對(duì)于輪廓噪聲具有較好的魯棒性。

2 骨架的基本概念

本文主要是通過對(duì)形狀的骨架做概率估計(jì)從而獲得一個(gè)與人的視覺感知相一致的理想骨架。為了更清晰地了解骨架結(jié)構(gòu)，這里給出了與之相關(guān)的幾個(gè)定義：

圖1 骨架結(jié)構(gòu)示意圖

基于上述定義，本文認(rèn)為骨架是一個(gè)由不同軸線片段連接組成的幾何結(jié)構(gòu)。結(jié)構(gòu)中每條軸上的骨架點(diǎn)沿兩側(cè)生長，直至其分支與形狀邊界相交，從而形成對(duì)應(yīng)形狀的描述符。

綜上所述，一個(gè)輸入骨架應(yīng)滿足如下的約束條件：

3 貝葉斯模型

3.1貝葉斯基本理論

貝葉斯統(tǒng)計(jì)是一種系統(tǒng)的統(tǒng)計(jì)推斷方法，其基本思想是利用當(dāng)前的觀察數(shù)據(jù)對(duì)先驗(yàn)分布進(jìn)行更新，從而獲得后驗(yàn)分布，更新的知識(shí)又作為先驗(yàn)信息來啟動(dòng)下一輪的學(xué)習(xí)，最終推斷對(duì)應(yīng)參數(shù)在給定數(shù)據(jù)下的條件分布。

3.2先驗(yàn)函數(shù)

形狀骨架的先驗(yàn)函數(shù)用于測(cè)量整體骨架的簡(jiǎn)潔程度，我們認(rèn)為骨架分支數(shù)量越少且分支彎曲越小的骨架結(jié)構(gòu)越簡(jiǎn)單。這里引入偏轉(zhuǎn)角來度量骨架分支的彎曲度，其中偏轉(zhuǎn)角為曲線上任意兩條相鄰切線間的夾角。

在第2節(jié)中提到骨架是由不同軸線片段組成的，把這一系列片段命名為，其中為第個(gè)軸線片段上的骨架點(diǎn)。從每個(gè)中的離散點(diǎn)可以確定出各自的偏轉(zhuǎn)角序列，例如是和間的夾角。我們使用指數(shù)分布來描述軸線上的偏轉(zhuǎn)角：

綜上所述，當(dāng)骨架包含的軸線片段越少越直時(shí)，骨架的先驗(yàn)概率值就越大，而當(dāng)骨架分支數(shù)增加，或者骨架的任意一個(gè)軸線片段的曲率增加時(shí)，先驗(yàn)概率值都會(huì)減小。

3.3似然函數(shù)

貝葉斯模型中的似然函數(shù)用于測(cè)量骨架解釋形狀的準(zhǔn)確程度，本文引入隨機(jī)生長過程來描述似然模型，我們認(rèn)為分支垂直于軸向兩側(cè)橫向生長的骨架與形狀最匹配。然而在實(shí)際生長過程中，每條從骨架點(diǎn)處延伸出的分支都有隨機(jī)的長度和方向(如圖2)。因此，引入方向誤差和長度誤差來度量骨架與形狀間的擬合度，誤差值越小，骨架解釋形狀越準(zhǔn)確。

圖2 似然函數(shù)模型

理想的骨架是分支以標(biāo)準(zhǔn)的方向和長度進(jìn)行生長形成的骨架，其中標(biāo)準(zhǔn)方向?yàn)檩S的法向，標(biāo)準(zhǔn)長度為分支的期望半徑。令表示軸上骨架點(diǎn)與邊界局部鄰域點(diǎn)間的距離集合，則可以表示為一系列距離值的平均值，即

由于不同的骨架點(diǎn)有不同的期望半徑，因此用一個(gè)指數(shù)形式衰減的密度函數(shù)描述的分布為延遲常數(shù)。

實(shí)際的骨架是分支以隨機(jī)的方向和長度從各軸線兩側(cè)生長到形狀邊界的結(jié)果。其中，生長方向由分支在垂直軸的方向上附加隨機(jī)方向誤差形成。用表示形狀上邊界點(diǎn)的法向，則可以得到方向誤差的表達(dá)式為

因?yàn)樾螤钍枪羌茈S機(jī)生長的結(jié)果，所以骨架分支作為隨機(jī)生長的向量代表了形狀輪廓與形狀骨架間的對(duì)應(yīng)關(guān)系。從輪廓上的一個(gè)形狀點(diǎn)出發(fā)，可以沿分支估計(jì)出它對(duì)應(yīng)的責(zé)任骨架點(diǎn)。由這條分支產(chǎn)生的長度誤差和方向誤差能測(cè)量骨架產(chǎn)生形狀點(diǎn)的可能性，因此該形狀點(diǎn)的似然函數(shù)被定義為

假設(shè)骨架產(chǎn)生的所有形狀點(diǎn)是彼此獨(dú)立的，那么整體形狀的似然函數(shù)就是考慮所有形狀點(diǎn)似然函數(shù)的結(jié)果：

4 裁剪過程

基于最大化后驗(yàn)概率的目標(biāo)，提出一個(gè)針對(duì)候選分支裁剪的評(píng)估準(zhǔn)則：若去除某分支可使整體骨架的后驗(yàn)概率增大就裁剪該分支。

最大化式(1)等同于最小化其負(fù)對(duì)數(shù)，即

式(9)的最優(yōu)解在滿足約束條件的骨架空間基礎(chǔ)上產(chǎn)生，由于分支對(duì)骨架的影響有結(jié)構(gòu)復(fù)雜性和形狀描述準(zhǔn)確性兩方面，故評(píng)估某分支是否裁剪的標(biāo)準(zhǔn)實(shí)質(zhì)是衡量該分支增加的擬合形狀精確性能否超過它產(chǎn)生的額外結(jié)構(gòu)復(fù)雜性。其數(shù)學(xué)描述為：為當(dāng)前待評(píng)估的骨架，為候選分支，如果

具體的裁剪過程為：

(1)提取中軸作為初始骨架。

(2)對(duì)骨架點(diǎn)集作結(jié)構(gòu)劃分：

(a)按照第2節(jié)中的定義，計(jì)算出中軸骨架的中心點(diǎn)和端點(diǎn)；

(d)計(jì)算端分支：對(duì)每個(gè)端點(diǎn)進(jìn)行八鄰域范圍的骨架點(diǎn)搜索，依次將新的骨架點(diǎn)加入到搜索路徑中，直到新加入的骨架點(diǎn)為交叉點(diǎn)；

(e)計(jì)算骨架軸：用八鄰域搜索計(jì)算出中心點(diǎn)到各交叉點(diǎn)間的路徑。以交點(diǎn)數(shù)為依據(jù)對(duì)路徑做方向分組，則各分組中的最長路徑為對(duì)應(yīng)方向上的骨架軸。

(3)建立貝葉斯模型： 根據(jù)第3節(jié)中的定義，確定具體骨架的先驗(yàn)函數(shù)和似然函數(shù)。

(4)確定候選分支： 選端分支作為候選分支。

(5)估計(jì)出理想骨架： 用貝葉斯模型對(duì)候選分支進(jìn)行測(cè)試，若包含某分支會(huì)使整體后驗(yàn)概率變小，那么該分支就因未通過測(cè)試而被裁剪，反之將被保留。用同樣的方法在新骨架中迭代地測(cè)試剩余的候選分支以此得到一系列不同的骨架，最后在骨架序列中選擇出最優(yōu)骨架。

5 實(shí)驗(yàn)

本文算法采用MATLAB實(shí)現(xiàn)，所有實(shí)驗(yàn)在一臺(tái)Intel CORE 2 Duo 2.00 GHz CPU, 2 GB DDR2 RAM的Windows 7平臺(tái)上完成。以下幾組實(shí)驗(yàn)證明了本文骨架符合人類直觀視覺感知且對(duì)輪廓噪聲有良好的魯棒性。所有的原始骨架由文獻(xiàn)[10]中的算法產(chǎn)生，它通過距離變換計(jì)算出的骨架被認(rèn)為與中軸近似。

為了證明本文方法得出的骨架能很好符合人類視覺感知且有良好的抗噪性，這里對(duì)文獻(xiàn)[21]中的數(shù)據(jù)做了幾組骨架裁剪實(shí)驗(yàn)。其中，圖3為本文方法與文獻(xiàn)[10]的對(duì)比實(shí)驗(yàn)，圖3(a)為文獻(xiàn)[10]方法提取的近似中軸骨架，圖3(b)為本文基于貝葉斯模型裁剪出的最大后驗(yàn)概率骨架。從實(shí)驗(yàn)結(jié)果來看，各骨架的分支都能自然地對(duì)應(yīng)到形狀的各個(gè)部分，在包含形狀拓?fù)湫畔⒌幕A(chǔ)上，骨架還擁有更加簡(jiǎn)潔的結(jié)構(gòu)，這直接證明了本文算法的有效性。圖4給出了本文骨架在魯棒性方面的說明，通過對(duì)3組不同的數(shù)據(jù)加入輪廓噪聲，觀察并對(duì)比它們與無噪形狀的骨架裁剪情況。其中圖4(a)是本文方法在未加噪聲時(shí)提取的理想骨架，圖4(b)為本文方法在形狀邊界加噪聲時(shí)得到的裁剪骨架，實(shí)驗(yàn)結(jié)果表明，即使在輪廓噪聲中我們的裁剪骨架依然能保持穩(wěn)定的結(jié)構(gòu)，證明骨架具有良好的抗噪性。

圖3 不同形狀的裁剪骨架

圖4 有邊界噪聲時(shí)的形狀骨架

為了證明本文方法在剪枝效果上的優(yōu)勢(shì)，我們使用相同數(shù)據(jù)在文獻(xiàn)[22]的方法上做了測(cè)試。圖5與圖6為本文方法與文獻(xiàn)[22]的方法在剪枝效果方面的對(duì)比實(shí)驗(yàn)，其中圖5(a)和圖6(a)為原始的中軸骨架，圖5(b)和圖6(b)為文獻(xiàn)[22]方法提取到的裁剪骨架，圖5(c)和圖6(c)為應(yīng)用本文的貝葉斯模型估計(jì)出的裁剪骨架。在圖5中，從和模型的各末端部分可以看出本文方法可以解決文獻(xiàn)[22]中不能解決的規(guī)則形狀的剪枝問題。在圖6中，從樹的底部以及狗的頭部和后腿前端部分可以看出本文方法在局部小分支處理方面效果較文獻(xiàn)[22]更加顯著，說明本文骨架更逼近于人們的直觀視覺反映。

圖5 規(guī)則形狀骨架裁剪對(duì)比實(shí)驗(yàn)

圖6 不規(guī)則形狀骨架裁剪對(duì)比實(shí)驗(yàn)

綜合以上實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)由本文模型估計(jì)出的裁剪骨架既有簡(jiǎn)潔的結(jié)構(gòu)又能保持形狀的拓?fù)湫畔⑼瑫r(shí)還擁有魯棒的抗噪性，符合人類的視覺感知特性。

6 骨架質(zhì)量評(píng)估

為了定量評(píng)估裁剪骨架的質(zhì)量，需要計(jì)算骨架的重建誤差率，其定義式為

圖7 重建對(duì)比實(shí)驗(yàn)

表1圖7中各形狀骨架的重建誤差率

由于原始中軸的重建誤差為0，因此骨架質(zhì)量不能僅由重建誤差率來決定，需要同時(shí)考慮骨架的簡(jiǎn)潔程度。為此，我們構(gòu)造有效率參數(shù)為

表2形狀骨架的重建誤差率與簡(jiǎn)潔率

圖8 裁剪對(duì)比實(shí)驗(yàn)

圖9 有效率對(duì)比圖

7 結(jié)束語

本文提出一種基于貝葉斯模型的骨架裁剪方法，將骨架的概率分布作為先驗(yàn)函數(shù)，骨架生長的隨機(jī)過程作為似然函數(shù)，結(jié)合形狀信息構(gòu)建完整的貝葉斯模型。通過對(duì)模型的迭代優(yōu)化不斷移除端分支以獲取最優(yōu)的骨架結(jié)構(gòu)。在此基礎(chǔ)上，進(jìn)一步綜合考慮骨架重建誤差率及簡(jiǎn)潔率，提出骨架有效率的概念。通過將有效率作為骨架質(zhì)量的客觀指標(biāo)，從而實(shí)現(xiàn)對(duì)骨架的定量分析。本文算法在大量不同的形狀上得到驗(yàn)證，實(shí)驗(yàn)顯示本文方法對(duì)邊界噪聲具有較好的魯棒性，且裁剪出的骨架能簡(jiǎn)潔而精確的描述整體形狀信息，相比同類方法有效率更高。

參考文獻(xiàn)

[1] Gong Y, Lazebnik S, Gordo A,.. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval[J]., 2013, 35(12): 2916-2929.

[2] Kim V G, Chaudhuri S, Guibas L,.. Shape2pose: Human-centric shape analysis[J].(), 2014, 33(4): 70-79.

[3] Huang S S, Shamir A, Shen C H,.. Qualitative organization of collections of shapes via quartet analysis[J].(), 2013, 32(4): 96-96.

[4] Blum H. Biological shape and visual science (Part I)[J]., 1973, 38(2): 205-287.

[5] Xu J. A generalized morphological skeleton transform using both internal and external skeleton points[J]., 2014, 47(8): 2607-2620.

[6] Song Z, Yu J, Zhou C,Skeleton correspondence construction and its applications in animation style reusing[J]., 2013, 120(10): 461-468.

[7] Al Nasr K, Liu C, Rwebangira M,Intensity-based skeletonization of cryoEM gray-scale images using a true segmentation-free algorithm[J]./(), 2013, 10(5): 1289-1298.

[8] Mayya N and Rajan V T. Voronoi diagrams of polygons: A framework for shape representation[J]., 1996, 6(4): 355-378.

[9] Díaz-Pernil D, Pe?a-Cantillana F, and Gutiérrez-Naranjo M A. Cellular Automata in Image Processing and Geometry[M]. Berlin: Springer International Publishing, 2014: 47-63.

[10] Choi W P, Lam K M, and Siu W C. Extraction of the Euclidean skeleton based on a connectivity criterion[J]., 2003, 36(3): 721-729.

[11] Sobiecki A, Yasan H C, Jalba A C,Mathematical Morphology and Its Applications to Signal and Image Processing[M]. Berlin: Springer International Publishing, 2013: 425-439.

[12] Babu G R M, Srikrishna A, Challa K,An error free compression algorithm using morphological decomposition[C]. 2012 International Conference on Recent Advances in Computing and Software Systems (RACSS), Chennai, 2012: 33-36.

[13] Karimipour F and Ghandehari M. Transactions on Computational Science XX[M]. Berlin: Springer International Publishing, 2013: 138-157.

[14] Jalba A C, Kustra J, and Telea A C. Surface and curve skeletonization of large 3D models on the GPU[J]., 2013, 35(6): 1495-1508.

[15] Karimov A, Mistelbauer G, Schmidt J,.. ViviSection: skeleton-based volume editing[C]. Computer Graphics Forum, Leipzig, 2013, 32(3pt4): 461-470.

[16] Cicconet M, Geiger D, Gunsalus K C,.. Mirror symmetry histograms for capturing geometric properties in images[C]. 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, 2014: 2981-2986.

[17] Mokhtarian F and Mackworth A K. A theory of multiscale, curvature-based shape representation for planar curves[J]., 1992, 14(8): 789-805.

[18] Ogniewicz R L and Kübler O. Hierarchic voronoi skeletons[J]., 1995, 28(3): 343-359.

[19] Couprie M, Coeurjolly D, and Zrour R. Discrete bisector function and Euclidean skeleton in 2D and 3D[J]., 2007, 25(10): 1543-1556.

[20] Bai X, Latecki L J, and Liu W Y. Skeleton pruning by contour partitioning with discrete curve evolution[J]., 2007, 29(3): 449-462.

[21] Sebastian T B, Klein P N, and Kimia B B. Recognition of shapes by editing their shock graphs[J]., 2004, 26(5): 550-571.

[22] Shen W, Bai X, Yang X W,.. Skeleton pruning as trade-off between skeleton simplicity and reconstruction error[J]., 2013, 56(4): 1-14.

Approach of Skeleton Pruning with Bayesian Model

Qin Hong-xing Sun Ying

(,&,400065,)(&,&,400065,)

Considering the problem that most of the existing skeleton calculation methods exhibit extreme sensitivity to the shape noise, a Bayes based algorithm for the skeleton pruning is proposed . The algorithm models the skeleton and growth process with Bayesian statistics framework. Based on the model, an iterative optimization is performed to prune the candidate branches. Due to the fact that the existing reconstruction error can not evaluate the simplicity of skeletons well, a new concept called Effective Rate is proposed to make quantitative analysis on the pruned skeleton with taking the simplicity into consideration. The experiments show that the proposed algorithm is robust to the shape noise and acts better in simplifying the skeleton structure and representing shape accurately.

Skeleton; Shape; Pruning; Bayes; Geometry processing; Effective rate of skeleton

TP391

A

1009-5896(2015)09-2069-07

10.11999/JEIT150003

秦紅星 qinhx@cqupt.edu..cn

2015-01-05收到，2015-05-13改回，2015-06-29網(wǎng)絡(luò)優(yōu)先出版

國家自然科學(xué)基金青年科學(xué)基金(61100113)，國家教育部留學(xué)歸國基金教外司留[2012]940號(hào)，重慶市首批青年骨干教師項(xiàng)目(渝教人(2011)31號(hào))，重慶市基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目(cstc2013jcyjA40062)，重慶郵電大學(xué)學(xué)科引進(jìn)人才基金(A2010-12)和重慶市研究生科研創(chuàng)新項(xiàng)目(CYS14142)資助課題

秦紅星： 男，1977年生，教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)圖形學(xué)與可視化.

孫 穎： 女，1991年生，碩士，主要研究領(lǐng)域?yàn)閿?shù)字幾何處理.