牙頜點(diǎn)云數(shù)據(jù)的顯著性特征提?、?/h1>
2016-02-20 06:52:14陳玲玲譙舟三陳文樂
計(jì)算機(jī)系統(tǒng)應(yīng)用 2016年12期
陳玲玲, 楊 玲, 譙舟三, 陳文樂
1(成都信息工程大學(xué) 電子工程學(xué)院, 成都 610225)2(中國氣象局 大氣探測重點(diǎn)開放實(shí)驗(yàn)室, 成都 610225)
牙頜點(diǎn)云數(shù)據(jù)的顯著性特征提取①
陳玲玲1,2, 楊 玲1,2, 譙舟三1, 陳文樂1,2
1(成都信息工程大學(xué) 電子工程學(xué)院, 成都 610225)2(中國氣象局 大氣探測重點(diǎn)開放實(shí)驗(yàn)室, 成都 610225)
隨著激光掃描測量技術(shù)的發(fā)展, 其數(shù)據(jù)測量精度的逐漸增高使得獲取的幾何模型表面點(diǎn)云數(shù)據(jù)的細(xì)節(jié)信息越豐富, 能更準(zhǔn)確的反應(yīng)物體幾何表面特征, 但如此海量的點(diǎn)云數(shù)據(jù)同時也帶來對應(yīng)的技術(shù)挑戰(zhàn), 海量的點(diǎn)云數(shù)據(jù)在計(jì)算機(jī)文件存儲、數(shù)據(jù)后期進(jìn)一步處理以及軟件可視化方面都不方便且效率低下. 本文中的算法首先采用柵格法對點(diǎn)云進(jìn)行空間劃分及領(lǐng)域關(guān)系的建立, 其次利用局部表面擬合的方法估算點(diǎn)云法向量, 然后利用點(diǎn)云K領(lǐng)域法的向量求解坐標(biāo)點(diǎn)的顯著性值, 最后根據(jù)顯著性的值構(gòu)建點(diǎn)云八叉樹. 該算法實(shí)現(xiàn)了對點(diǎn)云顯著性特征的提取和對點(diǎn)云數(shù)據(jù)量的進(jìn)一步簡化, 它不僅保留了對點(diǎn)云細(xì)節(jié)特征保持方面的優(yōu)勢, 而且在時間效率上得到了提高.
點(diǎn)云數(shù)據(jù); 可視化; 顯著性特征; 三維配準(zhǔn); 網(wǎng)格化重建
目前國內(nèi)外針對點(diǎn)云數(shù)據(jù)集的精簡算法可以分為兩類, 第一: 通過對點(diǎn)云網(wǎng)格化處理后基于網(wǎng)格的精簡算法; 第二: 基于對采集數(shù)據(jù)直接處理的點(diǎn)云精簡方法. 前者方法首先通過對采集數(shù)據(jù)進(jìn)行網(wǎng)格化三角剖份, 利用四面體模型表面的點(diǎn)、邊和面之間相互關(guān)系拓?fù)鋽?shù)據(jù)壓縮方法, 該算法中首先需要對散亂點(diǎn)云進(jìn)行Delaunay三角剖份, 其整個時間復(fù)雜度較高, 算法效率較低. 而后者直接針對數(shù)據(jù)的精簡算法既具有時間復(fù)雜度較低等優(yōu)點(diǎn), 并且操作簡單. 主要有直接隨機(jī)采樣精簡、基于包圍盒空間劃分方法、基于均勻網(wǎng)格劃分的隨機(jī)抽樣法和基于高斯曲率和主曲率的精簡算法.
2001年LEE KH[1]等人提出利用被測數(shù)據(jù)法向信息, 對采集數(shù)據(jù)空間包圍盒柵格劃分, 在單個空間格中選擇特征點(diǎn), 從而完成數(shù)據(jù)精簡. 2002年DYN[2]等人提出的基于雙變量適應(yīng)性數(shù)據(jù)精簡算法可以達(dá)到與被測物體模型表面接近的效果而高效精簡數(shù)據(jù). 2004年洪軍[3]等人在通過相關(guān)研究基礎(chǔ)上, 提出的同時利用改進(jìn)型系數(shù)的空間包圍盒法和基于角度-弦高簡化法的合成數(shù)據(jù)精簡算法, 取得較好的數(shù)據(jù)壓縮效果. Pai-Feng Lee等在2006年提出了基于共面標(biāo)準(zhǔn)的八叉樹細(xì)分點(diǎn)云簡化算法. 2009年Hao Song[4]通過在對模式識別算法研究基礎(chǔ)上提出的通過構(gòu)造Voronoi圖的全局聚類采樣算法, 能有效地保留了點(diǎn)云中的邊界特征, 去除非邊界數(shù)據(jù)的非特征點(diǎn), 但該算法容易產(chǎn)生數(shù)據(jù)刪除孔洞, 容易誤刪除部分特征點(diǎn), 且速度仍有待提高. 史寶權(quán)[5]等人提取了利用模式識別算法原理的基于聚類的點(diǎn)云特征保存數(shù)據(jù)精簡方法. 2009年黃文明[6]等人提出的保留幾何特征的散亂點(diǎn)云簡化方法,在論文特定條件下取得較好的特征提取效果. 張欣[7]等人在2012年提出的基于特征保留的三角形折疊網(wǎng)格簡化算法, 但該算法沒有針對數(shù)據(jù)輪廓特征進(jìn)行處理, 一定程度上依賴網(wǎng)格劃分結(jié)果. Yitian Zhao在2012年提出基于法向夾角和高斯曲率結(jié)合的點(diǎn)云精簡算法, 通過算法效果驗(yàn)證得出該算法具有較好的效果. Nira DyT[8]通過構(gòu)造了—個非負(fù)度量函數(shù)平均每個數(shù)據(jù)點(diǎn)的權(quán)重分配, 這種算法能夠有效去除非特征點(diǎn),誤差刪除較小, 但由于反復(fù)迭代計(jì)算導(dǎo)致其效率較低.
針對上述算法各自的應(yīng)用特點(diǎn), 本文在研究二維圖像顯著性區(qū)域輪廓檢測算法基礎(chǔ)上引申到點(diǎn)云數(shù)據(jù)特征提取中, 提出一種基于顯著性標(biāo)準(zhǔn)衡量的牙頜點(diǎn)云特征提取精簡算法. 該算法首先采用柵格法對點(diǎn)云進(jìn)行空間劃分及領(lǐng)域關(guān)系的建立, 其次利用局部表面擬合的方法估算點(diǎn)云法向量, 然后利用點(diǎn)云K領(lǐng)域法的向量求解坐標(biāo)點(diǎn)的顯著性值, 最后根據(jù)顯著性的值構(gòu)建點(diǎn)云八叉樹, 從而實(shí)現(xiàn)對點(diǎn)云顯著性特征的提取,最終做到進(jìn)一步精簡數(shù)據(jù)量.
1 牙頜點(diǎn)云數(shù)據(jù)法向量計(jì)算及顯著性概念
1.1 求解單位法向量
關(guān)于散亂點(diǎn)云的法向量估計(jì)[9]方法, 國內(nèi)外研究人員提出相關(guān)的文獻(xiàn)比較多, 同時也提出了多種改進(jìn)算法, 具體參考表1.
表1 各個法向量估算算法比較
通過對各種算法的分析比較, 本文采用對噪聲、尖銳特征以及外點(diǎn)均能很好處理的局部表面擬合的方法來求解點(diǎn)云法向量, 該算法整體計(jì)算步驟如下:
1) 構(gòu)建平面方程
2) 求解約束方程
3) 轉(zhuǎn)化為求解極值問題
1.2 顯著性檢測概念
顯著性檢測主要是對二維圖像[10]的顏色、特征輪廓、數(shù)據(jù)信息代表的梯度以及圖像紋理等屬性進(jìn)行檢測, 由于其具有強(qiáng)大的圖像信息提取能力, 因此, 顯著性檢測被廣泛地應(yīng)用于彩色與灰度圖像的分割[11]、自適應(yīng)圖像壓縮[11,12]、視頻圖像特征提取[13]以及新興的基于內(nèi)容的圖像檢索等研究領(lǐng)域.
在三維模型中, 零顯著性的區(qū)域?yàn)橐粋€球面, 本文中我們用各點(diǎn)法向量之間夾角關(guān)系來表示三維模型中的顯著性, 顯著性較高的區(qū)域, 其各個點(diǎn)的法向量之間夾角會比較大. 而顯著性值較低的區(qū)域, 各相鄰三維數(shù)據(jù)點(diǎn)間的法向量夾角會比較小, 如圖1和圖2,分別展示了特征點(diǎn)、非特征點(diǎn)與相鄰點(diǎn)間法向方向與夾角示意圖. 因此本文通過引入散亂點(diǎn)云數(shù)據(jù)與其K鄰近點(diǎn)間的法向量夾角值作為顯著性度量特征參數(shù),公式如下:
圖1 空間數(shù)據(jù)中特征點(diǎn)與相鄰點(diǎn)法向方向和夾角
圖2 空間數(shù)據(jù)中非特征點(diǎn)與相鄰點(diǎn)法向方向和夾角
對于三維點(diǎn)集M, 設(shè)頂點(diǎn)p的領(lǐng)域N（p,δ）, 其中:
則定義坐標(biāo)點(diǎn)的高斯平均顯著性為:
以上高斯平均顯著性計(jì)算公式中, 假定高斯濾波器的截止頻率為2δ.
1.3 八叉樹法原理
八叉樹作為區(qū)域四叉樹向三維空間的推廣, 用于描述三維空間的樹狀數(shù)據(jù)結(jié)構(gòu), 通過迭代遞歸分割模型點(diǎn)云數(shù)據(jù)空間而實(shí)現(xiàn).
算法流程如下：1)首先讀取點(diǎn)云數(shù)據(jù)，構(gòu)造數(shù)據(jù)集的三維空間包圍盒，并依此建立點(diǎn)云拓?fù)潢P(guān)系的基礎(chǔ)和模型，并進(jìn)一步劃分為八個子立方體, 同時將其加入到根節(jié)點(diǎn)的子節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)中. 2)反復(fù)迭代第一步, 直到最小子立方體的邊長小于或者等于設(shè)定的閾值, 到此, 將點(diǎn)云數(shù)據(jù)集三維空間已經(jīng)劃分為2的冪次方個子立方體(如圖3中 (b)和(c)展示的八叉樹空間模型建立過程). 如圖3中(a)所示, 在八叉樹三維模型空間劃分流程中, 子立方體拓?fù)浣Y(jié)構(gòu)的編碼與其所在的空間位置緊密相關(guān).
圖3 八叉樹空間劃分模型及劃分示意圖
2 基于顯著性的牙頜點(diǎn)云數(shù)據(jù)特征提取算法
2.1求解法向量和數(shù)據(jù)預(yù)處理
首先將讀取的牙頜點(diǎn)云數(shù)據(jù)采用局部表面擬合的方法求解法向量求解, 然后進(jìn)行點(diǎn)云數(shù)據(jù)的柵格空間劃分及模型三維鄰域關(guān)系的建立.
1) 根據(jù)讀取的點(diǎn)云數(shù)據(jù), 求解每個坐標(biāo)軸上最大和最小值, 分別為:xmax,xmin,ymax,ymin,zmax,zmin
2) 根據(jù)1)計(jì)算最小包圍盒的大小:
其中N表示所有頂點(diǎn)的個數(shù).
3) 根據(jù)步驟2)得到的最小包圍盒邊長, 計(jì)算三個坐標(biāo)軸上可劃分包圍盒空間的最大個數(shù):
4) 計(jì)算每個坐標(biāo)點(diǎn)在X, Y, Z軸三個坐標(biāo)的所屬包圍盒序號:
5) 根據(jù)X, Y, Z軸的包圍盒序號計(jì)算該點(diǎn)所屬空間包圍盒的BoxID,并存儲計(jì)算得到的BoxID與該點(diǎn)的ID為式(12):
圖4 空間包圍盒建立示意圖
2.2 點(diǎn)云顯著性特征值的求解
1) 采用k-d tree算法查找每個點(diǎn)云數(shù)據(jù)的K鄰近點(diǎn)坐標(biāo);
2) 利用顯著性計(jì)算公式(5)求解該點(diǎn)法向量去K鄰近點(diǎn)法向夾角值, 并計(jì)算對應(yīng)高斯平均顯著性值.
2.3 構(gòu)建點(diǎn)云八叉樹模型
構(gòu)建八叉樹模型首先需要初始化八叉樹的根節(jié)點(diǎn), 然后計(jì)算出八叉樹細(xì)分的最小節(jié)點(diǎn)長度為
和初始化八叉樹最小的菱長為
根據(jù)構(gòu)建的初始八叉樹, 按照如下的細(xì)分準(zhǔn)則對樹進(jìn)行劃分: 初始設(shè)置一個參數(shù)ξ, 計(jì)算顯著性變化的標(biāo)準(zhǔn)偏差為:
若δ＜ξ, 則節(jié)點(diǎn)所包含的區(qū)域被忽略為一個點(diǎn);若δ＞ξ, 則節(jié)點(diǎn)所包含的區(qū)域顯著性特征值大, 需要細(xì)分. 上述兩個細(xì)分準(zhǔn)則能夠根據(jù)某塊固定大小的區(qū)域內(nèi)顯著性的方差而去確定是否繼續(xù)細(xì)分. 算法流程圖如圖5 所示.
3 牙頜點(diǎn)云顯著性特征提取算法效果分析
如圖6所示為單顆牙齒點(diǎn)云數(shù)據(jù)及特征提取效果圖, 圖中的紅色點(diǎn)為采用顯著性方法提取的特征點(diǎn),藍(lán)色點(diǎn)為非特征點(diǎn). 從圖6(b)的法向量結(jié)果來看, 提取出來的顯著性特征值有很多都不是單顆牙齒中實(shí)際的顯著性特征值, 其對于顯著特征值提取的準(zhǔn)確率很低, 但是從圖6(c)的提取效果圖來看, 對于單顆牙齒的邊緣特征值都已經(jīng)成功提取出來, 并且并沒有提取出多余的非特征值點(diǎn). 對于圖7的完整牙頜點(diǎn)云顯著性特征值的提取效果來看, 法向量求解提取出來的特征值有很多都是非顯著性特征值, 而圖7(c)中采用顯著性特征提出的較多都是完整牙頜點(diǎn)云數(shù)據(jù)的顯著性特征值. 從圖8中的完整牙頜點(diǎn)云數(shù)據(jù)特征提取局部放大效果對比圖中也可以看出顯著性特征提取出來的特征值更加準(zhǔn)確可靠.
圖5 算法總流程圖
圖6 單顆牙齒點(diǎn)云數(shù)據(jù)及特征提取效果
圖7 完整牙頜點(diǎn)云顯著性特征提取效果
圖8 完整牙頜點(diǎn)云特征提取局部放大效果對比圖
如圖9所示, 是對于三顆牙齒點(diǎn)云數(shù)據(jù)提取效果對比圖, (b)是針對顯著性特征提取出來的效果圖, 其中紅色點(diǎn)基本都是分布在三顆牙齒的邊緣位置和輪廓較明顯的位置, (c)是通過高斯曲率特征提取的特征值效果圖, 圖中的紅色點(diǎn)較少, 對于明顯的特征位置都未提取出來, 所以其提取特征的效果很差.
圖9 三顆牙齒點(diǎn)云特征提取效果對比圖
為了驗(yàn)證此基于顯著性特征提取方法的實(shí)用性,利用斯坦福的開放數(shù)據(jù)(大象點(diǎn)云數(shù)據(jù)、兔子點(diǎn)云數(shù)據(jù)、馬點(diǎn)云數(shù)據(jù))進(jìn)行試驗(yàn), 其運(yùn)行測試效果圖如圖10、11、12所示, 從提取出來的實(shí)驗(yàn)結(jié)果圖中可以看出, 每幅點(diǎn)云數(shù)據(jù)中的邊緣輪廓、圖像紋理等顯著性特征都得到了較好的提取.
圖10 大象點(diǎn)云顯著性特征提取效果
圖11 兔子點(diǎn)云顯著性特征提取效果
圖12 馬點(diǎn)云顯著性特征提取局部放大效果
如表1所示, 通過采用頜部分缺失數(shù)據(jù)和完整牙頜數(shù)據(jù), 單顆牙齒數(shù)據(jù)、三顆牙齒數(shù)據(jù), 以及斯坦福大學(xué)開放的點(diǎn)云數(shù)據(jù)做進(jìn)一步測試, 同時還通過與該點(diǎn)云數(shù)據(jù)的平均曲率特征提取結(jié)果比較, 可以明顯看出本文算法能夠?qū)Ω鞣N數(shù)據(jù)的輪廓特征、圖像紋理進(jìn)行有效提取, 并且其時間效率是基于曲率特征提取算法的10%左右.
表1 特征提取算法時間對比分析
4 結(jié)語
本文提出一種新的基于顯著性牙頜點(diǎn)云特征提取的方法, 該方法利用法向量作為衡量三維點(diǎn)云模型顯著性特征的標(biāo)準(zhǔn), 直接對點(diǎn)云數(shù)據(jù)進(jìn)行顯著性特征的提取. 通過基礎(chǔ)性研究分析, 使用數(shù)據(jù)點(diǎn)單位法向量與K鄰近點(diǎn)的單位法向量的點(diǎn)積均值構(gòu)建高斯平均顯著性參量, 替代以曲率作為該點(diǎn)所在三維模型局部曲面的彎曲程度或者輪廓是否明顯的數(shù)值表示, 避免了曲率估算過程中引起的較高時間復(fù)雜度, 同時利用采集的單顆牙齒、三顆牙齒以及牙頜部分缺失數(shù)據(jù)和完整牙頜數(shù)據(jù)進(jìn)行驗(yàn)證分析, 利用斯坦福大學(xué)開放點(diǎn)云數(shù)據(jù)做進(jìn)一步測試, 并和曲率特征提取等算法進(jìn)行對比, 均取得較好效果. 算法不僅保留了對點(diǎn)云細(xì)節(jié)特征保持方面的優(yōu)勢, 而且在時間效率上得到了提高.
1 Lee KH, Woo H, Suk T. Point data reduction using 3D girds. The International Journal of Advanced Manufacturing Technology, 2001: 201–210.
2 Dyn N, Floater MS, Iske A. Adaptive thinning for bivariate scattered data. Journal of Computationaland Applied Mathematics, 2002.
3 洪軍,丁玉成,曹亮,等.逆向工程中的測量數(shù)據(jù)精簡技術(shù)研究.西安交通大學(xué)學(xué)報(bào),2004,38(7):661–664.
4 Song H, Feng HY. A global clustering approach to point cloud simplification with a specified data reduction ratio. Computer-Aided Design, 2008: 281–292.
5 史寶全,梁晉,張曉強(qiáng),等.特征保持的點(diǎn)云精簡技術(shù)研究.西安交通大學(xué)學(xué)報(bào),2010,44(11):37–40.
6 黃文明,肖朝霞.保留邊界的點(diǎn)云簡化方法.計(jì)算機(jī)應(yīng)用, 2010,30(2):348.
7 張欣,秦茂玲,謝堂龍.基于特征保持的三角形折疊網(wǎng)格簡化算法.計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(1):1–6.
8 Dyn N, Iske A, Wendland H. Meshfree thinning of 3D point clouds. Foundations of Computational Mathematics, 2008, 409–425.
9 李寶,程志.三維點(diǎn)云法向量估計(jì)綜述.計(jì)算機(jī)工程與應(yīng)用,2010,46(23):1–6.
10 Goferman S, Zelnik-Manor L, Tal A. Context-aware saliency detection. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2012, 1915–1926.
11 Perazzi F, Krahenbuhl P, Pritch Y, et al. Saliency filters: Contrast based filtering for salient region detection. 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE. 733–740.
12 Achanta R, Hemami S, Estrada F, et al. Frequency-tuned salient region detection. IEEE Conference on Computer Vision and Pattern Recognition, 2009. IEEE. 1597–1604.
13 Cheng MM, Zhang GX, Mitra NJ, et al. Global contrast based salient region detection. 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE. 2011. 409–416.
Significant Feature Extraction for the Dental Point Cloud Data
CHEN Ling-Ling1,2, YANG Ling1,2, QIAO Zhou-San1, CHEN Wen-Le1,212
(College of Electronic Engineering, Chengdu University of Information Technology, Chengdu 610225, China) (Key Laboratory of Atmospheric Sounding of CMA, Chengdu 610225, China)
With the development of laser scanning measurement technology, the detailed information about the surface point cloud data of the geometric model is more abundant due to the more efficient data detection accuracy, make it more precise to show the surface features of objects. However, the corresponding technical challenges may appear at the same time because of such a large amount of point cloud data, which can be used in the computer file storage, data post-processing and software visualization inconveniently and inefficiently. A new algorithm is introduced in this paper. Firstly, we make a space division for point cloud data and establish the domain relationship using the grid method. Secondly, we estimate the point cloud normal vector by means of local surface fitting. Thirdly, we find out the significant value of the coordinate points using the point cloud K field method. Finally, we achieve the point cloud octree according to the significant value. In a word, this algorithm realizes the goal that the significant features of the point cloud can be extracted and the amount of the point cloud data can be simplified. Not only does it retain the advantages of the detail characteristics of the point cloud, but also make it more effective.
point cloud data; visualization; significance feature; 3D registration; grid reconstruction
2016-04-29;收到修改稿時間:2016-07-14
10.15888/j.cnki.csa.005625
猜你喜歡
三維十字鏈表八叉樹的高效檢索實(shí)現(xiàn)棗莊學(xué)院學(xué)報(bào)(2022年5期)2022-09-21 09:35:22 一類帶強(qiáng)制位勢的p-Laplace特征值問題數(shù)學(xué)物理學(xué)報(bào)(2021年5期)2021-11-19 07:01:12 單圈圖關(guān)聯(lián)矩陣的特征值煙臺大學(xué)學(xué)報(bào)(自然科學(xué)與工程版)(2021年1期)2021-03-19 08:38:40 時常精簡多余物品特別健康(2018年2期)2018-06-29 06:14:00 一種面向應(yīng)用的流量監(jiān)測精簡架構(gòu)設(shè)計(jì)電子制作(2017年17期)2017-12-18 06:40:47 基于商奇異值分解的一類二次特征值反問題東北電力大學(xué)學(xué)報(bào)(2015年1期)2015-11-13 05:20:25 關(guān)于兩個M-矩陣Hadamard積的特征值的新估計(jì)四川輕化工大學(xué)學(xué)報(bào)(自然科學(xué)版)(2014年3期)2014-04-16 03:56:42 應(yīng)用于SAN的自動精簡配置架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)計(jì)算機(jī)工程(2014年6期)2014-02-28 01:25:08 散亂點(diǎn)云線性八叉樹結(jié)構(gòu)在GPU中的實(shí)現(xiàn)機(jī)械設(shè)計(jì)與制造工程(2013年4期)2013-09-12 03:23:04 基于密集型區(qū)域的八叉樹劃分算法科技傳播(2012年2期)2012-06-13 10:03:26
陳玲玲, 楊 玲, 譙舟三, 陳文樂
1(成都信息工程大學(xué) 電子工程學(xué)院, 成都 610225)2(中國氣象局 大氣探測重點(diǎn)開放實(shí)驗(yàn)室, 成都 610225)
牙頜點(diǎn)云數(shù)據(jù)的顯著性特征提取①
陳玲玲1,2, 楊 玲1,2, 譙舟三1, 陳文樂1,2
1(成都信息工程大學(xué) 電子工程學(xué)院, 成都 610225)2(中國氣象局 大氣探測重點(diǎn)開放實(shí)驗(yàn)室, 成都 610225)
隨著激光掃描測量技術(shù)的發(fā)展, 其數(shù)據(jù)測量精度的逐漸增高使得獲取的幾何模型表面點(diǎn)云數(shù)據(jù)的細(xì)節(jié)信息越豐富, 能更準(zhǔn)確的反應(yīng)物體幾何表面特征, 但如此海量的點(diǎn)云數(shù)據(jù)同時也帶來對應(yīng)的技術(shù)挑戰(zhàn), 海量的點(diǎn)云數(shù)據(jù)在計(jì)算機(jī)文件存儲、數(shù)據(jù)后期進(jìn)一步處理以及軟件可視化方面都不方便且效率低下. 本文中的算法首先采用柵格法對點(diǎn)云進(jìn)行空間劃分及領(lǐng)域關(guān)系的建立, 其次利用局部表面擬合的方法估算點(diǎn)云法向量, 然后利用點(diǎn)云K領(lǐng)域法的向量求解坐標(biāo)點(diǎn)的顯著性值, 最后根據(jù)顯著性的值構(gòu)建點(diǎn)云八叉樹. 該算法實(shí)現(xiàn)了對點(diǎn)云顯著性特征的提取和對點(diǎn)云數(shù)據(jù)量的進(jìn)一步簡化, 它不僅保留了對點(diǎn)云細(xì)節(jié)特征保持方面的優(yōu)勢, 而且在時間效率上得到了提高.
點(diǎn)云數(shù)據(jù); 可視化; 顯著性特征; 三維配準(zhǔn); 網(wǎng)格化重建
目前國內(nèi)外針對點(diǎn)云數(shù)據(jù)集的精簡算法可以分為兩類, 第一: 通過對點(diǎn)云網(wǎng)格化處理后基于網(wǎng)格的精簡算法; 第二: 基于對采集數(shù)據(jù)直接處理的點(diǎn)云精簡方法. 前者方法首先通過對采集數(shù)據(jù)進(jìn)行網(wǎng)格化三角剖份, 利用四面體模型表面的點(diǎn)、邊和面之間相互關(guān)系拓?fù)鋽?shù)據(jù)壓縮方法, 該算法中首先需要對散亂點(diǎn)云進(jìn)行Delaunay三角剖份, 其整個時間復(fù)雜度較高, 算法效率較低. 而后者直接針對數(shù)據(jù)的精簡算法既具有時間復(fù)雜度較低等優(yōu)點(diǎn), 并且操作簡單. 主要有直接隨機(jī)采樣精簡、基于包圍盒空間劃分方法、基于均勻網(wǎng)格劃分的隨機(jī)抽樣法和基于高斯曲率和主曲率的精簡算法.
2001年LEE KH[1]等人提出利用被測數(shù)據(jù)法向信息, 對采集數(shù)據(jù)空間包圍盒柵格劃分, 在單個空間格中選擇特征點(diǎn), 從而完成數(shù)據(jù)精簡. 2002年DYN[2]等人提出的基于雙變量適應(yīng)性數(shù)據(jù)精簡算法可以達(dá)到與被測物體模型表面接近的效果而高效精簡數(shù)據(jù). 2004年洪軍[3]等人在通過相關(guān)研究基礎(chǔ)上, 提出的同時利用改進(jìn)型系數(shù)的空間包圍盒法和基于角度-弦高簡化法的合成數(shù)據(jù)精簡算法, 取得較好的數(shù)據(jù)壓縮效果. Pai-Feng Lee等在2006年提出了基于共面標(biāo)準(zhǔn)的八叉樹細(xì)分點(diǎn)云簡化算法. 2009年Hao Song[4]通過在對模式識別算法研究基礎(chǔ)上提出的通過構(gòu)造Voronoi圖的全局聚類采樣算法, 能有效地保留了點(diǎn)云中的邊界特征, 去除非邊界數(shù)據(jù)的非特征點(diǎn), 但該算法容易產(chǎn)生數(shù)據(jù)刪除孔洞, 容易誤刪除部分特征點(diǎn), 且速度仍有待提高. 史寶權(quán)[5]等人提取了利用模式識別算法原理的基于聚類的點(diǎn)云特征保存數(shù)據(jù)精簡方法. 2009年黃文明[6]等人提出的保留幾何特征的散亂點(diǎn)云簡化方法,在論文特定條件下取得較好的特征提取效果. 張欣[7]等人在2012年提出的基于特征保留的三角形折疊網(wǎng)格簡化算法, 但該算法沒有針對數(shù)據(jù)輪廓特征進(jìn)行處理, 一定程度上依賴網(wǎng)格劃分結(jié)果. Yitian Zhao在2012年提出基于法向夾角和高斯曲率結(jié)合的點(diǎn)云精簡算法, 通過算法效果驗(yàn)證得出該算法具有較好的效果. Nira DyT[8]通過構(gòu)造了—個非負(fù)度量函數(shù)平均每個數(shù)據(jù)點(diǎn)的權(quán)重分配, 這種算法能夠有效去除非特征點(diǎn),誤差刪除較小, 但由于反復(fù)迭代計(jì)算導(dǎo)致其效率較低.
針對上述算法各自的應(yīng)用特點(diǎn), 本文在研究二維圖像顯著性區(qū)域輪廓檢測算法基礎(chǔ)上引申到點(diǎn)云數(shù)據(jù)特征提取中, 提出一種基于顯著性標(biāo)準(zhǔn)衡量的牙頜點(diǎn)云特征提取精簡算法. 該算法首先采用柵格法對點(diǎn)云進(jìn)行空間劃分及領(lǐng)域關(guān)系的建立, 其次利用局部表面擬合的方法估算點(diǎn)云法向量, 然后利用點(diǎn)云K領(lǐng)域法的向量求解坐標(biāo)點(diǎn)的顯著性值, 最后根據(jù)顯著性的值構(gòu)建點(diǎn)云八叉樹, 從而實(shí)現(xiàn)對點(diǎn)云顯著性特征的提取,最終做到進(jìn)一步精簡數(shù)據(jù)量.
1 牙頜點(diǎn)云數(shù)據(jù)法向量計(jì)算及顯著性概念
1.1 求解單位法向量
關(guān)于散亂點(diǎn)云的法向量估計(jì)[9]方法, 國內(nèi)外研究人員提出相關(guān)的文獻(xiàn)比較多, 同時也提出了多種改進(jìn)算法, 具體參考表1.
表1 各個法向量估算算法比較
通過對各種算法的分析比較, 本文采用對噪聲、尖銳特征以及外點(diǎn)均能很好處理的局部表面擬合的方法來求解點(diǎn)云法向量, 該算法整體計(jì)算步驟如下:
1) 構(gòu)建平面方程
2) 求解約束方程
3) 轉(zhuǎn)化為求解極值問題
1.2 顯著性檢測概念
顯著性檢測主要是對二維圖像[10]的顏色、特征輪廓、數(shù)據(jù)信息代表的梯度以及圖像紋理等屬性進(jìn)行檢測, 由于其具有強(qiáng)大的圖像信息提取能力, 因此, 顯著性檢測被廣泛地應(yīng)用于彩色與灰度圖像的分割[11]、自適應(yīng)圖像壓縮[11,12]、視頻圖像特征提取[13]以及新興的基于內(nèi)容的圖像檢索等研究領(lǐng)域.
在三維模型中, 零顯著性的區(qū)域?yàn)橐粋€球面, 本文中我們用各點(diǎn)法向量之間夾角關(guān)系來表示三維模型中的顯著性, 顯著性較高的區(qū)域, 其各個點(diǎn)的法向量之間夾角會比較大. 而顯著性值較低的區(qū)域, 各相鄰三維數(shù)據(jù)點(diǎn)間的法向量夾角會比較小, 如圖1和圖2,分別展示了特征點(diǎn)、非特征點(diǎn)與相鄰點(diǎn)間法向方向與夾角示意圖. 因此本文通過引入散亂點(diǎn)云數(shù)據(jù)與其K鄰近點(diǎn)間的法向量夾角值作為顯著性度量特征參數(shù),公式如下:
圖1 空間數(shù)據(jù)中特征點(diǎn)與相鄰點(diǎn)法向方向和夾角
圖2 空間數(shù)據(jù)中非特征點(diǎn)與相鄰點(diǎn)法向方向和夾角
對于三維點(diǎn)集M, 設(shè)頂點(diǎn)p的領(lǐng)域N（p,δ）, 其中:
則定義坐標(biāo)點(diǎn)的高斯平均顯著性為:
以上高斯平均顯著性計(jì)算公式中, 假定高斯濾波器的截止頻率為2δ.
1.3 八叉樹法原理
八叉樹作為區(qū)域四叉樹向三維空間的推廣, 用于描述三維空間的樹狀數(shù)據(jù)結(jié)構(gòu), 通過迭代遞歸分割模型點(diǎn)云數(shù)據(jù)空間而實(shí)現(xiàn).
算法流程如下：1)首先讀取點(diǎn)云數(shù)據(jù)，構(gòu)造數(shù)據(jù)集的三維空間包圍盒，并依此建立點(diǎn)云拓?fù)潢P(guān)系的基礎(chǔ)和模型，并進(jìn)一步劃分為八個子立方體, 同時將其加入到根節(jié)點(diǎn)的子節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)中. 2)反復(fù)迭代第一步, 直到最小子立方體的邊長小于或者等于設(shè)定的閾值, 到此, 將點(diǎn)云數(shù)據(jù)集三維空間已經(jīng)劃分為2的冪次方個子立方體(如圖3中 (b)和(c)展示的八叉樹空間模型建立過程). 如圖3中(a)所示, 在八叉樹三維模型空間劃分流程中, 子立方體拓?fù)浣Y(jié)構(gòu)的編碼與其所在的空間位置緊密相關(guān).
圖3 八叉樹空間劃分模型及劃分示意圖
2 基于顯著性的牙頜點(diǎn)云數(shù)據(jù)特征提取算法
2.1求解法向量和數(shù)據(jù)預(yù)處理
首先將讀取的牙頜點(diǎn)云數(shù)據(jù)采用局部表面擬合的方法求解法向量求解, 然后進(jìn)行點(diǎn)云數(shù)據(jù)的柵格空間劃分及模型三維鄰域關(guān)系的建立.
1) 根據(jù)讀取的點(diǎn)云數(shù)據(jù), 求解每個坐標(biāo)軸上最大和最小值, 分別為:xmax,xmin,ymax,ymin,zmax,zmin
2) 根據(jù)1)計(jì)算最小包圍盒的大小:
其中N表示所有頂點(diǎn)的個數(shù).
3) 根據(jù)步驟2)得到的最小包圍盒邊長, 計(jì)算三個坐標(biāo)軸上可劃分包圍盒空間的最大個數(shù):
4) 計(jì)算每個坐標(biāo)點(diǎn)在X, Y, Z軸三個坐標(biāo)的所屬包圍盒序號:
5) 根據(jù)X, Y, Z軸的包圍盒序號計(jì)算該點(diǎn)所屬空間包圍盒的BoxID,并存儲計(jì)算得到的BoxID與該點(diǎn)的ID為式(12):
圖4 空間包圍盒建立示意圖
2.2 點(diǎn)云顯著性特征值的求解
1) 采用k-d tree算法查找每個點(diǎn)云數(shù)據(jù)的K鄰近點(diǎn)坐標(biāo);
2) 利用顯著性計(jì)算公式(5)求解該點(diǎn)法向量去K鄰近點(diǎn)法向夾角值, 并計(jì)算對應(yīng)高斯平均顯著性值.
2.3 構(gòu)建點(diǎn)云八叉樹模型
構(gòu)建八叉樹模型首先需要初始化八叉樹的根節(jié)點(diǎn), 然后計(jì)算出八叉樹細(xì)分的最小節(jié)點(diǎn)長度為
和初始化八叉樹最小的菱長為
根據(jù)構(gòu)建的初始八叉樹, 按照如下的細(xì)分準(zhǔn)則對樹進(jìn)行劃分: 初始設(shè)置一個參數(shù)ξ, 計(jì)算顯著性變化的標(biāo)準(zhǔn)偏差為:
若δ＜ξ, 則節(jié)點(diǎn)所包含的區(qū)域被忽略為一個點(diǎn);若δ＞ξ, 則節(jié)點(diǎn)所包含的區(qū)域顯著性特征值大, 需要細(xì)分. 上述兩個細(xì)分準(zhǔn)則能夠根據(jù)某塊固定大小的區(qū)域內(nèi)顯著性的方差而去確定是否繼續(xù)細(xì)分. 算法流程圖如圖5 所示.
3 牙頜點(diǎn)云顯著性特征提取算法效果分析
如圖6所示為單顆牙齒點(diǎn)云數(shù)據(jù)及特征提取效果圖, 圖中的紅色點(diǎn)為采用顯著性方法提取的特征點(diǎn),藍(lán)色點(diǎn)為非特征點(diǎn). 從圖6(b)的法向量結(jié)果來看, 提取出來的顯著性特征值有很多都不是單顆牙齒中實(shí)際的顯著性特征值, 其對于顯著特征值提取的準(zhǔn)確率很低, 但是從圖6(c)的提取效果圖來看, 對于單顆牙齒的邊緣特征值都已經(jīng)成功提取出來, 并且并沒有提取出多余的非特征值點(diǎn). 對于圖7的完整牙頜點(diǎn)云顯著性特征值的提取效果來看, 法向量求解提取出來的特征值有很多都是非顯著性特征值, 而圖7(c)中采用顯著性特征提出的較多都是完整牙頜點(diǎn)云數(shù)據(jù)的顯著性特征值. 從圖8中的完整牙頜點(diǎn)云數(shù)據(jù)特征提取局部放大效果對比圖中也可以看出顯著性特征提取出來的特征值更加準(zhǔn)確可靠.
圖5 算法總流程圖
圖6 單顆牙齒點(diǎn)云數(shù)據(jù)及特征提取效果
圖7 完整牙頜點(diǎn)云顯著性特征提取效果
圖8 完整牙頜點(diǎn)云特征提取局部放大效果對比圖
如圖9所示, 是對于三顆牙齒點(diǎn)云數(shù)據(jù)提取效果對比圖, (b)是針對顯著性特征提取出來的效果圖, 其中紅色點(diǎn)基本都是分布在三顆牙齒的邊緣位置和輪廓較明顯的位置, (c)是通過高斯曲率特征提取的特征值效果圖, 圖中的紅色點(diǎn)較少, 對于明顯的特征位置都未提取出來, 所以其提取特征的效果很差.
圖9 三顆牙齒點(diǎn)云特征提取效果對比圖
為了驗(yàn)證此基于顯著性特征提取方法的實(shí)用性,利用斯坦福的開放數(shù)據(jù)(大象點(diǎn)云數(shù)據(jù)、兔子點(diǎn)云數(shù)據(jù)、馬點(diǎn)云數(shù)據(jù))進(jìn)行試驗(yàn), 其運(yùn)行測試效果圖如圖10、11、12所示, 從提取出來的實(shí)驗(yàn)結(jié)果圖中可以看出, 每幅點(diǎn)云數(shù)據(jù)中的邊緣輪廓、圖像紋理等顯著性特征都得到了較好的提取.
圖10 大象點(diǎn)云顯著性特征提取效果
圖11 兔子點(diǎn)云顯著性特征提取效果
圖12 馬點(diǎn)云顯著性特征提取局部放大效果
如表1所示, 通過采用頜部分缺失數(shù)據(jù)和完整牙頜數(shù)據(jù), 單顆牙齒數(shù)據(jù)、三顆牙齒數(shù)據(jù), 以及斯坦福大學(xué)開放的點(diǎn)云數(shù)據(jù)做進(jìn)一步測試, 同時還通過與該點(diǎn)云數(shù)據(jù)的平均曲率特征提取結(jié)果比較, 可以明顯看出本文算法能夠?qū)Ω鞣N數(shù)據(jù)的輪廓特征、圖像紋理進(jìn)行有效提取, 并且其時間效率是基于曲率特征提取算法的10%左右.
表1 特征提取算法時間對比分析
4 結(jié)語
本文提出一種新的基于顯著性牙頜點(diǎn)云特征提取的方法, 該方法利用法向量作為衡量三維點(diǎn)云模型顯著性特征的標(biāo)準(zhǔn), 直接對點(diǎn)云數(shù)據(jù)進(jìn)行顯著性特征的提取. 通過基礎(chǔ)性研究分析, 使用數(shù)據(jù)點(diǎn)單位法向量與K鄰近點(diǎn)的單位法向量的點(diǎn)積均值構(gòu)建高斯平均顯著性參量, 替代以曲率作為該點(diǎn)所在三維模型局部曲面的彎曲程度或者輪廓是否明顯的數(shù)值表示, 避免了曲率估算過程中引起的較高時間復(fù)雜度, 同時利用采集的單顆牙齒、三顆牙齒以及牙頜部分缺失數(shù)據(jù)和完整牙頜數(shù)據(jù)進(jìn)行驗(yàn)證分析, 利用斯坦福大學(xué)開放點(diǎn)云數(shù)據(jù)做進(jìn)一步測試, 并和曲率特征提取等算法進(jìn)行對比, 均取得較好效果. 算法不僅保留了對點(diǎn)云細(xì)節(jié)特征保持方面的優(yōu)勢, 而且在時間效率上得到了提高.
1 Lee KH, Woo H, Suk T. Point data reduction using 3D girds. The International Journal of Advanced Manufacturing Technology, 2001: 201–210.
2 Dyn N, Floater MS, Iske A. Adaptive thinning for bivariate scattered data. Journal of Computationaland Applied Mathematics, 2002.
3 洪軍,丁玉成,曹亮,等.逆向工程中的測量數(shù)據(jù)精簡技術(shù)研究.西安交通大學(xué)學(xué)報(bào),2004,38(7):661–664.
4 Song H, Feng HY. A global clustering approach to point cloud simplification with a specified data reduction ratio. Computer-Aided Design, 2008: 281–292.
5 史寶全,梁晉,張曉強(qiáng),等.特征保持的點(diǎn)云精簡技術(shù)研究.西安交通大學(xué)學(xué)報(bào),2010,44(11):37–40.
6 黃文明,肖朝霞.保留邊界的點(diǎn)云簡化方法.計(jì)算機(jī)應(yīng)用, 2010,30(2):348.
7 張欣,秦茂玲,謝堂龍.基于特征保持的三角形折疊網(wǎng)格簡化算法.計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(1):1–6.
8 Dyn N, Iske A, Wendland H. Meshfree thinning of 3D point clouds. Foundations of Computational Mathematics, 2008, 409–425.
9 李寶,程志.三維點(diǎn)云法向量估計(jì)綜述.計(jì)算機(jī)工程與應(yīng)用,2010,46(23):1–6.
10 Goferman S, Zelnik-Manor L, Tal A. Context-aware saliency detection. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2012, 1915–1926.
11 Perazzi F, Krahenbuhl P, Pritch Y, et al. Saliency filters: Contrast based filtering for salient region detection. 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE. 733–740.
12 Achanta R, Hemami S, Estrada F, et al. Frequency-tuned salient region detection. IEEE Conference on Computer Vision and Pattern Recognition, 2009. IEEE. 1597–1604.
13 Cheng MM, Zhang GX, Mitra NJ, et al. Global contrast based salient region detection. 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE. 2011. 409–416.
Significant Feature Extraction for the Dental Point Cloud Data
CHEN Ling-Ling1,2, YANG Ling1,2, QIAO Zhou-San1, CHEN Wen-Le1,212
(College of Electronic Engineering, Chengdu University of Information Technology, Chengdu 610225, China) (Key Laboratory of Atmospheric Sounding of CMA, Chengdu 610225, China)
With the development of laser scanning measurement technology, the detailed information about the surface point cloud data of the geometric model is more abundant due to the more efficient data detection accuracy, make it more precise to show the surface features of objects. However, the corresponding technical challenges may appear at the same time because of such a large amount of point cloud data, which can be used in the computer file storage, data post-processing and software visualization inconveniently and inefficiently. A new algorithm is introduced in this paper. Firstly, we make a space division for point cloud data and establish the domain relationship using the grid method. Secondly, we estimate the point cloud normal vector by means of local surface fitting. Thirdly, we find out the significant value of the coordinate points using the point cloud K field method. Finally, we achieve the point cloud octree according to the significant value. In a word, this algorithm realizes the goal that the significant features of the point cloud can be extracted and the amount of the point cloud data can be simplified. Not only does it retain the advantages of the detail characteristics of the point cloud, but also make it more effective.
point cloud data; visualization; significance feature; 3D registration; grid reconstruction
2016-04-29;收到修改稿時間:2016-07-14
10.15888/j.cnki.csa.005625
猜你喜歡
棗莊學(xué)院學(xué)報(bào)(2022年5期)2022-09-21 09:35:22
數(shù)學(xué)物理學(xué)報(bào)(2021年5期)2021-11-19 07:01:12
煙臺大學(xué)學(xué)報(bào)(自然科學(xué)與工程版)(2021年1期)2021-03-19 08:38:40
特別健康(2018年2期)2018-06-29 06:14:00
電子制作(2017年17期)2017-12-18 06:40:47
東北電力大學(xué)學(xué)報(bào)(2015年1期)2015-11-13 05:20:25
四川輕化工大學(xué)學(xué)報(bào)(自然科學(xué)版)(2014年3期)2014-04-16 03:56:42
計(jì)算機(jī)工程(2014年6期)2014-02-28 01:25:08
機(jī)械設(shè)計(jì)與制造工程(2013年4期)2013-09-12 03:23:04
科技傳播(2012年2期)2012-06-13 10:03:26
