許金波+楊晶東+韓太軍

摘要：

基于視覺信息的運動目標識別是室內(nèi)移動機器人自主導航的重要研究內(nèi)容。背景噪聲干擾、自然光照、機器人視角變化等因素經(jīng)常影響識別穩(wěn)定性。針對該問題，提出一種有效的目標物體識別方法，采用體素網(wǎng)格濾波和支持kd-tree結(jié)構(gòu)對點云數(shù)據(jù)有效組織，以識別復(fù)雜環(huán)境中的物體。實驗表明，該方法在滿足實時性前提下，相比傳統(tǒng)迭代最近點、采樣一致性初始配準算法具有更高的準確率，更適合復(fù)雜環(huán)境下的物體識別。

關(guān)鍵詞：

物體識別；點云濾波；迭代最近點；采樣一致性初始配準算法

DOIDOI：10.11907/rjdk.172033

中圖分類號：TP301

文獻標識碼：A文章編號文章編號：16727800（2018）001001405

Abstract：Moving object recognition based on visual information is an important research content of autonomous navigation of indoor mobile robot. The existing methods often affect the stability due to background noise interference， natural light and robot angle change. An effective target object recognition method is proposed for this problem， and the object in the complex environment is identified by using the voxel mesh filtering and supporting the kdtree structure to effectively organize the point cloud data. Experiments show that the method of sampling coherence initial registration algorithm has higher accuracy and more suitable for object recognition in complex environment than the traditional iterative nearest point under the premise of satisfying realtime.

Key Words：object recognition； point cloud filtering； iterative closest point； initial registration algorithm

0引言

利用視覺對物體進行識別，廣泛應(yīng)用于圖像檢索、機器人抓取、場景識別和移動定位。點云旋轉(zhuǎn)錯位、平移錯位以及點云的不完整性等影響物體點云匹配識別的精準性。點云的配準指通過攝像頭在不同角度下掃描獲得點云數(shù)據(jù)，這些點云數(shù)據(jù)之間有一定的重疊區(qū)域，通過變換坐標，可以將多幅點云數(shù)據(jù)合并到同一直角坐標系下。

目前常用的點云匹配算法包括經(jīng)典的迭代最近點（Iterative Closest Point，ICP）算法、基于歐式距離不變性的Greedy bound算法、采樣一致性初始配準（Sample Consensus Initial Alignment，SACIA）算法和利用kd tree加速搜索算法、優(yōu)化ICP算法，實驗效果都較好，但存在龐大數(shù)量級點云匹配時的時間效率問題。面對大數(shù)量級別的點云集合（大于100 000個點）對應(yīng)的剛體變換，Martin Magnusson提出了利用正態(tài)分布算法加以優(yōu)化，這種思路在時間效率上有了很大改進，但在局部準度上卻有所降低。本文提出一種基于點云特征的目標識別方法（IICP—SACIA），在獲得點云原圖后對其進行體素網(wǎng)格濾波，采用改進的ICP算法和SACIA算法匹配識別物體的點云特征，最大限度地濾除了背景點云，有效提高了算法的識別效率。實驗表明該方法在室內(nèi)環(huán)境下能有效識別物體特征，滿足了移動機器人視覺自主導航要求。

1相關(guān)理論

1.1物體識別原理

物體點云匹配識別指通過攝像頭在不同角度下掃描獲取點云數(shù)據(jù)，這些點云數(shù)據(jù)之間有著一定的重疊區(qū)域。通過變換坐標，可以使多幅點云數(shù)據(jù)疊合到同一直角坐標系下，最終得到物體的點云準確配準。三維空間上的幾何模型變換一般含有平移、縮放和旋轉(zhuǎn)，本文研究的點云匹配是剛性點云匹配，在不考慮縮放的前提下，通過求得目標點云集Q到源點集P的平移向量W和旋轉(zhuǎn)矩陣B，使坐標變換后得到的轉(zhuǎn)換矩陣（B*P +W）與Q之間的距離最小，即求min‖Q-（B×P+W）‖＼+2。

1.2改進的迭代最近點算法

