基于EMD距离的大规模图像数据相似性搜索方法

摘要

本发明公开了一种基于EMD距离的大规模图像数据相似性搜索方法，步骤包括：设计用于映射至一维实数键值空间Ω(Φ)的图像数据映射函数f；启动作业MR1，估计Ω(Φ)中各键值的负载；启动作业MR2，通过Map任务基于所估计的键值负载对Ω(Φ)进行切割，将切割区域对应的数据分片发送给Reduce任务；基于f将各Reduce任务接收的图像数据映射至Ω(Φ)中的键值，基于该键值构建面向EMD距离的索引结构；基于该索引结构执行基于EMD距离的相似性搜索；将MR2中各Reduce任务基于EMD距离相似性搜索的执行结果取并集输出。本发明具有网络传输数据量更低、计算负载分配更均衡，相似性搜索效率更高、对大数据集分析处理可扩展性更好的优点。

说明书

技术领域

本发明涉及计算机图像数据的相似性搜索技术，具体涉及一种基于EMD距离的大规模 图像数据相似性搜索方法。

背景技术

随着便携式电脑、智能手机和数码相机等数字化设备的普及，以图像为代表的多媒体数 据日益增多，呈爆炸式增长。这一切都告示着图像大数据时代已经到来。目前学术界、工业 界甚至于政府机构都已经开始密切关注图像大数据的分析处理问题。

要从大规模图像数据集中寻找具有重要价值的图像信息，传统的基于文本的图像检索方 式(Text-Based Image Retrieval，简称TBIR)显然无法满足需求。因为TBIR技术依赖于人工 对图像内容的手工标注，当图像数量急剧增大时就带来了两个严重问题：首先，人工注解的 工作量太大，注解成本太高；其次，人工注解的主观性太强，直接影响图像检索结果的可靠 性。于是，基于内容的图像检索技术(Content-Based Image Retrieval，简称CBIR)在图像大 数据时代越发被人们所重视，已成为21世纪必须攻克的关键技术之一。CBIR技术直接根据 图像内容的视觉特征(例如颜色、纹理和形状特征等)对图像数据集进行相似性检索，突破 了TBIR技术基于图像标注词检索的局限性，更适应于对大规模图像数据的分析处理。

在计算机视觉研究领域，图像内部的视觉特征往往被表示成直方图形式的多维向量，形 式为h_x＝{x₁,…,x_l}，其中x_i表示直方图h_x的第i个数据桶(即第i维)，记录了图像内容的视觉 特征在视觉特征空间的第i个子空间内的出现频数。例如反映图像内容灰度分布特性的图像灰 度直方图，表征图像内容色彩分布特性的颜色直方图，描述图像纹理分布特征的边缘直方图， 描述图像局部目标的表象和形状的梯度直方图以及基于尺度不变特征变换SIFT (Scale-Invariant Feature Transform)描述子构建的SIFT直方图等。基于直方图形式表征的图 像视觉特征，对两张图像内容的相似性比较即转化为对它们直方图之间的相似性匹配。因此， 针对大规模图像数据集的分析处理首先需要解决的问题是为图像视觉特征直方图选择高质量 的直方图相似性度量函数，以确保基于内容的图像检索技术的检索质量。

传统直方图相似性度量函数，例如曼哈顿距离和欧几里得距离，仅量化了直方图对应数 据桶之间的差异性，具有明显的局限性。图1中展示了从三张图像分别提取的图像灰度直方 图，表示为h_x，h_y和h_z。其中，直方图h_y相比于直方图h_z直观上更相似于直方图h_x，只是由 于使用设备和拍摄条件不同导致直方图h_x和直方图h_y所对应的两幅图像的灰度分布特性在 灰度属性域上存在微小偏移。然而，若基于曼哈顿距离计算它们彼此间的相似性会得到直方 图h_z更相似于直方图h_x的相反结论，进而降低基于内容的图像检索的检索精度。为了解决这 些问题，计算机视觉领域的研究人员提出了土堆移动距离(Earth Mover’s Distance)，简称为 EMD距离。EMD距离将两个直方图之间的相似性量化为将其中一个直方图转化为另一个直 方图所需付出的最小搬运代价。可见，EMD距离不仅考虑了直方图对应数据桶之间的差异性， 还兼顾考虑了相邻数据桶之间的差异性。如图1所示，基于EMD距离(计直方图数据桶之 间的搬运代价为d_ij)，我们可以得到直方图h_y相比于直方图h_z更相似于直方图h_x的正确结论， 符合人们对直方图相似性的直观认识。

表1EMD距离和欧几里得距离的平均计算时间比较(单位：秒)

综上，EMD距离比传统直方图相似性距离函数更鲁棒，被广泛应用于基于内容的图像相 似性检索，用以提高包括图像雷同检测，图像去重以及图像分类在内的图像相似性检索应用 的检索结果精度。然而，求解EMD距离具有O(l³logl)的高计算时间复杂度，其中l为直方图 数据桶的个数。表1统计了在直方图数据桶个数分别为8桶、30桶、128桶和256桶的四个 真实数据集上EMD距离和欧几里得距离的平均计算时间。可见，EMD距离的平均计算时间 是欧几里得距离平均计算时间的100倍以上，这无疑阻碍了EMD距离在大规模图像数据集 分析处理中的应用。

近年来研究人员提出了一系列优化算法旨于提高基于EMD距离的相似性搜索的查询处 理效率。大部分优化算法基于“扫描——求精”的问题求解框架进行查询优化。即多次线性扫 描数据集，每次扫描都利用一个计算复杂度较低的EMD距离的下界(或上界)距离函数过 滤一些与查询对象肯定不相似(或肯定相似)的直方图数据，通过降低整个查询处理过程中 EMD距离的计算次数来提高基于EMD距离的相似性搜索效率。然而“扫描——求精”的问题 求解框架需要多次扫描数据集，因此该框架在处理大数据集时缺乏良好的可扩展性。基于此， 一些研究人员致力于为基于EMD距离的相似性查询处理设计有效的直方图数据索引机制， 减少查询处理时对无关记录的访问与计算。然而，这些优化算法都是针对集中式计算环境设 计的，限制了算法所能处理的图像数据规模。

