一种快速高效的近似重复图像匹配方法

摘要

本发明公开了一种快速高效的近似重复图像匹配方法。本方法为：1)提取训练图像库中每一图像的ORB特征并对每一图像的ORB特征进行非线性映射，构建该训练图像库的视觉词汇表；2)根据已构建的视觉词汇表，利用局部约束线性编码对训练图像库中每一图像非线性映射的ORB特征进行稀疏编码；3)提取待匹配图像的ORB特征并对其进行非线性映射，然后根据所建视觉词汇表对该待匹配图像非线性映射的ORB特征进行稀疏编码；4)计算待匹配图像的稀疏编码与该训练图像库中图像的稀疏编码相似度，若相似度超过设定阈值，则匹配成功，否则匹配失败。本发明降低了硬量化方法的重构误差，极大地提高了匹配的速度，可以用来实时匹配。

说明书

技术领域

本发明涉及计算机视觉领域，特别涉及一种近似图像匹配(Near-Duplicate Image  Match)方法。

背景技术

随着多媒体技术和现代信息处理技术的快速发展，特别是云计算、微信、微博等大规模 移动应用的推广，图像/视频数量正在呈爆炸式增长，这就不可避免的存在了大量的近似重复 图像，给信息存储和用户检索带来非常的不便。因此近似重复图像匹配吸引了一些学者的兴 趣。通过近似重复图像匹配的研究，一方面可以实现图像版权保护，其次在图像搜索引擎中， 用于过滤掉检索结果中的重复图像，从而提高用户的检索质量，另外，在基于内容的敏感信 息监控中，用于监控敏感图像的传播，因此，近似重复图像匹配有非常重要的研究意义和应 用价值。

通常近似重复图像是由某幅源图像通过某些变换得到的，一般可以产生近似重复图像的 变换包括平移、缩放、旋转、图像色调的变化、添加网址或商标、格式变化、分辨率变化等 等。近似重复图像匹配最常用的框架有以下两类：基于词包模型(Bag of Words)的方法和基 于索引的方法。词包模型的框架主要包括提取表示图像视觉的局部特征，对局部特征量化或 编码，然后通过编码融合形成最终的直方图向量来表示图像，最后度量图像直方图向量之间 的相似性。基于索引的框架比较流行的是将提取的图像的特征通过哈希编码处理成一个紧凑 的显著的哈希串，这样相近的特征点以很高的概率被处理成相似的哈希串，在搜索的过程中， 仅仅搜索那些相似的哈希串，从而降低了搜索的时间复杂度，但是最终的检测结果并不是很 令人满意，同时它还需要大量的存储空间。因此，近年来，研究工作基本上是采用词包模型 的框架来做近似重复图像匹配。

当前非常流行的词包模型框架不仅用在近似重复图像匹配上，还用在图像检索、图像分 类等其他应用上。由于SIFT特征具有旋转、尺度不变性等良好的特征，目前匹配方法中广泛 使用SIFT局部特征，并配合欧式距离的聚类算法进行图像匹配，但是目前的方法存在速度慢、 噪声大且准确度较差等问题。另一方面，词包模型的另外一个缺陷就是词量化的问题，一般 的技术都采用硬量化的方式，从而导致了一个局部特征点只能映射到词汇表中的一个单词上， 相似的局部特征有可能映射为不同的单词，因此造成了明显的重构误差。

发明内容

针对现有的词包模型技术中局部特征点提取速度慢、噪声大、单词硬量化、图像匹配速 度慢等技术问题，本发明的目的是提供一种快速高效的近似重复图像匹配方法。本发明综合 分析了各项技术的特点，首先提取图像的ORB局部特征，并对ORB特征进行非线性映射， 然后利用局部约束线性编码对非线性映射后的局部特征进行稀疏编码，以及对得到的稀疏编 码构建倒排索引，通过这一系列综合技术处理，使得方案在避免噪声大的同时，能够提高匹 配速度。

本发明的技术方案为：

一种快速高效的近似重复图像匹配方法，其步骤为：

1)提取训练图像库中每一图像的ORB特征并对每一图像的ORB特征进行非线性映射， 构建该训练图像库的视觉词汇表；

2)根据已构建的视觉词汇表，利用局部约束线性编码对训练图像库中每一图像非线性映 射的ORB特征进行稀疏编码；

3)提取待匹配图像的ORB特征并对其进行非线性映射，然后根据所建视觉词汇表对该待 匹配图像非线性映射的ORB特征进行稀疏编码；

4)计算待匹配图像的稀疏编码与该训练图像库中图像的稀疏编码相似度，若相似度超过 设定阈值，则匹配成功，否则匹配失败。

进一步的，所述构建所述视觉词汇表的方法为：

