一種基于張量投票的CAD模型配準(zhǔn)方法

嚴(yán)燚坤，屈建勤，王本淇

（汕頭大學(xué)工學(xué)院，廣東 汕頭 515063）

0 引言

隨著工業(yè)產(chǎn)品的設(shè)計(jì)水平日益提升，不同的三維曲面和復(fù)雜型面[1]在工業(yè)零件的設(shè)計(jì)中的應(yīng)用越來(lái)越廣泛.這其中的關(guān)鍵技術(shù)是測(cè)量數(shù)據(jù)與CAD模型之間的配準(zhǔn)[2-3].在將CAD模型的配準(zhǔn)技術(shù)運(yùn)用到工業(yè)生產(chǎn)過(guò)程中，有幾個(gè)亟待解決的問(wèn)題.

我們知道，當(dāng)我們采集目標(biāo)的三維坐標(biāo)數(shù)據(jù)的時(shí)候，由于點(diǎn)集的不完整，旋轉(zhuǎn)錯(cuò)位，平移錯(cuò)位等因素的干擾，可能在原始的數(shù)據(jù)中存在大量的噪聲數(shù)據(jù)和離群點(diǎn)，最后導(dǎo)致配準(zhǔn)的準(zhǔn)確率大幅度下降，無(wú)法進(jìn)行正常的配準(zhǔn).另外，當(dāng)噪聲數(shù)據(jù)占比越大，配準(zhǔn)需要花費(fèi)的時(shí)間也會(huì)越多，而在實(shí)時(shí)處理系統(tǒng)中，我們往往需要及時(shí)地對(duì)研究的對(duì)象進(jìn)行配準(zhǔn)工作，這時(shí)候?qū)λ惴ㄐ室蠛芨?因此，如果能夠在一定程度上降低算法的復(fù)雜度，就能讓其能更好的服務(wù)于實(shí)時(shí)的配準(zhǔn)系統(tǒng)中.

目前，大部分研究都是基于ICP算法[4].例如，Zhang[5]提出了采用k-d樹(shù)加速的ICP算法；Sharp等[6]人則提出了一種基于歐幾里得不變特征的ICP算法；Truk等[7]人則利用三角網(wǎng)格作為基本的運(yùn)算單元進(jìn)行配準(zhǔn)的工作.在國(guó)內(nèi)，石愛(ài)軍和白瑞林等[8]人將遺傳算法和ICP算法相結(jié)合進(jìn)行研究；劉一凡和蔡振江[9]提出了ICP和SFM結(jié)合的算法.

上述各種算法都是在ICP算法的基礎(chǔ)上，通過(guò)不同的匹配對(duì)象的特征有針對(duì)性的提出改進(jìn)措施，并且取得了不錯(cuò)的效果.但是ICP類算法對(duì)點(diǎn)集的初始位置要求比較高，容易陷入局部最優(yōu)解，并且當(dāng)點(diǎn)集中存在大量噪聲的情況下配準(zhǔn)效果變得很差.

而由于張量投票算法是基于全局的數(shù)據(jù)，并采用投票的方式進(jìn)行計(jì)算的，因而能很好地避免噪聲對(duì)算法輸出的影響.作為一種魯棒性很強(qiáng)的算法，即使在存在大量噪聲數(shù)據(jù)的情況下，張量投票算法依然能保持很高的配準(zhǔn)準(zhǔn)確率.但是，原始的張量投票算法計(jì)算復(fù)雜度雖然相比ICP等迭代算法下降了很多，但是當(dāng)噪聲比例很大時(shí)，其運(yùn)行效率也會(huì)降低.在實(shí)時(shí)的處理系統(tǒng)中，由于對(duì)及時(shí)性要求非?？量?，對(duì)于效率的每一點(diǎn)提升都有很大的價(jià)值.

基于此，本文改進(jìn)了原始的張量投票算法[10]，通過(guò)簡(jiǎn)化token的表示，簡(jiǎn)化衰退性函數(shù)的模型，同時(shí)對(duì)計(jì)票的計(jì)算方式進(jìn)行細(xì)化和補(bǔ)充，使得算法的運(yùn)行效率有了很大的提高.

1 原始張量投票算法

張量投票算法由Gerard Medioni領(lǐng)導(dǎo)的研究組所提出，是一種符合人類視覺(jué)特征性的空間結(jié)構(gòu)特征的提取算法，該算法運(yùn)用到了張量分析[11]，幾何學(xué)，矩陣論這些方面的知識(shí)和Gestalt定律[12].

