段汕，毛振幗，謝長江

(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，武漢 430074)

1 問題的引入

自BLUM提出基于中軸變換[1]的骨架提取方法開始，各種骨架提取算法相繼涌現(xiàn)，這些方法所提取的骨架可以用于形狀描述，但大多包含大量的冗余骨架成分，且基于中軸變換所提取的骨架對邊緣噪聲往往較為敏感，使骨架穩(wěn)定性受到影響. 針對這個問題，研究者們提出了許多改進(jìn)方法[2-6]，其中FELDMAN J和SINGH M對形狀骨架的優(yōu)化提取進(jìn)行了相關(guān)研究[7]，提出獲取最大后驗概率(MAPS)的貝葉斯模型方法，將貝葉斯法則運(yùn)用于骨架生成，建立了最優(yōu)骨架提取的算法框架. SHEN W[8]以及秦紅星[9]等人則通過對貝葉斯模型方法的改進(jìn)，提出了基于中軸的骨架修剪方法，這些方法能有效地提取簡潔且能較為準(zhǔn)確地表示形狀的骨架成分.

本文在相關(guān)研究成果的基礎(chǔ)上，將貝葉斯模型方法運(yùn)用于基于圖像重構(gòu)誤差控制下的骨架簡化問題，通過建立平衡算法實(shí)現(xiàn)重構(gòu)精度與骨架簡化的平衡統(tǒng)一. 利用重構(gòu)誤差及骨架簡潔度作為控制參數(shù)，對圖像中軸所包含的骨架分支進(jìn)行優(yōu)選. 在算法的設(shè)計中，通過對骨架分支級別的設(shè)置，運(yùn)用控制參數(shù)和平衡算法，在骨架主軸的基礎(chǔ)上通過添加相關(guān)各級別的骨架分支，實(shí)現(xiàn)對骨架分支的優(yōu)選，最終獲得圖像的最優(yōu)近似骨架.

2 骨架相關(guān)基本概念

本文主要通過對形狀中軸進(jìn)行簡化來獲得最優(yōu)近似骨架，為了更明確地說明骨架結(jié)構(gòu)，首先給出一些相關(guān)概念.

目標(biāo)對象X的外形輪廓稱為形狀. 按照BLUM關(guān)于中軸的定義，嵌入形狀X內(nèi)部且與X至少在兩點(diǎn)相切的最大圓盤圓心的全體稱為形狀X的中軸，記為M. 形狀X的骨架是與中軸M具有相同拓?fù)浣Y(jié)構(gòu)的M的任一子集，記為S.

若骨架點(diǎn)s(s∈S)的八鄰域內(nèi)有n個骨架點(diǎn)，則稱其度為n(0≤n≤8)，見圖1.骨架上半徑最大的圓盤的圓心稱為骨架中心點(diǎn)(如圖2中的點(diǎn)o). 由骨架點(diǎn)到其八鄰域中鄰接骨架點(diǎn)的方向稱為正方向.

圖1 骨架點(diǎn)八鄰域示意圖Fig.1 Schematic diagram of the eight domain of skeleton point

設(shè)H為骨架上所有分支點(diǎn)(度大于2)的集合，將中心點(diǎn)與H中所有點(diǎn)之間的最長路徑稱為骨架主軸.若該路徑方向的反方向上存在H中的點(diǎn)，則該點(diǎn)與中心點(diǎn)間的路徑與原骨架軸合并成新的骨架軸. 如圖2所示，路徑L(o，p1)最長，但在其反方向上存在H中的點(diǎn)p2，則將路徑L(o，p1)與L(o，p2)合并成骨架主軸L(p1，p2).

圖2 骨架結(jié)構(gòu)示意圖Fig.2 Schematic diagram of skeleton structure

