段汕，毛振幗，謝長(zhǎng)江

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

1 問(wèn)題的引入

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

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

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

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

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

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

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

設(shè)H為骨架上所有分支點(diǎn)(度大于2)的集合，將中心點(diǎn)與H中所有點(diǎn)之間的最長(zhǎng)路徑稱(chēng)為骨架主軸.若該路徑方向的反方向上存在H中的點(diǎn)，則該點(diǎn)與中心點(diǎn)間的路徑與原骨架軸合并成新的骨架軸. 如圖2所示，路徑L(o，p1)最長(zhǎng)，但在其反方向上存在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]，若將骨架視為幾何圖，則骨架由有限個(gè)連接弧組成，這些連接弧稱(chēng)為骨架分支.由骨架主軸(亦稱(chēng)為零級(jí)骨架分支)沿著近似垂直于其外法線方向的最長(zhǎng)骨架分支稱(chēng)為一級(jí)骨架分支，由一級(jí)骨架分支沿著近似垂直于其外法線方向的最長(zhǎng)骨架分支稱(chēng)為二級(jí)骨架分支，以此類(lèi)推，n級(jí)骨架是由n-1級(jí)骨架分支沿著近似垂直于其外法線方向的最長(zhǎng)骨架分支.
圖2中路徑L(p1，p3)為一級(jí)骨架分支.

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

(1)

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

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

3 平衡算法

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

3.1 貝葉斯平衡策略

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

(2)

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

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

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

(3)

最終的近似骨架由

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

(4)

產(chǎn)生.

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

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

(5)

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

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

(6)

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

(7)

(8)

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

P(θ)∝exp(cosbθ).

(9)

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

(10)

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

3.3 平衡公式

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

(11)

這里a，b為控制參數(shù)，β為比例系數(shù)，參數(shù)及系數(shù)都將通過(guò)對(duì)圖像進(jìn)行大量算法實(shí)驗(yàn)，對(duì)實(shí)驗(yàn)結(jié)果作對(duì)比調(diào)整而得. (11)式表明：骨架各級(jí)分支轉(zhuǎn)角誤差越小，所對(duì)應(yīng)的分支對(duì)重構(gòu)圖像貢獻(xiàn)越大；重構(gòu)誤差越小，基于骨架的重構(gòu)圖像與原始圖像的匹配度越高，當(dāng)兩者同時(shí)達(dá)到最小時(shí)，平衡公式(11)將輸出最大值，此時(shí)骨架S對(duì)圖像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)方法. 本文提出的簡(jiǎn)化方法相對(duì)于常規(guī)方法是一個(gè)逆向的過(guò)程，采用以由中軸所確定的骨架主軸，即零級(jí)骨架為基礎(chǔ)的、平衡公式控制下的各級(jí)骨架分支逐級(jí)迭代添加的方法，最終獲取最優(yōu)近似骨架. 優(yōu)化算法具體實(shí)現(xiàn)過(guò)程包含以下幾個(gè)步驟:

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

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

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

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

(12)

(13)

(14)

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

(15)

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

5 實(shí)驗(yàn)檢測(cè)

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

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

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

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

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

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

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

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

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

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

(16)

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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