相似图像识别检—基于图像签名(LSH)|江阴雨辰互联

2023年7月26日发(作者：)

相似图像识别检—基于图像签名（LSH）参考：⼈⼯智能，⼀种现代⽅法第 617页，且原始论⽂给出了完整的证明过程。在ANN⽅法中，LSH算⼀种可靠的紧邻算法。少量检索使⽤KNN、⼤量检索使⽤K-Dtree、海量检索使⽤LSH，超海量检索使⽤......⼀、引⾔多媒体识别是信息检索中难度较⾼且需求⽇益旺盛的⼀个问题。以图像为例，按照图像检索中使⽤的信息区分，图像可以分为两类：基于⽂本的图像检索和基于内容识别的图像检索（CBIR：Content Based Image Retrieval）。基于⽂本的图像检索完全不分析和利⽤图像本⾝的内容，其检索质量完全依赖于与图像关联的⽂字信息与图像内容的相关性，因此有必要引⼊基于内容的图像检索。本为主要讨论后者。在计算机视觉中，图像内容通常⽤图像特征进⾏描述。事实上，基于计算机视觉的图像检索也可以分为类似⽂本搜索引擎的三个步骤：提取特征、建索引build以及查询。本⽂也按照这三步来分别阐述。⼆、图像特征的提取⽬前互联⽹上的图像识别可以归结为两类问题，其⼀是“近重复检索”，主要是针对同⼀源图经过不同形变（包括光照、⽔印、缩放、局部缺失替换等）的检索，或是针对⼤体类似的物件进⾏识别，主要应⽤在版权保护、违禁识别、图⽚去重以及基本的相似检索等等；其⼆是“局部检索”，指的是两张图⽚中只要有部分物件重复，即可匹配到，⽐如我们可以想象，不同offer的模特不⼀样，但只要她们都跨了同⼀款LV包，就可以认为是相似图像，即实现真正意义上的图像检索。与此相对应的，图像特征也可以分成两类：全局特征与局部特征。⼤部分图像签名算法都是利⽤图像的全局特征来描述⼀幅图像的内容，例如，颜⾊直⽅图、⾊彩分布、形状或者边缘信息等等，⽤⼀个字符串或是数组来作为⼀幅图像的hash值。总的来说，全局特征是对图像内容⾼度抽象的概括，只回答了“图像是什么”，⽽⼤多数场合以⽤户的视⾓来看，更希望回答“图像有什么”。例如，⽤户在检索图像时，经常更加关⼼的是图像中的场景、物体或者特定的任务，单单⼀个全局特征⽆法区分些信息，因此引⼊了局部特征。其中最为著名的就是“基于尺度不变特征变换的图像检索”，Scale Invariant Feature Transform，也就是⼤名⿍⿍的SIFT。其基本思想是将图像打散为许多⾼维特征点，因此将互联⽹上的图⽚已视觉词库的形式加以保存。由于SIFT特征在描述向量时不受尺度变换和旋转的影响，对图像噪⾳、仿射变形、光照变化以及三维视⾓皆不敏感，因此具有极强的区分度，被⼴泛应⽤于物体识别、视频追踪、场景识别、图像检索等问题。为简单起见，本⽂主要讨论基于全局特征的图像相似检索技术，⽽局部特征可以在此基础上⾃⾏加以扩展。MPEG（即Moving Picture Experts Group运动图像专家⼩组）是个国际标准，即所谓ISO11172。准确说来， MPEG－7 并不是⼀种压缩编码⽅法，⽽是⼀个多媒体内容描述接⼝。继 MPEG－4 之后，要解决的⽭盾就是对⽇渐庞⼤的图像、声⾳信息的管理和迅速搜索。MPEG7就是针对这个⽭盾的解决⽅案。MPEG－7 ⼒求能够快速且有效地搜索出⽤户所需的不同类型的多媒体影像资料，⽐如在影像资料中搜索有长江三峡镜头的⽚段。预计这个⽅案于2001年初最终完成并公布。虽然没有实现代码，MPEG-7公布了⼀些图像描述接⼝，制定了⼀些诸如颜⾊分布、纹理、边缘、主体颜⾊的标准。这⾥主要介绍⼀下后边使⽤到的边缘直⽅图描述算法的原理。计算边缘直⽅图的主要步骤如下：⾸先将⼀个原始图像平均分割为4×4 共16 个⼦图像，之后的处理都是对每⼀个⼦图像局部边缘的直⽅图进⾏计算。每个局部的边缘直⽅图使⽤五个5边缘算⼦进⾏处理。最终得到80维向量，⽤于唯⼀标识这张图⽚。把每个⼦图像分割成为⼀系列图像块, 这些图像块的，⾯积随着图像⾯积的变化⽽变化。其中每个⼦图像的图像数⽬是固定的，可参考图⼀。计算并统计每个图像块的五种边缘类型( ⽔平、垂直、45°、135°和⽆⽅向) ，此为MPEG-7推荐的五种边缘检测算⼦，最终得到五个边缘⽅向的最⼤值。对得到的边缘直⽅图的值进⾏归⼀化和量化。考虑到⼈眼视觉的⾮均匀性，将归⼀化以后的80 个直⽅条的值进⾏⾮线性量化, 每个直⽅条使⽤固定长度的3位进⾏编码（即量化范围为0～8），总共⽤240个bit来表⽰边缘直⽅图。考虑两个边缘直⽅图描述符, 通过计算直⽅图间的欧⼏⾥德距离得到两个纹理图像的相似度，⼗分直观的，距离为0说明两幅图⽚的边缘纹理完全相同，距离越⼤说明相似度越⼩。三、图像特征索引的build与基于图像的query