根據(jù)文獻(xiàn)[10]，若將骨架視為幾何圖，則骨架由有限個連接弧組成，這些連接弧稱為骨架分支.由骨架主軸(亦稱為零級骨架分支)沿著近似垂直于其外法線方向的最長骨架分支稱為一級骨架分支，由一級骨架分支沿著近似垂直于其外法線方向的最長骨架分支稱為二級骨架分支，以此類推，n級骨架是由n-1級骨架分支沿著近似垂直于其外法線方向的最長骨架分支.
圖2中路徑L(p1，p3)為一級骨架分支.

基于骨架S的形狀X的重建R(S)可以表示為：

(1)

其中B(s,ρ(s))是以s為圓心，ρ(s)為半徑的圓盤，ρ(s)表示骨架點(diǎn)s∈S所對應(yīng)的最大圓盤半徑，θρ(s)=ρ(s)Bo=B(s,ρ(s))，Bo為單位圓盤，δθρ是以θρ(s)為結(jié)構(gòu)元的形態(tài)膨脹變換.

若S=M，則R(S)=M，即由中軸M可以完全重構(gòu)形狀X. 受邊界噪聲和擾動的影響，中軸M往往包含著一些偽骨架分支，且其構(gòu)成較為復(fù)雜，在(1)式的重構(gòu)成分中存在大量的冗余.針對中軸的這一特點(diǎn)，許多學(xué)者對中軸進(jìn)行了修剪，以達(dá)到對中軸的簡化，所獲得的骨架僅保留中軸的主體骨架成分，且含有足夠多的信息，可使重構(gòu)圖像達(dá)到某一個精度范圍.本文以此為研究目標(biāo)，將貝葉斯模型方法運(yùn)用于基于圖像重構(gòu)誤差控制下的骨架簡化問題，通過建立平衡算法實(shí)現(xiàn)重構(gòu)誤差與骨架簡化的平衡統(tǒng)一.利用重構(gòu)誤差及骨架簡潔度作為控制參數(shù)，對圖像中軸所包含的骨架分支進(jìn)行優(yōu)選.在算法的設(shè)計中，通過對骨架分支級別的設(shè)置，運(yùn)用控制參數(shù)和平衡算法，在骨架主軸的基礎(chǔ)上通過添加相關(guān)各級別的骨架分支，實(shí)現(xiàn)對骨架分支的優(yōu)選，最終獲得圖像的最優(yōu)近似骨架.

3 平衡算法

費(fèi)爾德曼等學(xué)者[7]所提出的基于貝葉斯估計的最大后驗骨架MAPS(the maximum a posteriori skeleton)生長算法是實(shí)現(xiàn)重構(gòu)精度與骨架簡化平衡統(tǒng)一的一種策略，它通過引入基于骨架的重構(gòu)誤差及描述骨架簡潔性的簡潔度兩個量化指標(biāo)，以同時達(dá)到低誤差和高簡潔度的平衡為目標(biāo)，提出了形狀骨架的優(yōu)化算法.

3.1 貝葉斯平衡策略

貝葉斯模型方法[7]的基本思想是將骨架的形成視為一隨機(jī)生長過程，運(yùn)用貝葉斯法則：

(2)

提供平衡策略，這里Sj是構(gòu)成骨架S的有限個連接弧. 似然函數(shù)P(X|S)可視作骨架生長模型，用于刻畫骨架生長的準(zhǔn)確度. 骨架的簡潔度定量描述為骨架分支少且分支曲率小，采用先驗概率P(S)加以刻畫，所涉及的概率分布均采用指數(shù)分布作為近似.

對于(2)式中的分母，由全概率公式有：

P(S|X)=αP(X|S)P(S),

(3)

最終的近似骨架由

S*=argmin(-logP(S|X))

(4)

產(chǎn)生.

3.2 重構(gòu)誤差與骨架簡潔度

本文將貝葉斯骨架生長模型方法[7]的基本思想運(yùn)用于對中軸的修剪上，以獲取最優(yōu)近似骨架.首先要解決的問題是，如何基于中軸對重構(gòu)誤差和骨架簡潔度進(jìn)行具體量化.通過文獻(xiàn)[8]可知，重構(gòu)誤差的一個常用的估計方法是通過設(shè)置：

