基于双倍比特量化与分段哈希索引的军事图像过滤

李 雯 邓 涵 许玉珍

1.国防科学技术大学信息通信学院,武汉430010 2.中国科学院信息工程研究所, 北京100049 3.北京强度环境研究所, 北京100076

高维特征的最近邻查询是图像过滤[1]、计算机视觉[2]和目标检测[3]等领域的核心工作。最近邻搜索旨在大规模高维数据库中为查询数据找到与之相似的数据。在大规模数据库中查找最近邻时，通常把欧氏距离作为衡量高维数据之间是否相似的度量标准。然而却造成严重的性能瓶颈[4]。对高维特征最近邻查询性能的影响主要包括2个方面：计算时间和内存占用；传统浮点型特征需要大量的存储空间，且欧氏距离计算复杂度高。二进制码正好有效地解决这2大问题，一方面，海明距离的计算非常高效，只需要几个机器指令即可完成[5]；另一方面，二进制码占用的存储空间远远少于浮点型数据。

二进制码的显著优势推动了二进制量化与索引技术的发展[5]。二进制量化技术把原始的浮点型特征转换为二进制码，并且保证相似的特征以很高的概率被映射为相似的二进制码；同时为二进制码设计相应的索引算法，以实现大规模数据环境下的快速最近邻查询[6]。二进制量化方法主要可以分为2类：基于随机的量化和基于学习的量化[3]。随机量化与处理的数据无关，它通过若干个随机的哈希函数，把特征映射到超平面进行投影。这种映射方式需要维度足够高才具有较好的近似查询效果[7-8]；基于学习的量化是由训练集求出区分性最佳的映射空间，然后再把特征映射到该空间。该方法在维度较低的情况下也能得到较好的近似查询精度，但是它的量化方法极大减弱了原始特征之间的区分性，导致查询精度的降低。

尽管量化后的二进制码在匹配上十分高效，但线性查找仍然无法满足大规模数据环境下的需求。因此，研究者提出针对二进制码的索引技术。文献[9]直接用生成的二进制码作为键来构建哈希表，通过搜索一系列以查询为中心半径递增的海明球体，返回所有近似的结果。但是该方法在二进制码维度较高时，效率十分低下。对于较长的二进制码，文献[10]提出多索引哈希(Multi-index Hashing, MIH)算法。MIH的基本思想是将较长的二进制码划分为若干子串，然后在各个子空间内分别建立哈希表进行搜索。由于空间维度降低，MIH可以极大地提高搜索速度。但是MIH不能有效处理多维二进制量化[4]。

针对上述问题，提出双倍比特量化与分段哈希的近似查询索引，如图1所示，具体创新如下：

1)设计了一种双倍比特量化方法。通过二进制映射技术把高维浮点型的特征投影为中间空间的高维向量，然后把中间空间的高维向量中的每一维数据量化为2个比特二进制码，从而增加特征之间的区分性。双倍比特量化方法可以作用于不同的二进制量化技术、不同类型以及不同维度的特征；

2)针对双倍比特量化的二进制码提出双倍比特分段哈希索引。通过把双倍比特二进制码划分为若干段子串，并对每一段子串分别建立哈希表。在查询最近邻时，同样把查询特征划分为若干个子串，将每个子串在对应的哈希表中进行查询；为了快速计算双倍比特二进制码之间的距离，提出加权的海明距离，以提高查询速度。

本文方法具有3个优点：1)双倍比特量化方法可以有效地降低量化损失，从而提高近似查询精度；2)双倍比特分段哈希索引充分利用二进制码距离度量的特性，有效提高了查询速度；3)方法简单，易于实现。相比于目前已有的基于多倍比特量化的哈希量化索引方法，本文所述的方法只使用双倍比特量化方法，在降低量化损失的同时又保证系统的效率，实现编码比特数目和搜索效率之间更好的权衡，同时针对双倍比特量化技术设计了加权海明距离的计算方法，便于在MIH系统的应用，与线性搜索相比，显著提高了二进制码的查询速度。

在此基础上，设计了大规模军事图像过滤系统。实验表明，相比于Faster R-CNN+CNNH+MIH系统，可以使得大规模军事图像过滤精度提升5.4%。

图1 双倍比特量化与分段哈希索引示意图

1 双倍比特量化与分段哈希索引

1.1 双倍比特量化

为了提高查询效率并节省存储空间，本文通过双倍比特量化把浮点型特征映射为二进制码。并提出一种新的加权海明距离计算方法，提高海明距离的计算效率。

传统的量化方法只能粗略地把中间向量的每一维数据映射为2类(表示为0或者1)，导致中间向量的区分能力大幅降低[4]。为了缓解这个问题，把中间向量的每一维数据量化为2-bit的二进制码，并在最近邻查询时为不同的距离赋予不同的权重，从而有效地提高了高维数据之间的区分性。双倍比特量化方法的步骤如下：

