移动群智感知中图片情境信息的聚类动态查找算法

2021-07-27 02:59蔡丽萍张晨晨李世宝刘建航

计算机与现代化 2021年7期

蔡丽萍,张晨晨,李世宝,刘建航

(1.中国石油大学(华东)计算机科学与技术学院,山东青岛 266580；2.中国石油大学(华东)海洋与空间信息学院,山东青岛 266580)

0 引言

移动群智感知(Mobile Crowdsensing, MCS)[1]是当前移动计算与大数据应用领域的研究热点，结合众包思想和移动感知，将普通用户的移动智能设备作为基本的感知单元，通过相互协作进而形成群智感知网络，实现感知任务分发与感知数据收集，完成大规模的、复杂的社会感知任务。其中使用智能终端摄像头为主的感知方式[2]近年来越来越受到学术界和工业界的重视，由于图片和视频携带了更丰富的感知信息，因此广泛应用于各个领域，例如：平面图生成[3]、室内定位[4-7]、场景重建[8-10]、城市感知[11-12]、灾难救援[13-14]等。

图片感知数据收集是移动群智感知中关键挑战之一[15]，如何利用群智感知数据的异构特征对图片数据进行预筛选，去除冗余图片，提高数据集质量至关重要。合理的图片选择不但可以使移动群智感知系统在有限的带宽资源下传输更多的视觉信息，而且能帮助保证激励机制的有效性。但是，由于感知任务多样性，分布式上传动态数据流以及基于特征值的图像相似度判断的计算复杂性，使得移动群智感知的图片数据去除冗余具有一定挑战。为了提高图片数据质量，减少低质量采集与重复采集，重点在于如何降低收到冗余图片数据的概率，快速判断图片的价值，决定图片是否上传。

目前已经有很多学者研究移动群智感知中图片数据去除冗余的问题，PhotoNet[16]在拍照位置相距较远的前提下选取图像颜色直方图相差较大的多张图片；FlierMeet[17]提取图像的SIFT特征值，结合时间差和地理距离，采用判定树的方法判定图像是否重复；SmartPhoto[18]根据拍照方向的角度差判定相似度，并基于贪心思想选择拍照角度差别大的图片；MRC[19]提出了一个框架，首先要求设备上传元数据，通过将元数据与先前内容相关的信息进行比较决定是否上传；BEES[20]提出了一种带宽和能源高效的图像共享系统，根据手机电量决定特征值相似匹配精度。CrowdPic[21]为通用图片群智感知数据收集框架定义任务模型，并提出了一种金字塔树PTree，基于PTree的框架可以从数据流中选择具有高效用范围和低冗余子集，但是在照片情境信息聚类时仍然存在近边缘相似的问题。

本文提出一种移动群智感知图片数据动态聚类算法，通过利用照片的情境信息(如：地点、时间、拍摄角度等)低维异构数据聚类，将可能相似的图片聚类到同一区间，为的是减少或避免基于图片特征值的高维数据相似检测。为了适应移动群智感知分布式和数据流收集形式，该算法在优化聚类的基础上，提出动态查找算法(Dynamic Find Algorithm, DFA)，解决动态聚类近边缘相似的问题。通过收集带有情境信息的照片数据，验证所提算法的有效性。

1 移动群智感知任务模型

1.1 移动群智感知任务流程

移动群智感知任务流程可以通过任务启动、任务执行、数据聚合和结果交付4阶段过程来表征，如图1所示。在任务启动阶段，数据请求者可以定义不同要求的感知任务，任务管理后台将任务分发给合适的参与人员，或者由参与人员自行选择任务。在任务执行阶段，参与人员根据任务要求拍摄照片，并将其上传到服务端。由于服务端间歇性地接收分布式参与人员上传的图片数据，因此不可避免地在图片中可能存在冗余，并且某些参与人员提供的数据的质量可能很低。可以在任务执行和数据聚合2个阶段去除冗余的图片数据。任务执行阶段合理的用户招募[22]可以减少冗余，在数据聚合阶段，将根据任务规范和低维数据对图片进行分组、过滤和选择。在结果交付阶段，任务完成后，预选择后的数据将提供给数据请求者。

