第２７卷第３期　２０１２年５月　数　据　采　集　与　处　理　Ｊｏｕｒｎａｌ　ｏｆ　Ｄａｔａ　Ａｃｑｕｉｓｉｔｉｏｎ＆Ｐｒｏｃｅｓｓｉｎｇ　Ｖｏ１．２７　Ｎｏ．３　Ｍａｙ．２０１２　

文章编号：１００４—９０３７（２０１２）０３—０３６３—０５　

基于随机化映射和模式熵的近似重复图像检测　

蔺博宇　郭志刚　李弼程　高毫林　彭天强　

（解放军信息工程大学信息工程学院，郑州，４５０００２）　

摘要：针对传统方法检测效率低的问题，提出了一种基于随机化映射扣模式熵的近似重复图像检测方法。该方法　先利用精确欧式空间位置敏感哈希（Ｅｘａｃｔ　ｅｕｃｌｉｄｅａｎ　ｌｏｃａｌｉｔｙ　ｓｅｎｓｉｔｉｖｅ　ｈａｓｉｎｇ，Ｅ　ＬＳＨ）进行快速过滤，滤除大部　分非近似重复图像对，然后对于剩余的图像对，再采用尺度旋转不变模式熵（Ｓｃａｌｅ—ｒｏｔａｔｉｏｎ　ｉｎｖａｒｉａｎｔ　ｐａｔｔｅｒｎ　ｅｎ—　ｔｒｏｐｙ，ＳＲ—ＰＥ）进一步去除错误的匹配，从而实现近似重复图像检测。实验结果表明，新方法在不明显降低性能　的前提下大大加快了近似重复图像检测的速度，在检测性能与速度之间取得了较好的平衡。　关键词：图像检测；随机化映射；模式熵　中围分类号：ＴＰ３９１　文献标识码：Ａ　

Ｎｅａｒ－Ｄｕｐｌｉｃａｔｅ　Ｉｍａｇｅ　Ｄｅｔｅｃｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｒａｎｄｏｍ　Ｍａｐｐｉｎｇ　

ａｎｄ　Ｐａｔｔｅｒｎ　Ｅｎｔｒｏｐｙ　

Ｌｉｎ　Ｂｏｙｕ，Ｇｕｏ　Ｚｈｉｇａｎｇ，Ｌｉ　Ｂｉｃｈｅｎｇ，Ｇａｏ　Ｈａｏｌｉｎ，Ｐｅｎｇ　Ｔｉａｎｑｉａｎｇ　（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，ＰＬＡ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ，４５０００２，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｌｏｗ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄｓ，ａ　ｎｅｗ　ｎｅａｒ—ｄｕｐｌｉｃａｔｅ　ｉｍａｇｅ　ｄｅｔｅｃｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｒａｎｄｏｍ　ｍａｐｐｉｎｇ　ａｎｄ　ｐａｔｔｅｒｎ　ｅｎｔｒｏｐｙ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｆｉｒｓｔｌｙ，Ｅｘａｃｔ　ｅｕｃｌｉｄｅａｎ　ｌｏｃａｌｉｔｙ　ｓｅｎｓｉｔｉｖｅ　ｈａｓｈｉｎｇ（Ｅ　ＬＳＨ）ｉｓ　ｕｓｅｄ　ｔｏ　ｆｉｌｔｅｒ　ｍｏｓｔ　ｏｆ　ｔｈｅ　ｎｏｎ　ｎｅａｒ—ｄｕｐｌｉｃａｔｅ　ｉｍ—　ａｇｅ　ｐａｉｒｓ．Ｔｈｅｎ，ａ　ｐｏｏｌ　ｏｆ　ｖａｓｔｌｙ　ｒｅｄｕｃｅｄ　ｉｍａｇｅ　ｐａｉｒｓ　ｉｓ　ｆｕｒｔｈｅｒ　ｉｎｖｅｓｔｅｄ　ｂｙ　ｓｃａｌｅ—ｒｏｔａｔｉｏｎ　ｉｎ—　

