基于三維點(diǎn)云的重建算法

羅衛(wèi)，楊志成

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

基于三維點(diǎn)云的重建算法

羅衛(wèi)，楊志成

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

近年來，通過三維掃描儀獲得點(diǎn)云數(shù)據(jù)越來越流行，基于點(diǎn)云的重建技術(shù)成為計(jì)算機(jī)圖形學(xué)等領(lǐng)域的研究熱點(diǎn)。首先通過KNN算法計(jì)算出每個(gè)點(diǎn)需要擴(kuò)展為圓盤的半徑大小，然后將點(diǎn)云數(shù)據(jù)中將每個(gè)點(diǎn)擴(kuò)展為具有一定半徑大小的圓盤來彌補(bǔ)點(diǎn)與點(diǎn)之間的空洞；由于圓盤半徑過大會(huì)導(dǎo)致圓盤之間相互交叉，在圓盤上施加高斯濾波核函數(shù)來消除面元之間相互交叉帶來的失真現(xiàn)象，同時(shí)在指定參數(shù)閾值范圍內(nèi)自適應(yīng)地將核函數(shù)的能量限制在面元范圍內(nèi)，得到良好的繪制效果。

三維點(diǎn)云；KNN；點(diǎn)繪制

0 引言

點(diǎn)云是指通過三維掃描儀掃描物體得到的，或者通過對(duì)物體不同角度的照片使用算法生成的，用三維點(diǎn)集表示物體表面輪廓的模型?；谌S點(diǎn)云數(shù)據(jù)的重建技術(shù)成為逆向工程、醫(yī)療衛(wèi)生、文物恢復(fù)以及計(jì)算機(jī)圖形學(xué)等領(lǐng)域的研究熱點(diǎn)。

由于三維點(diǎn)云數(shù)據(jù)量比較大，少則幾萬，多則幾百上千萬，如果利用重建算法將點(diǎn)云數(shù)據(jù)重建成網(wǎng)格模型之后再做顯示繪制，那樣將非常低效。為了實(shí)現(xiàn)點(diǎn)云的快速顯示繪制，本文實(shí)現(xiàn)了一種基于面元的點(diǎn)繪制算法，不通過三維重建直接顯示點(diǎn)云表示的原始模型。

1 基于點(diǎn)的繪制算法

現(xiàn)在的三維重建方法主要有基于三角網(wǎng)格和上世紀(jì)90年代發(fā)展起來的基于點(diǎn)繪制的方法。點(diǎn)繪制的方法通過物體表面的采樣點(diǎn)來重建物體表面，每個(gè)點(diǎn)包含點(diǎn)的三維坐標(biāo)、法向量和顏色等，而且不需要維護(hù)點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系，因此可以很方便地實(shí)現(xiàn)多分辨率的點(diǎn)云繪制。

基于點(diǎn)的繪制算法是在點(diǎn)云的基礎(chǔ)上，通過將每個(gè)點(diǎn)擴(kuò)展為具有一定大小的圓盤來彌補(bǔ)點(diǎn)與點(diǎn)之間的空隙，由于過大的半徑會(huì)導(dǎo)致圓盤之間相互交叉比較嚴(yán)重，所以在半徑的選擇上采用了KNN算法來求得點(diǎn)到附近點(diǎn)之間平均距離，這樣就可以根據(jù)點(diǎn)的不同分布來決定圓盤半徑大小，從而減少圓盤過多的交叉；此文還在圓盤上采用了高斯濾波核函數(shù)來消除鋸齒，做了平滑操作，從而減少失真。

2 算法描述

本文的算法通過輸入的三維點(diǎn)云數(shù)據(jù)實(shí)現(xiàn)基于點(diǎn)的繪制算法，通過將點(diǎn)云數(shù)據(jù)擴(kuò)展為具有一定半徑大小的圓盤來填補(bǔ)點(diǎn)與點(diǎn)之間的空隙，相應(yīng)原盤的生成依靠三維點(diǎn)云所攜帶的三維數(shù)據(jù)（包含三維坐標(biāo)、法向量和顏色信息）。

2.1 KNN

