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

秦紅星 孫 穎

?

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

秦紅星*孫 穎

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

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

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

1 引言

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

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

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

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

2 骨架的基本概念

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

圖1 骨架結構示意圖

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

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

3 貝葉斯模型

3.1貝葉斯基本理論

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

3.2先驗函數

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

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

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

3.3似然函數

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

圖2 似然函數模型

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

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

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

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

假設骨架產生的所有形狀點是彼此獨立的，那么整體形狀的似然函數就是考慮所有形狀點似然函數的結果：

4 裁剪過程

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

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

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

具體的裁剪過程為：

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

(2)對骨架點集作結構劃分：

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

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

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

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

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

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

5 實驗

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

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

圖3 不同形狀的裁剪骨架

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

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

圖5 規則形狀骨架裁剪對比實驗

圖6 不規則形狀骨架裁剪對比實驗

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

6 骨架質量評估

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

圖7 重建對比實驗

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

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

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

圖8 裁剪對比實驗

圖9 有效率對比圖

7 結束語

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

參考文獻

[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網絡優先出版

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

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

孫 穎： 女，1991年生，碩士，主要研究領域為數字幾何處理.