基于量子群智能优化检测虚拟现实中物体碰撞

肖世龙， 张德育， 刘 源， 黄 勇， 刘 猛， 毛 容

(1. 沈阳理工大学 a. 艺术设计学院， b. 信息科学与工程学院， c. 材料科学与工程学院， 辽宁 沈阳 110159；2. 桂林医学院 广西脑与认知神经科学重点实验室， 广西 桂林 541001)

近年来，虚拟现实因成功解决了复杂环境的物体运动轨迹及运动状态的高精度仿真问题而成为应用热点。碰撞检测作为研究虚拟现实问题的一个环节[1]，更是虚拟现实研究中的热点。通过碰撞检测，分析虚拟现实环境中物体的运动状态的交互及空间占有的相斥，更容易判断三维立体环境中物体的真实运动情况。碰撞检测在虚拟制造和装配、 机械手控制、 无人驾驶等[2]多个虚拟现实环境中得到了广泛的应用。特别是在机械虚拟制造和虚拟装配方面，通过虚拟现实技术可以提前对装备环节进行模拟，预见并在实际操作中避免装备环节的错误和不当之处。准确的碰撞检测能够提高虚拟制造和装备的精准度，对现实操作有示范作用，同时还可以解决真实环境的虚拟现实模拟所带来的碰撞预警等。

碰撞检测技术根据虚拟环境中的物体空间分布，应用盒包围技术和二维投影，结合物体特征分析方法判别物体之间是否发生碰撞。文献[3]中将包围盒技术与多层级建模方法相结合以提高碰撞检测精度，解决了多层级建模所带来的复杂度造成碰撞检测效率较低的问题。文献[4]中运用两级滤波算法实现了物体的连续碰撞检测，旨在对连续碰撞状态及碰撞反馈进行检测，以提高对物体连续碰撞的检测效率。本文中采用人工鱼群算法结合量子比特编码方法(简称本文算法)进行虚拟现实中物体的碰撞检测研究，以进一步提高检测的准确度。

1 碰撞检测技术

1.1 碰撞检测的围合交叉

虚拟现实技术的碰撞粗检测一般采用围合的方法[5-6]。图1所示为AABB围合碰撞检测方法。

图1中有2个物体A和B，物体投影到二维平面分别为菱形和八边形，蓝色表示2个物体的围合，红色S部分表示2个围合的交叉部分。图1(a)中A和B的围合没有交叉部分，直接可以判定A和B不会发生碰撞。当图1(a)中物体A顺时针旋转90°至图1(b)的状态，A和B出现了围合交叉S，图1(b)图中物体A和B发生了碰撞， 但围合交叉并不代表2个物体一定会碰撞。在图1(c)中，A和B出现了围合交叉S，但是两者并未碰撞。综上，只根据围合交叉并不能判断物体是否发生碰撞，还需要通过其他方法进一步判别。本文中以围合交叉部分为出发点，对围合交叉部分进行网格特征提取，然后结合智能算法，进一步展开碰撞检测研究。

表2 不同采样规模下的碰撞检测时间

(a)无交叉无碰撞

1.2 物体碰撞检测的数学描述

设围合交叉空间中的物体A、B，ai、bj分别为物体A、B的特征， 其中ai∈A，i=1,2,…,M,M为物体A的特征总数；bj∈B，j=1,2,…,N,N为特体B的特征总数。 假设F(p)为物体A、B的同类特征的距离集合，δ为碰撞阈值，若F(p)≤δ，则A与B将发生碰撞[7]。

设采样物体A、B的一个空间分布特征为P(ai,bj)， 只要能够找到特征间距离最小的组合，结合δ，就能够实现2个物体的碰撞检测。

设物体速度v和位置X由2个部分组成，即

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

(1)

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

(2)

其适应度函数[8]为

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

(3)

每次更新后，物体的空间分布状态由其速度和位置共同决定。

2 量子人工鱼群

2.1 人工鱼群算法