傳統(tǒng)的迭代最近點（Interative Closest Point，ICP）是經(jīng)典的點云匹配算法，運用四元素模型，經(jīng)過最小二乘法迭代運算來最小化源點云和目標點之間的歐式距離函數(shù)，繼而完成空間上自由曲面的配準問題。算法過程：①在兩組點云中查找多對點，在這些點對里，其中的一個點在目標點云中，另一個在待配準點云里，兩者之間滿足歐式距離最近；假設(shè)某一點對之間的距離小于給定閾值，即能確認兩個點云對之間存在一一對應(yīng)關(guān)系；②構(gòu)造所有成對點之間的“距離誤差和”的目標函數(shù)，求取變換矩陣，要求目標函數(shù)值最小，也就是整體對點之間的距離之和最?。虎鄣\算，重復(fù)上述過程，一直到距離誤差和的值小于給定閾值或者運算達到最大迭代次數(shù)為止；④假如最后配準效果滿足指標要求，即將通過整體變換后的待配準點云疊加到目標點云圖中，完成該對點云的配準。endprint

本實驗粗配準階段使用改進的ICP算法：

（1）點云的準確性：Mitra等證明了點對的正確性對ICP結(jié)果的重要性，提出當輸入點云自身存有較多噪聲時，算法會把不正確的點對配對在一起，使匹配的過程不收斂。本實驗對點云圖像體素化網(wǎng)格濾波的預(yù)處理操作就是為了防止這種情況發(fā)生，為匹配過程奠定良好基礎(chǔ)。

（2）捜索策略：ICP算法效率不高的一個重要原因是，每次迭代都需要遍歷整個點云中的點用以搜素匹配的點對，本實驗運用kdtree結(jié)構(gòu)對點云數(shù)據(jù)進行合理組織，加快了ICP算法的搜索效率。

（3）去除錯誤點對：當經(jīng)過ICP算法匹配完成后，不是所有的匹配關(guān)系都符合要求，錯誤配對的點對將對旋轉(zhuǎn)矩陣和平移矩陣的運算產(chǎn)生負面干擾，這些有誤差的配準點對應(yīng)在精確配準階段剔除。排除手段有閾值、比例、分布等。本實驗運用較為簡單的最大歐氏距離來限制約束，就是當匹配后的點對Yi和Xi的歐氏距離大于預(yù)設(shè)的限制Dmax時，判斷為一個錯誤的匹配，不參與矩陣估計。假如產(chǎn)生一對多的情況，僅僅取與目標點云歐氏距離最近的那個點作為其對應(yīng)點，剔除錯誤的對應(yīng)關(guān)系。

1.3采樣一致性算法配準原理

SACIA配準是根據(jù)點云的FPFH特征展開的，匹配原理與過程如下：

設(shè)目標點云為Q，待配準點云為P，①n個采樣點選取自待配準點云P，這些采樣點滿足兩兩之間的距離大于dmin，即預(yù)先給定最小距離閾值，偏向于擁有不同的FPFH特征，這樣在不影響點云整體特征統(tǒng)計的同時降低計算量；②針對點云P中的每個樣點，在目標點云Q中查找與P中該點擁有類似FPFH特征的一系列點，也就是說P中的一個采樣點也許會在Q中匹配到多個與之相似的點；③運算從P中選擇的n個采樣點與在Q中查找到的對應(yīng)點剛體變換矩陣，依次求得所有對應(yīng)點變換之后的“距離誤差和”函數(shù)，判斷當前配準變換效果。這時的距離誤差和函數(shù)一般用Huber罰函數(shù)表達，

式（1）中：第i組對應(yīng)點在變更之后的距離差是li，ml為給定值。目的是尋求一個最優(yōu)的變換，把誤差函數(shù)值降到最小，此時的變換即是最終的匹配變換矩陣所得的匹配結(jié)果。

2物體識別

2.1點云濾波

因為深度體感相機采集的原始點云數(shù)據(jù)龐大，直接用來配準會加大計算機系統(tǒng)運算負擔，降低匹配效率。本實驗運用點云體素化網(wǎng)格濾波，在物體識別之前對點云進行濾波，可使體感相機獲取點云細節(jié)特征，具有較高的配準率。VG濾波器用以建立一個三維體素柵格，體素重心的點用下式表示：

