牙頜點云數(shù)據(jù)的顯著性特征提?、?/h1>

2016-02-20 06:52:14陳玲玲譙舟三陳文樂

計算機系統(tǒng)應(yīng)用訂閱 2016年12期 收藏

關(guān)鍵詞：八叉樹精簡特征值

陳玲玲, 楊 玲, 譙舟三, 陳文樂

1(成都信息工程大學 電子工程學院, 成都 610225)2(中國氣象局 大氣探測重點開放實驗室, 成都 610225)

牙頜點云數(shù)據(jù)的顯著性特征提?、?/p>

陳玲玲1,2, 楊 玲1,2, 譙舟三1, 陳文樂1,2

1(成都信息工程大學 電子工程學院, 成都 610225)2(中國氣象局 大氣探測重點開放實驗室, 成都 610225)

隨著激光掃描測量技術(shù)的發(fā)展, 其數(shù)據(jù)測量精度的逐漸增高使得獲取的幾何模型表面點云數(shù)據(jù)的細節(jié)信息越豐富, 能更準確的反應(yīng)物體幾何表面特征, 但如此海量的點云數(shù)據(jù)同時也帶來對應(yīng)的技術(shù)挑戰(zhàn), 海量的點云數(shù)據(jù)在計算機文件存儲、數(shù)據(jù)后期進一步處理以及軟件可視化方面都不方便且效率低下. 本文中的算法首先采用柵格法對點云進行空間劃分及領(lǐng)域關(guān)系的建立, 其次利用局部表面擬合的方法估算點云法向量, 然后利用點云K領(lǐng)域法的向量求解坐標點的顯著性值, 最后根據(jù)顯著性的值構(gòu)建點云八叉樹. 該算法實現(xiàn)了對點云顯著性特征的提取和對點云數(shù)據(jù)量的進一步簡化, 它不僅保留了對點云細節(jié)特征保持方面的優(yōu)勢, 而且在時間效率上得到了提高.

點云數(shù)據(jù); 可視化; 顯著性特征; 三維配準; 網(wǎng)格化重建

目前國內(nèi)外針對點云數(shù)據(jù)集的精簡算法可以分為兩類, 第一: 通過對點云網(wǎng)格化處理后基于網(wǎng)格的精簡算法; 第二: 基于對采集數(shù)據(jù)直接處理的點云精簡方法. 前者方法首先通過對采集數(shù)據(jù)進行網(wǎng)格化三角剖份, 利用四面體模型表面的點、邊和面之間相互關(guān)系拓撲數(shù)據(jù)壓縮方法, 該算法中首先需要對散亂點云進行Delaunay三角剖份, 其整個時間復雜度較高, 算法效率較低. 而后者直接針對數(shù)據(jù)的精簡算法既具有時間復雜度較低等優(yōu)點, 并且操作簡單. 主要有直接隨機采樣精簡、基于包圍盒空間劃分方法、基于均勻網(wǎng)格劃分的隨機抽樣法和基于高斯曲率和主曲率的精簡算法.

2001年LEE KH[1]等人提出利用被測數(shù)據(jù)法向信息, 對采集數(shù)據(jù)空間包圍盒柵格劃分, 在單個空間格中選擇特征點, 從而完成數(shù)據(jù)精簡. 2002年DYN[2]等人提出的基于雙變量適應(yīng)性數(shù)據(jù)精簡算法可以達到與被測物體模型表面接近的效果而高效精簡數(shù)據(jù). 2004年洪軍[3]等人在通過相關(guān)研究基礎(chǔ)上, 提出的同時利用改進型系數(shù)的空間包圍盒法和基于角度-弦高簡化法的合成數(shù)據(jù)精簡算法, 取得較好的數(shù)據(jù)壓縮效果. Pai-Feng Lee等在2006年提出了基于共面標準的八叉樹細分點云簡化算法. 2009年Hao Song[4]通過在對模式識別算法研究基礎(chǔ)上提出的通過構(gòu)造Voronoi圖的全局聚類采樣算法, 能有效地保留了點云中的邊界特征, 去除非邊界數(shù)據(jù)的非特征點, 但該算法容易產(chǎn)生數(shù)據(jù)刪除孔洞, 容易誤刪除部分特征點, 且速度仍有待提高. 史寶權(quán)[5]等人提取了利用模式識別算法原理的基于聚類的點云特征保存數(shù)據(jù)精簡方法. 2009年黃文明[6]等人提出的保留幾何特征的散亂點云簡化方法,在論文特定條件下取得較好的特征提取效果. 張欣[7]等人在2012年提出的基于特征保留的三角形折疊網(wǎng)格簡化算法, 但該算法沒有針對數(shù)據(jù)輪廓特征進行處理, 一定程度上依賴網(wǎng)格劃分結(jié)果. Yitian Zhao在2012年提出基于法向夾角和高斯曲率結(jié)合的點云精簡算法, 通過算法效果驗證得出該算法具有較好的效果. Nira DyT[8]通過構(gòu)造了—個非負度量函數(shù)平均每個數(shù)據(jù)點的權(quán)重分配, 這種算法能夠有效去除非特征點,誤差刪除較小, 但由于反復迭代計算導致其效率較低.

