基于自適應(yīng)鄰域的固有形狀特征算法

石志良，蔡旺月，汪國(guó)強(qiáng)，熊林杰

（武漢理工大學(xué)機(jī)電工程學(xué)院，武漢430070）

（?通信作者電子郵箱1719247190@qq.com）

0 引言

在過(guò)去的幾十年里，點(diǎn)云掃描設(shè)備發(fā)展迅速，比如微軟的Kinect 傳感器，由于其低硬件成本，可以實(shí)時(shí)提供三維點(diǎn)云和二維圖像而應(yīng)用廣泛。2014 年以來(lái)，英特爾推出了一系列功能更為強(qiáng)大、更為小型化、成本更低的RealSense 模組，大力推進(jìn)了機(jī)器人、無(wú)人機(jī)和增強(qiáng)現(xiàn)實(shí)/虛擬現(xiàn)實(shí)等應(yīng)用的發(fā)展。

點(diǎn)云掃描設(shè)備和處理工具的發(fā)展促進(jìn)了研究人員對(duì)三維點(diǎn)云的研究，其中物體匹配［1］和識(shí)別應(yīng)用［2］最為廣泛。三維物體匹配作為計(jì)算機(jī)視覺(jué)研究的一個(gè)重要組成部分，在建模、可視化、識(shí)別、分類和場(chǎng)景感知等領(lǐng)域有著廣泛應(yīng)用。基于描述符的三維識(shí)別算法通過(guò)匹配局部、半局部區(qū)域或曲面來(lái)匹配兩個(gè)物體，由于其對(duì)雜波和模糊的魯棒性，已成為三維應(yīng)用中一種非常有效的方法。但描述符的計(jì)算成本通常很高，從點(diǎn)云中所有頂點(diǎn)提取描述符是沒(méi)有意義的［3］，因此，使用特征點(diǎn)檢測(cè)算法來(lái)提取點(diǎn)云特征點(diǎn)，可僅計(jì)算特征點(diǎn)的描述符，從而提高描述符的匹配效率。

基于局部特征的匹配分為兩個(gè)步驟［4］:1）識(shí)別特征點(diǎn)，即根據(jù)特征或者顯著性的定義而獲得三維頂點(diǎn)；2）特征描述與匹配，即基于三維描述符特征點(diǎn)的鄰域，將鄰域投影到特征空間中，匹配在不同表面上計(jì)算的描述符，產(chǎn)生點(diǎn)與點(diǎn)的三維對(duì)應(yīng)。

研究三維點(diǎn)云特征點(diǎn)檢測(cè)算法的原因不僅僅是因?yàn)槠渥鳛槿S點(diǎn)云應(yīng)用中的重要一環(huán)，還包括以下幾點(diǎn):1）三維點(diǎn)云與三維網(wǎng)格不同，點(diǎn)云數(shù)據(jù)僅包含三維坐標(biāo)，或同時(shí)包含頂點(diǎn)顏色信息，無(wú)拓?fù)浣Y(jié)構(gòu)，故存儲(chǔ)空間小；2）目前特征點(diǎn)檢測(cè)算法在時(shí)間和效率上都不太令人滿意，嚴(yán)重限制了檢測(cè)算法在實(shí)際應(yīng)用中的部署，隨著能夠獲得和處理3D數(shù)據(jù)的便攜式設(shè)備增加，效率問(wèn)題可能變得特別重要；3）三維數(shù)據(jù)的干擾，即代表同一對(duì)象的數(shù)據(jù)間的點(diǎn)密度變化以及模型和場(chǎng)景之間的維數(shù)差異，影響了檢測(cè)算法的性能。

1 相關(guān)工作

1.1 自適應(yīng)鄰域算法