式（2）中：Pl為體素基元，Pmin為點云最小點，Pmul為點云中體素基元Pl各個方向上的擴展體素，Pid為該點體素重心，Round為基于基元Pl的矢量積，取整函數(shù)。

針對480×640深度圖像，采用體素網(wǎng)格法向下取整，得到體素范圍內(nèi)具有相同標識點云簇。計算點云在體素Pl下重心Pid信息。該方法對于曲面采樣點具有較高效率，能有效降低點云密度，確保局部點云特征。體素濾波要考慮點云壓縮效率和后期處理時間，確保在點云特征不丟失前提下設(shè)定壓縮參數(shù)。

圖1、圖2分別是點云圖和VG濾波后點云圖（見封二彩圖）?？梢钥闯鰹V波后點云密集度降低。VG濾波器將源點云數(shù)據(jù)根據(jù)體素比例投影到新點云集合中，在新集中每一個點都有唯一ID標識，根據(jù)ID對源點云進行處理，經(jīng)過VG濾波后，可濾除不必要的點云簇，有效提高后期物體識別效率。經(jīng)過多次體素濾波可得到擁有最佳點云特征的體素值。

2.2計算點云的法線特征

在不干擾整體點云幾何特征的情況下，降低點云幾何特征的運算量，對點云數(shù)據(jù)集進行體素網(wǎng)格濾波等處理，獲得點云幾何特征流程如圖3所示。

獲得點云的局部幾何特征直方圖（Point Feature Histograms，PFH）。幾何曲面中一個重要特征即是表面法線，廣泛運用于計算機圖形處理。一組點云數(shù)據(jù)集，運算全體點的法線方式有以下兩種：①依據(jù)曲面網(wǎng)格化（surface mesh）技術(shù)，對所獲得的點云數(shù)據(jù)進行曲面重建，然后依據(jù)重建的曲面計算其法線向量；②不進行曲面重建，而是用一組點云數(shù)據(jù)計算每一組點的法線。

本文運用第②種方法，曲面上的某一點法線以該點在曲面上的相切平面的法線所代替，因此到相切平面的擬合估計通常依據(jù)最小二乘法擬合。設(shè)需求點為p，其坐標為（x，y，z）＼+T，其k 個鄰域點為Pi，則在待求點處構(gòu)造協(xié)方差矩陣R如式（3）：

式（4）中：k為正整數(shù)，用來對特征值計數(shù)。協(xié)方差矩陣說明了待求點的局部變化。另外，該點處法線的走向依據(jù)協(xié)方差矩陣的最小特征值的特征向量來估算。

2.3物體識別

通過對原點云進行體素網(wǎng)格濾波處理，再依據(jù)物體特征直方圖進行物體識別。

深度相機點云簇形狀不規(guī)則且分布不均勻，可在3D空間使用固定寬度體素網(wǎng)格表示，并采用kd-tree結(jié)構(gòu)填充。該結(jié)構(gòu)具有二叉樹結(jié)構(gòu)，且不需空間等分，比八叉樹更好地包圍圖元。運用采樣一致性算法對待匹配點云進行粗配準，最后結(jié)合改進的ICP對點云進行細配準以提高配準準確度。系統(tǒng)流程如圖4所示。

設(shè)Po為單位向量，l為體素長度。Pp、Pr為人、物體、機器人位置，算法描述如下：

Start輸入源點云Pin

Step1設(shè)置基元體素Pl進行濾波

（1）體素參數(shù)Pl=Po/（l，l，l）

（2）獲取點云最大Pmax，Pmin，計算在x、y、z方向點云體素矢量Pdiv=（Pmax-Pmin）*Pl

（3）體素矢量積Pmul=（1，Pdiv[0]，Pdiv[0]Pdiv[1]，0）

（4）計算所有乘積系數(shù)點云簇Pid見公式（2）

（5）如果Pid只有一個，則P=Pin；若有n個Pid相同，則P=（∑Pin）/n，遍歷所有點endprint

Step2根據(jù)相機高度Hc，計算直通濾波參數(shù)