為了實(shí)現(xiàn)點(diǎn)擴(kuò)面的半徑自適應(yīng)性，本文中采用KNN算法來獲取點(diǎn)周圍的最近鄰的K個(gè)點(diǎn)，通過計(jì)算得出這些點(diǎn)與中心點(diǎn)的歐氏距離的平均值來得到半徑的大小。KNN算法即主要實(shí)現(xiàn)查找目標(biāo)點(diǎn)K個(gè)距離最近的鄰接點(diǎn)。最直觀的for循環(huán)方法可以準(zhǔn)確的實(shí)現(xiàn)KNN算法，但是在計(jì)算機(jī)圖形學(xué)等領(lǐng)域，面臨的樣本點(diǎn)一般都很大，所以需要高效快速的最近鄰搜索算法才能滿足需求。本文采用KD樹的空間劃分來建立搜索索引，相比于傳統(tǒng)的算法搜索效率高，占用空間內(nèi)存小。KNN算法具體實(shí)現(xiàn)如下：

構(gòu)造KD-Tree：

struct SInputData

{

const double*pData;//存放輸入的點(diǎn)集

unsigned int NumInput;//輸入點(diǎn)的個(gè)數(shù)

unsigned int Dimension;//輸入點(diǎn)的維度

SInputData():pData(NULL),NumInput(0),Dimension(0) //初始化

const double*getInputDataAt(unsigned int vIndex)const; //取特定點(diǎn)的值

}；

struct SNode

{

int SplitAxis;//確定分割空間的維度坐標(biāo)軸

int LeftIndex,RightIndex;//排序后，葉子節(jié)點(diǎn)左右邊界索引

double SplitLowerBound,SplitUpperBound;//劃分空間時(shí)，左子區(qū)域的最大值和右子區(qū)域的最小值

SNode*pLeftChild,*pRightChild;//左、右孩子節(jié)點(diǎn)指針

};

KD-Tree的構(gòu)建是一個(gè)遞歸的過程，核心是實(shí)現(xiàn)劃分函數(shù)，結(jié)果返回KD-Tree的跟節(jié)點(diǎn)。首先根據(jù)輸入的數(shù)據(jù)點(diǎn)集計(jì)算出一個(gè)超立方體包圍盒將所有的點(diǎn)集包圍，計(jì)算每一個(gè)維度上的最大值和最小值，然后通過每一維度上的最大最小值求出對(duì)應(yīng)維度的跨度，選擇跨度最大的維度作為劃分軸，同時(shí)求出劃分閾值(Max+ Min)/2用于對(duì)相應(yīng)維度上的數(shù)據(jù)排序，就確定了該點(diǎn)所屬的左右子區(qū)域，經(jīng)過多次調(diào)用后得到由小到大排序后的新數(shù)據(jù)集m_pRecorderData(用于后續(xù)搜索)，同時(shí)在上一步的每趟排序的時(shí)候會(huì)得到一個(gè)Left值，用于確定每次劃分超平面的節(jié)點(diǎn)偏移量。如此遞歸進(jìn)行，直到每個(gè)區(qū)域的樣本點(diǎn)小于預(yù)先設(shè)定的閾值m_MaxNumDataInFeafNode為止。

搜索過程：

經(jīng)過KD-Tree的建立，我們可以得到排序后的數(shù)據(jù)集m_pRecorderData和樹的根節(jié)點(diǎn)m_pRootNode，現(xiàn)輸入目標(biāo)點(diǎn)pTargetPoint，需要查找其K個(gè)鄰接點(diǎn)。首先，根據(jù)輸入的目標(biāo)點(diǎn)判斷其是否在最大的包圍區(qū)域內(nèi)，然后根據(jù)KD-Tree的根節(jié)點(diǎn)中存儲(chǔ)的當(dāng)前劃分軸SplitAxis、左子區(qū)域的當(dāng)前維度的最大值SplitLower-Bound和右子區(qū)域當(dāng)前維度的最小值SplitUpper-Bound，計(jì)算目標(biāo)點(diǎn)到他們的距離來判斷離哪個(gè)區(qū)域更近，如果pTargetPoint在當(dāng)前劃分軸上的值小于Split-LowerBound，則繼續(xù)向下搜索左子區(qū)域，并將左子區(qū)域標(biāo)記為pBestChild，右子區(qū)域?yàn)閜OtherChild；反之，如果pTargetPoint在當(dāng)前劃分軸的值大于SplitUpperBound，則繼續(xù)向下搜索右子區(qū)域，并將右子區(qū)域標(biāo)記為pBestChild，左子區(qū)域?yàn)閜OtherChild。同時(shí)保存pTargetPoint到當(dāng)前劃分軸SplitAxis的垂直距離，作為后續(xù)回溯搜索的依據(jù)。