在人工鱼群算法的物体碰撞检测过程中，提取所有物体的围合交叉特征作为人工鱼，根据鱼群运动状态来求解各物体特征点间的距离，以特征点间的距离的倒数作为食物浓度函数，通过鱼群的食物寻找过程求解2个物体所有采样特征的距离最小值，根据最小值和碰撞阈值进行碰撞检测。

设第i个物体特征Xi(t)在[t,t+1]时间段内随机移动，其位置更新量为ΔXi(t+1)，则有公式[9]

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

，

(4)

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

，

(5)

式中：rand(0,1)为随机函数；Vvis为鱼的视野，一般为固定距离值；*为卷积运算符。

在鱼群初始分布情况下， 计算人工鱼的各自位置的实物浓度， 在移动时， 先对比自身位置实物浓度和Vvis范围内其他鱼位置的实物浓度， 若自身位置实物浓度高， 则随机移动到位置Xj的方法见式(6)。 移动时为了避免鱼群蜂拥至同一位置， 并不是直接移动到实物浓度高的位置， 而是以特定步长Sstep移动。

若其他鱼位置实物浓度高，则向实物浓度高的定向位置Xo靠近，具体方法[10]为

(7)

若鱼Xi(t)在Vvis范围内有多个位置实物浓度值高于自身实物浓度值，选择Vvis内最大实物浓度值Xmax为目标，其移动方式[11]为

(8)

当|Xo-Xmax|≤δ时，算法停止，δ根据实际情况设定。

2.2 鱼群位置量子化

为了提高虚拟现实物体碰撞检测的精度，精细化标定物体运动过程中的坐标，结合人工鱼群的位置更新方式，引入量子比特相位，对人工鱼位置进行细化描述。

结合量子比特一般表示[12]为

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

(9)

式中:|·〉表示狄拉克符号，通常称为叠加态；α和β为满足条件|α|+|β|=1的2个复数。

为了更好地进行运算，将式(9)矩阵化处理，即

|φ〉=(α,β)T。

(10)

根据单位矩阵I计算方法， 设有矩阵U符合U(U*)T=I， 式(9)可表示[13]为

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

(11)

设比特位角度为θ，令α=cosθ，β=sinθ，式(9)更新为

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

(12)

结合式(12)，对采样的物体特征人工鱼的进行编码，

(13)

式中θij=2πrand(0,1)，i∈{1,2,…,n}，j∈{1,2,…,m}，其中n为采样的所有物体特征点数，m为物体特征维度。

根据式(13)，设Pi,c、Pi,s为物体特征的余弦分量、 正弦分量， 对围合交叉二维平面的特征点位置进行量子化表示为

(14)

设比特位角度θ为(α,β)T以|0〉=(1, 0)T为参照相位，式(13)可以继续化简[14]为

(15)

