基于量子群智能優(yōu)化檢測虛擬現(xiàn)實中物體碰撞

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

(1. 沈陽理工大學(xué) a. 藝術(shù)設(shè)計學(xué)院， b. 信息科學(xué)與工程學(xué)院， c. 材料科學(xué)與工程學(xué)院， 遼寧 沈陽 110159；2. 桂林醫(yī)學(xué)院 廣西腦與認知神經(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)境中物體的真實運動情況。碰撞檢測在虛擬制造和裝配、 機械手控制、 無人駕駛等[2]多個虛擬現(xiàn)實環(huán)境中得到了廣泛的應(yīng)用。特別是在機械虛擬制造和虛擬裝配方面，通過虛擬現(xiàn)實技術(shù)可以提前對裝備環(huán)節(jié)進行模擬，預(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ā)生碰撞。文獻[3]中將包圍盒技術(shù)與多層級建模方法相結(jié)合以提高碰撞檢測精度，解決了多層級建模所帶來的復(fù)雜度造成碰撞檢測效率較低的問題。文獻[4]中運用兩級濾波算法實現(xiàn)了物體的連續(xù)碰撞檢測，旨在對連續(xù)碰撞狀態(tài)及碰撞反饋進行檢測，以提高對物體連續(xù)碰撞的檢測效率。本文中采用人工魚群算法結(jié)合量子比特編碼方法(簡稱本文算法)進行虛擬現(xiàn)實中物體的碰撞檢測研究，以進一步提高檢測的準(zhǔn)確度。

1 碰撞檢測技術(shù)

1.1 碰撞檢測的圍合交叉

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

圖1中有2個物體A和B，物體投影到二維平面分別為菱形和八邊形，藍色表示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ā)生碰撞，還需要通過其他方法進一步判別。本文中以圍合交叉部分為出發(fā)點，對圍合交叉部分進行網(wǎng)格特征提取，然后結(jié)合智能算法，進一步展開碰撞檢測研究。

表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ù)最小值和碰撞閾值進行碰撞檢測。

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

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

，

(4)

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

，

(5)

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

在魚群初始分布情況下， 計算人工魚的各自位置的實物濃度， 在移動時， 先對比自身位置實物濃度和Vvis范圍內(nèi)其他魚位置的實物濃度， 若自身位置實物濃度高， 則隨機移動到位置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)實物體碰撞檢測的精度，精細化標(biāo)定物體運動過程中的坐標(biāo)，結(jié)合人工魚群的位置更新方式，引入量子比特相位，對人工魚位置進行細化描述。

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

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

(9)

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

為了更好地進行運算，將式(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)，對采樣的物體特征人工魚的進行編碼，

(13)

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

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

(14)

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

(15)

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

(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)確率達到設(shè)定的閾值時，輸出碰撞檢測結(jié)果。整個碰撞檢測流程如圖2所示。

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

3 實例仿真

通過實例仿真驗證量子人工魚群算法在虛擬現(xiàn)實碰撞檢測中的性能， 仿真平臺為MATLAB 2018b。 仿真數(shù)據(jù)來源為某航空公司機翼部分軸承虛擬裝配動作執(zhí)行樣本數(shù)據(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)確率的影響

在對圍合交叉部分的物體進行特征采樣時，采樣頻率越高，獲得的物體特征對數(shù)量越多，在構(gòu)建人工魚群時，魚群總量越多。以下針對不同采樣規(guī)模下的物體特征對，分別采用人工魚群算法和量子人工魚群算法對軸承虛擬裝配樣本進行仿真，仿真結(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 不同算法的碰撞檢測性能

選取機翼軸承虛擬裝配訓(xùn)練及測試樣本數(shù)量分別為1 000和200，特征對數(shù)量為700×700，采用MATLAB軟件分別對支持向量機(SVM)、粒子群算法、遺傳算法及本文算法的物體碰撞檢測準(zhǔn)確率進行仿真，結(jié)果見圖4。由圖可以看出，碰撞檢測準(zhǔn)確率隨著檢測時間的增加而提升，當(dāng)運算時間達到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ù)將進一步從人工魚群算法尋優(yōu)改進方面展開研究，以提高碰撞檢測的效率。