基于动态阈值哈希的大规模遥感影像快速内容检索方法

强永刚，肖志峰，陈欢欢，闫丽阳

(1. 中国科学技术大学计算机科学与技术学院，安徽 合肥 230027； 2. 武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉 430079)

随着对地观测技术的快速发展及高分辨率成像传感器的广泛使用，每天获取的遥感影像数量呈现指数级增长的趋势，使得大规模遥感影像数据库的有效管理和检索面临着巨大挑战。基于内容的遥感影像检索通过搜索并返回与查询影像相关的影像，为大规模遥感影像检索任务提供了可能的有效解决途径，近年来受到众多研究者的关注[1- 3]。基于内容的大规模遥感影像检索任务中，影像特征的长度及相似性度量方法将对检索效率产生重要影响，尤其是在面对超大规模影像数据库检索任务的情景下[4- 7]。因此，如何通过构建高效的特征索引结构实现快速检索是大规模影像检索必须面对的问题[8]。针对以上问题，本文提出动态阈值哈希索引方法，该方法根据特征向量的空间分布情况动态生成向量的哈希编码，对高维的遥感影像特征向量进行低维编码，大大降低了检索计算量，可显著提高大规模遥感影像库的检索准确率和效率，可有效应用于大规模遥感影像检索。

1 动态阈值哈希索引方法

由于遥感影像数据量巨大，常规特征提取方法往往提出了高维影像特征向量，此时进行特征向量的相似性度量需要消耗大量的时间，因此需要考虑建立高效的索引结构加快影像检索的速度。本文基于局部敏感哈希(local sensitive hashing,LSH)算法的基本思想，提出一种动态阈值哈希索引方法，为海量影像的相似性度量和快速检索提供思路，并将其应用于大规模遥感影像内容检索，减少影像检索所需的时间。

1.1 局部敏感哈希原理

LSH算法是一种常见的用于处理高维特征向量索引问题的方法[9]，其基本思想为：将原始数据空间中的相邻数据点通过某种哈希变换后，得到相同哈希结果的概率很大，而对于原始空间中不相邻的数据点，得到相同哈希结果的概率很小。局部敏感哈希的具体方案依赖于所使用的局部敏感哈希函数[10]，对于位于Rd空间中的任意两个向量p和q，如果存在函数族H，满足以下条件，则称H是(R,cR,p1,p2)敏感的。

(1) 如果‖p-q‖≤R，则PrH[h(p)=h(q)]≥p1。

(2) 如果‖p-q‖≥cR，则PrH[h(p)=h(q)]≤p2。

其中，PrH[h(p)-h(q)]表示p和q哈希结果相同的概率，c是一个不大于1的正数。

在对原始数据哈希映射之后，可以用所得二进制编码之间的海明距离代替原空间中的距离计算方法计算特征向量之间的距离，在大大提高运算速度的基础上，得到较为准确的近似最近邻结果。

1.2 动态阈值哈希算法

基于深度卷积神经网络的遥感影像内容检索中[11- 13]，采用余弦相似度比较两个特征向量之间的相似性。特征向量在比较距离之前进行了L2范数归一化处理后所有的特征向量的长度为1。对于这种海量特征数据，可以采用一种按照各维度上数值的正负号进行哈希的方法划分原始数据空间，其实质是根据特征点分布在多维空间中的不同象限进行哈希分块。若原始特征向量为F，其长度为D，特征经过哈希所得的二进制编码为C，则C中第位的值为

哈希后的二进制编码长度仍为D，共有2D种哈希结果。对于二维特征向量，在平面中的划分如图1所示。

这种划分方式有效地保持了向量之间的相似程度，余弦相似度大的向量被划分到同一子空间的概率足够大，而余弦相似度小的向量被划分到同一子空间的概率很小，对于原始空间中更相似的特征向量，其对应的二进制编码之间的海明距离更小。但若直接比较各维度上数值与0的大小，则可能丧失对实际数据的理解。实际数据在每一个维度上并不一定是以0作为中位数的分布，特别是当原始数据中某一维度上的取值全为正时，所有数据的哈希结果中对应的二进制位将全部被标记为1，无法产生理想的哈希效果。因此，可先通过训练数据计算数据在这一维度上的中位数，代替原设计中的0，用于后续哈希计算，本文将这种方法称为动态阈值哈希方法(dynamic threshold hashing,DTH)。若训练数据中的特征向量总条数为M，则当处理到第i维时，首先计算所有训练数据在第i维的中位数Ti

