中文--基于鄰近徑向基函數(shù)的三角網(wǎng)格模型的孔洞自動(dòng)修補(bǔ)技術(shù)

1、<p><b>　　中文6222字</b></p><p>　　出處：3D Data Processing, Visualization, and Transmission, Third International Symposium on. IEEE, 2006: 727-734</p><p>　　基于鄰近徑向基函數(shù)的三角網(wǎng)格模型的</p>

2、<p><b>　　孔洞自動(dòng)修補(bǔ)技術(shù)</b></p><p>　　John Branch,Flavio Prieto, Pierre Boulanger</p><p><b>　　發(fā)表于2006年</b></p><p><b>　　摘 要</b></p><p&g

3、t;　　僅僅應(yīng)用傳統(tǒng)造型技術(shù)生成實(shí)體模型是困難而復(fù)雜的，而逆向工程能夠很好地解決這些問(wèn)題。在逆向工程中，快速光學(xué)掃描測(cè)量常常地用于從幾個(gè)方向?qū)嶓w進(jìn)行采樣，收集采樣數(shù)據(jù)，并把數(shù)據(jù)集成到三角網(wǎng)格實(shí)體模型的區(qū)域圖像。實(shí)際中，由于視角限制形成測(cè)量盲區(qū)，自遮擋和測(cè)不到等原因，實(shí)體表面的某些區(qū)域通常沒(méi)有被采樣，在模型中人為地留下一些孔洞。</p><p>　　本文提出一種新穎的自動(dòng)修補(bǔ)三角網(wǎng)格模型孔洞的算法。本算法開(kāi)始于孔洞

4、邊界的搜索。孔洞的邊界處的三角形為邊界三角形，孔洞的邊界就是由邊界三角形互相不共享的邊組成的封閉路徑。根據(jù)孔洞邊界上的點(diǎn)對(duì)邊界進(jìn)行B樣條曲線擬合，再根據(jù)擬合結(jié)果計(jì)算孔洞邊界的撓率變化平均值，最后通過(guò)撓率變化的極限值判斷該孔洞是否屬于人為孔洞。判斷人為孔洞后，依托鄰近區(qū)域，運(yùn)用徑向基函數(shù)插值自動(dòng)修補(bǔ)孔洞。該算法在實(shí)驗(yàn)中取得了理想的結(jié)果。</p><p><b>　　1簡(jiǎn)介</b></p&

5、gt;<p>　　在真實(shí)的環(huán)境中，運(yùn)用傳統(tǒng)造型技術(shù)，很難生成精確的實(shí)體幾何模型。激光測(cè)距儀[5]與被采樣對(duì)象在幾何上相對(duì)獨(dú)立且數(shù)據(jù)獲取時(shí)間極短，故使用激光測(cè)距儀更具吸引力。深度和顏色圖象的綜合運(yùn)用前途樂(lè)觀，并且創(chuàng)新地被用于高真實(shí)度視覺(jué)感受的實(shí)現(xiàn)[15，16]。然而，由于實(shí)體表面性質(zhì)(例如低反射率或鏡面全反射)，自遮擋和測(cè)不到等原因，常常不能掃描到一些曲面單元，導(dǎo)致部分用于重構(gòu)實(shí)體的數(shù)據(jù)的缺失并最終在模型中引入了孔洞。由上述

6、不完整數(shù)據(jù)集合生成高質(zhì)量的網(wǎng)格幾何模型依然十分困難 [24]。考慮到實(shí)現(xiàn)完全掃描真實(shí)環(huán)境的技術(shù)難題和經(jīng)濟(jì)成本，通過(guò)改進(jìn)殘缺的數(shù)據(jù)集合半自動(dòng)或自動(dòng)地提高造型質(zhì)量的工具值得期待。 </p><p>　　三角網(wǎng)格模型中的孔洞修補(bǔ)問(wèn)題可以分為兩個(gè)子問(wèn)題：孔洞識(shí)別和基于鄰近有用數(shù)據(jù)的缺失數(shù)據(jù)重構(gòu)。兩個(gè)問(wèn)題都很重要，對(duì)于幾何內(nèi)容豐富的實(shí)體（例如逼真的雕塑），在掃描它們過(guò)程中生成的孔洞一般非常復(fù)雜[9]。 然而，在許多實(shí)際案件