目前，定義點(diǎn)云中一頂點(diǎn)p 的鄰域有多種方法，其中最普遍使用的是球鄰域、圓柱鄰域和k 近鄰鄰域，如圖1 所示。圖1（a）表示球鄰域由以點(diǎn)p為中心、半徑為rs的球體內(nèi)所有點(diǎn)構(gòu)成；圖1（b）將點(diǎn)投影到一平面上，以點(diǎn)p 的投影點(diǎn)為中心、半徑為rc的圓內(nèi)的點(diǎn)即為圓柱鄰域，這里的投影面一般為水平面；圖1（c）中k 近鄰鄰域是指距點(diǎn)p 最近的k 個(gè)點(diǎn)。k 近鄰鄰域定義的鄰域與球鄰域類似，會(huì)產(chǎn)生一個(gè)近似的球鄰域，這個(gè)鄰域中頂點(diǎn)數(shù)量相同，但k 近鄰鄰域的近似半徑并不固定，對(duì)于不同點(diǎn)云，k近鄰鄰域更具通用性。上述三種鄰域均為固定值方式，由于不同點(diǎn)云具有特有且不同的參數(shù)值，而且參數(shù)的選取過(guò)程通常建立在人為經(jīng)驗(yàn)基礎(chǔ)之上，需要反復(fù)試探，最終得到主觀意識(shí)上相對(duì)比較正確的值。如圖2 所示，在數(shù)據(jù)采集后，可能存在不同大小（圖2（a））、不同點(diǎn)密度的點(diǎn)云（圖2（b）），或者一個(gè)點(diǎn)云中點(diǎn)密度不均勻（圖2（c））的現(xiàn)象，而且每一點(diǎn)周圍的幾何結(jié)構(gòu)不同，采用固定值方式的鄰域定義針對(duì)這些情況需手動(dòng)改變固定鄰域的大小，存在諸多局限性。

為了克服上述固定值鄰域的局限性，許多研究者大多基于k 近鄰鄰域和優(yōu)化的方法尋找最優(yōu)鄰域。Mitra 等［5］提出了一種基于曲率、點(diǎn)密度和法向誤差的迭代方法，該方法為了得到最優(yōu)鄰域，需計(jì)算設(shè)置的參數(shù)較多，并依賴于點(diǎn)云的屬性。劉鵬等［6］依據(jù)所求頂點(diǎn)位置的點(diǎn)云密度，計(jì)算了一個(gè)合適的動(dòng)態(tài)球半徑，但該算法對(duì)于稀疏、不規(guī)則點(diǎn)云存在一定的缺陷。Mark 等［7］提出了基于曲面變化的方法。Jerome 等［8］提出了基于維度的尺度選擇。Weinmann 等［9］提出了基于特征熵的尺度選擇，并分析對(duì)比了最優(yōu)鄰域的三維場(chǎng)景分類結(jié)果與固定值鄰域的差異，發(fā)現(xiàn)前者更有優(yōu)勢(shì)。何鄂龍［10］在特征熵的基礎(chǔ)上，提出了一種顧及曲率的自適應(yīng)鄰域（Adaptive Neighborhood，AN）算法。Blomley 等［11］驗(yàn)證了點(diǎn)云中每一點(diǎn)是否應(yīng)該具有不同大小的鄰域。自適應(yīng)鄰域是在固定鄰域的基礎(chǔ)之上進(jìn)行最優(yōu)鄰域的選取，理論計(jì)算時(shí)間增加，但根據(jù)以上研究結(jié)果，發(fā)現(xiàn)雖然計(jì)算點(diǎn)云中每個(gè)點(diǎn)特有的鄰域大小會(huì)造成額外的計(jì)算時(shí)間，但自適應(yīng)鄰域的優(yōu)點(diǎn)可以彌補(bǔ)其自身造成的時(shí)間成本缺陷。

1.2 三維特征點(diǎn)檢測(cè)算法

