随着图像和视频数据爆炸式的增长，视觉搜索在计算机视觉、多媒体领域引起了极大的关注。大规模图像或视频数据集具有3个典型的特征：图像数据量大、特征维度高以及要求响应时间短。大规模视觉搜索需要准确、高效地从大型图像或者视频数据集中检索出最相关的视觉内容。与此同时，由于视觉描述符通常具有数百甚至数千个维度，大多数视觉任务也面临维度灾难。

直接采用暴力搜索(brute-force search)策略难以满足系统实时性的要求。避免暴力搜索的一个典型方案是执行近似最近邻(approximate nearest neighbor，ANN)方法搜索，也即利用数据量增大后数据之间会形成簇状聚集分布的特性，通过对数据分析聚类的方法对数据库中的数据进行分类或编码，对于目标数据根据其数据特征预测其所属的数据类别，返回类别中的部分或全部作为检索结果。

哈希是一种被广泛研究的近似最近邻搜索的解决方案，其目的是将高维数据项转换为低维表示(Wang等，2018；费伦科等，2020)，或者是由一组位序列组成的短代码(又称为哈希码)。基于哈希方法的基本思想是构造一系列哈希函数，将每个视觉对象映射到一个二进制特征向量中，从而将视觉上相似的样本映射到相似的二进制码中。将高维实值特征向量编码为低维紧凑二进制码，可以显著加快相似度计算速度，节省搜索过程中的存储空间。局部敏感哈希(locality sensitive hashing，LSH)(Charikar，2002；Indyk和Motwani，1998)独立于数据，属于无监督哈希算法，提供了渐近理论特性，从而保证了性能(Wang等，2016)，被认为是高维空间上快速最近邻搜索的重要突破，是最常用的方法之一(Gionis等，1999)。

然而，基于LSH的方法有以下缺点。首先，哈希函数数目$K$如果设置得过小，会导致每一个哈希桶中容纳了过多数据项，从而增加查询响应时间; 而当$K$设置得过大时，会使得落入每个哈希桶中的数据项数目变小。其次，为了达到预期的搜索精度，LSH通常需要使用长哈希码，这降低了召回率。使用多个哈希表可以缓解这个问题，但是会显著增加存储成本和查询时间。另外，LSH的理论只适用于某些度量，如${l_p}\left({p \in \left({0, 2} \right]} \right)$和Jaccard(Wang等，2012)。最后，由于视觉语义空间与度量空间存在较大差异(毛晓蛟和杨育彬，2014)，也即语义鸿沟(Smeulders等，2000)，在这样的度量空间中，LSH可能不会获取良好的搜索性能。

不同于当前流行的学习型哈希方法，本文提出一种基于特征空间划分的无监督哈希检索算法(weighted semantic LSH，WSLSH)。该算法在对参考特征建立索引时，考虑参考特征与查询特征的距离关系，利用两层视觉词典对参考特征空间进行二次空间划分，在每个子空间里使用加权语义局部敏感哈希进行精确索引，从而形成层次化的索引结构。这可以在大规模检索过程中迅速地收敛搜索范围，然后再进行精确查询。接着，提出利用动态变长哈希码在一个哈希表里检索多个哈希桶，在保证检索性能的基础上减少哈希表数量，提高检索速度。此外，针对LSH的随机不稳定性，在LSH函数设计中加入反映参考特征空间语义的统计性数据，设计简单投影语义哈希函数，确保算法检索性能的稳定性。

现有的哈希方法主要分为不依赖数据的哈希算法(如LSH)和依赖数据的哈希算法。依赖数据的哈希算法主要基于数据应用各种统计学习、机器学习和深度学习来学习哈希函数，将样本映射成二进制码。目标是学习数据处理和特定于任务的哈希函数，例如通过与传统降维技术相结合，多采用由一组学习超平面构成的线性编码函数，包括谱哈希法(spectral hashing，SpH) (Weiss等，2008)、二元重构嵌入法(binary reconstruction embedding，BRE)(Kulis等，2009)、迭代量化法(iterative quantization，ITQ)(Gong等，2013)、K-means哈希法(K-means hashing，KMH)(He等，2013)、最小损失哈希法(minimal loss hashing，MLH)(Norouzi和Fleet，2011)和序列投影学习哈希法(sequence projection learning hashing，SPLH)(Wang等，2012)等。在关于深度学习和二值化编码的研究中，Xia等人(2014)和Lai等人(2015)利用卷积神经网络(convolutional neural networks，CNN)学习了一组哈希函数(Lin等，2016)。虽然基于学习的哈希方法一般比数据独立的哈希方法性能更好，但它需要更长的训练时间和更昂贵的计算成本。