張量投票算法的主要思想有兩點(diǎn)：一是張量[13-14]的數(shù)字化表示，張量的特征值大小構(gòu)成了特征的分層表示；二是特征的計(jì)算，通過(guò)收集附近鄰域以及方向信息來(lái)確定.張量投票算法的精髓在于用張量疊加的方式來(lái)加強(qiáng)待提取的特征，得到顯著性特征程度圖，然后用張量的分解來(lái)解釋投票產(chǎn)生的結(jié)果.

張量投票算法中主要是對(duì)矩陣的特征向量和特征值進(jìn)行分解.該算法對(duì)噪聲數(shù)據(jù)和離群點(diǎn)具有較好的魯棒性，同時(shí)能有效避免算法陷入局部最優(yōu).在2007年，Leo Reyes和Gerard Medioni等人將張量投票算法應(yīng)用到三維點(diǎn)集的配準(zhǔn)過(guò)程中[15]，并且取得了很好的實(shí)驗(yàn)效果.

2 配準(zhǔn)的數(shù)學(xué)描述

2.1 配準(zhǔn)的實(shí)質(zhì)

配準(zhǔn)的本質(zhì)其實(shí)就是將不同坐標(biāo)或者不同系統(tǒng)的同一對(duì)象的幾何特征，通過(guò)剛性變換讓兩個(gè)對(duì)象在方向和位置上完全重合的過(guò)程.一般在我們采集數(shù)據(jù)進(jìn)行完預(yù)處理后可以得到其測(cè)量坐標(biāo)系，而CAD模型處于設(shè)計(jì)坐標(biāo)系，這兩個(gè)坐標(biāo)系相互獨(dú)立.為了完成配準(zhǔn)工作，我們需要將測(cè)量坐標(biāo)下的數(shù)據(jù)經(jīng)過(guò)幾何轉(zhuǎn)換到設(shè)計(jì)坐標(biāo)系下，讓測(cè)量數(shù)據(jù)和CAD模型盡可能多的重合.所以配準(zhǔn)的本質(zhì)就是求測(cè)量數(shù)據(jù)到CAD模型所經(jīng)歷的平移和旋轉(zhuǎn)變換的參數(shù).

2.2 剛性變化的過(guò)程

在歐式空間中，如果一個(gè)物體被看作是理想情況下的剛體，那么不管是物體的方向或位置發(fā)生變化還是我們?cè)诓煌淖鴺?biāo)系下觀察同一個(gè)物體，物體的大小和形狀都會(huì)保持不變.所以，在歐氏變換中，只要對(duì)象的形狀和大小不發(fā)生改變就叫剛性變換.剛性變化包含兩個(gè)方面，一是平移變換，二是旋轉(zhuǎn)變換，我們研究的CAD模型配準(zhǔn)問(wèn)題中的對(duì)象都是剛體.設(shè)在坐標(biāo)系 O（x，y，z）下的點(diǎn) P 的坐標(biāo)是（x，y，z），在坐標(biāo)系 O（x′，y′，z′）下點(diǎn)Q的坐標(biāo)為（x′，y′，z′）.則從點(diǎn)P到Q的剛性變換如下式所示：

上式中，T＝（tx，ty，tz）T表示剛性變換的平移矩陣，R表示剛性變換的旋轉(zhuǎn)矩陣，即

由式（2）可知，旋轉(zhuǎn)矩陣包含9個(gè)參數(shù).一般情況下，R是由繞X，Y，Z三個(gè)軸的基本的旋轉(zhuǎn)方向復(fù)合而成，設(shè)繞三個(gè)軸旋轉(zhuǎn)的角度分別為w，φ和k.用歐拉角表示法如圖2所示：

我們將繞X軸旋轉(zhuǎn)的矩陣RX（w）定義為：

我們將繞Y軸旋轉(zhuǎn)的矩陣RY（φ）定義為：

我們將繞Z軸旋轉(zhuǎn)的矩陣RZ（k）定義為：

其中R＝RX（w）RY（φ）RZ（k）.

對(duì)于3D點(diǎn)集的配準(zhǔn)問(wèn)題，其本質(zhì)就是求解剛體運(yùn)動(dòng)方程的過(guò)程

2.3 幾何約束