7、中，如掃描那些光順且平整的區(qū)域多的內(nèi)部環(huán)境(例如，家里或辦公室內(nèi)的環(huán)境)的時(shí)候，在深度圖像中生成的孔洞可以簡(jiǎn)化拓?fù)潢P(guān)系。此時(shí)，更簡(jiǎn)單的用于識(shí)別孔洞和參數(shù)化鄰近的算法可以避免一般情況下產(chǎn)生的問(wèn)題。 </p><p>　　本文提出一種新穎的自動(dòng)識(shí)別和修補(bǔ)較光順表面區(qū)域上孔洞的算法。但是本算法僅適用于光滑表面上的孔洞，而不是提供面向一般孔洞修補(bǔ)問(wèn)題的解決方案。本算法概念上非常簡(jiǎn)單，使用起來(lái)十分直接。本算法采用三角網(wǎng)格模

8、型進(jìn)行邊界分析(是否屬于一個(gè)三角形)。界限邊構(gòu)成環(huán)的存在代表孔洞產(chǎn)生。因此，一旦找到界限邊，算法將追蹤整個(gè)邊界區(qū)域。邊界環(huán)上的點(diǎn)最終將進(jìn)行擬合，以用于孔洞修補(bǔ)的插值計(jì)算?？锥脆徑c(diǎn)集通過(guò)徑向基函數(shù)插值擬合出表面。本算法一個(gè)重要特點(diǎn)是能夠保證重構(gòu)補(bǔ)丁光順地融入原始表面。</p><p>　　而且，重構(gòu)后的表面將保存原始網(wǎng)格的采樣率。如果新點(diǎn)不能滿足以上條件，它們將進(jìn)行下一步處理。算法是在用于生成網(wǎng)格模型的表面運(yùn)行，

9、故可以使用任何重構(gòu)技術(shù)且算法本身僅受限于孔洞尺寸。本文算法在真正的數(shù)據(jù)集合上的高效率且能極大地改善三角網(wǎng)格模型的整體質(zhì)量得到了詳盡的展示。 </p><p>　　本文各部分組織如下：第1部分是簡(jiǎn)介，第2部分簡(jiǎn)述前置處理，第3部分詳述孔洞修補(bǔ)算法，第4部分是算法結(jié)果，第5部分是論文總結(jié)和未來(lái)展望。</p><p>　　2已有研究和相關(guān)成果</p><p>　　孔洞修補(bǔ)

10、是實(shí)體重構(gòu)中的重大課題，其基礎(chǔ)是深度圖像識(shí)別[6，17，20]和基于點(diǎn)云的表面重構(gòu)[2，3，11，12]等以往的研究成果。 </p><p>　　Curless和Levoy [8]在實(shí)體凹面區(qū)域用內(nèi)插無(wú)采樣表面來(lái)進(jìn)行孔洞修補(bǔ)。在這種情況下，使用快速原型機(jī)器，增加的表面層可以生成用于再生產(chǎn)的水密模型。此算法對(duì)實(shí)體的外觀的只有很少的影響或沒(méi)有影響。我們關(guān)注的是，在任務(wù)中，如果沒(méi)有固定對(duì)象，孔洞重構(gòu)會(huì)導(dǎo)致模型建立中的人

11、為錯(cuò)誤。</p><p>　　Carr等人[7]使用多維徑向基函數(shù)(RBF)對(duì)一套樣本點(diǎn)進(jìn)行擬合，得到間接的表達(dá)結(jié)果。此方法引入一個(gè)有符號(hào)的距離函數(shù)，對(duì)這個(gè)距離函數(shù)進(jìn)行徑向基函數(shù)擬合，從得到的結(jié)果中提取的標(biāo)準(zhǔn)表面。這個(gè)技術(shù)雖然把整個(gè)點(diǎn)云集合當(dāng)作一個(gè)隱函數(shù)處理，不過(guò)很通用且能得到很好的結(jié)果。為了生成有符號(hào)的距離函數(shù)，系統(tǒng)需要知道空間中的哪個(gè)部分對(duì)應(yīng)著表面的外部，哪個(gè)部分對(duì)應(yīng)著表面的內(nèi)部，而這些常常并不是已知條件。

12、</p><p>　　Davis等人[9]使用一種類似于內(nèi)部噴涂技術(shù)[4，18]的容量擴(kuò)散方法來(lái)修補(bǔ)局部掃描中出現(xiàn)的孔洞。該過(guò)程包括把普通界面轉(zhuǎn)換成一個(gè)具有有符號(hào)距離函數(shù)的綜合表示界面。該擴(kuò)散算法交替地進(jìn)行著模糊和混合，直到表面可以運(yùn)用等值面抽取技術(shù)[14]進(jìn)行提取。</p><p>　　Alexa等人 [1]等使用類似于本文算法用點(diǎn)云集合描述形狀，在表面上生成新點(diǎn)集合并以此擬合表面。重構(gòu)