隨著點(diǎn)云技術(shù)的不斷發(fā)展，點(diǎn)云數(shù)據(jù)的獲取和處理越來(lái)越容易。點(diǎn)云是指物體或環(huán)境表面的點(diǎn)數(shù)據(jù)集合，點(diǎn)云與網(wǎng)格模型不同，前者沒(méi)有額外的拓?fù)浣Y(jié)構(gòu)，文件存儲(chǔ)空間較小，計(jì)算過(guò)程不需過(guò)多顧慮點(diǎn)數(shù)量的增減影響計(jì)算時(shí)間的問(wèn)題:因?yàn)楫?dāng)網(wǎng)格點(diǎn)數(shù)據(jù)的增加或減少，原先的拓?fù)浣Y(jié)構(gòu)肯定不再適用，如若計(jì)算中需使用拓?fù)浣Y(jié)構(gòu)，則需重新建立拓?fù)浣Y(jié)構(gòu)，即3D 表面重建；而點(diǎn)云只需重新建立KDtree 結(jié)構(gòu)，在時(shí)間成本上，表面重建的計(jì)算成本遠(yuǎn)多于建立一個(gè)KDtree的時(shí)間。

三維點(diǎn)云特征點(diǎn)檢測(cè)算法是計(jì)算機(jī)視覺(jué)研究中識(shí)別、分類和場(chǎng)景感知等領(lǐng)域的關(guān)鍵環(huán)節(jié)，其目的是確定可重復(fù)的特征點(diǎn)，以便在視點(diǎn)的變化下，有效地描述和匹配物體。三維特征點(diǎn)檢測(cè)算法分為兩類，即固定尺度檢測(cè)算法和自適應(yīng)尺度檢測(cè)算法。固定尺度算法主要包括修剪和非極大值抑制（Non-Maximum Suppression，NMS）兩個(gè)步驟，初步挑選出候選特征點(diǎn)，經(jīng)過(guò)非極大值抑制算法，得到最終的特征點(diǎn)集合。與固定尺度檢測(cè)算法相比，自適應(yīng)尺度檢測(cè)算法則需建立和選取尺度空間。

Chen 等［12］提 出 局 部 表 面 補(bǔ) 丁（Local Surface Patches，LSP）算法，基于頂點(diǎn)的最大和最小主曲率來(lái)計(jì)算頂點(diǎn)的形狀指數(shù)，并以此來(lái)衡量該頂點(diǎn)的顯著性:通過(guò)計(jì)算頂點(diǎn)及其鄰域中每一點(diǎn)的形狀指數(shù)，得到該鄰域的平均形狀指數(shù)，若該頂點(diǎn)的形狀指數(shù)明顯大于或明顯小于平均形狀指數(shù)，則該頂點(diǎn)被保留下來(lái)，作為候選特征點(diǎn)。當(dāng)候選特征點(diǎn)篩選完成之后，對(duì)這些點(diǎn)執(zhí)行NMS；判斷一個(gè)頂點(diǎn)的形狀指數(shù)是否為局部極大值或局部極小值，若一個(gè)頂點(diǎn)的形狀指數(shù)全部大于或全部小于其鄰域中每一點(diǎn)，則該頂點(diǎn)屬于真正的特征點(diǎn)。

Zhong［13］于2009 年提出了固有形狀特征（Intrinsic Shape Signatures，ISS）算法。ISS 算法是基于頂點(diǎn)鄰域的協(xié)方差矩陣的特征值分解來(lái)計(jì)算頂點(diǎn)的顯著性:在修剪階段，兩連續(xù)特征值之比均小于閾值的點(diǎn)被保留，并作為候選特征點(diǎn)，其目的是為了滿足可重復(fù)性，避免檢測(cè)在主軸方向上具有近似擴(kuò)散特征的點(diǎn)。在NMS 階段，顯著性取決于最小特征值的大小，若一頂點(diǎn)的最小特征值均小于其鄰域中每一點(diǎn)，則該點(diǎn)屬于真正的特征點(diǎn)。

