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

喬海峰　牛瑞濤

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

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

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

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

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

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

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

八叉樹剖分算法流程

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

（2）若子?xùn)鸥駜?nèi)點(diǎn)數(shù)大于等于4，則對該柵格內(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ì)算出過球心坐標(biāo)與質(zhì)心坐標(biāo)的方向矢量，并保留離質(zhì)心坐標(biāo)最近的點(diǎn)的數(shù)據(jù)，將方向矢量賦予給該點(diǎn)并轉(zhuǎn)（4），否則轉(zhuǎn)（1）；

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

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

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

2 算法實(shí)例

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

3 結(jié)語

文章提出了一種點(diǎn)云簡化算法，該方法首先采用柵格法建立點(diǎn)云的空間拓?fù)潢P(guān)系，然后在此基礎(chǔ)上擬合出球面方程，從而計(jì)算曲率值，并根據(jù)計(jì)算出的曲率值和給定的曲率值進(jìn)行對比，決定是延伸到該柵格的26近鄰還是進(jìn)行八叉樹剖分，并由此來對曲率較大出的區(qū)域保留較多的點(diǎn)，從而對點(diǎn)云進(jìn)行簡化。結(jié)果表明，該算法簡單高效，所提出的點(diǎn)云精簡算法能夠?qū)Υ罅棵芗瘮?shù)據(jù)進(jìn)行直接而有效的精簡，并且對曲率變化大且含有較多細(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ù)精簡技術(shù)的研究[J].西安電子科技大學(xué)學(xué)報：自然科學(xué)版，2008，35（02）：334-339.