在大数据浪潮的推动下，2002年谷歌公司提出了映射规约(MapReduce)分布式编程框 架，通常被称为MapReduce框架。MapReduce框架的工作流示意图如图2所示。其基本思想 是将处理大规模数据集的大任务分解成多个处理小数据集的小任务来实现分而治之。具体而 言，系统有多个映射(Map)任务，每个映射任务的输入都是分布式文件系统中的一个原始 的文件块。Map任务将文件块转换成一个键-值对序列，并将这些键-值对按照它们的键值大 小排序。随后具有相同键的键值对在数据洗牌阶段被发送到同一个规约(Reduce)任务中， 该Reduce任务随后按照用户定义的处理逻辑处理对应于同一键的所有键值并输出最终结果。 MapReduce框架有诸多好处：首先，将问题分而治之，增加了对大规模数据的并发处理能力； 其二，MapReduce框架简单明了，很容易在数据所在地进行编程处理，即有效实现了“将计 算推送到数据”，避免了“将数据推送到计算”时的大量数据传输开销；其三，MapReduce 框架基于键-值对处理数据，而不是像传统数据库那样基于繁复的数据模式来处理数据，因而 便于处理图像数据这样的非结构化数据。由于MapReduce模型具有诸多优势，一经提出就受 到极大关注。借助于MapReduce分布式编程框架，研究人员们提出了Melody-Join算法，即 基于MapReduce框架下并行化基于EMD距离的数据集相似性连接算法。然而，Melody-Join 具有以下两方面局限性。首先，Melody-Join在分布式代价模型定义上仍然以数据量的多少来 估计一个计算节点的相似性连接计算代价。鉴于EMD距离的高计算复杂性，以数据量(而 不是以实际发生的EMD距离计算次数)来估计计算节点的计算代价显然有失偏颇，不利于 均衡各个计算节点的计算负载，直接降低了整个分布式系统的查询处理性能。另一方面当图 像数据集的规模激增的时候，Melody-Join中的分布式索引对无关计算的过滤性能仍显得力不 从心。以上两方面直接导致Melody-Join在处理大规模图像数据集时的可扩展性能不能满足实 际应用的需求。

发明内容

本发明要解决的技术问题是：针对现有技术的上述技术问题，提供一种网络传输数据更 低、计算负载分配更均衡，相似性搜索效率更高、对大数据集分析处理具有可扩展性更好的 基于EMD距离的大规模图像数据相似性搜索方法。

为了解决上述技术问题，本发明采用的技术方案为：

一种基于EMD距离的大规模图像数据相似性搜索方法，步骤包括：

1)设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据映射函数f，所述图像 数据映射函数f包含图像数据和一维实数键值空间Ω(Φ)中键值之间的映射关系；

2)启动一个MapReduce作业MR1，通过MapReduce作业MR1基于查询图像集Q和待 检索图像集I估计所述一维实数键值空间Ω(Φ)中各个键值所对应的查询处理负载量；

3)启动一个MapReduce作业MR2，通过MapReduce作业MR2的Map任务基于所述步 骤2)估计得到的查询处理负载量对一维实数键值空间Ω(Φ)进行切割，分别将所述一维实数 键值空间Ω(Φ)不同切割区域所对应的查询图像集Q中的图像数据分片或待检索图像集I中的 图像数据分片发送给MapReduce作业MR2中的各个Reduce任务；

4)基于所述图像数据映射函数f将MapReduce作业MR2中各个Reduce任务所接收的 图像数据分片划分为查询图像集数据分片Q′和待检索图像集数据分片I′并分别映射至一维实 数键值空间Ω(Φ)，得到查询图像集数据分片Q′或待检索图像集数据分片I′在一维实数键值空 间Ω(Φ)中对应的键值；基于所述待检索图像集数据分片I′在一维实数键值空间Ω(Φ)中对应 的键值构建面向EMD距离的索引；

5)所述MapReduce作业MR2中各个Reduce任务分别基于所述面向EMD距离的索引执 行查询图像集数据分片Q′中的每个查询对象在待检索图像集数据分片I′上基于EMD距离的 相似性搜索；

6)MapReduce作业MR2中的每个Reduce任务将查询图像集数据分片Q′中每个查询对 象基于EMD距离的相似性搜索的执行结果取并集输出。

优选地，所述步骤1)中设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据 映射函数f时，对于给定任意一组EMD距离对偶线性规划问题的可行解，记为Φ＝{Ψ,Π}， 其中Ψ＝{ψ₁,…,ψ_l}和Π＝{π₁,…,π_l}，其中l表示图像数据的直方图中的数据桶个数，所述图 像数据映射函数f通过式(1)计算图像数据集中每张图像X的直方图h_x＝{x₁,…,x_l}的键值 key(h_x,Φ)，从而将图像X映射至一维实数键值空间Ω(Φ)中；

f(X,Φ)＝key(h_x,Φ)＝∑_iψ_i·x_i  (1)

式(1)中，f(X,Φ)表示将图像X基于一组EMD距离对偶线性规划问题的可行解Φ映 射至一维实数键值空间Ω(Φ)的映射函数，key(h_x,Φ)表示图像X的直方图h_x＝{x₁，…,x_l}的键 值，表示将所有(ψ_i·x_i)的值求和且1≤i≤l，其中l表示图像数据的直方图中的数据 桶个数，ψ_i表示一组可行解Φ＝{Ψ,Π}中向量Ψ＝{ψ₁,…,ψ_l}的第i维的取值，x_i表示图像X 的直方图h_x＝{x₁,…,x_l}的第i维的取值。

优选地，所述步骤1)中设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据 映射函数f时，所述图像数据映射函数f将EMD距离值相近的直方图所对应的图像数据映射 至一维实数键值空间Ω(Φ)中的临近键值区域内，与任意目标图像X相似的所有图像Y均满 足式(2)，其中目标图像X的直方图为h_x＝{x₁,…,x_l}，图像Y的直方图为h_y＝{y₁,…,y_l}；且 相似图像Y的直方图h_y的键值key(h_y,Φ)必落在式(3)所示的一维实数键值空间Ω(Φ)中的键 值区间内；

EMD(h_x,h_y)≤θ  (2)