Mian 等［14］提 出 了 一 種 稱 為 特 征 點(diǎn) 質(zhì) 量（KeyPoint Quality，KPQ）的三維特征點(diǎn)檢測(cè)算法，其原理與ISS 算法類似，顯著性基于協(xié)方差矩陣來(lái)衡量，但特征點(diǎn)通過(guò)兩個(gè)主軸長(zhǎng)度比與閾值比較來(lái)確定。這類似于閾值化的特征值比，與ISS不同的是KPQ 只考慮前兩個(gè)主方向，得到更多的候選特征點(diǎn)。在NMS 階段，KPQ 通過(guò)經(jīng)驗(yàn)公式計(jì)算得出。Mian 除了提出了固定尺度的方法外，還提出了一種自適應(yīng)尺度的特征點(diǎn)質(zhì)量（KPQ-Adaptive-Scale，KPQ-AS）算法。該算法的尺度空間是通過(guò)增加鄰域大小來(lái)建立的，在修剪階段，KPQ-AS 算使用方法與KPQ 相同。KPQ-AS 與KPQ 的顯著性定義相同，但NMS在其選定的尺度上執(zhí)行。

Sun 等［15］于2009 年 提 出 了 熱 核 特 征（Heat Kernel Signature，HKS）的方法:對(duì)任何流形，存在一個(gè)函數(shù)，該函數(shù)定義為在時(shí)間t內(nèi)單位熱源從一點(diǎn)傳遞到另一點(diǎn)的熱量，稱為熱核。擴(kuò)散熱量的多少由流形決定。為了將HKS 應(yīng)用于特征點(diǎn)檢測(cè)算法，Sun 將顯著性定義為較大t 值下的函數(shù)值，并選擇2環(huán)鄰域內(nèi)顯著性的局部最大值的頂點(diǎn)作為特征點(diǎn)。

針對(duì)自適應(yīng)尺度檢測(cè)算法，Unnikrishnan等［16］提出了一種Laplace Beltrami 尺 度 空 間（Laplace Beltrami Scale Space，LBSS）方法:通過(guò)不斷增加三維網(wǎng)格中每個(gè)頂點(diǎn)的鄰域大小來(lái)計(jì)算Laplace-Beltrami 算子，再基于平均曲率和Laplace-Beltrami 算子計(jì)算一個(gè)常量，并以該常量建立尺度空間，而常量值則用來(lái)衡量顯著性。

與LBSS 相同，MeshDoG［17］將三維網(wǎng)格作為構(gòu)建尺度空間的輸入。尺度空間是通過(guò)應(yīng)用不同的歸一化高斯導(dǎo)數(shù)的差分高斯（Difference-of-Gaussians，DoG）算子創(chuàng)建，MeshDoG 不改變網(wǎng)格幾何，其中，DoG 的計(jì)算可以基于平均曲率或者高斯曲率或者光度信息，而其輸出作為頂點(diǎn)的顯著性。Bronstein等［18］基于文獻(xiàn)［17］的工作提出了一種突出點(diǎn)（Salient Points，SP）的自適應(yīng)尺度算法，該算法也是一種基于DoG 算子的方法，但它通過(guò)改變網(wǎng)格幾何建立尺度空間，在不同尺度的濾波之后，檢測(cè)具有顯著位移的頂點(diǎn)作為特征點(diǎn)。

韓磊等［19］針對(duì)三維掃描儀獲取的點(diǎn)云數(shù)據(jù)在簡(jiǎn)化過(guò)程中容易丟失模型細(xì)節(jié)特征這一問(wèn)題，根據(jù)均勻分布點(diǎn)云的特點(diǎn)提出一種自適應(yīng)點(diǎn)云特征點(diǎn)提取算法，但該算法主要針對(duì)均勻點(diǎn)云，耗時(shí)長(zhǎng)。王慶華等［20］為了有效獲取散亂點(diǎn)云中的尖銳特征點(diǎn)和邊界特征點(diǎn)，提出一種利用多判據(jù)融合的特征點(diǎn)提取算法，主要用于點(diǎn)云精簡(jiǎn)，計(jì)算效率差。

