分布式高维度多媒体对象匹配算法的研究

[摘 要]在解决高维度多媒体对象匹配效率问题时，仅仅依靠提高处理器的处理能力和单个计算机的数量来提高指纹匹配效率，势必会引起成本的巨额增加，并大大降低了灵活性和扩展性。为了解决这个问题，本文提出利用分布式的方式，实现从连续的K帧中提取相联系指纹的并行处理方式，这样指纹匹配的任务会被分散到一个个分布式的环境中，使匹配能够在不同的机器上并行，从而提高视频指纹匹配的效率。

[关键词]分布式匹配引擎；多媒体；视频指纹匹配；云计算

doi：10.3969/j.issn.1673 - 0194.2017.14.079

[中图分类号]TP399 [文献标识码]A [文章编号]1673-0194（2017）14-0-02

1 研究背景

随着数字视频的爆炸性增长，加上视频处理软件的增多，导致复制和盗版者可以很轻松地对视频进行任意处理，严重影响版权所有者的利益。同一视频资源经过复制或是盗版会出现各种各样的拷贝视频，当需要检索一个数字视频时，会出现大量与之相似的视频，这不仅影响了查询所需视频的检索时效，也是对视频原创者的不尊重。虽然最早用于防伪技术的数字水印技术，通过在视频中预先插入设计好的数字水印，以起到防伪和拷贝检测的作用，但随着网站视频被复制和转载数量的急剧增加，数字水印的认证精度无法得到保证，且在视频中插入数字水印的成本过高，且易被破坏，不合适个人用户进行使用。尤其是在云计算环境下，使用者通过对原视频多种方式的變换后，如添加、嵌入、自由裁切，以及对视频的外观、色彩、对比度、灰度等进行修改，就可以获得多个类似视频的版本，且变换的方式还有很多种，还可以不同的变换方式进行叠加，这些都给视频的拷贝检测及匹配带来了难度，单纯通过单一检测匹配方式是很难完成视频原创性的检测和鉴定的，在云计算环境下，为了解决高维度多媒体对象检测匹配效率的问题，本文提出通过利用分布式的方式，实现检测匹配效率的提高，利用分布式架构模型MapReduce解决高维度多媒体对象匹配效率问题，从而提高视频指纹匹配速度和准确度，并降低成本。

2 MapReduce简介

MapReduce是一种编程模型，可用于大规模的算法图形并行处理。具体工作思想是：通过指定一个Map（映射）函数，以把一组键值对映射成一组新的键值对，并指定并发的Reduce（归约）函数，以保证所有映射的键值对中的每一个共享相同的键组。其中，Map的操作是可以高度并行的，这对完成高维度的匹配非常关键。简单的理解其工作原理就是，将一些大规模的处理任务分解成许多较小的处理任务，并分散到不同的计算节点上，然后对计算处理的结果进行汇总，从而得到最终想要的结果。将计算任务分散到节点上能够充分利用数据本地性的优势。

在MapReduce程序中通过自定义图像接口ImageInputFormat ImageRecordReader，实现基于MapReduce的大量图像的在线并行处理。目前，MapReduce可处理的图像格式还比较少，主要处理的常见图片格式为bmp、jpg、png等。MapReduce有两个基本的运算单元Map和Reduce，即通过作业的提交、Map任务的分配和执行、Reduce任务的分配和执行、作业的完成四个过程，实现对图像的分布式处理。其具体的工作流程如图1所示。

3 MapReduce问题描述

云安全环境下的多媒体内容检测是多媒体数据库中的一项重要应用，在进行多媒体内容检测时，需要提取的特征向量大都是具有高维度的特性，传统的索引结果模式不能很好地实现高维度的匹配，基于此，本文提出分布式高维度多媒体对象匹配引擎的设计，这里采用MapReduce来实现。在云安全环境下，将云计算技术引入批量图像处理领域，不仅充分利用了云端的计算和存储优势，还可以极大地提高图像的处理速度，便于高效地实现分布式高维度多媒体对象的匹配，并能很好地降低图像的计算成本和存储成本。MapReduce是为大规模处理图像而设计开发的，只是用MapReduce处理单个的小图像体现不出它的优势，只有用MapReduce处理海量的图像（至少GB级别以上）时效果明显，其本身分布式处理的优势才能体现出来。

MapReduce编程模型目前所采用的图像输入格式有两种：一种是普通图文件格式：from_vid to_vid这种输入图格式，在运行程序时需要选择“random”的partition方式（分图方式）。程序的各个进程将会并行且均分读取文件的相应部分；另一种是metis输出的子图格式，为了将全图的不同部分放到不同的计算节点上进行并行计算，需要将原图划分为若干子图。划分工具采用开源的Parmetis进行，Parmetis是基于MPI进行大规模的子图划分。MapReduce本身所带的数据格式是不能被直接用来进行大规模图像处理的，它能够处理的图像文件有两种：一是将要处理的图像信息进行预处理后，转换成MapReduce数据能够识别的二进制串数据；另外一种是通过自定义处理图像文件接口方式，实现大批量图像信息的处理。基于MapReduce的图像处理能够实现从连续的K帧中提取相联系指纹的并行处理方式，这样指纹匹配的任务会被分散到一个个分布式的环境中，使匹配能够在不同的机器上并行，从而能够提高视频指纹匹配的效率。

