一種改進的薄壁文物碎片特征輪廓線提取技術(shù)

李 康， 李 靜， 孫家澤， 耿國華， 馬忠玲， 劉 磊

(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710127)

一種改進的薄壁文物碎片特征輪廓線提取技術(shù)

李 康， 李 靜， 孫家澤， 耿國華， 馬忠玲， 劉 磊

(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710127)

針對使用一般的邊界提取方法提取三維網(wǎng)格模型特征輪廓線不完整問題，提出一種新的薄壁文物碎片特征輪廓線提取的綜合算法。區(qū)別了特征輪廓線和輪廓線的概念，引入主輪廓線和次輪廓線以及二級鄰接生長曲面的概念。主輪廓線的提取使用改進的基于邊重數(shù)判斷的提取方法；提出次輪廓線的一種新的提取方法：首先對三維網(wǎng)格曲面分割并識別斷裂面，然后對斷裂面的二級鄰接生長曲面進行曲面掃描，提取次輪廓線；最后從主輪廓線和次輪廓線中得到三維模型的特征輪廓線。使用該算法準確地提取了文物碎片的特征輪廓線，實驗結(jié)果表明此方法穩(wěn)定且準確。

三維薄壁文物模型；主次輪廓線；曲面分割；斷裂面二級鄰接生長；特征輪廓線

文物碎片三維模型的特征提取是計算機輔助文物虛擬復(fù)原研究中的關(guān)鍵環(huán)節(jié)，其提取準確性直接決定了碎片匹配效果。對于薄壁類的碎片來說，特征輪廓線是其最重要的特征之一，是碎片進行形狀互補匹配復(fù)原[1-2]的重要依據(jù)，文物碎片三維模型的特征輪廓線精確提取方法也成為碎片拼接關(guān)鍵技術(shù)之一。

碎片模型的特征輪廓線不同于輪廓線。碎片模型的特征輪廓線是指文物碎片的外表面與斷裂面的交線，輪廓線是指模型的曲面邊界線(本文稱其為主輪廓線)，如圖1所示。模型曲面邊界不能精確的表示文物碎片模型的邊界特征，這樣就不能簡單地提取主輪廓線作為模型的特征輪廓線進行匹配，而應(yīng)該結(jié)合斷裂面和外表面的交線(次輪廓線)共同確定三維模型特征輪廓線。

圖1 采集到部分斷裂面的碎片模型1

吳亞東和劉玉樹[3]提出了兩種新的抽取三維模型輪廓線算法，先利用輪廓線的局部極值特性來獲得部分輪廓邊，然后利用輪廓線的連通性，通過簡單的比較運算，即可獲得三維模型的外部輪廓線。Decarlo等[4]使用基于視角的特征線提取方法，提取三維模型形狀的細節(jié)特征，但該算法只能找到可見的外凸區(qū)域內(nèi)的主觀輪廓線。還有很多提取模型輪廓線的優(yōu)秀算法，但都只是提取了模型的邊界線，即主輪廓線，而非次輪廓線，而本文所要提取的特征輪廓線是主輪廓線和次輪廓線的組合，所以上述方法提取模型的特征輪廓線并不完整。

樊少榮等[5]提取的特征輪廓線是由內(nèi)輪廓線和外輪廓線組合而成，本文借鑒這一思路展開研究，提出了一種新的提取三維模型特征輪廓線的算法。將文獻[5]的內(nèi)外輪廓線分別重新定義為主、次輪廓線，因為模型的邊界線是輪廓線的主要組成部分，也是模型的一個明顯特征，所以稱其為主輪廓線更加貼切，而內(nèi)輪廓線是形成特征輪廓線的一個小部分，所以稱其為次輪廓線。本文算法主要步驟如下：①改進的基于邊重數(shù)判斷的主輪廓線提取方法；②區(qū)域生長算法對三維網(wǎng)格模型曲面分割，并用一種簡化的邊界移除法合并小的區(qū)域；③識別并提取斷裂面；④用掃描曲線掃描斷裂面的二級鄰接生長曲面，找出曲率極值點，得出次輪廓線；⑤根據(jù)所提取的主次輪廓線構(gòu)成三維文物模型的特征輪廓線。本文提取的碎片模型的特征輪廓線是與視角無關(guān)的空間輪廓曲線。

