基于改進三維形狀上下文的點云配準(zhǔn)

趙云濤，齊佳祥，李維剛，甘 鐳

（1.武漢科技大學(xué) 冶金自動化與檢測技術(shù)教育部工程研究中心，湖北 武漢 430081；2.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081）

1 引 言

3D視覺傳感器日新月異，為視覺圖像的理論研究以及點云數(shù)據(jù)的應(yīng)用提供了無限可能，而配準(zhǔn)作為視覺領(lǐng)域的核心，近些年對于配準(zhǔn)的研究層出不窮。三維點云配準(zhǔn)的目的是計算最優(yōu)匹配，將不同視圖中的點集轉(zhuǎn)換到全局坐標(biāo)下。三維點云配準(zhǔn)主要分為兩階段：初始配準(zhǔn)和精確配準(zhǔn)。初始配準(zhǔn)是為精確配準(zhǔn)提供初始變換矩陣；精確配準(zhǔn)是基于初始變換矩陣進一步得到更精確的解，從而提高配準(zhǔn)精度。精確配準(zhǔn)多采用迭代最近點（ICP）算法［1］，其具有極高的配準(zhǔn)精度的優(yōu)點，但需要良好的初始變換矩陣，否則兩點云之間的轉(zhuǎn)換較大會影響ICP迭代收斂過程，使其陷入局部最優(yōu)解。因此選擇合適的初始配準(zhǔn)算法決定了配準(zhǔn)效果。常見的初始配準(zhǔn)算法有點云直方圖算法［2］、快速點云直方圖算法［3］以及三維形狀上下文算法，其中三維形狀上下文算法可求得更優(yōu)的初始變換矩陣。

三維形狀上下文（3DSC）是Belongie等［4］是在二維形狀上下文［5］的基礎(chǔ)上拓展得來的，并將其用于目標(biāo)形狀之間相似性識別。形狀上下文配準(zhǔn)在計算機圖像學(xué)領(lǐng)域引起了廣泛關(guān)注。K?rtgen等［6］嘗試將3DSC應(yīng)用于三維形狀檢索和匹配。形狀上下文極大地簡化了源形狀和目標(biāo)形狀之間點的對應(yīng)關(guān)系，可以作為形狀相似性的可靠描述。經(jīng)研究比較，基于形狀上下文的描述符對噪聲場景具有較高的識別率。3DSC描述符結(jié)構(gòu)簡單、分辨力強，并且在雜亂場景上優(yōu)于其他描述符。

形狀上下文引入三維對象，將一個空間點上的形狀上下文用于捕獲周圍空間其他點相對位置上的分布，進而可以通過局部豐富的描述來總結(jié)全局形狀和鑒別全局特征。相似性的度量一般通過兩個形狀上的對應(yīng)關(guān)系來估計其對齊變換矩陣，兩個相似形狀上的對應(yīng)點具有相似的形狀上下文。3DSC具有縮放、旋轉(zhuǎn)和平移下的不變性以及描述能力，為三維對象之間的相似性度量提供了基礎(chǔ)。配準(zhǔn)是三維任務(wù)的關(guān)鍵，21世紀(jì)以來，國內(nèi)外學(xué)者針對3DSC的配準(zhǔn)做了很多研究。Kokkinos等［7］提出了三維形狀的內(nèi)在形狀背景（ISC）描述符，將形狀上下文中使用的圖像域極性采樣推廣到曲面上，利用內(nèi)在形狀進行分析并基于最先進的密集形狀描述符構(gòu)造ISC，實現(xiàn)了在標(biāo)準(zhǔn)基準(zhǔn)上形狀匹配的顯著改進。Li等［8］基于內(nèi)在形狀上下文針對特征點提出了一種獨特的多尺度形狀背景（MSC）等尺度的三維形狀描述和配準(zhǔn)方法，通過對一個稀疏特征點集的檢測驗證了其在兩個公共基準(zhǔn)上的性能有顯著提高。Liu等［9］為了更好地實現(xiàn)軌跡分類的全局不變性，采用球形鄰域?qū)⑿螤钌舷挛淖匀坏財U展到時空域，利用形狀上下文的自適應(yīng)外半徑進行三維形狀特征的提取。該方法的有效性為3DSC匹配方法中特征的提取提供了有利的證明。Xu等［10］結(jié)合內(nèi)在形狀特征（ISS）和3DSC提出了一種改進的迭代最近點算法。采用體素網(wǎng)格濾波器進行降采樣，然后利用ISS算法提取特征點并由3DSC描述進行粗配準(zhǔn)，最后利用迭代最近點算法進行精確配準(zhǔn)。實驗結(jié)果表明，該算法具有更快的配準(zhǔn)速度，同時保持了較高的配準(zhǔn)精度。