13、的表面可以繼續(xù)對(duì)點(diǎn)云集合采樣。然而，此方法卻不是用于孔洞修補(bǔ)。 </p><p>　　Wang和Oliveira [21]提出一種改進(jìn)深度圖像集合描述情景的重構(gòu)過(guò)程的方法。該方法先進(jìn)行分割，然后是對(duì)缺失幾何和紋理信息的重構(gòu)。在缺失幾何數(shù)據(jù)的重構(gòu)中可以利用包含許多平面和相對(duì)稱表面等真正的(室內(nèi))情景。因此，3D Hough變換用于識(shí)別大平面區(qū)域[10，22，23]，其對(duì)應(yīng)的區(qū)域被三角網(wǎng)格替換，且在點(diǎn)云集合中刪除對(duì)

14、應(yīng)點(diǎn)。對(duì)余下的數(shù)據(jù)集合，通過(guò)使用一種增加表面的重建算法[11]單個(gè)實(shí)體被劃分成空間上互相接近的若干點(diǎn)群。在每個(gè)點(diǎn)群種，運(yùn)用3D Hough變換[21]的變化分析點(diǎn)云以搜索出大致對(duì)稱形狀。這些形狀被識(shí)別后，算法會(huì)自動(dòng)地通過(guò)模型中數(shù)據(jù)的鏡像復(fù)制進(jìn)行重構(gòu)。相對(duì)于原始模型，此算法有重大改善，但仍會(huì)產(chǎn)生一些可見(jiàn)孔洞。這樣孔洞本質(zhì)上起因于模型兩邊的缺乏數(shù)據(jù)和表面重建算法[2，3，11，12]在多采樣密度區(qū)域的局限性。本文所述的算法針對(duì)于以上各種情況

15、下不能解決的孔洞。</p><p><b>　　3孔洞修補(bǔ)算法 </b></p><p>　　為了便于修正網(wǎng)格幾何模型中由于數(shù)據(jù)缺失而引起的拓?fù)浞闯，F(xiàn)象，常常需要引入新點(diǎn)。提出的方法是首先分析并識(shí)別網(wǎng)格模型中孔洞，判斷出當(dāng)前孔洞哪個(gè)必須填裝，哪個(gè)屬于對(duì)象的拓?fù)浣Y(jié)構(gòu)。例如，面具的表面的眼睛區(qū)域允許存在表面間斷的孔洞，詳見(jiàn)如圖1。圖2是本算法的結(jié)構(gòu)圖。</p>

16、<p>　　圖1 .a）表面孔洞，b）重述孔洞</p><p>　　對(duì)孔洞的分析包括研究每個(gè)輪廓曲線的撓率。這種分析的依據(jù)是在表面孔洞是光滑而規(guī)則的，但是自遮擋造成的孔洞通常在輪廓曲線上呈現(xiàn)出撓率的不規(guī)則性，如有些例子在圖3所示。接著，依靠鄰近點(diǎn)，開(kāi)始重復(fù)修補(bǔ)孔洞。通過(guò)鄰近點(diǎn)集的徑向基函數(shù)插值生成一些新點(diǎn)，直到達(dá)到擬合預(yù)設(shè)值。</p><p><b>　　圖2 算

17、法結(jié)構(gòu)圖</b></p><p><b>　　3.1孔洞識(shí)別 </b></p><p>　　孔洞修補(bǔ)過(guò)程的第一步是孔洞識(shí)別，依據(jù)對(duì)象拓?fù)浣Y(jié)構(gòu)此步得知當(dāng)前孔洞的類型。有些孔洞真正地屬于表面，還有些孔洞產(chǎn)生于數(shù)據(jù)的獲取階段，例如由于自遮擋或測(cè)不到等原因造成的孔洞，如圖4所示。</p><p>　　如果對(duì)象是一個(gè)三角網(wǎng)格模型，孔洞包含一條

18、由邊界三角形邊組成的閉合路徑。一個(gè)邊界三角形至少有一條未與其他三角共享的邊(此邊稱為限制邊)。通過(guò)搜索這些邊界邊可以自動(dòng)地找到孔洞。區(qū)分兩種邊界的極限量是確定表面孔洞的內(nèi)部極限和確定一個(gè)補(bǔ)丁或在孔洞內(nèi)部極限內(nèi)部補(bǔ)丁的外部極限孔。在孔洞修補(bǔ)中，代表表面孔洞的內(nèi)部極限的路徑在檢測(cè)時(shí)不予考慮，這就排除識(shí)別后的每個(gè)孔洞都不是表面孔洞的可能性。</p><p>　　圖3 a)自遮擋引起的孔洞， b)部分掃描引起的孔洞。&