然后对于每条特征向量，根据Fi与Ti的大小关系确定哈希所得的二进制编码C中第i位的值

图2给出了分别使用0作为固定阈值进行哈希(如图2(a)所示)和使用动态阈值进行哈希(如图2(b)所示)的效果,可以明显看出，使用动态阈值进行哈希能够使数据划分更加均匀。

实际应用中，二进制编码的位数应该尽量短小，以保证存储大规模的影像数据。因此，需要编码的二进制位数N通常远小于原始特征数据的维数，最基本的解决办法是从原始数据中随机抽取N个维度进行处理，但这种方法很难保证原始数据在所选取的维度上具有良好的区分能力。对原始高维特征数据进行降维处理[14]，然后再利用DTH方法对降维后的数据进行处理是一种可行的方案。

DTH作为一种动态哈希手段，可以对其他通过降维的特征进行动态哈希处理。若对原始数据进行主成分分析，将原始特征数据降维到N维，然后再使用动态阈值哈希方法对降维后的N维数据进行处理，这种哈希方法记为PCA- DTH。若求取原始数据在每一维度上的标准差，然后选择标准差最大的前N个维度，在这些维度上进行动态阈值哈希处理，这种利用最大标准差(max standard deviation,MSD)进行数据预处理的动态阈值哈希方法记为MSD- DTH。

为了进一步提升其性能，可以考虑将这种基于动态阈值进行哈希的思想应用到性能优良的迭代量化方法(ITQ)中。ITQ算法的基本思想是首先对原始特征数据进行降维处理，然后通过期望最大化(expectation maximization,EM)算法求取使得新数据具有最小量化误差的旋转矩阵，通过该旋转矩阵对降维后数据进行旋转后，能够取得更稳定的哈希效果。本文基于动态阈值哈希索引方法的思想对其进行改进，首先对ITQ算法中PCA降维后的特征数据进行中位数置0，也即计算降维后数据在每一维上的中位数，然后对每一维度上的数据进行相应的中位数大小的偏移，使偏移后的数据在每一维度上的中位数都为0，这时，新的数据是以0为中位数的分布，最后对偏移后的数据进行ITQ的迭代操作，求取最佳旋转矩阵。本文将这种哈希方法记为PCA- DTH- ITQ，相应的，基于MSD- DTH实现的ITQ算法称之为MSD- DTH- ITQ。图3通过将PCA- DTH- ITQ哈希方法与PCA- ITQ哈希方法进行对比，描述了该哈希方法的思路，其中图3(b)为PCA- ITQ哈希方法对图3(a)中的特征数据旋转后的结果，图3(c)通过数据偏移将图3(a)中的特征数据的中位数置为0，图3(d)为PCA- DTH- ITQ哈希方法对图3(c)中的特征数据旋转后的结果。

2 试验分析

2.1 试验数据及环境

通过已有的数据集对检索性能进行评价是必不可少的关键步骤。自然图像检索中已经存在大量公开的数据集，但由于遥感影像自身的特点，公开的遥感影像数据集很少，因此，为了有效评价基于深度神经网络模型所提取的遥感影像特征在遥感影像内容检索中的性能，在进行具体的试验前需要手动制作合适的遥感影像数据集。本文从天地图第14级遥感影像中选择了14 129幅大小为768×768像素的遥感影像，它由相邻的9张256像素大小的遥感影像瓦片按照3×3的排列方式拼接而成。将其分为10个类别，各影像类别的名称及具体数量见表1，具体如图4所示。

影像类别影像数量影像类别影像数量裸地1685海岸1126耕地1682岛屿742云层1153居民区1024林地2183湖泊398半林地1917河流2219

2.2 性能分析

为了验证本文所提出的动态阈值哈希索引方法对大规模影像高维特征的索引效果，基于遥感影像数据集，将动态阈值哈希索引方法的检索效果与其他局部敏感哈希方法进行比较。试验中采用基于ImageNet训练所得的VGG- F模型提取影像的深度特征[13]，并将其降维到512维，从数据库中随机选择2000张作为测试图像。

对于局部敏感哈希算法及其相关的近似最近邻搜索算法，存在两种常见的算法评价方案。