特别注意的是，式(10)是|φ〉的矩阵表示，式(15)则是|φ〉的相位表示，均为量子的2种表示。根据相位表示法，结合公式(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的设置将影响碰撞检测的精度，而且影响碰撞检测的时间。采用相移表示之后，人工鱼的位置更新问题转变为相移的变化问题，本文中选择动态相移变化方式，随着运算迭代的增加，算法越接近最优值。为了防止相移更新过大造成错过最优值的情况，将相移变化量与迭代次数绑定，具体方法为

(17)

式中：It为算法停止时共计迭代次数；k为动态相移因子，k∈(0,1)。

2.3 基于量子人工鱼群的碰撞检测流程

根据上述碰撞检测和量子人工鱼群算法，以适应度函数作为量子人工鱼群求解的目标函数，以围合交叉的特征对样本为输入，经过量子人工鱼群初始化，以适应度函数的倒数作为鱼群实物浓度函数，经过量子人工鱼群多次训练，获得物体的碰撞检测结果。结合测试集，判断碰撞检测性能，当检测的准确率达到设定的阈值时，输出碰撞检测结果。整个碰撞检测流程如图2所示。

图2 量子人工鱼群的碰撞检测流程

3 实例仿真

通过实例仿真验证量子人工鱼群算法在虚拟现实碰撞检测中的性能， 仿真平台为MATLAB 2018b。 仿真数据来源为某航空公司机翼部分轴承虚拟装配动作执行样本数据， 记录机械手装配轴承碰撞的整个过程。 虚拟现实空间为100 cm×100 cm×100 cm(长度×宽度×高度)的立方体， 首先对人工鱼群的Vvis和动态相移因子k差异化设置， 以便能够调整最优的视野和步长来训练该样本， 然后验证量子编码对人工鱼群优化的性能提升， 最后对比常用物体碰撞检测算法[15]， 比较不同算法对物体碰撞检测的性能。

3.1 人工鱼群主要参数对碰撞检测的性能影响

分别选择围合交叉空间的2个物体特征个数均为500，构成特征对数为500×500的人工鱼群，差异化设置Vvis和k，其碰撞检测准确率如图3所示。由图可以看出，相比于相移因子k，准确率对Vvis更加敏感，碰撞检测准确率随着Vsis值的增加先增大后减少，在Vvis为11处取得了较大值，且在k=3处取得了最大值，因此选择Vvis=11，k=3。

图3 视野和相移因子对检测准确率的影响

3.2 量子编码对碰撞检测准确率的影响

在对围合交叉部分的物体进行特征采样时，采样频率越高，获得的物体特征对数量越多，在构建人工鱼群时，鱼群总量越多。以下针对不同采样规模下的物体特征对，分别采用人工鱼群算法和量子人工鱼群算法对轴承虚拟装配样本进行仿真，仿真结果见表1、 2。

从表1可以看出，随着特征数量的增加，2种算法的检测准确率均在提高，其原因是特征对数量增多更能准确描述围合交叉部分的物体空间整体结构，更加方便获取物体的边缘特性，使得检测准确度越高。当特征对数量为700×700时，物体碰撞检测准确率趋于稳定；当特征对数量增加至1 000×1 000时， 准确率并没有明显提升。对比发现，经过量子处理后，物体的碰撞检测准确率有了明显提升，以特征对数量为700×700为例，检测准确率提升了约12.5%。随着特征对数量的增加，均方根误差逐渐减小，因此仅从碰撞检测准确率方面来说，采样的特征对数量越多越好。

表1 不同采样规模下的碰撞检测准确率

表2所示为对不同采样规模下的碰撞检测时间的仿真结果，设置检测准确率阈值为80%。从表中数据可以看出，随着特征对数量的增加，2种算法的碰撞检测时间均在增加，其原因是随着人工鱼数量的增加，需要迭代全局寻优的时间相应增加。经过量子编码后，所需要的检测时间比传统人工鱼群算法略有增加，但是并没有造成很大的时间消耗。

综合而言，由于采样规模对碰撞检测的准确率和检测时间具有不同的影响，因此在实际操作时应当均衡考虑采样频率，合理设置特征对数量。

3.3 不同算法的碰撞检测性能

选取机翼轴承虚拟装配训练及测试样本数量分别为1 000和200，特征对数量为700×700，采用MATLAB软件分别对支持向量机(SVM)、粒子群算法、遗传算法及本文算法的物体碰撞检测准确率进行仿真，结果见图4。由图可以看出，碰撞检测准确率随着检测时间的增加而提升，当运算时间达到600 ms左右时， SVM算法开始收敛， 粒子群算法大约在680 ms时开始收敛， 遗传算法和本文算法大约在720 ms时检测准确率趋于稳定。 当算法稳定时， 本文算法的网络链路检测准确率最高，为0.97，SVM算法的最差。

图4 不同算法的碰撞检测准确率

4 结语

采用量子人工鱼群算法用于虚拟现实物体碰撞检测，通过盒包围技术和人工鱼群算法的同类特征最小距离判断，配合量子编码及动态相移位置更新，可以有效提高碰撞检测准确率。通过对比发现，人工鱼群位置量子化后对检测时间的影响较小，而且量子人工鱼群算法的碰撞检测准确率性能优于常见的碰撞检测算法的。后续将进一步从人工鱼群算法寻优改进方面展开研究，以提高碰撞检测的效率。