本文算法的流程圖如圖2所示。

圖2 本文算法流程圖

在主輪廓線提取部分，本文算法對文獻[5]算法進行了改進。采用并行搜索的思想改進了文獻[5]方法，節(jié)省了時間開銷。次輪廓線的提取部分，原文需要采集大量數(shù)據(jù)以計算出斷裂面和外表面的夾角合理閾值，以及包含次輪廓線的特征點集的兩次提取的繁瑣步驟，閾值確定的是否準確直接影響輪廓線的提取效果的好壞。而本文算法不依賴樣本數(shù)據(jù)的先驗知識，并且因為特征點集存在于斷裂面區(qū)域，所以直接提取斷裂面，一步確定包含次輪廓線的特征點集。

1 主輪廓線提取

本文算法中主輪廓線的提取結(jié)合并行搜索的思想，對基于邊重數(shù)判斷的主輪廓線提取算法進行了改進。采用兩條線路并行搜索的策略，以相反的方向同時尋找模型的邊界，兩條線路搜索出的邊界線共同合成模型的主輪廓線。邊的重數(shù)N指這條邊所屬的三角形個數(shù)，N取值1或2。本文改進后的算法主要步驟如下：

(1) 找出模型中任意一條N=1的邊，把這條邊的2個頂點P1和P2分別入棧S1和S2；

(2) 以2個棧的棧頂?shù)狞c為當(dāng)前2個起點，分別按照相反方向搜索模型的邊，在當(dāng)前點的鄰接點集中搜索與其構(gòu)成的邊的重數(shù)為 1的點， 把該點加入當(dāng)前棧；

(3) 判斷棧S1和S2的棧頂元素是否為同一個點，若是，轉(zhuǎn)步驟(4)，否則轉(zhuǎn)步驟(2)；

(4) 棧S1和S2中的點出棧，連接形成模型的主輪廓線。

對于圖3(a)中的碎片模型1和2，使用本文算法提取其主輪廓線的結(jié)果如圖3(b)所示，本文算法和文獻[5]算法在提取主輪廓線部分的基本原理是一樣的，所以提取的結(jié)果基本一樣。文獻[5]算法中用來存儲邊的棧是沒有意義的，因為棧中所存儲邊的2個點已經(jīng)記錄在點棧，而本文算法合理利用了2個棧，分別存儲2個方向搜索的邊界點，既省去了文獻[5]算法中冗余的空間占用，同時，并行搜索也使算法執(zhí)行時間減半，提高了算法的效率。表1是算法改進前后的執(zhí)行時間對比。

圖3 兩個碎片模型和主輪廓線

表1 算法執(zhí)行時間對比

2 次輪廓線提取

若碎片模型中包含斷裂面，只用邊界線來描述輪廓線會給后期的匹配拼接帶來困難，所以還需要提取碎片的次輪廓線。

實驗發(fā)現(xiàn)，文獻[5]算法存在很大的局限性，由于有的陶俑碎片表面較為復(fù)雜，很難計算斷裂面和外表面的夾角，所以采集大量數(shù)據(jù)計算出一個平均夾角值更為困難，而且計算的夾角閾值不適用于很多兵馬俑碎片，所以提取的特征輪廓線不準確，為后期碎片拼接帶來困難。

本文提取次輪廓線的算法流程和所參考的方法有很大不同，因為次輪廓線點集處于碎片斷裂面的邊緣部分，因此本文是從碎片斷裂面中提取模型的次輪廓線，算法主要分為以下4個步驟：①采用區(qū)域生長法對三維模型進行曲面分割；②合并小的分割曲面；③識別并提取模型斷裂面；④對斷裂面的二級鄰接生長曲面進行掃描得出內(nèi)輪廓線。