式(2)中，h_x表示目标图像X的直方图，h_y表示与目标图像X相似的图像Y的直方图， EMD(h_x,h_y)表示直方图h_x和直方图h_y之间的EMD距离，θ表示给定的相似性阈值；

$[{\min }_{i=1}^l({\psi }_1+{\pi }_i)+\mathrm{key}(h_x,\Phi )-\theta ,\theta -\mathrm{ckey}(h_x,\Phi )]---\left(3\right)$

式(3)中，ψ_i表示表示一组可行解Φ＝{Ψ,Π}中向量Ψ＝{ψ₁,…,ψ_n}的第i维的取值，π_i表示表示一组可行解Φ＝{Ψ,Π}中向量Π＝{π₁,…,π_n}的第i维的取值，表示求 取所有(ψ_i+π_i)值中的最小值且1≤i≤l，其中l表示图像数据的直方图中的数据桶个数， key(h_x,Φ)表示直方图h_x基于可行解Φ计算得到的键值，Φ表示EMD距离对偶线型规划问题 的一组可行解，θ表示给定的相似性阈值，其中ckey(h_x,Φ)表示键值key(h_x,Φ)的对称键值， ckey(h_x,Φ)的表达式如式(4)所示；

$\mathrm{ckey}(h_x,\Phi )=\underset{j=1}{\overset{l}{\Sigma }}({\pi }_j·x_j)---\left(4\right)$

式(4)中，表示将所有(π_j·x_j)的值求和且1≤j≤l，其中l表示图像数据的直 方图中的数据桶个数，π_j表示一组可行解Φ＝{Ψ,Π}中向量Π＝{π₁,…,π_n}的第j维的取值， x_j表示直方图h_x＝{x₁,…,x_l}的第j维的取值。

优选地，所述步骤2)启动的MapReduce作业MR1包括m个Map任务和1个Reduce 任务；所述MapReduce作业MR1的每一个Map任务执行下述步骤：①对查询图像集Q的文 件分块Q_i或待检索图像集I的文件分块I_i进行随机采样；②、挑选出基数分别为|Q_i|·p和|I_i|·p 的两个图像数据子集分发给MapReduce作业MR1的Reduce任务，其中p表示预设的采样比 率；所述MapReduce作业MR1的Reduce任务执行下述步骤：①、接收来自m个Map任务 发送的图像数据，将所接收的图像数据根据其携带的标签划分成查询图像集Q的子集Q′、待 检索图像集I的子集I′；②、基于EMD距离相似性搜索算法执行查询图像集Q的子集Q′中 的每一个查询对象q_i在待检索图像集I的子集I′上的相似性检索，并记录相似性检索的时间 代价c_i作为其查询处理负载代价；③、将每一个查询对象q_i的直方图基于给定用于数据划 分的一组EMD距离对偶线性规划问题的可行解Φ_partition计算得到键值和该查 询对象q_i对应的查询负载代价c_i组成二元组④、执行完查询图像集子 集Q的子集Q′中所有查询对象q_i的查询后，将得到的由所有二元组组 成的“键值-查询负载代价”二元组的序列写入分布式文件系统 中。

优选地，所述步骤3)启动的MapReduce作业MR2包括m个Map任务和n个Reduce 任务，其中每一个Map任务执行下述步骤：

3.1)从分布式文件系统中读取“键值-查询负载代价”二元组的序列

3.2)将所述序列中的每个二元组基于其 键值进行从小到大排序得到排序后的列表为List_sorted{<key(q_i,Φ_partition),c_i>}， 同时累加其中的查询负载代价c_i得到总查询负载代价C；

3.3)基于排序后的列表List_sorted{<key(q_i,Φ_partition),c_i>}找到所述可行解Φ_partition所对应的一 维实数键值空间Ω(Φ_partition)中的n-1个分位数{key_i,…,key_n-1}，使得排序后的列表 List_sorted{<key(q_i,Φ_partition),c_i>}中落在任意两个相邻分位数区间内的键值的累计查询负载值约 等于平均查询负载值c，其中平均查询负载值c为总查询负载C除以MapReduce作业MR2 中Reduce任务的数量n所得到的结果；

3.4)从分布式存储系统中读取查询图像集Q和待检索图像集I中的每一个数据分块；针 对读取的每一个数据分块包含的图像数据d，首先抽取图像数据d直方图h_d，并基于所述直 方图h_d和所述EMD距离对偶线性规划问题的可行解Φ_partition计算出所述图像数据d在所述可 行解Φ_partition所对应的一维实数映射空间Ω(Φ_partition)中的键值key(h_d,Φ_partition)；然后对图像数 据d的键值key(h_d,Φ_partition)进行判断，若key(h_d,Φ_partition)≤key₁，则将图像数据d发送给第1 个Reduce任务；若key_i≤key(h_d,Φ_partition)≤key_i+1，则将图像数据d发送给第i+1个Reduce任 务；若key_n-1≤key(h_d,Φ_partition)，则将图像数据d发送给第n个Reduce任务，其中key₁表示所 述n-1个分位数{key_i,…,key_n-1}中的第1个分位数，key_i表示所述n-1个分位数{key_i,…,key_n-1} 中的第i个分位数，key_i+1表示所述n-1个分位数{key_i,…,key_n-1}中的第i+1个分位数，key_n-1表 示所述n-1个分位数{key_i,…,key_n-1}中的第n-1个分位数。

优选地，所述步骤4)的详细步骤包括：

4.1)MapReduce作业MR2中各个Reduce任务将MapReduce作业MR2中各个Map任务 发送过来的图像数据分片根据各个图像数据携带的标签划分成查询图像集数据分片Q′和待检 索图像集数据分片I′，所述查询图像集数据分片Q′为查询图像集Q的子集，所述待检索图像 集数据分片I′为待检索图像集I的子集；

4.2)已知由L组EMD距离对偶线性规划问题的可行解构成的可行解集合，记为 S_Φ＝{Φ₁,…,Φ_L}，对待检索图像集数据分片I′中的每一个待检索图像对象i，其中1≤i≤L， 基于可行解集合S_Φ中每组可行解Φ_i计算待检索图像对象i的直方图h_i在Φ_i所对应的一维映 射空间Ω_i(Φ_i)内的键值key(h_i,Φ_i)，因此针对待检索图像集数据分片I′中的每个待检索图像对 象i而言，可得到相对于L组可行解的L个键值{key(h_i,Φ_i),…,key(h_i,Φ_L)}；

