數(shù)據(jù)簡(jiǎn)化中的邊界提取方法

趙偉玲

(黑龍江科技大學(xué) 現(xiàn)代制造工程中心, 哈爾濱 150022)

?

數(shù)據(jù)簡(jiǎn)化中的邊界提取方法

趙偉玲

(黑龍江科技大學(xué) 現(xiàn)代制造工程中心, 哈爾濱 150022)

針對(duì)三維點(diǎn)云數(shù)據(jù)簡(jiǎn)化過(guò)程中邊界特征容易丟失問(wèn)題,研究了一種點(diǎn)云邊界特征提取方法。首先，對(duì)點(diǎn)的k近鄰進(jìn)行查找,并進(jìn)行點(diǎn)的球擬合計(jì)算,得到擬合球的半徑、點(diǎn)的曲率、點(diǎn)到球心距離。其次,通過(guò)數(shù)據(jù)點(diǎn)周圍點(diǎn)的分布均勻性、自適應(yīng)調(diào)節(jié)參數(shù)公式中的閾值,可以達(dá)到檢測(cè)邊界特征的目的。由不同模型的實(shí)驗(yàn)數(shù)據(jù)表明,該算法提取的邊界滿足了后期數(shù)據(jù)簡(jiǎn)化所需。

逆向工程; 點(diǎn)云數(shù)據(jù); 曲率; 邊界提取

0　引　言

隨著產(chǎn)品數(shù)字化和快速制造技術(shù)的發(fā)展,逆向工程得到了越來(lái)越多的應(yīng)用和研究,其各環(huán)節(jié)的智能化及自動(dòng)化一直是這一領(lǐng)域的目標(biāo)。產(chǎn)品逆向工程設(shè)計(jì)的初期,通過(guò)非接觸式三維設(shè)備測(cè)量可得到點(diǎn)云數(shù)據(jù)。邊界特征是表達(dá)點(diǎn)云幾何特征的重要因素之一,在后續(xù)的數(shù)據(jù)處理中對(duì)建模的質(zhì)量和精度具有重要作用。三維點(diǎn)云數(shù)據(jù)簡(jiǎn)化過(guò)程中邊界特征容易丟失問(wèn)題,快速?gòu)碾x散點(diǎn)云信息中提取出邊界,成為基于點(diǎn)云的逆向工程建模研究的核心之一。

目前,國(guó)內(nèi)外有很多學(xué)者對(duì)測(cè)量數(shù)據(jù)的邊界特征識(shí)別進(jìn)行了研究。張獻(xiàn)穎等[1]通過(guò)建立點(diǎn)云的三角網(wǎng)格模型提取點(diǎn)云邊界特征。該算法邊界特征提取準(zhǔn)確,但耗費(fèi)大量的系統(tǒng)資源,運(yùn)行速度慢。胡鑫等[2]采用圖像處理中的梯度求解法來(lái)估算數(shù)據(jù)點(diǎn)的法矢和曲率,通過(guò)閾值法得到候選邊界點(diǎn),再利用曲率極值法得到最終邊界點(diǎn),擬合最終邊界點(diǎn)得到邊界曲線。賀美芳等[3]用局部基面參數(shù)化方法求出曲率極值點(diǎn)并從中提取邊界點(diǎn)，王宏濤等[4]提出了采用八叉樹(shù)劃分點(diǎn)云空間保留葉節(jié)點(diǎn)中距離重心最近點(diǎn)的方法,陳義仁等[5]利用雙向最近點(diǎn)搜索算法對(duì)提取出來(lái)的特征點(diǎn)進(jìn)行排序并自動(dòng)生成邊界曲線,錢錦鋒等[6]由數(shù)據(jù)點(diǎn)及周圍點(diǎn)的分布均勻性進(jìn)行邊界提取。筆者在此基礎(chǔ)上,改進(jìn)了一種點(diǎn)云邊界提取方法。

1　數(shù)據(jù)預(yù)處理

1.1k近鄰搜索