19、lt;/p><p>　　開(kāi)始時(shí)，本算法取任意一個(gè)網(wǎng)格中的三角形為起始點(diǎn)，并以此開(kāi)始全局搜索網(wǎng)格，直到一次遞歸后查找到一個(gè)封閉邊界的路徑。先確定哪個(gè)三角形邊是邊界，然后搜索那些共享端點(diǎn)的鄰近三角形的邊界。直到再次查找到初始三角形，算法繼續(xù)執(zhí)行。為了高效率地完成查找，構(gòu)建一個(gè)包含三角形三個(gè)頂點(diǎn)和各點(diǎn)包含的拓?fù)潢P(guān)系的綜合數(shù)據(jù)結(jié)構(gòu)十分必要。另外，每個(gè)已被查找的三角形都得到標(biāo)記。 </p><p>　　

20、圖4顯示的是斯坦福兔寶寶數(shù)據(jù)集合和和孔洞識(shí)別算法的最終結(jié)果。</p><p>　　圖4 a)斯坦福兔寶寶的側(cè)向視圖，</p><p>　　b)和c)網(wǎng)格中孔洞識(shí)別算法的結(jié)果，即五個(gè)被識(shí)別的孔洞。 </p><p><b>　　3.2孔洞分析 </b></p><p>　　孔洞識(shí)別的下一步是孔洞分析，這個(gè)階段設(shè)法確定孔洞

21、是否必須需要修補(bǔ)，設(shè)法確定這個(gè)孔洞是否存在于真實(shí)實(shí)體的表面，或者確定生成于網(wǎng)格重構(gòu)的中間階段的孔洞。</p><p>　　自由形式實(shí)體的孔洞沒(méi)有確定的編碼，以至于很難識(shí)別此孔洞是否屬于實(shí)際表面，這就是孔洞修補(bǔ)中需要用戶交互的原因。然而，嘗試把這個(gè)過(guò)程自動(dòng)化的做法就在于分析每個(gè)孔洞輪廓曲線。人造實(shí)體通常具有光順的輪廓曲線，且輪廓曲線的光順與采樣點(diǎn)的密度有關(guān)。另外，自遮擋生成的孔洞，其表現(xiàn)是輪廓曲線的高可變性，如圖5

22、所示。 </p><p>　　圖5 a)內(nèi)部輪廓， b)外部輪廓</p><p>　　因?yàn)檩喞€也是一種曲線，故它可以根據(jù)幾何特性如曲率和撓率進(jìn)行孔洞研究和分類。由于在表面上的孔洞可能有大范圍曲率變化，本文使用的分類輪廓曲線的量是撓率而不是曲率。建立每個(gè)空間輪廓曲線特性十分重要，如它的平滑性或高可變性。</p><p>　　曲線的撓率特性取決于密切面的性質(zhì)。密切

23、面是在某任意點(diǎn)A處距離曲線最近的平面。該平面包含A點(diǎn)，以及平面在A點(diǎn)的切矢和法矢。</p><p>　　沿著曲線從一點(diǎn)到另一點(diǎn)，密切面的位置與正切以相同的方式變化。這個(gè)簡(jiǎn)單的特征適用于曲率特性的描述。密切面的變化可以用于曲線撓率的計(jì)算的。類似于曲率，密切面的變化可以通過(guò)對(duì)應(yīng)弧線來(lái)測(cè)量。即，設(shè)是密切面在固定點(diǎn)A和鄰居點(diǎn)X之間變化的夾角，設(shè)是兩點(diǎn)之間的弧線AX的長(zhǎng)度，點(diǎn)A的撓率則可用極限定義如下：</p>

24、<p>　　撓率的符號(hào)取決于點(diǎn)沿著曲線移動(dòng)時(shí)密切面的相對(duì)曲線兩邊的指向。然而，由于幾何上的差異，曲線在某點(diǎn)的特性取決于該點(diǎn)處任意小的空間性質(zhì)。因此，該特性被定義為在該點(diǎn)處的各量的引申量。撓率可以如下定義： </p><p>　　評(píng)估三維輪廓曲線的撓率運(yùn)用引申定義是必要的。為了計(jì)算這些引申量，對(duì)邊界點(diǎn)進(jìn)行B樣條參數(shù)擬合，定義如下：</p><p><b>　　此時(shí)，&

25、lt;/b></p><p>　　此時(shí)是B樣條曲線的控制點(diǎn)，而是三次Bernstein多項(xiàng)式，它們定義如下：</p><p>　　輪廓曲線每段都是四個(gè)連續(xù)點(diǎn)擬合的三次Bézier曲線，直到計(jì)算出每個(gè)點(diǎn)撓率的預(yù)估值。 </p><p>　　一旦獲得預(yù)估值，每段的撓率評(píng)估方程在最后一點(diǎn)。由于Bézier曲線可以確保評(píng)估值能從極限點(diǎn)計(jì)算出來(lái)，故中