LSH是通过随机映射和手工构造得到其函数族，属于数据独立的代表性哈希方法，已广泛应用于快速目标检测(Dean等，2013)、图像匹配(Chum和Matas，2010；Shan等，2014)等领域。一些学者基于上述开创性的工作，分别提出了一些有前景的工作，如满足各种距离度量的局部敏感特性的随机哈希函数(费伦科等，2020；Shan等，2014；Broder，1997；Broder等，1997；Dasgupta等，2011；Datar等，2004；Motwani等，2006)提供一个较小的相似性估计方差(O’Donnell等，2014；Li等，2007；Ji等，2012)，获得了更好的搜索效率和精度(Broder等，1997；Li等，2012)，发展更好的搜索方案(Wang等，2012；Panigrahy，2006)，更小的存储(Lyu等，2007；Li和König，2010)，或更快的哈希函数(Ji等，2012；Li等，2006, 2010)。关于LSH的详细综述可参考Wang等人(2014)的论文。LSH虽然得到了广泛的应用，但仍存在一些不足。为了提高查询效率，该算法需要大量的哈希表来构建索引结构，这导致了大量的内存消耗。即使是很小的数据集，创建索引结构也需要大量的内存。在内存有限的情况下，LSH查询性能会变得更差。在极端情况下，LSH会接近线性搜索的程度，这在一定程度上限制了LSH的应用。此外，尽管LSH的查询效率很高，但仍有进一步优化的空间。为了克服这些不足，机器学习和统计学界也对LSH的研究做出了贡献。其重点是开发LSH函数的变体，提供一定距离或相似性的无偏估计量、较小的方差(O’Donnell等，2014；Li等，2007；Ji等，2012)或存储需求较小的哈希码(Lyu等，2007；Li和König，2010)，或计算速度较快的哈希函数(Ji等，2012；Li等，2006, 2010；Wang等，2014)。然而，这些改进的方法并没有完全解决LSH的缺陷，其性能也没有显著提高(Wang等，2014)。本文提出的基于特征空间划分的加权语义局部敏感哈希算法(WSLSH)将参考数据空间划分为若干个子空间，不同子空间中的对象对给定的查询对象有不同的贡献。在子空间中对参考对象进行加权后，本文设计了加权语义局部敏感哈希(WSLSH)，使用动态变量随机语义哈希码构造LSH索引来加速检索。

假设A。给定一个查询特征$\mathit{\boldsymbol{q}}$，在特征空间中，与$\mathit{\boldsymbol{q}}$距离越近的参考特征被哈希索引次数越多，相反，距离越远的特征被索引次数就越少。那么，查询特征与越相似的参考特征发生哈希冲突的概率就越高，而与越不相似的参考特征发生哈希冲突的概率越低。

在现实中，特征之间的相似度往往利用距离来衡量，因此假设A是成立的，如果可以实现该假设A则可以解决基本LSH算法缺陷的问题。按照假设A，在特征空间$\mathit{\boldsymbol{S}}$中，对于哈希函数族: $\mathit{\boldsymbol{H = }}\left\{ {{h_i}:\mathit{\boldsymbol{S}} \to \mathit{\boldsymbol{U}}|i = 1, 2, \cdots, k} \right\}$，任意参考特征$\mathit{\boldsymbol{O}} \in \mathit{\boldsymbol{S}}$被索引后与查询特征$\mathit{\boldsymbol{q}}$发生冲突的概率为

$ {P_\mathit{\boldsymbol{H}}}\left({\mathit{\boldsymbol{q}}, \mathit{\boldsymbol{O}}} \right) = 1 - {\left({1 - p} \right)^L} $

(1)

式中，$p$为$\mathit{\boldsymbol{O}}$被索引一次后与$\mathit{\boldsymbol{q}}$发生冲突的概率，$L$是$\mathit{\boldsymbol{O}}$被索引的次数，与$\mathit{\boldsymbol{q}}$和$\mathit{\boldsymbol{O}}$之间的距离呈负相关关系，即$\mathit{\boldsymbol{q}}$和$\mathit{\boldsymbol{O}}$之间的距离越大，$L$越小。

本文通过对参考特征空间进行二次划分来判断参考特征与给定查询特征之间的距离关系，以此对参考特征被索引的次数进行加权，从而实现假设A，最终实现利用较少的哈希表进行索引就可以达到较好的效果。针对参考特征空间的二次划分，本文采用了量化速度快的两层视觉词典进行。