在數(shù)據(jù)預(yù)處理中,搜索數(shù)據(jù)點(diǎn)集中每個(gè)點(diǎn)的k近鄰幾乎是一項(xiàng)最基本的工作。這是因?yàn)闇y(cè)量得到的散亂數(shù)據(jù)只包含數(shù)據(jù)點(diǎn)的三維坐標(biāo)值,點(diǎn)與點(diǎn)之間沒(méi)有明顯的幾何分布信息,都呈散亂無(wú)序狀態(tài),因此必須建立數(shù)據(jù)點(diǎn)之間的空間拓?fù)潢P(guān)系進(jìn)而搜索每個(gè)點(diǎn)的k近鄰。散亂數(shù)據(jù)點(diǎn)k近鄰的建立能夠極大地簡(jiǎn)化散亂點(diǎn)云數(shù)據(jù)后期處理過(guò)程的計(jì)算復(fù)雜度,降低其計(jì)算量,并提高重建結(jié)果的精度和可靠性。目前常用的k近鄰計(jì)算方法有空間單元格法、八叉樹(shù)法和k-d樹(shù)法。這里選擇采用空間單元格法[7-8]。多組實(shí)驗(yàn)及經(jīng)驗(yàn)表明,一般k值取10～30之間是一個(gè)較好的選擇。

1.2基于球面擬合計(jì)算

三維測(cè)量數(shù)據(jù)在小范圍內(nèi)理想意義上所在的曲面應(yīng)該是很光滑的,所以任何點(diǎn)的局部鄰域都可以用平面或者曲面進(jìn)行很好的擬合。這里，采用球擬合的方法對(duì)點(diǎn)的k個(gè)鄰域點(diǎn)進(jìn)行擬合,可以很簡(jiǎn)便得到點(diǎn)的曲率值,為邊界提取做必備準(zhǔn)備工作。

點(diǎn)p的距離最近k個(gè)點(diǎn)Pi(xi,yi,zi)(i=1,2,3,…,k)稱為p的k-近鄰,通過(guò)點(diǎn)p及其k個(gè)近鄰點(diǎn),利用最小二乘法擬合便可以得到球心坐標(biāo)和球半徑r,則點(diǎn)的曲率為1/r。

首先計(jì)算

(1)

(2)

接著求取矩陣的廣義逆矩陣M-1,及F=M-1·N,假設(shè)求出的F=[f(0)f(1)f(2)f(3)]T,則

(3)

2　點(diǎn)云邊界提取方法

在數(shù)據(jù)點(diǎn)及周圍點(diǎn)的分布均勻性提取邊界算法基礎(chǔ)上,提出了一種基于曲率的點(diǎn)云邊界特征提取算法。該算法根據(jù)曲率能反映邊界特征,較好的保持原有模型的邊界信息[9]。

首先,進(jìn)行點(diǎn)p的k近鄰角度標(biāo)準(zhǔn)差計(jì)算,得到點(diǎn)云的外邊界。然后,根據(jù)點(diǎn)的曲率以及點(diǎn)離擬合球面的距離綜合參數(shù)補(bǔ)充得到點(diǎn)云邊界點(diǎn)。圖1是點(diǎn)p所在擬合球面及其距離示意圖,d是點(diǎn)p(xp,yp,zp)到擬合球心O(x0,y0,z0)的距離,r是擬合球半徑,點(diǎn)p的曲率則用1/r表示,點(diǎn)p到擬合球的距離為b=d-r。

圖1　點(diǎn)的球擬合距離

通過(guò)點(diǎn)p的k個(gè)鄰域點(diǎn),根據(jù)球擬合方法可以很容易得到球心O坐標(biāo)及半徑r的大小。這樣,得到點(diǎn)p到球心O的距離為

(4)

(5)

其中,α為系數(shù)。通過(guò)調(diào)節(jié)系數(shù)α可以改變函數(shù)值。λ越大,則說(shuō)明點(diǎn)成為邊界的可能性越大。