(5)

對誤差進(jìn)行測量，這里Λ(·)是基于像素或區(qū)域的面積測量運(yùn)算. 骨架的生長模型P(X|S)所描述的是基于骨架的重構(gòu)圖像與原始圖像的相似程度，相似程度越高即重構(gòu)誤差越小.由文獻(xiàn)[8]可知，重構(gòu)誤差近似服從指數(shù)分布，故?。?/p>

P(X|S)∝exp(-λσ),

(6)

其中λ為分布參數(shù).

(7)

(8)

利用Von. Mises分布[7]特點(diǎn)，所有n級骨架分支關(guān)于n-1級骨架分支轉(zhuǎn)角誤差之和θ服從Mises分布. 若將Z=eiθ作為隨機(jī)變量，則θ～V(0,b)，即:

P(θ)∝exp(cosbθ).

(9)

骨架分支數(shù)量是對骨架簡潔度的另一衡量標(biāo)準(zhǔn)，骨架越簡潔，其包含的分支越少，分支的總長度μ(S)就越小，優(yōu)選骨架點(diǎn)落在最優(yōu)近似骨架上的可能性就越大，這意味著骨架簡潔度P(S)與μ(S)成反比：

(10)

其中分母的設(shè)計使得P(S)∈[0,1].

3.3 平衡公式

利用貝葉斯平衡策略的基本思想，在以上關(guān)于骨架重構(gòu)誤差和骨架簡潔度量化表示的基礎(chǔ)上，利用(5)～(10)式及相關(guān)變量所服從的分布特點(diǎn)，引入平衡公式：

(11)

這里a，b為控制參數(shù)，β為比例系數(shù)，參數(shù)及系數(shù)都將通過對圖像進(jìn)行大量算法實(shí)驗，對實(shí)驗結(jié)果作對比調(diào)整而得. (11)式表明：骨架各級分支轉(zhuǎn)角誤差越小，所對應(yīng)的分支對重構(gòu)圖像貢獻(xiàn)越大；重構(gòu)誤差越小，基于骨架的重構(gòu)圖像與原始圖像的匹配度越高，當(dāng)兩者同時達(dá)到最小時，平衡公式(11)將輸出最大值，此時骨架S對圖像X描述的準(zhǔn)確度最高. 因此，最優(yōu)近似骨架應(yīng)滿足f(θ,σ|S)取得最大值，即

maxf(θ,σ|S)?min(-logf(θ,σ|S)),

因此，最優(yōu)近似骨架產(chǎn)生于：

S*=argmin(-logf(θ,σ|S)).

4 修剪算法

本節(jié)將在以上所研究的骨架提取平衡算法的基礎(chǔ)上，給出獲取最優(yōu)近似骨架的具體實(shí)現(xiàn)方法. 本文提出的簡化方法相對于常規(guī)方法是一個逆向的過程，采用以由中軸所確定的骨架主軸，即零級骨架為基礎(chǔ)的、平衡公式控制下的各級骨架分支逐級迭代添加的方法，最終獲取最優(yōu)近似骨架. 優(yōu)化算法具體實(shí)現(xiàn)過程包含以下幾個步驟:

1)確定骨架主軸S(0)：以中軸作為初始骨架，根據(jù)第二小節(jié)的定義，確定中心點(diǎn)，運(yùn)用八鄰域法搜索計算得到主軸，稱為零級近似骨架成分；

2)向骨架主軸從低到高逐級添加各級骨架分支：當(dāng)近似骨架達(dá)到所設(shè)定的重構(gòu)精度時，停止迭代添加；

3)各級近似骨架成分迭代生成方法：令Ei(i=1,2,…,n)為添加入第i-1級近似骨架成分的i級骨架分支，則有以下遞推關(guān)系式：

S(0)=S，S(i)=S(i-1)+Ei.

(12)

(13)

(14)

