基于八叉樹(shù)和柵格法的點(diǎn)云簡(jiǎn)化算法

喬海峰　牛瑞濤

摘 要：隨著大規(guī)模點(diǎn)云數(shù)據(jù)的大量涌現(xiàn)，點(diǎn)云簡(jiǎn)化問(wèn)題成為數(shù)字幾何處理領(lǐng)域的研究熱點(diǎn).為了提高實(shí)體反求的效率，提出一種點(diǎn)云簡(jiǎn)化方法。該方法通過(guò)劃分柵格來(lái)建立采樣點(diǎn)與空間柵格的拓?fù)潢P(guān)系，進(jìn)而擬合出球面方程來(lái)估算該區(qū)域的曲率，并通過(guò)八叉樹(shù)算法來(lái)保留曲率大的區(qū)域的點(diǎn)云，結(jié)果表明，該算法簡(jiǎn)單高效，所提出的點(diǎn)云精簡(jiǎn)算法能夠?qū)Υ罅棵芗瘮?shù)據(jù)進(jìn)行直接而有效的精簡(jiǎn)，并且對(duì)曲率變化大且含有較多細(xì)節(jié)特征的區(qū)域保留更多的細(xì)節(jié)信息

關(guān)鍵詞：點(diǎn)云；簡(jiǎn)化；八叉樹(shù)；柵格法

隨著各種產(chǎn)品的極大豐富，從飛機(jī)到汽車到社會(huì)的各個(gè)方面，都要用到反求工程，而隨著反求工程技術(shù)的發(fā)展，物體表面數(shù)據(jù)的采集方法越來(lái)越多樣化，三維測(cè)量設(shè)備得到了長(zhǎng)足的進(jìn)步，設(shè)備的精度越來(lái)越高，得到的點(diǎn)云數(shù)據(jù)也越來(lái)越多，如果直接用海量的點(diǎn)云進(jìn)行曲面重構(gòu)，勢(shì)必大大影響處理的速度和效率，所以，在不影響精度的條件下，對(duì)海量的點(diǎn)云進(jìn)行簡(jiǎn)化就顯的非常必要。近年來(lái)，人們對(duì)三維點(diǎn)云數(shù)據(jù)的簡(jiǎn)化進(jìn)行了大量的研究，Hamann提出一種根據(jù)三角面處的曲率值決定該三角面的取舍，然后重新擬合出新的三維模型的方法，然而這方法只適用于STL文件的自動(dòng)生成，不適用于對(duì)無(wú)序點(diǎn)云的精簡(jiǎn)。文獻(xiàn)提出了平均距離精簡(jiǎn)法，但是這種方法容易丟失細(xì)節(jié)信息，且一般用于掃描線形式的點(diǎn)云數(shù)據(jù)。針對(duì)以上方法的不足，文章提出一種新的點(diǎn)云簡(jiǎn)化算法，該算法簡(jiǎn)單高效，適用于逆向工程中測(cè)量所得的散亂無(wú)序的點(diǎn)云數(shù)據(jù)，能夠?qū)Υ罅棵芗瘮?shù)據(jù)進(jìn)行直接而有效的精簡(jiǎn)，并且對(duì)曲率變化大且含有較多細(xì)節(jié)特征的區(qū)域保留更多的細(xì)節(jié)信息。

1 點(diǎn)云簡(jiǎn)化算法

文章提出的算法，是先通過(guò)柵格法，將海量的離散點(diǎn)云建立拓?fù)潢P(guān)系，并通過(guò)對(duì)各個(gè)柵格內(nèi)的點(diǎn)云擬合出一個(gè)球面方程，來(lái)得到該柵格內(nèi)點(diǎn)云的曲率；通過(guò)設(shè)置給定曲率值，來(lái)決定是否對(duì)柵格進(jìn)行八叉樹(shù)剖分，并在子?xùn)鸥駜?nèi)進(jìn)行擬合，進(jìn)而達(dá)到高效的對(duì)曲率變化大且含有較多細(xì)節(jié)特征的區(qū)域保留更多的細(xì)節(jié)信息的目的。

由于離散點(diǎn)的分布缺少規(guī)律性，因此，在對(duì)點(diǎn)云進(jìn)行簡(jiǎn)化等處理前應(yīng)先建立點(diǎn)云的拓?fù)潢P(guān)系，文章通過(guò)對(duì)離散點(diǎn)云應(yīng)用三維柵格法，來(lái)進(jìn)行離散點(diǎn)云拓?fù)潢P(guān)系的建立。