文獻(xiàn)［3-4］綜述了相關(guān)三維特征點(diǎn)檢測(cè)算法，文獻(xiàn)［4］實(shí)驗(yàn)算法包括LSP、ISS、KPQ、HKS、MeshDoG、LBSS、KPQ-AS、SP，文獻(xiàn)［3］對(duì)比了點(diǎn)云庫(kù)（Point Cloud Library，PCL）中已實(shí)現(xiàn)的特征點(diǎn)檢測(cè)算法:ISS、SIFT3D、Harris3D、SUSAN、Lowe、KLT、Curvature、Noble。文獻(xiàn)［4］的研究表明KPQ 的可重復(fù)性、區(qū)分性和抗噪性表現(xiàn)最好，而ISS 算法在絕對(duì)和相對(duì)可重復(fù)性間具有最好的權(quán)衡，效率較高；針對(duì)物體識(shí)別，MeshDoG和KPQ-AS 表現(xiàn)較好，后者在抗噪性和顯著性方面更出色，ISS算法在可重復(fù)性上具有較好的結(jié)果，只要數(shù)據(jù)沒(méi)有太多噪聲，ISS是一個(gè)可行的方法；在計(jì)算成本方面，自適應(yīng)尺度檢測(cè)算法明顯多于固定尺度檢測(cè)算法。文獻(xiàn)［3］的實(shí)驗(yàn)結(jié)果表明，ISS 算法在重復(fù)性方面比尺度不變特征變換（Scale-Invariant Feature Transform，SIFT）表現(xiàn)更好，但在旋轉(zhuǎn)平移變換下，兩種算法在重復(fù)性方面都有所下降，且變化明顯。根據(jù)以上實(shí)驗(yàn)結(jié)果，發(fā)現(xiàn)ISS 算法在可重復(fù)性具有較好的表現(xiàn)，但在噪聲和旋轉(zhuǎn)平移變換下存在明顯的不足。

針對(duì)固定尺度和自適應(yīng)尺度三維特征點(diǎn)檢測(cè)算法所存在的問(wèn)題，本文提出一種自適應(yīng)鄰域的ISS 改進(jìn)算法ANISS，用于檢測(cè)點(diǎn)云特征點(diǎn)。該方法利用局部特征計(jì)算每一點(diǎn)的自適應(yīng)鄰域k 值，并應(yīng)用于ISS、NMS 算法，得到最終的特征點(diǎn)。ANISS算法不需要手動(dòng)設(shè)置參數(shù)，不僅避免了ISS算法因參數(shù)設(shè)置有誤而導(dǎo)致不良的算法效果，而且實(shí)驗(yàn)表明，ANISS 算法的可重復(fù)性和抗噪性明顯優(yōu)于ISS 算法，且兩者的計(jì)算效率差異可以忽略不計(jì)。

2 ANISS算法

ANISS 算法與ISS算法采用不同的鄰域確定方式，由自適應(yīng)鄰域替代球鄰域。

2.1 AN算法

AN 算法作為ANISS 算法中關(guān)鍵一環(huán)，目的是為點(diǎn)云中的每一頂點(diǎn)找到一個(gè)最優(yōu)的鄰域大小。

給定一點(diǎn)云P(pi，i = 0，1，…，n，n ∈N)，則根據(jù)點(diǎn)云P 中某一頂點(diǎn)pi的鄰域，計(jì)算加權(quán)協(xié)方差矩陣C:

其中:pi是點(diǎn)云P 中第i+1 個(gè)頂點(diǎn)；k 是點(diǎn)pi的鄰域頂點(diǎn)的個(gè)數(shù)；pˉ是點(diǎn)pi鄰域的幾何中心。

矩陣C 是對(duì)稱正定矩陣，其特征值λ1、λ2、λ3（λ1≥λ2≥λ3≥0）是非負(fù)的，并且對(duì)應(yīng)的特征向量v1、v2、v3是正交的。特征值與對(duì)應(yīng)的特征向量實(shí)質(zhì)上描述了一個(gè)橢球范圍，特征向量代表的是主軸方向，對(duì)應(yīng)的特征值是主軸長(zhǎng)度，因此，可以通過(guò)特征值來(lái)描述局部三維形狀。