在配準(zhǔn)相關(guān)的研究中，很多都是基于純幾何或者純代數(shù)的方式去描述配準(zhǔn)過(guò)程中的約束關(guān)系，其過(guò)程復(fù)雜而且繁瑣.為了表達(dá)上的簡(jiǎn)潔，本文使用幾何代數(shù)的方式來(lái)描述配準(zhǔn)過(guò)程中的約束關(guān)系.在文獻(xiàn)[15]中，Medioni利用幾何代數(shù)對(duì)配準(zhǔn)問(wèn)題的描述進(jìn)行了簡(jiǎn)化，并最終將約束方程的簡(jiǎn)化成了式（6）.

我們假設(shè)A＝[0 0 1]T，則問(wèn)題變成了二維的形式.我們只需要探討x和y之間的關(guān)系，通過(guò)上面的方程可以得到如圖2.

圖2 點(diǎn)對(duì)之間的對(duì)應(yīng)關(guān)系

圖2中的（a）和（d）表示兩個(gè)屬于相同剛性變換和幾何圖形的對(duì)應(yīng)點(diǎn).（b）和（e）表示兩個(gè)屬于不同變換（旋轉(zhuǎn)角度）和幾何平面的對(duì)應(yīng)點(diǎn).（c）和（f）表示多個(gè)對(duì)應(yīng)點(diǎn)的例子.

由圖可知，方程（6）的約束可以用來(lái)拒絕錯(cuò)誤的匹配.通過(guò)這個(gè)過(guò)程，我們可以將尋找兩組三維點(diǎn)對(duì)剛性變換方程的過(guò)程轉(zhuǎn)換成在接點(diǎn)空間中尋找滿足三組幾何約束的三維平面的問(wèn)題.

3 張量投票算法的改進(jìn)

在本文的研究過(guò)程中發(fā)現(xiàn)，文獻(xiàn)[15]中使用張量投票算法進(jìn)行三維點(diǎn)集配準(zhǔn)的過(guò)程中有兩個(gè)存在優(yōu)化和細(xì)化的地方.一是token如何編碼成張量的形式，二是在計(jì)票方式上細(xì)化和補(bǔ)充.

3.1 token的張量的表示

在文獻(xiàn)[15]中，Medioni將token全部編碼成球張量，然后參與投票，而本文改進(jìn)了原文中的編碼方式.在本文中，我們通過(guò)將token和其轉(zhuǎn)置矩陣相乘編碼成一個(gè)張量.

同時(shí)，原文中生成新的張量的方式是通過(guò)張量積分的方式進(jìn)行，筆者將其進(jìn)行了簡(jiǎn)化，通過(guò)將token領(lǐng)域內(nèi)的張量和衰退性函數(shù)DF（s，k，σ）積的累加和得到最后新的張量.這種方式有效的減小了計(jì)算的復(fù)雜度，在一定程度上提升了算法的效率.

3.2 計(jì)票的方式

在文獻(xiàn)[15]中，Medioni采用原始張量投票的計(jì)票方式，即選擇被投票點(diǎn)特定范圍內(nèi)的token所表示的張量對(duì)其進(jìn)行投票.筆者認(rèn)為這種方式可能存在一些問(wèn)題，比如當(dāng)領(lǐng)域內(nèi)的token數(shù)量較少時(shí)可能會(huì)導(dǎo)致投票結(jié)果和實(shí)際情況存在偏差，所以本文在此基礎(chǔ)上進(jìn)行細(xì)化和改進(jìn).

本文所采用的計(jì)票方式分為下面的步驟進(jìn)行：

1）設(shè)定參與投票的點(diǎn)不得少于m個(gè)，如果被投票的token領(lǐng)域內(nèi)的token數(shù)量n＞m時(shí)，投票步驟按張量投票的原始算法進(jìn)行；

2）當(dāng)統(tǒng)計(jì)得到的n＜m時(shí)，我們采用另一種計(jì)票方式.即篩選出距離被投票token最近的m個(gè)點(diǎn)參與投票.

通過(guò)上面的計(jì)票方式可以避免部分token領(lǐng)域中的投票稀疏的問(wèn)題.

3.3 模型評(píng)價(jià)標(biāo)準(zhǔn)

