三維散點云非均勻簡化算法

三維散點云非均勻簡化算法

0點云簡化算法近年來，隨著面漆技術(shù)的進(jìn)步，采樣點的精度達(dá)到了亞毫米水平。在3d水平的三維掃描中，有許多點。使用這些點進(jìn)行折射重建和后續(xù)處理將需要大量的時間和空間。因此,在保證能為模型重建提供必需信息的前提下,簡化測量數(shù)據(jù)點云是十分必要的。國內(nèi)外許多學(xué)者對三維散亂數(shù)據(jù)點集的簡化進(jìn)行了研究,Wang等人先用幾何圖像表示采樣點,然后根據(jù)簡化密度和曲面變分將點云進(jìn)行簡化;馬磊等人和王洪濤等人根據(jù)點數(shù)和表面變化系數(shù)實現(xiàn)測量數(shù)據(jù)點集的快速遞歸分塊,然后在每個分塊子集內(nèi)保留一個與該子集重心點最近的測量點實現(xiàn)數(shù)據(jù)簡化。賀美芳等人先計算出所有點的法向量,然后把曲率值小于給定閾值的數(shù)據(jù)點提取出來,按照數(shù)據(jù)個數(shù)進(jìn)行簡化,把曲率值大于給定閾值的數(shù)據(jù)點提取出來,進(jìn)行排序,再按照給定百分比提取;Pauly等人運用遞增式和分割式聚類方法實現(xiàn)了數(shù)據(jù)點集的快速遞歸劃分,在每個類中保留一個點實現(xiàn)了簡化。然而,以上點云簡化算法都沒有檢測邊界點,當(dāng)點云數(shù)據(jù)包含邊界時,邊界點可能會丟失,從而影響后續(xù)的曲面重建。文獻(xiàn)認(rèn)為如果數(shù)據(jù)點p的k鄰近點的分布偏向一側(cè),則點p為邊界特征點。本文根據(jù)其對邊界點的定義,對其鄰近點分布均勻性的判定方法進(jìn)行改進(jìn)。在邊界提取的基礎(chǔ)上,保留所有邊界點,再利用曲面變分將其他非邊界點區(qū)分為特征點和非特征點。對特征點,在其鄰域內(nèi)按比例保留,非特征點在鄰域內(nèi)保留一個點。1維k-to散亂點云沒有明顯的幾何分布特征,即沒有規(guī)律性,都呈散亂無序狀態(tài),因此必須建立數(shù)據(jù)點之間的空間拓?fù)潢P(guān)系才有利于查找每個點的k近鄰。目前搜索k近鄰常見的方法有三種:八叉樹、空間單元格和kd-tree法。本文首先采用kd-tree建立數(shù)據(jù)點之間的拓?fù)潢P(guān)系,從而找出各數(shù)據(jù)點的k近鄰,通過鄰近點的位置反映出待重建曲面在該測點處的形狀信息。kd-tree是Friedman等人于1977年提出的一種高維二叉樹,在其上可實現(xiàn)對給定目標(biāo)點的快速最近鄰查找。kd-tree的每一層將空間分成兩個。樹的頂層節(jié)點按一維進(jìn)行劃分,下一層節(jié)點按另一維進(jìn)行劃分,以此類推,各個維循環(huán)往復(fù)。劃分要使得在每個節(jié)點,大約一半存儲左子樹中,而另一半存儲在右子樹中。當(dāng)一個節(jié)點中的點數(shù)少于給定的最大點數(shù)時,劃分結(jié)束。二維kd-tree如圖1所示,左圖為剖分規(guī)則,其中水平線表示按X軸剖分,豎線表示按Y軸剖分。本文選取了一個合適的分割規(guī)則,即每次分割時選擇最長軸作為分割軸。散亂點云在X,Y,Z軸方向的最小和最大值分別為:Xmin,Xmax,Ymin,Ymax,Zmin,Zmax,則分割軸長分別為:ΔX=Xmax-Xmin,ΔY=Ymax-Ymin,ΔZ=Zmax-Zmin。例如ΔZ最大,即選擇Z軸進(jìn)行分割。計算出位于Z坐標(biāo)中間值的點,小于中間值的點位于節(jié)點的左子樹,大于中間值的點則位于節(jié)點的右子樹。2點pi、協(xié)方差矩陣以曲率為準(zhǔn)則的簡化算法,能夠保留模型的特征,其繪制效率顯著提高,但是對于散亂點集模型進(jìn)行曲率估算都比較復(fù)雜而耗時。Pauly等人使用曲面變分來估計點云的局部曲面變化,該方法簡單且能有效地反應(yīng)曲面信息,他指出曲面變分值越大,表示該處的曲面越彎曲,反之亦然。對于局部區(qū)域中某個點pi,pi周圍鄰近點記為pm∈Nb(pi),Nb(pi)表示離pi最近的k個點,pi周圍鄰近點均值為pi?=1k∑1kpipi-=1k∑1kpi,點pi的協(xié)方差矩陣定義為:Ci=????(p1?pˉi)?(pm?pˉi)????T????(p1?pˉi)?(pm?pˉi)????Ci=[(p1-pˉi)?(pm-pˉi)]Τ[(p1-pˉi)?(pm-pˉi)]Ci是對稱半正定矩陣,存在3個實數(shù)特征值,設(shè)其分別為λ1,λ2,λ3(假設(shè)λ1≤λ2≤λ2),它們對應(yīng)的特征向量分別為v1,v2,v3,v2和v3張成了pi處的最小二乘擬合平面,v1即為該平面的法矢方向,λ1的大小表明了待重建曲面在pi處沿法向方向的變化量。定義pi處的曲面變分為:σi=λ1λ1+λ2+λ3σi=λ1λ1+λ2+λ3。為了確定曲面變分的閾值,本文采取隨機采樣法估計點云的曲面變分平均值。在點云中隨機取出N點,計算這些點的曲面變分,然后計算平均值,即得到曲面變分的估計值,σ=∑i=0N?1σkσ=∑i=0Ν-1σk,曲面變分的閾值為:η=d*σ,d為期望保留點占總的點數(shù)的比值。3邊界點的計算文獻(xiàn)利用數(shù)據(jù)點的拓?fù)潢P(guān)系以及數(shù)據(jù)點法矢等信息構(gòu)造最小二乘平面,然后根據(jù)鄰域內(nèi)數(shù)據(jù)點在平面上的投影點之間分布均勻性提取邊界,如圖2中(a)所示。文獻(xiàn)投影點均勻性的判斷標(biāo)準(zhǔn)是角度標(biāo)準(zhǔn)差。該方法首先要找到離該點最近的點作為基準(zhǔn)點,其次要對鄰近點的夾角進(jìn)行排序從而計算出夾角標(biāo)準(zhǔn)差,當(dāng)數(shù)據(jù)量很大時,上述兩個步驟都會耗費大量時間。文獻(xiàn)投影點均勻性的判斷標(biāo)準(zhǔn)是角度間隔,該方法同樣要依據(jù)角度對數(shù)據(jù)點進(jìn)行排序,然后計算出相鄰數(shù)據(jù)點之間的角度差,效率也很低。本文基于鄰域內(nèi)數(shù)據(jù)點在平面上的投影點之間分布均勻性的思想,但是不計算夾角,而是直接比較坐標(biāo)值,因此可以節(jié)省很多時間。設(shè)點p為點云中的某一點,先利用kd-tree檢索該點的k鄰域,然后構(gòu)建最小二乘平面,并將鄰近點投影到其最小二乘平面上(如圖2(b)所示),過p點作平行于坐標(biāo)軸平面xoy,xoz,yoz的平面xpy,xpz,ypz,以xpy,xpz,ypz為參考平面,當(dāng)其鄰近點中位于某一平面一側(cè)的點與位于另外一側(cè)的點數(shù)差與鄰近點總數(shù)的比大于一定閾值時,該點即為邊界點。以p點和平面xpy為例,位于xpy上方的點有13個,位于下方(包括平面上)的點有2個,所以位于兩側(cè)的點數(shù)之差與鄰近點總數(shù)的比例為0.7333。邊界點的具體計算過程如下:1)由p點的鄰近點,計算出p點的法向量,然后構(gòu)造最小二乘平面T;2)將p點的鄰近點投影到平面T上;3)過p點作平行于xoy,xoz,yoz的平面,并計算出位于三個平面兩側(cè)的點;4)若位于平面兩側(cè)的點數(shù)之差占鄰近點總數(shù)的比例大于或等于f,該點即為邊界點。4鄰近保留點文獻(xiàn)根據(jù)局部區(qū)域中曲面變分和包含的點數(shù)進(jìn)行散亂點云簡化。要將原始點集細(xì)分成許多子集,這樣會占用大量的空間,而且當(dāng)曲面存在比較大的平坦區(qū)域時,文獻(xiàn)的方法會產(chǎn)生空洞。保留所有邊界點,對非邊界點,本文根據(jù)曲面變分及鄰近點保留情況進(jìn)行散亂點云的簡化。將曲面變分大于給定閾值點稱為特征點,而局部法向量大于給定閾值點稱為非特征點。如果某點的一鄰近點已經(jīng)確定為要保留的點,那么該鄰近點即為鄰近保留點。對特征點,根據(jù)其鄰近保留點數(shù)的比例進(jìn)行簡化;對非特征點,k鄰域中只保留一個點。這樣就可以在曲面變分大的地方保留更多的點,而曲面變分小的地方保留更少的點,輸出點集既不產(chǎn)生空洞,同時也能保留足夠的細(xì)節(jié)。簡化步驟如下:1)輸入散亂點云,建立kd-tree,從而建立點云的拓?fù)潢P(guān)系,找到數(shù)據(jù)點的k鄰域;2)判斷該點是否為邊界點,是則保留該點,否則跳至下一步;3)計算該點的曲面變分和鄰近點保留點的個數(shù),將曲面變分跟曲面變分閾值η比較,大于則跳至4),否則跳至5);4)將鄰近保留點數(shù)占鄰近點總數(shù)的比例與特征點比例系數(shù)e進(jìn)行比較,小于則保留該點,同時將該點的保留標(biāo)識置為true,否則刪除該點,直接跳至6);5)比較鄰近保留點數(shù)是否等于0,是則保留該點,同時將該點保留標(biāo)識置為true,否則刪除該點;6)重復(fù)3)～5),直到遍歷完點云數(shù)據(jù)中的所有點結(jié)束。5基于主機邊界點提取的案例應(yīng)用VC++6.0和OpenGL工具,在P43.0GHz,內(nèi)存2.0GB的計算機上實現(xiàn)了本文上述算法,并對幾組數(shù)據(jù)進(jìn)行了邊界點的提取及保留邊界點的簡化。本文點云數(shù)據(jù)均來自Hoppe的個人主頁。5.1汽車模型的邊界提取圖3為汽車模型和hypersheet模型的邊界提取。出于比較的目的,本文也可實現(xiàn)文獻(xiàn)中基本角度判定的算法,表1為本文算法和與角度判定法的耗費時間對比。從圖中可以看出汽車模型的車窗和車輪等底部的邊界非常清晰,hypersheet的外邊界圈也非常明朗,這表明本文的邊界提取算法效果良好。汽車模型的頂部突起部分之所以沒有保留,是因為本文定義的邊界是指開區(qū)域的邊界,并不包含邊界拐點。調(diào)整算法參數(shù),使得兩種算法提取的邊界點數(shù)目相等,見表1,從表中可以本文算法的效率明顯優(yōu)于角度判定算法。這主要是因為本文算法無需計算各鄰近點之間的角度并進(jìn)行角度差的排序,而是直接計算投影點的位置,從而可以節(jié)省很多時間。5.2模型的簡化和簡化為了突出模型邊界,本文算法提取到的邊界點用灰色顯示出來,如圖4和圖5中(b)所示。從圖中可以看出,文獻(xiàn)的方法由于沒有考慮邊界問題,在汽車模型的邊界部分丟失了一些點,使得模型的邊界很模糊甚至變形。汽車模型的車輪由于丟失了一些點使得車輪形狀發(fā)生了改變,而本文先提取邊界點,然后在簡化時,將邊界點全部保存下來,因此整個車模型的輪廓非常清楚。hypersheet也發(fā)生了變形,尤其是第二個圈由原來的圈變成了不規(guī)則的形狀。曲面變分的大小反應(yīng)了曲面的變化程度,在曲面變化大的地方按照比例保留點云,而在較平坦的區(qū)域鄰域內(nèi)只保留一點,從而既可以保留足夠的特征信息也可以達(dá)到點云簡化的目的。調(diào)節(jié)本文算法的系數(shù)和文獻(xiàn)聚類法的系數(shù),使得簡化后的點數(shù)相同,見表2。從表中可以看出,本文的簡化時間跟聚類法差不多,但是占用內(nèi)存少。文獻(xiàn)之所以占用的內(nèi)存大于本文占用的內(nèi)存,這是因為聚類的思想都要把點云剖分成許多小的點集,每個子集都占用一定的內(nèi)存,因此占用的內(nèi)存會很大;而本文逐個點進(jìn)行簡化,不需要額外的內(nèi)存開銷。6保留邊界點云簡化算法本文