当前还没有通用的视觉词典，如何构造视觉词典是一个开放性的研究课题。Datar等人(2004)提出利用RB-Kmeans(repeated bisecting k-means)算法来构建包含根节点层和叶节点层的两层视觉词典，如图 1所示。要建立规模为$\mathit{\boldsymbol{N}}$的视觉词典，首先要确定根节点个数$\mathit{\boldsymbol{M}}$和训练集的规模。训练集规模是视觉词典大小的20~80倍为最佳。该两层词典的构建过程如下: 1)利用RB-Kmeans算法对训练集进行聚类，得到$m$个类簇${\mathit{\boldsymbol{A}}_1}, {\mathit{\boldsymbol{A}}_2}, \cdots, {\mathit{\boldsymbol{A}}_i}, \cdots, {\mathit{\boldsymbol{A}}_m}$。然后计算每个类簇的中心点(如式(2)所示)，每个中心点作为两层视觉词典中根节点层的一个根节点。2)再次利用RB-Kmeans算法对每个类簇${\mathit{\boldsymbol{A}}_i}$进行二次聚类得到$n/m$个子类，$ m$为根节点个数，$n$为叶节点个数。利用式(2)计算每个子类的中心点作为叶节点层的叶节点，${\mathit{\boldsymbol{F}}_{ij}}$表示在第$i$个类簇中的第$j$个参考特征。从而得到视觉词典的第2层。

$ {\mathit{\boldsymbol{R}}_i} = \frac{{\bf{1}}}{{\left| {{\mathit{\boldsymbol{A}}_j}} \right|}} \times \sum\limits_{j = 1}^{\left| {{\mathit{\boldsymbol{A}}_i}} \right|} {{\mathit{\boldsymbol{F}}_{ij}}} $

(2)

对于大规模特征库和大型的视觉词典来说，要将特征量化到视觉单词上是一个十分耗时的过程。为了加速该过程而不影响量化的准确性，多层词典是一个很好的解决方法。本文采用了Zhao等人(2010)提到的两层视觉词典。两层视觉词典中，根节点层作为索引，而叶节点层则作为视觉单词层(即每个叶节点就是一个视觉单词)。通过两层视觉词典，待量化特征不需要与所有的视觉单词(叶节点)进行比较，只需先与所有的根节点比较以确定最近邻的根节点，然后再与归属于该根节点的所有视觉单词比较以最终确定量化到最近邻的视觉单词。根节点层作为索引层，其节点数量(设为$m$)远远少于叶节点的数量(设为$n$)。正常情况下，$\frac{1}{{15}} < \frac{m}{n} < \frac{1}{5}$，$m$越小，特征量化的速度越快，但是量化错误的风险就越高。所介绍的两层视觉词典与传统的单层视觉词典在性能上是相当的，换句话说，两层结构没有很大地损坏词典的性能，但是大大改善了其特征量化效率，因此很适合应用于大量的视频特征索引中。

1) 硬划分。利用两层视觉词典将所有参考特征量化到最近邻的视觉单词上，每个视觉单词对应所有参考特征中的一个子集合。因此，参考特征空间被无重叠地划分为${\mathit{\boldsymbol{v}}_1}, {\mathit{\boldsymbol{v}}_2}, \cdots, {\mathit{\boldsymbol{v}}_n}$, 共$n$个子空间，每个子空间内的参考特征之间较于其他子空间更为相似，如图 2的蜂巢状空间划分。本次利用视觉单词的空间划分是硬划分。对于给定查询特征$\mathit{\boldsymbol{q}}$，通过计算$\mathit{\boldsymbol{q}}$与每个视觉单词的距离从而将其量化到最近的子空间，那么则认为该子空间所有参考特征都与$\mathit{\boldsymbol{q}}$相近，其他子空间的参考特征则远离$\mathit{\boldsymbol{q}}$，但无法衡量参考特征与$\mathit{\boldsymbol{q}}$的相近程度。

2) 软划分。对视觉词典的两层建立多对多的映射关系，如图 3所示，每个视觉单词(叶节点)同时归属于最近邻的$\theta + 1$个根节点(本来所属的根节点和另外最近邻的$ \theta $个根节点)。根据该映射关系，将每个根节点拥有的视觉单词与经过硬划分对应的子空间合并。因此参考特征空间被重新划分为有重叠的$m$个子空间${\mathit{\boldsymbol{R}}_1}, {\mathit{\boldsymbol{R}}_2}, \cdots, {\mathit{\boldsymbol{R}}_m}$，如图 2的椭圆划分。给定查询特征$\mathit{\boldsymbol{q}}$，首先根据硬划分确定量化子空间${\mathit{\boldsymbol{v}}_i}$，然后利用视觉词典两层映射关系确定子空间${\mathit{\boldsymbol{R}}_j}, {\mathit{\boldsymbol{R}}_{j + 1}}, \cdots, {\mathit{\boldsymbol{R}}_{j + \theta }}$。这种情况下，这$\theta + 1$个子空间的并集: $\mathit{\boldsymbol{UR}} = {\mathit{\boldsymbol{R}}_j} \cup {\mathit{\boldsymbol{R}}_{j + 1}} \cup \cdots \cup {\mathit{\boldsymbol{R}}_{j + \theta }}$里的参考特征与查询特征集有不同程度的近邻关系，$\mathit{\boldsymbol{UR}}$以外的参考特征则远离查询特征。在$\mathit{\boldsymbol{UR}}$中，在$\theta + 1$个子空间的交集$\mathit{\boldsymbol{IR}} = {\mathit{\boldsymbol{R}}_j} \cap {\mathit{\boldsymbol{R}}_{j + 1}} \cap \cdots \cap {\mathit{\boldsymbol{R}}_{j + \theta }}$中的参考特征与$\mathit{\boldsymbol{q}}$最近邻，其次是任意$ \theta $个子空间的交集中的参考特征，如此类推。

