胡凡建

(1. 湖北第二師范學(xué)院 物理與機(jī)電學(xué)院, 武漢 430205；2. 華中科技大學(xué) 材料成形與模具技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢 430074)

?

基于三角網(wǎng)格表示的點(diǎn)云匹配算法

胡凡建1, 2

(1. 湖北第二師范學(xué)院 物理與機(jī)電學(xué)院, 武漢 430205；2. 華中科技大學(xué) 材料成形與模具技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢 430074)

摘要：針對傳統(tǒng)的匹配方法收斂速度慢、對初值敏感的問題，本文提出了一種基于三角網(wǎng)格表示的點(diǎn)云匹配算法。該算法主要包括兩個(gè)步驟：首先，采用主成份分析對點(diǎn)云進(jìn)行整體分析，通過奇異值分解計(jì)算初始變換參數(shù)；然后，采用螺旋運(yùn)動理論在三角網(wǎng)格模型中定義點(diǎn)-切面距離以構(gòu)造目標(biāo)函數(shù)，并通過求解一個(gè)線性方程組計(jì)算最優(yōu)剛體變換參數(shù)。實(shí)驗(yàn)結(jié)果證明了本文所提算法的有效性。

關(guān)鍵詞：匹配；剛體變換；主成份分析；螺旋運(yùn)動

近年來，高精度的接觸式或非接觸式測量方法在汽車覆蓋件、航空發(fā)動機(jī)葉片等曲面類零件的加工制造中廣泛應(yīng)用。然而，受測量設(shè)備自由度和視場限制，需多次測量才能獲取整體數(shù)據(jù)。點(diǎn)云匹配目的就是計(jì)算三維空間的剛體變換參數(shù)，將不同坐標(biāo)系下的點(diǎn)云數(shù)據(jù)統(tǒng)一到同一平臺下。點(diǎn)云匹配(也稱對齊或拼合)技術(shù)在逆向工程、曲面尋位、質(zhì)量檢測和文物保護(hù)等領(lǐng)域均有著廣泛應(yīng)用，已成為這些領(lǐng)域的研究熱點(diǎn)也是難點(diǎn)問題之一。

點(diǎn)云匹配可分為粗匹配(Coarse Registration)算法和精匹配(Fine Registration)算法兩類[1]。粗匹配利用曲面特征構(gòu)造幾何不變量，在不同視圖搜索對應(yīng)點(diǎn)完成匹配。Johnson和Hebert[2]提出了Spin-Image方法，利用法線距離和切平面距離構(gòu)造了二維幾何不變量；斯坦福大學(xué)的Gelfand等[3]構(gòu)造體積不變量解決米開朗琪羅工程中的匹配問題；Masuda使用局部高度映射構(gòu)造了LPHM搜索對應(yīng)點(diǎn)[4]。上述粗匹配算法需對目標(biāo)視圖中的所有點(diǎn)構(gòu)造不變量，匹配效率較低。近年來，Yamany[5]、Maekawa[6]、孫玉文[7]、劉宇[8]等學(xué)者提取微分信息構(gòu)造不變量。然而微分信息對噪聲敏感，處理由許多相似區(qū)域構(gòu)成的曲面時(shí)，會產(chǎn)生多重對應(yīng)，導(dǎo)致匹配失敗。

ICP算法(Iterative Closest Point)[9]及其改進(jìn)算法[10]是目前應(yīng)用最廣泛的基于迭代策略的精匹配算法。該算法定義點(diǎn)-點(diǎn)歐式距離作為目標(biāo)函數(shù)，通過奇異值分解得到最大特征值對應(yīng)的特征向量計(jì)算旋轉(zhuǎn)變換參數(shù)，進(jìn)而由質(zhì)心坐標(biāo)計(jì)算平移變換參數(shù)。ICP算法無需構(gòu)造幾何不變量，線性收斂于局部最優(yōu)解，其主要缺點(diǎn)是收斂速度慢，收斂精度與初值有關(guān)。從幾何優(yōu)化的角度，Pottmann等[11]提出了TDM(Tangent Squared Distance Minimization)和SDM(Squared Distance Minimization)算法。TDM算法使用點(diǎn)-切面距離構(gòu)造目標(biāo)函數(shù)，由于無需計(jì)算曲率值，相比SDM算法應(yīng)用更為廣泛。Pottmann等證明了TDM算法比ICP算法收斂速度快，但對初值非常敏感。當(dāng)點(diǎn)云相距較遠(yuǎn)時(shí)，算法易陷入局部最優(yōu)甚至發(fā)散。此外，Chow[12]、Salvi[13]等提出了基于遺傳方法的精匹配算法，盡管該類方法對初值無要求，但計(jì)算效率低。