依據(jù)上次搜索過程對(duì)pBestChild子區(qū)域進(jìn)行遞歸操作，知道搜索到葉子結(jié)點(diǎn)，計(jì)算葉子結(jié)點(diǎn)中的樣本點(diǎn)到目標(biāo)點(diǎn)的歐氏距離并通過優(yōu)先級(jí)隊(duì)列排序，取得歐氏距離最小的K個(gè)節(jié)點(diǎn)并保存。

2.2 基于點(diǎn)的繪制算法

本文實(shí)現(xiàn)的點(diǎn)繪制算法的重建操作都是在GPU上進(jìn)行的，算法流程如下：

圖1

由三維點(diǎn)云通過計(jì)算得到相應(yīng)點(diǎn)擴(kuò)面的半徑，然后通過三維坐標(biāo)、半徑、法向量來構(gòu)建原盤，通過構(gòu)建圓盤生成深度圖，通過深度圖判斷在下一階段是否生成相應(yīng)的圓盤，同時(shí)完成背面剔除，然后把交叉原盤的法向量進(jìn)行融合，最后進(jìn)行光照計(jì)算得到最后的繪制結(jié)果。

由于采集到的點(diǎn)云之間存在空隙，所以需要在點(diǎn)的法平面上擴(kuò)展出一個(gè)一定半徑大小的圓盤來填補(bǔ)點(diǎn)與點(diǎn)之間的空隙，過小半徑的圓盤不足以填補(bǔ)點(diǎn)與點(diǎn)之間的空隙，太大半徑的圓盤會(huì)導(dǎo)致圓盤之間的交叉，使最后的繪制結(jié)果出現(xiàn)明顯的失真，因此本文采用表面融合算法來對(duì)交叉的圓盤進(jìn)行平滑處理。

本文實(shí)驗(yàn)部分采用的點(diǎn)云數(shù)據(jù)是通過相應(yīng)程序計(jì)算得到，點(diǎn)云分布不太均勻，因此采用了前面提到的KNN算法來自適應(yīng)的得到圓盤半徑。渲染過程中，第一步通過點(diǎn)云數(shù)據(jù)生成相應(yīng)的圓盤，同時(shí)開啟深度測(cè)試。第二步生成圓盤融合之后的法向量，在這一過程中，為了加速繪制算法，通過第一步保存的深度信息來判斷是否需要在第二步中構(gòu)建圓盤，從而避免冗余的圓盤生成，加速繪制效率，最后在第三步進(jìn)行光照計(jì)算渲染場(chǎng)景重建出三維物體。

在面元交叉處由于法向量會(huì)出現(xiàn)突變現(xiàn)象，所以需要進(jìn)行表面融合，消除或減弱法向量的突變現(xiàn)象，使之看起來近似于連續(xù)變化。本文考慮視點(diǎn)射線閾值范圍內(nèi)所有的相交點(diǎn)，將射線上所有相交點(diǎn)的法向量加權(quán)平均作為當(dāng)前點(diǎn)渲染點(diǎn)的法向量。本文通過Gauss函數(shù)來表示權(quán)值關(guān)系，本文通過Gauss邊界限定值來調(diào)節(jié)能量函數(shù)在面元上的分布，視點(diǎn)發(fā)出的射線與圓盤的每一個(gè)交點(diǎn)都對(duì)應(yīng)有相應(yīng)的Guass權(quán)值，最后可以得到視點(diǎn)方向下的相交點(diǎn)的法向量表示為：

對(duì)于超出射線閾值范圍的其他點(diǎn)，不做法向量融合操作。然后再將閾值范圍內(nèi)的交點(diǎn)的法向量做Guass加權(quán)平均，得到的結(jié)果可以有效地避免法向量突變。

在第一步處理時(shí)，在當(dāng)前視點(diǎn)下渲染整個(gè)場(chǎng)景，然后將場(chǎng)景的深度信息保存到紋理。在第二步的處理中引入深度值，通過深度值來判定是否生成圓盤。重新根據(jù)點(diǎn)的位置信息和法向量信息構(gòu)建圓盤，該步驟的主要目的是進(jìn)行法向量的融合。而且由于視點(diǎn)只能夠觀察到場(chǎng)景的前表面，也就是被遮擋的部分不需要進(jìn)行重新構(gòu)建面元。因此算法在這一步驟中，構(gòu)建面元之前事先計(jì)算當(dāng)前位置點(diǎn)與深度圖中保存的深度信息比較，如果處在閾值范圍內(nèi)則需要重新構(gòu)建面元，否則丟棄當(dāng)前點(diǎn)，這樣可以實(shí)現(xiàn)加速的目的。

