肖世龍， 張德育， 劉 源， 黃 勇， 劉 猛， 毛 容

(1. 沈陽理工大學(xué) a. 藝術(shù)設(shè)計學(xué)院， b. 信息科學(xué)與工程學(xué)院， c. 材料科學(xué)與工程學(xué)院， 遼寧 沈陽 110159；2. 桂林醫(yī)學(xué)院 廣西腦與認(rèn)知神經(jīng)科學(xué)重點實驗室， 廣西 桂林 541001)

近年來，虛擬現(xiàn)實因成功解決了復(fù)雜環(huán)境的物體運動軌跡及運動狀態(tài)的高精度仿真問題而成為應(yīng)用熱點。碰撞檢測作為研究虛擬現(xiàn)實問題的一個環(huán)節(jié)[1]，更是虛擬現(xiàn)實研究中的熱點。通過碰撞檢測，分析虛擬現(xiàn)實環(huán)境中物體的運動狀態(tài)的交互及空間占有的相斥，更容易判斷三維立體環(huán)境中物體的真實運動情況。碰撞檢測在虛擬制造和裝配、 機(jī)械手控制、 無人駕駛等[2]多個虛擬現(xiàn)實環(huán)境中得到了廣泛的應(yīng)用。特別是在機(jī)械虛擬制造和虛擬裝配方面，通過虛擬現(xiàn)實技術(shù)可以提前對裝備環(huán)節(jié)進(jìn)行模擬，預(yù)見并在實際操作中避免裝備環(huán)節(jié)的錯誤和不當(dāng)之處。準(zhǔn)確的碰撞檢測能夠提高虛擬制造和裝備的精準(zhǔn)度，對現(xiàn)實操作有示范作用，同時還可以解決真實環(huán)境的虛擬現(xiàn)實模擬所帶來的碰撞預(yù)警等。

碰撞檢測技術(shù)根據(jù)虛擬環(huán)境中的物體空間分布，應(yīng)用盒包圍技術(shù)和二維投影，結(jié)合物體特征分析方法判別物體之間是否發(fā)生碰撞。文獻(xiàn)[3]中將包圍盒技術(shù)與多層級建模方法相結(jié)合以提高碰撞檢測精度，解決了多層級建模所帶來的復(fù)雜度造成碰撞檢測效率較低的問題。文獻(xiàn)[4]中運用兩級濾波算法實現(xiàn)了物體的連續(xù)碰撞檢測，旨在對連續(xù)碰撞狀態(tài)及碰撞反饋進(jìn)行檢測，以提高對物體連續(xù)碰撞的檢測效率。本文中采用人工魚群算法結(jié)合量子比特編碼方法(簡稱本文算法)進(jìn)行虛擬現(xiàn)實中物體的碰撞檢測研究，以進(jìn)一步提高檢測的準(zhǔn)確度。

1 碰撞檢測技術(shù)

1.1 碰撞檢測的圍合交叉

虛擬現(xiàn)實技術(shù)的碰撞粗檢測一般采用圍合的方法[5-6]。圖1所示為AABB圍合碰撞檢測方法。

圖1中有2個物體A和B，物體投影到二維平面分別為菱形和八邊形，藍(lán)色表示2個物體的圍合，紅色S部分表示2個圍合的交叉部分。圖1(a)中A和B的圍合沒有交叉部分，直接可以判定A和B不會發(fā)生碰撞。當(dāng)圖1(a)中物體A順時針旋轉(zhuǎn)90°至圖1(b)的狀態(tài)，A和B出現(xiàn)了圍合交叉S，圖1(b)圖中物體A和B發(fā)生了碰撞， 但圍合交叉并不代表2個物體一定會碰撞。在圖1(c)中，A和B出現(xiàn)了圍合交叉S，但是兩者并未碰撞。綜上，只根據(jù)圍合交叉并不能判斷物體是否發(fā)生碰撞，還需要通過其他方法進(jìn)一步判別。本文中以圍合交叉部分為出發(fā)點，對圍合交叉部分進(jìn)行網(wǎng)格特征提取，然后結(jié)合智能算法，進(jìn)一步展開碰撞檢測研究。

表2 不同采樣規(guī)模下的碰撞檢測時間