在上述工作的基礎(chǔ)上，本文提出了一種基于三角網(wǎng)格表示的匹配算法。本算法包括兩個(gè)主要步驟：首先，使用主成份分析(PCA：Principal Component Analysis)獲取移動視圖與目標(biāo)視圖的笛卡爾坐標(biāo)系統(tǒng)，計(jì)算初始旋轉(zhuǎn)變換和平移變換參數(shù)；然后，在網(wǎng)格曲面上定義點(diǎn)-切面距離，由螺旋運(yùn)動理論將匹配問題定義為非線性最小二乘問題，并通過求解線性方程組計(jì)算最優(yōu)剛體變換參數(shù)。

1初始剛體變換參數(shù)的計(jì)算

1.1數(shù)據(jù)預(yù)處理

為了提高三角網(wǎng)格的質(zhì)量，在匹配前需對直接測量的數(shù)據(jù)進(jìn)行預(yù)處理。點(diǎn)云數(shù)據(jù)預(yù)處理的內(nèi)容包括去除噪聲、修補(bǔ)空洞、網(wǎng)格三角化和網(wǎng)格細(xì)分等。對于粗大噪聲，可在商業(yè)化軟件(如Geomagic、Polyworks等)中由人工交互直接去除。對于高斯噪聲、空洞和稀疏網(wǎng)格，可使用Geomagic軟件中相應(yīng)模塊進(jìn)行操作。將處理后的網(wǎng)格曲面存為PLY文件，以便于不同軟件平臺中的轉(zhuǎn)換和傳輸。PLY文件格式是美國斯坦福大學(xué)開發(fā)的數(shù)據(jù)存儲格式，圖形學(xué)領(lǐng)域很多著名的模型 (如兔子、米開朗琪羅和中國龍等)均采用該格式存儲。

1.2曲面PCA

圖1　在三角網(wǎng)格中計(jì)算權(quán)重系數(shù)

定義移動點(diǎn)云P={p1,p2,…,pnp}、目標(biāo)點(diǎn)云Q={q1,q2,…,qnQ}。如圖1所示，對于網(wǎng)格曲面P中任意pi，定義環(huán)繞pi點(diǎn)一周內(nèi)的三角形頂點(diǎn)為Vi={v1,v2,…,vni}，三角形Fi={f1,f2,…,fni}的面積分別為{a1,a2，…,ani}。計(jì)算P的質(zhì)心μP及坐標(biāo)差pi

pi=pi-μp

(1)

(2)

對矩陣Hp進(jìn)行奇異值分解，得

(3)

(4)

式中R0∈R3×3,(R0)T=(R0)-1,det(R0)=1。進(jìn)而求解初始平移變換參數(shù)

t0=μQ-RμP

(5)

式中t0∈R3。求得的剛體變換參數(shù)g0=(R0,t0)可作為下節(jié)精匹配的初始值，由迭代策略進(jìn)一步計(jì)算最優(yōu)剛體變換參數(shù)。需要特別指出的是通過本節(jié)方法計(jì)算初始變換參數(shù)時(shí)，只需構(gòu)造一個(gè)協(xié)方差矩陣，由奇異值分解計(jì)算正交單位矢量。不需要對移動點(diǎn)云中所有點(diǎn)構(gòu)造幾何不變量，同時(shí)也不需要定義嚴(yán)格的相似性度量指標(biāo)，計(jì)算簡單。

2基于螺旋運(yùn)動的精匹配算法

任何物體從一個(gè)位姿到另一個(gè)位姿的運(yùn)動都可以表示為繞某直線的轉(zhuǎn)動和沿此直線移動的復(fù)合實(shí)現(xiàn)，這種復(fù)合運(yùn)動稱為螺旋運(yùn)動，因此，剛體變換參數(shù)可由螺旋運(yùn)動表示和求解。本節(jié)將提出一種基于螺旋運(yùn)動的精匹配算法-ScrewMotion-basedFineRegistration(SMFR)。

2.1螺旋運(yùn)動基礎(chǔ)

定義單參數(shù)螺旋運(yùn)動坐標(biāo)系為∑P/∑Q，則

pi(t)=R(t)pi+t(t)

(6)

上式表示在時(shí)刻t，將移動坐標(biāo)系∑P中的點(diǎn)pi映射到目標(biāo)坐標(biāo)系∑Q中。∑P中所有的點(diǎn)在∑Q有一條路徑曲線，該曲線的原點(diǎn)為pi，曲線形狀由變換參數(shù)R(t),t(t)控制。對式(6)求導(dǎo)，得

v(pi)=R(t)pi+t(t)

(7)

v(pi)表示t時(shí)刻點(diǎn)pi在∑Q中描述的速度矢量。對式(7)進(jìn)行線性化表示[14]，可得

(8)

pi=pi+v(pi)

(9)

(1) 如果l=0，則該運(yùn)動為平移運(yùn)動；