4.3)以待检索图像集数据分片I′中每张图像基于所述可行解集合S_Φ中同一组可行解Φ_i计 算得到的键值为B⁺树的键值构建一棵B⁺树索引结构，记为B⁺(Φ_i)，因为所述可行解集合S_Φ一共包含L组可行解，因此共为待检索图像集数据分片I′构建了L棵B⁺树索引结构，记为 {B⁺(Φ₁),…,B⁺(Φ_L)}；对于查询图像集数据分片Q′中的任一查询对象q，基于所述L棵B⁺树 索引结构可以得到L组查询候选集{Ca(q,Φ₁),…,Ca(q,Φ_L)}，则所述L组查询候选集 {Ca(q,Φ₁),…,Ca(q,Φ_L)}的交集Ca(q,Φ₁)∩…∩Ca(q,Φ_L)即构成了查询对象q在待检索图像 集数据分片I′上的查询候选集Ca(q)。

优选地，所述步骤4.2)中已知由L组EMD距离对偶线性规划问题的可行解构成的可行 解集合中L的取值为3。

优选地，所述步骤5)通过所述MapReduce作业MR2中各个的Reduce任务分别基于所 述面向EMD距离的索引执行查询图像集数据分片Q′中的每个查询对象在待检索图像集数据 分片I′上基于EMD距离的相似性搜索的详细步骤包括：

5.1)将查询图像集数据分片Q′中的每个查询对象q按照其基于已知L组EMD距离对偶 线性规划问题的可行解集合S_Φ中某组可行解Φ_i计算得到的一维键值进行从小到大排序；

5.2)基于所述B⁺树索引结构{B⁺(Φ₁),…,B⁺(Φ_L)}，根据步骤5.1)中从小到大排序得到的 顺序，执行查询图像集数据分片Q′中的每个查询对象q在待检索图像集数据分片I′上基于 EMD距离的相似性搜索，为每个查询对象q检索出待检索图像集数据分片I′中与其EMD距 离相近的所有查询对象。

优选地，所述步骤5.2)的详细步骤包括：

5.2.1)基于所述B⁺树索引结构{B⁺(Φ₁),…,B⁺(Φ_L)}，并利用式(3)所示的索引过滤结论 获取每个查询对象q在待检索图像集数据分片I′上的查询候选集Ca(q)；并统计所述可行解集 合S_Φ＝{Φ₁,…,Φ_L}中每组EMD距离对偶线性规划问题的可行解Φ_i对待检索图像集数据分片 I′中无关图像数据的过滤性能；

5.2.2)在步骤5.1)从小到大排序得到的顺序的基础上，若每个查询对象q的上一查询对 象q′的查询结果集RS(q′)不为空，则基于三角不等式理论过滤每个查询对象q的查询候选集 Ca(q)，得到约简后的查询候选集Ca(q)₁；

5.2.3)基于EMD距离的下界函数LB_IM和基于EMD距离的上界函数UB_p进一步约简每 个查询对象q的查询候选集Ca(q)₁，得到约简后的查询候选集Ca(q)₂；

5.2.4)针对每个查询对象q的查询候选集Ca(q)₂中的每个图像数据i，计算图像数据i的 直方图h_i和对应的查询对象q的直方图h_q之间的EMD距离EMD(h_q,h_i)，若该EMD距离 EMD(h_q,h_i)小于给定的相似性阈值θ，则判定图像数据i为查询对象q的查询结果，将查询结 果二元组<i,EMD(h_q,h_i)>插入查询对象q的结果列表RS(q)，并同时写入分布式文件系统中； 同时，在计算计算图像数据i的直方图h_i和对应的查询对象q的直方图h_q之间的EMD距离 EMD(h_q,h_i)的过程中会顺带产生一组新的EMD距离对偶线性规划问题的可行解将所述 可行解插入新可行解候选列表

5.2.5)从所述新可行解候选集合中随机挑选一组新可行解Φ_new，根据统计得到的所 述可行解集合S_Φ＝{Φ₁,…,Φ_L}中每组可行解Φ_i对所述待检索图像集数据分片I′中无关图像数 据的过滤性能，用Φ_new替换掉所述可行解集合S_Φ＝{Φ₁,…,Φ_L}中过滤性能最差的那组可行 解；

5.2.6)将各个查询对象q的查询结果集RS(q)作为查询对象q检索出的待检索图像集数据 分片I′中与其EMD距离相近的所有查询对象输出。

优选地，所述步骤5.2.2)中基于三角不等式理论过滤每个查询对象q的查询候选集Ca(q) 的详细步骤包括：针对每个查询对象q，对于查询对象q中任意隶属于查询候选集Ca(q)中的 查询候选图像i′，若查询候选图像i′也在上一查询对象q′的查询结果集RS(q′)中，且查询候选 图像i′若满足下式(5)，则判定查询候选图像i′不是查询对象q的查询结果，即将查询候选图 像i′从查询候选集Ca(q)中剔除；

