秦紅星 孫 穎

?

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

秦紅星*孫 穎

(重慶郵電大學(xué)計算智能重慶市重點實驗室 重慶 400065)(重慶郵電大學(xué)計算機科學(xué)與技術(shù)學(xué)院 重慶 400065)

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

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

1 引言

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

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

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

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

2 骨架的基本概念

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

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

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

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

3 貝葉斯模型

3.1貝葉斯基本理論

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

3.2先驗函數(shù)

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

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

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

3.3似然函數(shù)

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

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

理想的骨架是分支以標準的方向和長度進行生長形成的骨架，其中標準方向為軸的法向，標準長度為分支的期望半徑。令表示軸上骨架點與邊界局部鄰域點間的距離集合，則可以表示為一系列距離值的平均值，即

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

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

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

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

4 裁剪過程

基于最大化后驗概率的目標，提出一個針對候選分支裁剪的評估準則：若去除某分支可使整體骨架的后驗概率增大就裁剪該分支。

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

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

具體的裁剪過程為：

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

(2)對骨架點集作結(jié)構(gòu)劃分：

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

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

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

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

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

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

5 實驗

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

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

圖3 不同形狀的裁剪骨架

圖4 有邊界噪聲時的形狀骨架

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

圖5 規(guī)則形狀骨架裁剪對比實驗

圖6 不規(guī)則形狀骨架裁剪對比實驗

綜合以上實驗結(jié)果，可以發(fā)現(xiàn)由本文模型估計出的裁剪骨架既有簡潔的結(jié)構(gòu)又能保持形狀的拓撲信息同時還擁有魯棒的抗噪性，符合人類的視覺感知特性。

6 骨架質(zhì)量評估

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

圖7 重建對比實驗

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

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

表2形狀骨架的重建誤差率與簡潔率

圖8 裁剪對比實驗

圖9 有效率對比圖

7 結(jié)束語

本文提出一種基于貝葉斯模型的骨架裁剪方法，將骨架的概率分布作為先驗函數(shù)，骨架生長的隨機過程作為似然函數(shù)，結(jié)合形狀信息構(gòu)建完整的貝葉斯模型。通過對模型的迭代優(yōu)化不斷移除端分支以獲取最優(yōu)的骨架結(jié)構(gòu)。在此基礎(chǔ)上，進一步綜合考慮骨架重建誤差率及簡潔率，提出骨架有效率的概念。通過將有效率作為骨架質(zhì)量的客觀指標，從而實現(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號，重慶市首批青年骨干教師項目(渝教人(2011)31號)，重慶市基礎(chǔ)與前沿研究計劃項目(cstc2013jcyjA40062)，重慶郵電大學(xué)學(xué)科引進人才基金(A2010-12)和重慶市研究生科研創(chuàng)新項目(CYS14142)資助課題

秦紅星： 男，1977年生，教授，主要研究領(lǐng)域為計算機圖形學(xué)與可視化.

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