牙頜點云數據的顯著性特征提取①

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

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

牙頜點云數據的顯著性特征提取①

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

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

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

點云數據; 可視化; 顯著性特征; 三維配準; 網格化重建

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

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

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

1 牙頜點云數據法向量計算及顯著性概念

1.1 求解單位法向量

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

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

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

1) 構建平面方程

2) 求解約束方程

3) 轉化為求解極值問題

1.2 顯著性檢測概念

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

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

圖1 空間數據中特征點與相鄰點法向方向和夾角

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

對于三維點集M, 設頂點p的領域N（p,δ）, 其中:

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

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

1.3 八叉樹法原理

八叉樹作為區域四叉樹向三維空間的推廣, 用于描述三維空間的樹狀數據結構, 通過迭代遞歸分割模型點云數據空間而實現.

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

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

2 基于顯著性的牙頜點云數據特征提取算法

2.1求解法向量和數據預處理

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

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

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

其中N表示所有頂點的個數.

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

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

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

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

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

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

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

2.3 構建點云八叉樹模型

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

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

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

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

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

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

圖5 算法總流程圖

圖6 單顆牙齒點云數據及特征提取效果

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

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

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

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

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

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

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

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

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

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

4 結語

本文提出一種新的基于顯著性牙頜點云特征提取的方法, 該方法利用法向量作為衡量三維點云模型顯著性特征的標準, 直接對點云數據進行顯著性特征的提取. 通過基礎性研究分析, 使用數據點單位法向量與K鄰近點的單位法向量的點積均值構建高斯平均顯著性參量, 替代以曲率作為該點所在三維模型局部曲面的彎曲程度或者輪廓是否明顯的數值表示, 避免了曲率估算過程中引起的較高時間復雜度, 同時利用采集的單顆牙齒、三顆牙齒以及牙頜部分缺失數據和完整牙頜數據進行驗證分析, 利用斯坦福大學開放點云數據做進一步測試, 并和曲率特征提取等算法進行對比, 均取得較好效果. 算法不僅保留了對點云細節特征保持方面的優勢, 而且在時間效率上得到了提高.

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 洪軍,丁玉成,曹亮,等.逆向工程中的測量數據精簡技術研究.西安交通大學學報,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 史寶全,梁晉,張曉強,等.特征保持的點云精簡技術研究.西安交通大學學報,2010,44(11):37–40.

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

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