高斯函數(shù)約束下的多判別參數(shù)散亂點(diǎn)云邊緣檢測(cè)

楊文橋， 鄭力新， 朱建清， 董進(jìn)華， 鄭義姚， 劉穎， 汪泰伸

(1. 華僑大學(xué) 工學(xué)院， 福建 泉州 362021； 2. 華僑大學(xué) 工業(yè)智能化與系統(tǒng)福建省高校工程研究中心， 福建 泉州 362021)

邊緣檢測(cè)最先是針對(duì)二維數(shù)字圖像提出的，目的是對(duì)圖像特性發(fā)生變化的位置進(jìn)行識(shí)別與檢測(cè)[1].作為圖像分析和計(jì)算機(jī)視覺的重要研究領(lǐng)域，邊緣檢測(cè)受到眾多學(xué)者的關(guān)注，現(xiàn)已發(fā)展出多種成熟的邊緣檢測(cè)算法.隨著三維激光與計(jì)算機(jī)技術(shù)的發(fā)展，人們更多地通過激光技術(shù)獲取目標(biāo)的三維點(diǎn)云數(shù)據(jù)，得到更好的現(xiàn)實(shí)空間特征.點(diǎn)云的幾何特征主要體現(xiàn)為掃描物體的點(diǎn)、線、面、體[2]，這些特征在點(diǎn)云精簡(jiǎn)、點(diǎn)云配準(zhǔn)、點(diǎn)云分割等方面具有重要的意義.

不同點(diǎn)云數(shù)據(jù)模型的邊緣特征提取方式也不相同，大致可分為基于網(wǎng)格和基于散亂點(diǎn)云的特征提取方式[3-4].基于網(wǎng)格的特征提取先將點(diǎn)云進(jìn)行網(wǎng)格化處理，通過遍歷三角化后的點(diǎn)云及閾值約束，最終獲得點(diǎn)云的邊緣特征.其中，最著名的三角剖分(delaunay)算法形成的三角網(wǎng)絡(luò)簡(jiǎn)潔、直觀，但在三角化的過程中，需要評(píng)估點(diǎn)云之間的歐氏距離，如果歐氏距離選擇不合適，將會(huì)產(chǎn)生孔洞.此外，該方法若應(yīng)用于三維點(diǎn)云，需要使用每個(gè)點(diǎn)云的法向確定投影方向，故該算法更適用于均勻、平滑的點(diǎn)云[5].基于散亂點(diǎn)云的特征提取主要從該類型的點(diǎn)云中提取一定規(guī)律的點(diǎn)、線、面等特征，所以更加注重局部特征.Song等[6]將點(diǎn)云每一點(diǎn)的向量與k鄰近點(diǎn)的向量做均方根，以此作為提取邊緣特征的標(biāo)準(zhǔn)，這種方法雖然很好地體現(xiàn)了點(diǎn)云的每個(gè)點(diǎn)與其鄰近點(diǎn)法向之間的關(guān)系，但在邊緣提取的結(jié)果中會(huì)檢查出邊緣鄰近的非邊緣點(diǎn).Han等[7]利用邊界點(diǎn)法向異于非邊界法向的特點(diǎn)保留邊緣特征，但得到的邊緣與非邊緣部分密度相同.陳龍等[8]提出多參數(shù)約束的特征提取算法，通過法向、曲率及歐式距離判斷特征點(diǎn).文獻(xiàn)[9-10]采用主成分分析(PCA)和法向提取邊緣特征點(diǎn).基于此，本文提出一種基于高斯函數(shù)的多判別參數(shù)散亂點(diǎn)云邊緣檢測(cè)算法.

1 算法原理及方法

散亂點(diǎn)云邊緣特征提取是以點(diǎn)云數(shù)據(jù)各點(diǎn)法向、曲率及k近鄰歐式距離為基礎(chǔ)，在高斯函數(shù)的約束下提取邊緣信息，具體有以下3個(gè)步驟.

步驟1定義散亂點(diǎn)云數(shù)據(jù)P={pi(xi,yi,zi)|i=1,2,…,N}，構(gòu)建點(diǎn)云拓?fù)浣Y(jié)構(gòu).

步驟2定義基于k近鄰計(jì)算樣點(diǎn)pi的曲率為Ci,該點(diǎn)與k近鄰重心的距離為di，該點(diǎn)與k近鄰點(diǎn)的最遠(yuǎn)距離為dmax，該點(diǎn)與k近鄰各點(diǎn)單位距離夾角均值為θi.