26、間點(diǎn)不影響撓率預(yù)估的近似誤差 (參見(jiàn)圖6)。</p><p>　　圖6 對(duì)輪廓曲線的Bézier曲線預(yù)估和相關(guān)點(diǎn)</p><p>　　最后，計(jì)算出撓率的變化，以便得到這些測(cè)量值的離散程度。那些撓率預(yù)估值大于預(yù)設(shè)值的孔洞將會(huì)被修補(bǔ)，測(cè)量值可由如下方式得到： </p><p>　　一般來(lái)說(shuō)，低離散值的孔洞表示表面孔洞。圖7代表的是不同離散值的孔洞和相應(yīng)的離散

27、值。在這些情況下，低離散值可認(rèn)為值少于0.1。然而長(zhǎng)輪廓曲線的光順取決于樣品密度。我們假設(shè)，在一個(gè)真正的數(shù)據(jù)范圍中密度是充分的，并且網(wǎng)格沒(méi)有衰減。 </p><p>　　圖7 六種不同情況下的輪廓曲線測(cè)量值</p><p>　　a) 3.10e-1，b) 4.2e-1，c) 2.45e-1，d) 1.0e-4，e) 1.0e-2和f) 3.5e-1</p><p>

28、;<b>　　3.3插值計(jì)算</b></p><p>　　當(dāng)需要修補(bǔ)的孔洞被分類后，運(yùn)用連續(xù)插值的方法計(jì)算出缺失的點(diǎn)。為了實(shí)現(xiàn)這個(gè)過(guò)程，從輪廓曲線鄰近同源方式分布的點(diǎn)云集合中計(jì)算出函數(shù)，此函數(shù)由徑向基函數(shù)構(gòu)造而成。</p><p>　　基于徑向基函數(shù)的解決方案在許多方面都有很大的用途，例如從干擾、離散或殘缺不全的數(shù)據(jù)[25，26，27]中重構(gòu)形狀。關(guān)于RBF的最新研究

29、都集中在基于由現(xiàn)代設(shè)備獲取的點(diǎn)云集合的實(shí)體重構(gòu)[11，17，7，26]。 </p><p>　　徑向基函數(shù)是圍繞某點(diǎn)的中心對(duì)稱函數(shù)，該點(diǎn)可稱為中心。為了計(jì)算基于徑向基函數(shù)的插值，設(shè)為采樣于表面S的點(diǎn)集，設(shè)為表示表面方向的法矢集合。我們的主要目標(biāo)是構(gòu)造函數(shù)，同時(shí)讓在這種情況下空集滿足等式：。 P點(diǎn)集合的典型的插值函數(shù)定義如下：</p><p>　　此時(shí)：，它是用于缺損表面估計(jì)的一個(gè)三階徑向基

30、函數(shù)。是每個(gè)中心的質(zhì)量，是典型的二階或三階多項(xiàng)式，而是中心。</p><p>　　為了修補(bǔ)孔洞，獨(dú)立地計(jì)算出每個(gè)孔洞的插值是必要的。所以，每個(gè)孔洞都有不同的插值函數(shù)，且參與估計(jì)的點(diǎn)數(shù)目遞減。此點(diǎn)集應(yīng)盡可能地大且分布在同一點(diǎn)群，以便得到的函數(shù)能更好地預(yù)估缺失點(diǎn)的拓?fù)浣Y(jié)構(gòu)。 </p><p><b>　　3.4中心選擇 </b></p><p>　

31、　徑向基函數(shù)的插值計(jì)算，如果沒(méi)有必要的交互支持，經(jīng)濟(jì)成本很高。所以，合理地選擇中心或用于插值計(jì)算點(diǎn)集的尺寸能更好地預(yù)估表面。重復(fù)地充分利用鄰近點(diǎn)以完成估計(jì)(參見(jiàn)圖8)。 </p><p>　　圖8 a)疊代1，鄰近點(diǎn)集尺寸： 38</p><p>　　b)疊代2，鄰近點(diǎn)集尺寸： 106 </p><p>　　c)疊代3，鄰近點(diǎn)集尺寸： 172 </p&g