2.1 曲面分割并識別斷裂面

本文的次輪廓線需要從碎片的斷裂面提取，所以需要對碎片三維模型曲面分割，然后提取碎片的斷裂面。借鑒文獻[6]的網(wǎng)格模型分割方法，本文的曲面分割算法采用了一種基于曲率和法向量判斷的區(qū)域生長法。因為碎片模型表面信息復(fù)雜并且存在噪聲，所以曲面過度分割是不可避免，然后借鑒文獻[7]中邊界移除的思想，采用一種簡化的區(qū)域合并方法將相鄰塊整體融合從而對分割結(jié)果進行優(yōu)化處理。經(jīng)過上面的分析，通過以下3個主要步驟進行斷裂面的提?。?/p>

(1) 區(qū)域生長。本文算法根據(jù)對模型三角面片的幾何屬性值的判斷，進行區(qū)域生長。計算各個三角面片的曲率值和法向量，區(qū)域生長條件是欲生長單元T和已生長區(qū)域S的曲率差值和法向量夾角都滿足閾值條件。具體步驟如下：①選取模型中曲率均值最大的三角面片Ti作為種子生長點，并將Ti加入到空的生長區(qū)域Si中；②以深度優(yōu)先的搜索策略生長Ti的鄰接三角面片，把滿足生長條件的三角面片加入到已生長區(qū)域Si中，直到區(qū)域Si不能再加入三角面片，該區(qū)域生長結(jié)束；③選取模型中還未生長且曲率極大的三角面片 Tj作為下一個種子生長點，并加入到空的區(qū)域Sj中，按照第②步的方法生長區(qū)域。重復(fù)以上步驟，最后直到所有三角面片都進行了區(qū)域生長，最終將網(wǎng)格模型分割成多個曲面。

(2) 區(qū)域合并。由于模型噪聲和表面特性的影響，過度分割問題不可避免，經(jīng)過上面的區(qū)域生長，模型曲面會被分割成過多的小區(qū)域，需要對這些區(qū)域進行合并。每次選擇面積較小的區(qū)域判斷是否能和其相鄰區(qū)域進行合并。首先引入移除概率pij概念，即一個區(qū)域的邊界Ei相對于另一條邊界Ej被移除的概率，Pij公式定義如下：

其中，Length(Ei)是指邊界線Ei的長度，Avg(θi)指邊界線的平均二面角值。實驗發(fā)現(xiàn)邊界的平均二面角值比長度更加影響合并因素，所以取β取值為0.1。

若相鄰兩個區(qū)域的公共邊界線的pij在各自區(qū)域都是最大的，則其滿足區(qū)域合并的條件，移除這條邊界線，合并兩個區(qū)域，并更新合并后新的區(qū)域的信息。

以圖3(a)中的兵馬俑碎片模型2為例的實驗，在對模型進行區(qū)域生長后，模型被分割為多個小的區(qū)域(如圖4(a))，經(jīng)過區(qū)域合并，最終形成理想的被分割后的曲面，曲面被合并成了較大且有意義的區(qū)域(如圖4(b))。從表2中的數(shù)據(jù)可以看出，使用區(qū)域合并后，在沒有改變模型三角面片數(shù)的情況下，分割的曲面?zhèn)€數(shù)從16減少到2，有效合并了由于曲面過度分割產(chǎn)生的沒有意義的分割區(qū)域。

圖4 碎片曲面分割結(jié)果

表2 曲面分割結(jié)果

(3) 識別斷裂面。斷裂面和原始面的顯著區(qū)別在于斷裂面較原始面粗糙，所以根據(jù)所分割面上所有頂點的法矢擾動值[8]的大小并結(jié)合區(qū)域生長得到的各個分割區(qū)域的面積值，來區(qū)分模型的斷裂面和原始面。