图1 移动群智感知任务流程

1.2 PTree图片数据聚类方法

PTree[21]是移动群智感知分布式数据流有效的聚类方法。如图2所示，感知照片数据包括地点、时间、拍摄角度和图片特征的信息，PTree分为5层，除了根节点，每层分别对应感知照片数据的某个一维属性，每个非叶子节点对应了某个特征的聚类，每个叶子节点对应相应的感知数据。

图2 PTree的基本结构和生长

PTree以先入为主的形式开辟分支，当有新的照片数据进入PTree，首先从最上层判断是否在相应的区间内，如果在相应的区间内聚类到已有的叶子区间，否则开辟新分支，以此类推，从最上层到最下层，当地点、时间和拍摄角度都在同一区间时再进行高维数据图像相似判断。如果一个感知图片数据使PTree长出新的非叶子节点，说明该数据是新数据，即高价值的数据仅需要低维数据的计算，该计算是非常高效的。

2 聚类与动态查找

2.1 聚类改进

PTree中每层对应感知数据一个信息，但是由于图像特征是高维数据，有别于地点、拍摄角度等低维数据，图像特征的提取依赖于智能设备端复杂的计算，同时根据特征点的相似判断也需要一定的时间复杂度，因此如何减少和避免图片特征提取和相似计算是个关键问题。

图片数据可以区分为低维数据和高维的图像特征数据，智能设备端先向服务端上传多种低维数据，按照已有的低维数据进行聚类，当聚类开辟新分支时反馈智能设备端直接上传，当进入已有分支时，反馈智能设备端提取图片特征值上传，通过判断是否与分支内已有图片相似决定是否上传。用分2步上传的方式以减少智能设备端计算图片特征值耗费的电量、时间和流量数据。

先入为主的动态数据流聚类方式存在后入者在边缘区域与相邻区间距离过近的问题，如图3所示，P1先到生成N1区域，P2后续生成新的区域N2，P3进入N1的区域，P4进入N1的区域，如果P1、P3、P4归为一类进行相似比较，会存在P2的距离和P4最近的问题，实际上P4的最佳相似度判断区域如图3(a)虚线所示区域，这个问题是普遍的，角度信息也会存在这个问题，如图3(b)所示，P4和P3不在同一个区域，但是会存在相似的可能性。

图3 动态聚类近边缘相似

可以将位置信息聚类问题转化为随机落在圆内的随机2点的平均距离，而最佳相似区域可以看作是随机落在圆内的随机一点到圆心的平均距离，通过计算两者距离期望表示理论提升。

对于先入为主的位置信息聚类问题，通过计算单位圆上随机一点到随机一点的距离期望表示平均距离。在单位圆内的x处随机取一个点作为第1个点。从第1个点距离r处取随机第2个点，其密度函数f(r)为：

对于f(r|x)，当r<1-x，距离x点为r的点在单位圆内，因此：

f(r|x)=2r

当1-x≤r≤2，只有部分点落在单位圆内，因此：

计算得：

单位圆内随机点到随机点的距离期望：

对于最佳相似区域，可以通过计算从单位圆的圆心到圆内随机一点的距离期望。其分布函数F(x)：

密度函数f(x)：

f(x)=2x

从单位圆心到圆内随机一点的距离期望：

对于一维信息，如照片方向、时间等，假设x是区间[0,1]中的随机一点。随机一点到中点距离期望：

[0,1]内随机2点x、y之间的距离期望：