針對上述算法各自的應(yīng)用特點, 本文在研究二維圖像顯著性區(qū)域輪廓檢測算法基礎(chǔ)上引申到點云數(shù)據(jù)特征提取中, 提出一種基于顯著性標準衡量的牙頜點云特征提取精簡算法. 該算法首先采用柵格法對點云進行空間劃分及領(lǐng)域關(guān)系的建立, 其次利用局部表面擬合的方法估算點云法向量, 然后利用點云K領(lǐng)域法的向量求解坐標點的顯著性值, 最后根據(jù)顯著性的值構(gòu)建點云八叉樹, 從而實現(xiàn)對點云顯著性特征的提取,最終做到進一步精簡數(shù)據(jù)量.

1 牙頜點云數(shù)據(jù)法向量計算及顯著性概念

1.1 求解單位法向量

關(guān)于散亂點云的法向量估計[9]方法, 國內(nèi)外研究人員提出相關(guān)的文獻比較多, 同時也提出了多種改進算法, 具體參考表1.

表1 各個法向量估算算法比較

通過對各種算法的分析比較, 本文采用對噪聲、尖銳特征以及外點均能很好處理的局部表面擬合的方法來求解點云法向量, 該算法整體計算步驟如下:

1) 構(gòu)建平面方程

2) 求解約束方程

3) 轉(zhuǎn)化為求解極值問題

1.2 顯著性檢測概念

顯著性檢測主要是對二維圖像[10]的顏色、特征輪廓、數(shù)據(jù)信息代表的梯度以及圖像紋理等屬性進行檢測, 由于其具有強大的圖像信息提取能力, 因此, 顯著性檢測被廣泛地應(yīng)用于彩色與灰度圖像的分割[11]、自適應(yīng)圖像壓縮[11,12]、視頻圖像特征提取[13]以及新興的基于內(nèi)容的圖像檢索等研究領(lǐng)域.

在三維模型中, 零顯著性的區(qū)域為一個球面, 本文中我們用各點法向量之間夾角關(guān)系來表示三維模型中的顯著性, 顯著性較高的區(qū)域, 其各個點的法向量之間夾角會比較大. 而顯著性值較低的區(qū)域, 各相鄰三維數(shù)據(jù)點間的法向量夾角會比較小, 如圖1和圖2,分別展示了特征點、非特征點與相鄰點間法向方向與夾角示意圖. 因此本文通過引入散亂點云數(shù)據(jù)與其K鄰近點間的法向量夾角值作為顯著性度量特征參數(shù),公式如下:

圖1 空間數(shù)據(jù)中特征點與相鄰點法向方向和夾角

圖2 空間數(shù)據(jù)中非特征點與相鄰點法向方向和夾角

對于三維點集M, 設(shè)頂點p的領(lǐng)域N（p,δ）, 其中:

則定義坐標點的高斯平均顯著性為:

以上高斯平均顯著性計算公式中, 假定高斯濾波器的截止頻率為2δ.

1.3 八叉樹法原理

八叉樹作為區(qū)域四叉樹向三維空間的推廣, 用于描述三維空間的樹狀數(shù)據(jù)結(jié)構(gòu), 通過迭代遞歸分割模型點云數(shù)據(jù)空間而實現(xiàn).

算法流程如下：1)首先讀取點云數(shù)據(jù)，構(gòu)造數(shù)據(jù)集的三維空間包圍盒，并依此建立點云拓撲關(guān)系的基礎(chǔ)和模型，并進一步劃分為八個子立方體, 同時將其加入到根節(jié)點的子節(jié)點拓撲結(jié)構(gòu)中. 2)反復迭代第一步, 直到最小子立方體的邊長小于或者等于設(shè)定的閾值, 到此, 將點云數(shù)據(jù)集三維空間已經(jīng)劃分為2的冪次方個子立方體(如圖3中 (b)和(c)展示的八叉樹空間模型建立過程). 如圖3中(a)所示, 在八叉樹三維模型空間劃分流程中, 子立方體拓撲結(jié)構(gòu)的編碼與其所在的空間位置緊密相關(guān).