隨著3DSC理論的深入研究與完善，3DSC配準(zhǔn)方法逐漸在實際生產(chǎn)生活中拓展應(yīng)用。卜琰等［11］為解決自動化裝配中工件自動上下料時匹配識別困難的問題，提出一種基于改進形狀上下文特征的工件識別和定位算法，利用形狀上下文的形狀識別方法檢測工件的外形輪廓，在復(fù)雜環(huán)境下進行配準(zhǔn)從而滿足了工業(yè)作業(yè)中的技術(shù)需要。實驗結(jié)果證明，基于形狀上下文的識別匹配方法能夠適應(yīng)復(fù)雜的環(huán)境，有著很高的精度，能精準(zhǔn)地對工件識別匹配。訾玲玲等［12］提出采用形狀部件的上下文語義關(guān)系進行功能識別的方法，解決了當(dāng)三維形狀的幾何特征和拓?fù)浣Y(jié)構(gòu)發(fā)生較大變化時形狀部件的自動識別問題。實驗結(jié)果表明，相比于已有方法，采用形狀部件的上下文語義關(guān)系進行功能識別的方法可取得更高的部件匹配準(zhǔn)確率和更低的分類錯誤率。Zhu等［13］提出一種基于3DSC的測量手勢相似度的方法，并將其用于手勢識別匹配，為3DSC匹配的發(fā)展運用提供了方向。文獻［14］和文獻［15］對PFH、FPFH和3DSC進行了對比分析，計算了點云的配準(zhǔn)時間和配準(zhǔn)誤差，從數(shù)據(jù)分析中體現(xiàn)出3DSC方法的高精度配準(zhǔn)性能，為高精度行業(yè)機器視覺引導(dǎo)指明了研究方向。由于3DSC配準(zhǔn)時間比較長，其僅適合點云數(shù)據(jù)量比較少的形狀配準(zhǔn)。

3DSC的高精度配準(zhǔn)要以犧牲配準(zhǔn)時間為代價。針對3DSC配準(zhǔn)效率，近年來也有學(xué)者進行研究并提出改進方法。文獻［16］和文獻［17］提出了兩種快速形狀檢索的算法用來快速修剪搜索相似的形狀，但是快速形狀檢索的算法本質(zhì)是對圖像進行多個塊采樣并求其配準(zhǔn)成本，選擇其中配準(zhǔn)代價最小的樣本，錯誤率達(dá)到了10%~14%，對于生產(chǎn)制造行業(yè)中高精度工藝并不適用。文獻［18］展示了如何部署一個獨特的局部參考系來提高3DSC描述符的準(zhǔn)確性和減少內(nèi)存占用，其主要是提升抗噪能力，減少噪點數(shù)據(jù)占用內(nèi)存和噪點對配準(zhǔn)精度的影響，針對噪點較小點云圖像的優(yōu)化并不明顯，與傳統(tǒng)3DSC并沒有太大差異。另外隨著計算機的發(fā)展，也有人提出以GPU并行方式配準(zhǔn)運算的方法，但是效果有限。為進一步提高3DSC的配準(zhǔn)效率且不失配準(zhǔn)精度的高性能，點云圖像數(shù)據(jù)的處理［19］、邊界點云的采集方式［20］以及如何優(yōu)化3DSC算法是難點，也是重點［21］。

本文提出改進的3DSC-ICP點云配準(zhǔn)方法，通過改進輪廓點云降采樣方式實現(xiàn)對三維形狀輪廓特征的提取，對采集的點云依次進行三維網(wǎng)格劃分形成3DSC進行改進的3DSC初始配準(zhǔn)，將丟失的精度通過ICP精確配準(zhǔn)補足，實現(xiàn)了源點云與目標(biāo)點云之間的旋轉(zhuǎn)平移變換，3DSC配準(zhǔn)的速度和精度得到了提升，在提高3DSC配準(zhǔn)效率的同時，也解決了ICP配準(zhǔn)算法陷入局部最優(yōu)的缺點。

2 三維形狀上下文描述符

2.1 二維形狀上下文向三維的擴展