Step3對VG濾波后的點云Pi填充kdtree結(jié)構(gòu)

Step4采用一致性算法對待匹配點云進行粗配準

Step5采用IICP算法精準匹配，輸出結(jié)果

End

3實驗分析

在室內(nèi)進行物體識別實驗，其中部分實驗是在燈光照明環(huán)境下進行。操作系統(tǒng)為Ubuntu 12.04，CPU 為Intel（R） Core（TM） i3 2.53GHz，內(nèi)存為2GB。

3.1體素網(wǎng)格濾波

圖5、圖6分別是點云圖和體素網(wǎng)格濾波后點云圖（見封二彩圖），表1為不同體素網(wǎng)格濾波參數(shù)下的點云簇和壓縮效率變化。

由表1可以看出，隨著點云體素增加，濾波后點數(shù)逐漸減少，壓縮效率接近飽和。此時，點云簇中的每個點云特征具有最基本的單體特性，點云體素網(wǎng)格濾波對物體識別過程影響較小。表2為不同體素下物體識別各階段與平均時間偏差率。

表2中的正負數(shù)表示超出和低于平均時間，由此得出，濾波偏差率在-4.55%～7.15%之間波動，識別偏差

率處于-15.52%～9.48%之間。由表2可分析出，當體素值為0.01，且參數(shù)在0.02～0.023之間時，濾波偏差率波動較大，處理各階段所需時間較長，不能穩(wěn)定識別物體。當體素值大于0.027時，特征點云點數(shù)趨于飽和，濾波趨于穩(wěn)定，不同體素參數(shù)下濾波點數(shù)也趨于一致。但如果體素參數(shù)無限增大，可能導致場景中各特征點云相互融合，丟失部分有效的特征點云。因此，在滿足所需點云特征前提下，選擇合理體素可有效提升點云識別效率。

3.2物體識別

在實驗室環(huán)境下進行物體識別實驗，按照簡單環(huán)境識別和復(fù)雜環(huán)境識別，分析物體識別后的距離均方誤差變化情況。圖7、圖8為物體在簡單環(huán)境下的識別中體素網(wǎng)格濾波和最后的濾波效果（見封二彩圖）。

針對以上場景可測得物體識別后的距離均方誤差，圖8為物體點云配準輸出效果圖，可以看出簡單環(huán)境下物體的識別效果達到了預(yù)期要求。

圖9、圖10為復(fù)雜環(huán)境下的物體識別實驗（見封二彩圖），環(huán)境中待識別物體處于兩個干擾物中間，圖11、圖12、圖13為物體在復(fù)雜環(huán)境下運用IICP算法、SACIA算法、聯(lián)合IICP和SACIA算法識別效果（見封二彩圖）。

ICP和SACIA兩種配準算法的配準效果并不客觀，兩幅物體點云中存在嚴重偏差。為了獲得更精準的配準效果，本文提出了一種結(jié)合SACIA算法以及改進的ICP配準算法的點云配準進行改進。對點云進行一次SACIA匹配，作為粗配準準備，提升配對點云的吻合度；運用改進的ICP做一次精配準，得到最后的效果圖。因為歷經(jīng)了一次初始的預(yù)配準，點云之間的差異大大降低，所以，運行改進的ICP配準能更快收斂，得到更好的配準性能，明顯降低了迭代次數(shù)，節(jié)省了運行時間，提升了配準概率和配準效果。

為了比較配準效果，以“橄欖油包裝盒”點云為配準模型，與上述效果進行對比。在改進的ICP算法及SACIA基礎(chǔ)上，將SACIA的最大迭代次數(shù)由500降低為350，縮短了運行時間，最后由改進的ICP來進行精準配準。由表3看到，聯(lián)合優(yōu)化的配準總時間為268 009ms，其中SACIA配準用時304 588ms，改進的ICP配準用時51 133ms。利用聯(lián)合優(yōu)化的點云配準流程后，得到“橄欖油包裝盒”模型的源點云和目標點云，如圖13所示。從圖13可以看到，兩幀點云中物體盒子的各個部分都得到了良好的配準。完成聯(lián)合配準后源點云和目標點云一一對應(yīng)點對的距離誤差平方值，如圖14～圖16所示?；诟倪M的ICP聯(lián)合SACIA對應(yīng)點對的距離均方誤差結(jié)果約為：1.12e-6。