UB_p(h_q,h_q')+EMD(h_q',h_i')≥θ  (5)

式(5)中，UB_p表示基于EMD距离的上界函数，EMD(h_q′,h_i′)表示直方图h_q′和直方图h_i′之间的EMD距离，h_q表示查询对象q的直方图，h_q′表示查询对象q之前的上一查询对象q′ 的直方图，h_i′表示查询对象q的查询候选集Ca(q)中的查询候选图像i′的直方图，且该查询候 选图像i′是查询对象q之前的上一查询对象q′的查询结果，θ表示给定的相似性阈值。

本发明基于EMD距离的大规模图像数据相似性搜索方法具有下述优点：本发明基于 EMD距离的大规模图像数据相似性搜索方法，设计用于映射至一维实数键值空间Ω(Φ)的图 像数据映射函数f；启动作业MR1，估计Ω(Φ)中各个键值所对应的查询处理负载；启动作业 MR2，通过Map任务对Ω(Φ)进行切割，将不同切割区域对应的图像集的数据分片发送给 Reduce任务；基于f将各个Reduce任务接收的数据分片映射至Ω(Φ)中对应的键值，基于该 键值构建面向EMD距离的索引结构，基于该索引结构执行基于EMD距离的相似性搜索；将 所有基于EMD距离的相似性搜索的执行结果取并集输出，基于上述技术手段，使得本发明 基于EMD距离的大规模图像数据相似性搜索方法(1)在数据通信开销方面，本发明的方法 比传统方法Melody-Join大约节省1/m的数据通信开销，其中m是第二个MapReduce作业 MR2在数据映射阶段(Map阶段)所划分的数据块的个数(也等于Map任务的个数)。(2) 在负载均衡性方面，相比于传统方法Melody-Join，本发明的方法中各个规约(Map)任务较 均衡的查询处理运行时间，即可避免某个计算节点因分配的查询负载过重而拖后MapReduce 作业总体完成时间的情况。(3)在可扩展性方面，当数据集大小从20万增大至640万的过程 中，本发明的方法的执行时间比传统方法Melody-Join的执行时间呈更平稳的趋势上涨，说明 本方法对分析大规模图像数据集具有更好的可扩展性。综上所述，本发明基于EMD距离的 大规模图像数据相似性搜索方法具有网络传输数据量更低、计算负载分配更均衡，相似性搜 索效率更高、对大数据集分析处理可扩展性更好的优点。

附图说明

图1为现有技术的EMD距离和曼哈顿距离的鲁棒性比较示意图。

图2为现有分布式并行处理框架MapReduce的工作流程示意图。

图3为本发明实施例的基本实施流程示意图。

图4为本发明实施例步骤3)的基本实施流程示意图。

图5为本发明实施例步骤4)的基本实施流程示意图。

图6为本发明实施例步骤5)的基本实施流程示意图。

具体实施方式

如图3所示，本实施例基于EMD距离的大规模图像数据相似性搜索方法的步骤包括：

1)设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据映射函数f，图像数据 映射函数f包含图像数据和一维实数键值空间Ω(Φ)中键值之间的映射关系；

2)启动一个MapReduce作业MR1，通过MapReduce作业MR1基于查询图像集Q和待 检索图像集I估计一维实数键值空间Ω(Φ)中各个键值所对应的查询处理负载量；

3)启动一个MapReduce作业MR2，通过MapReduce作业MR2的Map任务基于步骤2) 估计得到的查询处理负载量对一维实数键值空间Ω(Φ)进行切割，分别将一维实数键值空间 Ω(Φ)不同切割区域所对应的查询图像集Q中的图像数据分片或待检索图像集I中的图像数据 分片发送给MapReduce作业MR2中的各个Reduce任务；

4)基于图像数据映射函数f将MapReduce作业MR2中各个Reduce任务所接收的图像 数据分片划分为查询图像集数据分片Q′和待检索图像集数据分片I′并分别映射至一维实数键 值空间Ω(Φ)，得到查询图像集数据分片Q′或待检索图像集数据分片I′在一维实数键值空间 Ω(Φ)中对应的键值；基于待检索图像集数据分片I′在一维实数键值空间Ω(Φ)中对应的键值 构建面向EMD距离的索引；

5)MapReduce作业MR2中各个Reduce任务分别基于面向EMD距离的索引执行查询图 像集数据分片Q′中的每个查询对象在待检索图像集数据分片I′上基于EMD距离的相似性搜 索；

6)MapReduce作业MR2中的每个Reduce任务将查询图像集数据分片Q′中每个查询对 象基于EMD距离的相似性搜索的执行结果取并集输出。

本实施例基于线性规划中的“原始-对偶”理论(Primal-Dual Theory)设计高效的图像数据 映射函数f，由于求解EMD距离就是求解一个线性规划问题，若把求解EMD距离的线性规 划问题看成是原始问题，则该问题有且仅有一个对偶线性规划问题，那么可以基于该对偶线 性规划问题设计f。本实施例中，步骤1)中设计用于将图像数据映射至一维实数键值空间Ω(Φ) 的图像数据映射函数f时，对于给定任意一组EMD距离对偶线性规划问题的可行解，记为 Φ＝{Ψ,Π}，其中Ψ＝{ψ₁,…,ψ_l}和Π＝{π₁,…,π_l}，其中l表示图像数据的直方图中的数据桶 个数，图像数据映射函数f通过式(1)计算图像数据集中每张图像X的直方图h_x＝{x₁,…,x_l} 的键值key(h_x,Φ)，从而将图像X映射至一维实数键值空间Ω(Φ)中；

f(X,Φ)＝key(h_x,Φ)＝∑_iψ_i·x_i  (1)

式(1)中，f(X,Φ)表示将图像X基于一组EMD距离对偶线性规划问题的可行解Φ映 射至一维实数键值空间Ω(Φ)的映射函数，key(h_x,Φ)表示图像X的直方图h_x＝{x₁,…,x_l}的键 值，表示将所有(ψ_i·x_i)的值求和且1≤i≤l，其中l表示图像数据的直方图中的数据 桶个数(维数)，ψ_i表示一组可行解Φ＝{Ψ,Π}中向量Ψ＝{ψ₁,…,ψ_l}的第i维的取值，x_i表 示图像X的直方图h_x＝{x₁,…,x_l}的第i维(或第i个数据桶)的取值。基于前述的线性规划中 的“原始-对偶”理论(Primal-Dual Theory)设计高效的图像数据映射函数f(具体参见式(1))， 能够快速将图像数据映射至一维实数键值空间(表示为Ω(Φ))，并保证EMD距离值相近的 直方图所对应的图像数据被映射至Ω(Φ)中的邻近键值区域内。

本实施例中，步骤1)中设计用于将图像数据映射至一维实数键值空间Ω(Φ)的图像数据 映射函数f时，图像数据映射函数f将EMD距离值相近的直方图所对应的图像数据映射至一 维实数键值空间Ω(Φ)中的临近键值区域内，与任意目标图像X相似的所有图像Y均满足式 (2)，其中目标图像X的直方图为h_x＝{x₁,…,x_l}，图像Y的直方图为h_y＝{y₁,…,y_l}；且相似 图像Y的直方图h_y的键值key(h_y,Φ)必落在式(3)所示的一维实数键值空间Ω(Φ)中的键值区 间内；