第三步則根據(jù)融合得到的法向量進(jìn)行光照計(jì)算，得到重建出的物體。

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)數(shù)據(jù)來源于拍攝的圖片，通過前期處理生成.ply文件，文件中包含了點(diǎn)云數(shù)據(jù)的三維坐標(biāo)信息，法向量，顏色信息；通過本文的算法首先計(jì)算出各個(gè)點(diǎn)需要擴(kuò)展為圓盤的半徑大小，然后通過點(diǎn)繪制算法繪制出物體。

以下是不同角度的重建模型：

圖2

4 結(jié)語

基于點(diǎn)的繪制算法在圓盤的生成過程中，圓盤半徑過大會(huì)導(dǎo)致圓盤之間的交叉，因此本文引入Gauss濾波核函數(shù)為與視線相交并且在閾值范圍內(nèi)的相交點(diǎn)指定權(quán)值，最后得到加權(quán)平均之后的法向量。在進(jìn)行法向量融合時(shí)，充分利用深度圖保存的場(chǎng)景深度信息避免不必要的面元構(gòu)建，提高算法繪制效率。

本文的算法通過實(shí)現(xiàn)了圓盤半徑的自適應(yīng)可以更好地應(yīng)用于點(diǎn)云分布不均勻的模型，通過利用深度圖保存的場(chǎng)景信息來完成繪制的加速。本文基于點(diǎn)的繪制算法保證了點(diǎn)云的繪制效率但是在低采樣率的條件下不能得到良好的繪制效果，未來的工作會(huì)在提高低采樣率條件下的繪制效果方面作進(jìn)一步的改進(jìn)。

[1]Guennebaud G,Gross M.Algebraic Point Set Surfaces[C].ACM Transactions on Graphics(TOG).ACM,2007,26(3):23.

[2]Kim H J,Bickel B,Gross M,et al.Subsurface Scattering Using Splat-Based Diffusion in Point-Based Rendering[J].Science China In-formation Sciences,2010,53(5):911-919.

[3]Wu L.GPU Based Real-Time Rendering for Point-Based Models[J].Microcomputer Information,2010.

[4]Rusinkiewicz S,Levoy M.QSplat:A Multiresolution Point Rendering System for Large Meshes[C].Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques.ACM Press/Addison-Wesley Publishing Co.,2000:343-352.

[5]Goswami P,Zhang Y,Pajarola R,et al.High Quality Interactive Rendering of Massive Point Models Using Multi-way kd-Trees[J]. Computer Graphics and Applications(PG),2010 18th Pacific Conference on,2010:93-100.

[6]Pfister H,Zwicker M,Van Baar J,et al.Surfels:Surface Elements as Rendering Primitives[C].Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques.ACM Press/Addison-Wesley Publishing Co.,2000:335-342.

[7]Ren L,Pfister H,Zwicker M.Object Space EWA Surface Splatting:A Hardware Accelerated Approach to High Quality Point Rendering[C].Computer Graphics Forum.Blackwell Publishing,Inc,2002,21(3):461-470.

[8]Kim H J,Bickel B,Gross M,et al.Subsurface Scattering Using Splat-Based Diffusion in Point-Based Rendering[J].Science China Information Sciences,2010,53(5):911-919.

[9]張武,黃爭(zhēng)舸,張楨夏.點(diǎn)繪制技術(shù)的研究.計(jì)算機(jī)工程,2007(05):197-199.

Reconstruction Algorithm Based on 3D Point Cloud

LUO Wei,YANG Zhi-cheng

（College of Computer Science,Sichuan University，Chengdu 610065）

In recent years,It is more and more popular to get point cloud data from 3D scanner,As a result,point cloud based reconstruction has widely been studied in areas such as computer graphics and etc.This article uses KNN algorithm to calculate the radius of each point which needs to be extended to the disk size,then extends each point as a surfel with a certain size radius to cover the holes between each point,but the resulting problems is that the excessive length radius would produce the overlap with each surfel.We apply a gauss filter kernel function on each surfel to eliminate the cross distortion.At the same time,within the user defined parameters,we constraint the kernel function energy onto the surfel and obtain the desirable rendering result.

3 D Point Cloud;KNN;Point Based Rendering

1007-1423（2017）02-0054-04

10.3969/j.issn.1007-1423.2017.02.014

羅衛(wèi)（1990-），男，四川眉山人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)

0-），男，湖北襄陽人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)

2016-11-16

2017-01-12