在二維形狀上下文中，基于二維對數(shù)極坐標(biāo)系建立點直方圖，如圖1（a）所示。在3DSC中，通過構(gòu)建基于三維球坐標(biāo)系的點直方圖，將二維形狀上下文描述符擴展到三維空間，如圖1（b）所示。傳統(tǒng)的坐標(biāo)利用笛卡爾坐標(biāo)中的x、y、z來表示點云的每個位置，三維中可以用球坐標(biāo)表示如下：

圖1 二維形狀上下文轉(zhuǎn)三維形狀上下文Fig.1 2DSC extends to 3DSC

一般來說，一個3DSC描述符可以用5個參數(shù)來描述：沿方位角維度的θ、沿徑向維度的r、沿高程維度的φ、外半徑和內(nèi)半徑（外半徑為3DSC球中最外球的半徑，內(nèi)半徑為3DSC球中最內(nèi)球的半徑）。笛卡爾坐標(biāo)中各點的（x、y、z）位置可在球坐標(biāo)中轉(zhuǎn)換為（r、θ、φ），如式（2）所示：

2.2 三維形狀上下文描述符

3DSC使用向量（指定點的描述符）描述指定點及其在曲面上的形狀特征，并通過匹配向量的值建立不同曲面點之間的對應(yīng)關(guān)系。3DSC描述符具體構(gòu)造方法如下：

（1）在以指定點P為中心的球面支撐域中，將網(wǎng)格劃分為3個坐標(biāo)方向：徑向、方向角和俯仰角；

（2）計算落入網(wǎng)格的點數(shù)，并構(gòu)造向量V（點P的描述符），V的每個元素對應(yīng)于三維域中的一個網(wǎng)格，元素的值是相應(yīng)網(wǎng)格中的點數(shù)。3DSC網(wǎng)格劃分如圖2所示。

圖2 三維形狀上下文網(wǎng)格劃分Fig.2 3DSC meshing

3 改進的3DSC點云配準(zhǔn)

3.1 改進的3DSC

傳統(tǒng)形狀上下文配準(zhǔn)對于形狀輪廓采樣一般使用全采樣、隨機采樣和平均采樣的方式。全采樣方式點云數(shù)據(jù)量大，配準(zhǔn)效率慢；隨機采樣和平均采樣的方式會丟失輪廓中具有重要形狀特征的點云數(shù)據(jù)。

本文設(shè)計了閾值降采樣方式（圖3）提取3D圖像的邊界點云，以其中某一點云為起始點0，逆時針方向?qū)吔琰c云排序，并對鄰近兩點云進行向量描述，向量夾角記為βi，閾值即為βi≤π），閾值范圍為

圖3 三維形狀上下文輪廓降采樣Fig.3 Downsampling of 3DSC contours

給定閾值后即可根據(jù)向量角度大小對邊界點云進行篩選采集，提取邊界點云中更具特征的點云。

假設(shè)有λ個輪廓采樣點組成的集合P=｛p1，...，pλ｝，以第i個采樣點pi為坐標(biāo)原點，按照r、θ、φ將三維球域劃分成J×V×W個柵格，其中r的計算方法如式（3）所示：

其中rmin為三維網(wǎng)格劃分中最小球半徑，rmax為三維網(wǎng)格劃分中最大球半徑。

然后用直方圖來表示其余采樣點的分布情況。設(shè)hi（k）為形狀上下文特征，則：

其中：q為剩余的采樣點；bk為第k個柵格，1≤k≤J×V×W。

對于任意兩個點m和n，m屬于源點云形狀點集，n屬于待配準(zhǔn)點云形狀點集，點m與點n的形狀上下文可以表示為直方圖hm（l）和hn（l），其中l(wèi)={1，2，…，L}是柵格的數(shù)量。由此可求得源點云形狀和待配準(zhǔn)點云形狀的相似性度量，即可通過使用χ2來表示的兩個直方圖之間的成本代價Cmn：

兩個形狀上下文的成本值較低意味著兩點之間的相似性較高。

對于曲面配準(zhǔn)，將一對點上的形狀上下文方法應(yīng)用于來自兩個相似曲面（例如源點云形狀和待配準(zhǔn)點云形狀）的一對點集，并應(yīng)用于尋找兩組點之間是否存在點對應(yīng)。與源點云形狀的點和待配準(zhǔn)點云形狀的點之間的每個對應(yīng)關(guān)系可通過式（5）求得。對于源點云形狀中的每個點，待配準(zhǔn)點云形狀的所有點都有相應(yīng)的成本。考慮到待配準(zhǔn)點云形狀中的所有點，可以在這兩個形狀之間定義一個代價矩陣。理想的一組對應(yīng)關(guān)系會使相應(yīng)成本代價的和最小化。這是待配準(zhǔn)點云形狀中的點集，類似于源點云形狀中的相關(guān)點集，可以表示如式（6）所示：