文章主要是現(xiàn)給定合適的柵格寬度，和給定曲率對(duì)每個(gè)柵格內(nèi)所有點(diǎn)擬合出球面方程，然后，根據(jù)擬合出的球面方程估算球面方程的曲率，并用估算出的球面方程的曲率和給定曲率比較，如果，則將與該柵格相鄰的26個(gè)近鄰進(jìn)行合并，重新估算球面方程和曲率；如果，則對(duì)該柵格進(jìn)行八叉樹(shù)分解，并對(duì)八叉樹(shù)中各個(gè)子?xùn)鸥襁M(jìn)行球面方程的擬合；直到八叉樹(shù)各個(gè)子?xùn)鸥駜?nèi)球面方程的曲率，通過(guò)子?xùn)鸥駜?nèi)點(diǎn)云的質(zhì)心與球心的連線來(lái)估算法矢，并對(duì)子?xùn)鸥駜?nèi)的點(diǎn)云進(jìn)行采樣，從而實(shí)現(xiàn)點(diǎn)云的簡(jiǎn)化。

八叉樹(shù)剖分算法流程

（1）將柵格進(jìn)行八叉樹(shù)剖分形成八個(gè)子?xùn)鸥瘢?/p>

（2）若子?xùn)鸥駜?nèi)點(diǎn)數(shù)大于等于4，則對(duì)該柵格內(nèi)所有點(diǎn)分別擬合出球面方程并擬合出的球面方程的球心坐標(biāo)及曲率，并繼續(xù)（3），否則刪除子?xùn)鸥駜?nèi)的點(diǎn)轉(zhuǎn)（4）；

（3）若曲率，估算出該柵格內(nèi)所有點(diǎn)的質(zhì)心坐標(biāo)，計(jì)算出過(guò)球心坐標(biāo)與質(zhì)心坐標(biāo)的方向矢量，并保留離質(zhì)心坐標(biāo)最近的點(diǎn)的數(shù)據(jù)，將方向矢量賦予給該點(diǎn)并轉(zhuǎn)（4），否則轉(zhuǎn)（1）；

（4）若還有子?xùn)鸥駴](méi)有被采樣，則繼續(xù)（2），否則，轉(zhuǎn)（5）；

（5）若有上一級(jí)子?xùn)鸥瘢瑒t返回，并轉(zhuǎn)（4），否則，轉(zhuǎn)（6）；

（6）算法結(jié)束。

2 算法實(shí)例

為了驗(yàn)證文章算法的正確性和有效性，在測(cè)試硬件環(huán)境為Intel Core 2 Duo 2.0 GHz CPU，2GB內(nèi)存，用C++語(yǔ)言在VC++6編譯器上結(jié)合OpenGL庫(kù)分別對(duì)某零件的點(diǎn)云模型進(jìn)行了簡(jiǎn)化處理。圖1為零件通過(guò)文章點(diǎn)云簡(jiǎn)化算法簡(jiǎn)化處理的效果。圖1（a）為零件1的原始點(diǎn)云圖，共有79629個(gè)點(diǎn)；圖1（b）為柵格寬度和給定曲率時(shí)原始點(diǎn)云簡(jiǎn)化的效果圖，共有49740個(gè)點(diǎn)，簡(jiǎn)化率為62.5%；圖1（c）為柵格寬度和給定曲率時(shí)原始點(diǎn)云簡(jiǎn)化的效果圖，共有28852個(gè)點(diǎn)，簡(jiǎn)化率為36.2%。從圖中可以看出，簡(jiǎn)化點(diǎn)云不存在簡(jiǎn)化后點(diǎn)云的局部過(guò)密或局部過(guò)稀的情況，而且依然保留了原始點(diǎn)云的基本特征，沒(méi)有出現(xiàn)形狀的缺失，對(duì)于曲率變化較大區(qū)域特征區(qū)域表達(dá)依然清楚。

3 結(jié)語(yǔ)

文章提出了一種點(diǎn)云簡(jiǎn)化算法，該方法首先采用柵格法建立點(diǎn)云的空間拓?fù)潢P(guān)系，然后在此基礎(chǔ)上擬合出球面方程，從而計(jì)算曲率值，并根據(jù)計(jì)算出的曲率值和給定的曲率值進(jìn)行對(duì)比，決定是延伸到該柵格的26近鄰還是進(jìn)行八叉樹(shù)剖分，并由此來(lái)對(duì)曲率較大出的區(qū)域保留較多的點(diǎn)，從而對(duì)點(diǎn)云進(jìn)行簡(jiǎn)化。結(jié)果表明，該算法簡(jiǎn)單高效，所提出的點(diǎn)云精簡(jiǎn)算法能夠?qū)Υ罅棵芗瘮?shù)據(jù)進(jìn)行直接而有效的精簡(jiǎn)，并且對(duì)曲率變化大且含有較多細(xì)節(jié)特征的區(qū)域保留更多的細(xì)節(jié)信息。

參考文獻(xiàn)

[1] Hamann B. A data reducation scheme for triangulated surfaces.Computer Aided Geometric Desig[J].1994，11（02）：197-214.

[2] 劉德平，陳建軍.逆向工程中數(shù)據(jù)精簡(jiǎn)技術(shù)的研究[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，35（02）：334-339.