基于文獻(xiàn)［3-5］中自適應(yīng)鄰域算法，提出兩種思路:

1）對(duì)于尖銳特征使用較小的k 值，對(duì)于平坦部位采用較大的k值；

2）在尖銳部位采用較大的k 值，在平坦部位采用較小的k值。

在局部鄰域算法中，可能由于鄰域大小的改變，尖銳部位鄰域信息變化明顯，若尖銳部位采用大的k 值，鄰域信息更豐富，算法在較大范圍里更準(zhǔn)確地描述此部位原始形狀；在平坦部位由于特征變化不大，鄰域大小的改變對(duì)原始表面描述的準(zhǔn)確性可能影響不大。

三個(gè)特征值表示k 近鄰鄰域的橢球范圍的三個(gè)主軸長(zhǎng)度，λ1是最大的主軸長(zhǎng)度，λ3是最小的主軸長(zhǎng)度，所提出的AN 算法將用λ3/λ1值來(lái)描述此k 近鄰鄰域的特征大小。給定k 值選取范圍[k1，k2]，由于λ3/λ1與最優(yōu)k 值間的關(guān)系未知，因此，給出如下6種計(jì)算每一頂點(diǎn)k值的方式:

2.2 ANISS算法

給 定 一 點(diǎn) 云 P(pi，i = 1，2，…，n，n ∈N)，點(diǎn) 集 合NEIB(neibj，j = 1，2，…，ki，ki≤n)是點(diǎn)pi的鄰域。其中:n 是點(diǎn)云P 的點(diǎn)數(shù)量；點(diǎn)neibj是點(diǎn)pi的鄰域點(diǎn)；ki是點(diǎn)pi根據(jù)AN算法計(jì)算的鄰域k 值，將AN 算法計(jì)算的自適應(yīng)鄰域k 值傳遞給ISS算法和NMS算法即為AN算法與ISS算法融合過(guò)程。圖3為ANISS算法判斷每一頂點(diǎn)是否為特征點(diǎn)的流程圖，主要分為五個(gè)步驟:

1）通過(guò)AN算法計(jì)算每一頂點(diǎn)的自適應(yīng)鄰域ki值。

2）計(jì)算點(diǎn)pi鄰域中每一點(diǎn)的權(quán)重wi:

3）計(jì)算點(diǎn)pi鄰域的加權(quán)協(xié)方差矩陣C(pi):

4）計(jì)算矩陣C(pi)的特征值λ1、λ2、λ3(λ1≥λ2≥λ3)，判斷點(diǎn)pi是否為近似特征點(diǎn)的依據(jù)是通過(guò)連續(xù)特征值間的比值與閾值γ12、γ23相比較，小于閾值則是近似特征點(diǎn)；否則，不為近似特征點(diǎn)。

5）NMS算法。由于點(diǎn)云中特征突出部位的近似特征點(diǎn)分布集中，為了減少信息冗余，將對(duì)近似特征點(diǎn)應(yīng)用NMS 算法，從中提取出最具特征的近似特征點(diǎn)；根據(jù)AN 算法計(jì)算的鄰域k 值，篩選出鄰域中最小第三特征值對(duì)應(yīng)的近似特征點(diǎn)，作為真正的特征點(diǎn)。

圖3 ANISS算法流程Fig. 3 ANISS algorithm flowchart

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

實(shí)驗(yàn)?zāi)康氖菧y(cè)試ANISS算法的旋轉(zhuǎn)平移不變性和噪聲敏感性，并與ISS 算法進(jìn)行比較，得到一種最優(yōu)的ANISS 算法。實(shí)驗(yàn)的硬件環(huán)境中CPU為IntelCore i7-8700K CPU@3.70 GHz，內(nèi)存為16.00 GB，主硬盤為120 GB SSD，顯卡為NVIDIA GeForce GTX1050 Ti（4 GB），Windows 10 專業(yè)版（64 位）操作系統(tǒng)，開(kāi) 發(fā) 環(huán) 境 為Visual Studio2013、PCL1.8.0、VTK7.0.0、QT5.7.0。