圖3 八叉樹空間劃分模型及劃分示意圖

2 基于顯著性的牙頜點云數(shù)據(jù)特征提取算法

2.1求解法向量和數(shù)據(jù)預處理

首先將讀取的牙頜點云數(shù)據(jù)采用局部表面擬合的方法求解法向量求解, 然后進行點云數(shù)據(jù)的柵格空間劃分及模型三維鄰域關(guān)系的建立.

1) 根據(jù)讀取的點云數(shù)據(jù), 求解每個坐標軸上最大和最小值, 分別為:xmax,xmin,ymax,ymin,zmax,zmin

2) 根據(jù)1)計算最小包圍盒的大小:

其中N表示所有頂點的個數(shù).

3) 根據(jù)步驟2)得到的最小包圍盒邊長, 計算三個坐標軸上可劃分包圍盒空間的最大個數(shù):

4) 計算每個坐標點在X, Y, Z軸三個坐標的所屬包圍盒序號:

5) 根據(jù)X, Y, Z軸的包圍盒序號計算該點所屬空間包圍盒的BoxID,并存儲計算得到的BoxID與該點的ID為式(12):

圖4 空間包圍盒建立示意圖

2.2 點云顯著性特征值的求解

1) 采用k-d tree算法查找每個點云數(shù)據(jù)的K鄰近點坐標;

2) 利用顯著性計算公式(5)求解該點法向量去K鄰近點法向夾角值, 并計算對應(yīng)高斯平均顯著性值.

2.3 構(gòu)建點云八叉樹模型

構(gòu)建八叉樹模型首先需要初始化八叉樹的根節(jié)點, 然后計算出八叉樹細分的最小節(jié)點長度為

和初始化八叉樹最小的菱長為

根據(jù)構(gòu)建的初始八叉樹, 按照如下的細分準則對樹進行劃分: 初始設(shè)置一個參數(shù)ξ, 計算顯著性變化的標準偏差為:

若δ＜ξ, 則節(jié)點所包含的區(qū)域被忽略為一個點;若δ＞ξ, 則節(jié)點所包含的區(qū)域顯著性特征值大, 需要細分. 上述兩個細分準則能夠根據(jù)某塊固定大小的區(qū)域內(nèi)顯著性的方差而去確定是否繼續(xù)細分. 算法流程圖如圖5 所示.

3 牙頜點云顯著性特征提取算法效果分析

如圖6所示為單顆牙齒點云數(shù)據(jù)及特征提取效果圖, 圖中的紅色點為采用顯著性方法提取的特征點,藍色點為非特征點. 從圖6(b)的法向量結(jié)果來看, 提取出來的顯著性特征值有很多都不是單顆牙齒中實際的顯著性特征值, 其對于顯著特征值提取的準確率很低, 但是從圖6(c)的提取效果圖來看, 對于單顆牙齒的邊緣特征值都已經(jīng)成功提取出來, 并且并沒有提取出多余的非特征值點. 對于圖7的完整牙頜點云顯著性特征值的提取效果來看, 法向量求解提取出來的特征值有很多都是非顯著性特征值, 而圖7(c)中采用顯著性特征提出的較多都是完整牙頜點云數(shù)據(jù)的顯著性特征值. 從圖8中的完整牙頜點云數(shù)據(jù)特征提取局部放大效果對比圖中也可以看出顯著性特征提取出來的特征值更加準確可靠.

圖5 算法總流程圖

圖6 單顆牙齒點云數(shù)據(jù)及特征提取效果

圖7 完整牙頜點云顯著性特征提取效果

圖8 完整牙頜點云特征提取局部放大效果對比圖

如圖9所示, 是對于三顆牙齒點云數(shù)據(jù)提取效果對比圖, (b)是針對顯著性特征提取出來的效果圖, 其中紅色點基本都是分布在三顆牙齒的邊緣位置和輪廓較明顯的位置, (c)是通過高斯曲率特征提取的特征值效果圖, 圖中的紅色點較少, 對于明顯的特征位置都未提取出來, 所以其提取特征的效果很差.

圖9 三顆牙齒點云特征提取效果對比圖

為了驗證此基于顯著性特征提取方法的實用性,利用斯坦福的開放數(shù)據(jù)(大象點云數(shù)據(jù)、兔子點云數(shù)據(jù)、馬點云數(shù)據(jù))進行試驗, 其運行測試效果圖如圖10、11、12所示, 從提取出來的實驗結(jié)果圖中可以看出, 每幅點云數(shù)據(jù)中的邊緣輪廓、圖像紋理等顯著性特征都得到了較好的提取.