EMD(h_x,h_y)≤θ  (2)

式(2)中，h_x表示目标图像X的直方图，h_y表示与目标图像X相似的图像Y的直方图， EMD(h_x,h_y)表示直方图h_x和直方图h_y之间的EMD距离，θ表示给定的相似性阈值；

式(3)中，ψ_i表示表示一组可行解Φ＝{Ψ,Π}中向量Ψ＝{ψ₁,…,ψ_n}的第i维的取值，π_i表示表示一组可行解Φ＝{Ψ,Π}中向量Π＝{π₁,…,π_n}的第i维的取值，表示求 取所有(ψ_i+π_i)值中的最小值且1≤i≤l，其中l表示图像数据的直方图中的数据桶个数， key(h_x,Φ)表示直方图h_x基于可行解Φ计算得到的键值，Φ表示EMD距离对偶线型规划问题 的一组可行解，θ表示给定的相似性阈值，其中ckey(h_x,Φ)表示键值key(h_x,Φ)的对称键值， ckey(h_x,Φ)的表达式如式(4)所示；

式(4)中，表示将所有(π_j·x_j)的值求和且1≤j≤l，其中l表示图像数据的直 方图中的数据桶个数，π_j表示一组可行解Φ＝{Ψ,Π}中向量Π＝{π₁,…,π_n}的第j维的取值， x_j表示直方图h_x＝{x₁,…,x_l}的第j维的取值。

本实施例基于前述的一维实数键值空间Ω(Φ)维护了图像数据面向EMD距离的良好数据 局部性(Data Locality)。给定相似性阈值θ，与某图像X(直方图为h_x＝{x₁,…,x_n})相似的所 有图像Y(直方图为h_y＝{y₁,…,y_n})，即满足EMD(h_x,h_y)≤θ，其直方图的键值key(h_y,Φ)必 落在Ω(Φ)中式(3)所示的键值区间内。由于本实施例基于线性规划中的“原始-对偶”理论 (Primal-Dual Theory)设计高效的图像数据映射函数f，使得基于前述的一维实数键值空间 Ω(Φ)维护了图像数据面向EMD距离的良好数据局部性，进而MapReduce框架下数据映射阶 段中每个映射(Map)任务使用的基于线性规划“原始-对偶”理论设计的图像数据集划分策略， 使得每个规约(Reduce)任务获得的数据分片具有面向EMD距离的良好数据局部性。

本实施例中，步骤2)启动的MapReduce作业MR1包括m个Map任务和1个Reduce 任务。

MapReduce作业MR1的每一个Map任务执行下述步骤：

①对查询图像集Q的文件分块Q_i或待检索图像集I的文件分块I_i进行随机采样；

②、挑选出基数分别为|Q_i|·p和|I_i|·p的两个图像数据子集分发给MapReduce作业MR1 的Reduce任务，其中p表示预设的采样比率。

MapReduce作业MR1的Reduce任务执行下述步骤：

①、接收来自m个Map任务发送的图像数据，将所接收的图像数据根据其携带的标签(每 个查询图像集Q或待检索图像集I中的图像对象都附带一个标签标识其所属数据集)划分成 查询图像集Q的子集Q′待检索图像集I的子集I′

②、基于EMD距离相似性搜索算法(和步骤5中的基于EMD距离相似性搜索算法相同) 执行查询图像集Q的子集Q′中的每一个查询对象q_i在待检索图像集I的子集I′上的相似性检 索，并记录相似性检索的时间代价c_i作为其查询处理负载代价；

③、将每一个查询对象q_i的直方图h_qi基于给定用于数据划分的一组EMD距离对偶线性 规划问题的可行解Φ_partition计算得到键值和该查询对象q_i对应的查询负载代价 c_i组成二元组

④、执行完查询图像集子集Q的子集Q′中所有查询对象q_i的查询后，将得到的由所有二 元组组成的“键值-查询负载代价”二元组的序列 写入分布式文件系统(本实施例具体为Hadoop Distributed File  System，简称为HDFS)中。

本实施例中，步骤2)要解决的技术问题是估计一维实数键值空间Ω(Φ)内的查询负载分 布情况，作为基于EMD距离的相似性搜索算法的输入(详见步骤3)。以每个查询图像集Q 的子集Q′中的每一个查询对象q_i(q_i∈Q')为查询对象，在待检索图像集I的子集I'上进行 相似性检索，并记录相似性检索的时间代价c_i，作为其查询处理负载代价。本实施例中具体 启动一个MapReduce作业(记为MR₁)对查询图像集Q和待检索图像集I进行采样，并基于 采样得到的查询图像集Q的子集Q'和检索图像集I的子集I'估计一维 实数键值空间Ω(Φ)中各个实数值(后文亦称之为“键值”)所对应的查询处理负载代价。给定 一组EMD距离对偶线性规划的可行解用于数据划分，记为Φ_partition，若查询对象q_i的直方图h_qi基于Φ_partition计算得到的键值为则得到该键值和其查询负载代价组成的二元 组，记为执行完Q'中所有的查询，即得到一个“键值—查询负载代价” 二元组的序列，记为写入分布式文件系统HDFS中。

如图4所示，本实施例步骤3)启动的MapReduce作业MR2包括m个Map任务和n个 Reduce任务，其中每一个Map任务执行下述步骤：

3.1)从分布式文件系统HDFS中读取“键值-查询负载代价”二元组的序列

3.2)将序列中的每个二元组基于其键值 进行从小到大排序得到排序后的列表为List_sorted{<key(q_i,Φ_partition),c_i>}，同时 累加其中的查询负载代价c_i得到总查询负载代价C(即)；假设 MapReduce作业MR2中需要启动n个Reduce任务。为了实现Reduce任务间查询负载均衡， 则每个Reduce在处理Q'在I'上的相似性检索时，需要承担的查询负载量；

3.3)基于排序后的列表List_sorted{<key(q_i,Φ_partition),c_i>}找到可行解Φ_partition所对应的一维实 数键值空间Ω(Φ_partition)中的n-1个分位数{key_i,…,key_n-1}，使得排序后的列表 List_sorted{<key(q_i,Φ_partition),c_i>}中落在任意两个相邻分位数区间内的键值的累计查询负载值约 等于平均查询负载值c，其中平均查询负载值c为总查询负载C除以MapReduce作业MR2 中Reduce任务的数量n所得到的结果；