在海量（百万以上）的图像特征中，寻找亚线性时间复杂度的匹配算法是⼗分有挑战的，特别的，由于是近似检索，我们需要的是数字上的⾮精确匹配，让我们看⼀下能想到的⽅法：

线性扫描：即对整个样本向量集合进⾏穷举式的顺序扫描，分别计算其与query图像的欧式距离，然后排序输出。准确度100%但过⾼的时间复杂度导致其实⽤性极差基于树结构的索引：⽐如sift作者推荐的KD-tree，SR-tree等。但由于“维度灾难（curse of dimensionality）”的存在，当向量维度⼤于10到20之后，基于树结构的索引需要扫描整个向量集合的绝⼤部分，加上算法本⾝的开销，其效果甚⾄要差于上述的蛮⼒查找。聚类：摒弃了树型结构建⽴索引之后，许多研究⼈员继⽽使⽤基于Kmeans聚类（层级聚类）的向量量化⽅法，其本质是将向量映射为标量，取得了⼀定的成功。但是，该⽅法的时间复杂度与图像的数量息息相关，当规模扩⼤时，biuld与query的时间开销仍然⽆法达到线上使⽤的地步。基于散列表的索引：与上类似，其本质也是将向量转化为标量进⾏匹配。散列表的主要好处有两点，⼀是query时间与数据结构的⼤⼩⽆关，基本上是O(1)的时间复杂度；⼆是增量build较其它⽅法更为⽅便。当然，直接将图像特征存放在散列表中，或者放在数据库的某⼀个字段中，只能进⾏精确匹配，只能返回⼀模⼀样的图⽚，对于图像检索来说，其价值点⼏乎为零；因此单纯的散列表技术还是⽆法满⾜我们的需求。常⽤的hash函数（crc、md5等），本质上都是基于密码学的脆弱哈希函数，其特点是输⼊只要有略微不同，产⽣的结果应该尽可能⼤的变化。本⽂采⽤的局部敏感哈希（Locality Sensitive Hashing， LSH）⽅法，在向量匹配⽅⾯与索引⽅⾯都要⽐传统的树结构和聚类算法快上好⼏个数量级，⽀持⾮精确查找，在我看来，是⽬前所知最适⽤于多媒体检索的算法。LSH主要是⽤来解决多维向量的K近邻（K Nearst Neighgor）问题，即查找某⼀多维向量间的K个最相似的向量。这是⼀种概率算法，其原理类似于bloom filter，存在⼀定的false positive，但换来的是检索效率的飞跃提升。

LSH的主要原理是：建⽴L个散列表来存放索引，每⼀个散列表Ti包含M个存放数据的桶，另外提供两套函数族Gi与Hi与之相关联。局部敏感哈希算法在概率意义上将相近的向量映射到相同的桶当中去，利⽤该特质可以对图像特征进⾏⾮精确匹配。为了最⼤限度的避免概率上的失误，采⽤多个hash函数映射到不同的hash表中去，分散误差，如图⼆所⽰。利⽤LSH为图像特征建⽴索引的具体流程如下：

将向量p标识转化为Hamming空间中的⼆进制向量（每⼀维仅为1或0），设某⼀维的向量值为x，最⼤值为c，则表⽰为连续的x个1紧跟c-x个0的c维⼆进制向量。因此该向量在原始空间的距离与其Hamming距离⼀致。将散列函数G作⽤在前⾯所产⽣的结果上，G的定义为，选取⽬标向量的K维⼆进制向量进⾏拼接。可以看出，⽬标向量之间相似度越⼤，其产⽣的hash值相等的概率越⼤。这是达到⾮精确检索的关键⼀环。基于2产⽣的结果，再⽤常规的哈希函数（md5）进⾏⼆次哈希将⼆次哈希得到的结果存放到⼀张哈希表的⼀个桶⾥，再使⽤下⼀个函数进⾏计算，周⽽复始。正如我们前⾯所说的那样，采⽤了多个hash函数来减少相似检索的误差。这样，相似的图像就被放到同⼀个桶⾥，⽽不同的图像则被放到另外的桶⾥了，如图三所⽰。query图像时，计算其特征值，并从前⾯建⽴的多个表中查询出结果，拼接在⼀起，如图四所⽰。针对上⼀步返回的近似图像，分别计算其欧式距离，排序，进⼀步去除极⼩概率上的false positive。局部敏感哈希将多维近似检索的时间复杂度进⼀步降低到亚线性级别，同时，合理选择哈希函数的个数与种类⼜可以使检索的准确率和召回率达到平衡。

四、实验结果

为验证MPEG-7边缘直⽅图配合局部敏感哈希算法的结果，本⽂使⽤了隐⽹项⽬中的违禁数据库进⾏测试。测试环境为公司的Dell PC，测试条件如下所⽰：样本库数量:14085

样本类别:国家安全类、⽂化传媒类、限售、药物器械

持久化index⽂件容量:3.07MB

从图⽚build时间:406ms

从索引⽂件build时间:15min

query时间:0ms

测试效果范例：

输⼊的待检索图⽚：

Query得到相似图⽚结果：

五、后续⼯作

1、sift特征的引⼊，局部图像检索的实现