(a)無交叉無碰撞

1.2 物體碰撞檢測的數(shù)學(xué)描述

設(shè)圍合交叉空間中的物體A、B，ai、bj分別為物體A、B的特征， 其中ai∈A，i=1,2,…,M,M為物體A的特征總數(shù)；bj∈B，j=1,2,…,N,N為特體B的特征總數(shù)。 假設(shè)F(p)為物體A、B的同類特征的距離集合，δ為碰撞閾值，若F(p)≤δ，則A與B將發(fā)生碰撞[7]。

設(shè)采樣物體A、B的一個空間分布特征為P(ai,bj)， 只要能夠找到特征間距離最小的組合，結(jié)合δ，就能夠?qū)崿F(xiàn)2個物體的碰撞檢測。

設(shè)物體速度v和位置X由2個部分組成，即

v={va,vb}={(vax,vay,vaz),(vbx,vby,vbz)}，

(1)

X={Xa,Xb}={(xa,ya,za), (xb,yb,zb)}，

(2)

其適應(yīng)度函數(shù)[8]為

F(Xa,Xb)=(xa-xb)2+(ya-yb)2+(za-zb)2。

(3)

每次更新后，物體的空間分布狀態(tài)由其速度和位置共同決定。

2 量子人工魚群

2.1 人工魚群算法

在人工魚群算法的物體碰撞檢測過程中，提取所有物體的圍合交叉特征作為人工魚，根據(jù)魚群運動狀態(tài)來求解各物體特征點間的距離，以特征點間的距離的倒數(shù)作為食物濃度函數(shù)，通過魚群的食物尋找過程求解2個物體所有采樣特征的距離最小值，根據(jù)最小值和碰撞閾值進(jìn)行碰撞檢測。

設(shè)第i個物體特征Xi(t)在[t,t+1]時間段內(nèi)隨機(jī)移動，其位置更新量為ΔXi(t+1)，則有公式[9]

Xi(t+1)=Xi(t)+ΔXi(t+1)

，

(4)

ΔXi(t+1)=Vvis*rand(0,1)

，

(5)

式中：rand(0,1)為隨機(jī)函數(shù)；Vvis為魚的視野，一般為固定距離值；*為卷積運算符。

在魚群初始分布情況下， 計算人工魚的各自位置的實物濃度， 在移動時， 先對比自身位置實物濃度和Vvis范圍內(nèi)其他魚位置的實物濃度， 若自身位置實物濃度高， 則隨機(jī)移動到位置Xj的方法見式(6)。 移動時為了避免魚群蜂擁至同一位置， 并不是直接移動到實物濃度高的位置， 而是以特定步長Sstep移動。

若其他魚位置實物濃度高，則向?qū)嵨餄舛雀叩亩ㄏ蛭恢肵o靠近，具體方法[10]為

(7)

若魚Xi(t)在Vvis范圍內(nèi)有多個位置實物濃度值高于自身實物濃度值，選擇Vvis內(nèi)最大實物濃度值Xmax為目標(biāo)，其移動方式[11]為

(8)

當(dāng)|Xo-Xmax|≤δ時，算法停止，δ根據(jù)實際情況設(shè)定。

2.2 魚群位置量子化

為了提高虛擬現(xiàn)實物體碰撞檢測的精度，精細(xì)化標(biāo)定物體運動過程中的坐標(biāo)，結(jié)合人工魚群的位置更新方式，引入量子比特相位，對人工魚位置進(jìn)行細(xì)化描述。

結(jié)合量子比特一般表示[12]為

|φ〉=α|0〉+β|1〉，

(9)

式中:|·〉表示狄拉克符號，通常稱為疊加態(tài)；α和β為滿足條件|α|+|β|=1的2個復(fù)數(shù)。

為了更好地進(jìn)行運算，將式(9)矩陣化處理，即

|φ〉=(α,β)T。

(10)

根據(jù)單位矩陣I計算方法， 設(shè)有矩陣U符合U(U*)T=I， 式(9)可表示[13]為

U|φ〉=U(α|0〉+β|1〉)。

(11)

設(shè)比特位角度為θ，令α=cosθ，β=sinθ，式(9)更新為