式（6）的結(jié)果是從所有可能的匹配點對的成本求和中找到的成本和最小的一個，因此，本文選擇相似度高的匹配點作為最終的對應(yīng)點。

3.2 點云配準(zhǔn)

將獲取的待配準(zhǔn)點云進行預(yù)處理（歐式聚類提取、半徑濾波），提取目標(biāo)并去除圖像中的噪點。然后設(shè)定閾值，通過改進的降采樣方式采集輪廓點云，對采集的點云依次進行三維網(wǎng)格劃分形成3DSC。接著進行改進的3DSC初始配準(zhǔn)，找到對應(yīng)的匹配點之后，便可以使用SVD算法求解在這種匹配下的旋轉(zhuǎn)和位移矩陣。獲得最優(yōu)初始變換矩陣后，通過所求的旋轉(zhuǎn)平移矩陣更新點云初始位置。至此初始配準(zhǔn)完成，進而采用ICP算法進行精確配準(zhǔn)。

通過ICP算法尋找待匹配點云和目標(biāo)點云之間距離最近的點對集，然后通過最小二乘法迭代計算點對集的最優(yōu)剛性變換參數(shù)。ICP算法的具體實現(xiàn)流程如下：

（1）給定兩個點云集：

A和B之間存在某種旋轉(zhuǎn)關(guān)系R和平移關(guān)系T，求解R和T使點對集中對應(yīng)點的誤差E最小。

（2）尋找A和B中距離最近的點對集，以此計算R和T。根據(jù)R和T計算對應(yīng)點誤差。

（3）若誤差未達(dá)到要求，則繼續(xù)迭代直至滿足誤差要求；若誤差達(dá)到要求，則終止迭代，輸出最優(yōu)解R和T。

改進的3DSC-ICP配準(zhǔn)算法流程如圖4所示。

圖4 改進的3DSC-ICP配準(zhǔn)算法流程Fig.4 Flow chart of improved 3DSC-ICP registration al?gorithm

4 實驗與分析

4.1 實驗環(huán)境

將本文配準(zhǔn)算法與經(jīng)典PFH、FPFH以及傳統(tǒng)形狀上下文配準(zhǔn)算法進行對比實驗，從數(shù)據(jù)預(yù)處理、配準(zhǔn)結(jié)果和配準(zhǔn)誤差3方面進行對比分析，以驗證本文配準(zhǔn)算法的優(yōu)越性。

系 統(tǒng) 環(huán) 境：Windows 10專 業(yè) 版64位；硬 件環(huán)境：Intel Core i5 6300HQ 2.5 GHz，16G內(nèi)存；開發(fā)環(huán)境：Visual Studio 2019。實驗數(shù)據(jù)：（1）斯坦福兔子（Bunny）：源點云數(shù)目40 256，目標(biāo)點云數(shù)目35 336；（2）kinect 3D相機拍攝的花盆點云（Flowerpot）：源點云數(shù)目74 994，目標(biāo)點云數(shù)目70 336。

4.2 點云配準(zhǔn)顯示

4.2.1形狀輪廓點云降采樣顯示

形狀輪廓點云降采樣如圖5與圖6所示。3DSC配準(zhǔn)算法即對輪廓點云進行采樣，以輪廓點云形成形狀上下文進行配準(zhǔn)。3DSC的配準(zhǔn)精度高但配準(zhǔn)時間較長，減少其配準(zhǔn)時間有利于該配準(zhǔn)方法的推廣應(yīng)用。本文設(shè)計了閾值降采樣方式，設(shè)定閾值將源點云輪廓進行采樣，如圖5（c）和圖6（c）所示。相對于全采樣方式，形狀輪廓點云降采樣可有效減少輪廓點云數(shù)量。將點云圖像輪廓以閾值降采樣，既不失形狀特征，又可簡化形狀上下文的運算，達(dá)到減少配準(zhǔn)時間的效果。

圖5 斯坦福兔子形狀輪廓點云降采樣Fig.5 Downsampling of bunny-shaped contour point cloud

圖6 花盆形狀輪廓點云降采樣Fig.6 Downsampling of flowerpot shape contour point cloud

4.2.2改進的3DSC-ICP配準(zhǔn)結(jié)果顯示