圖1 散亂點(diǎn)云邊緣特征提取流程圖Fig.1 Flowchart of edge feature extraction of scattered point clouds

步驟3根據(jù)以上4個(gè)參數(shù)定義樣點(diǎn)特征參數(shù)wi，結(jié)合高斯函數(shù)定義單側(cè)σ原則的特征判別閾值W+σ，通過比較點(diǎn)云每點(diǎn)的特征參數(shù)與特征判別閾值的大小，最終確定特征點(diǎn).

散亂點(diǎn)云邊緣特征提取流程圖，如圖1所示.

1.1 點(diǎn)云拓?fù)潢P(guān)系的建立

通過三維測(cè)量設(shè)備獲取的點(diǎn)云數(shù)據(jù)數(shù)量大、分布不均勻，不具有實(shí)體網(wǎng)格下的幾何拓?fù)潢P(guān)系，所以在提取點(diǎn)云邊緣特征前，需要有序地組織點(diǎn)云，以便查詢每個(gè)點(diǎn)的k近鄰.搜索k近鄰主要有八叉樹、k-d樹及空間網(wǎng)格[11]等3種方法.空間網(wǎng)格法的算法簡(jiǎn)單，但不適用于非均勻點(diǎn)云；八叉樹[4,12]和k-d樹[4]采用的空間索引方式是自頂向下逐級(jí)劃分的，但八叉樹結(jié)構(gòu)在搜索過程中會(huì)出現(xiàn)冗余，對(duì)于數(shù)量較多的點(diǎn)云，占用的存儲(chǔ)空間較大，而k-d樹不會(huì)浪費(fèi)空間，搜索時(shí)間相對(duì)較少，且不受點(diǎn)云密度的影響.因此，采用k-d樹建立點(diǎn)云數(shù)據(jù)之間的拓?fù)浣Y(jié)構(gòu).

1.2 特征判別參數(shù)的建立

在前人研究[13-16]的基礎(chǔ)上，提出基于高斯函數(shù)的多判別參數(shù)散亂點(diǎn)云邊緣檢測(cè)算法(文中算法)，該算法利用樣點(diǎn)pi(i=1,2，…,N)的相關(guān)曲率、法向、重心及密度等，綜合判斷其是否為特征點(diǎn).pi和鄰近點(diǎn)的夾角及該點(diǎn)的曲率反映其周圍曲面彎曲的程度；pi到該點(diǎn)領(lǐng)域重心的距離反映該點(diǎn)在k近鄰區(qū)域內(nèi)的相對(duì)位置；pi與k近鄰點(diǎn)之間的距離反映其周圍點(diǎn)云的密度.

1.2.1 法向及曲率的估計(jì) 選擇基于局部表面擬合方法[17]對(duì)點(diǎn)云法向進(jìn)行估計(jì).基于局部表面擬合方法是對(duì)點(diǎn)云中的每一個(gè)點(diǎn)pi(i=1,2，…,N)，獲取與其最近鄰的k個(gè)點(diǎn)，利用這些點(diǎn)，通過最小二乘法擬合一個(gè)局部平面，使該平面最佳擬合數(shù)據(jù)，方法簡(jiǎn)單快速，且可以求解曲率.

對(duì)點(diǎn)pi(i=1,2，…,N)擬合的平面表達(dá)式為

Ax+By+Cz=D

.

(1)

式(1)中：A,B,C分別為平面方程的系數(shù)；x,y,z為坐標(biāo)軸；D為常量.

(2)

將目標(biāo)函數(shù)轉(zhuǎn)化為求解對(duì)應(yīng)的對(duì)稱半正定矩陣M的特征值，M也被稱為協(xié)方差矩陣，其表達(dá)式為

(3)

通過PCA方法求解矩陣M，得到M的3個(gè)特征值λ0，λ1，λ2.若λ0≥λ1≥λ2，則λ2對(duì)應(yīng)的特征向量ni為點(diǎn)pi的法向.此時(shí)，曲率Ci可表示為

Ci=λ2/(λ0+λ1+λ2)

.

(4)

定義pi的k鄰近點(diǎn)mj(j=1,2，…，k)的法向?yàn)閚i,j(j=1,2，…，k)，則該點(diǎn)k近鄰?qiáng)A角的均值為

(5)