從表3可以得出，僅僅使用改進的ICP 算法運行時間最短，但距離均方值誤差最大，配準結(jié)果最不理想；單單使用SACIA 算法的運行時間最長，距離均方差較小，但部分區(qū)域偏差較大；SACIA算法和改進的ICP算法組合配準方式的運行時間比SACIA 的時間少，且匹配后的距離均方誤差很小，此組合優(yōu)化匹配效果最好。

4結(jié)語

本文提出了一種有效物體識別算法，對基于深度視覺的原點云進行體素網(wǎng)格過濾，通過改進ICP算法和優(yōu)化配準流程實時對物體進行識別。實驗表明，該算法相比單純IICP算法和SACIA算法具有更高的準確率，相比于ICP算法具有更高的識別速度。在確保實時性前提下，較其它物體識別方法具有較高的識別精度和穩(wěn)定性，提高了自主機器人目標跟蹤的魯棒性。

參考文獻：

[1]馬爾，姚國正，劉磊，等.視覺計算理論[M].北京：科學出版社，1988.

[2]ZHANG Z.A flexible new technique for camera calibration[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions， 2000，22（11）：13301334.

[3]陳陽.三維點云數(shù)據(jù)配準方法研究[D].天津：天津大學，2014.

[4]WILMA PAIRO1， JAVIER RUIZDELSOLAR， RODRIGO VERSCHAE1， et al.Person following by mobile robots： analysis of visualand range tracking methods and technologies[C]. 17th annual RoboCup International Symposium， 2014.

[5]HONG HAN， JINGXIANG GOU.Sparse geometric features for visual detection and estimation.image feature detection and description[J].Neurocomputing， 2013，120（1）：192202.endprint

[6]RUSU R B， BLODOW N， BEETZ M. Fast point feature histograms （FPFH） for 3D registration[C]. Robotics and Automation， IEEE International Conference， 2009：32123217.

[7]FELZENSZWALB PF， GIRSHICK R B， MCALLESTER D， et al. Object detection withdiscriminatively trained part based models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2010，32（9）：120.

[8]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM， 1975，18（9）：509517.

[9]RUSU R B， COUSINS S. 3D is here： point cloud library （pcl）[C]. Robotics and Automation （ICRA）， IEEE International Conference， 2011：14.

[10]戴靜蘭，陳志楊，葉修梓.ICP算法在點云配準中的應(yīng)用[J].中國圖象圖形學報，2007，12（3）：517521.

[11]EMI MATSUMOTO， MICHLE SEBAG，EINOSHIN SUZUKI.Using SVM to avoid humans： a case of a small autonomous mobile robot in an office[C]. Computer and information Sciences， 2011.

[12]王欣，張明明，于曉，等.應(yīng)用改進迭代最近點方法的點云數(shù)據(jù)配準[J].光學精密工程，2012，20（9）：20682077.

[13]解則曉，徐尚.三維點云數(shù)據(jù)拼接中ICP及其改進算法綜述[J].中國海洋大學學報：自然科學版，2010（1）：99103.

[14]楊現(xiàn)輝，王惠南.ICP算法在3D點云配準中的應(yīng)用研究[J].計算機仿真，2010（8）：235238.

[15]ROBIN STRANDA， BENEDEK NAGYB， GUNILLA BORGEFORSC. Digital distance functions on threedimensional grids[J].Theoretical Computer Science， 2011，412（15）：13501363.

[16]STEPHEN J REDMOND， CONOR HENEGHAN. A method for initialising the Kmeans clustering algorithm using kdtrees pattern[J]. Recognition Letters， 2007，28（8）：965973.

[17]劉博源，陸明剛，闞文濤.激光掃描表面特征的點云數(shù)據(jù)處理方法[J].光學儀器，2016，38（1）：4144.

[18]錢煒，付東翔，李曉燕，等.越障機器人的設(shè)計與研究[J].上海理工大學學報，2002（3）：264267.

（責任編輯：杜能鋼）endprint