4 基于MapReduce的图像匹配算法的设计实现

在解决高维度多媒体对象匹配效率问题时，仅仅依靠提高处理器的处理能力和单个计算机的数量来提高指纹匹配效率，势必会引起成本的巨额增加，并大大降低灵活性和扩展性，这也是传统图像处理算法的弊端，基于MapReduce的图像处理算法能够实现分布式图像处理，充分利用图像处理数据的本地性特点，实现图像高处理速度和大规模图像的分布式高效化处理。

基于MapReduce的图像处理主要通过Map函数和Reduce函数的功能实现，MapReduce需要把输入的图像信息分成大小相同的数据分片（一般为128 M），并为这些大小相同的分片分别构造一个Map任务，Map（）函数以key/value对（k1，v1）作为图像信息的输入，从而会产生另外一系列key/value对（k2，v2），这就是处理过程中的输出会被保存到本地磁盘，在shuffle阶段这些Map的数据输出（k2，v2）能够按照k2值进行聚集生成[k2，{v2，…}]，然后MapReduce程序统一将这些聚集生成的数据交给Reduce（）函数处理。Reduce（）函数把k2和聚集生成的对应列表{v2，…}当做输入，然后把输入中的每个k2和对应列表中的v2值进行合并，产生另外的一系列数据key/value对（k3，v3），新产生的这些数据最终会被写入到HDFS中。使用者只需要做好Mapper和Reducer这两类工作，就能完成分布式图像处理的程序设计。

迭代的图像计算处理流程如下。

（1）图像信息计算数据的交换：

第一步，Map函数阶段需先遍历需要计算的子图graph与其他相邻子图的图像信息情况，同时需要收集向其他节点发送的信息，并保存到本地磁盘；

第二步，通过MPI_Alltoall（）实現各个节点间所需信息的交换，每个节点把自己所需要的信息交换到后，各个节点自行计算和申请接受信息所需要的存储空间；

在每个节点内将Map生成的键值对按键值进行排序。

第四步，每个子图将自己的边界顶点发送给其所连接的邻居节点，采用MPI-Alltlall（）实现，调用MPI_Alltoallv（），将发送缓存中的数据发往各节点。

（2）计算1th/2：map。将子图graph和接受缓冲区中的数据实例化为顶点Vertex，再调用业务逻辑函数Map，将顶点Vertex生成key/value list。

（3）对生成key/value list进行排序：sort

（4）计算2th/2：reduce。将排序好的key/value list按照业务逻辑函数Reduce进行。

（5）将Reduce计算的结果更新到graph中。根据键值，对键值相同的键值组执行Reduce函数

（6）对Reduce的结果进行排序，并对迭代计算的结束条件进行判断，如果计算完毕即可给出结果，否则返回到相邻数据交换处继续执行迭代计算。

切图（non-mandatory）为兼容非图结构的MapReduce计算，框架为了能够同时支持非图结构数据的MapReduce计算，需要在函数Map与Reduce之间实现除局部排序之外的全局排序。

图结构的MapReduce计算和非图结构的MapReduce计算在计算步骤上并不一样，其中，图结构计算步骤为：开始→分图→邻居数据交换→局部Map、SortReduce-Reduce结果更新→判断迭代结束条件，如果判断结果为未结束，则返回到邻居数据交换阶段→结束。非图结构计算步骤为：开始→数据分割→Map→全局Sort、Shuffle→Reduce→判断迭代结束条件，如果判断结果为未结束，则返回到Map阶段→结束。

实验证明，通过MapReduce程序能够很好地实现分布式高维度对象的匹配，虽然研究中还有很多问题没有解决，比如，搜索算法的使用效率问题、并行广度优先搜索算法的MapReduce实现问题等，但笔者会在以后的研究中逐步进行解决。

5 结 语

随着信息时代的到来，多媒体数据将会呈现爆炸性的增长，尤其是视频数据的增加，像3D视频在生活中的地位越来越高，这对知识产权的保护提升到很高的地位、如何更好地保护视频原创者的权益、如何更好地检测和匹配出视频的不同，都是需要重点研究的内容。对于如何更好地捕获三维视频图像的深度，更好地对检测的三维视频图像进行匹配，本文虽然提出了基于分布式的高维度多媒体对象匹配方式，通过研究证明，分布式的视频检测匹配是可行的，需要在此方面进行更加深入的研究；但是具体的应用还有很长的路要走，寻找鲁棒性更好、匹配效率更高的方式和高维度索引算法，将会成为视频产权保护的重要保证措施。

主要参考文献

[1]李振举，李学军，刘涛，等.MapReduce编程模型及其在图像处理中的应用研究综述[J].测绘与空间地理信息，2015（4）.

[2]谭台哲，向云鹏.Hadoop平台下海量图像处理实现[J].计算机工程与设计，2017（4）.

[3]张兴忠，李皓，张三义.基于关键帧多特征融合的视频拷贝检测[J].太原理工大学学报，2015（5）.

[4]开源中国社区.基于MapReduce编程模型的图计算框架[EB/OL].（发表时间不详）[2017-05-03].http：//git.oschina.net/wdfnst/GraphMapReduce.