在本文中，我們使用隨機(jī)生成的點(diǎn)集數(shù)據(jù)做測(cè)試數(shù)據(jù)，利用這些數(shù)據(jù)來(lái)比較本文改進(jìn)的張量投票算法和文獻(xiàn)[15]中的配準(zhǔn)算法的結(jié)果.為了測(cè)試結(jié)果盡可能客觀和公平，本文共設(shè)計(jì)了多組對(duì)比實(shí)驗(yàn)用來(lái)觀察旋轉(zhuǎn)角度的大小、平移的距離、數(shù)據(jù)規(guī)模和離群點(diǎn)比例等因素對(duì)配準(zhǔn)效率和準(zhǔn)確率的影響.最終，通過(guò)統(tǒng)計(jì)不同情況下的配準(zhǔn)結(jié)果來(lái)做對(duì)比.

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

4.1 實(shí)驗(yàn)條件

本文算法采用Matlab作為編程工具，在一臺(tái)個(gè)人筆記本電腦上進(jìn)行實(shí)驗(yàn).筆記本電腦的配置和環(huán)境為：CPU為Intel Core i7-8750H（主頻為2.2 GHZ，六核十二線程），內(nèi)存為8G，顯卡為NVIDIA GTX1060（顯存為6G），硬盤(pán)容量為128G的SSD，操作系統(tǒng)為Windows 10.

4.2 實(shí)驗(yàn)數(shù)據(jù)

在本節(jié)，我們將設(shè)計(jì)兩組實(shí)驗(yàn)來(lái)比較和驗(yàn)證算法的配準(zhǔn)效果.兩組實(shí)驗(yàn)分別對(duì)比的是F-ICP算法，原始張量投票算法和改進(jìn)后的張量投票算法，比較的指標(biāo)是配準(zhǔn)準(zhǔn)確率和配準(zhǔn)時(shí)間.

在第一組實(shí)驗(yàn)中，我們利用合成數(shù)據(jù)進(jìn)行配準(zhǔn)的實(shí)驗(yàn).我們通過(guò)Matlab的rand函數(shù)在空間1×1×1內(nèi)生成隨機(jī)的40 000個(gè)數(shù)據(jù).為了測(cè)試結(jié)果盡可能客觀和公平，實(shí)驗(yàn)進(jìn)行了多次，并取實(shí)驗(yàn)的平均值作為結(jié)果.最終，通過(guò)統(tǒng)計(jì)不同情況下的平均配準(zhǔn)結(jié)果作對(duì)比.

在第二組實(shí)驗(yàn)中，我們對(duì)斯坦福兔子進(jìn)行配準(zhǔn)實(shí)驗(yàn)，對(duì)算法在實(shí)際應(yīng)用中的效果進(jìn)行驗(yàn)證.

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

除了測(cè)試改進(jìn)后的張量投票算法，本文還接著利用隨機(jī)數(shù)據(jù)對(duì)F-ICP算法和原始的張量投票算法作對(duì)比，得出了在不同離群點(diǎn)程度的情況下各算法的配準(zhǔn)率和配準(zhǔn)效率.表1為F-ICP算法的配準(zhǔn)結(jié)果.

表1 F-ICP算法的配準(zhǔn)結(jié)果

為了實(shí)驗(yàn)結(jié)果更具有說(shuō)服性，第二組測(cè)試數(shù)據(jù)的旋轉(zhuǎn)角度的限制擴(kuò)展到0°～360°，平移距離也擴(kuò)大到-10～＋10.表2為本文改進(jìn)后的算法的配準(zhǔn)結(jié)果.

表2 本文改進(jìn)后的張量投票算法的配準(zhǔn)結(jié)果

表3的實(shí)驗(yàn)結(jié)果來(lái)自文獻(xiàn)[15]，其實(shí)驗(yàn)環(huán)境和約束與表2中的一致，其實(shí)驗(yàn)結(jié)果為使用原始的張量投票算法進(jìn)行配準(zhǔn)的結(jié)果.

表3 原始張量投票算法的配準(zhǔn)結(jié)果

在第二組實(shí)驗(yàn)中，首先我們對(duì)著名的斯坦福兔子模型進(jìn)行配準(zhǔn)實(shí)驗(yàn)，在配準(zhǔn)前，其輸入數(shù)據(jù)為測(cè)量點(diǎn)集數(shù)據(jù)和兔子的模型數(shù)據(jù)，如圖3所示.

其中圖3上方是測(cè)試點(diǎn)集數(shù)據(jù)，圖下方是兔子的模型數(shù)據(jù).使用改進(jìn)后的張量投票算法進(jìn)行配準(zhǔn)后的效果如圖4所示.

圖3 測(cè)試的兔子數(shù)據(jù)