其中η為一個不大的正數(shù)，運(yùn)用max函數(shù)可以提取出簡潔度與重構(gòu)誤差度比重最大的骨架分支，即又短又直且包含形狀拓?fù)湫畔⒍嗟墓羌芊种?用arg函數(shù)求出大權(quán)重值對應(yīng)的那些分支，即構(gòu)成所添加的第j個i級骨架分支：

(15)

5)最優(yōu)近似骨架：利用迭代公式S(i)=S(i-1)+Ei，重復(fù)上述過程，直到最新獲得的近似骨架成分S(i)滿足Λ(X-R(S(i)))≤ε，則終止執(zhí)行，此時的S(i)即為所求最優(yōu)近似骨架.

5 實(shí)驗檢測

算法測試?yán)肕ATLAB編程實(shí)現(xiàn)，中軸是由MATLAB自帶的骨架提取函數(shù)產(chǎn)生的. 取β=1，b=10,a=1/π來進(jìn)行如下所有實(shí)驗.

本節(jié)將從算法有效性、骨架重構(gòu)質(zhì)量、骨架穩(wěn)定性、算法優(yōu)越性等幾個方面來進(jìn)行實(shí)驗.為了說明本文算法的有效性，選取以下幾幅圖形進(jìn)行實(shí)驗.
圖3(a)為輸入圖形及中軸，圖3(b)為本文算法獲得的骨架以及重構(gòu)形狀，圖3(c)為重構(gòu)誤差圖. 實(shí)驗結(jié)果顯示圖3(b)中各骨架分支能較好地對應(yīng)到形狀的各個部分，跟圖3(a)相比，本文算法所得骨架不僅保留了形狀的拓?fù)湫畔⑶医Y(jié)構(gòu)更加簡潔，誤差也僅僅表現(xiàn)在圖像極少部分邊界上.

圖3 幾組圖形的骨架修剪結(jié)果及重構(gòu)對比實(shí)驗Fig.3 Results of skeleton pruning and reconstruction contrastive experiment of several groups of graphics

表1給出了圖3中相關(guān)重構(gòu)誤差率及骨架長度對比差值. 表1的數(shù)據(jù)和圖3的視覺效果顯示：在對圖像的描述上，本文算法得到的骨架不僅具有良好的準(zhǔn)確性，同時所占用的儲存空間相對較少.

表1 圖3中各個形狀的骨架重構(gòu)誤差率及骨架長度差Tab.1 The error rate of skeleton reconstruction and the difference of skeleton length in each shape inFig.3

為了說明本文算法的穩(wěn)定性，選取兩組形狀來進(jìn)行測試，通過對形狀邊界進(jìn)行一定程度的干擾來檢測骨架的變化情況.
圖4(a)為無噪聲情況下提取的中軸，圖4(b)為無噪聲情況下本文算法所提取的骨架；圖4(c)為加噪聲情況下提取的中軸，圖4(d)為加噪聲情況下本文算法所提取的骨架. 通過對比可以看出，邊緣噪聲干擾對中軸的影響較大，但本文方法獲得的骨架則表現(xiàn)出較好的穩(wěn)定性.

圖4 骨架的穩(wěn)定性對比實(shí)驗Fig.4 Comparison experiment on the stability of skeleton

為了表明本文算法在骨架簡潔效果上的改進(jìn)，本文選取了一個規(guī)則形狀的大寫字母E、不規(guī)則形狀烏龜和樹與文獻(xiàn)[8]中的方法進(jìn)行對比測試.
圖5(a)為中軸，圖5(b)為用文獻(xiàn)[8]提出的方法簡化得到的骨架，圖5(c)為本文算法簡化得到的骨架. 由實(shí)驗結(jié)果可以看出，與文獻(xiàn)[8]方法提取的骨架相比，本文的方法在處理規(guī)則形狀以及一些小分支上效果更好.

圖5 本文方法與文獻(xiàn)[8]方法間的骨架修剪對比實(shí)驗Fig.5 Comparison of skeleton pruning experiments between the method of this paper and the method of reference[8]

為了便于對兩種方法進(jìn)行對比，引入有效率指標(biāo)：