當(dāng)點(diǎn)云密度不均勻時(shí)，在k近鄰范圍內(nèi),可能出現(xiàn)間隔較遠(yuǎn)，但當(dāng)夾角較大的情況，為避免誤判[18]，使用兩點(diǎn)的歐式距離作為特征識(shí)別的權(quán)值，以降低距離對(duì)特征識(shí)別的影響，則法向夾角均值公式可改為

(6)

式(6)中：di,j為點(diǎn)pi與第j個(gè)k近鄰點(diǎn)的歐式距離.

由Ci，θi的表達(dá)式可知：當(dāng)Ci越大時(shí)，pi為特征點(diǎn)的可能性越大；同理，當(dāng)θi越大時(shí)，pi所在的曲面就越尖銳.

1.2.2pi到k近鄰重心的距離與k近鄰的最遠(yuǎn)距離 點(diǎn)云邊界是曲面模型的重要特征，但在點(diǎn)云獲取的過程中，由于物體表面的特點(diǎn)，如反射、局部不遮擋等，導(dǎo)致獲取的模型數(shù)據(jù)局部丟失，最終點(diǎn)云可視化中會(huì)出現(xiàn)孔洞[19].目前，國(guó)內(nèi)外學(xué)者已針對(duì)邊界檢測(cè)進(jìn)行了大量的研究.文獻(xiàn)[20]利用pi鄰域內(nèi)的三維位置梯度幾何信息，在鄰域點(diǎn)構(gòu)成的梯度協(xié)方差下，判斷邊界點(diǎn)，但該方法不適合散亂點(diǎn)云.文獻(xiàn)[21]根據(jù)pi到重心的距離與樣點(diǎn)到最遠(yuǎn)距離的比值識(shí)別邊界點(diǎn)，這種方法對(duì)平滑邊界點(diǎn)識(shí)別效果較好，但對(duì)尖銳點(diǎn)的識(shí)別效果不佳.為解決這一問題，可將曲率與法向作為點(diǎn)云邊界特征提取的依據(jù)，以其為尖銳曲面邊界點(diǎn)提取的主導(dǎo)因素，并以文獻(xiàn)[21]方法作為識(shí)別平滑邊界的因素.

定義點(diǎn)pi的k鄰近重心οi為

(7)

點(diǎn)pi到k近鄰重心的距離di為

di=‖pi-οi‖

.

(8)

點(diǎn)pi與k近鄰的最遠(yuǎn)距離dmax為

dmax=max{di,j|j=1,2,…,k}.

(9)

1.3 特征點(diǎn)的提取

基于單位距離法向夾角的準(zhǔn)則可以很好地弱化非均勻點(diǎn)對(duì)判別結(jié)果的影響；基于曲率的準(zhǔn)則可以提取尖銳邊緣特征；基于樣點(diǎn)pi到重心的距離與k近鄰最遠(yuǎn)點(diǎn)距離的比值可以保留平滑邊界.綜合以上優(yōu)點(diǎn)，通過加權(quán)算法將3種判定準(zhǔn)則應(yīng)用于特征點(diǎn)的判定中，以獲得更好的特征點(diǎn)提取效果.

通過獲取點(diǎn)云數(shù)據(jù)中任一點(diǎn)pi的曲率Ci、該點(diǎn)單位距離k近鄰?qiáng)A角均值θi、樣點(diǎn)pi到k近鄰重心的距離di及最遠(yuǎn)距離dmax，計(jì)算數(shù)據(jù)點(diǎn)的判別參數(shù)wi為

(10)

式(10)中：α為曲率控制系數(shù)；β為法向夾角控制系數(shù)；γ為點(diǎn)pi的k近鄰重心控制系數(shù).

整個(gè)點(diǎn)云數(shù)據(jù)的特征閾值W為

(11)

式(11)中：N為點(diǎn)云數(shù)據(jù)量；η為點(diǎn)云特征點(diǎn)數(shù)控制系數(shù)(一般取值為1).

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

文中算法的硬件平臺(tái)為Inter(R) Core(TM) i5-7300HQ 2.5 GHz，16 G內(nèi)存；操作系統(tǒng)為Win 10；軟件環(huán)境為Visual Studio 2017；開發(fā)語(yǔ)言為C++；測(cè)試數(shù)據(jù)為斯坦福大學(xué)modelnet40_normal_resampled圖片庫(kù)中的airplane模型、chair模型和bunny模型.從邊緣檢測(cè)效果、特征點(diǎn)保留數(shù)量和運(yùn)行時(shí)間等3個(gè)方面，分別使用文中算法、法向算法、曲率算法、文獻(xiàn)[8]算法及文獻(xiàn)[18]算法對(duì)3種模型進(jìn)行算法對(duì)比.

