基于改進(jìn)差分進(jìn)化算法的曲面零件匹配檢測(cè)研究

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

圖像匹配技術(shù)又稱圖像配準(zhǔn)、圖像對(duì)齊技術(shù)，其在復(fù)雜零件的加工、檢測(cè)、逆向工程、圖像處理以及模式識(shí)別等領(lǐng)域有著重要的應(yīng)用[1-4]。圖像匹配技術(shù)以三維點(diǎn)集為研究對(duì)象，通過剛體轉(zhuǎn)換矩陣把處在不同坐標(biāo)系中的兩片或多片點(diǎn)集匹配到同一坐標(biāo)系內(nèi)，并使對(duì)齊誤差最小。

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

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

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

1 點(diǎn)云匹配模型

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

圖1 匹配檢測(cè)流程圖

假定工件在設(shè)計(jì)坐標(biāo)系下的模型點(diǎn)集為Q，Q={qi}，i=1,…,nq。其中，nq為設(shè)計(jì)點(diǎn)集中點(diǎn)的個(gè)數(shù)；工件掃描坐標(biāo)系下模型點(diǎn)集為P，P={pi}，i=1,…,np，其中，np為掃描點(diǎn)集中點(diǎn)的個(gè)數(shù)，np=nq。式(1)表示對(duì)P中的點(diǎn)進(jìn)行旋轉(zhuǎn)和平移操作。

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

(1)

式中，R為對(duì)點(diǎn)集中的一點(diǎn)執(zhí)行旋轉(zhuǎn)操作；T為對(duì)點(diǎn)集中的一點(diǎn)執(zhí)行平移操作?，F(xiàn)使設(shè)計(jì)坐標(biāo)系下的點(diǎn)集Q保持不動(dòng)，通過對(duì)點(diǎn)集P中的所有點(diǎn)執(zhí)行旋轉(zhuǎn)和平移操作，使得兩片點(diǎn)集中的對(duì)應(yīng)點(diǎn)進(jìn)行匹配。該操作的目標(biāo)是找到一個(gè)最優(yōu)的變換矩陣f*，使得變換后，兩片點(diǎn)集間的各點(diǎn)距離和最小，如式(2)所示。

(2)

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

(3)

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

T=μQ-RμP

(4)

式中，μQ、μP分別為Q、P點(diǎn)集的重心。

2 改進(jìn)差分進(jìn)化算法

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

2.1 算法編碼

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

(5)

式中，Np為種群大??；txi、tyi、tzi分別為沿x、y、z軸的平移量；rxi、ryi、rzi分別為沿x、y、z軸的旋轉(zhuǎn)量。其中，對(duì)于各平移變量的正負(fù)值表示沿各坐標(biāo)軸的正負(fù)方向；對(duì)于各旋轉(zhuǎn)變量的正值表示繞各坐標(biāo)軸順時(shí)針方向旋轉(zhuǎn)，負(fù)值表示繞各坐標(biāo)軸逆時(shí)針方向旋轉(zhuǎn)。

2.2 變異策略

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

(6)

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

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ū)間內(nèi)隨機(jī)選擇的個(gè)體且不等于i；j∈[1,NPgood]；r6～r9是在[1,NPgood] 范圍內(nèi)隨機(jī)選擇的個(gè)體，且不等于j；xbest,G為當(dāng)前種群內(nèi)的最好個(gè)體。本文中，比例因子的選擇方法為[18]

(9)

式中，F(xiàn)0為個(gè)常量；Gmax為最大迭代次數(shù)；G為當(dāng)前進(jìn)化次數(shù)，且G=1,2,…,Gmax。

3 實(shí)驗(yàn)及結(jié)果分析

如圖2所示，采用5個(gè)復(fù)雜曲面零件模型進(jìn)行試驗(yàn)。從左到右，從上到下依次為葉片1、葉片2、法蘭、汽車，以及氣道模型。針對(duì)每個(gè)模型的掃描點(diǎn)云采用均勻法進(jìn)行采樣，采樣個(gè)數(shù)為1000。

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

表1 預(yù)設(shè)轉(zhuǎn)換矩陣

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

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

圖2 各模型初始位置圖

單位：mm

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

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

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

圖3 葉片1模型匹配結(jié)果

圖4 葉片2模型匹配結(jié)果

圖5 法蘭模型匹配結(jié)果

圖6 汽車模型匹配結(jié)果

圖7 氣道模型匹配結(jié)果

4 結(jié)束語

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