32、t;<p>　　該過(guò)程開(kāi)始于少量的中心，作為輪廓曲線某點(diǎn)鄰近點(diǎn)集。計(jì)算出每個(gè)疊代的插值，直至其低于或等于預(yù)設(shè)值。插值法的質(zhì)量的評(píng)估借助一組參考點(diǎn)完成，該參考點(diǎn)先屬于孔洞的鄰近區(qū)域但是沒(méi)有用于插值計(jì)算。 </p><p>　　圖9顯示，在一個(gè)真實(shí)實(shí)體上，通過(guò)充分選擇鄰近區(qū)域來(lái)計(jì)算插值函數(shù)的結(jié)果內(nèi)插。一旦獲得原始的鄰近區(qū)域，通過(guò)參考點(diǎn)集合來(lái)評(píng)估插值函數(shù)的質(zhì)量。在本文提出的算法中最初鄰近區(qū)域點(diǎn)集應(yīng)成群地生

33、成區(qū)域，以描述孔洞鄰近因拓?fù)浣Y(jié)構(gòu)變化不同而互相區(qū)別的區(qū)域。本文使用K法分類成群[19]，其中參量K是形成孔洞輪廓的點(diǎn)的數(shù)目。</p><p>　　圖9 a)和b)小兔的每個(gè)孔洞的最終鄰近區(qū)域。</p><p>　　一旦得到每群定義的區(qū)域，從區(qū)域中任意的挑出一點(diǎn)(參見(jiàn)圖10)，反過(guò)來(lái)此點(diǎn)將代表整個(gè)區(qū)域。這樣，假設(shè)評(píng)估在孔洞鄰近同類地完成。如果一個(gè)插值函數(shù)以高準(zhǔn)確度達(dá)到預(yù)設(shè)值，此時(shí)意味著它代

34、表孔洞的鄰近拓?fù)浣Y(jié)構(gòu)。</p><p>　　圖10 a)鄰近區(qū)域成群，b)和c)參考點(diǎn)集合的選擇</p><p><b>　　3.5孔洞修補(bǔ)</b></p><p>　　修補(bǔ)孔洞中，重要的是記住被重構(gòu)的部分應(yīng)該保持原始網(wǎng)格的采樣密度，也是測(cè)量每個(gè)孔洞的采樣密度。一般來(lái)說(shuō)，確定修補(bǔ)孔洞的新點(diǎn)有兩個(gè)重要標(biāo)準(zhǔn)。第一，新點(diǎn)的位置應(yīng)該在孔洞內(nèi)部，并且新

35、增的三角形應(yīng)易于原始網(wǎng)格融合。為了避免點(diǎn)云重復(fù)構(gòu)造網(wǎng)格，則本地三角測(cè)量是孔洞修補(bǔ)的高效方法。另外的步驟如新點(diǎn)估計(jì)和表征增加區(qū)域表面特性的輪廓點(diǎn)的法線估計(jì)也易達(dá)到 (參見(jiàn)圖11)。第二，新點(diǎn)的密度必須類似于鄰近區(qū)域點(diǎn)。 </p><p>　　圖11 孔洞三角測(cè)量，</p><p><b>　　(a)最初的網(wǎng)格</b></p><p>　　(b)

36、輪廓離散，生成新點(diǎn)和本地三角測(cè)量， </p><p><b>　　(c)孔洞修補(bǔ)</b></p><p>　　為生成網(wǎng)格的新片，我們使用了RBF插值[7]標(biāo)準(zhǔn)表面算法。假設(shè)密度函數(shù)為S，值為a的標(biāo)準(zhǔn)表面用點(diǎn)集定義為。在表面重構(gòu)中，S代表有符號(hào)的距離函數(shù)。標(biāo)準(zhǔn)界面對(duì)應(yīng)的重構(gòu)表面滿足。</p><p>　　函數(shù)S定期的被周期性采樣，以構(gòu)造一個(gè)用以指

37、定方法描述理想標(biāo)準(zhǔn)界面的復(fù)雜網(wǎng)格模型。新片的密度等于原始網(wǎng)格密度的平均值。使用微小平面端點(diǎn)，以保證鄰近邊緣(小平面法線)的密度梯度與其密度函數(shù)S的梯度相同。等值面抽取算法是一種著名的一般目的算法，可通過(guò)它構(gòu)造三角網(wǎng)格新點(diǎn)和輪廓點(diǎn)，詳見(jiàn)圖12。 </p><p>　　圖12 修補(bǔ)在第3.1部分中被識(shí)別的孔洞</p><p><b>　　4結(jié)果 </b></p&g