2.1 數(shù)據(jù)說明

airplane模型和chair模型的點(diǎn)云數(shù)量為10 000點(diǎn)，bunny模型的點(diǎn)云數(shù)量為35 946點(diǎn).3種原始模型，如圖2所示.

(a) airplane模型 (b) chair模型 (c) bunny模型圖2 3種原始模型Fig.2 Three original models

airplane模型具有閉合特征(如機(jī)身)及非閉合特征(如螺旋槳)，點(diǎn)云密度不均勻，此外，還具有尖銳棱線一樣的特征.airplane模型由于本身特征強(qiáng)弱不同，類型也不相同，特征提取較難.chair模型較為簡(jiǎn)單，具有清晰的邊緣特征，點(diǎn)云密度不均勻，邊緣特征相對(duì)容易提取.bunny模型以弱曲率特征為主，屬于閉合類點(diǎn)云，不同部位點(diǎn)云密度差異較大，故點(diǎn)云邊緣不易檢測(cè)，相較于前兩種模型，該模型的點(diǎn)云密度較大.

2.2 算法對(duì)比及分析

2.2.1 airplane模型的算法對(duì)比 airplane模型的參數(shù)設(shè)置為α=5，β=2，γ=1.分別采用法向算法、曲率算法、文獻(xiàn)[8]算法、文獻(xiàn)[18]算法和文中算法提取邊緣特征，特征點(diǎn)的保留數(shù)量分別為3 611，4 437，3 606，6 823，3 394點(diǎn)；運(yùn)行時(shí)間分別為7.501，7.345，8.945，9.754，8.711 s；每1 000點(diǎn)的運(yùn)行時(shí)間分別為0.481,0.604,0.403,0.700,0.390 s.

airplane模型邊緣檢測(cè)效果對(duì)比，如圖3所示.由圖3可知：文中算法與法向算法、文獻(xiàn)[8]算法的邊緣提取效果的差別不大.這3種算法對(duì)螺旋槳尖銳棱線和密度較小區(qū)域的邊緣提取效果較差，但文中算法特征點(diǎn)的保留數(shù)量少于法向算法與文獻(xiàn)[8]算法，節(jié)省了存儲(chǔ)空間，精簡(jiǎn)了特征點(diǎn)，這為后期通過特征進(jìn)行檢測(cè)及配準(zhǔn)做好準(zhǔn)備；曲率算法和文獻(xiàn)[18]算法的邊緣提取效果優(yōu)于文中算法，但前兩者提取的特征不夠精簡(jiǎn)，包含大量非特征點(diǎn)，特別是文獻(xiàn)[18]算法對(duì)機(jī)身和機(jī)翼等特征弱曲率點(diǎn)不夠敏感，且耗時(shí)最長(zhǎng).

(a) 法向算法 (b) 曲率算法 (c) 文獻(xiàn)[8]算法 (d) 文獻(xiàn)[18]算法 (e) 文中算法圖3 airplane模型邊緣檢測(cè)效果對(duì)比Fig.3 Edge detection effect comparison of airplane model

2.2.2 chair模型的算法對(duì)比 chair模型參數(shù)設(shè)置為α=0，β=6，γ=0.分別采用法向算法、曲率算法、文獻(xiàn)[8]算法、文獻(xiàn)[18]算法和文中算法提取邊緣特征，特征點(diǎn)保留數(shù)量分別為3 841，3 685，5 982，6 798，4 938點(diǎn)；運(yùn)行時(shí)間分別為8.879，8.598，10.292，11.125，9.934 s；每1 000點(diǎn)的運(yùn)行時(shí)間分別為0.433,0.429,0.581,0.611,0.497 s.