ｖａｒｉａｎｔ　ｐａｔｔｅｒｎ　ｅｎｔｒｏｐｙ（ＳＲ—ＰＥ）ｆｏｒ　ｒｅｍｏｖｉｎｇ　ｔｈｅ　ｗｒｏｎｇ　ｍａｔｃｈｅｓ，ｔｈｕｓ　ｒｅａｌｉｚｉｎｇ　ｔｈｅ　ｎｅａｒ—ｄｕ—　ｐｌｉｃａｔｅ　ｉｍａｇｅ　ｄｅｔｅｃｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｎｏｖｅｌ　ｍｅｔｈｏｄ　ｓｉｇｎｉｆｉｃａｎｔｌｙ　ｓｐｅｅｄ　ｕｐ　ｔｈｅ　ｄｅｔｅｃｔｉｏｎ　ｗｉｔｈｏｕｔ　ａｐｐａｒｅｎｔ　ｄｅｇｒａｄａｔｉｏｎ　ｉｎ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎｄ　ａｃｈｉｅｖｅ　ａ　ｇｏｏｄ　ｂａｌａｎｃｅ　ｂｅｔｗｅｅｎ　

ｄｅｔｅｃｔｉｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎｄ　ｅｆｆｉｃｉｅｎｃｙ．　

Ｋｅｙ　ｗｏｒｄｓ：ｉｍａｇｅ　ｄｅｔｅｃｔｉｏｎ；ｒａｎｄｏｍ　ｍａｐｐｉｎｇ；ｐａｔｔｅｒｎ　ｅｎｔｒｏｐｙ（ＰＥ）　

引　言　

随着互联网技术的快速发展以及各种图像编　

辑软件功能的日趋强大，当前网络上涌现出海量的　

数字图像。其中，存在大量的近似重复图像。根据　

所做修改的不同，近似重复图像主要分为３类［１＿４］：　

（１）编辑操作（如滤波、裁剪以及改变对比度、饱和　

度和分辨率等）的影响；（２）物体运动、添加和遮挡　

引起的场景变化；（３）照相机设置及拍摄角度的变　

化。本文只针对第一种情况。图１给出了由于裁剪、　

旋转、加框、改变对比度和饱和度形成的近似重复　

基金项目：国家自然科学基金（６０８７２１４２）资助项目。　收稿日期：２０１１—０７—１８；修订日期：２０１１—１０—１８　图像。近似重复图像的出现，随之带来了版权侵犯　

和检索结果存在冗余等诸多问题。因此，迫切需要　

一种技术来解决上述问题，近似重复图像检测技术　

应运而生。　在近似重复图像检测任务中，Ｃｈａｎｇ等［２　提出　

了一种随机属性关系图匹配框架，属性关系图的每　

个顶点代表局部特征点，每条边表示局部特征点之　

间的空间关系，然后基于期望最大化（Ｅｘｐｅｃｔａｔｉｏｎ—　

ｍａｘｉｍｉｚａｔｉｏｎ，ＥＭ）学习算法计算图中的参数。但　

是，属性关系图匹配方法包含复杂的随机置信传播　

过程，因此，检测速度很慢。Ｚｈａｏ等［３　提出了一种　

尺度一旋转不变模式熵（Ｓｃａｌｅ—ｒｏｔａｔｉｏｎ　ｉｎｖａｒｉａｎｔ

　３６４　数　据　采　集　与　处　理　第２７卷　

－＿＿　

＿＿　

图１近似重复图像　

ｐａｔｔｅｒｎ　ｅｎｔｒｏｐｙ，ＳＲ—ＰＥ）算法，在点点对称（Ｏｎｅ—　

ｔｏ—ｏｎｅ　ｓｙｍｍｅｔｒｉｃ，ＯＯＳ）匹配的基础上进行ＳＲ—　

ＰＥ计算。然而，通常一幅图像含有成百上千个局　

部特征点，ｏＯｓ匹配十分耗时，即使采用了局部感　兴趣点索引结构（Ｌｏｃａｌ　ｉｎｔｅｒｅｓｔ　ｐｏｉｎｔ—ｉｎｄｅｘ　ｓｔｒｕｔ—　ｔｕｒｅ，ＬＩＰ—ＩＳ）来加快匹配的速度，速度提升的幅度　有限且伴随着检测性能的下降。Ｘｕ等Ｌ４　提出了一　

种空间对齐金字塔匹配（Ｓｐａｔｉａｌｌｙ　ａｌｉｇｎｅｄ　ｐｙｒａｍｉｄ　ｍａｔｃｈｉｎｇ，ＳＡＰＭ）算法，利用推土机距离（Ｅａｒｔｈ　ｍｏｖｅｒｓ　ｄｉｓｔａｎｃｅ，ＥＭＤ）度量图像块间的相似性。　

由于ＥＭＤ计算代价太高，造成ＳＡＰＭ算法效率低　

下。综上所述，现有方法都需要对每对图像进行复　杂的计算，而图像对的数量与数据集大小成平方关　