(1) 以真实的最近邻搜索的结果为真值。对于所有特征向量，计算各自与其第N个最近邻之间的距离，并将这些距离的平均值作为一个距离阈值。对于每一条待测试的特征向量，可通过此距离阈值确定哪些特征向量与之相关或不相关，与之距离小于等于该阈值则相关，反之则不相关。在进行哈希查找近似最近邻时，以此作为判断返回结果是否与查询向量相关的依据[15]。实际上，该方法是以线性搜索的结果为标准进行算法评价，在本文试验中，N取值为500，在该评价方案中，以召回率- 精度(recall- precision)曲线和平均检索精度mAP作为具体的评价指标。

(2) 以具有相同类别标签的数据为真值。对于具有类别标签的数据集，可以直接使用原始特征数据的类别标签作为评价算法性能的依据。在进行哈希查找近似最近邻时，根据返回结果的类别标签是否与查询向量一致作为判断其是否相关的依据[16]。该评价方案中，本文将检索返回的图像数量为500时的检索精度作为具体的评价指标。

试验中将以上4种动态阈值哈希索引方法(MSD- DTH、PCA- DTH、MSD- DTH- ITQ、PCA- DTH- ITQ)与其他多种流行的哈希算法进行了比较，主要有随机超平面散列法(RHH)、密度敏感哈希(DSH)、谱哈希(SH)和迭代量化方法(PCA- ITQ)[17- 18]，分别用以真实的最近邻搜索的结果为真值的评价方案和以具有相同类别标签的数据为真值的评价方案进行算法性能评估。图5给出了两种算法评价方案中各种不同哈希索引方法的检索性能。其中，图5(a)基于以真实的最近邻搜索结果为真值的评价方案，给出了哈希编码位数与平均检索精度之间的关系；图5(b)基于以具有相同类别标签的数据为真值的评价方案，给出了返回的影像数量为500时，哈希编码位数与检索精度之间的关系。图6给出了第1种评价方案下，召回率与精度的关系。图7给出了第2种评价方案下，检索时返回的影像数量与检索精度的关系。

根据对各种不同哈希算法的性能分析结果，可以得出以下几个结论：

(1) 若单独使用本文所提出的较为简单的MSD- DTH和PCA- DTH算法，其性能表现一般，这和笔者的预期是一致的。但若将DTH算法的思想应用到ITQ算法中，由此产生的MSD- DTH- ITQ和PCA- DTH- ITQ算法性能优良，特别是在哈希编码的位数较小时，它们能够取得最优的检索效果。

(2) 主成分分析是进行特征选择和降维的最常用方法，大量研究表明该方法具有十分优良的特性。但根据本试验结果，MSD- DTH的性能优于PCA- DTH，MSD- DTH- ITQ的性能优于PCA- DTH- ITQ。表明在某些应用中，使用标准差最大化的简单策略进行特征选择和降维，其性能并不亚于甚至优于主成分分析法。

(3) 图5(b)是以具有相同类别标签的数据为真值的评价方案，图中表明了返回的影像数量为500时，哈希编码位数与检索精度之间的关系。当哈希编码的位数大于32时，MSD- DTH- ITQ和PCA- DTH- ITQ的检索精度优于线性搜索(linear- search)，PCA- ITQ算法在哈希编码的位数大于64时也具有这种性质。结果表明基于ITQ系列索引方法所得的近似最近邻结果相对线性搜索所得的最近邻结果，更加贴近遥感影像数据的真实类别标签。

当哈希编码位数为64时，在遥感影像数据集上使用以具有相同类别标签的数据为真值的评价方案进行遥感影像检索，所得的各哈希方法的前30个检索结果如图8所示，其中，带×号的图像是不相关影像。

通过以上试验，表明了本文所提出的动态阈值哈希索引方法的有效性和先进性，对于大规模数据的快速查询与检索，基于动态阈值的哈希索引方法具有较大的应用潜力。

3 结 语

遥感影像高维特征造成的“维度灾难”是遥感影像内容检索研究面临的重要问题，造成检索响应时间的大大增加。为了解决这一问题，本文将遥感影像内容检索的特征最近邻搜索问题转化为近似最近邻问题，提出了动态阈值哈希索引方法，在影像检索的精度损失非常小的情况下，显著提升了检索的速度，对大规模遥感影像内容检索研究具有较好的促进作用。