|φ〉=cosθ|0〉+sinθ|1〉=(cosθ, sinθ)T。

(12)

結(jié)合式(12)，對采樣的物體特征人工魚的進(jìn)行編碼，

(13)

式中θij=2πrand(0,1)，i∈{1,2,…,n}，j∈{1,2,…,m}，其中n為采樣的所有物體特征點數(shù)，m為物體特征維度。

根據(jù)式(13)，設(shè)Pi,c、Pi,s為物體特征的余弦分量、 正弦分量， 對圍合交叉二維平面的特征點位置進(jìn)行量子化表示為

(14)

設(shè)比特位角度θ為(α,β)T以|0〉=(1, 0)T為參照相位，式(13)可以繼續(xù)化簡[14]為

(15)

特別注意的是，式(10)是|φ〉的矩陣表示，式(15)則是|φ〉的相位表示，均為量子的2種表示。根據(jù)相位表示法，結(jié)合公式(14)，對采樣的物體特征點進(jìn)行更新描述，

(16)

式中：(cos[θij(t)], sin[θij(t)])T和(cos[θij(t+1)], sin[θij(t+1)])T分別為t、t+1時刻第i條魚第j維量子位； Δθij(t+1)為t時刻到t+1時刻的相移。

更新步長Sstep的設(shè)置將影響碰撞檢測的精度，而且影響碰撞檢測的時間。采用相移表示之后，人工魚的位置更新問題轉(zhuǎn)變?yōu)橄嘁频淖兓瘑栴}，本文中選擇動態(tài)相移變化方式，隨著運算迭代的增加，算法越接近最優(yōu)值。為了防止相移更新過大造成錯過最優(yōu)值的情況，將相移變化量與迭代次數(shù)綁定，具體方法為

(17)

式中：It為算法停止時共計迭代次數(shù)；k為動態(tài)相移因子，k∈(0,1)。

2.3 基于量子人工魚群的碰撞檢測流程

根據(jù)上述碰撞檢測和量子人工魚群算法，以適應(yīng)度函數(shù)作為量子人工魚群求解的目標(biāo)函數(shù)，以圍合交叉的特征對樣本為輸入，經(jīng)過量子人工魚群初始化，以適應(yīng)度函數(shù)的倒數(shù)作為魚群實物濃度函數(shù)，經(jīng)過量子人工魚群多次訓(xùn)練，獲得物體的碰撞檢測結(jié)果。結(jié)合測試集，判斷碰撞檢測性能，當(dāng)檢測的準(zhǔn)確率達(dá)到設(shè)定的閾值時，輸出碰撞檢測結(jié)果。整個碰撞檢測流程如圖2所示。

圖2 量子人工魚群的碰撞檢測流程

3 實例仿真

通過實例仿真驗證量子人工魚群算法在虛擬現(xiàn)實碰撞檢測中的性能， 仿真平臺為MATLAB 2018b。 仿真數(shù)據(jù)來源為某航空公司機(jī)翼部分軸承虛擬裝配動作執(zhí)行樣本數(shù)據(jù)， 記錄機(jī)械手裝配軸承碰撞的整個過程。 虛擬現(xiàn)實空間為100 cm×100 cm×100 cm(長度×寬度×高度)的立方體， 首先對人工魚群的Vvis和動態(tài)相移因子k差異化設(shè)置， 以便能夠調(diào)整最優(yōu)的視野和步長來訓(xùn)練該樣本， 然后驗證量子編碼對人工魚群優(yōu)化的性能提升， 最后對比常用物體碰撞檢測算法[15]， 比較不同算法對物體碰撞檢測的性能。

3.1 人工魚群主要參數(shù)對碰撞檢測的性能影響

分別選擇圍合交叉空間的2個物體特征個數(shù)均為500，構(gòu)成特征對數(shù)為500×500的人工魚群，差異化設(shè)置Vvis和k，其碰撞檢測準(zhǔn)確率如圖3所示。由圖可以看出，相比于相移因子k，準(zhǔn)確率對Vvis更加敏感，碰撞檢測準(zhǔn)確率隨著Vsis值的增加先增大后減少，在Vvis為11處取得了較大值，且在k=3處取得了最大值，因此選擇Vvis=11，k=3。