21)对每一图像的每一ORB特征进行非线性映射，即首先对ORB特征1范数归一化， 然后对ORB特征向量的每一维进行开平方根运算；

22)对训练图像库中所有图像经过非线性映射后的ORB特征利用聚类算法进行聚类，根 据聚类结果构建视觉词汇表。

进一步的，所述聚类算法中根据非线性映射后的ORB特征之间的巴氏距离进行聚类。

进一步的，利用公式对ORB特征进行所述非线性映射；其中，x_i为ORB特征向 量x的第i维分量，d为ORB特征向量的维数。

进一步的，利用下列公式对所述ORB特征进行稀疏编码：其中，条件1^Tc_i＝1保证了局部约束编码的平移不变性，Y＝[y₁,y₂,...,y_i,...,y_N]表示N个维数 为d的非线性映射后的ORB特征，⊙表示向量内元素两两相乘，d为ORB特征的维数，c_i∈R^M是对非线性映射后的第i个ORB特征y_i局部约束线性编码后的稀疏向量。

进一步的，采用最大值融合方法对图像进行编码融合，得到该图像的稀疏编码。

进一步的，根据图像的稀疏编码对该训练图像库建立倒排索引，得到一倒排索引文件， 步骤4)中利用该倒排索引文件，计算该待匹配图像与训练图像库中的所有图像的相似度。

进一步的，所述倒排索引文件的结构为：倒排索引的每一条记录表示一个单词，对应的 值为所包含该视觉单词的图像ID列表以及对应的TF-IDF值。

进一步的，计算该视觉单词对应的TF-IDF值的方法为：TF为该视觉单词在其所在图像稀 疏编码中的非零元素数量，IDF值为其中，|D|表示该训练图像库中图像的总数，|D_i| 表示的是包含视觉单词i的图像数目。

本发明的主要内容包括步骤：

步骤1：提取训练图像库中所有图像的局部特征并进行非线性映射，构建视觉词汇表；

步骤2：根据已经构建的视觉词汇表，利用局部约束线性编码对训练图像库非线性映射 后的局部特征进行稀疏编码；

步骤3：将训练图像库中稀疏编码表示的图像建立倒排索引；

步骤4：对待匹配图像，同样提取局部特征并进行非线性映射和稀疏编码，利用倒排索 引文件，计算待匹配图像与训练图像库中的所有图像的相似度并排序，若相似度超过一定阈 值，则匹配成功，否则匹配失败。

与现有技术相比，本发明具有以下优点：

1、本发明中利用的局部特征提取方法，具有计算速度快、对噪音不敏感、旋转不变性 等特点。

2、本发明中将局部特征进行非线性映射，映射后局部特征点之间的欧式距离就可以转 化为巴氏距离，从而大大提高了整个匹配阶段的性能，而且这种方法简单易实现，不需要额 外的存储空间，能够在线操作。

3、本发明利用局部约束线性编码对局部特征进行稀疏编码，使得一个局部特征可能会 有多个编码，克服了传统的硬量化只能映射到词汇表中一个单词导致的量化误差的问题，同 时局部约束线性编码使得相似的局部特征编码后也是相邻的，局部约束线性编码能达到局部 平滑稀疏性。

4、本发明使用倒排索引(inverted index)技术对样例库图像进行索引，以提高在线匹配 时的速度与精度。

附图说明

图1为本发明近似重复图像匹配的方法流程图。

图2为倒排索引文件结构图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图 1，对本发明进一步详细说明。

本发明的执行环境采用一台具有2.4G赫兹中央处理器和8G字节内存的奔腾4计算机并 用C++语言编制了快速高效的近似图像匹配的算法程序，还可以采用其他的执行环境，在此 不再赘述。

图1是本发明近似重复图像匹配的方法流程图，包括以下步骤：

步骤1：提取训练图像库中每一图像的局部特征并进行非线性映射，构建视觉词汇表；

其中步骤1中所述局部特征指的是ORB(ORiented Brief)特征，ORB特征具有旋转不 变性、对噪声不敏感等特性。而ORB特征最大的特点是速度快，ORB特征的提取速度是SIFT (Scale-invariant Feature Transform)特征的数十至一百倍，ORB特征描述了图像局部精准特 征，可以进行准确的匹配。

所述步骤1进一步包括以下步骤：

步骤11：对训练图像库中的每一幅图像提取局部特征ORB，表示为x，x∈R^d，R为一 个实数，d为ORB特征的维数，通常为32。提取ORB特征的过程可以参考文献“E.Rublee, V.Rabaud,K.Konolige,and G.Bradski,ORB：an efficient alternative to SIFT or SURF,2564-2571, ICCV2011”。