為了避免過分依賴閾值導(dǎo)致算法穩(wěn)定性太差的問題，并且每個碎片模型的特征各不相同，不設(shè)定曲面法矢擾動閾值來作為區(qū)分斷裂面和原始面的條件。因為斷裂面的法矢擾動明顯大于原始面，所以根據(jù)曲面法矢擾動值的大小對比以及曲面的面積，區(qū)分碎片的斷裂面和原始面。若曲面的法矢擾動明顯小于其他曲面，則它為光滑的外表面，若曲面的法矢擾動明顯大于其他曲面，并且該曲面的面積值小于相對其他曲面較小，則它為斷裂面。

表3列出了碎片的曲面法矢擾動值和面積值，通過表中的數(shù)據(jù)可以看出曲面1為外表面，曲面2為斷裂面。

表3 識別模型斷裂面

2.2 斷裂面的二級鄰接生長

因為次輪廓線是外表面與斷裂面的交線，所以次輪廓線必定位于斷裂面的邊界，并且是特征值變化極值點。由于模型數(shù)據(jù)噪聲干擾或曲面分割階段一些不確定影響因素，提取的斷裂面邊界部分有可能數(shù)據(jù)丟失，為確保斷裂面的邊界線信息完整無誤，對斷裂面進行二級鄰接生長，使包含次輪廓線的特征點集位于曲面內(nèi)部，從而對曲面掃描找出特征極值點。

首先闡述一個概念：二階鄰接曲面生長。設(shè)斷裂面的三角面片集為 TriBreak，對斷裂面的每個三角面片TriBreak[i](i=0,1,2,···,a)，找出它的鄰接三角面片，若這個鄰接三角面片沒在 TriBreak中，則將其加入到 TriBreak，從而擴大了斷裂面區(qū)域，這稱為一級鄰接曲面生長。對一階鄰接曲面生長得到的鄰接三角面片再進行一次鄰接曲面生長稱為二級鄰接曲面生長，新形成的曲面為TriBreakNew。

假設(shè)圖 5(a)是經(jīng)過曲面分割得到的斷裂曲面三角面片集TriBreak，點G、A、B、C連接成的線段是已提取的部分主輪廓線。對斷裂曲面進行二級鄰接曲面生長后得到圖 5(b)所示的新的網(wǎng)格曲面TriBreak New，陰影部分為新加入的三角面片，圖5(b)為斷裂面的二級生長曲面。

圖5 曲面的二級鄰接生長

2.3 曲面掃描提取次輪廓線

由于次輪廓線的特征點集存在于斷裂面的二級鄰接生長曲面TriBreakNew上，所以需要分析計算曲面TriBreakNew的特征值，以找出特征點集。本文采用曲面掃描的方法，即用一組平行面去切割曲面TriBreakNew，通過分析掃描數(shù)據(jù)，計算這組掃描面上的曲率極值點，可獲得特征點集[9]。具體提取步驟如下：

(1) 計算曲面TriBreakNew的平均法向量a；

(2) 確定一組和a平行且互相平行的面組Sn作為掃描面；

(3) 求出掃描面組Sn和曲面TriBreakNew的交線組Ln，這組交線即為掃描線；

(4) 計算每條掃描線Li(i=1,2,···,n)上每點的曲率值，找出曲率極值點集Pi；

(5) 所有曲率極值點集Pn構(gòu)成最終的次輪廓線特征點集；

(6) 對點集Pn曲線擬合，確定次輪廓線。

圖 6是第一條掃描線L1的曲率情況分布直方圖，在掃描線L1上的第80個點附近出現(xiàn)曲率極值點，這個點將是次輪廓線點集的一部分。

圖6 掃描線的曲率分布情況

和文獻[5]算法的原理一樣，只是所掃描的曲面不同，文獻[5]算法中是對所求得的包絡(luò)次輪廓線特征點集的擬合曲面進行曲面掃描，而本文算法是對斷裂面的二級鄰接生長曲面掃描。