(16)

該公式表明，重構(gòu)誤差率越小、骨架簡潔度越高時，有效率越大，骨架整體效果也會越好. 針對兩個不規(guī)則形狀，表2給出了與文獻(xiàn)[8]方法進(jìn)行對比的結(jié)果(E屬于規(guī)則圖形，故未納入表2).

表2 圖5中不規(guī)則形狀的數(shù)據(jù)對比Tab.2 Comparison of data of irregular shapes inFig.5

除此之外，本文還做了一組與文獻(xiàn)[9]方法的對比測試實(shí)驗.
圖6(a)為形狀中軸，圖6(b)為文獻(xiàn)[9]方法修剪得到的骨架，圖6(c)為本文算法修剪得到的骨架，其重構(gòu)數(shù)據(jù)對比見表3.

圖6 本文方法與文獻(xiàn)[9]方法間的骨架修剪對比實(shí)驗Fig.6 Comparison of skeleton pruning experiments between the method of this paper and the method of reference[9]

形狀重構(gòu)誤差率σ本文方法文獻(xiàn)[9]骨架簡潔度P(S)本文方法文獻(xiàn)[9]有效率ω本文方法文獻(xiàn)[9]駱駝0.06000.0445O.00310.00343.23.0

表2和表3中有效率一欄是(16)式計算結(jié)果擴(kuò)大1000倍得到的數(shù)據(jù). 將文獻(xiàn)[8]、文獻(xiàn)[9]與本文相關(guān)數(shù)據(jù)進(jìn)行對比，盡管本文的重構(gòu)誤差率高于其他兩種方法，但本文算法的重構(gòu)誤差是可以控制的，并且獲得的重構(gòu)圖像在形狀上仍然保留著原圖像大部分的形狀和拓?fù)涮卣? 通過控制重構(gòu)誤差，本文的骨架簡潔率優(yōu)于文獻(xiàn)[8]和文獻(xiàn)[9]，并且有效率也優(yōu)于這兩種方法，這表明本文方法在骨架簡潔度以及整體效果上更好.

除此之外，本文的方法在運(yùn)算速度上也快于文獻(xiàn)[8]和文獻(xiàn)[9]的方法. 文獻(xiàn)[8]與文獻(xiàn)[9] 給出的算法每次迭代只能優(yōu)選出一條骨架分支，而本文可以一次性選取多條符合條件的骨架分支，從而減少了迭代次數(shù). 另外，文獻(xiàn)[8]和文獻(xiàn)[9]每次迭代修剪時都會保存當(dāng)前骨架，在完成所有分支刪減后，還要將所有迭代產(chǎn)生的一系列不同的骨架再進(jìn)行一次對比運(yùn)算，才能最終產(chǎn)生出優(yōu)選骨架，而本文則直接在骨架主軸上添加各級分支，以更新骨架直到骨架到達(dá)指定重構(gòu)誤差才停止運(yùn)算. 從這個方面來說，本文的算法復(fù)雜度較低，運(yùn)算速度也優(yōu)于文獻(xiàn)[8]和文獻(xiàn)[9]，且這種優(yōu)勢在越復(fù)雜的形狀處理上體現(xiàn)得越充分.

6 結(jié)語

本文通過改進(jìn)費(fèi)爾德曼和辛格提出的貝葉斯模型，建立了一個用于骨架簡化的平衡公式，利用平衡公式將滿足條件的骨架分支迭代添加入骨架主軸中，以獲得最優(yōu)近似骨架. 同時本文還從算法有效性、骨架重構(gòu)質(zhì)量、骨架穩(wěn)定性、算法優(yōu)越性等幾個方面進(jìn)行了實(shí)驗測試，實(shí)驗結(jié)果表明本文的算法是有效的，本文方法所獲得的近似骨架不僅簡潔且能保證良好的形狀視覺呈現(xiàn). 相比其他同類方法，本文方法在骨架簡潔性、整體效果以及運(yùn)算速度等方面都有所改進(jìn).