38、t;<p>　　為了校準(zhǔn)模型和確認(rèn)在三維點(diǎn)集上的插值的正確性，需對(duì)生成的孔洞做出若干測(cè)試。因?yàn)樵趯?shí)際情況中，插值生成點(diǎn)相對(duì)于實(shí)際表面的精確度無(wú)法測(cè)量，合成孔洞的平均在新點(diǎn)評(píng)估中十分必要。測(cè)試包括用真實(shí)深度圖像生成合成孔洞，并用kd樹(shù)結(jié)構(gòu)離散鄰近點(diǎn)集。接著，用提出的方法修補(bǔ)孔洞，并測(cè)量從真實(shí)表面提取的數(shù)據(jù)和新增點(diǎn)之間的調(diào)整誤差。圖13所述的是四個(gè)不同孔洞中新增點(diǎn)和真實(shí)點(diǎn)之間誤差。圖14所示為帶孔洞的實(shí)體。</p>

39、<p>　　圖13 孔洞修補(bǔ)中的鄰近區(qū)域尺寸變化</p><p>　　圖14 不同尺寸的孔洞</p><p>　　圖15和圖16所示的三維案例中得到結(jié)果描述了本算法的特點(diǎn)。這些圖象說(shuō)明，本算法能正確地識(shí)別了每個(gè)孔洞，且可生成光順的新面片來(lái)修補(bǔ)孔洞。 </p><p>　　圖15 a）原始網(wǎng)格，b）中心點(diǎn)集，c）用RBF插值修補(bǔ)孔洞</p&g

40、t;<p>　　圖16 a）原始網(wǎng)格，b）用RBF插值修補(bǔ)孔洞</p><p><b>　　5結(jié)論 </b></p><p>　　本文介紹了一種在三角網(wǎng)格模型中使用輪廓曲線的撓率變化規(guī)律識(shí)別孔洞并基于徑向基函數(shù)插值修補(bǔ)孔洞的新技術(shù)。在本算法中，輪廓曲線用參與撓率分析計(jì)算的Bézier曲線段進(jìn)行近似。由于徑向基函數(shù)能輻完美地?cái)M合表面，且總能生成

41、一個(gè)閉合的人造的三角網(wǎng)格，故本算法簡(jiǎn)單高效。</p><p>　　當(dāng)網(wǎng)格中存在大孔洞時(shí)，插值函數(shù)不能充分地?cái)M合表面。尺寸超出網(wǎng)格模型總尺寸的3%的孔洞為大孔洞，若沒(méi)有大孔洞產(chǎn)生，這個(gè)掃描過(guò)程就十分理想。本算法只有一個(gè)參數(shù)： 確定孔洞是否需要修補(bǔ)的撓率變化的預(yù)設(shè)值。 而其他參量如鄰近區(qū)域的尺寸都可以自動(dòng)地計(jì)算得到。 </p><p>　　識(shí)別孔洞的撓率變化預(yù)設(shè)值會(huì)受采樣密度和網(wǎng)格生成方法的影

42、響，因此一種從網(wǎng)格中自動(dòng)地確定預(yù)設(shè)值的方法是值得研究的。有時(shí)孔洞在平面上，本算法必然可以完成限制邊緣的撓率分析；但是由于孔洞經(jīng)常由自遮擋等原因造成且所處表面復(fù)雜，這不是常見(jiàn)情況，故我們期待更普遍通用且簡(jiǎn)單高效的算法出現(xiàn)。 </p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] Alexa, M., Behr, J., Cohen-Or, D.,

43、Fleishman, S., Levin, D., and Silva, C., "Point Set Surfaces", IEEE Visualization, pp. 21–28, 2001. </p><p>　　[2] Amenta, N., Bern, M., and Kamvysselis, M., "A new Voronoi-based surface recon

44、struction algorithm", SIGGRAPH’98, pp.415–421, 1998. </p><p>　　[3] Bajaj, C., Bernardini, F., and Xu, G., "Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans", SIGGRAPH’95,

45、pp.109–118, 1995. </p><p>　　[4] Bertalmio,M.,Shapiro, G., Caselles, V., and Ballester, C."Image Inpainting", SIGGRAPH’00, pp.417–424, 2000. </p><p>　　[5] Besl, P., "Advances in

46、Machine Vision", Advances in Machine Vision, Springer Verlag, Chapter 1–Active Optical Range Sensors, pp. 1–63, 1989. </p><p>　　[6] Besl, P. and McKay, N., "A method for registration of 3D shapes&

47、quot;, IEEE Trans. on PAMI, 14 (2). pp. 239–256, 1992. </p><p>　　[7] Carr, J., Beatson, R., Cherrie, J., Mitchell, T. Fright, W., and McCallum, B., "Reconstruction and Representation of 3D Objects with

48、 Radial Basis Functions", SIGGRAPH’ 01, pp. 67–76, 2001. </p><p>　　[8] Curless, B. and Levoy , M.., "A Volumetric Method for Building Complex Models from Range Images", SIGGRAPH’ 96, pp. 303–