采用常用的斯坦福兔子和花盆的點云圖像進行配準(zhǔn)實驗，其中綠色點云為源點云，紅色點云為待配準(zhǔn)點云，藍(lán)色點云為已配準(zhǔn)點云。配準(zhǔn)結(jié)果如圖7和圖8所示，藍(lán)色點云圖與紅色點云圖的重合度體現(xiàn)了配準(zhǔn)的效果。改進的3DSC配準(zhǔn)算法克服了傳統(tǒng)3DSC算法配準(zhǔn)時間長的局限性，在有失配準(zhǔn)精度的初始配準(zhǔn)下，通過ICP精確配準(zhǔn)保證了配準(zhǔn)精度，提高了3DSC的點云配準(zhǔn)效率。

圖7 斯坦福兔子配準(zhǔn)結(jié)果Fig.7 Registration result of bunny

圖8 花盆配準(zhǔn)結(jié)果Fig.8 Registration result of flowerpot

4.3 數(shù)據(jù)分析

基于斯坦福兔子和花盆點云圖像進行配準(zhǔn)數(shù)據(jù)分析，將本文改進算法和傳統(tǒng)3DSC方法進行對比。表1數(shù)據(jù)對比顯示，通過設(shè)定閾值可有效減少輪廓點云數(shù)量，保留輪廓形狀特征的同時也減少了配準(zhǔn)時間。表2為配準(zhǔn)方法的配準(zhǔn)時間和配準(zhǔn)精度比較。本文算法相對于傳統(tǒng)3DSC方法在時間上得到了明顯的優(yōu)化。針對斯坦福兔子和花盆點云圖像，傳統(tǒng)3DSC算法配準(zhǔn)時間為151.676 s和146.236 s，本文算法將配準(zhǔn)時間降到28.181 s和20.856 s，節(jié)省了近75%~85%的配準(zhǔn)時間。表2和表3將本文改進的3DSC-ICP配準(zhǔn)方法與FPFH-ICP、PFH-ICP以及傳統(tǒng)3DSC配準(zhǔn)方法相比較，配準(zhǔn)精度可提高2~3倍，本文改進算法配準(zhǔn)誤差、配準(zhǔn)精度占有絕對的優(yōu)勢。實驗證明本文改進的3DSC-ICP配準(zhǔn)算法具有很大優(yōu)越性，改善了3DSC的配準(zhǔn)效率。

表1 數(shù)據(jù)預(yù)處理對比Tab.1 Comparison of data preprocessing

表2 配準(zhǔn)時間和配準(zhǔn)精度對比Tab.2 Comparison of registration time and registration accuracy

表3 配準(zhǔn)誤差對比Tab.3 Comparison of registration errors

5 結(jié) 論

3DSC以采集三維形狀輪廓點云為基準(zhǔn)，對每個采集點云進行上下文描述，若輪廓點云密集且數(shù)量集很大，數(shù)據(jù)運算量將會嚴(yán)重影響配準(zhǔn)效率。對輪廓點云集以合理方式進行采樣，有助于提高配準(zhǔn)速度，減少配準(zhǔn)時間。經(jīng)典的3DSC一般以全采樣或平均采樣的方式進行采樣，從而形成形狀上下文，也有對輪廓點云歸一化處理的研究。平均采樣和歸一化的研究方法雖然能夠優(yōu)化配準(zhǔn)時間，但是配準(zhǔn)精度卻是大打折扣，以至于這些方式并不能廣泛應(yīng)用。本文對于三維形狀輪廓點云改進采樣方式，可針對不同的應(yīng)用場景設(shè)置采樣閾值，對輪廓點云集中角度變化較大的點云進行采集，保證了輪廓圖像形狀，有助于提高配準(zhǔn)效率。本文提出的改進3DSC的配準(zhǔn)算法在配準(zhǔn)精度和配準(zhǔn)時間上可做出平衡選擇，降低輪廓采樣減少傳統(tǒng)3DSC配準(zhǔn)時間的同時通過ICP精配準(zhǔn)補足了配準(zhǔn)精度的缺失。與傳統(tǒng)3DSC配準(zhǔn)算法相比，改進的3DSC配準(zhǔn)算法可節(jié)省75%~85%的配準(zhǔn)時間；與常用的PFH-ICP、FPFH-ICP配準(zhǔn)算法相比，配準(zhǔn)精度可提高2~3倍，為機器視覺在工業(yè)生產(chǎn)制造中開拓更廣應(yīng)用的同時也驗證了3DSC配準(zhǔn)在高精度工業(yè)運用的可能性。