圖2　 瞬時(shí)螺旋運(yùn)動中的幾何量,其中點(diǎn)位置由線性擬合得到

2.2目標(biāo)函數(shù)定義

圖3　點(diǎn)-切面距離誤差定義

如圖3(a)所示，對于?pi∈P，在目標(biāo)點(diǎn)云Q搜索其距離最近點(diǎn)qj，滿足

(10)

由于網(wǎng)格曲面中含有三角形曲面片的方向矢量，點(diǎn)qj處的法向矢量nj由下式擬合

(11)

式中，ak表示環(huán)繞pi點(diǎn)三角形曲面片的面積，nk表示對應(yīng)三角形的法矢。測量的離散數(shù)據(jù)具有一定的采樣分辨率，大多數(shù)情況下點(diǎn)pi不在nj上，所以點(diǎn)pi到切平面Tj的距離為jj(pi-qj)。經(jīng)過空間運(yùn)動后，pi點(diǎn)位置變?yōu)閜i，此時(shí)點(diǎn)-切面距離為

(12)

考慮到pi點(diǎn)的影響程度，引入權(quán)重系數(shù)定義精匹配算法的目標(biāo)函數(shù)

(13)

2.3變換參數(shù)求解

(14)

=C+2BTS+STAS

(15)

AS+B=0

(16)

在微分運(yùn)動條件下，剛體變換參數(shù)由下式?jīng)Q定[14]

(17)

3計(jì)算復(fù)雜度分析

本文所提出的點(diǎn)云匹配算法整體步驟如下：

(1) 求解初始變換矩陣g0=(R0,t0)，完成移動點(diǎn)云P同目標(biāo)點(diǎn)云Q的初步匹配。

(a) 查詢圍繞點(diǎn)pi的曲面片，計(jì)算權(quán)重系數(shù)wi；

(c) 根據(jù)式(4-5)，計(jì)算初始旋轉(zhuǎn)變換參數(shù)R0和平移變換參數(shù)t0。

(a) 更新pi點(diǎn)位置，對于?pi∈P搜索最近點(diǎn)qj；

(b) 查詢圍繞點(diǎn)qj一周的三角形面片，確定法矢量nj；

(d) 求解式(16)中線性方程組計(jì)算變量S，按式(17)計(jì)算剛體變換參數(shù)g=(R,t)；

(e) 分析是否滿足終止條件，如果滿足則輸出最優(yōu)剛體變換參數(shù)g*=(R*,t*)；否則轉(zhuǎn)(2-a)循環(huán)。

4實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文所提算法的有效性，采用具有復(fù)雜曲面特征的殼體零件為例進(jìn)行仿真實(shí)驗(yàn)。移動點(diǎn)云P采用Salvi的方法[1]由Q沿坐標(biāo)軸旋轉(zhuǎn)和平移產(chǎn)生，旋轉(zhuǎn)角度和平移距離分別為45°、3mm。為了測試算法對噪音的魯棒性，在點(diǎn)云數(shù)據(jù)中加入了高斯噪音N(0.05,0.01)2，同時(shí)在移動點(diǎn)云中去除1/5左右的數(shù)據(jù)。仿真實(shí)驗(yàn)結(jié)果見圖4和圖5，從實(shí)驗(yàn)結(jié)果可以看出在所有測試算法中PCA+SMFR算法是收斂速度最快且匹配精度最高的。在初值較差的情況下，使用點(diǎn)-點(diǎn)距離的ICP算法經(jīng)過20步迭代后均值誤差仍沒有達(dá)到穩(wěn)定值。本文所提算法首先使用PCA計(jì)算一個(gè)初始變換參數(shù)，在此初值下使用SMFR在5步迭代內(nèi)快速達(dá)到最優(yōu)值。

本實(shí)驗(yàn)使用PCA+SMFR算法后獲得的最終剛體變換參數(shù)和均值誤差見表1。盡管跟ICP算法具有相似的計(jì)算復(fù)雜度，但由于PCA+SMFR算法收斂速度快，獲得最優(yōu)剛體變換變換參數(shù)的計(jì)算耗時(shí)遠(yuǎn)小于ICP算法。

圖5　使用殼體模型比較均值誤差

粗匹配精匹配旋轉(zhuǎn)參數(shù)R0.4646-0.10580.87920.59470.7729-0.2213-0.65610.62570.4220?è???÷0.4938-0.17360.85210.51130.8505-0.1230-0.70340.49640.5087?è???÷平移參數(shù)t(4.2831,6.0692,5.4735)(4.8251,5.0732,4.9486)均值誤差(mm)0.98250.2613

5結(jié)論