3.1 點(diǎn)云數(shù)據(jù)庫(kù)

為了評(píng)估特征點(diǎn)檢測(cè)算法關(guān)于旋轉(zhuǎn)平移的不變性，需生成 本 次 實(shí) 驗(yàn) 的 點(diǎn) 云 數(shù) 據(jù) 庫(kù) ，PCL 中 的RenderViewsTesselatedSphere 類可以模擬現(xiàn)實(shí)掃描設(shè)備，在遮擋、旋轉(zhuǎn)、平移的環(huán)境下，掃描得到可見(jiàn)部分的物體點(diǎn)云。以ply 文件作為輸入，輸出掃描點(diǎn)云。在生成點(diǎn)云的數(shù)量上，算法可以設(shè)置ply 文件生成掃描點(diǎn)云的數(shù)量，共有6 個(gè)級(jí)別:42、80、162、320、642、1 280，本次實(shí)驗(yàn)使用42 這一級(jí)別，即在42個(gè)不同的視點(diǎn)下，生成42 個(gè)掃描點(diǎn)云。基于斯坦福（http://graphics. stanford. edu/data/3Dscanrep/）的2 例模型，每一模型生成42 個(gè)不同的掃描點(diǎn)云，圖4 為Bunny、Happy 模型的5 個(gè)掃描點(diǎn)云。

圖4 Bunny、Happy模型的掃描點(diǎn)云Fig.4 Scanning point clouds of Bunny and Happy models

為了模擬環(huán)境噪聲、添加更加合理的噪聲，計(jì)算每個(gè)點(diǎn)云的分辨率rlt，定義點(diǎn)云中每一頂點(diǎn)與其最近鄰距離的平均值為點(diǎn)云的分辨率。利用Boost 算法庫(kù)，以［0，2rlt］、［0，4rlt］、［0，6rlt］為隨機(jī)數(shù)生成范圍，分別生成隨機(jī)實(shí)數(shù)，并增加到頂點(diǎn)坐標(biāo)值中，從而形成不同噪聲級(jí)別的噪聲，這里將噪聲級(jí)別簡(jiǎn)稱為L(zhǎng)2、L4、L6；在L2、L4、L6 級(jí)別的基礎(chǔ)上，根據(jù)每一點(diǎn)云中添加噪聲的頂點(diǎn)數(shù)量在點(diǎn)云頂點(diǎn)總數(shù)中的占比，再次進(jìn)行級(jí)別的劃分5%、10%、15%，簡(jiǎn)稱為P5、P10、P15。圖5 為整個(gè)噪聲點(diǎn)云的級(jí)別劃分示意圖，圖6 為Bunny、Happy 的原始點(diǎn)云與噪聲點(diǎn)云圖。

圖5 噪聲點(diǎn)云的級(jí)別劃分Fig.5 Level division of noise point cloud

圖6 原始點(diǎn)云與噪聲點(diǎn)云Fig.6 Original point clouds and noise point clouds

3.2 評(píng)價(jià)指標(biāo)

三維特征點(diǎn)檢測(cè)算法的主要特征是特征性和可重復(fù)性:前者是一種能夠有效描述和匹配特征點(diǎn)的能力，從而盡可能防止點(diǎn)與點(diǎn)的錯(cuò)誤對(duì)應(yīng)；后者是在各種干擾下準(zhǔn)確檢測(cè)相同特征點(diǎn)的能力。實(shí)驗(yàn)中刻意強(qiáng)調(diào)可重復(fù)性的原因有兩個(gè):1）可重復(fù)性可以給定定義，并可以根據(jù)定義評(píng)判檢測(cè)的特征點(diǎn)是否具有可重復(fù)性；2）局部形狀元素的特征性實(shí)際上是場(chǎng)景或模型的一個(gè)相對(duì)全局的屬性，因此很難被局部算法（例如特征點(diǎn)檢測(cè)算法）所捕獲。因此，將可重復(fù)性作為三維點(diǎn)云特征點(diǎn)檢測(cè)算法最重要的特性，以絕對(duì)可重復(fù)性和相對(duì)可重復(fù)性作為實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)。

