(1.中國船舶重工集團公司第七一八研究所，河北 邯鄲 056000； 2.華中科技大學 機械科學與工程學院，湖北 武漢 430074)

圖像匹配技術又稱圖像配準、圖像對齊技術，其在復雜零件的加工、檢測、逆向工程、圖像處理以及模式識別等領域有著重要的應用[1-4]。圖像匹配技術以三維點集為研究對象，通過剛體轉換矩陣把處在不同坐標系中的兩片或多片點集匹配到同一坐標系內，并使對齊誤差最小。

匹配技術最早是在70年代美國軍事研究中提出的。20世紀80年代后，不同領域的學者對數據匹配進行了深入研究，提出了許多改進方法并得到了廣泛的應用[5-6]。目前，應用最為廣泛的匹配算法是1992年Bsel等人提出的ICP(Iterative Closest Point)算法[7]，該算法通過計算兩片點集中對應點的距離，能夠快速找到一個合適的剛體變換矩陣，使得點對間的距離和最小。但ICP算法對待匹配的兩片點云的初始位置有特定要求。此外，由于該算法以最小二乘法來求解變換矩陣，對于一些復雜的點云數據，該算法的求解結果易陷入局部最優(yōu)。因此，近幾年不少學者對ICP算法的收斂速度和收斂性進行了較多研究[8-10]。

隨著計算機技術的發(fā)展，啟發(fā)式算法的研究取得了巨大的成就，其良好的尋優(yōu)能力及收斂性能在三維點云匹配研究領域也得到了廣泛的應用。Lee[11]等人采用遺傳編程算法刪除深度圖像匹配過程中的異常點； Cai[12]等人利用分支定界方法來解決LiDAR掃描圖像的匹配問題；Casella[13]等人提出一種自適應分布式差分進化算法來解決深度圖像的匹配問題并利用GPUs來加速計算過程；Corden[14-16]等人利用多種智能算法解決圖像匹配問題，尤其在醫(yī)學圖像處理領域取得了較大的進展。

本文利用改進的差分進化算法解決曲面零件匹配檢測問題，通過種群進化來搜索最優(yōu)的旋轉和平移矩陣。本算法對點集的初始位置不敏感，能夠有效解決ICP算法易陷入局部最優(yōu)的問題。此外，該算法收斂速度快、魯棒性好，在曲面零件加工及檢測環(huán)節(jié)能夠有效降低測量誤差對尺寸檢測及加工余量檢測的影響，滿足生產節(jié)拍要求。

1 點云匹配模型

所研究的圖像是深度圖像，即通過非接觸式光學掃描儀獲得的圖像。相比較于傳統(tǒng)的接觸式三坐標測量儀，非接觸式掃描儀具有測量速度快、對工件材質無要求以及測量視角廣等優(yōu)點。三維圖像匹配框架如圖1所示，從圖中可以看出，匹配的幾個關鍵步驟主要包括：點集輸入、計算轉換矩陣、模型位置更新及誤差判定。

圖1 匹配檢測流程圖

假定工件在設計坐標系下的模型點集為Q，Q={qi}，i=1,…,nq。其中，nq為設計點集中點的個數；工件掃描坐標系下模型點集為P，P={pi}，i=1,…,np，其中，np為掃描點集中點的個數，np=nq。式(1)表示對P中的點進行旋轉和平移操作。

f(pi)=R(pi)+T，i={1,…,np}

(1)

式中，R為對點集中的一點執(zhí)行旋轉操作；T為對點集中的一點執(zhí)行平移操作。現使設計坐標系下的點集Q保持不動，通過對點集P中的所有點執(zhí)行旋轉和平移操作，使得兩片點集中的對應點進行匹配。該操作的目標是找到一個最優(yōu)的變換矩陣f*，使得變換后，兩片點集間的各點距離和最小，如式(2)所示。

(2)

經相似度測量，使得式(3)中的F值最小。

(3)

由于實際中較難獲得兩片點云間精確的對應關系，一般采用增加點數來提高變換矩陣的計算精度。在ICP及其相關的改進算法中，對于旋轉矩陣R和平移矩陣T的求解，目前采用最多的是奇異值分解法。這種方法需要計算點集的重心，并構造協方差矩陣，通過求取最大特征值或最大特征向量首先解得旋轉矩陣R，并根據式(4)求得平移矩陣。

T=μQ-RμP

(4)

式中，μQ、μP分別為Q、P點集的重心。

2 改進差分進化算法

差分進化算法(Differential Evolution,DE)[17]是一種并行搜索方法，常用于求解非線性連續(xù)空間函數的優(yōu)化問題。DE算法通過個體的選擇、交叉和變異過程進行種群的更新。

2.1 算法編碼

利用改進的差分進化算法解決點云匹配檢測問題，并把需要求解的3個旋轉變量和3個平移變量定義為種群個體，如式(5)所示。

(5)

式中，Np為種群大??；txi、tyi、tzi分別為沿x、y、z軸的平移量；rxi、ryi、rzi分別為沿x、y、z軸的旋轉量。其中，對于各平移變量的正負值表示沿各坐標軸的正負方向；對于各旋轉變量的正值表示繞各坐標軸順時針方向旋轉，負值表示繞各坐標軸逆時針方向旋轉。

2.2 變異策略

