陳玲玲, 楊 玲, 譙舟三, 陳文樂(lè)

1(成都信息工程大學(xué) 電子工程學(xué)院, 成都 610225)2(中國(guó)氣象局 大氣探測(cè)重點(diǎn)開(kāi)放實(shí)驗(yàn)室, 成都 610225)

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

陳玲玲1,2, 楊 玲1,2, 譙舟三1, 陳文樂(lè)1,2

1(成都信息工程大學(xué) 電子工程學(xué)院, 成都 610225)2(中國(guó)氣象局 大氣探測(cè)重點(diǎn)開(kāi)放實(shí)驗(yàn)室, 成都 610225)

隨著激光掃描測(cè)量技術(shù)的發(fā)展, 其數(shù)據(jù)測(cè)量精度的逐漸增高使得獲取的幾何模型表面點(diǎn)云數(shù)據(jù)的細(xì)節(jié)信息越豐富, 能更準(zhǔn)確的反應(yīng)物體幾何表面特征, 但如此海量的點(diǎn)云數(shù)據(jù)同時(shí)也帶來(lái)對(duì)應(yīng)的技術(shù)挑戰(zhàn), 海量的點(diǎn)云數(shù)據(jù)在計(jì)算機(jī)文件存儲(chǔ)、數(shù)據(jù)后期進(jìn)一步處理以及軟件可視化方面都不方便且效率低下. 本文中的算法首先采用柵格法對(duì)點(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ù). 該算法實(shí)現(xiàn)了對(duì)點(diǎn)云顯著性特征的提取和對(duì)點(diǎn)云數(shù)據(jù)量的進(jìn)一步簡(jiǎn)化, 它不僅保留了對(duì)點(diǎn)云細(xì)節(jié)特征保持方面的優(yōu)勢(shì), 而且在時(shí)間效率上得到了提高.

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

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

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

針對(duì)上述算法各自的應(yīng)用特點(diǎn), 本文在研究二維圖像顯著性區(qū)域輪廓檢測(cè)算法基礎(chǔ)上引申到點(diǎn)云數(shù)據(jù)特征提取中, 提出一種基于顯著性標(biāo)準(zhǔn)衡量的牙頜點(diǎn)云特征提取精簡(jiǎn)算法. 該算法首先采用柵格法對(duì)點(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ù), 從而實(shí)現(xiàn)對(duì)點(diǎn)云顯著性特征的提取,最終做到進(jìn)一步精簡(jiǎn)數(shù)據(jù)量.

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

1.1 求解單位法向量

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

表1 各個(gè)法向量估算算法比較

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

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

2) 求解約束方程

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

1.2 顯著性檢測(cè)概念

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

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

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

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

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

則定義坐標(biāo)點(diǎn)的高斯平均顯著性為:

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

1.3 八叉樹(shù)法原理

八叉樹(shù)作為區(qū)域四叉樹(shù)向三維空間的推廣, 用于描述三維空間的樹(shù)狀數(shù)據(jù)結(jié)構(gòu), 通過(guò)迭代遞歸分割模型點(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)一步劃分為八個(gè)子立方體, 同時(shí)將其加入到根節(jié)點(diǎn)的子節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)中. 2)反復(fù)迭代第一步, 直到最小子立方體的邊長(zhǎng)小于或者等于設(shè)定的閾值, 到此, 將點(diǎn)云數(shù)據(jù)集三維空間已經(jīng)劃分為2的冪次方個(gè)子立方體(如圖3中 (b)和(c)展示的八叉樹(shù)空間模型建立過(guò)程). 如圖3中(a)所示, 在八叉樹(shù)三維模型空間劃分流程中, 子立方體拓?fù)浣Y(jié)構(gòu)的編碼與其所在的空間位置緊密相關(guān).

圖3 八叉樹(shù)空間劃分模型及劃分示意圖

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ù), 求解每個(gè)坐標(biāo)軸上最大和最小值, 分別為:xmax,xmin,ymax,ymin,zmax,zmin

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

其中N表示所有頂點(diǎn)的個(gè)數(shù).

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

4) 計(jì)算每個(gè)坐標(biāo)點(diǎn)在X, Y, Z軸三個(gè)坐標(biāo)的所屬包圍盒序號(hào):

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

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

2.2 點(diǎn)云顯著性特征值的求解

1) 采用k-d tree算法查找每個(gè)點(diǎn)云數(shù)據(jù)的K鄰近點(diǎn)坐標(biāo);

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

2.3 構(gòu)建點(diǎn)云八叉樹(shù)模型

構(gòu)建八叉樹(shù)模型首先需要初始化八叉樹(shù)的根節(jié)點(diǎn), 然后計(jì)算出八叉樹(shù)細(xì)分的最小節(jié)點(diǎn)長(zhǎng)度為

和初始化八叉樹(shù)最小的菱長(zhǎng)為

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

若δ＜ξ, 則節(jié)點(diǎn)所包含的區(qū)域被忽略為一個(gè)點(diǎn);若δ＞ξ, 則節(jié)點(diǎn)所包含的區(qū)域顯著性特征值大, 需要細(xì)分. 上述兩個(gè)細(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é)果來(lái)看, 提取出來(lái)的顯著性特征值有很多都不是單顆牙齒中實(shí)際的顯著性特征值, 其對(duì)于顯著特征值提取的準(zhǔn)確率很低, 但是從圖6(c)的提取效果圖來(lái)看, 對(duì)于單顆牙齒的邊緣特征值都已經(jīng)成功提取出來(lái), 并且并沒(méi)有提取出多余的非特征值點(diǎn). 對(duì)于圖7的完整牙頜點(diǎn)云顯著性特征值的提取效果來(lái)看, 法向量求解提取出來(lái)的特征值有很多都是非顯著性特征值, 而圖7(c)中采用顯著性特征提出的較多都是完整牙頜點(diǎn)云數(shù)據(jù)的顯著性特征值. 從圖8中的完整牙頜點(diǎn)云數(shù)據(jù)特征提取局部放大效果對(duì)比圖中也可以看出顯著性特征提取出來(lái)的特征值更加準(zhǔn)確可靠.

圖5 算法總流程圖

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

圖7 完整牙頜點(diǎn)云顯著性特征提取效果

圖8 完整牙頜點(diǎn)云特征提取局部放大效果對(duì)比圖

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

圖9 三顆牙齒點(diǎn)云特征提取效果對(duì)比圖

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

圖10 大象點(diǎn)云顯著性特征提取效果

圖11 兔子點(diǎn)云顯著性特征提取效果

圖12 馬點(diǎn)云顯著性特征提取局部放大效果

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

表1 特征提取算法時(shí)間對(duì)比分析

4 結(jié)語(yǔ)

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

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 洪軍,丁玉成,曹亮,等.逆向工程中的測(cè)量數(shù)據(jù)精簡(jiǎn)技術(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)云精簡(jiǎn)技術(shù)研究.西安交通大學(xué)學(xué)報(bào),2010,44(11):37–40.

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

7 張欣,秦茂玲,謝堂龍.基于特征保持的三角形折疊網(wǎng)格簡(jiǎn)化算法.計(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;收到修改稿時(shí)間:2016-07-14

10.15888/j.cnki.csa.005625