当前大量移动设备和可穿戴设备使用广泛，而在这些设备的使用中包含了一系列的连续视频检测任务，如道路车辆检测和监控、行人数量统计和街道导航等．完成这些任务主要是基于深度学习的目标检测技术，当前主流的针对实时目标检测模型的工作有文献[1-3]等．主流的目标检测模型计算准确率高，但检测实时性难以满足移动视觉任务的需求．为解决这一问题，文献[4-6]实现模型轻量化的方法降低模型的内存量和浮点计算量．文献[7-9]从端云协同的角度优化模型计算．文献[10-13]在本地设备上设计优化系统降低计算时间和能耗．文献[14]采用端云协作和本地设备相结合优化的方式．文献[11-14]借助连续视频帧包含有重复区域的特性，利用上一帧的重复结果辅助到下一帧的检模型测，以运动估计算法为基础．文献[15]采用分离前景和目标的方法实现对感兴趣物体的快速捕捉．本研究利用连续视频帧包含有重复区域的特性，主要采用图像块匹配算法用于实现连续帧去重．文献[11]提出了单方向搜索算法，该算法中的图像块匹配算法在菱形搜索算法的基础上改进，通过统计所有图像块的平均位移向量作为整张图像的位移向量，利用平均位移向量寻找连续视频帧的重复区域，但是单方向搜索算法只考虑到拍摄镜头的移动方向，没有考虑到场景物体与镜头移动方向不一致而寻找不到重复区域．为解决这一问题，本研究提出基于多方向搜索的图像块匹配算法，该搜索算法有如下创新：a．根据图像块的方向进行分类得到不同方向的集合；b．对每个集合计算平均位移向量之前，先对图像块的位移向量进行聚类；c．利用上一帧检测到的目标，在当前帧图像中搜索寻找可能与目标匹配的重复区域．1 图像块匹配算法1.1　菱形搜索算法算法图像块匹配算法用于寻找两张图像中相似的图像区域，菱形搜索算法是其中的一种经典算法．该算法基于两个匹配模板进行搜索，即大菱形模板和小菱形模板．对于已经分块的原图像和待匹配图像，菱形搜索算法会以原图像块为中心点，在待匹配图像中以大菱形模板作为搜索范围，计算和每个检测点对应图像块的平均绝对值误差，并以最小值作为最小误差块．当最小误差块落在模板中心处时，使用小菱形模板替换大菱形模板，与小菱形模板五个检测点对应图像块中计算平均绝对值误差，以最小误差块作为匹配块；当最小误差块落在大菱形模板的非中心处，则以该块作为大菱形模板中心点，重新计算大菱形模板上图像块的误差值，反复迭代直到最小误差块落在模板中心处，再用小菱形模板寻找匹配块．1.2　单方向搜索算法单方向搜索算法以菱形搜索算法为基础，目的是得到整张图像的位移向量．对于原图像和待匹配图像，单方向搜索算法一共有四个步骤．步骤1 对原图像和待匹配图像进行分块，原图像和待匹配图像尺寸大小一致，按横纵一定比例进行切片操作得到同等大小图像块，图像尺寸宽高都为L，切片间距为m，则最终得到的分块数量Nblock为Nblock=L2/m2．(1)步骤2 通过菱形搜索算法计算每个待匹配图像块在原图像的匹配块，在这个过程中算法计算平均绝对值误差EMAD，计算式为EMAD=1wh∑j=1h∑i=1w|Iij-Kij|，式中：w和h分别为图像块的宽和高；Iij为待匹配图像块；Kij为原图像块．之后算法会计算两个块之间的Spsnr值，用于后续计算平均移动向量，计算公式为Spsnr=10lg(Smax2/Emse)，(2)式中：Smax为图像点颜色的最大数值，如果每个像素点采用8 bit数据表示，那么Smax=28=256；Emse的计算方式为Emse=1wh∑i=0w-1∑j=0h-1|I(i,j)-K(i,j)|2．步骤3 在计算待匹配块和匹配块之间的Spsnr值后，设定阈值T搜集匹配块，并计算这些块的平均位移向量Mvector，计算式为Mvector(x,y)=(Nset-1∑(xi-xi'),Nset-1∑(yi-yi'))((xi,yi),(xi',yi')∈S), (3)式中：xi和yi为待匹配图像块坐标；xi'和yi'为对应的匹配块坐标；S为搜集Spsnr值大于阈值T的图像块集合；Nset为集合S的元素数量．步骤4 算法根据移动向量Mvector计算待匹配块在匹配图像中新的匹配块，并计算Spsnr值．然后仍用阈值T筛选最终匹配块，对于Spsnr值大于T值的匹配块予以保留，而其他匹配块则舍弃．最终算法将所有保留的匹配块作为原图像在待匹配图像的重复区域．单方向搜索算法可用于计算原图像和待匹配图像的平均位移向量，但实际应用场景中并非所有物体都按照同一位移向量运动．对于静止物体和建筑物，可以通过平均位移向量找到对应匹配块，但对于运动物体，其运动向量与图像的平均位移向量不一致，如果只考虑单一方向的位移向量，那么这些运动目标就无法在原始图像中找到匹配块．为此，本研究提出一种基于多方向搜索的图像块匹配算法．2 多方向搜索的图像块匹配算法基于多方向搜索的图像块匹配算法是在单方向搜索算法的基础上进行改进，经过两段处理流程：第一段流程为算法的主要部分，算法寻找连续两帧图像的匹配块；第二段流程为算法的辅助部分，算法结合上一帧检测目标结果寻找更多的匹配区域．第一段流程分为以下四个步骤．步骤1 对原图像和待匹配图像进行分块，与单方向搜索算法步骤1的分块方式一致．步骤2 使用菱形搜索算法计算每个待匹配图像块在原图像的匹配块．步骤3 以直角坐标系作为参考，匹配块图像的位移向量可以落在四个象限、四条坐标轴和原点共九种情况，因此按九个方向进行分类，然后在每个方向分类分别对位移向量计算两两之间的欧氏距离，采用k-means方法根据距离进行聚类，算法设置聚类数量k为2．对每个聚类的数据点xi和相应的中心点cj计算如下方程式，即∑minj∈1,2,...,k||xi-cj||2．每个方向可以聚类得到两个集合，每个集合根据其集合内的位移向量计算平均位移向量．步骤4 根据每个集合的平均位移向量，算法分别计算每个集合图像块在原图像上的匹配块，同时计算图像块和匹配块的Spsnr值，并设定阈值T搜集每个集合中Spsnr值大于T的匹配块，最终以搜集得到的匹配块作为原图像在待匹配图像的重复区域．根据本研究实验观察，每个方向集合的绝大部分图像块位移向量集中在一定的运动范围内，符合实际场景中的变化规律．例如：若拍摄方向沿着某一方向前进，则在该方向的集合大部分位移向量与拍摄方向相近；若场景中有沿着其他方向运动的物体，则在该方向上物体所在图像块的位移向量也是与物体运动方向一致的，只有极少数图像块是因为场景、光照等影响导致算法计算得到的位移向量是远离集合平均位移向量．因此在聚类的过程中，算法将聚类数量设为两类：第一类为集合平均位移向量上的图像块；第二类为受光照和场景影响的图像块．不采用单方向搜索算法计算平均位移向量是为了减少第二类图像块的影响，保证第一类图像块能够按照更准确的平均位移向量找到满足阈值的匹配块．算法的第二段流程是利用上一帧图像检测结果，进一步寻找更多的重复区域．算法将检测结果生成的目标框当成图像块，采用菱形搜索算法寻找当前检测图像中匹配的图像块．由于连续视频帧的特性，目标在前后帧的移动间隔很小，因此以目标作为图像块进行搜索，既可以寻找到连续出现的目标区域作为重复区域，又可以减少当单一目标被切分在不同图像块上时，有的图像块被认为是重复区域，有的图像块不是重复区域的情况．3 实验结果分析3.1　实验设计及评价指标本次实验使用的操作系统为ubuntu18.04，仅使用CPU运行实验，CPU型号为i7-8700．实验代码使用C++语言设计并实现算法，采用ncnn框架实现目标检测模型，采用mobilenetv2模型进行特征提取，将特征信息输进yolov3结构检测目标位置和类别．模型输入图像宽高L为416，图像块数量Snum为169，每个图像块的大小n为32，阈值T为20．实验数据采用KITTI数据集，该数据集由卡尔斯鲁厄理工学院和丰田美国技术研究院共同建立，包含不同类型的数据，用于评估计算机视觉技术的性能，如物体检测、跟踪、立体图像和车载环境中的视觉测距等．KITTI数据集包含从城市地区、村庄和高速公路等场景收集的真实图像数据，每幅图像包含多达15辆车和30名行人，而待检测目标具有不同程度的遮挡和截断．本实验主要使用KITTI的跟踪数据集，跟踪数据集包含20个视频数据集，每个视频数据集是一个连续的视频图像序列集，每个序列集包含数百幅图像．本实验流程如下：采用模型对连续视频帧的第一帧图像进行检测，当第二帧图像到来时，先采用搜索算法计算与前一帧图像之间的重复区域，为了实验对比，搜索算法采用三种方式，即单方向搜索算法、多方向搜索算法和无搜索算法(不寻找任何重复区域)．然后采用模型对非重复区域进行检测，并采用先寻找重复区域再检测的方式处理后续图像帧．实验的主要目的是分析多方向搜索算法为模型检测节省的计算量．三种搜索重复区域方式的优缺点将由检测区域数量、算法运行时间、图像检测时间和计算精度来衡量，这四种指标具体计算方式如下．a．检测区域数量．根据搜索算法计算得到须要重新检测块的数量，对于每个视频图像序列集，计算式为Nregion=Npatch/(NimageL2)，式中：Nregion为检测区域数量；Npatch为检测图像块总数；Nimage为图像数量．b．算法运行时间．主要统计算法在搜索两张连续图像重复区域所需要的运行时间．c．图像检测时间．在模型推断的过程中所需要的计算时间．搜索算法会计算得到当前图像和前一帧图像的重复区域，模型推断的过程中会跳过这部分区域，统计对剩下区域进行模型计算所需时间，具体计算方式为统计检测视频集所有图像的时间总和再取平均得到．d．计算精度．本实验计算单方向搜索算法的F和多方向搜索算法的F'的误差Eerr，即Eerr=F-F'，(4)式中：F为采用搜索算法的模型的检测精度；F'为不采用搜索算法的模型的检测精度．F和F'计算方式相同，F的计算式为F=2PR/(P+R)，(5)式中：P为准确率；R为召回率．准确率和召回率的计算式分别为P=Ntp/(Ntp+Nfp)；(6)R=Ntp/(Ntp+Nfn)，(7)式中：Ntp为真阳性，代表检测到目标且与真实目标类别一致的数量；Nfp为假阳性，代表检测到目标但与真实目标类别不一致的数量；Nfn为假阴性，代表未被模型检测出来但实际存在的目标．3.2　每帧图像检测区域对比表1给出了不同搜索算法方式对后续模型检测区域数量的影响，在无搜索算法情况下，模型检测图像区域为169，表中多方向搜索一表示仅使用了多方向搜索算法中的流程一，多方向搜索二表示流程一和二都使用了．表中仅列出了四个视频数据集的检测结果，但这四个视频数据集包含各种场景，场景变化从大到小的排序为video0，video19，video15和video5．从结果可以看到：单方向搜索算法对比无搜索算法检测区域数量平均减少50%，多方向搜索算法对比单方向搜索算法可以再减少25%的检测区域数量，同时多方向搜索算法对于变化较大的场景可以搜索出更多的重复区域，对于变化较小的场景提升较少．10.13245/j.hust.211106.T001表1使用不同搜索算法后模型检测区域数量搜索算法video0video5video15video19单方向搜索96603580多方向搜索一70412055多方向搜索二58341644图1给出了多方向搜索算法和单方向搜索算法在搜索重复区域上的对比，红色区域为模型须检测区域，其他区域为重复区域．可以看到：多方向搜索算法能够进一步减少检测区域数量，也不会出现物体被分成多个图像块，部分图像块须要检测而部分不须要检测的情况，保证了物体检测的完整性．10.13245/j.hust.211106.F001图1不同搜索算法须检测区域3.3　每帧图像检测时间比较在模型检测时间的实验中仍展示video0，video5，video15和video19这四组数据集的对比结果，如表2所示．当算法采用无搜索算法方式时，模型检测一张图片的计算时间开销为66 ms．在采用单方向搜索算法后，模型检测每帧图像的计算时间减少了50%，算法采用多方向搜索的方式，每幅图像的模型计算时间可以再减少约10%．每帧图像模型计算时间和检测区域数量存在线性关系，例如在采用了多方向搜索算法的情况下，video0模型计算时间减少了7 ms，对应的检测区域数量减少了26，在多方向搜索算法的基础上，利用上一帧结果寻找更多的重复区域可以进一步减少每帧图像的检测时间．总的来说，多方向搜索算法能够寻找得到更多的重复区域，为后续模型计算节省更多的开销．10.13245/j.hust.211106.T002表2使用不同搜索算法后模型检测时间搜索算法video0video5video15video19单方向搜索33241930多方向搜索一26201423多方向搜索二24191320ms3.4　计算精度比较本实验统计了单方向搜索算法和多方向搜索算法计算精度误差，该误差是与无搜索算法的精度进行计算得到，统一在20个视频集数据集上计算Eerr来衡量．计算结果为单方向搜索算法得到的误差值为1.43%，仅采用流程一的多方向搜索算法误差值为1.86%，这两种方法与无搜索算法方式对比精度几乎相差无几，精度误差值都在2%以内．当多方向搜索算法所有流程都应用时，计算误差降到了1.71%．相比于单方向搜索算法，多方向搜索算法计算精度误差略微高了一些，这是由于多方向搜索算法搜集了更多的可重复区域，在模型检测精度上的精细程度要小一些，但这个细微误差可忽略不计．3.5　算法运行时间对比本实验还测试了不同搜索算法运行时间对比，其中，单方向搜索算法运行时间为3.1 ms，多方向搜索的算法运行时间为3.3 ms，模型检测单帧图像时间为66.3 ms．可以看出：这两种搜索算法的计算时间都很小，但应用这两种算法使得后续模型检测时间的成本大大降低了，相比之下，算法本身带来的额外计算时间开销可以忽略不计．虽然多方向搜索算法的计算时间比单方向搜索算法的计算时间多，但是增加算法的计算代价并不大，与减少模型时间相比，计算代价可以忽略不计．3.6　多方向搜索聚类情况图2为video19数据集中的图片进行多方向搜索算法时某一方向上的聚类情况，图中每个点表示图像块通过菱形搜索算法寻找到的匹配块的偏移向量，且大部分偏移向量存在相同值使得图中的点包含重叠的情况．可以看到：大部分图像块(红色)沿着移动向量可以找到匹配块，只有极少部分点(绿色)会受场景光照等影响寻找到的匹配块位置偏离，而采用聚类方式可以使得后续计算Mvector时避免偏离点的干扰．10.13245/j.hust.211106.F002图2算法聚类情况4 结语基于多方向搜索的连续帧目标检测去重算法在精度损失和算法运行开销时间不增加的情况下，能够在前人工作基础上寻找到连续帧中更多的重复区域，用于减少后续模型检测图像的时间．从结果上看，多方向搜索算法可以减少模型18%的计算区域数量，减少约8 ms的检测时间，提升了检测效率．