经过利用两层视觉词典对参考特征空间的二次划分，给定一个查询特征，可以确定哪些参考特征与查询特征具有近邻关系以及近邻程度，因此可以确定它们被索引次数的权值。这里$L\left({\theta + 1} \right)$个哈希表用来对每个子空间${\mathit{\boldsymbol{R}}_j}$中的参考特征进行哈希索引，$\mathit{\boldsymbol{UR}}$所覆盖的范围则作为哈希检索的范围。利用该方法，在检索范围内，参考特征可能被$\left({\theta + 1, \theta, \cdots, 1} \right)$个子空间$\mathit{\boldsymbol{R}}$覆盖。将被覆盖次数作为每个参考特征的权值，那么被索引的次数可能为$\frac{L}{{\theta + 1}} \times \left({\theta + 1} \right), \frac{L}{{\theta + 1}} \times \theta, \cdots, \frac{L}{{\theta + 1}} \times 1$。至此，通过这种空间划分对被索引次数进行加权的方法实现了假设A。

回顾基本LSH的定义和理论框架，所有特征无区分地被索引$L$次，并通过增加参数$k$和$L$的值以增加高冲突概率和低冲突概率的差距，但是效果不够理想，且需要消耗大量的索引空间，同时降低了检索速度。而本文提出的加权索引算法考虑参考特征与查询特征之间的近邻关系，通过利用视觉词典进行空间划分的方法确定参考特征与查询特征的近邻程度并对参考特征进行加权，使得越近邻的参考特征获得越大的权值，被索引更多次。最终达到以较少的哈希表和较短的哈希码就能有效地加大高冲突概率与低冲突概率的差距，提高索引精度。

在LSH中，每个哈希表的哈希函数是由$k$个原子哈希函数串联而成，$k$值越大，经过串联哈希函数发生冲突的特征的相似度就越高。在基本LSH算法框架中，为了确保检索精度，传统LSH通常使用长哈希码($k$值较大)，因此需要查询多个哈希表来提高查全率，但这是以增加索引空间和检索时间为代价的。在现实的近似相似检索过程中，检索任务往往只需要返回符合一定条件，如与查询特征距离小于某个阈值或者前$m$个近邻。因此针对该问题，本文提出利用动态变长哈希码在同一个哈希表里检索多个哈希桶，从而在保证查全率的同时，减少哈希表个数和检索时间。

动态变长哈希码的主要思想为：长度为$k$的串联哈希函数$g\left(\mathit{\boldsymbol{q}} \right) = \left({{h_1}\left(\mathit{\boldsymbol{q}} \right), \cdots, {\mathit{h}_k}\left(\mathit{\boldsymbol{q}} \right)} \right)$，其哈希码形式为: $\mathit{\boldsymbol{Hkey}} = ke{y_1}, \cdots, ke{y_k}$。从$g$中随机抽取不定数量的原子哈希函数来构成新的串联函数，那么利用新的串联哈希函数计算得到的哈希码就是原哈希码的一个子集。由于每个原子哈希函数都是独立的，所以无需重新构造新串联函数来产生哈希码子集，只需要从原哈希码中随机抽取不定数量原子哈希码来构成新的哈希码。利用这种方法为查询特征和对应哈希表的每个哈希桶都构造一组不等长的哈希码，并且利用查询特征的这组不等长哈希码进行多次哈希桶匹配，进而实现在一个哈希表里检索多个哈希桶的目的。

利用$g$计算给定查询特征$\mathit{\boldsymbol{q}}$的哈希码得$\mathit{\boldsymbol{Hkey}}_k^q = g\left(\mathit{\boldsymbol{q}} \right) = key_1^q, \cdots, key_k^q$。利用算法1获取$\mathit{\boldsymbol{q}}$的一组变长哈希码。本文利用哈希算法查找符合$m - {\rm{NN}}$条件的参考特征作为相似特征返回，即

$ \begin{array}{l} \;\;\;\;\;\;\;\;m - {\rm{NN = }}\\ \left\{ {\frac{{dist\left({{\mathit{\boldsymbol{F}}_q}, {\mathit{\boldsymbol{F}}_r}} \right) < \varepsilon }}{{{\mathit{\boldsymbol{F}}_r}是{\mathit{\boldsymbol{F}}_q}的前m个最近邻的参考特征}}} \right\} \end{array} $

(3)

算法1产生变长哈希码

输入：原哈希码$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_k}$，重复次数$n$，最大舍弃数量$m$。