擬合球的半徑反映了被測(cè)物形狀的起伏程度。通過(guò)曲率值的不同對(duì)點(diǎn)云進(jìn)行分片處理,分片的數(shù)目可根據(jù)曲率的變化量采用自適應(yīng)法。通過(guò)文中函數(shù)與設(shè)定閾值的比較、距離d與k近鄰點(diǎn)到圓心的平均距離比較,可以找到并提取出邊界點(diǎn)。

3　實(shí)驗(yàn)結(jié)果與分析

3.1某加工件的邊界提取分析

使用自主研發(fā)設(shè)備進(jìn)行非接觸式三維測(cè)量,點(diǎn)的個(gè)數(shù)是211 134個(gè)。圖2是某加工件的點(diǎn)云數(shù)據(jù)及特征提取顯示效果圖。其中,圖2a是由自主研發(fā)的三維掃描系統(tǒng)測(cè)量某加工件所得到的點(diǎn)云數(shù)據(jù)顯示效果圖,圖2b是點(diǎn)云數(shù)據(jù)經(jīng)過(guò)文獻(xiàn)[6]邊界提取的顯示效果圖,圖2c是點(diǎn)云數(shù)據(jù)經(jīng)過(guò)文中方法處理后得到的特征提取效果圖。從顯示效果可以看出,圖2b中的中間軸位置提取的圓形特征不全面,而且四周有的扇形也提取不完整,但是在圖2c中可以看出,這些問(wèn)題都不存在。該方法很好地實(shí)現(xiàn)了某加工件的特征提取,為后續(xù)的點(diǎn)云簡(jiǎn)化等數(shù)據(jù)處理提供了很好的依據(jù)。

圖2　某加工件的點(diǎn)云數(shù)據(jù)及特征提取顯示效果

3.2米老鼠頭像的邊界提取分析

這里使用的是米老鼠頭像模型的點(diǎn)云數(shù)據(jù)。圖3a是米老鼠半個(gè)頭像的點(diǎn)云數(shù)據(jù)顯示效果圖,圖3b是點(diǎn)云數(shù)據(jù)經(jīng)過(guò)文獻(xiàn)6得到的邊界特征顯示效果圖,圖3c是點(diǎn)云數(shù)據(jù)經(jīng)過(guò)文中方法處理后得到的特征提取效果圖。比較圖3a和3b,圖3a中米老鼠的鼻子、嘴巴等一些重要部位的特征利用文獻(xiàn)[6]沒(méi)能提取出來(lái);比較圖3b和圖3c看出,圖3c比圖3b多了鼻子、嘴巴、眼睛等重要部位,而圖3c中這些特征正好可以把米老鼠的重要特征很好地顯示出來(lái)。所以，文中方法實(shí)現(xiàn)了對(duì)米老鼠頭像的點(diǎn)云數(shù)據(jù)特征提取,為數(shù)據(jù)簡(jiǎn)化所需邊界可進(jìn)行直接有效的提取。

圖3　米老鼠頭像的點(diǎn)云數(shù)據(jù)及特征提取顯示效果

4　結(jié)束語(yǔ)

研究了一種點(diǎn)云邊界特征提取方法,首先對(duì)所有點(diǎn)的近鄰搜索,并計(jì)算k近鄰點(diǎn)的球面擬合,得到球半徑、點(diǎn)曲率、點(diǎn)到球心距離等基本參數(shù)。然后,通過(guò)k近鄰點(diǎn)的分布均勻性及自適應(yīng)調(diào)節(jié)參數(shù)公式中的閾值,便可檢測(cè)出點(diǎn)云數(shù)據(jù)的邊界特征。同時(shí),通過(guò)對(duì)某加工件和米老鼠的數(shù)據(jù)實(shí)例進(jìn)行實(shí)驗(yàn)分析,驗(yàn)證該算法的可操作性。該算法提取的邊界雖然還存在遺漏和誤判的情況,但是總體來(lái)說(shuō)該算法在保證數(shù)據(jù)簡(jiǎn)化所需邊界的前提下,能夠?qū)c(diǎn)云數(shù)據(jù)進(jìn)行直接有效的邊界提取。