3.4)从分布式存储系统HDFS中读取查询图像集Q和待检索图像集I中的每一个数据分 块(File Split，分布式文件系统HDFS通常设置文件分块的大小为64M)；针对读取的每一个 数据分块包含的图像数据d，首先抽取图像数据d直方图h_d，并基于直方图h_d和EMD距离 对偶线性规划问题的可行解Φ_partition计算出图像数据d在可行解Φ_partition所对应的一维实数映 射空间Ω(Φ_partition)中的键值key(h_d,Φ_partition)；然后对图像数据d的键值key(h_d,Φ_partition)进行判 断，若key(h_d,Φ_partition)≤key₁，则将图像数据d发送给第1个Reduce任务；若 key_i≤key(h_d,Φ_partition)≤key_i+1，则将图像数据d发送给第i+1个Reduce任务；若 key_n-1≤key(h_d,Φ_partition)，则将图像数据d发送给第n个Reduce任务，其中key₁表示n-1个分 位数{key_i,…,key_n-1}中的第1个分位数，key_i表示n-1个分位数{key_i,…,key_n-1}中的第i个分位 数，key_i+1表示n-1个分位数{key_i,…,key_n-1}中的第i+1个分位数，key_n-1表示n-1个分位数 {key_i,…,key_n-1}中的第n-1个分位数。步骤3.3)得到的一维键值空间Ω_partition(Φ)内的n-1个 分位数{key_i,…,key_n-1}来决定每个图像数据d被发送给哪个Reduce任务，实现对图像数据集 的切割划分。

本实施例步骤4)在MapReduce作业MR2作业的每个Reduce任务所持有的待检索图像 数据集的数据分片构建面向EMD距离的索引，以加速相似性检索的效率。如图5所示，本 实施例步骤4)的详细步骤包括：

4.1)MapReduce作业MR2中各个Reduce任务将MapReduce作业MR2中各个Map任务 发送过来的图像数据分片根据各个图像数据携带的标签划分成查询图像集数据分片Q′和待检 索图像集数据分片I′，查询图像集数据分片Q′为查询图像集Q的子集，待检索图像集数据分 片I′为待检索图像集I的子集；

4.2)已知由L组EMD距离对偶线性规划问题的可行解构成的可行解集合，记为 S_Φ＝{Φ₁,…,Φ_L}，对待检索图像集数据分片I′中的每一个待检索图像对象i，其中1≤i≤L，基 于可行解集合S_Φ中每组可行解Φ_i计算待检索图像对象i的直方图h_i在Φ_i所对应的一维映射 空间Ω_i(Φ_i)内的键值key(h_i,Φ_i)，因此针对待检索图像集数据分片I′中的每个待检索图像对象 i而言，可得到相对于L组可行解的L个键值{key(h_i,Φ_i),…,key(h_i,Φ_L)}；由于待检索图像集 数据分片I'中的每张图像基于可行解Φ_i都存在唯一的键值，该键值即可作为B⁺树索引的键 值；

4.3)以待检索图像集数据分片I′中每张图像基于可行解集合S_Φ中同一组可行解Φ_i计算 得到的键值为B⁺树的键值构建一棵B⁺树索引结构，记为B⁺(Φ_i)。因为可行解集合S_Φ一共包 含L组可行解，因此共为待检索图像集数据分片I′构建了L棵B⁺树索引结构，记为 {B⁺(Φ₁),…,B⁺(Φ_L)}；对于查询图像集数据分片Q′中的任一查询对象q，基于所述L棵B⁺树 索引结构可以得到L组查询候选集{Ca(q,Φ₁),…,Ca(q,Φ_L)}，则所述L组查询候选集 {Ca(q,Φ₁),…,Ca(q,Φ_L)}的交集Ca(q,Φ₁)∩…∩Ca(q,Φ_L)即构成了查询对象q在待检索图像 集数据分片I′上的查询候选集Ca(q)。

根据式(1)可知，通过在索引结构B⁺(Φ_i)上执行基于键值的范围查询，即可快速过滤 得到I'中和查询对象q∈Q'相似(即满足EMD(q,i)≤θ)的所有的查询候选图像数据，即查 询候选集，记为Ca(Φ_i)。基于S_Φ中L组EMD距离对偶线性规划问题的可行解可以同理为待 检索图像数据分片I'构建出L棵B⁺树索引结构，即{B⁺(Φ₁),…,B⁺(Φ_L)}。因此对于任一查询 对象q∈Q'，基于这L棵B⁺树索引结构可以得到L组查询候选集，记为 {Ca(q,Φ₁),…,Ca(q,Φ_L)}。这些查询候选集的交集，即Ca(q,Φ₁)∩…∩Ca(q,Φ_L)即构成了查 询对象q的约简查询后选集Ca(q)。通过为待检索图像数据分片I'构建多棵B⁺树索引结构可 以有效约简查询候选集的大小，基于实验测试经验，本实施例步骤4.2)中已知由L组EMD 距离对偶线性规划问题的可行解构成的可行解集合中L的取值为3。

本实施例基于上述步骤4.1)～4.3)在MapReduce框架下数据规约阶段中每个规约 (Reduce)任务使用的面向EMD距离的图像数据索引，能够实现加速相似性检索的效率， 具有相似性检索的效率高的优点。

本实施例步骤5)是在MapReduce作业MR2的每个Reduce任务中基于步骤4)构建的B⁺树索引结构执行查询图像数据分片Q'中的每个查询对象在待检索图像数据分片I'上基于 EMD距离的相似性搜索。如图6所示，本实施例步骤5)通过MapReduce作业MR2中各个 的Reduce任务分别基于面向EMD距离的索引执行查询图像集数据分片Q′中的每个查询对象 在待检索图像集数据分片I′上基于EMD距离的相似性搜索的详细步骤包括：

5.1)将查询图像集数据分片Q′中的每个查询对象q按照其基于已知L组EMD距离对偶 线性规划问题的可行解集合S_Φ(S_Φ＝{Φ₁,…,Φ_L})中某组可行解Φ_i计算得到的一维键值进 行从小到大排序；