输出：变长哈希码集合${\mathit{\boldsymbol{C}}_{HkeySet}}$，被选原子哈希码索引: $\mathit{\boldsymbol{Inde}}{\mathit{\boldsymbol{x}}_{\mathit{Set}}}$。

1) FOR ${l_1} = 1:m$;

2) FOR ${l_2} = 1:\mathit{n}$;

3) 从$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_k}$中随机选择${n_f} = k - {l_1}$个原子哈希码组成一个长度为${n_f}$的哈希码$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_{{\mathit{\boldsymbol{n}}_f}}}$，原子哈希码下标为: $\mathit{\boldsymbol{Index}} = \left\{ {{i_1}, \cdots, {i_i}, \cdots, {i_{{\mathit{\boldsymbol{n}}_f}}}} \right\}$，其中1≤${i_i}$≤$k$;

4) 将$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_{{\mathit{\boldsymbol{n}}_f}}}$加入${\mathit{\boldsymbol{C}}_{HkeySet}}$，将$\mathit{\boldsymbol{Index}}$加入$\mathit{\boldsymbol{Inde}}{\mathit{\boldsymbol{x}}_{\mathit{Set}}}$;

5) END;

6) END。

在本文中，首先利用$\mathit{\boldsymbol{Hkey}}_k^q$检索符合$m - {\rm{NN}}$条件的参考特征，如果足够$m$个参考特征符合条件则返回，否则利用候选哈希码集合中的变长哈希码继续检索，直到找够$m$个符合$m - {\rm{NN}}$条件的参考特征，或者所有变长哈希码都被使用一遍。其检索流程如算法2所示。

算法2  利用变长哈希码进行动态检索

输入：查询特征原哈希码$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_q}$和变长哈希码集合${\mathit{\boldsymbol{C}}_{HkeySet}}$，被选择原子哈希码索引$\mathit{\boldsymbol{Inde}}{\mathit{\boldsymbol{x}}_{\mathit{Set}}}$，返回近邻个数$m$。

输出：候选参考特征集合${\mathit{\boldsymbol{C}}_{RojectSet}}$。

1) 利用$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_q}$与所有未被标志的哈希桶的哈希码进行匹配，选出匹配哈希桶。遍历该哈希桶中所有参考特征，将符合条件的参考特征加入${\mathit{\boldsymbol{C}}_{RojectSet}}$，并标志该哈希桶；

2) 计算${\mathit{\boldsymbol{C}}_{RojectSet}}$中参考特征的数量，如果达到$m$，则算法结束返回；

3) 判断${\mathit{\boldsymbol{C}}_{HkeySet}}$是否为空，如果为空，则算法结束，返回；

4) 从${\mathit{\boldsymbol{C}}_{HkeySet}}$中取出最长的哈希码作为新的$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}_q}$，并从$\mathit{\boldsymbol{Inde}}{\mathit{\boldsymbol{x}}_{\mathit{Set}}}$中取出对应的被选择原子哈希码索引，然后使用相应长度的哈希码检索所有未被标志的哈希桶；

5) 转到步骤1)。

较长的哈希码确保了散列在同一个哈希桶中的特征都是高度相似的，而且哈希桶中的特征数量较少，从而减少在哈希桶里进行穷举匹配的时间。因此本文在建立哈希索引的时候使用较长的哈希码。利用变长哈希码检索是一个动态过程。为了防止遗漏本来相似的特征，根据实际需求通过选取部分原子哈希函数进行索引，缩短哈希码长度，逐渐降低索引精度，以扩大检索范围，在确保检索的查全率的同时，又可以避免检索更多的哈希表。

现在比较流行的局部敏感哈希函数的设计方法有Min-Hashing、随机投影(Datar等，2004)和L-p范数等方法。这里设计一种简单语义投影局部敏感哈希函数，有3个参数: 1)投影维数$K$ (用户指定); 2) ${\mathit{\boldsymbol{S}}_d}$，随机选择的特征维度索引，是一个$K$维向量; 3) $\mathit{\boldsymbol{T}}$，所选择维度的对应量化阈值，是一个$K$维向量。其构造方法如算法3。

算法3  简单语义投影LSH函数设计

输入：投影维数$ k$，参考数据集${\mathit{\boldsymbol{R}}_{Fset}}$。

输出：包括${\mathit{\boldsymbol{S}}_d}$，$\mathit{\boldsymbol{T}}$两个域的结构体。

1) 统计${\mathit{\boldsymbol{R}}_{Fset}}$中所有数据对象每一维的中值，得到参考特征空间统计中值向量${\mathit{\boldsymbol{M}}_{1 \times d}}$，其中$d$为数据对象的维度；

2) 随机选择参与哈希映射的维度，得到${\mathit{\boldsymbol{S}}_d}\mathit{\boldsymbol{ = }}\left\{ {{d_1}, \cdots, {d_i}, \cdots, {d_k}} \right\}$为${1 \sim d}$之间的整数，表示维度索引；