1)特征映射。得到一个K维的特征x，首先用多维投影方法g(s)=[gk(s),k=1，…，K]′把x投影为中间向量g(x)。为了提高特征之间距离计算的有效性，对所有中间向量的每一维数据进行L1归一化得到，其中，li(s)=N[gi(s)],i=1，…，K,N表示对数据归一化；

2)数据划分。首先根据中间向量每一维数据的正负符号把这些数据划分为2类。然后，在每个维度上都计算出到这2类数据的中值，nmi和pmi分别表示第i维的正数数据以及负数数据的中值。根据每维数据的正负符号以及2个中值，把中间向量的每一维数据划分为4类，如图2所示。尽管这个划分方法很简单，该方法仍能应用于多种二进制映射方法上并得到很好的效果；

图2 双倍比特量化方法

3)二进制量化。对数据进行划分后，为了标明不同的4类数据，提出了一种新颖的量化方法。如图2所示，把中间向量的每一维数据量化为2-bit的二进制码。对特征s中的第i维数据，双倍比特量化定义为：

假设特征y为特征x的最近邻，由于中间向量很好地保持了原始特征的相似性，则DBQi(x)和DBQi(y)以很大概率被映射为同一类数据。相反，如果x和y在原始空间的距离很远，那DBQi(x)和DBQi(y)以很大概率被映射到间隔较大的2类数据中。因此，DBQ可以很自然地保持特征之间的相似性。双倍比特量化的本质是为靠近查询向量的特征赋予更高的权重。

1.2 双倍比特分段哈希索引

MIH通过增加海明距离并检测相应的哈希桶来获得最近邻。给定查询q，可以通过q XOR mask来计算需要检测的哈希桶的地址，其中，mask中的比特位的值为1的个数表示海明距离。例如，假设q = 00011011，而需要查询的是与q的海明距离为3的二进制码。于是得到其中一个mask，值为00000111，最后计算出q XOR mask = 00011100，可以验证该结果与q的海明距离为3。

表1 每一维的加权海明距离

然而，当执行最近邻搜索时，XOR操作并不适合于双倍比特二进制码。因此，提出了一种双倍比特分段哈希索引，可以将双倍比特二进制码应用于基于MIH的索引而不改变MIH的结构。如表1所示，在每个维度中有4种二进制码，即00，01，10和11。它们分别对应于十进制中的0，1，2和3。其中，最大值为3(二进制为11)，最小值为0(二进制为00)。因此，每种维度可达的距离范围是不一样的。例如，00可以通过加1，2和3变为01，10和11；对于10，可以对其加1以及减1或2。由于不同的距离相当于不同的权重，所以值的增加或减小被认为是加权海明距离(weighted Hamming distance, WHD)。因此，进行最近邻查询时，在计算加权海明距离的过程中，每种维度都有不同的情况，而不是简单的0/1位翻转。所以，分别讨论不同的情况，具体步骤如下：

1)调整mask大小。mask中的1的数量等于加权海明距离。并且，mask某一维度中1的数量表示对应维度的加权海明距离。假设C1是二进制码中00和11的数量，而C2是二进制码中10和01的数量。由于11和00的加权海明距离的范围是0～3，01和10的加权海明距离的范围是0～2，所以mask的长度被设置为3×C1+2×C2，其中C1+C2=b/2；

3)检测哈希桶。经过前面的步骤，要检测的哈希桶的地址为：

address= query+IN-RN,

举个例子，给定查询 01001011，它是 4 维的 8 位二进制码， mask 的长度设置为 10-bit。假设加权海明距离是 4，则掩码应该包含4个 1。假设其中1个 mask是 0010110100。对于第1维(从右到左)， mask 的相应维度不包含任何 1，因此IN或RN没有任何变化；对于第2维 00， mask(共 3-bit)有2个值为 1 的位，因此IN=IN| 00100000；对于第3维 10，对应的 mask 有1个值为 1 的位，则RN=RN| 00000100；对于第4维 11，存在1个比特值为 1，因此RN=RN|00000001。于是得到IN= 00100000，RN= 00000101。代入公式可得：需要检测的哈希桶的地址是 01100110，其与 q 的加权海明距离为 4。

后续的查询操作与原始MIH算法[10]一致。

双倍比特分段哈希索引考虑了加权海明距离的所有情况，并且每种情况只出现1次。为了使双倍比特二进制码适用于MIH，本文考虑mask和二进制码的不同组合而不是单个mask，以获得要检测哈希桶的地址。从实验结果来看，与线性查询相比，双倍比特分段哈希索引可以显著提高查询速度。

2 实验结果及分析

本节验证本文算法的有效性。第2.1小节使用多种二进制映射方法验证双倍比特量化的有效性；第2.2小节验证双倍比特分段哈希索引的有效性；第2.3小节验证本文方法在大规模军事图像过滤上的性能。

2.1 双倍比特量化实验及结果分析