圖4 斯坦福兔子配準(zhǔn)后的效果圖

從第一組測(cè)試數(shù)據(jù)可以看出，改進(jìn)后的張量投票算法相比F-ICP算法而言，在離群點(diǎn)比例逐漸增加的情況下具有很大的優(yōu)勢(shì)，即使在旋轉(zhuǎn)角度和平移距離明顯大于F-ICP算法的環(huán)境下，改進(jìn)后的張量投票算法的配準(zhǔn)準(zhǔn)確率仍然大大超過(guò)F-ICP算法，同時(shí)運(yùn)行效率也遠(yuǎn)遠(yuǎn)高于F-ICP算法，效率的提升在10倍以上.從表格1的實(shí)驗(yàn)結(jié)果可以得出F-ICP算法對(duì)原始點(diǎn)集和目標(biāo)點(diǎn)集之間的變換幅度很敏感.當(dāng)離群點(diǎn)的比例超過(guò)75%時(shí)，配準(zhǔn)的準(zhǔn)確率下降到了60%，而改進(jìn)后的算法在離群點(diǎn)占比高達(dá)93%的情況下，配準(zhǔn)準(zhǔn)確率依然保持在75%.從中可以得出結(jié)論：相比于ICP類算法，張量投票算法對(duì)噪聲數(shù)據(jù)和離群點(diǎn)具有很好的魯棒性，并且其對(duì)初始位置的要求不高，算法的普適性更好.

與原始的張量投票算法相比，兩者的配準(zhǔn)準(zhǔn)確率差別不是很明顯，但是實(shí)驗(yàn)的結(jié)果表明，改進(jìn)后的張量投票算法穩(wěn)定性更好.在離群點(diǎn)比例逐步變大的過(guò)程中，改進(jìn)后的算法的配準(zhǔn)準(zhǔn)確率更加均勻地下降.在離群點(diǎn)的比例達(dá)到83%，88%和93%的情況下，本文改進(jìn)的算法的配準(zhǔn)準(zhǔn)確率相對(duì)于原始的張量投票算法有了小幅的提升.另一方面，對(duì)于算法運(yùn)行的效率而言，改進(jìn)后的算法比原始算法提升了39.2%～90.8%，說(shuō)明改進(jìn)后的算法在復(fù)雜度方面更低.

我們知道，在實(shí)時(shí)的配準(zhǔn)系統(tǒng)中，往往對(duì)于配準(zhǔn)的精確度沒(méi)有那么高，并且在實(shí)際的情況中，噪聲數(shù)據(jù)的比例一般維持在一定的范圍內(nèi)，不會(huì)過(guò)于夸張.而其對(duì)配準(zhǔn)效率的要求很高，所以配準(zhǔn)效率的提升對(duì)于配準(zhǔn)的實(shí)際應(yīng)用有很大的價(jià)值.而本文通過(guò)改進(jìn)張量投票算法，在保證配準(zhǔn)精準(zhǔn)度與原始張量投票算法基本持平的情況下，有效的提升了配準(zhǔn)的效率.使得改進(jìn)后的算法能夠更好的應(yīng)用于實(shí)時(shí)的配準(zhǔn)系統(tǒng)中.

5 總結(jié)

為了實(shí)現(xiàn)CAD模型的配準(zhǔn)，本文通過(guò)一種基于張量投票的配準(zhǔn)算法，并對(duì)文獻(xiàn)[15]中的部分實(shí)驗(yàn)步驟進(jìn)行了改進(jìn)，最后通過(guò)和原文的實(shí)驗(yàn)結(jié)果進(jìn)行比較，取得了一定的效果.并且，本文利用斯坦福兔子作為測(cè)試對(duì)象，證明了改進(jìn)后的張量投票算法在實(shí)際的配準(zhǔn)工作中取得了很好的效果.但是仍然需要更大的樣本空間進(jìn)一步的研究去提升算法效率和準(zhǔn)確率.文本可以在一下幾個(gè)方面繼續(xù)研究和改進(jìn)：（1）擴(kuò)展算法的應(yīng)用場(chǎng)景，讓其能適配非剛性的變換；（2）進(jìn)一步擴(kuò)大樣本空間，從多個(gè)角度出發(fā)設(shè)計(jì)實(shí)驗(yàn)，進(jìn)一步測(cè)試算法的穩(wěn)定性；（3）優(yōu)化算法的計(jì)算復(fù)雜度.