3) 产生投影基向量$\mathit{\boldsymbol{T}} = \mathit{\boldsymbol{M}}\left({{\mathit{\boldsymbol{S}}_d}} \right) = \left\{ {{t_1}, \cdots, {t_i}, \cdots, {t_k}} \right\}$。

利用该函数计算给定数据对象$\mathit{\boldsymbol{x}}$的语义投影$\mathit{\boldsymbol{Hke}}{\mathit{\boldsymbol{y}}^x} = \left[ {\mathit{\boldsymbol{x}}\left({{\mathit{\boldsymbol{S}}_d}} \right) \ge \mathit{\boldsymbol{T}}} \right]$，即$\mathit{\boldsymbol{x}}$中被选择的维度与$\mathit{\boldsymbol{T}}$中相应维度的阈值相比较，大于等于阈值的维度被置为1，小于阈值的维度则被置为0。因此，得到的哈希码为$k$位的0—1串。然后转成128和129序列，并将该序列每个值乘以相应素数并将相加的和作为数据对象$\mathit{\boldsymbol{x}}$的哈希地址。

目前大部分LSH函数的构造都具有随机性，主要体现在：一方面，参与映射的特征维度是随机选择的; 另一方面，特征的量化阈值是随机产生的。因为这些随机性使得经过哈希函数映射效果也具有随机性，从而导致最后的检索性能不稳定。特征维度选择的随机性可以通过增加维度的维数(哈希码长度)和多次重复(哈希函数个数)来消除其随机性。但是由于特征向量每维的值的范围较大，无法通过该方法消除特征量化阈值的随机性，因此本文提出利用参考特征集中的统计值作为量化阈值。

根据Dasgupta等人(2011)，Zhao等人(2010)的结论表明，利用参考特征集中具有统计性的值作为量化阈值可以消除随机不稳定性。由于统计值一定程度上反映了该特征集的语义，因此取得了良好量化效果。据此，本文统计整个参考特征空间的所有特征每个维度的中值作为投影基向量$\mathit{\boldsymbol{T}}$。

由于本方法是面向图像视频的视觉特征检索任务，所以从视觉特征评估网站(http://www.robots.ox.ac.uk/~vgg/research/affine/)采集图像，构造数据集，同时也采用图像检索的经典数据集Holidays与Oxford5k来进行评测。

1) DataSetA。测试数据为从视觉特征评估网站下载的6组图像。在每一组图像中，1幅图像为源图像，其余5幅图像为该源图像的近似拷贝(不同视角、缩放旋转、模糊化、改变光照条件等)。从每幅图像中随机提取10 000个20×20的小块，将其转成400维的特征向量，则一共得到360 000个400维的特征向量。这36万个向量组成了数据集DataSetA。

2) DataSetB。对从视觉特征评估网站下载的6组图像进行SIFT(scale-invariant feature transform)特征提取，得到6个子集，共有90 944个SIFT特征，每个子集的SIFT特征数量如表 1所示。

3) Holidays。Holidays数据集包含了非常多的场景类型(自然、人造等)，并且图像分辨率很高。数据集包含500个图像组，每个图像组表示一个不同的场景或对象。每个组的第1幅图像是查询图像，正确的检索结果是该组的其他图像。Holidays数据集包含1 491幅不同位置和对象的图像，其中500幅用做查询。

4) Oxford5k。牛津建筑数据集是通过搜索Flickr中的牛津地标收集而来。Oxford5k数据集由5 063幅建筑图像和55幅查询图像组成，这些图像对应于牛津11座不同的建筑。

在本实验中，在DataSetA中随机抽取特征向量作为查询特征，然后利用本文提出的WSLSH算法进行近似相似检索，并返回前10个最近邻参考特征10-NN(不包括查询本身)，然后将查询特征和返回的10个近邻参考特征转成20×20像素的灰度图像块更直观地展示出来。通过比较这些10-NN与查询特征的相似度来评价检索算法的可行性。

图 4中给出了6个查询样例。其中，第1行(第4行)为查询样本，第2，3行(第5, 6行)为利用WSLSH进行近似检索返回的10个近邻参考样本。从返回的10-NN中，可以看到WSLSH算法从36万个参考特征集中返回的10个相似近邻在灰度值和灰度分布上都与查询具有很高的相似性，因此本文提出的WSLSH算法对近似相似性检索是可行的。

WSLSH、LSH和E2LSH(exact Euclidean locality sensitve hashing)(Datar等，2004)算法都是数据独立型的随机映射哈希算法，本文在时间性能方面对3个算法进行了比较。实验在数据集DataSetB上进行，DataSetB中保存了6组图像的SIFT特征，本文利用源图像的SIFT特征与剩余的拷贝图像的SIFT特征进行匹配。即使用源图像的SIFT特征作为查询特征Q在DataSetB中进行近似相似查询，并返回5-NN(因为每个查询特征最多有5个匹配参考特征)。在相同参数$k$ (串联哈希函数的个数)和$L$ (哈希表个数)下，LSH，E2LSH和WSLSH三种算法的检索的时间性能如图 5所示。

