點(diǎn)云重建三角網(wǎng)格

點(diǎn)云重建三角網(wǎng)格三角網(wǎng)格重建的研究現(xiàn)狀曲面重建技術(shù)在逆向工程[57]、數(shù)據(jù)可視化[58]、機(jī)器視覺(jué)[59]、虛擬現(xiàn)實(shí)[60]、醫(yī)療技術(shù)[61]等領(lǐng)域中得到了廣泛的應(yīng)用。網(wǎng)格重建作為曲面重建的重要前處理一直是研究的熱點(diǎn)。近十幾年來(lái)，國(guó)內(nèi)外學(xué)者提出了許多網(wǎng)格重建的算法。根據(jù)重建過(guò)程中采用的具體方法可以將網(wǎng)格重建算法分為基于Delaunay重建法、區(qū)域擴(kuò)張重建法、基于隱式曲面重建法和基于統(tǒng)計(jì)學(xué)重建法。基于Delaunay重建方法，具有很強(qiáng)的數(shù)學(xué)基礎(chǔ)，一般能精確地重建物體表面，但計(jì)算量比較大，對(duì)帶有噪聲的物體和尖銳特征的物體，采用該方法重建并不能取得比較理想的結(jié)果。Boissonnat[62]通過(guò)采用三維Delaunay三角剖分得到數(shù)據(jù)點(diǎn)的凸包，然后逐步剝離冗余四面體，使所有數(shù)據(jù)點(diǎn)可見(jiàn)，最終重建出物體的網(wǎng)格模型。在采樣點(diǎn)足夠稠密的情況下，該方法能重建出與物體拓?fù)湟恢碌木W(wǎng)格模型，但當(dāng)采樣點(diǎn)不均勻以及存在噪聲數(shù)據(jù)時(shí)，不能構(gòu)造出與物體拓?fù)涞葍r(jià)的網(wǎng)格模型，同時(shí)計(jì)算復(fù)雜，內(nèi)存消耗比較多。Edelsbrunner[63]提出一種α-shape方法，該方法通過(guò)刪除四面體凸包中包圍球或者外半徑大于α的四面體、三角面片和邊重建測(cè)量數(shù)據(jù)的網(wǎng)格模型，但α-shape不是流形結(jié)構(gòu)，必須經(jīng)過(guò)后續(xù)處理才能得到正確的二維流形網(wǎng)格[64]，同時(shí)該方法對(duì)采樣不均勻的點(diǎn)云難以選擇合適的α值重建出正確的網(wǎng)格模型。Amenta[65][66][67]對(duì)掃描數(shù)據(jù)進(jìn)行Voronoi圖分解，然后通過(guò)Delaunay三角化方法重建網(wǎng)格模型。該方法能精確地通過(guò)掃描數(shù)據(jù)點(diǎn)，但對(duì)噪聲模型和具有尖銳特征的模型不能取得理想的效果。Floater[68]將數(shù)據(jù)點(diǎn)投影到平面，在平面采用Denaulay三角化方法，生成平面網(wǎng)格，并將拓?fù)潢P(guān)系映射回空間數(shù)據(jù)點(diǎn)，從而達(dá)到網(wǎng)格重建的目的，該方法簡(jiǎn)單高效，但只適用于單值曲面。屬于該類(lèi)的方法還有Crust方法[69]和Cocone方法[70]?；陔[式表面重建方法，可以有效處理噪聲數(shù)據(jù)，但不能有效地處理具有尖銳特征的模型，一般只用于計(jì)算機(jī)視覺(jué)和虛擬現(xiàn)實(shí)中。Hoppe[71]首先給出了一個(gè)刻畫(huà)點(diǎn)集密度的方法，引入了ρ密度樣本的定義，通過(guò)計(jì)算點(diǎn)的法矢，得到數(shù)據(jù)點(diǎn)局部處的切平面，用切平面線性逼近待重建網(wǎng)格的局部形狀，從而建立距離場(chǎng)函數(shù)，通過(guò)提取等值曲面得到三角網(wǎng)格。該方法通常涉及復(fù)雜的法矢一致性調(diào)整，不能較好地重建細(xì)節(jié)特征。周儒榮[72]對(duì)Hoppe的方法進(jìn)行了改進(jìn)，提出以切平面中心代替數(shù)據(jù)點(diǎn)，改善網(wǎng)格質(zhì)量，較好地處理了法矢?jìng)鞑ブ械墓聧u問(wèn)題。Curless[73]提出了以掃描圖像作為加權(quán)距離場(chǎng)函數(shù)，通過(guò)合并多幅圖像的方法進(jìn)行網(wǎng)格重建，能處理上百萬(wàn)的數(shù)據(jù)。Car[74]等提出通過(guò)徑向基函數(shù)進(jìn)行網(wǎng)格重建，他們以徑向基作為基函數(shù)，建立插值函數(shù)，通過(guò)求解線性方程組，達(dá)到網(wǎng)格重建的目的，但由于約束點(diǎn)比較多，方程為全局方程，需要消耗較多的內(nèi)存和計(jì)算時(shí)間。Ohtake[76]、朱心雄[77]提出一種MPU(MultilevelPartitionofUnity)方法，該方法克服了一般隱式表面重建法不能還原尖銳特征的缺點(diǎn)。Kazhdan[78]通過(guò)泊松等式△f=div(n)建立隱式曲面，然后提取等值面，從而達(dá)到網(wǎng)格重建的目的。屬于這類(lèi)的方法還有[71][73][74][75][77][78]。水平集的方法，最早是由Osher和Sethian[79][80]于1988年提出的，它的基本思想是將曲線或者曲面看成是某一更高維函數(shù)的零水平集，利用函數(shù)的演化與Hamilton-Jacobi方程的相似性，將曲線或者曲面的演化過(guò)程轉(zhuǎn)化為函數(shù)的演化過(guò)程.Whitaker[81]、Zhao[82]、Sethian[83]、Osher[84]、Zhao[85]等人也提出將水平集方法應(yīng)用到曲面重構(gòu)中，并取得了較好的結(jié)果.變形表面方法與之類(lèi)似，從初始表面開(kāi)始，在能量函數(shù)的驅(qū)動(dòng)下可以逼近真實(shí)表面。區(qū)域擴(kuò)張法，一般都是從一個(gè)初始種子出發(fā)，不斷向周邊擴(kuò)張直到所有數(shù)據(jù)點(diǎn)都被處理，其中初始種子可以是一個(gè)三角面片或者一條邊。Bernardinit在α-shape理論基礎(chǔ)上提出了BPA算法，通過(guò)使用一個(gè)給定半徑或者使用不同半徑的球繞著活動(dòng)邊轉(zhuǎn)動(dòng)，直到找到另外一點(diǎn)，生成新的三角面片。該算法需要點(diǎn)的法矢信息，而且不容易取到合適的半徑。Crossno[86]提出螺旋邊準(zhǔn)則，根據(jù)邊界邊最小內(nèi)切圓準(zhǔn)則尋找一個(gè)新的頂點(diǎn)并構(gòu)建新三角形，逐步覆蓋整個(gè)數(shù)據(jù)集，該方法能高效地處理均勻數(shù)據(jù)點(diǎn)。Huang[64]將K個(gè)臨近點(diǎn)投影到活動(dòng)邊所在三角面片的平面上，剔除不可見(jiàn)的點(diǎn)，然后利用最小長(zhǎng)度準(zhǔn)則在剩余點(diǎn)中選擇一點(diǎn)構(gòu)造新的三角面片。Lin[87]提出IPD算法，該算法定義了采樣點(diǎn)均勻度，利用該均勻度建立活動(dòng)邊的影響區(qū)域，從而獲得候選點(diǎn)集合，然后根據(jù)加權(quán)邊長(zhǎng)和最小準(zhǔn)則選擇一點(diǎn)構(gòu)造新的三角面片。屬于區(qū)域擴(kuò)張法的還有[86][87]，該類(lèi)方法思想簡(jiǎn)單、實(shí)現(xiàn)容易、效率高，可以處理復(fù)雜拓?fù)淠Ｐ偷闹亟?，但現(xiàn)有的該類(lèi)方法尖銳特征重建效果不是很理想?；诮y(tǒng)計(jì)學(xué)方法，將統(tǒng)計(jì)學(xué)習(xí)和機(jī)器學(xué)習(xí)的方法運(yùn)用于網(wǎng)格重建。Kohonen[88]提出基于自我組織學(xué)習(xí)的網(wǎng)格重建算法，最先將統(tǒng)計(jì)學(xué)方法引入網(wǎng)格重建中。將反向傳播用于網(wǎng)格重建，建立四層BP神經(jīng)網(wǎng)格，以網(wǎng)格曲面或者B樣條曲面作為樣例訓(xùn)練該神經(jīng)網(wǎng)絡(luò)，不斷調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)值，將數(shù)據(jù)點(diǎn)與重建曲面轉(zhuǎn)化為非線性問(wèn)題，通過(guò)梯度方向搜索使數(shù)據(jù)點(diǎn)與重建曲面的方差最小，重建出來(lái)的曲面一般精度比較高，但它存在收斂性問(wèn)題。Ivrissimtzis[89]將神經(jīng)網(wǎng)絡(luò)引入網(wǎng)格模型重建，該方法將三角網(wǎng)格作為神經(jīng)網(wǎng)絡(luò)，將數(shù)據(jù)點(diǎn)作為信號(hào)，通過(guò)信號(hào)刺激神經(jīng)網(wǎng)絡(luò)，逐步更新網(wǎng)格。Diebel[90]將貝葉斯框架引入了網(wǎng)格重建。另外屬于這個(gè)范疇的方法還有[91][92][93]。多種子點(diǎn)和平坦部分優(yōu)先生長(zhǎng)方法的點(diǎn)云到網(wǎng)格重建(a)(b)(c)(d)(a)(b)(c)(d)(e)Fig.1.Theflat(horizontalorvertical)portionsoftheobjecthaveahigherprioritytobetriangulatedthantheplaceswithsharpcurvaturechange.(a)anflatportions;(b)rightlygrowing;(c)falselygrowing;(c)falselygrowing;(d)multi-seedsmesh;(e)thefinishedmesh.當(dāng)前前沿邊的鄰近點(diǎn)，不一定是自由點(diǎn)，也可能是已接受的、在前沿邊上的點(diǎn)。我們稱已接受的、在前沿邊上的點(diǎn)為前沿點(diǎn)。在構(gòu)造新三角形時(shí)，根據(jù)鄰近點(diǎn)的屬性，有四種操作：(1)加入：如果鄰近點(diǎn)是自由的候選點(diǎn)，加入新三角形，推進(jìn)前沿邊；Fig.2Fig.2.MeshGrowing.1istheseedtriangle,and2thefinishedtriangle,3afrontedge,4thecurrentfrontedge,5thefreepoints,6theboundingball,7theclosepoint,8thereferencepoint.(3)連接：如果鄰近點(diǎn)是已接受點(diǎn)，但是鄰近點(diǎn)與前沿邊的某一個(gè)端點(diǎn)的連接邊已存在，而與前沿邊的另一個(gè)端點(diǎn)的連接邊不存在，把鄰近點(diǎn)和前沿邊構(gòu)造成新三角形，從前沿邊堆棧中刪除鄰近點(diǎn)與前沿邊間已存在的連接邊，把新三角形的另一邊加入前沿邊堆棧；(a)(b)(a)(b)(c)Fig.3.TopologicalOperations.(a)ameshwiththecurrentfrontedgee1;(b)themeshgrowingprocess;(c)thetemporalresultmeshafter4topologicaloperations.Fig.4.Fig.4.Triangulation.三角形都是有方向的，按逆時(shí)針?lè)较蚪?gòu)，這樣表面的方向都指向外面。前沿邊也始終是封閉的有向曲線，數(shù)目始終在變化。加入操作會(huì)新填二個(gè)前沿邊，刪除一個(gè)前沿邊；填充操作不會(huì)新填前沿邊，但會(huì)刪除三個(gè)前沿邊；連接操作會(huì)刪除一個(gè)前沿邊，新填一個(gè)前沿邊；縫接操作會(huì)刪除二個(gè)前沿邊，新填二個(gè)前沿邊。如果在填充、連接或者縫接時(shí)發(fā)現(xiàn)新三角形的某兩條邊是前沿邊，并且方向不一致，那么網(wǎng)格在此處發(fā)生了糾纏。(a)(b)(c)(d)Fig.(a)(b)(c)(d)Fig.5.Reconstructtheheadmodel:(a)Points;(b)Mergelocaltriangularmesh;(c)Meshoptimize;(d)Geometricmodelafternormalconsistent.(1)算法的第一步，尋找平坦部位的種子點(diǎn)，如果需要計(jì)算每個(gè)三角形的法向才能知道哪些三角形是平坦的，計(jì)算成本高，需要更有效的方法；(2)從當(dāng)前前沿邊的中心構(gòu)造范圍球時(shí)，球的半徑如何選擇才合適。球的半徑太大，會(huì)多產(chǎn)生異常點(diǎn)，甚至得到錯(cuò)誤的拓樸連接；但是多數(shù)范圍球內(nèi)至少應(yīng)該有超過(guò)一個(gè)的候選點(diǎn)。但是無(wú)論如果，范圍球的半徑與點(diǎn)間的平均距離有關(guān)系。如果需要范圍球的半徑與局部自適應(yīng)，那么可以計(jì)算出局部點(diǎn)云的平均距離。平均距離由點(diǎn)云的包圍盒和點(diǎn)的數(shù)目計(jì)算而來(lái)；(3)新三角形應(yīng)該與已成的網(wǎng)格不相交，相交性檢測(cè)是一個(gè)費(fèi)時(shí)的計(jì)算?？梢栽谛氯切紊先∫粋€(gè)比范圍球更大的區(qū)域，檢測(cè)是否有已成的網(wǎng)格，新三角形的三個(gè)頂點(diǎn)是否落在每個(gè)網(wǎng)格平面的同一邊；(4)從候選點(diǎn)集中選取鄰近點(diǎn)的代價(jià)函數(shù)，其實(shí)是在鄰近點(diǎn)與當(dāng)前三角形的夾角、法向變化和鄰近點(diǎn)與當(dāng)前邊距離這三者考慮何者優(yōu)先。如果重建對(duì)象平坦光滑，那么法向變化應(yīng)該小，距離可以取得大一些；相反，法向變化可以取得大，距離應(yīng)該取得小。各個(gè)局部的情況與此相同。而且在種子生長(zhǎng)階段和最后表面縫合階段，代價(jià)函數(shù)也應(yīng)不同；因此，代價(jià)函數(shù)中三個(gè)因素間的系數(shù)應(yīng)該是與局部情況相適應(yīng)的；(5)既然是平坦部分優(yōu)先生長(zhǎng)，那么當(dāng)前前沿邊應(yīng)該是前沿邊中最平坦的部分。因此前沿邊堆棧也需要按平坦程度排序。點(diǎn)云到網(wǎng)格的重建

1.1哈希表的構(gòu)造方法一般的線性表、樹(shù)中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類(lèi)查找方法建立在“比較”的基礎(chǔ)上，查找的效率與比較次數(shù)密切相關(guān)。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而查找時(shí)，只需根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f找到給定值K的像f(K)。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲(chǔ)位置上，由此不需要進(jìn)行比較便可直接取得所查記錄。在此，稱這個(gè)對(duì)應(yīng)關(guān)系f為哈希函數(shù)，按這個(gè)思想建立的表為哈希表（又稱為雜湊法或散列表）。哈希表不可避免沖突(collision)現(xiàn)象：對(duì)不同的關(guān)鍵字可能得到同一哈希地址即key1≠key2，而f(key1)=f(key2)。具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來(lái)說(shuō)稱為同義詞(synonym)。因此，在建造哈希表時(shí)不