圖10 大象點云顯著性特征提取效果

圖11 兔子點云顯著性特征提取效果

圖12 馬點云顯著性特征提取局部放大效果

如表1所示, 通過采用頜部分缺失數(shù)據(jù)和完整牙頜數(shù)據(jù), 單顆牙齒數(shù)據(jù)、三顆牙齒數(shù)據(jù), 以及斯坦福大學開放的點云數(shù)據(jù)做進一步測試, 同時還通過與該點云數(shù)據(jù)的平均曲率特征提取結(jié)果比較, 可以明顯看出本文算法能夠?qū)Ω鞣N數(shù)據(jù)的輪廓特征、圖像紋理進行有效提取, 并且其時間效率是基于曲率特征提取算法的10%左右.

表1 特征提取算法時間對比分析

4 結(jié)語

本文提出一種新的基于顯著性牙頜點云特征提取的方法, 該方法利用法向量作為衡量三維點云模型顯著性特征的標準, 直接對點云數(shù)據(jù)進行顯著性特征的提取. 通過基礎(chǔ)性研究分析, 使用數(shù)據(jù)點單位法向量與K鄰近點的單位法向量的點積均值構(gòu)建高斯平均顯著性參量, 替代以曲率作為該點所在三維模型局部曲面的彎曲程度或者輪廓是否明顯的數(shù)值表示, 避免了曲率估算過程中引起的較高時間復雜度, 同時利用采集的單顆牙齒、三顆牙齒以及牙頜部分缺失數(shù)據(jù)和完整牙頜數(shù)據(jù)進行驗證分析, 利用斯坦福大學開放點云數(shù)據(jù)做進一步測試, 并和曲率特征提取等算法進行對比, 均取得較好效果. 算法不僅保留了對點云細節(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ù)研究.西安交通大學學報,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 史寶全,梁晉,張曉強,等.特征保持的點云精簡技術(shù)研究.西安交通大學學報,2010,44(11):37–40.

6 黃文明,肖朝霞.保留邊界的點云簡化方法.計算機應(yīng)用, 2010,30(2):348.

7 張欣,秦茂玲,謝堂龍.基于特征保持的三角形折疊網(wǎng)格簡化算法.計算機技術(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 李寶,程志.三維點云法向量估計綜述.計算機工程與應(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

猜你喜歡

八叉樹精簡特征值

三維十字鏈表八叉樹的高效檢索實現(xiàn)

棗莊學院學報(2022年5期)2022-09-21 09:35:22

一類帶強制位勢的p-Laplace特征值問題

數(shù)學物理學報(2021年5期)2021-11-19 07:01:12

單圈圖關(guān)聯(lián)矩陣的特征值

煙臺大學學報(自然科學與工程版)(2021年1期)2021-03-19 08:38:40

時常精簡多余物品

特別健康(2018年2期)2018-06-29 06:14:00

一種面向應(yīng)用的流量監(jiān)測精簡架構(gòu)設(shè)計

電子制作(2017年17期)2017-12-18 06:40:47

基于商奇異值分解的一類二次特征值反問題

東北電力大學學報(2015年1期)2015-11-13 05:20:25

關(guān)于兩個M-矩陣Hadamard積的特征值的新估計

四川輕化工大學學報(自然科學版)(2014年3期)2014-04-16 03:56:42

應(yīng)用于SAN的自動精簡配置架構(gòu)設(shè)計與實現(xiàn)

計算機工程(2014年6期)2014-02-28 01:25:08

散亂點云線性八叉樹結(jié)構(gòu)在GPU中的實現(xiàn)

機械設(shè)計與制造工程(2013年4期)2013-09-12 03:23:04

基于密集型區(qū)域的八叉樹劃分算法

科技傳播(2012年2期)2012-06-13 10:03:26

計算機系統(tǒng)應(yīng)用2016年12期

計算機系統(tǒng)應(yīng)用的其它文章

面向?qū)嶓w邊界模型的設(shè)計特征重構(gòu)①

基于多示例多標記的抽油機故障診斷①

多租戶高可用并行任務(wù)調(diào)度框架①

安全高效的移動終端數(shù)字簽名方案①

跨平臺技術(shù)在礦山監(jiān)測系統(tǒng)中的研究與應(yīng)用①

基于C++的動態(tài)內(nèi)存實時監(jiān)測器①