由图 5可以看出，在每一个子集中WSLSH算法的平均检索时间最少，E2LSH次之，检索时间最长的是LSH。这表明WSLSH相比其他的随机映射哈希算法，搜索速度更快。为了验证数据集规模对检索时间性能的影响，本文从DataSetA中随机选择10 K、60 K、120 K、180 K、240 K、300 K和360 K个参考特征分别组成7个数据集。WSLSH、LSH和E2LSH算法分别在这7个不同规模的数据集上进行检索时间测试，结果如图 6所示。

由图 6可以看出，随着数据集规模的增大，LSH和E2LSH算法的检索时间快速增加，而WSLSH算法的检索时间增长较缓慢。这是因为随着数据集规模增大，用更大的视觉词典进行空间划分之后，每次检索时，WSLSH算法对所涉及的参考特征子集的规模变化不是很敏感，因此检索时间也不会变化太大，因而体现了面向大规模数据集的WSLSH的检索优势。

本次实验在DataSetB、Holidays、Oxford5k数据集上比较了一些具有代表性的无监督哈希算法的检索性能，采用检索返回的前1 000幅图像的平均精确度均值(mean average precision, mAP)和precision-recall(PR)曲线作为衡量标准，并使用图像检索工具包(Yuan，2014)对比了下述方法。迭代量化(iterative quantization，ITQ)(Gong等，2013)，主要思想是基于主成分分析(principal component analysis, PCA)采用正交旋转矩阵对初始投影矩阵进行优化以减少误差。局部敏感哈希(locality sensitive hashing，LSH)(Charikar，2002)，基于随机投影。投影向量是从$p$稳定分布(例如，高斯分布)中随机采样得到的。主成分分析哈希(principal component analysis hash，PCAH)(Wang等，2006)，通过主成分分析方法学习到转置矩阵。PCA-RR(principal component analysis-random rotation)(Gong等，2013)，通过随机正交矩阵乘以PCA处理的数据集并将其转换为投影矩阵。密度敏感哈希(density sensitive hashing，DSH)(Jin等，2014)，利用数据的几何结构来决定投影选择，从而可以生成具有更多区分能力的哈希码。谱哈希(SpH)(Weiss等，2008)，将哈希编码过程转化为图像分割问题，进而通过放松约束条件将分割问题转化成拉普拉斯特征图的降维问题，从而求解原问题得到图像数据的哈希编码。加权语义局部敏感哈希(WSLSH)，即本文方法。同时特征聚合哈希(simultaneous feature aggregating and hashing，SAH)(Do等，2017)是在给定一组局部图像表示的前提下，同时学习表示图像的聚合向量和哈希函数。

在这些方法中，LSH，WSLSH是基于随机映射的方法，而SAH，ITQ，PCAH，SpH，DSH和PCA-RR是基于学习得到的哈希映射。

图 7分别展示了各种哈希方法在DataSetB、Holidays、Oxford5k这3个数据集上的mAP曲线。可以看到，基于随机映射的两个方法(LSH，WSLSH)当编码长度较短时，mAP较低。随着编码长度的增加，mAP逐渐增大。尤其是本文的WSLSH随着编码长度的增加，mAP显著增加。在DataSetB、Holidays、Oxford5k数据集上，当编码长度达到32位时，WSLSH的性能已经接近最先进的SAH方法。当编码长度为64位时，本文提出的WSLSH超越了其他比较的方法。通过观察图 7可以看到，基于学习的方法(SAH，ITQ，PCAH，SpH，DSH，PCA-RR)的mAP在编码长度较短时高于基于随机映射的方法。但是随着编码长度的增加，基于学习方法的mAP增长速度较为缓慢。本文WSLSH方法是一种数据独立的采用了随机语义投影的哈希方法，通过建立两层视觉词典更加精细地将相似的参考特征划分到同一视觉子空间，极大地缩小检索数据的范围，在长编码情况下，性能将达到最好。

图 8展示了各种哈希方法在DataSetB数据集上分别使用长度为24，32和64位编码时的PR曲线，从图中可以看出，在24位编码长度时，WSLSH方法的性能低于大部分检索算法。当编码长度为32位时，WSLSH的性能逐渐增强。当编码长度到64位时，WSLSH已经超越了其他算法。图 9是各种哈希方法在Holidays数据集上分别使用长度为24，32和64位编码时的PR曲线，从图中可以看到，WSLSH在24位编码时性能仍然较低，但当编码长度为32位时，WSLSH已经和最先进的SAH接近，并在64位时实现了超越。图 10是各种哈希方法在Oxford5k数据集上分别使用长度为24，32和64位编码时的PR曲线，从图中可以看到，当编码长度为32，64位时，WSLSH超越了其他比较的哈希算法。

