基于群智感知的高效三维场景数据收集

2021-11-18王黎征

南阳理工学院学报 2021年4期

王浩，王旭，王黎征

(1.南阳理工学院数字媒体与艺术设计学院河南南阳 473004；2.南阳高等医学专科学校第一附属医院河南南阳 473000)

0 引言

在场景理解系统中，RGB图像或者遥感卫星图像等二维空间的图像仅仅提供了目标的颜色、纹理、角点等关键信息和数据，由于缺少空间上的深度信息，在三维场景下，因光照不均匀、目标易遮挡和位置易变化等原因，通常无法提取三维空间坐标和目标的重要空间信息。因此，学者们更加关注构建3D场景理解技术来开发3D场景理解[1-3]方面的研究和实践工作。因此，如何构建三维场景数据集是非常关键的基础性工作。

本文拟利用三维点云传感器，运用三维数据采集设备(如图1所示)，发挥三维点云提供空间感知距离的优势，完成三维空间下对城市环境中目标的三维图像数据收集，这已经成为三维点云目标检测、三维场景目标分割，以及利用现有的人工智能算法实现三维目标匹配的基础。

图1 三维数据采集设备

本文拟采用计算机视觉和激光雷达相结合的方式，并运用雷达成像和高清影像技术来收集三维点云数据。在图1中，构建城市三维场景图像的硬件设备可以分为如下几种：(a)带有传感设备的三维数据采集车。其中包含采用基于激光扫描与全景影像相结合的车载移动系统；(b)为含激光雷达的手推式采集车；(c)为三维深度摄像机及其支架；(d)为固定扫描仪；(e)采集人员背负采集设备。这些雷达成像和高清影像相结合的三维数据采集方式有3个方面的优势：第一、雷达扫描技术可以快速、准确地识别远距离的三维空间信息，也就是，这可以得到大型、复杂、标准或不标准的实景3D空间几何信息；第二、数据采集车或者背负式背包，移动覆盖范围广，且探测距离比Kinect的视野范围要远很多；第三、志愿者背负式采集系统携带灵活方便且效果好，不受地理位置空间限制。

如图1所示，既可以通过信息采集车远距离合成雷达成像和高清影像的方式得到三维点云图，也可以背着3D采集设备得到近距离的三维点云图，甚至全景路线图也可以得到。

1 群智感知的数据采集方法

利用群智感知机制来完成三维场景下目标点云收据收集，受到众多学者的青睐[1-4]。他们从不同的机制、方案和模型角度，提出来各种各样的算法和技术。然而，不同的算法和模型对应的优化参数各不相同。例如，在机会网络的背景下，由于能够容忍延时数据，群智感知平台收集这些数据往往让参与者有意识或者无意识地完成三维数据收集，或者分配相应的任务。通常会感知或预测参与任务收集的志愿者，并且分析他们的行走路径，进而设计任务分配方案，这类情形的目标往往是最小化完成任务的人数[4]，或者最大化完成任务的数量[5]，或者最小化总体的成本。本文关注在时间敏感的数据收集背景下，如何让参与者有意识地移动到指定地点并完成数据收集任务，优化目标使移动距离最小化[6]，也就是，总体时间最小化来实现高效的数据收集。

群智感知的数据收集方式，在现有的数据收集机制中广泛存在。例如，有的学者从模型的角度分析应用背景，提出拍卖的任务方案和模型，让更多的人来参与数据收集和任务分配；而原有的学者，从优化目标的角度出发，关注不同背景下的任务优化目标，在延时容忍的数据收集目标下，群智平台往往关注数据收集的志愿者无意识或者有意识地收集数据，也会预测志愿者的路径，进而设计任务分配方案，其目标往往是优化完成任务的开销。

2 研究现状

就实现最大任务最小化的目标而言，本文工作的关注点和距离优化的相关成果最相似，例如：Soylu等人提出的GVNS算法[6,7]，在该算法中他们[6]设计出总体长度最小化的总体优化目标，其应用背景是土耳其某城市的网络信号灯故障检查问题，由10名相关志愿员共同合作，完成将近200个故障信号灯的访问,他们设计的GVNS 算法能够实现总体任务的成本开销最小，通过变领域搜索机制来交换相邻区域的任务分配。此外，该算法利用多个邻居之间的移动位置交换，实现重新调整相邻区域之间的任务分配，他们采用的具体算法有 n点移动、3-opt移动、2-opt最优点移动、3-opt点移动和 2-opt 等多种任务交换的方式[8,9]实现有机的任务分配机制。Wang等人[7]分析了在时间约束情形下，多旅行商问题(MTSP)及其变化模式，设计的任务分配平台是参与者从原点出发，并最终回到原出发点的任务分配情形，并确定了最长距离最小化的优化目标。

3 基于密目的单项变邻域算法

首先，本文分析任务分布的异构性特征，群智感知平台的任务分布往往是零散的，换句话说，有的任务地点分布稀疏；有的任务地点分布稠密。通常情况下，任务分布稀疏的区域，收集任务的参与者付出较长的行走时间，完成任务收集的数量却较少；然而，任务分布稠密的区域，任务收集的参与者付出较短的行走时间，完成任务收集的数量却较多，群智感知平台的任务分布具有非均匀分布特性，也就称为任务分布的异构性特征[10,11]。

