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

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

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

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

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

1 碰撞檢測(cè)技術(shù)

1.1 碰撞檢測(cè)的圍合交叉

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

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

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

(a)無(wú)交叉無(wú)碰撞

1.2 物體碰撞檢測(cè)的數(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的一個(gè)空間分布特征為P(ai,bj)， 只要能夠找到特征間距離最小的組合，結(jié)合δ，就能夠?qū)崿F(xiàn)2個(gè)物體的碰撞檢測(cè)。

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

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 量子人工魚(yú)群

2.1 人工魚(yú)群算法

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

設(shè)第i個(gè)物體特征Xi(t)在[t,t+1]時(shí)間段內(nèi)隨機(jī)移動(dòng)，其位置更新量為Δ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為魚(yú)的視野，一般為固定距離值；*為卷積運(yùn)算符。

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

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

(7)

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

(8)

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

2.2 魚(yú)群位置量子化

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

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

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

(9)

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

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

|φ〉=(α,β)T。

(10)

根據(jù)單位矩陣I計(jì)算方法， 設(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)，對(duì)采樣的物體特征人工魚(yú)的進(jìn)行編碼，

(13)

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

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

(14)

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

(15)

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

(16)

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

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

(17)

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

2.3 基于量子人工魚(yú)群的碰撞檢測(cè)流程

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

圖2 量子人工魚(yú)群的碰撞檢測(cè)流程

3 實(shí)例仿真

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

3.1 人工魚(yú)群主要參數(shù)對(duì)碰撞檢測(cè)的性能影響

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

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

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

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

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

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

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

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

3.3 不同算法的碰撞檢測(cè)性能

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

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

4 結(jié)語(yǔ)

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