本次实验使用的3个数据集DataSetB，Holidays和Oxford5k数据规模依次增大。通过综合比对图 8—图 10可以得出，在编码长度相同的情况下，WSLSH算法在规模越大的数据集上的准确度越高。例如，当编码长度为32位时，WSLSH在规模最大的Oxford5k上性能最好，而在小规模的DataSetB上WSLSH的性能仅仅接近ITQ。这说明WSLSH方法更适合于更大规模的数据集。这是因为数据规模越大，视觉词典对参考特征的空间划分越细致，而在同一视觉子空间的相似参考特征数量并没有显著增加，并没有严重影响到WSLSH算法的准确度。

Razavian等人(2014)，刘颖等人(2020)证明了在图像检索问题中与深度学习结合，即使用卷积神经网络(CNN)生成的全连接层特征比大多数手工特征(如VLAD(Jégou等，2010)，Fisher(Perronnin和Dance，2007))表现得更好。在实验中，将WSLSH与目前先进的无监督哈希方法进行了比较，这些方法使用来自预先训练好的VGG(visual geometry group)网络(Simonyan和Zisserman，2015)的第7层全连接层的输出作为输入。实验中也将使用相同的预训练VGG网络的全连接层特征作为WSLSH的输入，以探索深度特征对图像检索哈希算法精确度的影响。

正如表 2和表 3所示，表 2是ITQ，SPH，SAH，WSLSH使用GIST(Oliva和Torralba，2001)特征的前1 000幅返回图像的mAP。表 3是这4种哈希方法使用从相同预先训练的VGG(Simonyan和Zisserman，2015)最后一层全连接层提取出的特征的前1 000幅返回图像的mAP。表 3清楚地表明ITQ，SPH，SAH，WSLSH应用到全连接层特征后，性能都有了明显的提升。并且，当编码长度为64位时，WSLSH-CNN优于其他方法。

本次实验在SUN397图像数据集(https://vision.princeton.edu/projects/2010/SUN/)上对WSLSH进行测试。该数据集包含397个类别。图像数量因类别而异，但每个类别至少有100幅图像，总共108 754幅图像。实验使用SIFT特征和SURF特征分别建立了两层视觉词典，并使用了加权语义局部敏感哈希(WSLSH)算法分别进行检索，其检索示例如图 11所示。

图 11中最左边的一列为3幅查询图像。其中第1行表示使用SURF特征进行线性查找所得的最近邻的图像，第2行为使用SURF特征并采用WSLSH方法进行检索得到的最近邻图像，第3行为基于图像SIFT特征使用WSLSH检索所得的最近邻图像。因为SUN397图像数据集中的每个图像都属于确定的类，所以通过确定查询结果是否与查询图像属于同一个类别。在图 11中，使用红色框来标记错误的查询结果。从图中可以看出，第2、3行使用WSLSH检索的效果与第1行使用线性检索得到的效果相近。从图 11中也可观察到基于SIFT特征的WSLSH在室外场景中的检索效果比线性检索效果更好，但在室内或封闭空间中，如第3个查询图像，检索效果不佳。

本文在层次化索引结构上对LSH算法进行改进，针对LSH多次索引特征的框架、需要大量的哈希表以及检索速度慢等问题提出加权语义局部敏感哈希(WSLSH)算法。本文对参考特征建立索引时，首先考虑了参考特征与查询特征的距离关系，利用两层视觉词典对参考特征空间进行二次空间划分，根据距离关系对参考特征的哈希索引次数进行加权，区别对待参考特征以避免上述问题。接着，通过随机选择原子哈希函数构造新的变长哈希码，动态使用变长哈希码在同一个哈希表里检查多个哈希桶，提高检索的召回率。最后，针对LSH的随机不稳定性，利用参考特征空间统计中值作为哈希函数量化阈值，确保检索性能稳定性。

实验验证了WSLSH算法的可行性和有效性。在DataSetB，Holidays和Oxford5k这3个数据集上，当编码长度为64位时，WSLSH的mAP、查准率和召回率都优于其他方法。并且，在编码长度相同的情况下，WSLSH算法在规模越大的数据集上的效果越好。

WSLSH算法在建立哈希索引时动态地使用长哈希码来保证特征的高度相似性和检索范围，所以在编码长度较短时，WSLSH算法查准率会有所降低。同时，视觉词典可以一定程度保证落在同一个子集的特征相似性，但也有可能让本来相似的特征没能落到同一个子集上而导致无法检索到，从而导致召回率低。

在将来的工作中，将对特征空间的划分方法、动态变长哈希码的阈值以及语义哈希函数进行进一步的探索，以提高算法在短编码情况下的查准率和召回率。