表2显示在BIGANN 1M GIST数据集[11]上，使用原始二进制映射算法和双倍比特量化方法的比较结果。实验包括了1000个查询，这1000个查询的平均准确率和平均召回率用作判断双倍比特量化的性能指标。结果表明，双倍比特量化方法的查询精度总是高于传统二进映射算法。当采用SH时，可以观察到128bit的二进制码的准确率提高了42.3%。实验结果表明，双倍比特量化为传统的二进制映射获得了极大的性能提升。

表2 在数据集BIGANN 1M GIST的结果(%)

表2显示了二进制码分别为64bit, 128bit, 256bit和512bit，二进制投影算法分别为ITQ，RR，SH，LSH。P@1表示表示top-1的准确率，R@10表示top-10的召回率。SB表示单比特量化，DB表示双比特量化。

2.2 双倍比特分段哈希索引实验及结果分析

在BIGANN SIFT1G[11]数据集上验证双倍比特分段哈希索引，使用多个查询的平均查询速度度量索引的查询速度。每个实验进行10000次查询，每个查询的平均运行时间作为双倍比特分段哈希索引的判别指标。当二进制维度为64时，将二进制码划分为4段，而128bit的二进制码被分成8段。结果表明，与线性查询相比，双倍比特分段哈希索引的查询效率显著提升。图3和4显示了不同k-NN问题和2个不同二进制码长度(64bit和128bit)的线性查询和双倍比特分段哈希索引的查询速度。虽然二进制代码的线性查询速度已经足够快[9]，但双倍比特分段哈希索引执行速度仍然比线性查询提高了若干倍。例如，当二进制码为128维并且最近邻个数为100时，双倍比特分段哈希索引的速度大约比线性查询提高了5倍(图3)。1NN和10NN的性能更令人印象深刻。而使用64位LSH二进制码，双倍比特分段哈希索引执行1NN搜索任务的速度比线性搜索快30倍。

图3 通过LSH生成的64bit二进制码在分段哈希索引中进行最近邻查询的平均运行时间，并以线性查询为基准，其中设置最近邻数量分别为1,10和100

图4 通过LSH生成的128bit二进制码在分段哈希索引中进行最近邻查询的平均运行时间，并以线性查询为基准，其中设置最近邻数量分别为1，10和100

把特征的每一维数据量化为2个bit二进制码，因此在二进制特征存储层面会使得存储空间翻倍。由于二进制码每1位只占1个比特位，因此增加的存储空间有限。

2.3 基于双倍比特量化和分段哈希索引的军事图像过滤性能

为了验证本文方法在军事图像过滤上的有效性，基于上述方法设计了图像过滤系统。图像过滤系统框架如图5所示，运行于Linux平台，采用C++和Python混合编码实现。本文分别构建含10类军事标识(枪支、刀具、飞机、军舰、军章、军衔、基地、旗帜、设备和奖章)的训练集和测试集。其中训练集有2万幅图像，每类标识有2000幅图像；样例集有2000幅图像，每类标识有200幅图像。从网络上采集10000幅含有各类军事标识的图像作为测试集，模拟网络图像过滤。实验的硬件环境是：Intel Xeon E5-2620*2(2.00 GHz, 7.2GT/s, 15M cache, 6cores)，K80GPU，64G内存。

图5 图像过滤系统架构

基于Faster R-CNN+CNNH+MIH框架[11]的图像过滤系统主要分为3个部分：①采用了何凯明等人提出的Faster R-CNN的目标检测算法，进行目标的定位；②颜水成等人在2014年提出的CNNH算法，此算法提取目标特征，并且将浮点数特征量化为二进制码；③2011年Norouzi等人提出的哈希索引算法，采用分段检索的方法进行二进制码的快速最近邻查询。表3对比了本文系统与基于Faster R-CNN+CNNH+MIH框架的图像过滤系统对军事图像的过滤精度，可以看出本文系统具有更高的过滤精度，相比于Faster R-CNN+CNNH+MIH系统，可以使得过滤精度提升5.4%。图6显式地展示了本文系统对军事图像的过滤效果。

表3 2种图像过滤系统精度对比(度量标准是mAP)

图6 图像过滤系统架构军事图像过滤展示(左侧为库图像，右侧为系统发现的与其内容相似的网络图像)

3 结论

为充分利用二进制码占用存储空间少且易于进行距离度量的优势，研究者提出二进制量化方法以实现大规模数据环境下的快速最近邻查询。但是，二进制量化损失原始特征的信息量，导致查询精度的降低。针对这一问题，提出双倍比特量化与分段哈希的近似查询索引；把特征的每一维数据量化为2个比特二进制码以增加特征之间的区分性；对二进制码分段并建立哈希索引提高查询速度。据此，本文设计了大规模军事图像过滤系统。实验表明，相比于Faster R-CNN+CNNH+MIH系统，本文方法可以使军事图像过滤精度提升5.4%。