49、312, 1996. </p><p>　　[9] Davis, J., Marschner, S., Garr, M., and Levoy, M.., "Filling Holes in Complex Surfaces Using Volumetric Diffusion" Proc. First International Symposium on 3D Data Processin

50、g, Visualization, Transmission, pp. 428–861, 2002. </p><p>　　[10] Efros, A. and Freeman, W., "Image Quilting for Texture Synthesis and Transfer",SIGGRAPH’01, pp. 341–348, 2001. </p><p&g

51、t;　　[11] Gopi, M. and Krishnan, S., "A Fast and Efficient Projection Based Approach for Surface Reconstruction", Intern. Journal of High Performance Computer Graphics, Multimedia and Visualization, 1 (1), pp.

52、1–12, 2000. </p><p>　　[12] Hoppe, H., DeRose, T., Duchamp, McDonald, T. J.A., and Stuetzle, W., "Surface</p><p>　　reconstruction from unorganized points", SIGGRAPH’92, pp. 71–78, 1992.

53、 </p><p>　　[13] Lancaster, P. and Salkauskas, K., Curve and Surface Fitting: an Introduction. Academic</p><p>　　Press. 1986. </p><p>　　[14] Lorensen, W. and Cline, H., "Marchi

54、ng cubes: A high resolution 3D surface construction</p><p>　　algorithm", Proc. SIGGRAPH’87, pp. 163–169, 1987. </p><p>　　[15] McAllister, D., Nyland, L., Popescu, V., Lastra A. and McCue,

55、C., "Real Time Rendering of</p><p>　　Real World Environments", Proc. Rendering Techniques’99, pp. 145–160, 1999.</p><p>　　[16] Nyland, L., et al., "The Impact of Dense Range Data

56、on Computer Graphics", Proceedings of</p><p>　　Multi-View Modeling and Analysis Workshop, pp. 3–10, 1999. </p><p>　　[17] Nyland, L., Lastra, A., Mc Allister, D., Popescu, V., McCue, C., and

57、 Fuchs, H., "Capturing,</p><p>　　Processing and Rendering Real-World Scenes", In Videometrics and Optical Methods for</p><p>　　3DShape Measurement, Electronic Imaging,, PhotonicsWest

58、, SPIE Vol. 4309, pp. 107–116,</p><p><b>　　2001. </b></p><p>　　[18] Oliveira, M., Bowen, B., McKenna, R., and Chang, Y., "Fast Digital Image Inpainting",</p><p&g

59、t;　　International Conference on Visualization, Imaging and Image Processing (VIIP 2001), Marbella, Spain, pp.261–2665, 2001. </p><p>　　[19] Hartigan, J. and Wong, M. A., "A K–Means Clustering Algorithm&

60、quot;, Journal of Applied Statistics, 28 (1), pp. 100–108, 1979. </p><p>　　[20] Pulli, K., "Multiview Registration for Large Data Sets", 3DIM’99, pp. 160–168, 1999. </p><p>　　[21] Wang

61、, J. and Oliveira, M., "Improved Scene Reconstruction from Range Images", Proc. EUROGRAPHICS’ 2002, pp. 521–530, 2002. </p><p>　　[22] Wei, L.Y. and Levoy, M., "Texture Synthesis over Arbitra

62、ry Manifold Surfaces", SIGGRAPH’01, pp. 355–360, 2001. </p><p>　　[23] Ying, L., Hertzmann, A., Biermann, H., and Zorin, D., "Texture and Shape Synthesis on Surfaces", Eurographics´2001,

63、 Rendering Workshop, pp. 301–312, 2001. </p><p>　　[24] Yu, Y., Ferencz, A., and Malik, J., "Extracting Objects from Range and Radiance Images", IEEE Transactions on Visualization and Computer Gr

64、aphics, 7 (4), pp. 351–364, 2001. </p><p>　　[25] Carr, J. C., Beatson, R. K., McCallum, B. C., Fright, W. R., McLennan, T. J., and Mitchell, T. J., "Smooth surface reconstruction from noisy range data&q

65、uot;, Proceedings of the 1st international conference on computer graphics and interactive techniques in Australasia and South East Asia, Melbourne, Australia, February 11–14, ACM Press, pp. 119, 2003. </p><p

66、>　　[26] Buhmann, M., "Radial Basis Function: Theory and Implementations", Cambridge Monographs on Applied and Computational Mathematics, 2003. </p><p>　　[27] Carr, J.C., Beatson, R.K., Cherrie,

67、J. B., Mitchell, T.J., Fright, W. R., McLennan, T.J., and Evans, T.R., "Reconstruction and representation of objects with radial basis function", Proceedings of the 28th annual conference on Computer graphics a