圖3 視野和相移因子對檢測準(zhǔn)確率的影響

3.2 量子編碼對碰撞檢測準(zhǔn)確率的影響

在對圍合交叉部分的物體進(jìn)行特征采樣時，采樣頻率越高，獲得的物體特征對數(shù)量越多，在構(gòu)建人工魚群時，魚群總量越多。以下針對不同采樣規(guī)模下的物體特征對，分別采用人工魚群算法和量子人工魚群算法對軸承虛擬裝配樣本進(jìn)行仿真，仿真結(jié)果見表1、 2。

從表1可以看出，隨著特征數(shù)量的增加，2種算法的檢測準(zhǔn)確率均在提高，其原因是特征對數(shù)量增多更能準(zhǔn)確描述圍合交叉部分的物體空間整體結(jié)構(gòu)，更加方便獲取物體的邊緣特性，使得檢測準(zhǔn)確度越高。當(dāng)特征對數(shù)量為700×700時，物體碰撞檢測準(zhǔn)確率趨于穩(wěn)定；當(dāng)特征對數(shù)量增加至1 000×1 000時， 準(zhǔn)確率并沒有明顯提升。對比發(fā)現(xiàn)，經(jīng)過量子處理后，物體的碰撞檢測準(zhǔn)確率有了明顯提升，以特征對數(shù)量為700×700為例，檢測準(zhǔn)確率提升了約12.5%。隨著特征對數(shù)量的增加，均方根誤差逐漸減小，因此僅從碰撞檢測準(zhǔn)確率方面來說，采樣的特征對數(shù)量越多越好。

表1 不同采樣規(guī)模下的碰撞檢測準(zhǔn)確率

表2所示為對不同采樣規(guī)模下的碰撞檢測時間的仿真結(jié)果，設(shè)置檢測準(zhǔn)確率閾值為80%。從表中數(shù)據(jù)可以看出，隨著特征對數(shù)量的增加，2種算法的碰撞檢測時間均在增加，其原因是隨著人工魚數(shù)量的增加，需要迭代全局尋優(yōu)的時間相應(yīng)增加。經(jīng)過量子編碼后，所需要的檢測時間比傳統(tǒng)人工魚群算法略有增加，但是并沒有造成很大的時間消耗。

綜合而言，由于采樣規(guī)模對碰撞檢測的準(zhǔn)確率和檢測時間具有不同的影響，因此在實際操作時應(yīng)當(dāng)均衡考慮采樣頻率，合理設(shè)置特征對數(shù)量。

3.3 不同算法的碰撞檢測性能

選取機(jī)翼軸承虛擬裝配訓(xùn)練及測試樣本數(shù)量分別為1 000和200，特征對數(shù)量為700×700，采用MATLAB軟件分別對支持向量機(jī)(SVM)、粒子群算法、遺傳算法及本文算法的物體碰撞檢測準(zhǔn)確率進(jìn)行仿真，結(jié)果見圖4。由圖可以看出，碰撞檢測準(zhǔn)確率隨著檢測時間的增加而提升，當(dāng)運算時間達(dá)到600 ms左右時， SVM算法開始收斂， 粒子群算法大約在680 ms時開始收斂， 遺傳算法和本文算法大約在720 ms時檢測準(zhǔn)確率趨于穩(wěn)定。 當(dāng)算法穩(wěn)定時， 本文算法的網(wǎng)絡(luò)鏈路檢測準(zhǔn)確率最高，為0.97，SVM算法的最差。

圖4 不同算法的碰撞檢測準(zhǔn)確率

4 結(jié)語

采用量子人工魚群算法用于虛擬現(xiàn)實物體碰撞檢測，通過盒包圍技術(shù)和人工魚群算法的同類特征最小距離判斷，配合量子編碼及動態(tài)相移位置更新，可以有效提高碰撞檢測準(zhǔn)確率。通過對比發(fā)現(xiàn)，人工魚群位置量子化后對檢測時間的影響較小，而且量子人工魚群算法的碰撞檢測準(zhǔn)確率性能優(yōu)于常見的碰撞檢測算法的。后續(xù)將進(jìn)一步從人工魚群算法尋優(yōu)改進(jìn)方面展開研究，以提高碰撞檢測的效率。