在本文中，我们关注高效数据收集问题，这可以形式化为公式(1)：最小化时间消耗集合T(Γ)，这是由下面集合的最小值决定的{T(Γ1),T(Γ2),…,T(Γi),…,T(Γn)}。其中 |Γi| 的和应该等于 |Γ|，因为Γ里所有任务都要求参与者来完成。另外，针对某个具体的任务t∈Γ，应当仅由一个参与者来完成，这主要避免任务重复分配。∀Γi,Γi′∈{Γ1,Γ2 ,…,Γi,…,Γn},Γi∩Γi′ = ∅。总之，MMT 问题可以表示如下

MMT:-MaxminT(Ti)

(1)

3.1 单区域寻找路径

按照任务聚集点之间的距离，我们用 K-means 算法把所有任务聚类为n个区域，每个区域对应一个参与者,单个区域内时间消耗如图2所示。

图2 单区域任务收集模式

该时间消耗主要由两部分组成：志愿者在指定路径行走消耗的路径时间和对三维目标的数据采集消耗的收集时间。我们尽可能寻找单个区域内耗总时间最小的路径，让其对应的任务采集者按照某个指定区域所规划的路径，移动并收集数据，进而完成三维目标的拍摄任务。

该算法的具体步骤描述如下：

第一步：随机选择本单个区域中三维任务收集点对应的位置信息。

第二步：随机选择若干个位置(lt)，与之最近的位置，其距离可以从Dijkstra 算法的变形求得简单的结果，得到最近的位置lt+1，这是局部最优的结果。如果L 中存在和序列l1,l2,…,lt+1的局部序列相同，那么，该算法区选择次近(次优)的位置任务，这样就得到路径中的最优下一个位置，求解过程也是通过 Dijkstra 算法及其变形依次求得。

第三步：删除序列l1,l2,…,lt+1的局部序列中的相同或者相近最优解，这表示lt+1已经加入l1,l2,…,lt+1序列，运行Dijkstra 算法及其变形模式的结果，并返回第二步，直到增加所有任务点到 L 序列中。

第四步：为防止过早收敛，该算法使用2-opt和3-opt相结合的算法分析方式，删除{l1,l2,…,lt,…} 序列中连续3个紧邻节点之间的非相连弧。

第五步：我们增加序列{l1,l2,…,lt,…} 逐步增加高效的序列及其组合，直到满足L的前置条件。

从遗传算法的自然适应和选择角度，不断地选择自适应函数调整比率，如公式(2)所示

(2)

经过数代的Meme选择，子孙后代比父代具有更优秀的遗传基因，进而选择更优的路径实现路径选择。公示(2)中的适应度函数可以用来评价路径个体之间的优劣程度，进而判断下一步选择的路径。具有较高适应度F函数值的路径，在下一代选择中具有更高的继承概率的个体。

3.2 区域之间的任务调整

我们所提出的MMT问题，根本目标是让最大时间消耗的参与者花费最少的代价，然而，这种代价由距离和任务分布特征，以及区域内任务数量来决定。实际上，单位区域内任务数量对总目标MMT的实现，在时间消耗方面只是局部因素，因为完成任务的总时间开销是MMT的重要组成部分。

本算法提出双向变邻域搜索结构，交换相邻区域任务，这不仅可以移动相邻任务采集点到某个区域，而且分析将其从相邻区域把任务采集点划分到本区域，以此达到局部最优的目标。如图4左图所示，在普通的变邻域结构中，算法仅仅根据任务分配的特点和采集数据的属性，交换相邻结构中的一个或者两个任务，从而改变路径和任务分配方案。这样的缺点非常明显，只考虑单项的任务分配结构和任务点的交换，这导致算法所考虑的任务分配结构减少了很大的搜索空间。但是，在图3的右图中，我们利用BGVNS算法来调整边界上的任务，考虑多个任务点的重新分配任务和路径规划，增大了搜索空间，考虑更加广阔的搜索空间，这有利于算法准确性的提高。

图3 单向变邻域任务搜索结构

图4 不同算法的定位误差对比

4 实验

在本实验中，为了实现公平对比，GB-GVNS算法网络边长在2000～3500 m的范围内进行性能模拟测试，我们采用文献[8]的地图，针对城市中采用均匀分布/非均匀任务异构分布的特征，通过实验对比参与者个数M对时间开销的影响。在图4的实验中，收集任务招募的志愿者个数都设置为6。我们测试了网格边长对定位误差的影响。由图4可知，GB-GVNS算法整体性能较好，定位误差较其他同类算法要低，且随着网格边上M的增大，定位误差随之降低，但变化不明显。

在时间开销中，我们根据具体的场景，用不同算法进行试验。为了验证算法的可用性，本部分采用完整的数据采集方案，在不同背景下分配任务，进而按照时间的节点，给出时间开销，因此，我们采用不同的应用场景在运行算法，比较时间开销，相同的任务数量，时间开销越小，运行的效率越高。在表1中，GB-GVNS算法的时间开销比同类算法的时间开销都小，这是因为采用双向变邻域的方案，增加了搜索空间，找到更加优化的任务分配方式。