由上可得，通过最佳相似区域优化，二维位置信息的平均距离期望可减少26.36%，一维方向时间信息的平均距离期望可减少25%。因此在聚类算法PTree的基础上，优化并提出了DFA动态查找算法，用来快速找到图中所示的虚线区域。基于对PTree算法的改造，如图4所示，塔型树的每一层对应元数据的一个维度(例如三层树结构可以对应位置、角度、时间3个维度)。通过一次生长多条枝叶表示同一批次上传多张图片的情境信息，生长前服务端存储了P1和P2的数据信息，经过聚类生长，生成了P4、P6实枝叶和P3、P5、P7虚枝叶。实枝叶的图像数据服务端向智能设备端发送指令直接上传，虚枝叶的图像数据需要智能设备端提取图像特征属性，然后上传图片特征信息通过DFA算法查找最佳相似区域内的数据。

图4 PTree聚类生长虚枝叶

2.2 动态查找算法

DFA算法的目的是找到虚枝叶数据的最佳相似区域，从而解决聚类区间临近边缘区域相似的问题。PTree生长结束后，记录虚枝叶每层的属性，定义聚类阈值为a，即大于a时2个数据之间没有相似关系，定义距离小于a/2为非边缘区域，当前数据和节点中心点数据相差大于a/2定义为虚枝叶层属性，并且只要上层级被定义为虚节点，剩下层级全部为虚节点。

为了查找最佳相似区域，采用局部扩大查找合适的数据点，再缩小至最优范围区间的思想，如图5所示。N1区域中心点P1，半径为a，非边缘区域为a/2，P9和P10同属于N1，P9距离P1大于a/2则会出现边缘相似问题，需要扩大至2a范围查找相邻区间到可能相似区间。为了查找距离P9小于a的点，即图5中半径为a的虚线区域以内的部分，DFA算法不需要遍历所有点，根据PTree的结构，查找中心点距离P9为2a以内的区域，即N1、N2、N3区域，缩小范围后只需在N1、N2、N3区域内查找距离P9小于a的点，即P1、P5、P6、P8为P9可能相似点。P10距离P1小于a/2没有近边缘相似问题不执行扩大范围查找。以3层的PTree为例，假设L2层为位置属性，L3层为拍摄角度属性，L4层为时间属性，3层PTree会出现以下4种情况：

图5 DFA动态查找算法

1)虚枝叶层属性为L2层位置距离不在a/2以内，无论L3层方向角度差，L4层时间差在a/2与否，将会从L2层执行2a范围查找，查找L2层、L3层、L4层。

2)虚枝叶层属性为L2层位置距离在a/2以内，L3层方向角度差不在a/2以内，无论L4层时间差是否在a/2以内，将会从L3层执行2a范围查找，查找L3层、L4层。

3)虚枝叶层属性为L2层位置距离在a/2以内，L3层方向角度差在a/2以内，L4层时间差不在a/2以内。仅L4层执行2a范围查找。

4)虚枝叶层属性为L2层、L3层、L4层都在a/2以内。不会执行2a范围查找，即在PTree L4层同一父节点下的数据区间。

我曾经有段时间寄居在朋友家，朋友是台州人，嗜食海鲜。她母亲每次来小住，必定满桌海鲜佳肴。临行之前，因为担心我们在外面吃得不好，朋友妈妈还会煮上一大锅腊味焖饭。米饭里夹杂着腊肠、豌豆、香菇、土豆丁、萝卜丁、玉米粒，当然不能少了干贝这样的鲜美之味。这一锅焖饭五彩斑斓，圆润的米粒里吸收了腊味的咸香，萝卜、豌豆和玉米粒味道各异，每一口嚼下去都是惊喜。所以，我们俩抱着饭锅吃了几天的腊味焖饭，也丝毫不觉得厌腻。

经过DFA算法查找为同一可能相似区间的图像数据需要用特征相似判断做进一步处理，对相似的图片数据进行过滤，DFA动态查找递归算法如算法1所示。

算法1 动态查找算法DynamicFind

输入 p: 一个照片当前层元数据，l: 层编号，Nc: 当前树节点，fl: 当前虚枝叶层属性, a: 聚类阈值

输出 P: 最优可能相似区间数据集

1: if EndBranch(Nc) then

2: for each leaf:Nc then

3: if abs(leaf-p)