[1]張獻(xiàn)穎, 周明全, 耿國(guó)華. 空間三角網(wǎng)格曲面的邊界提取方法[J]. 中國(guó)圖像圖形學(xué)報(bào), 2003, 8(10): 1223-1226.

[2]胡鑫, 習(xí)俊通, 金燁. 基于圖像法的點(diǎn)云數(shù)據(jù)邊界自動(dòng)提取[J]. 上海交通大學(xué)學(xué)報(bào), 2002, 36(8): 1118-1120.

[3]賀美芳, 周來(lái)水, 朱延娟. 基于局部基面參數(shù)化的點(diǎn)云數(shù)據(jù)邊界自動(dòng)提取[J]. 機(jī)械科學(xué)與技術(shù), 2004, 23(8): 912-

915.

[4]王宏濤, 張麗艷, 杜佶, 等. 測(cè)量點(diǎn)集的簡(jiǎn)化及其隱式曲面重建誤差分析[J]. 中國(guó)圖象圖形學(xué)報(bào), 2007, 12(11): 2114-2118.

[5]陳義仁, 王一賓, 彭張節(jié), 等. 一種改進(jìn)的散亂點(diǎn)云邊界特征點(diǎn)提取算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 26(4): 1-7.

[6]錢錦鋒, 陳志楊, 張三元, 等. 點(diǎn)云數(shù)據(jù)壓縮中的邊界特征檢測(cè)[J]. 中國(guó)圖象圖形學(xué)報(bào), 2005, 10(2): 164-169.

[7]趙偉玲, 謝雪冬, 程俊廷. 保留邊界特征的點(diǎn)云簡(jiǎn)化算法[J]. 黑龍江科技學(xué)院學(xué)報(bào), 2013, 23(1): 83-88.

[8]劉立強(qiáng). 散亂點(diǎn)云數(shù)據(jù)處理相關(guān)算法的研究[D]. 西安: 西北大學(xué), 2010: 37-42.

[9]劉立國(guó). 點(diǎn)云模型的光順去噪研究[D]. 杭州: 浙江大學(xué), 2007: 36-38.

(編輯晁曉筠)

Research of boundary extraction method in data reduction

ZHAO Weiling

(ModernManufactureEngineeringCenter,HeilongjiangUniversityofScience&Technology,Harbin150022,China)

Aimedatpreventingboundaryfeaturelossmorelikelytooccurintheprocessof3Ddatareduction,thispaperhighlightsaboundaryfeatureextractionmethodofpointcloud.Themethodinvolvesfirstlyseekingthekcloseneighborsofthesamplingpoint,andobtainingtheballfittingradius,thepointcurvature,andthedistancebetweenthepointandthecenterofthesphereusingtheball-fittingmethod,whilegetting,andthenachievingtheboundaryfeaturedetection,dependingonthedistributeduniformityoftheclosestneighborsofpointandself-adaptiveadjustmentofthethresholdvalueoftheparameterequation.Theexperimentaldatafromthedifferentmodelsverifytheabilityofthealgorithmtogivetheboundaryadequateforthefollow-updatareduction.

reverseengineering;pointcloud;curvature;boundaryextraction

2013-06-20

國(guó)家自然科學(xué)基金項(xiàng)目(51075128);國(guó)家科技重大專項(xiàng)項(xiàng)目(2010ZX04016-012);博士后研究人員落戶黑龍江科研啟動(dòng)資助金項(xiàng)目(LBH-Q12019)

趙偉玲(1981-),女,河北省保定人,講師,碩士,研究方向:逆向工程、計(jì)算機(jī)視覺(jué)、數(shù)據(jù)處理,E-mail:weilingzhao@126.com。

10.3969/j.issn.1671-0118.2013.05.015

TP391.41

1671-0118(2013)05-0469-03

A