5.2)基于B⁺树索引结构{B⁺(Φ₁),…,B⁺(Φ_L)}，根据步骤5.1)中从小到大排序得到的顺序， 执行查询图像集数据分片Q′中的每个查询对象q在待检索图像集数据分片I′上基于EMD距 离的相似性搜索，为每个查询对象q检索出待检索图像集数据分片I′中与其EMD距离相近的 所有查询对象。

本实施例通过步骤5.1)～5.2)中MapReduce框架下数据规约阶段中每个规约(Reduce) 任务使用的基于索引过滤思想和Reduce任务所具有的面向EMD距离的良好数据局部性设计 的相似性搜索算法，能够确保相似性搜索的高效执行。

本实施例中，步骤5.2)的详细步骤包括：

5.2.1)基于B⁺树索引结构{B⁺(Φ₁),…,B⁺(Φ_L)}，并利用式(3)所示的索引过滤结论获取 每个查询对象q在待检索图像集数据分片I′上的查询候选集Ca(q)(详见步骤4.3)；并统计可 行解集合S_Φ＝{Φ₁,…,Φ_L}中每组EMD距离对偶线性规划问题的可行解Φ_i对待检索图像集数 据分片I′中无关图像数据的过滤性能；

5.2.2)在步骤5.1)从小到大排序得到的顺序的基础上，若每个查询对象q的上一查询对 象q′的查询结果集RS(q′)不为空，则基于三角不等式理论过滤每个查询对象q的查询候选集 Ca(q)，得到约简后的查询候选集Ca(q)₁；

5.2.3)基于EMD距离的下界函数LB_IM和基于EMD距离的上界函数UB_p进一步约简每 个查询对象q的查询候选集Ca(q)₁，得到约简后的查询候选集Ca(q)₂；

5.2.4)针对每个查询对象q的查询候选集Ca(q)₂中的每个图像数据i，计算图像数据i的 直方图h_i和对应的查询对象q的直方图h_q之间的EMD距离EMD(h_q',h_i)，若该EMD距离 EMD(h_q',h_i)小于给定的相似性阈值θ，则判定图像数据i为查询对象q的查询结果，将查询 结果二元组<i,EMD(h_q,h_i)>插入查询对象q的结果列表RS(q)，并写入分布式文件系统中； 同时，在计算计算图像数据i的直方图h_i和对应的查询对象q的直方图h_q之间的EMD距离 EMD(h_q',h_i)的过程中会顺带产生一组新的EMD距离对偶线性规划问题的可行解将可 行解插入新可行解候选列表

5.2.5)从新可行解候选集合中随机挑选一组新可行解Φ_new，根据统计得到的可行解 集合S_Φ＝{Φ₁,…,Φ_L}中每组可行解Φ_i对待检索图像集数据分片I′中无关图像数据的过滤性 能，用Φ_new替换掉可行解集合S_Φ＝{Φ₁,…,Φ_L}中过滤性能最差的那组可行解；

5.2.6)将各个查询对象q的查询结果集RS(q)作为查询对象q检索出的待检索图像集数据 分片I′中与其EMD距离相近的所有查询对象输出。

本实施例中，步骤5.2.2)中基于三角不等式理论过滤每个查询对象q的查询候选集Ca(q) 的详细步骤包括：针对每个查询对象q，对于查询对象q中任意隶属于查询候选集Ca(q)中的 查询候选图像i′，若查询候选图像i′也在上一查询对象q′的查询结果集RS(q′)中，且查询候选 图像i′若满足下式(5)，则判定查询候选图像i′不是查询对象q的查询结果，将查询候选图像 i′从查询候选集Ca(q)中剔除；

UB_p(h_q,h_q')+EMD(h_q',h_i')≥θ  (5)

式(5)中，UB_p表示基于EMD距离的上界函数，EMD(h_q',h_i')表示直方图h_q′和直方图 h_i′之间的EMD距离，h_q表示查询对象q的直方图，h_q′表示查询对象q之前的上一查询对象q′ 的直方图，h_i′表示查询对象q的查询候选集Ca(q)中的查询候选图像i′的直方图且该查询候选 图像i′是查询对象q之前的上一查询对象q′的查询结果，θ表示给定的相似性阈值。

本实施例中前文提及的符号及其对应的含义也可参见表2。

表2：本实施例前文提及的符号及其对应的含义表。

从互联网上爬取640万张图像作为图像数据集对本实施例基于EMD距离的大规模图像数据 相似性搜索方法进行性能评估。提取每张图像归一化后的灰度直方图用于表征该图像的内容， 即得到640万条灰度直方图数据。每条灰度直方图数据包含256个数据桶，对应灰度空间中 256个不同的灰度等级。为了测试并行算法的可扩展性，分别从图像数据集中生成包含20万、 40万、80万、160万、320万和640万的图像数据集。实验使用的集群由20台机器组成，一 台机器担任主控机(Master)，其余19台机器担任工作机(Slaver)。每台机器的配置是Intel(R) Core(TM)i3CPU(3.10GHz)、8G内存，运行内核为2.6.32的Linux操作系统。集群上部署的 MapReduce框架是Apache Hadoop 0.20.2版本。算法实现语言为C++，使用Hadoop针对C++ 语言开发的Hadoop Pipes接口实现算法逻辑。实验证明当相似性阈值设置合理时，在数据通 信开销方面，本实施例基于EMD距离的大规模图像数据相似性搜索方法比传统方法 Melody-Join大约节省1/m的数据通信开销。其中，m是算法在第二个MapReduce任务MR2 的数据映射阶段(Map阶段)所划分的数据块的个数(也等于Map任务的个数)。在负载均 衡性方面，相比于传统方法Melody-Join，本实施例基于EMD距离的大规模图像数据相似性 搜索方法中各个规约(Map)任务较均衡的查询处理运行时间，即可避免某个计算节点因分 配的查询负载过重而拖后MapReduce作业总体完成时间的情况。在可扩展性方面，当数据集 大小从20万增大至640万的过程中，本实施例基于EMD距离的大规模图像数据相似性搜索 方法的执行时间比传统方法Melody-Join的执行时间呈更平稳的趋势上涨，说明本方法对分析 大规模图像数据集具有更好的可扩展性。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡 属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通 技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本 发明的保护范围。