3 生成特征輪廓線

通過本文算法分別提取了碎片模型的主輪廓線Lm和次輪廓線Ln，而模型的特征輪廓線是外表面和斷裂面的交線，所以特征輪廓線是由主次輪廓線的共同組成。對于存在斷裂面的部分選取相應(yīng)的次輪廓線，否則選取主輪廓線，最后將這些選取的線段連接起來構(gòu)成閉合曲線Ls，即三角網(wǎng)格曲面模型的特征輪廓線。如圖7所示，以黑色的粗線標(biāo)示碎片的輪廓線，圖7 (a)表示主輪廓線，圖7(b)標(biāo)示次輪廓線，圖7(c)為通過主、次輪廓線的選取，確定最終的特征輪廓線。

圖7 經(jīng)主、次輪廓線連接而成的碎片特征輪廓線

4 實驗結(jié)果

實驗通過對陶俑碎片1和2特征輪廓線進行提取，對比了文獻[5]算法和本文算法。通過實驗結(jié)果可以看出，文獻[5]算法不是對所有碎片都能正確提取次輪廓線?？赡艹霈F(xiàn) 2種情況的錯誤提取：①由于閾值選擇的不合適，完全提取不到次輪廓線，如圖8(a)提取的碎片1的次輪廓線為空，因為碎片 2斷裂面和外表面的夾角較小，文獻[5]算法中確定的閾值過大，導(dǎo)致包含次輪廓線的特征點集沒有被提取到，所以最終形成的特征輪廓線也只是碎片的邊界線。②有的提取到的次輪廓線有偏差，如圖8(b)提取的碎片2的次輪廓線一部分是錯誤的，導(dǎo)致最終碎片的特征輪廓線還包含了錯誤的特征線。圖9(a)和9(b)是使用本文算法提取碎片1和2的特征輪廓線，觀察碎片模型可以看出提取的輪廓線是準確的。

圖8 文獻[5]算法實驗結(jié)果圖

圖9 改進后的算法實驗結(jié)果圖

表4是所提取碎片的輪廓線包含點的個數(shù)，從表中的數(shù)據(jù)可以更清楚地看到文獻[5]算法在提取有的碎片會出現(xiàn)提取錯誤的情況，例如通過文獻[5]算法所提取的碎片 1次輪廓線特征點數(shù)為 0的情況。

表4 實驗結(jié)果參數(shù)對比(個)

選取一個兵馬俑中的一些碎片模型，分別使用文獻[5]算法和本文算法提取碎片的特征輪廓線，圖10列出了其中3個碎片的實驗結(jié)果，第1列為3個碎片模型，第2列是使用文獻[5]算法提取的碎片的特征輪廓線，第3列是使用本文算法所提取的特征輪廓線的結(jié)果。從圖10可以看出對碎片1和碎片2使用文獻[5]算法所提取的特征輪廓線是有錯誤的，而本文算法正確提取了碎片模型的特征輪廓線。碎片 3使用本文算法都正確提取了模型的特征輪廓線。

通過實驗可以得出文獻[5]算法不是對所有碎片模型都能正確提取特征輪廓線，而本文算法對所有碎片都正確提取特征輪廓線。碎片1

圖10 文獻[5]算法和本文算法提取的特征輪廓線

5 結(jié) 束 語

本文借鑒已有的特征輪廓線的形成思想，提出了一種改進的特征輪廓線提取算法，對內(nèi)、外輪廓線的概念進行了重新命名定義，并分別對主、次輪廓線提取方法的都做了改進和變更。主輪廓線提取的算法合理利用了數(shù)據(jù)空間，并使算法執(zhí)行時間減半。在文獻[5]算法中次輪廓線提取部分過分依賴閾值的確定，穩(wěn)定性太差，本文算法通過從提取的斷裂面中獲得特征點集提取的次輪廓線是精確并且穩(wěn)定的，算法適用性強，針對薄壁文物碎片能正確地提取特征輪廓線，所以本文改進后的算法是穩(wěn)定且準確的。