(1) 提出了一種基于三角網(wǎng)格表示的點(diǎn)云匹配算法。該算法首先執(zhí)行PCA完成初始匹配，然后執(zhí)行SMFR計(jì)算最優(yōu)剛體變換參數(shù)。使用主成份分析快速計(jì)算出初始旋轉(zhuǎn)變換參數(shù)，解決了精匹配算法對初值敏感的問題。此外，該算法不需要重新計(jì)算法矢、曲率等微分信息，穩(wěn)定性好。

(2) 分析了本文所提算法的計(jì)算復(fù)雜度，并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的匹配效率和精度。實(shí)驗(yàn)結(jié)果表明，本文所提算法比ICP更快的收斂于最優(yōu)解，快速準(zhǔn)確的完成了移動點(diǎn)云與目標(biāo)點(diǎn)云的匹配任務(wù)。

(3) 需特別指出的是本文所提算法使用條件同ICP相似：要求移動點(diǎn)云為目標(biāo)點(diǎn)云的子集。當(dāng)該條件不成立時(shí)，可先由Huber和Hebert[15]的方法查詢重疊區(qū)域后，再使用本文所提算法進(jìn)行匹配。

參考文獻(xiàn):

[1]SALVI J, MATABOSCH C, FOFI D, et al. A review of recent range image registration methods with accuracy evaluation[J]. Image and Vision Computing, 2007, 25(5): 578-596.

[2]JOHNSON A E, HEBERT M. Surface matching for object recognition in complex three-dimensional scenes[J]. Image and Vision Computing, 1998, 16(9-10): 635-651.

[3]GELFAND N, MITRA N J, GUIBAS L J, et al. Robust global registration[C].Proceedings of the Symposium on Geometry Processing, 2005, Vienna, Austria: 197-206.

[4]MASUDA T. Log-polar height maps for multiple range image registration[J]. Computer Vision and Image Understanding, 2009, 113(11): 1158-1169.

[5]YAMANY S M, FARAG A A. Surface signatures: An orientation independent free-form surface representation scheme for the purpose of objects registration and matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(8): 1105-1120.

[6]KO K H, MAEKAWA T, PATRIKALAKIS N M. An algorithm for optimal free-form object matching[J]. Computer-Aided Design, 2003, 35(10): 913-923.

[7]徐金亭, 孫玉文, 劉偉軍. 復(fù)雜曲面加工檢測中的精確定位方法[J]. 機(jī)械工程學(xué)報(bào), 2007, 43(6): 175-179.

[8]劉宇, 熊有倫. 基于法矢的點(diǎn)云匹配方法[J]. 機(jī)械工程學(xué)報(bào), 2007, 43(8): 7-11.

[9]BESL P J, MCKAY H D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[10]LIU Y. Improving ICP with easy implementation for free-form surface matching[J]. Pattern Recognition, 2004, 37(2): 211-226.

[11]POTTMANN H, HUANG Q-X, YANG Y-L, et al. Geometry and convergence analysis of algorithms for registration of 3D shapes[J]. International Journal of Computer Vision, 2006, 67(3): 277-296.

[12]SILVA L, BELLON O R P, BOYER K L. Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 762-776.

[13]CORDON O, DAMAS S, SANTAMARIA J. A fast and accurate approach for 3D image registration using the scatter search evolutionary algorithm[J]. Pattern Recognition Letters, 2006, 27(11): 1191-1200.

[14]熊有倫, 尹周平, 熊蔡華, 等. 機(jī)器人操作[M]. 武漢: 湖北科學(xué)技術(shù)出版社, 2002.

[15]HUBER D. F., HEBERT M. Fully automatic registration of multiple 3D data sets[J]. Image and Vision Computing, 2003, 21(7): 637-650.

A Registration Algorithm For Point Clouds Based on The Triangular Representation

HU Fan-jian1,2

(1. Hubei University of Education, Wuhan 430205, China;2. State Key Laboratory of Materials Processing and Die & Mould Technology,Huazhong University of Science & Technology, Wuhan 430074, China)

Abstract:This paper proposes a novel registration algorithm based on the triangular representation, aiming to handle the problems of slow convergence and existing sensibility to initial value in traditional algorithms. The proposed algorithm consists of two major steps: First, Principal Component Analysis is used to analyze the data, then the Singular Value decomposition is used to calculate the initial transformation parameters; Second, the theory of screw motion is employed to define the point-tangent distance in triangles in order to construct the objective function which is calculated to obtain the optimal rigid transformation parameters by solving a series of linear systems. The validity of the proposed algorithm is verified by the experiment.

Key words:matching; rigid transformation; principal component analysis; screw motion

收稿日期：2016-01-10

作者簡介：胡凡建(1981-)，男，湖北咸寧人，博士研究生，研究方向?yàn)椴牧霞庸すこ獭?/p>

中圖分類號：TH14

文獻(xiàn)標(biāo)識碼：A

文章編號：1674-344X(2016)02-0016-06