差分進化算法在種群進化過程中有多個變異策略可選，當用于解決匹配問題時，復雜的變異策略將降低算法的計算效率。基于點云匹配問題的特性，在可接受的計算精度范圍內設計了一種新的變異策略。 “DE/rand/2/bin” 策略是根據隨機選擇的5個個體進行種群的更新，具有較好的全局搜索能力。“DE/best/2/bin” 策略生成新的個體時是根據當前最好的個體來生成的，該策略具有較強的局部搜索能力。本文結合這兩種策略的優(yōu)勢，設計了一種新差分進化算法，簡稱FDE。根據每個個體計算得到的適應度值，把個體分為“good”個體和“bad”個體。其中，對于“bad”個體采用“DE/rand/2/bin”策略進行變異，對于“good”個體采用 “DE/best/2/bin”策略來進行變異，該混合策略能夠顯著提高算法的可靠性。定義分類因子為λ,且λ∈(0,1)，“good”個體和“bad”個體的種群數量采用式(6)進行計算。

(6)

式中，round( )為隨機操作，種群個體按式(7)和式(8)進行更新。

vbad,i,G=xr1,G+F·(xr2,G-xr3,G)+F·(xr4,G-xr5,G)

(7)

vgood,j,G=xbest,G+F·(xr6,G-xr7,G)+F·(xr8,G-xr9,G)

(8)

式中，i∈[1,NPbad]；r1～r5為在[1,NPbad]區(qū)間內隨機選擇的個體且不等于i；j∈[1,NPgood]；r6～r9是在[1,NPgood] 范圍內隨機選擇的個體，且不等于j；xbest,G為當前種群內的最好個體。本文中，比例因子的選擇方法為[18]

(9)

式中，F0為個常量；Gmax為最大迭代次數；G為當前進化次數，且G=1,2,…,Gmax。

3 實驗及結果分析

如圖2所示，采用5個復雜曲面零件模型進行試驗。從左到右，從上到下依次為葉片1、葉片2、法蘭、汽車，以及氣道模型。針對每個模型的掃描點云采用均勻法進行采樣，采樣個數為1000。

為驗證本文所提算法對復雜初始位置的有效性，和文獻[19]的試驗方法一樣，本文利用掃描模型經一定空間變換T轉換后再對齊到其原始掃描模型。為增加模型初始位置的復雜性，按表1設置了3個初始位置，表中，L為模型空間尺寸(長、寬、高)的最大值。

表1 預設轉換矩陣

為驗證本文方法的魯棒性，在轉換后的模型上增加了20個噪聲點，并將本文所提方法與 ICP[7]、SICP[20]、IRLS[21]、ADF[19]、DE等5種方法進行了對比。在ICP、SICP、IRLS和ADF算法中最大迭代次數設置為50。結合本文問題的計算效率要求，算法的最大函數評價次數設置為30000。對于DE和FDE個體數量設置為50，最大迭代次數為Itermax=6000。經定量比較的匹配結果如表2所示。表中加粗數據表示計算結果的最優(yōu)值。

從表2可以看出，對于本文采用的5個曲面零件模型，ICP和SICP算法隨著模型初始位置復雜程度的提高，其計算誤差逐漸增大。對于葉片2模型，在T1和T2位置情形下ICP、IRLS和FDE算法均能獲得全

圖2 各模型初始位置圖

單位：mm

局最優(yōu)解。但在T3位置情形下，前兩種方法由于搜索能力有限其計算結果已陷入局部最優(yōu)，而FDE算法對模型的初始位置不敏感，在較復雜的T3情形下仍能保持較強的全局搜索能力。相對來說，ADF算法采用自適應計算策略其結果要優(yōu)于ICP、SICP、IRLS和DE算法，但由于ADF本質上仍屬于確定性算法，其全局搜索能力有限。通過以上對比發(fā)現，所提出的FDE算法在計算精度、搜索能力以及魯棒性等方面均優(yōu)于其他5種方法。

圖3～圖7為各算法在T3初始位置時所計算得到的匹配結果，其中各圖(a)～圖(f)依次為ICP、SICP、IRLS、ADF、DE、FDE算法的匹配結果。

圖3～圖7定性比較了各算法在T3位置情形下的匹配結果。從這些匹配結果中可以看出，ICP算法對葉片1和法蘭模型的匹配結果誤差較大，經空間轉換后待匹配的兩模型仍存在明顯的位置偏差。SICP算法雖在葉片1模型獲得較好的匹配結果，但對于汽車模型該算法計算結果誤差較大，算法通用性差。在該對比條件下，ADF算法計算結果優(yōu)于IRLS算法，但這兩種方法易受噪聲點的影響，計算結果為局部最優(yōu)解。啟發(fā)式算法DE和FDE采用隨機搜索機制具有較強的全局搜索能力，在該對比條件下兩者的計算結果明顯優(yōu)于其他4種算法。但是，DE算法所得結果在模型邊界處的匹配誤差較大，相比較來說，FDE算法所得結果更優(yōu)。

圖3 葉片1模型匹配結果

圖4 葉片2模型匹配結果

圖5 法蘭模型匹配結果

圖6 汽車模型匹配結果

圖7 氣道模型匹配結果

4 結束語

本文針對復雜曲面零件的結構特性，利用改進的差分進化算法求解模型匹配問題，有效解決了曲面零件的質量檢測中匹配誤差對檢測精度的影響問題。通過對算法種群編碼方式、個體變異策略的選擇等方面的深入分析與改進，大大提高了個體的尋優(yōu)能力。本文所提方法可有效解決ICP算法易陷入局部最優(yōu)的問題，且本方法對點集的初始位置不敏感，算法收斂速度快、魯棒性好。本文算法所得結果能夠保證為全局最優(yōu)解，為復雜曲面零件的質量檢測提供可靠的精度保障。