[1] Cohen F, Taslidere E, Liu Zexi, et al. Virtual reconstruction of archaeological vessels using expert priors ＆SurfaceMarkings [C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.San Francisco, USA: IEEE ComputerSociety, 2010: 7-14.

[2] 周術(shù)誠. 三維復(fù)雜形狀拼接與破碎物體復(fù)原技術(shù)研究[D]. 西安: 西北大學(xué), 2007．

[3] 吳亞東, 劉玉樹. 三維模型輪廓線抽取算法[J]. 中國圖象圖形學(xué)報: A版, 2001, 6(2): 192-194.

[4] DeCarlo D, Finkelstein A, RusinkiewiczS, et al.Suggestive contours for conveyingShape [C]//Proc ofSIGGRAPH. New York: ACM Press, 2003: 848-855．

[5] 樊少榮, 茹少峰, 周明全, 等. 破碎剛體三角網(wǎng)格曲面模型的特征輪廓線提取方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2005, 17(9): 2004-2007.

[6] 曹彩霞, 董洪偉, 丁金仲. 基于區(qū)域生長的網(wǎng)格模型分割[J]. 計算機工程與應(yīng)用, 2008,44(31): 84-86.

[7] 楊 飛, 周 凡, 王若梅. 一種快速有效地基于區(qū)域增長的網(wǎng)格分割算法[C]//第六屆全國幾何設(shè)計與計算學(xué)術(shù)會議論文集, 大連, 2013.

[8] Huang Qixing, FloryS, Gelfand N, et al. Reassembling fractured objects by geometricMatching [J]. ACM Transactions on Graphics, 2006, 25(3): 569-578．

[9] Deschenes F, Ziou D. Detection of line junctions and line terminations using curvilinear features [J]. Pattern Recognition Letters, 2000, 21(6-7): 637-649.

An Improved Technique of Extracting Feature Contour from Thin-Walled Cultural Relic Fragments

Li Kang, Li Jing, Sun Jiaze, Geng Guohua, Ma Zhongling, Liu Lei
(School of InformationScience and Technology, Northwest University, Xi′anShaanxi 710127, China)

Aiming at the problem of incomplete feature contour extraction for 3DMeshModel by using GeneralMethod of detecting the edge, a new integrated algorithm of extracting feature contour from thin-walled cultural relic fragments is proposed. This paper distinguished the concept of feature contour from contour. Then it introduced theMain contours andSecondary contours, and proposed the concept of twice adjacent growth ofSurfaces. The algorithm used the improvedMethod based on edge weight number judgment to extract theMain contours; a newMethod of extracting theSecondary contours is proposed. Firstly, theSurface of 3DMesh isSegmented and the fractureSurface is recognized. Then the algorithmScans the two adjacentSurfaces of growth of fractureSurface withSurface to extract theSecondary contours. Finally, it could get the feature contour of 3DMeshModel from theMain contours andSecondary contours. It extracted the feature contour of cultural relic fragments accurately with this algorithm. The experimental resultsShow that thisMethod is efficient and accurate.

3D thin-walled cultural relic fragments;Main andSecondary contours;SurfaceSegmentation; twice adjacent growth of fractureSurface; feature contour

A

2095-302X(2015)02-0251-06

2014-10-08；定稿日期：2014-10-24

國家自然科學(xué)基金面上項目(61373117)；陜西省科技統(tǒng)籌創(chuàng)新工程計劃資助項目(2011KTCG03-08)；陜西省教育廳產(chǎn)業(yè)化培育資助項目(2012JC24)

李 康(1980–)，男，陜西寶雞人，講師，博士。主要研究方向為計算機可視化技術(shù)。E-mail：854092@qq.com

TP 391