步骤12：对每一图像的每一局部特征ORB进行非线性映射，首先1范数归一化x，x_i为 ORB特征向量x的第i维分量，然后对ORB向量的每一维进行开平方根运算，具体计算方法 如下：

$\sqrt{\frac{x_i}{\underset{j=1}{\overset{d}{\Sigma }}{x}_j}}$

步骤13：对训练图像库中所有图像经过非线性映射后的ORB特征集利用聚类算法构建 视觉词汇表。比如使用现有技术中常用的k-means聚类方法进行聚类，得到M个聚类中心， 即为视觉词汇表B＝[b₁,b₂,...,b_M]∈R^d×M。由于采用了步骤12中的非线性映射，使得k-means 聚类算法中需要计算的欧式距离转化为巴士距离，而巴士距离对较大的值不敏感，从而大大 提升了匹配性能。

步骤2：基于已经构建的视觉词汇表，利用局部约束线性编码把非线性映射后的ORB特征 编码为稀疏向量。具体的局部约束线性编码方法如下式所示：

上式中，Y＝[y₁,y₂,...,y_N]∈R^d×N表示N个维数为d的非线性映射后的ORB特征，y_i为x_i开根号处理后的值，⊙表示向量内元素两两相乘，这里统一N的个数，取值为100，c_i∈R^M是对非线性映射后的特征y_i局部约束线性编码后的稀疏向量。条件1^Tc_i＝1保证了局部约束 编码的平移不变性，1表示元素都为1的向量。

这样，对于每一幅图像，就生成一个M×N维的矩阵，其每一列分别代表每个特征对应 的局部约束线性编码。采用最大值融合方法对该图像进行编码融合，其定义为：

p(i)＝max{c₁(i),c₂(i),...,c_N(i)}

p(i)是融合后的新向量p∈R^M的第i个元素。R^M表示的是M维的向量。

步骤3：将训练图像库中的图像建立倒排索引；局部约束线性编码后每一幅图像可以由 p表示，p中的每一维也可以当作是硬量化得到的视觉单词，p是稀疏的，大部分的值都为 0，若p(i)＝0,则表示不包含第i个单词，我们将p中的非零元素插入到倒排索引文件中。倒 排索引文件结构如图2所示，倒排索引的每一条记录即表示一个单词，对应的值为所包含该 视觉单词的图像ID列表以及对应的TF-IDF值，TF-IDF＝TF*IDF。

其中，TF表示的是词频即p中非零元素，IDF表示的是倒排文件频率，视觉词语i的 IDF值计算方法下：

${\mathrm{IDF}}_i=\log \frac{\left|D\right|}{\left|D_i\right|}$

其中，|D|表示的是训练图像库中图像的总数，|D_i|表示的是包含视觉单词i的图像数 目。

步骤4：对于待匹配的图像，同样提取局部特征ORB并进行非线性映射，利用倒排索引 文件，计算待匹配图像与训练图像库中的所有图像的相似度并排序，若相似度超过一定阈值， 则匹配成功，否则匹配失败。

所述步骤4进一步包括以下步骤：

步骤41：提取待匹配图像的ORB特征；

步骤42：对ORB特征按照步骤12的方法进行非线性映射；

步骤43：根据步骤1构建的视觉词汇表，将步骤42得到的特征进行非线性约束稀疏 编码；

步骤45：计算待匹配图像与训练库中每一图像的相似度，相似度的计算方法如下：

$s(y_q,y_d)=\frac{{y_q}^T·y_d}{\left|\right|y_q\left|\right|\left|\right|y_d\left|\right|}$

其中，y_q表示的是查询图像的稀疏编码，y_d表示的是训练库中图像的TF-IDF值

步骤S46：对相似度进行排序，若排在第一的图像的相似度

s(y_q,y_d)≥T

则匹配成功，否则匹配失败，其中T表示的是预先定义的阈值。

综上，本发明的特点在于提出了一种快速高效的重复图像匹配算法。本发明利用了ORB 局部特征提取算法，速度快，对噪音不敏感；通过对ORB进行非线性映射，使得在后续用聚 类算法构造词汇表中ORB局部特征之间的欧式距离转化为巴氏距离，而巴氏距离相对于欧式 距离能够避免较大的值的影响，性能更优；利用局部约束稀疏编码保持了特征的局部平滑性， 相似的特征经过局部约束稀疏编码后仍然相邻，降低了硬量化方法的重构误差；本发明通过 对训练图像的特征建立索引，极大地提高了匹配的速度，可以用来实时匹配。

以上所述，仅为本发明中的具体实施方式，但本发明的保护范围并不局限于此，任何熟 悉该技术的人在本发明所揭露的技术范围内，可理解想到的变换或替换，都应涵盖在本发明 的包含范围之内，因此，本发明的保护范围应该以权利要求书的保护范围为准。