基于三維點云的重建算法

羅衛(wèi)，楊志成

（四川大學計算機學院，成都 610065)

基于三維點云的重建算法

羅衛(wèi)，楊志成

（四川大學計算機學院，成都 610065)

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

三維點云；KNN；點繪制

0 引言

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

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

1 基于點的繪制算法

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

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

2 算法描述

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

2.1 KNN

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

構(gòu)造KD-Tree：

struct SInputData

{

const double*pData;//存放輸入的點集

unsigned int NumInput;//輸入點的個數(shù)

unsigned int Dimension;//輸入點的維度

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

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

}；

struct SNode

{

int SplitAxis;//確定分割空間的維度坐標軸

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

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

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

};

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

搜索過程：

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

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

2.2 基于點的繪制算法

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

圖1

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

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

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

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

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

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

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

3 實驗結(jié)果

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

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

圖2

4 結(jié)語

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

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

[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]張武,黃爭舸,張楨夏.點繪制技術(shù)的研究.計算機工程,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-），男，四川眉山人，碩士研究生，研究方向為計算機圖形學、虛擬現(xiàn)實

0-），男，湖北襄陽人，碩士研究生，研究方向為計算機圖形學、虛擬現(xiàn)實

2016-11-16

2017-01-12