ｅａｌ－ｖａｌｕｅｄ　ｃｏｕｎｔｅｒｐａｒｔ　ｏｆ　ｔｈｅ　ｏｂｊｅｃｔｉｖｅ　ｆｕｎｃｔｉｏｎ　ｉｎｓｔｅａｄ．Ａｆｔｅｒ　ｔｈａｔ，ｔｈｅ　ｏｐｔｉｍｕｍｏｂｔａｉｎｅｄ　ｉｎ　ｔｈｅ　ｒｅｌａｘｅｄ　ｒｅａｌ－ｖａｌｕｅｄ　ｓｐａｃｅ　ａｒｅ　ａｇａｉｎ　ｑｕａｎｔｉｚｅｄ　ｔｏ　ｇｅｎｅｒａｔｅ　ｔｈｅ　ｒｅａｌ　ｂｉｎａｒｙ　ｃｏｄｅｓ．Ｈｏｗｅｖｅｒ，ｔｈｅｒｅ　ｉｓ　ｎｏ　ｇｕａｒａｎｔｅｅ　ｔｈａｔ　ｔｈｅ　ｒｅａｌ－ｖａｌｕｅｄ　ｏｐｔｉｍｕｍ　ｗｏｕｌｄ　ｒｅｍａｉｎ　ｏｐｔｉｍｕｍ　ａｆｔｅｒ　ｑｕａｎｔｉｚａｔｉｏｎ，ａｎｄ　ｔｈｕｓ　ｅｘｉｓｔｉｎｇ　ｍｅｔｈｏｄｓ　ｉｎｅｖｉｔａｂｌｙ　ｓｕｆｆｅｒ　ｆｒｏｍ　ｐｅｒｆｏｒｍａｎｃｅ　ｄｒｏｐ　ｗｈｅｎ　ｑｕａｎｔｉｚｉｎｇ　ｔｈｅ　ｒｅａｌ－ｖａｌｕｅｄｏｐｔｉｍｉｚａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｉｎｔｏ　ｂｉｎａｒｙ　ｃｏｄｅｓ，ｄｕｅ　ｔｏ　ｔｈｅ　ｄｉｓｃｒｅｐａｎｃｙ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｂｉｎａｒｙ　Ｈａｍｍｉｎｇ　ｓｐａｃｅａｎｄ　ｔｈｅ　ｒｅａｌ－ｖａｌｕｅｄ　Ｅｕｃｌｉｄｅａｎ　ｓｐａｃｅ．Ｔｏ　ｂｅｔｔｅｒ　ｄｅａｌ　ｗｉｔｈ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｑｕａｎｔｉｚａｔｉｏｎ，ｔｈｉｓ　ｐａｐｅｒｐｒｏｐｏｓｅｓ　ａ　ｎｏｖｅｌ　ｈａｓｈ　ｌｅａｒｎｉｎｇ　ｍｅｔｈｏｄ，ｎａｍｅｄ　Ｄｅｅｐ　Ｄｉｓｃｒｅｔｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｈａｓｈｉｎｇ （ＤＤＯＨ）．Ｆｉｒｓｔ　ｏｆ　ａｌｌ，ｔｈｅ　ｉｎｉｔｉａｌ　ｂｉｎａｒｙ　ｃｏｄｅｓ　ｏｆ　ａｌｌ　ｔｒａｉｎｉｎｇ　ｉｍａｇｅ　ｓａｍｐｌｅｓ　ａｒｅ　ｏｂｔａｉｎｅｄ　ｂｙ　ｏｎｅ　ｏｆ　ｔｈｅ　ｔｈｒｅｅｂｉｎａｒｙ　ｃｏｄｅ　ｉｎｉｔｉａｌｉｚａｔｉｏｎ　ｍｅｔｈｏｄｓ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ａｆｔｅｒ　ｔｈａｔ，ａ　ｄｉｓｃｒｅｔｅ　ｂｉｎａｒｙ　ｃｏｄｅｓｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｄｅｓｉｇｎｅｄ，ｗｈｉｃｈ　ｔａｋｅｓ　ｔｈｅ　ｉｎｉｔｉａｌ　ｂｉｎａｒｙ　ｃｏｄｅｓ　ｏｆ　ｔｒａｉｎｉｎｇ　ｉｍａｇｅｓ　ａｓ　ｗｅｌｌ　ａｓｔｈｅｉｒ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｌａｂｅｌ　ｉｎｆｏｒｍａｔｉｏｎ　ａｓ　ｉｎｐｕｔｓ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｔｅｒａｔｉｖｅｌｙｄｅｃｉｄｅｓ　ｗｈｅｔｈｅｒ　ｏｒ　ｎｏｔ　ｔｏ　ｆｌｉｐ　ｃｅｒｔａｉｎ　ｂｉｎａｒｙ　ｂｉｔｓ　ｉｎ　ｔｈｅ　ｂｉｎａｒｙ　ｃｏｄｅｓ　ｗｉｔｈ　ｔｈｅ　Ｆｉｓｈｅｒ’ｓ　ｌａｗ，ａｎｄ　ｉｔｉｓ　ｔｈｅｏｒｅｔｉｃａｌｌｙ　ｐｒｏｖｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｔｈａｔ　ｂｙ　ｄｏｉｎｇ　ｓｏ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｗｏｕｌｄ　ｉｍｐｒｏｖｅ　ｏｒ　ａｔｌｅａｓｔ　ｗｏｕｌｄ　ｎｏｔ　ｄｅｃｒｅａｓｅ　ｔｈｅ　ｄｉｓｃｒｉｍｉｎａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ｂｉｎａｒｙ　ｃｏｄｅｓ　ｉｎ　ｔｅｒｍｓ　ｏｆ　ｔｈｅ　Ｆｉｓｈｅｒ’ｓ　ｌａｗ．Ｎｅｘｔ，ｔｏ　ｏｂｔａｉｎ　ｔｈｅ　ｈａｓｈ　ｆｕｎｃｔｉｏｎｓ　ｗｈｉｃｈ　ｗｏｕｌｄ　ｂｅ　ｕｓｅｄ　ｔｏ　ｅｎｃｏｄｅ　ｎｅｗ－ｃｏｍｉｎｇ　ｉｍａｇｅｓ，ａ　ｄｅｅｐｃｏｎｖｏｌｕｔｉｏｎａｌ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ（ＣＮＮ）ｉｓ　ｔｒａｉｎｅｄ　ｔｏ　ｆｉｔ　ｔｈｅ　ａｆｏｒｅｍｅｎｔｉｏｎｅｄ　ｂｉｎａｒｙ　ｃｏｄｅｓ．Ｓｐｅｃｉｆｉｃａｌｌｙ，ｗｉｔｈ　ｔｈｅ　ｏｐｔｉｍｉｚｅｄ　ｂｉｎａｒｙ　ｃｏｄｅｓ，ｅａｃｈ　ｂｉｔ　ｃａｎ　ｂｅ　ｓｅｅｎ　ａｓ　ａ　ｂｉｎａｒｙ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｐｒｏｂｌｅｍ，ａｎｄ　ａｌｌｂｉｎａｒｙ　ｃｌａｓｓｉｆｉｅｒｓ　ｔｈａｔ　ｓｈａｒｅ　ｔｈｅ　ｓａｍｅ　ｆｅａｔｕｒｅ　ｍａｐ　ｏｆ　ｔｈｅ　ＣＮＮ　ａｓ　ｔｒａｉｎｉｎｇ　ｉｎｐｕｔｓ　ａｒｅ　ｔｒａｉｎｅｄ　ｔｏｐｅｒｆｏｒｍ　ａｓ　ｔｈｅ　ｈａｓｈｉｎｇ　ｆｕｎｃｔｉｏｎｓ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｏｎ　ｔｗｏ　ｗｉｄｅｌｙ　ｓｔｕｄｉｅｄ　ｄａｔａｓｅｔｓ　ＣＩＦＡＲ－１０ａｎｄＩｍａｇｅＮｅｔ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ａｃｈｉｅｖｅｓ　ｓｔａｔｅ　ｏｆ　ｔｈｅ　ａｒｔ　ｒｅｔｒｉｅｖａｌ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｎＣＩＦＡＲ－１０，ａｎｄ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｅｘｉｓｔｉｎｇ　ｈａｓｈｉｎｇ　ｍｅｔｈｏｄｓ　ｂｙ　ａｂｏｕｔ　２．２％ ｍｅａｎＡｖｅｒａｇｅ　Ｐｒｅｃｉｓｉｏｎ（ｍＡＰ）ｏｎ　ＩｍａｇｅＮｅｔ－１００，ｖａｌｉｄａｔｉｎｇ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ．Ｋｅｙｗｏｒｄｓ　 ａｐｐｒｏｘｉｍａｔｅ　ｎｅｉｇｈｂｏｒ　ｓｅａｒｃｈ；ｈｉｇｈ　ｄｉｍｅｎｓｉｏｎａｌ　ｆｅａｔｕｒｅ　ｉｎｄｅｘｉｎｇ；ｈａｓｈ　ｌｅａｒｎｉｎｇ；ｄｉｓｃｒｅｔｅｏｐｔｉｍｉｚａｔｉｏｎ；ｃｏｎｖｏｌｕｔｉｏｎａｌ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ１　引　言随着便携式拍照设备的大量普及和社交网络的快速发展，互联网上的图片数量呈现爆炸式增长的趋势．面对海量的图像数据，在有限的时间和计算资源下，根据用户提供的查询图像搜索相似图像也变得极为困难．为了在可接受的时间内返回检索结果，近似近邻搜索算法在大规模以图搜图任务中得到了越来越多的关注．作为一种具有代表性的近似近邻搜索算法，哈希学习方法通过学习一组可以保持原始空间中相似性的哈希函数，将高维的图像样本编码为相对低维的二值编码．由于低维二值编码占用的存储空间非常小，同时可以通过 ＣＰＵ 中集成的异或、比特计数等指令实现高效地距离计算，因此哈希学习方法逐渐成为了一种主流的近似近邻搜索方法，相应 地 也 出 现 了 越 来 越 多 新 的 哈 希 学 习 实 现方法．从本质上来说，哈希学习的目标是获得能够保持原始空间中相似性的二值编码 及相应的 哈希函数．由于二值码的离散性质，哈希学习算法中无法避免地要涉及到离散优化的问题．但是直接对二值码优化是一个 ＮＰ 困难的问题，无法进行高效地精确求解．为了解决这个问题，大多数已有的哈希学习方法［１－３］通常首先将离散取值的二值码松弛为实数值，并对定义在实数值上的近似问题进行优化．在对近似问题完成优化后，再重新将优化得到的实数值量化为二值的编码．但是由于实数值的欧氏空间与二值的汉明空间之间存在本质的差异，上述基于松弛－量化的方法即使可以在实数值空间中得到最优的实数值编码，也无法保证在量化之后得到的二值编码仍然是最优的．为了解决这个问题，本文提出一种新的哈 希 学 习 方 法———深 度 离 散 优 化 哈 希 （ＤｅｅｐＤｉｓｃｒｅｔｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｈａｓｈｉｎｇ，ＤＤＯＨ）．该方法可以通过直接在二值的汉明空间中进行离散优化来避免松弛－量化过程的缺点．具体来说，本文方法的框０５１１ 计　　算　　机　　学　　报 ２０１９年．首先通过随机初始化或主成分分析的方式获得样本初始的二值码，之后通过汉明空间中的离散迭代优化增强二值码的判别能力．最后，通过训练卷积神经网络模型来拟合优化得到的二值码，并将训练得到的神经网络作为编码时使用的哈希函数．图 １　深度离散优化哈希（Ｄｅｅｐ　Ｄｉｓｃｒｅｔｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｈａｓｈｉｎｇ，ＤＤＯＨ）方法流程示意图（本文方法主要包括三个步骤：第一步，通过使用任意的图像特征，并在该特征的基础上通过随机初始化、随机投影或主成分分析（Ｐｒｉｎｃｉｐｌｅ　Ｃｏｍｐｏｎｅｎｔ　Ａｎａｌｙ－ｓｉｓ，ＰＣＡ）的方式，获得初始的二值编码；第二步通过离散二值码优化对初始二值码进行迭代更新，获得判别力更强的二值码；第三步，通过训练深度卷积神经网络拟合优化得到的二值码，同时学习具有强判别能力的图像特征并获得相应的用于编码的哈希函数）具体来说，在离散二值码优化部分，本文提出的方法基于 Ｆｉｓｈｅｒ准则，要求相似的图像具有相似的二值码，不相似图像对应的二值码也尽可能不同．在优化的时候，通过在离散的汉明空间中计算损失函数的次梯度，并根据相应设计的规则，通过对满足一定条件的比特进行翻转的方式进行优化，以此提升二值编码的判别能力．在拟合部分，以优化得到的二值编码作为监督，在预训练的深度卷积神经网络的基础上，使用交叉熵损失对卷积神经网络模型进行参数微调，得到相应的模型用来对图像进行编码．当模型训练完成后，以图像作为卷积神经网络模型的输入，对模型的输出进行量化即可得到相应图像的二值编码．在此基础上，可以通过汉明距离排序、哈希表查表等方式进行快速的近似近邻搜索．为了验证本文方法的有效性，在 ＣＩＦＡＲ－１０和ＩｍａｇｅＮｅｔ－１００两个常用的图像检索评测数据库上进行了实验，在平均检索精度（ｍｅａｎ　Ａｖｅｒａｇｅ　Ｐｒｅｃｉｓｉｏｎ，ｍＡＰ）指标上达到了与已有方法同样优秀或者超过已有方法的性能，特别是在ＩｍａｇｅＮｅｔ－１００数据库上相比于已有方法提升了约２．２个百分点，证明了本文提出方法的有效性．本文 第 ２ 节对于已有的哈希学习方法进行综述，并讨论本文方法与已有方法的区别；第３节对本文方法中的各个环节进行详细的介绍；第４节在通用的大规模图像检索评测数据集 上进行大 量的实验，验证本文方法的有效性；第５节对本文工作进行总结和展望．２　相关工作近邻搜索任务的目标是在给定一个查询样本的条件下，对数据库进行搜索，并返回数据库中和查询样本相似的样本．当数据库的规模非常大或者计算样本间的相似度非常耗时的情况下，精确的近邻搜索所需的计算代价也将增长到难以接受的程度．因此，作为一种更实用的替代方案，近似近邻搜索凭借其更高的效率受到了越来越多的关注．近似近邻搜索的关键在于使用一种高效的相似度计算方式替代原有的、低效的计算方式．作为一种具有代表性的近似近邻搜索方法，哈希［１－５］方法由于占用的存储空间极小、计算极为高效，吸引了大量研究人员的关注．在哈希方法中，早期的研究工作主要关注不依赖于数 据 的 哈 希 算 法，如 局 部 敏 感 哈 希 （ＬｏｃａｌｉｔｙＳｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ，ＬＳＨ）［４］方法．这 类 方 法 使 用 随机投影的方式对特征空间进行划分，生成二值码的不同比特．理论上可以证明，随着二值码比特数量的增长，通过这类方法得到的二值码之间的汉明距离可以渐近地逼近相应样本在原 始特征空间 中的距离．但是由于这类方法没有考虑数据的实际分布情况，往往需要较多的比特才能达到较好的检索结果，因此对于存储空间的需求较高．为了获得更紧凑的二值码，基于数据进行学习的哈希学习算法逐渐成为主流．这类哈希学习方法通过在一个训练集上进行学习，相比于不依赖数据５期 刘昊淼等：基于离散优化的哈希编码学习方法１５１１到与数据更加适配的哈希函数，因此通常在使用同样数量的比特时，可以达到更好的检索精度．按照训练数据是否有人工标注的标签，哈希学习方法又可以进一步分为无监督方法和有监督方法两类．其中，无监督方法适用于数据没有标签的情况，可以直接在无标注的训练数据上学习哈希函数．在无监督哈希 学 习 方 法 中，谱 哈 希 （ＳｐｅｃｔｒａｌＨａｓｈｉｎｇ，ＳＨ）［６］以样本对在原始特征空间中的相似度作为权重，通过最小化投影后得到的二值码之间的加权汉明距离学习哈希函数；迭代量化（ＩｔｅｒａｔｉｖｅＱｕａｎｔｉｚａｔｉｏｎ，ＩＴＱ）［１］通 过 主 成 分 分 析 （ＰｒｉｎｃｉｐｌｅＣｏｍｐｏｎｅｎｔ　Ａｎａｌｙｓｉｓ，ＰＣＡ）将样本投影到低维空间后，寻找一个正交变换矩阵尽可能减小量化损失，以正交变换后的主成分作为哈希函数．为了更好地应对面向复杂的语义相似度进行检索的任务，研究者进一步提出使用人工标注的标签信息辅助进行有监督的哈希函数学习．在有监督哈希学习方法中，典型相关分析迭代量化 （ＣａｎｏｎｉｃａｌＣｏｒｒｅｌａｔｉｏｎ　Ａｎａｌｙｓｉｓ　Ｉｔｅｒａｔｉｖｅ　Ｑｕａｎｔｉｚａｔｉｏｎ，ＣＣＡ－ＩＴＱ）［１］的思想与迭代量化大致相同，只是在投影到低维空间时，通过利用样本的标签，使用典型相关分析（ＣＣＡ）对 样 本 的 特 征 进 行 投 影；最 小 损 失 哈 希（Ｍｉｎｉｍａｌ　Ｌｏｓｓ　Ｈａｓｈｉｎｇ，ＭＬＨ）［７］为了缓解松弛－量化带来的负面影响，在松弛之后通过优化一个近似的损失上界来学习哈希函数．上述方法均使用线性投影作为哈希函数对数据的原始特征进行变换，因此无法很好地处理数据线性不可分的情况．为了解决这个问题，核 监 督 哈 希 （Ｋｅｒｎｅｌ　Ｓｕｐｅｒｖｉｓｅｄ　Ｈａｓｈｉｎｇ，ＫＳＨ）［８］和 二 值 重 建 嵌 入 （Ｂｉｎａｒｙ　ＲｅｃｏｎｓｔｒｕｃｔｉｖｅＥｍｂｅｄｄｉｎｇ，ＢＲＥ）［９］提出在核空间中学习非线性的哈希函数；深度哈希（Ｄｅｅｐ　Ｈａｓｈｉｎｇ，ＤＨ）［１０］使用高度非线性的深层感知机制学习判别能力更强的非线性哈希函数．尽管上述方法在哈希学习任务中取得了一定的成功，但是由于在学习的过程中使用的样本特征表示并不能完全和数据匹配，因此在检索精度上有一定的局限．为了解决这个问题，近期的一些深度哈希方法提出使用深度卷积神经网络，同时学习图像的特征表示和非线性的哈希函数．其中，卷积神经网络哈希（Ｃｏｎｖｏｌｕｔｉｏｎａｌ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ　Ｈａｓｈｉｎｇ，ＣＮＮＨ）［１１］首先对样本间的相似度矩阵进行二值矩阵分解来获得样本 的 目 标 二 值 码，再 训 练 卷 积 神 经 网 络 拟合目标二 值 码，但 是 由 于 该 方 法 中 两 个 步 骤 之 间是相互割裂的，无法保证学到的二值编码 的 质量；深度神经网络哈希（Ｄｅｅｐ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ　Ｈａｓｈｉｎｇ，ＤＮＮＨ）［１２］、深 度 语 义 排 序 哈 希 （Ｄｅｅｐ　ＳｅｍａｎｔｉｃＲａｎｋｉｎｇ　Ｈａｓｈｉｎｇ，ＤＳＲＨ）［１３］、深度正则化相似度比较哈希（Ｄｅｅｐ　Ｒｅｇｕｌａｒｉｚｅｄ　Ｓｉｍｉｌａｒｉｔｙ　ＣｏｍｐａｒｉｓｏｎＨａｓｈｉｎｇ，ＤＲＳＣＨ）［１４］通过在汉明空间中设置锚点的方法，通过约束“与锚 点相似的样 本到锚点的距离要比与锚点不相似的样本到锚点的距离更近”的方式端到端地学习哈希函数，得到了判别能力更强的二值码；为了减小量化损失的影响，深度监督哈希（Ｄｅｅｐ　Ｓｕｐｅｒｖｉｓｅｄ　Ｈａｓｈｉｎｇ，ＤＳＨ）［２］、深度样本对监督哈希（Ｄｅｅｐ　Ｐａｉｒｗｉｓｅ　Ｓｕｐｅｒｖｉｓｅｄ　Ｈａｓｈｉｎｇ，ＤＰＳＨ）［１５］、哈希网络（ＨａｓｈＮｅｔ）［３］通过最小化／最大化相似／不相似样本对之间的距离端到端地学习具有强判别力的哈希 函 数，同 时 通 过 显 式 地 惩 罚 松 弛 后 的 实值特征与目标二值码之间的量化损失，进一步提升了二值码 的 检 索 精 度；有 监 督 语 义 保 持 深 度 哈 希（Ｓｕｐｅｒｖｉｓｅｄ　Ｓｅｍａｎｔｉｃ－ｐｒｅｓｅｒｖｉｎｇ　Ｄｅｅｐ　Ｈａｓｈｉｎｇ，ＳＳＤＨ）［１６］首先通过 ｓｉｇｍｏｉｄ激 活 函数将卷积网络中某一层的输出限定在０到１的范围内，并端到端地训练模型在尽可能减小量化误差的条件下，使用这一层的输出预测样本的标签，以此将语义信息编码到这一层的输出中，之后通过量化的方式获得真正的二值编码．尽管上述哈希方法通过对量化损失的显示约束，在近似近邻搜索任务上达到了很好的性能指标，但是由于方法中固有的松弛－量化步骤，仍然无法保证松弛后得到的实数值的最优解，在量化为二值后仍然是最优的．为了更好地解决这种量化带来的问题，一些近期的哈希学习方法提出直接在离散的汉明空间中进 行 优 化．其 中 离 散 图 哈 希 （Ｄｉｓｃｒｅｔｅ　ＧｒａｐｈＨａｓｈｉｎｇ，ＤＧＨ）［１７］和有监督 离 散 哈 希 （ＳｕｐｅｒｖｉｓｅｄＤｉｓｃｒｅｔｅ　Ｈａｓｈｉｎｇ，ＳＤＨ）［１８］通过逐个比特的优化，在不需要松弛的条件下，直接得到了具有判别力的二值码；深 度 离 散 监 督 哈 希 （Ｄｅｅｐ　Ｄｉｓｃｒｅｔｅ　ＳｕｐｅｒｖｉｓｅｄＨａｓｈｉｎｇ，ＤＤＳＨ）［１９］通过将离散优化与特征表示学习融合在一起，进一步提高了二值码的检索精度．但是 ＤＤＳＨ 方法只能在每个训练的小批量样本（ｍｉｎｉ－ｂａｔｃｈ）中得到最优的二值码，因此无法保证得到的二值码相对于整个数据集是最优的．为了解决这个问题，本文提出了一种新的离散优化算法，通过在整个训练集上进行优化，得到最优的二值码；并在最优二值码的基础上，训练深度卷积网络同时学习图像表示和相应的哈希函数．因此，与 ＤＤＳＨ 方法相比，２５１１ 计　　算　　机　　学　　报 ２０１９年２９；在线出版日期：２０１９－０３－２７．本课题得到国家“九七三”重点基础研究发展规划项目基金（２０１５ＣＢ３５１８０２）、国家自然科学基金（６１７７２５００）、中国科 学 院 前 沿 科 学 重 点 研 究 项 目 （ＱＹＺＤＪ－ＳＳＷ－ＪＳＣ００９）、中 国 科 学 院 青 年 创 新 促 进 会 （２０１５０８５）资 助．刘昊淼，博士研究生，主要研究方向为图像检索、可解释的物体识别模型．Ｅ－ｍａｉｌ：ｈａｏｍｉａｏ．ｌｉｕ＠ｖｉｐｌ．ｉｃｔ．ａｃ．ｃｎ．王瑞平，博士，研究员，中国计算机学会（ＣＣＦ）会员，主要研究领域为计算机视觉、模式识别、机器学习．山世光，博士，研究员，中国计算机学会（ＣＣＦ）会员，主要研究领域为计算机视觉、模式识别、机器学习．陈熙霖（通信作者），博士，研究员，中国计算机学会（ＣＣＦ）会士，主要研究领域为计算机视觉、多模式人机接口．Ｅ－ｍａｉｌ：ｘｌｃｈｅｎ＠ｉｃｔ．ａｃ．ｃｎ．基于离散优化的哈希编码学习方法刘昊淼　王瑞平　山世光　陈熙霖（中国科学院计算技术研究所智能信息处理重点实验室　北京　１００１９０）（中国科学院大学计算机科学与技术学院　北京　１０００４９）摘　要　哈希作为近似近邻搜索的一种主流方法，通过将样本索引为紧致的二值编码，在计算效率和存储上都非常高效．由于二值码的离散特性，以往的哈希方法往往需要将二值码松弛为实数值才能高效地进行优化，因此在优化完成后重新将实数值的结果量化为二值时难免会由于二值的汉明空间与实数值的欧氏空间之间的差异而遇到性能上的损失问题．为了更好地解决量化损失的问题，本文提出了一种深度离散优化哈希（Ｄｅｅｐ　Ｄｉｓｃｒｅｔｅ　Ｏｐｔｉｍｉｚａ－ｔｉｏｎ　Ｈａｓｈｉｎｇ，ＤＤＯＨ）方法．首先，设计了一种新的离散优化算法，通过直接在二值的汉明空间中对二值码进行优化，得到具有强判别性的二值编码．然后，训练卷积神经网络模型拟合上述二值码，得到用于编码的哈希函数．在ＣＩＦＡＲ－１０和ＩｍａｇｅＮｅｔ－１００两个常用的评测数据集上的实验显示，本文提出的方法在 ＣＩＦＡＲ－１０数据库上与目前最好的方法达到了同样的性能，在ＩｍａｇｅＮｅｔ－１００数据库上的平均准确率指标与已有方法相比提升了约２．２％，证明了该方法的有效性．关键词　近似近邻搜索；高维特征索引；哈希学习；离散优化；卷积神经网络中图法分类号ＴＰ３１１　　　ＤＯＩ号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０１９．０１１４９Ｌｅａｒｎｉｎｇ　ｔｏ　Ｈａｓｈ　ｗｉｔｈ　Ｄｉｓｃｒｅｔｅ　ＯｐｔｉｍｉｚａｔｉｏｎＬＩＵ　Ｈａｏ－Ｍｉａｏ　ＷＡＮＧ　Ｒｕｉ－Ｐｉｎｇ　ＳＨＡＮ　Ｓｈｉ－Ｇｕａｎｇ　Ｘｉｌｉｎ　Ｃｈｅｎ（Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１００１９０）（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１０００４９）Ａｂｓｔｒａｃｔ　Ｉｎ　ｒｅｃｅｎｔ　ｙｅａｒｓ，ｂｉｌｌｉｏｎｓ　ｏｆ　ｉｍａｇｅｓ　ａｒｅ　ｕｐｌｏａｄｅｄ　ｔｏ　ｔｈｅ　Ｉｎｔｅｒｎｅｔ　ｅｖｅｒｙ　ｄａｙ，ｍａｋｉｎｇ　ｉｔｅｘｔｒｅｍｅｌｙ　ｄｉｆｆｉｃｕｌｔ　ｔｏ　ｆｉｎｄ　ａｎ　ｉｎｔｅｒｅｓｔｅｄ　ｉｍａｇｅ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ａ　ｕｓｅｒ’ｓ　ｄｅｍａｎｄ．Ｔｈｉｓ　ｐａｐｅｒ　ａｄｄｒｅｓｓｅｓｔｈｅ　ｃｏｎｔｅｎｔ－ｂａｓｅｄ　ｉｍａｇｅ　ｒｅｔｒｉｅｖａｌ　ｔａｓｋ，ｗｈｉｃｈ　ａｉｍｓ　ａｔ　ｌｏｏｋｉｎｇ　ｆｏｒ　ｄａｔａｂａｓｅ　ｉｍａｇｅｓ　ｔｈａｔ　ａｒｅ　ｓｉｍｉｌａｒｔｏ　ｔｈｅ　ｇｉｖｅｎ　ｑｕｅｒｙ　ｉｍａｇｅ．Ｈｏｗｅｖｅｒ，ｄｕｅ　ｔｏ　ｔｈｅ　ｈｕｇｅ　ｓｉｚｅ　ｏｆ　ｍｏｄｅｒｎ　ｄａｔａｓｅｔｓ，ｅｘａｃｔ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓｅａｒｃｈ　ｍｅｔｈｏｄ　ｃａｎｎｏｔ　ｐｒｏｄｕｃｅ　ｒｅｔｒｉｅｖａｌ　ｒｅｓｕｌｔｓ　ｉｎ　ａｃｃｅｐｔａｂｌｅ　ｔｉｍｅ．Ｔｈｅｒｅｆｏｒｅ，ａｐｐｒｏｘｉｍａｔｅｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｓｅａｒｃｈ　ｍｅｔｈｏｄｓ　ａｒｅ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｓａｃｒｉｆｉｃｅ　ａｃｃｕｒａｃｙ　ｆｏｒ　ａｃｃｅｐｔａｂｌｅ　ｒｅｔｒｉｅｖａｌ　ｔｉｍｅ．Ａｓ　ａ　ｍａｉｎｓｔｒｅａｍ　ａｐｐｒｏｘｉｍａｔｅ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ （ＡＮＮ）ｓｅａｒｃｈ　ｍｅｔｈｏｄ，ｈａｓｈｉｎｇ　ｐｒｏｊｅｃｔｓ　ｔｈｅｏｒｉｇｉｎａｌ　ｆｅａｔｕｒｅ　ｖｅｃｔｏｒｓ　ｏｆ　ｓａｍｐｌｅｓ　ｉｎｔｏ　ｖｅｒｙ　ｃｏｍｐａｃｔ　ｂｉｎａｒｙ　ｃｏｄｅｓ，ａｎｄ　ｔｈｕｓ　ｉｓ　ｖｅｒｙ　ｅｆｆｉｃｉｅｎｔ　ｉｎｂｏｔｈ　ｃｏｍｐｕｔａｔｉｏｎ　ａｎｄ　ｓｔｏｒａｇｅ．Ａｓ　ａ　ｒｅｓｕｌｔ，ｈａｓｈｉｎｇ　ｍｅｔｈｏｄｓ　ｈａｖｅ　ｒｅｃｅｉｖｅｄ　ｍｏｒｅ　ａｎｄ　ｍｏｒｅｒｅｓｅａｒｃｈ　ａｔｔｅｎｔｉｏｎ　ｏｖｅｒ　ｔｈｅ　ｐａｓｔ　ｔｗｅｎｔｙ　ｙｅａｒｓ．Ｈｏｗｅｖｅｒ，ｄｕｅ　ｔｏ　ｔｈｅ　ｄｉｓｃｒｅｔｅ　ｎａｔｕｒｅ　ｏｆ　ｂｉｎａｒｙ　ｃｏｄｅｓ，ｄｉｒｅｃｔｌｙ　ｏｐｔｉｍｉｚｉｎｇ　ｔｈｅ　ｂｉｎａｒｙ　ｃｏｄｅｓ　ｉｓ　ａｎ　ＮＰ－ｈａｒｄ　ｐｒｏｂｌｅｍ　ａｎｄ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎ　ｔｉｍｅ　ｒｅｑｕｉｒｅｄ　ｆｏｒｏｂｔａｉｎｉｎｇ　ｔｈｅ　ｇｌｏｂａｌ　ｏｐｔｉｍｕｍ　ｗｏｕｌｄ　ｂｅ　ｕｎａｃｃｅｐｔａｂｌｅ．Ｔｏ　ｄｅａｌ　ｗｉｔｈ　ｔｈｉｓ　ｐｒｏｂｌｅｍ，ｅｘｉｓｔｉｎｇ　ｈａｓｈｉｎｇｍｅｔｈｏｄｓ　ｃａｎ　ｏｎｌｙ　ｐｅｒｆｏｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｅｆｆｉｃｉｅｎｔｌｙ　ｂｙ　ｒｅｌａｘｉｎｇ　ｔｈｅ　ｂｉｎａｒｙ　ｃｏｄｅｓ　ｔｏ　ｒｅａｌ　ｖａｌｕｅｓ，ａｎｄ的二值码判别力更强，在检索时可以达到更高的精度．３　方　法为了进一步缓解松弛－量化步骤对哈希学习方法的负面影响，提出了一种新的离散优化算法，直接在二值的汉明空间中进行优化，提升初始二值码的判别能力．为了在得到优化之后的二值码基础上得到相应的用于编码的哈希函数，训练了一个深度卷积神经网络同时学习更适配于数据的特征表示并对二值码进行拟合，整个方法的流程示意如图１所示．下面将分别详细介绍本文方法中的三个关键步骤，即二值码初始化、离散二值码优化、哈希函数学习．３．１　形式化令Ω 表示 ＲＧＢ 彩色图像空间，ＳｔｒΩ 表示训练图像构成的集合，哈希学习方法的目标是在训练集Ｓｔｒ上学习一个从图像空间Ω 到Ｋ 比特二值码的变换ｆ：Ω→ ｛０，１｝Ｋ，使得相似的图像在变换之后的二值码也相似，不相似的图像的二值码也不相似．对于深度 哈 希 方 法，上 述 变 换 可 以 进 一 步 分 解 为ｆ（Ｘ）＝ｈ（ψ（Ｘ）），其中Ｘ∈Ω 表示一张 ＲＧＢ彩色图像，ψ：Ω→Ｒｄ表示使用深度卷积网络提取ｄ 维图像特征的过程，ｈ：Ｒｄ→ ｛０，１｝Ｋ表示将深度特征变换为二值码的操作．具体来说，ｈ（ψ（Ｘ））＝Ｉ［ＷＴψ（Ｘ）＋ｂ＞０］，其中 Ｗ ∈Ｒｄ×Ｋ表示哈希函数 的 权 重 矩 阵，ｂ∈ＲＫ表示相应的偏置项，Ｉ［条件］代表指示函数，当括号中的条件为真时取值为１，否则取值为０．为了便于表示，在下文中将使用 Ｂ 表示所有训练图像的二值码，Ｂ（ｔ）ｉ表示第ｉ个样本在第ｔ 次离散优化之后对应的二值码，Ｂ（ｔ）ｉ（ｋ）表示相应二值码的第ｋ个比特．在本文方法中，需要学习 Ｗ 和ｂ 中参数的值，同时也要对深度卷积网络中特征提取部分ψ的参数值进行学习（如卷积神经网络中卷积核的权重、全连接层的变换参数等）．３．２　二值码初始化一种最简单直接的获得初始二值码Ｂ（０）ｉ的方法是通过随机采样的方式初始化二值码，完全不考虑图像特征的分布情况：Ｂ（０）ｉ＝Ｉ［ｒａｎｄｎ（Ｋ）＞０］ （１）其中ｒａｎｄｎ（ｋ）表示从标准正态分布中随机采样 Ｋ次．该方法通过直接对这 Ｋ 个采样结果分别进行量化得到初始的Ｋ 比特二值码．上述方法虽然可以快速地得到初始二值码，但是由于没有考虑到数据的真实分布情况，因此可能会给之后的优化步骤带来一些困难．为了解决这个问题，本文进一步考虑基于数据的真实分布的初始化方法．通常来说，在ＩｍａｇｅＮｅｔ的 １０００ 类 物体识别任务［２０］上预训练的深度卷积网络中，最后一层的输出对应的是图像属于相应的１０００个类别的概率，而倒数第二层的输出对应的则是更加通用的图像表示．大量已有工作［２１－２２］表明，在ＩｍａｇｅＮｅｔ上预训练的深度卷积网络倒数第二层的特征可以应用于各种各样的计算机视觉任务．因此，一种可行的得到初始的二值码方法为：对于训练集中的第ｉ张图像Ｘｉ∈Ｓｔｒ，本文方法首先将图片作为输入送入预训练的深度卷积神经网络模型，并使用网络倒数第二层的输出作为训练图像的特征ψ（Ｘｉ）．相应地，在该特征的基础上考虑两种初始方法：第一，通过对特征进行随机线性变换得到初始的二值码Ｂ（０）ｉ：ｍ＝１／ Ｓｔｒ×∑Ｘｉ∈Ｓｔｒψ（Ｘｉ） （２）Ｂ（０）ｉ＝Ｉ［ＷＴｒａｎｄ（ψ（Ｘｉ）－ｍ）＞０］ （３）其中 ｍ 表示所有训练数据的平均特征，用于将样本的特征平移到特征空间的原点附近；· 表示集合的元素个数；Ｗｒａｎｄ∈Ｒｄ×Ｋ表示一个ｄ×Ｋ 维的随机矩阵，该矩阵中的每一个元素都是从标准正态分布中随机采样得到的；第二，通过使用主成分分析的方法对特征进行降维，并以此获得初始的二值码：Ｂ（０）ｉ＝Ｉ［ＷＴｐｃａ（ψ（Ｘｉ）－ｍ）＞０］ （４）其中ｍ 为式（２）中定义的样本平均特征，Ｗｐｃａ∈Ｒｄ×Ｋ表示训练数据的前Ｋ 个主成分方向．讨论：上述三种初始化方法中，第一种完全没有考虑数据的分布情况，因此该方法得到的初始二值码无法保持样本间的相似度关系，但是计算十分高效；第二种做法与局部敏感哈希［４］相似，可以在一定程度上保持图像原始特征之间的相似度关系，而且计算上也比较高效；第三种做法利用数据分布的主方向，可以得到冗余度较小的初始二值码，但是由于需要计算主成分分析，因此在计算效率上低于前两种方法，并且当训练集规模增大时，计算量和内存需求也会随之增大．综 上所述，上 述 三种初始化方法中，前两种即使在训练数据规模非常大的情况下，依然可以很高效地得到初始的二值码．３．３　离散二值码优化初始二值码Ｂ（０）ｉ的判别力较弱，因此如果直接将其用于近似近邻搜索任务将很难达到令人满意的５期 刘昊淼等：基于离散优化的哈希编码学习方法３５１１码的判别力，本文提出一种新的离散二值码优化方法，直接在汉明空间中学习最优的二值码．具体来说，对于拥有类别标签的样本，在检索任务中，同类的图像应该具有相似的二值码，而不同类的图像的二值码也应该不同．令ｙｉ∈｛１，２，３，…，Ｃ｝表示第ｉ张训练图像所属的类别标号，对于相应的训练图像 Ｘｉ，优化的目标是减小第ｉ张图像的二值码与同类图像的二值码之间的距离，同时增大第ｉ张图像与其他类图像的二值码之间的距离．在本文方法中，各个比特相互独立，因此不失一般性的，对于第ｋ个比特，相应的优化目标为Ｌｉ＝１∑ｊＩ［ｙｊ＝ｙｉ（ ］）×∑ｙｊ＝ｙｉ（Ｂ（０）ｉ（ｋ）－Ｂ（０）ｊ（ｋ））２－１∑ｊＩ［ｙｊ≠ｙｉ（ ］）×∑ｙｊ≠ｙｉ（Ｂ（０）ｉ（ｋ）－Ｂ（０）ｊ（ｋ））２（５）其中第一项为归一化的类内差异，第二项为归一化的类间差异．值得注意的是，对于二值码来说，其取值只有两种可能的结果，因此式（５）可以改写为　Ｂ（０）ｉ（ｋ）＝０：Ｌｉ＝∑ｙｊ＝ｙｉＢ（０）ｊ（ｋ）－λ∑ｙｊ≠ｙｉＢ（０）ｊ（ｋ），　Ｂ（０）ｉ（ｋ）＝１：Ｌｉ＝∑ｙｊ＝ｙｉＢ（０）ｊ（ｋ）－λ∑ｙｊ≠ｙｉＢ（０）ｊ（ｋ）（６）其中λ＝∑ｊＩ［ｙｊ＝ｙｉ］∑ｊＩ［ｙｊ≠ｙｉ］，　 表示取反操作．为了使式（６）取得最小值，分情况进行讨论，当Ｂ（０）ｉ（ｋ）＝０时，不难证明当∑ｙｊ＝ｙｉＢ（０）ｊ（ｋ）－λ∑ｙｊ≠ｙｉＢ（０）ｊ（ｋ）＜０时，维持Ｂ（０）ｉ（ｋ）＝０可以使式（６）取得最小值；反之，当∑ｙｊ＝ｙｉＢ（０）ｊ（ｋ）－λ∑ｙｊ≠ｙｉＢ（０）ｊ（ｋ）＞０时，翻转Ｂ（０）ｉ（ｋ）的值可以使式（６）取得最小值．具体的证明见附录１．同理 可 得，当 Ｂ（０）ｉ（ｋ）＝１ 且∑ｙｊ＝ｙｉＢ（０）ｊ（ｋ）－λ∑ｙｊ≠ｙｉＢ（０）ｊ（ｋ）＜０时，维持Ｂ（０）ｉ（ｋ）的值可以使式（６）取得最小值；反之，当∑ｙｊ＝ｙｉＢ（０）ｊ（ｋ）－λ∑ｙｊ≠ｙｉＢ（０）ｊ（ｋ）＞０时，翻转Ｂ（０）ｉ（ｋ）的值可以取得最小值．因此，对所有比特按照上述方式进行更新，即可降低损失的值．通过迭代地更新，即可得到具有强判别力的二值码，该过程的总体更新算法详见算法 １．由于二值码优化是一个 ＮＰ难的问题，目前已有的理论无法保证本算法可以收敛到全局最小值．因此，本文将在第４节中，通过大量实验验证该算法在多种初始条件下的收敛性及有效性．算法１．　离散二值码优化算法．输入：训练数据的初始二值码矩阵 Ｂ（０），训练数据标签ｙ，优化迭代次数ｎ输出：优化后的二值码矩阵Ｂ（ｎ）１．ｆｏｒ　ｉｔｅｒ＝１：ｎ２． ｆｏｒ　ｋ＝１：Ｋ３． Ｃ０＝∑ｉＢ（ｉｔｅｒ－１）ｉ（ｋ）／／训练集所有样本在第ｋ个比特取０的个数４． Ｃ１＝∑ｉＢ（ｉｔｅｒ－１）ｉ（ｋ）／／训练集所有样本在第ｋ个比特取１的个数５． ｆｏｒ　ｃ＝１：Ｃ６． Ｓｃ，０＝∑ｙｉ＝ｃＢ（ｉｔｅｒ－１）ｉ（ｋ）／／第ｃ类样本在第ｋ个比特上取０的个数７． Ｓｃ，１＝∑ｙｉ＝ｃＢ（ｉｔｅｒ－１）ｉ（ｋ）／／第ｃ类样本在第ｋ 个比特上取１的个数８． Ｄ０＝Ｃ０－Ｓｃ，０ ／／除第ｃ类外，其他所有类样本在第ｋ个比特上取０的个数９． Ｄ１＝Ｃ１－Ｓｃ，１ ／／除第ｃ类外，其他所有类样本在第ｋ个比特上取１的个数１０． ｇ０＝Ｓｃ，１－λＤ１ ／／第ｃ类在第ｋ 个比特上取值为０的样本的损失１１． ｇ１＝Ｓｃ，０－λＤ０ ／／第ｃ类在第ｋ 个比特上取值为１的样本的损失１２． ｆｏｒ　ｙｉ＝＝ｃ１３． ｉｆ　Ｂ（ｉｔｅｒ－１）ｉ（ｋ）１４． Ｂ（ｉｔｅｒ－１）ｉ（ｋ）＝ （ｇ１＞０）１５． ｅｌｓｅ１６． Ｂ（ｉｔｅｒ－１）ｉ（ｋ）＝（ｇ０＞０）１７．ｒｅｔｕｒｎ　Ｂ（ｎ）由于本文方法在进行二值码优化的时候，只需要考虑二值码的判别性，而不需要像大多数已有的深度哈希方法一样考虑量化损失的问题，因此可以避免在判别性损失和量化损失之间进行权衡，从而相比于已有的哈希方法，本文方法可以更加专注于二值码的判别性，从而可以获得具有更强判别能力的二值码．３．４　哈希函数学习上述离散二值码优化过程虽然可以在训练集上得到具有强判别力的二值码，但是无法对训练集之外的样本进行编码．为了得到用于编码的哈希函数，本文方法通过训练深度卷积神经网络，在训练集上拟合优化得到的二值码．因此，对于第ｋ 个比特，优化的目标是使深度卷积网络输出的二值码尽可能地接近优化得到的二值码：ｍｉｎ∑ｉＥ（ｈ（ψ（Ｘｉ）），Ｂ（ｎ）ｉ） （７）其中Ｅ（·，·）是对两个向量之间差异的度量，可以４５１１ 计　　算　　机　　学　　报 ２０１９年ｇｅ损失、Ｓｉｇｍｏｉｄ交叉熵损失等方式定义．本文中采用Ｓｉｇｍｏｉｄ交叉熵的形式，对于第ｉ个训练样本，损失函数的具体定义为　Ｅ（ｈ（ψ（Ｘｉ）），Ｂ（ｎ）ｉ）＝　　－∑ｋ［Ｂ（ｎ）ｉ（ｋ）×ｌｏｇ（σ（ＷＴｋψ（Ｘｉ）＋ｂｋ））＋　　（１－Ｂ（ｎ）ｉ（ｋ））×ｌｏｇ（１－σ（ＷＴｋψ（Ｘｉ）＋ｂｋ））］（８）其中σ（ａ）＝１／（１＋ｅｘｐ（－ａ））是 Ｓｉｇｍｏｉｄ函数，Ｗｋ表示矩阵Ｗ 的第ｋ 列，ｂｋ表示向量ｂ 的第ｋ 个元素．为了便于表示，令ｈｉ（ｋ）＝σ（ＷＴｋψ（Ｘｉ）＋ｂｋ），上述损失函数对ｈｉ（ｋ）是可导的，其导数定义为Ｅ／ｈｉ（ｋ）＝σ（ＷＴｋψ（Ｘｉ）＋ｂｋ）－１，Ｂ（ｎ）ｉ（ｋ）＝１，Ｅ／ｈｉ（ｋ）＝σ（ＷＴｋψ（Ｘｉ）＋ｂｋ），Ｂ（ｎ）ｉ（ｋ）＝０ （９）因此，利用链式法则，该模型可以通过标准的反向传播算法进行优化．模型训练结束后，对于样本 Ｘ，可以通过对卷积网络输出进行量化的方式，得到样本的二值码：Ｂ（ｋ）＝０．５×ｓｉｇｎ（ＷＴｋψ（Ｘ）＋ｂｋ）＋０．５ （１０）其中ｓｉｇｎ（·）表示符号函数，当 自 变 量 的 值 大 于 ０时，函数值为１，否则函数值为－１．４　实验验证在本节中，通过在两个常用的图像检索数据集上进行对比实验，验证本文方法相对于已有方法的优越性．另外，通过大量的消融实验和模块测试，验证本文方法中采用的各个模块的有效性，并对参数的敏感性进行分析．４．１　实验环境和数据集实验环境．本次实验在一台 ＧＰＵ 服务器上进行，离散二值码优化部分使用 ＭＡＴＬＡＢ，二值码拟合部分使用的深度学习平台为 Ｃａｆｆｅ，基于 ＣＵＤＡ和ｃｕｄｎｎ进行 ＧＰＵ 加速，实际实验中只使用一块ＧＰＵ 进行实验，机器的配置见表１．表１　实验机器配置信息操作系统 Ｕｂｕｎｔｕ　１６．０４．５ＬＴＳＣＰＵＩｎｔｅｌ（Ｒ）Ｘｅｏｎ（Ｒ）ＣＰＵＥ５－２６２０ｖ３＠２．４０ＧＨｚ内存 ３２ＧＢＧＰＵ　 ４×Ｔｉｔａｎ　Ｘ显卡驱动版本 ３９６．５４ＣＵＤＡ 版本 ９．２ｃｕｄｎｎ版本 ７．０数据集．为了和已有哈希学习方法进行公平的对比，实验过程中沿用 ＣＩＦＡＲ－１０［２３］和ＩｍａｇｅＮｅｔ－１００［３］两个已有方法中常用的图像检索评测数据集来测试本文 方 法 的 有 效 性．ＣＩＦＡＲ－１０：该 数 据 库 包 含６０　０００张分辨率为３２×３２的彩色图像．这些图像属于１０个互斥的类别，其中每类６０００张图像．在本次实验中，使用 ＣＩＦＡＲ－１０数据库标准的训练、测试数据划分，使用５００００张图像（每类５０００张）训练模型并作为检索的数据库，１０　０００张图像（每类１０００张）作为查询图像．ＩｍａｇｅＮｅｔ－１００：该数据库是ＩｍａｇｅＮｅｔ物体识别任务的一个子集，包含１００类物体．其中来自ＩｍａｇｅＮｅｔ训练集的 １２８　５０３张图像作为检索的数据库，其中每类１３０张图像（共１３　０００张）用于训练模型，来 自 ＩｍａｇｅＮｅｔ校 验 集 的 每 类 ５０ 张 图 像（共５０００张）作为测试时使用的查询图像．由于目前只有极少数方法在更大规模的数 据集上进 行了评测，为了保证本文汇报结果的准确性，减小复现对比方法中可能的错误对对比方法性能的不利影响，本文仅在上述两个数据库上进行评测．码长．由于ＣＩＦＡＲ－１０数据库相对比较简单，本文中使用已 有 工作中常用的评测 协 议［２，１６］，在１２、２４、３２、４８比特四个不同的码长上进行模型的评测．对于ＩｍａｇｅＮｅｔ－１００，本文沿用文献［３］的评测方式，在１６、３２、４８、６４四个码长上进行测试．评测方法及指标．在上述两个数据集上，使用查 询 数 据 对 数 据 库 进 行 检 索，当 返 回 结 果 与 查询图像来自同一个类别时，认定为一个正确的检索结果．通 过 使 用 检 索 的 查 准 率 （ｐｒｅｃｉｓｉｏｎ）、召 回 率（ｒｅｃａｌｌ）、平均准确率（ｍＡＰ）、汉明距离小于等于２的样本的准确率作为指标评价各个方法的性能并进行对比．特别的，对于ＩｍａｇｅＮｅｔ－１００数据库，由于在数据库中一个类别只有约１３００张图像，因此本文沿用文献［３］的评测方式，使用前１０００个返回结果的平均准确率（ｍＡＰ）作为评测的指标．４．２　方法实现细节网络结构．对于大规模图像检索任务来说，编码速度是一个重要的指标．考虑到编码速度与检索性能的权衡，本文采用 ＡｌｅｘＮｅｔ［２４］的网络结构进行哈希学习．为了减少模型的可训练参数，降低过拟合的风险，本文方法在ＩｍａｇｅＮｅｔ物 体识别任 务上预训练的网络参数的基础上进行参数微调．具体来说，基于深度卷积网络的哈希函数中的参数 Ｗ 和ｂ 是预训练模型中所没有的，因此需要从随机初始化开始从头学习；另一方面，ψ表示卷积网络中的卷积、池化等操作，其中 的参数 已经在ＩｍａｇｅＮｅｔ物体识别任务上进行了训练，因此能够从图像中提取表示能力较强的特征，在学习哈希函数的时候只需根据５期 刘昊淼等：基于离散优化的哈希编码学习方法５５１１相应的数据进行微调．参数设置．对于对比方法，本文使用原作者在各自论文中建议的结果设置参数．对于本文提出的 ＤＤＯＨ方法，离散二值码优化时 的迭代次数ｎ 设置为 １０次．训练卷积网络时，新加入的哈希层的学习率设置为０．００３，前面在ＩｍａｇｅＮｅｔ识别任务上预训练过的层学习率设置为０．０００３．在 ＣＩＦＡＲ－１０数据库上，因为训练数据量比较大，且训练数据与ＩｍａｇｅＮｅｔ预训练的数据差异较大，因此需要训练的时间也较长，共训练５０　０００次，其中在２５　０００次的时候将学习率降低到原来的１／１０．在ＩｍａｇｅＮｅｔ－１００数据库上，由于训练数据较少，为了避免过拟合，总共训练 １０００次，其中在５００次的时候将学习率降低到初始学习率的１／１０．此外，在两个数据库上，模型的权重衰减系数均设置为０．０００５，训练时使用的小批量大小为２５６．在训练的过程中，所有输入图像首先缩放为２５６×２５６的尺寸，之后从中随机裁剪出２２７×２２７的图像块作为模型的输入．在测试阶段，同样首先将输入图像缩放为２５６×２５６，然后选取位于图像中心的大小为２２７×２２７的图像块作为输入，通过对网络前向计算后，对输出进行量化得到最终的二值码．４．３　与已有方法对比为了验证本文方法的有效性，每次测试均与已有的哈希方法进行了对比．具体来说，对比的方法包括局部敏感哈希（ＬＳＨ）［４］、迭代量化（ＩＴＱ）［１］、基于典型相关分析的迭代量化（ＣＣＡ－ＩＴＱ）［１］、有监督离散哈希（ＳＤＨ）［１８］、卷积神经网络哈希（ＣＮＮＨ）［１１］、深度 卷 积 网 络 哈 希 （ＤＮＮＨ）［１２］、深 度 监 督 哈 希（ＤＳＨ）［２］、哈希网络（ＨａｓｈＮｅｔ）［３］、有监督语义保持深度哈希（ＳＳＤＨ）［１６］．对比结果见表２、图２和图３．在 ＣＩＦＡＲ－１０数据库上（表２左侧和图２），本文提出的方法在平均准确率、精度－召回率曲线、汉明距离小于等于２的样本的精度三项指标上都达到了和现有最好的方法一样好的性能指标．特别是在精度－召回率曲线上，即使在召回率接近１的情况下，本文的方法仍然可以保持非常高的精度，这说明本文的方法中，同类的样本之间非常紧凑，而且每一类的编码都有很强的差异．在ＩｍａｇｅＮｅｔ－１００数据库上，本文提出的方法在所有指标上都显著超越了已有的方法，这证明了该方法的优越性．表２　与现有哈希学习方法在平均准确率指标（ｍＡＰ）上的对比（本文方法（ＤＤＯＨ）的结果见表中最后一行，对比方法的最好结果用下划线标出）方法ＣＩＦＡＲ－１０（ｍＡＰ）１２－ｂｉｔ　 ２４－ｂｉｔ　 ３２－ｂｉｔ　 ４８－ｂｉｔＩｍａｇｅＮｅｔ－１００（ｍＡＰ＠１０００）１６－ｂｉｔ　 ３２－ｂｉｔ　 ４８－ｂｉｔ　 ６４－ｂｉｔＬＳＨ［４］０．１２５　 ０．１５０　 ０．１６９　 ０．１８６　 ０．０８０　 ０．１６０　 ０．２２４　 ０．２７４ＩＴＱ［１］０．２３０　 ０．２４１　 ０．２５３　 ０．２５９　 ０．３０７　 ０．４５７　 ０．５１６　 ０．５５３ＣＣＡ－ＩＴＱ［１］０．５７３　 ０．６１４　 ０．６２５　 ０．６３４　 ０．３２１　 ０．４９４　 ０．５８９　 ０．６５０ＳＤＨ［１８］０．２０５　 ０．６３７　 ０．６３２　 ０．６６０　 ０．４８１　 ０．５６７　 ０．６００　 ０．６１７ＣＮＮＨ［１１］０．８５６　 ０．８６０　 ０．８６３　 ０．８６４　 ０．２８１　 ０．４５０　 ０．５２５　 ０．５５４ＤＮＮＨ［１２］０．６９４　 ０．８２１　 ０．８２５　 ０．８３５　 ０．２９０　 ０．４６１　 ０．５３０　 ０．５６５ＤＳＨ［２］０．９２０　 ０．９２９　 ０．９３３　 ０．９３５　 ０．５５８　 ０．６３２　 ０．６５０　 ０．６６３ＨａｓｈＮｅｔ［３］０．９４３　 ０．９５０　 ０．９５２　 ０．９５３　 ０．５０６　 ０．６３１　 ０．６６３　 ０．６８４ＳＳＤＨ［１６］０．９２７　 ０．９４２　 ０．９４５　 ０．９４７　 ０．６２１　 ０．６８０　 ０．６８８　 ０．７００ＤＤＯＨ　 ０．９４９　 ０．９４８　 ０．９４９　 ０．９５０　 ０．６４７　 ０．６９７　 ０．７１２　 ０．７２０图 ２　在 ＣＩＦＡＲ－１０数据库上进行测试时得到的４８比特模型的精度－召回率（Ｐｒｅｃｉｓｉｏｎ－Ｒｅｃａｌｌ，ＰＲ）曲线（左图）和不同码长模型的汉明距离小于等于２的样本的精度曲线（右图）６５１１ 计　　算　　机　　学　　报 ２０１９年