點(diǎn)云Pos是場(chǎng)景中物體點(diǎn)云在點(diǎn)云OP的對(duì)應(yīng)部位的特征點(diǎn)點(diǎn)云，獲得該點(diǎn)云的方法是點(diǎn)云OP的特征點(diǎn)經(jīng)過(guò)旋轉(zhuǎn)平移變換，搜索變換后的特征點(diǎn)在場(chǎng)景點(diǎn)云中的最近鄰，若兩者距離小于閾值ε1，則該特征點(diǎn)屬于點(diǎn)云Pos。其中，閾值ε、ε1均設(shè)置為2rlt。

3.3 旋轉(zhuǎn)平移不變性實(shí)驗(yàn)與分析

旋轉(zhuǎn)平移不變性實(shí)驗(yàn)?zāi)康氖菫榱朔治鎏卣鼽c(diǎn)檢測(cè)算法在點(diǎn)云存在旋轉(zhuǎn)平移下的表現(xiàn)情況，并與ISS算法比較。

ISS 算法的參數(shù)包括搜索半徑、極大值抑制算法半徑、γ12、γ23，根據(jù)文獻(xiàn)［4］，分別設(shè)置為6rlt、4rlt、0.975、0.975，ANISS 算法的參數(shù)包括極大值抑制算法k值、γ12、γ23。為了保證實(shí)驗(yàn)算法的可比較性，更改ANISS算法的極大值抑制算法k值為點(diǎn)云中每一頂點(diǎn)自適應(yīng)鄰域k 值的2/3，兩個(gè)連續(xù)特征值比率的閾值與ISS算法保持一致。

實(shí)驗(yàn)以2.1 節(jié)中的旋轉(zhuǎn)平移點(diǎn)云為測(cè)試數(shù)據(jù)，以絕對(duì)可重復(fù)性和相對(duì)可重復(fù)性為判斷依據(jù)，對(duì)測(cè)試數(shù)據(jù)應(yīng)用ANISS和ISS 算法，得到各個(gè)點(diǎn)云特征點(diǎn)點(diǎn)云的平均絕對(duì)可重復(fù)性和平均相對(duì)可重復(fù)性，如表1所示。

表1 針對(duì)旋轉(zhuǎn)平移點(diǎn)云的平均絕對(duì)可重復(fù)性和平均相對(duì)可重復(fù)性Tab.1 Average absolute repeatability and average relative repeatability for rotationally translated point clouds

圖7 五種算法的特征點(diǎn)檢測(cè)結(jié)果對(duì)比Fig.7 Comparison of feature point detection results of five algorithms

表2 不同算法的平均計(jì)算時(shí)間對(duì)比 單位：sTab.2 Average calculation time comparison of different algorithms unit:s

3.4 噪聲敏感性實(shí)驗(yàn)與分析

表3 針對(duì)噪聲點(diǎn)云的平均絕對(duì)可重復(fù)性和平均相對(duì)可重復(fù)性Tab.3 Average absolute repeatability and average relative repeatability for noisy point clouds

圖8 ISS、ANISS的特征點(diǎn)檢測(cè)結(jié)果對(duì)比Fig.8 Comparison of feature point detection results of ISS and ANISS

4 結(jié)語(yǔ)

雖然所提算法在一定程度上優(yōu)于ISS，但導(dǎo)致產(chǎn)生較多的特征點(diǎn)，特征點(diǎn)中可能存在噪聲點(diǎn)，對(duì)特征描述階段不利。在后續(xù)的工作中，將對(duì)特征點(diǎn)數(shù)量抑制和抗噪性作進(jìn)一步研究。