系，因此，普遍存在效率低的问题，不适用于实时在　线近似重复图像检测。　非近似重复图像对增长的速度远远大于近似　重复图像对增长的速度，非近似重复图像对所占比　例越来越大，将它们快速滤除就成为高效检测方法　

的重要组成部分。因此，本文提出了一种基于随机　化映射和模式熵的近似重复图像检测方法。该方法　先利用Ｅ　ＬＳＨ［５］进行快速过滤，滤除大部分非近似　

重复图像对，然后对于剩余的图像对，再采用ＳＲ—　ＰＥ进一步去除错误的匹配。　

１　Ｅ　ＬＳＨ原理　

Ｅ　ＬＳＨ是位置敏感哈希ＬＳＨ在欧式空间的一　种随机化实现方法，它的基本思想是，利用基于Ｐ一　

稳定分布的位置敏感函数对高维数据进行降维映　射，使得原始空间中距离很近的两个点经过映射操　作后依然很近。位置敏感函数以及ｐ一稳定分布的定　

义如下。　定义１给定点集　中任意点ｇ，＇，∈Ｓ，函数族　

：｛ｈ：　一　）是位置敏感的，如果函数　

Ｐ（　）一ＰｒＨＥｈ（ｇ）一ｈ（＇，）：１ｌ　ｇ一’，１Ｉ—ｔ３（１）　随ｔ严格递减，即点ｇ和ｖ碰撞概率随它们的距离递　减。　定义２分布Ｄ被称为户一稳定分布，如果存在　

户≥０，使得对于任意，ｚ个实数　一，　以及服从Ｄ　分布的独立同分布变量ｘ　一，　，随机变量　

∑Ｍ　ｘ　和（∑　吉ｘ同分布，这里ｘ是服从Ｄ　

分布的随机变量。　具体地，Ｅ。ＬＳＨ中使用的位置敏感哈希函数　

具有如下形式　

ｈａ，ｂ㈤一ｌ　ｊ　（２）　

式中：ｌ・Ｊ为向下取整操作；口为从满足户一稳定　

分布函数中随机抽样得到的ｄ维向量；ｂ为一个在　

Ｅ０，　］上均匀分布的随机变量。哈希函数ｈ　（＇，）：　

一ｚ把一个ｄ维向量＇，映射到整数集上。为拉大　

距离近的点映射后碰撞概率与距离远的点映射后　

碰撞概率之间的差距，Ｅ　ＬＳＨ将若干个位置敏感　

函数联合起来使用。定义函数族　

一｛ｇ：Ｓ—　Ｕ　）　（３）　

式中ｇ（１，）一（＾　（１，），…，ｈｋ（　）），ｈ　（・）∈　。式（３）　中ｋ决定了哈希冲突的概率，ｋ越大，哈希冲突的概　

率越小。同时，由于函数ｇ（１’）具有随机性，为了降低　

这种随机性，从函数族　中选取　个独立的函数　

ｇｌ，…＇ｇＬ　ｏ　对于每个数据点ｌ，∈　，经函数ｇ（１，）∈　降维　

映射后，可以得到一个ｋ维的向量ｃ：＝＝（ｃ　，Ｃ：，…，　

）。Ｅ。ＬＳＨ利用主哈希函数ｈ　和次哈希函数ｈ　对　

降维后向量进行哈希，建立哈希表存储数据点，ｈ　

和ｈ：的具体形式如下　

ｈｌ（　ｃ２，…，Ｃｋ）＝（（∑ｒ：Ｃ１）ｒｏｏｄ　ｐｒｉｍｅ）　一１　ｒｏｏｄ　ｔａｂｌｅｓｉｚｅ　（４）　

＾　ｈ２（ｃ１，ｃ　－．，　）＝（∑ｒ，Ｃｉ）ｍｏｄ　ｐｒｉｍｅ　（５）　＝１　式中：ｒ　和ｒ，为随机整数；ｔａｂｌｅｓｉｚｅ为哈希表的大　

小，其取值为数据点的总个数；ｐｒｉｍｅ为一个大的　

素数，取值５～２弛。　

２　基于随机化映射和模式熵的近似　

重复图像检测方法　

本文将Ｅ　ＬＳＨ和ＳＲ—ＰＥ应用于近似重复图像　检测，实现了一种基于随机化映射和模式熵的近似　重复图像检测方法，该方法的流程如图２所示。

　第３期　蔺博宇，等：基于随机化映射和模式熵的近似重复图像检测　３６５　

Ｅ　ＬＳＨ过滤　

图像　

图２近似重复图像检测流程　

２．１　Ｅ　ＬＳＨ过滤　

利用函数ｇ　（　＝１，…，Ｌ）将图像中的每个尺度　