chair模型邊緣檢測(cè)效果對(duì)比，如圖4所示.由圖4可知：法向算法與曲率算法可以提取強(qiáng)特征邊緣，但這兩種算法對(duì)弱邊緣特征不夠敏感，椅面、靠背的邊緣特征有不同程度的缺失，而文中算法在邊緣提取效果上優(yōu)于法向算法和曲率算法，能夠很好地保留靠背及椅面邊的邊緣特征；文獻(xiàn)[8]算法和文獻(xiàn)[18]算法雖然對(duì)弱邊緣特征提取效果較好，但對(duì)非特征點(diǎn)存在誤判，如靠背弱曲率非特征點(diǎn)的誤判導(dǎo)致提取的特征點(diǎn)不夠精簡(jiǎn)，而文中算法可以很好地將邊緣特征與非邊緣特征進(jìn)行區(qū)分，且提取的特征點(diǎn)數(shù)量較少，所用時(shí)間相對(duì)較少.

(a) 法向算法 (b) 曲率算法 (c) 文獻(xiàn)[8]算法(d) 文獻(xiàn)[18]算法 (e) 文中算法圖4 chair模型邊緣檢測(cè)效果對(duì)比Fig.4 Edge detection effect comparison of chair model

2.2.3 bunny模型的算法對(duì)比 bunny模型的參數(shù)設(shè)置為α=10，β=0，γ=0.分別采用法向算法、曲率算法、文獻(xiàn)[8]算法、文獻(xiàn)[18]算法和文中算法提取邊緣特征，特征點(diǎn)的保留數(shù)量分別為8 183，9 359，8 064，6 665，6 741點(diǎn)；運(yùn)行時(shí)間分別為23.238，24.562，24.373，24.549，24.054 s；每1 000點(diǎn)的運(yùn)行時(shí)間分別為0.352,0.381,0.331,0.261,0.280 s.

bunny模型邊緣檢測(cè)效果對(duì)比，如圖5所示.由圖5可知：文中算法與法向算法、文獻(xiàn)[8]算法及文獻(xiàn)[18]算法的邊緣提取效果差別不大，對(duì)bunny的尾巴、腳和耳朵等特征部位提取較好，對(duì)身體的弱特征區(qū)域提取較差；在保留相同特征效果的情況下，文中算法運(yùn)行時(shí)間最少，特征點(diǎn)保留數(shù)量與文獻(xiàn)[18]僅相差76點(diǎn)；在提取弱邊緣特征時(shí)，文中算法比曲率算法差，但數(shù)據(jù)更加精簡(jiǎn)，可避免非特征點(diǎn)的誤判，而曲率算法提取的特征包含一定數(shù)量的非邊緣特征點(diǎn)，如bunny的腿和背部上的非特征點(diǎn).

(a) 法向算法 (b) 曲率算法 (c) 文獻(xiàn)[8]算法 (d) 文獻(xiàn)[18]算法 (e) 文中算法圖5 bunny模型邊緣檢測(cè)效果對(duì)比Fig.5 Edge detection effect comparison of bunny model

綜上所述，在保證邊緣特征(主特征和次特征)基本相同的情況下，文中算法特征點(diǎn)提取數(shù)量大幅減少或至最少，這有利于縮減計(jì)算和存儲(chǔ)內(nèi)存，提高運(yùn)行效率；在保證主輪廓(主特征)相同的情況下，相較于文獻(xiàn)[8]及文獻(xiàn)[18]算法，文中算法的特征提取時(shí)間最少，降低了時(shí)間成本.綜上所述，文中算法在提取特征上具有一定的優(yōu)勢(shì).

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

提出一種基于高斯函數(shù)的多判別參數(shù)散亂點(diǎn)云邊緣檢測(cè)算法.利用曲率和法向提取尖銳邊緣，采用文獻(xiàn)[21]方法提取平滑邊緣特征，結(jié)合高斯函數(shù)單側(cè)σ原則減少特征點(diǎn)數(shù)量.實(shí)驗(yàn)結(jié)果表明：該算法能夠?qū)c(diǎn)云不同部位特征進(jìn)行劃分與提取，在特征點(diǎn)檢測(cè)上更加精簡(jiǎn)、速度更快，在邊緣檢測(cè)、目標(biāo)識(shí)別和基于點(diǎn)云特征配準(zhǔn)中具有一定的實(shí)用價(jià)值.然而，該算法也需進(jìn)一步改進(jìn)，當(dāng)點(diǎn)云離散程度較大，點(diǎn)云較稀疏時(shí)，邊緣提取容易出現(xiàn)孤立點(diǎn)和孔洞，提取效果有待加強(qiáng).因此，將在此算法基礎(chǔ)上對(duì)孤立點(diǎn)檢測(cè)進(jìn)行進(jìn)一步研究.