基于改進三維形狀上下文的點云配準

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

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

1 引 言

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

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

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

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

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

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

2 三維形狀上下文描述符

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

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

圖1 二維形狀上下文轉三維形狀上下文Fig.1 2DSC extends to 3DSC

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

2.2 三維形狀上下文描述符

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

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

（2）計算落入網格的點數，并構造向量V（點P的描述符），V的每個元素對應于三維域中的一個網格，元素的值是相應網格中的點數。3DSC網格劃分如圖2所示。

圖2 三維形狀上下文網格劃分Fig.2 3DSC meshing

3 改進的3DSC點云配準

3.1 改進的3DSC

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

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

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

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

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

其中rmin為三維網格劃分中最小球半徑，rmax為三維網格劃分中最大球半徑。

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

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

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

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

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

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

3.2 點云配準

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

通過ICP算法尋找待匹配點云和目標點云之間距離最近的點對集，然后通過最小二乘法迭代計算點對集的最優剛性變換參數。ICP算法的具體實現流程如下：

（1）給定兩個點云集：

A和B之間存在某種旋轉關系R和平移關系T，求解R和T使點對集中對應點的誤差E最小。

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

（3）若誤差未達到要求，則繼續迭代直至滿足誤差要求；若誤差達到要求，則終止迭代，輸出最優解R和T。

改進的3DSC-ICP配準算法流程如圖4所示。

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

4 實驗與分析

4.1 實驗環境

將本文配準算法與經典PFH、FPFH以及傳統形狀上下文配準算法進行對比實驗，從數據預處理、配準結果和配準誤差3方面進行對比分析，以驗證本文配準算法的優越性。

系 統 環 境：Windows 10專 業 版64位；硬 件環境：Intel Core i5 6300HQ 2.5 GHz，16G內存；開發環境：Visual Studio 2019。實驗數據：（1）斯坦福兔子（Bunny）：源點云數目40 256，目標點云數目35 336；（2）kinect 3D相機拍攝的花盆點云（Flowerpot）：源點云數目74 994，目標點云數目70 336。

4.2 點云配準顯示

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

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

圖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配準結果顯示

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

圖7 斯坦福兔子配準結果Fig.7 Registration result of bunny

圖8 花盆配準結果Fig.8 Registration result of flowerpot

4.3 數據分析

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

表1 數據預處理對比Tab.1 Comparison of data preprocessing

表2 配準時間和配準精度對比Tab.2 Comparison of registration time and registration accuracy

表3 配準誤差對比Tab.3 Comparison of registration errors

5 結 論

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