不变特征变换（Ｓｃａｌｅ　ｉｎｖａｒｉａｎｔ　ｆｅａｔｕｒｅ　ｔｒａｎｓｆｏｒｍ，　ＳＩＦＴ）［　点哈希到　个桶中，对桶建立倒排文档，　

统计两幅图像共现桶（特征点哈希到同一个桶中）　

的数量。那么，若两幅图像共现桶的数量越多，则近　

似重复的程度越高。其详细过程如下：　

（１）ＳＩＦＴ点检测。对于图像数据库　一｛Ｉ　，Ｉ　，　

…，　一，　一　，　），检测出　中所有图像的ＳＩＦＴ特　

征点，得到包含ｍ个点的点集Ｓ＝｛Ｓ　，Ｓ：，…，　…，　

一　，　），其中每个点＆都是一个１２８维的ＳＩＦＴ特　

征向量。　

（２）Ｅ　ＬＳＨ降维映射。对，中的每个ＳＩＦＴ点ｓ，　

利用函数ｇ　（　＝１，…，Ｌ）对其进行降维映射，得到忌　维的向量ｇ　（　）。　

（３）Ｅ　ＬＳＨ桶哈希。按式（４，５）分别计算ＳＩＦＴ　点　的主哈希值ｈ　（ｇｌ（　））和次哈希值ｈ２（ｇ　（　））。将　

主、次哈希值都相同的点放人同一个桶中，生成哈　希表Ｔ　＝（Ｂ　，Ｂ　，…，Ｂ　，…，Ｂｊ；）＿１，Ｂ　｝（　＝１，　

…，Ｌ），Ｂ　表示哈希表丁　的第ｋ个桶，Ⅳ　为哈希表　丁　中包含桶的个数。　

（４）建立倒排文档。对所有的桶｛Ｂ｛”，Ｂ；＂，…　

Ｂ　，…，Ｂｊ　，…，Ｂ　一　，Ｂ　）建立倒排文档，其每　

一项由包含桶Ｂ　’的图像集组成。　（５）Ｅ　ＬＳＨ过滤。对于每对图像＜Ｉｉ，Ｉｔ＞，ｌ≤　

ｉ＜ｊ￣ｎ，统计共现桶的数量ｃｏＢｕｃｋｅｔＮｕｍｕ。由于　

哈希冲突的影响，可能造成并不相似的点也哈希到　同一个桶中。因此，引入阈值丁以舍弃没有足　够匹配点对的图像对，减少哈希冲突的影响，保留　ｃｏＢｕｃｋｅｔＮｕｍ　＞丁的图像对＜　¨Ｉｔ＞，１≤ｉ＜ｊ≤　

。通常，ｎ　《，ｚ。　

２．２　ＳＲ—ＰＥ检测　

对于剩余的图像对，先进行局部特征点匹配，　

然后再计算匹配模式。其详细步骤如下。　（１）采用ＬＩＰ—ＩＳ＋ＯＯＳ进行局部特征点匹配。　

（２）估计每两个匹配上点对的尺度Ｓ和角度　。　

设　和ｑ　为图像ｉ中的两个关键点，分别匹配到图　

像Ｊ中的户　和ｑ　。令长度ｚ　为Ｐ　到ｑ　的欧式距离，　

长度ｚ』亦然，则估计尺度Ｓ为ｚ　／　，角度０为　和　的　

夹角。　

（３）分别对ｓ和０进行ｍｅａｎ—ｓｈｉｆｔ聚类。　（４）确定每个点对的聚类隶属关系，即将每个　

点对分配到其出现次数最多的那一类。　

（５）设两种划分分别为Ｐ＝｛户ｚ，户。，…，户　）和　

Ｑ＝（ｑ　，口。，…，口　），其中，户　和ｑ　代表类，且ｍ≤ｎ，　

则模式熵ＰＥ。　定义为　

ＰＥ。　（Ｑ，Ｐ）＝－－）ｕＹ

…］Ｅｎｔｒｏｐｙ（ｑｉ　Ｐ）　（６）　

其中，　

胁娜　＝一　荟　×　

ｌｏｇ　（７）　

Ｍ一∑Ｉｑ　Ｉ一∑　（８）　ｑｉ６Ｏ　ＰｉＧＰ　式中：ｌ　ｑ　ｎ　ｆ为ｑ　和Ｐ　交集大小；　为匹配点对　

的总数量。实验中，判断ＰＥ　＜Ｏ．５的图像对即为近　

似重复图像对。　斓　口．１　像　Ｙ二　白近似重复图像对