基于稀疏自编码的无监督图像哈希算法

文献标志码：+

2019年5月May 2019中图分类号：TP391基于稀疏自编码的无监督图像哈希算法代亚兰，何朗，黄樟灿(武汉理工大学理学院，武汉430070)摘要：哈希方法因快速及低内存的特点广泛应用于大规模图像检索中，但在哈希函数构造过程中对数据稀疏性 缺乏研究$为此，提出一种无监督稀疏自编码的图像哈希算法$在哈希函数的学习过程中加入稀疏构造过程和自 动编码器，利用稀疏自编码的KL差异对哈希码进行稀疏约束，以增强局部保持映射过程中的判别性。在CIPAR-10

数据集和YouTube Faces数据集上进行实验，结果表明，该算法平均准确率优于DH算法$关键词：哈希算法；图像检索；稀疏自编码；无监督；KL差异中文引用格式：代亚兰，何朗，黄樟灿.基于稀疏自编码的无监督图像哈希算法:J).计算机工程，2019，45 (5 ) ：222- 225，236.英文弓丨 用格式：DA【Yalan，HE Lang，HUANG Zhangcan. Unsupervied image hashing algorithm based on sparse-Lutoencoder

(J］. Computer Engineering，2019，45 (5) :222-225，236.Unsupervised Image Hashing Algorithm Based on Sparse-autoencoderDA【Yalan & HE Lang & HUANG Zhangcan(School of Science，Wuhan Unperspy of Technology & Wuhan 430070 & China)+ Abstract] The hash method it widely used in large-scale image retrieval due to its fast and low memory characteristict， but p lacks research on data sparsity in the construction of hash functions. To this end，an unsupervised sparse self­encoding image hash algorithm it proposed. In the learning process of the hash function，a sparse construction process and an automatic encoder are added，and the hash code it sparsely constrained by the Kullback-Leiblr( KL) divergence of the sparse-Luto encoder to enhance the discriminability in the local preservation mapping process. Experimentt on the CIPAR- 10 datasets and YouTube Faces datasets show that the average accuracy of the algorithm is better than the DH algorithm.+ Key words] hash algorithm ； image retrieval； sparse-autoencoder ； unsupervised ； Kullback-Leibler( KL) divergence DOI： 10. 19678/j. issn. 1000-3428.00506530概述高维数据处理广泛应用于模式识别、数据挖掘 等领域［1］。随着互联网技术的发展，图像的数量呈 现大规模增长$因此，研究从高维数据中选择具有 代表性的图像特征子集和消除不相关特征具有重要 意义$针对在监督哈希的实际应用中数据集过大、可 用标签数量不足等问题［2-］，国内外学者提出无监督 哈希算法$当原始相邻数据映射为哈希码时，使相 邻数据映射为相似哈希码的概率大，不相邻的数据 映射为相邻的哈希概率小，同时在大数据集中寻找 相邻元素的问题转化为在小数据集中寻找相邻元素 的问题，且减小了计算负荷$哈希编码将特征由连 续值域映射到离散值域$因此，哈希函数的优化过

deterministie Polynomial，NP)［4］，但如何构造一个有

效且精度高的哈希函数是面临的难题$为弥补数据稀疏结构的不足，本文提出一种基

于稀疏自编码的图像哈希函数学习算法$通过KL (KullUack-Leiblar)差异［5］对哈希码进行稀疏约束以 增强局部保持映射过程中的判别性，同时降低哈希 码在自编码器中带来的量化误差$1相关知识1.1自编码器自动编码器由编码器和解码器2个部分组 成［6］$在编码器部分，将无标签样本作为列向量％ 的输入，则自编码器的隐藏层激活函数为：y = A( 9% + bias)

(1)程是一个多项式复杂程度的非确定性问题(Non-

基金项目：国家自然科学基金(61672391) $其中，(是一个大于-1小于1的非线性函数，例如 tanh或sigmoid函数，9为自编码器编码部分的权重，作者简介：代亚兰(1992―)，女，硕士研究生，主研方向为图像检索、模式识别；何 朗，副教授、博士；黄樟灿，教授、博士 收稿日期：2018-03-07

修回日期：2018-05-19 E-mail：418095604@ qq. com第 45 卷 第 5 期代亚兰，何 朗，黄樟灿：基于稀疏自编码的无监督图像哈希算法2 23:为自编码器的偏置参数，且和％具有同样维度的 列向量。在解码部分，对自编码器的隐藏层激活函数

y进行重构％'，并使得％'与％尽可能相似，有：%，=(( 9'y + bias'\" (2)其中，9,为自编码器解码部分的权重，bias'为自编码 器解码部分的偏置参数，9满足9, =9t。目标函数

采用平均重构误差D可表示为：min D=|| % - %' || 2

(3 )D越小,输出与输入值越相近，编码器对%进行 重构效果就越好，且在编码过程中保留样本的主要

信息及特征$1.2稀疏编码通过自编码器，哈希函数能够解决在优化求解

时难度较大的问题，但自编码器只能保存样本的特

征信息，不能实现图像检索$稀疏约束在自动编码

器上能使其不仅学到样本的特征表达，还能学到复

制的非线性函数$稀疏性约束是指在激活函数为

sigmoid函数时，当神经元的输出接近1时认为它被 激活，而输出接近0时认为它被抑制，使得神经元多 数时间处于抑制状态(6)$同理，若假设的神经元的 激活函数是tanh函数，当神经元输出为-1时，神经 元被抑制$为使大部分神经元处于被抑制状态，数据的数 据集X将分解为多个基元的线性组合，可表示为：.='(4)

j j 1其中,x %尺\"，在一般情况下k远远大于1,其基组合才

能更容易学到输入数据内在的结构和特征。在常见

算法中，如PCA算法，由于基向量数量少，因此分解后 可以得到唯一确定的系数a$在稀疏编码中，基向量 数k远远大于目标向量维数1,其分解系数a不能唯

一确定，以达到约束的目的。稀疏编码算法的来源便 是对系数a进行约束,其编码函数表达式为：min ' | . -' %； # | 2 +A'S (%；)

(5)%!F(j i 01

j 0 1

j 0 1前一项表达式为输入样本向量和经过自编码器 后的重构向量之间的误差,最小的误差即目标函数, 该项使即算法获得一个线性拟合式$后一项是惩罚

项，即稀疏项$ S( %jF )作为分解稀疏的稀疏惩罚函 数，在大于0时，对其进行“惩罚”，使.的稀疏

有更多的0$常量！控制稀疏性惩罚因子的权重，即 控制误差量和稀疏项之间的相对程度$在分解系数 中，只有少数系数远远大于0 ,其他系数全为0$因

此，必须防止将系数％jF减到很小的同时将每个基 的值增加到很大，第1项的代价值基本保持不变,而 第2项的稀疏惩罚依旧很小$基于上述分析,限制 '为一个有限空间，即|| ' | 2 式为：min ' || X\")- '

： 2 +!'S ()j) (j j = 1

j = 1

j = 1II '||2束，因此增强了局部特征并保持映射过程中的判别

性$同时，为得到更精确的哈希码,需适当控制哈希 码的量化误差$稀疏自动编码器由编码器和解码器2个部分组 成。在编码器部分，函数h(%,.)将输入的d维列向量% 映射到k维空间,即将X %匸/映射得到特征向量

X%匚D,其中k了获得二进制哈希码得到样本特征,经过自动编码 器的阈值函数为：a = sign (h( %,.)) = sign( h) %,.) ) ,) = 1,2，…,J(7)

其中，h(%,)表示输入数据经过自动编码器的编码部 分后，即样本向量%j在稀疏自编码器的隐藏层的特 征向量的第j个值,sign为符号函数，当h (%j) >0

时,sign h (%,.) = 1，神经元被激活；否则sign h (%,.)=

-1，神经元被抑制$自动编码器的激活函数将特征 向量由连续值变成离散的值$解码部分与编码部分同理,/(')映射'到匸/空间

去重构％，为学习理想的哈希函数h,目标函数为编码 器的输入值与解码器输出值的均方误差&可表示为：61=' II %j ~f( a j) | 2

(8)01式(8)是样本和隐藏层特征向量的最小均方误 差，目的是对相似的点在编码时保持相似性$由于 优化一个离散的非光滑的函数是NP问题,而a j是 经过编码部分求得的k维二进制离散哈希码,需要

解码层将离散哈希码再次变回连续值来求解,于是 采用隐藏层的输出值h (%,.)作为解码层的输入，目标 函数变为：62 = ' II %, ~f( h( %,)) | 2

(9)01式(9)为目标函数样本$和解码器输出的最小 均方误差，而在得到连续值来解决NP问题的同时, 离散的二进制码松弛到连续输入值的过程中产生了

不可控的量化误差$引用L2范数控制量化误差,则

目标函数变为原先的均方误差加上L2范数，有：224计 算 机 工 程2019年5月15日03='i = II 1% ；-/( A %,)) ||$+\"|| $ ;-h( % ,)|| $(10)

其中，\"是控制量化误差的权重参数，|| • ：$是L2 范数$在目标函数中加上稀疏约束来增强局部保持映

射过程中的判别性，根据式(4)稀疏编码器的隐藏层 第/个单元的平均激活值为：P,=^'人 1 N ( A(%,■)] (11)其中，a(%；)表示在给定输入样本向量为%；时,自编 码神经网络隐藏神经元F的激活度$由于稀疏限制，

隐藏神经元的平均激活度要尽可能小，为使哈希层 的所有单元的平均激活值p接近于0，采用KL距离 作为一项额外的惩罚因子，有：KL( p || )) =plg ¥+( 1 ~P) lg 乜 (1$)Pi 1 _P其中J依次代表隐藏层中的每一个神经元，并且 KL(p || P)的值随着p与P的差距增大而单调递增，

当p =pj时，KL(p || p： = 0$通过结合式(12 )和

式(10)的03，得到整体的目标函数为：04 = ' ||%i-_(A(%J) ||$+\" ||«i-A(%;) |$ +

i=1yKL(p || P) (13 )其中，D是隐藏层中隐藏神经元的数量，/为控制稀 疏性的参数$传统的哈希方法在经过GIST特征训练之后，连 续值的输出被用作哈希码的松弛处理。经过稀疏自

动编码器,通过对连续输出应用阈值函数来获得哈希 码。但是，该方法的缺陷是收敛速度很慢，且带来较

大的量化误差。同时，符号函数不可微分，难以反向 传播损失函数的梯度。由于欧几里得空间与汉明空

间之间的差异，如果完全忽略二元约束，那么会导致 次优哈希码。本文方法将符号函数直接应用在自动 编码器的解码器输出之后，严格限制输出为二元变

量，保持二进制码的离散性，同时利用随机梯度下降 法有助于算法的快速收敛,并得到最优权重值。同时

学习的二进制码使成对标签的似然性尽可能大，相似 的样本在映射到汉明空间后的哈希码也相似，不相似

的样本汉明距离较大。同时考虑哈希码学习过程中 的量化误差，利用L2范数使量化误差尽可能小，从而

得到更好的哈希码。基于GIST特征的稀疏自编码的 哈希算法如算法1所示。算法1 基于GIST特征的稀疏自编码的哈希 算法输入 ！个无标签的样本X = { X；

1输出均方误差最小值，并且得到最优权重为5 =/ WsABA， 5dh，5pCA， 5lsh，5sh，5kmh01 .样本经过自编码器阈值函数，得到离散的0-1码2. 以连续的隐藏层输出值h( Et)代替0-1码3. 最小均方误差加上L2范数4. 加上稀疏约束,并得到-45. 利用随机梯度下降法求取最优权重3实验结果与分析3.1

实验环境本文实验分别在 CIPAR-10(7]和 YouTube

Faces18]2个数据集进行图像检索算法精度验证，这 $个数据集由于开源、样本数量大等特点，在评价算 法的图像检索性能时被多数学者使用其中，

CIPAR-10数据集是由飞机、汽车、鸟、猫、鹿、狗、青 蛙、马、船以及卡车十类图像各6 000幅组成的60 000张 彩色图片的数据集$而YouTube Faces数据集是由 1 595个人组成的621 126张人脸的图像数据集$根 据文献(7 -8 ]，本文实验在CIPAR-10数据集中随机 抽出1 000张作为测试集，其余59 000张图片作为 训练集$在YouTubeFaces数据集中，本文实验将 65 个人中每个人选取 100 张人脸作为测试集， 其余 作为训练样本$根据文献(10 ]，本文实验评价指标是信息检索 实验中的常用指标平均准确率(Mean Average

Precision，MAP)，及召回率-查准率曲线(Precision Rate-Recall Rate Curve，PRC)[11] $ 其中，MAP 是指

平均精度的平均值$设第i张图片的检索精度是 ,%，则所有样本图片检索精度的平均值为：MAP = P%—n

(14)本文实验的CIPAR-10数据集实验中取n = 59 000$在PRC中，召回率是指系统检索到的相关

文件数量除以系统所有相关的文件总数，查准率是 指系统检索到的相关文件数除以系统所有检索到的

文件总数，一般情况下，两者成反比$本文所提出的模型使用开源库Tensorflow[ 12]来 实现，实验环境为 GeForce GTX Titan X GPU，中央

处理器为 Inwl ( R) Core it-5930K 3. 50 GHz，内存

为64 GB，操作系统为Ubuntu 14. 04 $3.2结果分析为测量本文所提出的SABA哈希算法检索性 能，在 CPFAR-10 数据集和 YouTub+Fac+s数据集中

采用深度哈希(Deep Hashing，DH)[ 10]、局部敏感哈 希(Locality Sensitive Hashing，LSH )[13]、谱哈希 (Spectral Hashing，SH )[ 14]、K 平均哈希(K-Means

Hashing，KMH)[15]以及基于主成分分析的迭代量化 哈希！ Pfncip/ Componentt An/ysis-Lera/ve Quantization Hashing，PCALEQ)[ 16]这5种无监督哈希算法进行

第45卷第5期代亚兰，何 朗，黄樟灿：基于稀疏自编码的无监督图像哈希算法2 25对比实验,如表1、表2所示&分别表示不同哈希码长

度（H\"在2个数据集上的检索结果$可以看出: 1）除表2中的SH算法以外,其他无监督哈希算法的 MAP变化趋势随编码位数的增加而加大$ 2）在特 定的编码位数上，本文算法的平均检索精度要比其 他无监督哈希算法高$综上，本文具有稀疏约束的

自编码器可以提高传统无监督哈希方法的检索精

度，并且L2范数可以有效控制量化误差$因此，本 文算法可以有效地学习哈希函数，并且精度优于其 他无监督哈希方法$表1 CIFAR-10数据集上不同算法平均准确率对比％算法H = 16H = 24H = 32H = 48H = 64本文算法18.0418.6419.0219.4319.86DH算法16.1716.4116.6216.8616.96LSH算法12.5513.0213.7614.4415.07SH算法12.9513.6614.0913.9813.89KMH算法13.5913.7813.9314.4414.46PCA-ITQ 算法15.6715.8616.2016.4416.64表2 YouTube Faces数据集上不同算法平均准确率对比％算法H = 16H = 24H=32H = 48H = 64本文算法31 . 3231.6631.8732.0732.32DH算法28.5029.0629.2529.9230.44LSH算法5.566. 086. 647. 127. 77

SH算法14.3514.7315.1216.2416.86KMH算法20.6120.9421 . 5321 . 9122.42PCA-ITQ 算法27.5428.0628.8429.0429.61图1表示在CITAR-10数据集上32 bC编码下

的查准率-召回率曲线，可以看出:1）随着召唤率的 增加，所有算法的查准率均会减少，即查准率与召回 率近似成反比$ 2 ）本文算法的PRC曲线与横纵轴 围成的曲线面积最大，其反映平均检索精度的大小$ 综上,本文基于稀疏自编码的哈希算法在PRC指标 下均优于其他对比算法，与表2结果相吻合$0.500.0 0.1

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1.0召回率图1 CIFAR-10数据集上不同算法查准率-召回率曲线对比结果4结束语本文提出一种无监督稀疏自编码哈希图像检索 算法。该算法从稀疏编码增强局部映射过程中的判

别性出发,将稀疏自动编码器与哈希方法相结合,解 决了哈希码的离散性导致的优化困难问题，并减少 输入输出的量化误差$实验结果验证了本文算法的 有效性$下一步研究如何将该算法应用到深度神经 网络中,以解决浅层特征语义信息不充分问题$参考文献[1 ] ZHENG Zhaohui, WU Xiaoyun, SRIHARI R, ei si.Feature selection for text categorization on imbalanccd data[ J]. ACM SIGKDD Explorationt Newsletter,2004 , 6(1) *80-89.[2 ]杨定中,陈心浩•基于投影残差量化哈希的近似最近

邻搜索[J] •计算机工程,2015 ,41 (12) *161 -165,170.[3 ]柯圣财,赵永威,李弼程,等.基于卷积神经网络和监

督核哈希的图像检索方法[J] •电子学报,2017 , 45 (1) *157-163.[4 ] LIU Wei, MU Cun, KUMAR S, ei si. Discrete graph

hashing[ C]///roccedingt of the 27th Internationai Conferencc on Neurai Information Proccssing Systems. Cambridge,USA:MIL Press,2014 *3419-3427.[5 ]赵文星•变系数部分线性模型的统计推断[D] •南京：

南京信息工程大学,2015•[6 ] XU Jun, XIANG Lei, LIU Qinshan, ci ai. Stacted sparse

autoen coder for nuciei dete ction on breast cancer histopathoiogy images [ J ] . IEEE Transactions on Medical Imaging ,2015 ,35 (1) *119-130.[7 ] LI Hongmin, LIU Hanchao, JI Xiangyang, ei i.

CITAR10-DVS: an event-stream datasei for objeci ciassificaion [ EB/OL] . [ 2018-02-05] .h *ps* //www.ncbi.nim.nih.gov /pmc/aricies/PMC5447775 /.[ 8 ] WOLFL, HASSNER T, MAOZ I.Face recogniion in unconstrained videos with matched backgroundsimiiariy[ C] //Proceedings of IEEE Conference on Compu erVision and Paern Recogniion.Washing*on D.C. , USA*IEEE Computer Society,2011 *529-534.[ 9 ] JIANG Qingyuan, LI Wueun. S caiabie graph hashing

with feature transformation [ C ] //Pro ceedings of the 24th InternationaiConference on ArtificiaiInteiigence$ [S.i. ] :AAAI Press,2015 *2248-2254.[ 10] L=ONG V E, LU Jiwen , WANGGang, etai.Deep hashing

for compaci binary codes learning [ C ] //Proceedings of IEEE Conference on Computer Viion and Patern Recognition.2475-2483$ Washington D. C. ,USA*IEEE Press,2015 : [11 ] MCJUNKIN M C. Precision and rcceli in title keyword

searches [ J ]. Information Technology and Linrarics, 1995,14(3) *161 -171.[12 ] ABADI M,BARHAM P,CHEN Jianmin,ci si. Tensordow*a

system for large-scale machine learning[C]//Proceedings of the 12th USENIX conferencc on Operating Systems Desicn and Implementation. Berkeley, USA* USENIX Association, 2016*265-283.[13 ]钟川,陈军•基于精确欧氏局部敏感哈希的改进协同

过滤推荐算法[J] •计算机工程,2017,34(2) *74-78•(下转第236页)23 6表2各算法性能对比结果算法计 算 机 工 程2019年5月15日时间平均时间平均MOS评分平均丢包率/%1.846PSNR 值/dB37. 63937. 60236. 733tha scalable video coding extension of tha H. 264/AVC standa ed[ J] $EEEETeansaetionson Cieeuitsand Systems for Video Technology ,2007,17 (9) *1103-1120.LDP-based 算法HA-based 算法OLSR-3算法3. 9653. 8963. 0004. 2417.114[7 ]杨晋生，胡自胜,陈为刚•无线可伸缩视频实时传输系统

设计与实现[J] •电子测量技术,2013 ,36 (1 )*115-119.[8 ] SEZER S,SCOTT-HAYWARD S, CHOUHAN P K, ai al.

Are wa ready for SDN? Implemenetion cha/engas for

softwaee-defined netwoeks [ J ] .EEEE Communieations

4结束语本文提出一种面向软件定义无线Mesh网络的

Magazine,2013 ,51 (7) *36-3.[9 ] MCKEOWN N,ANDERSON T,BALAKRIEHNAN H,ai al.

OpenFTow:enabling innovation in campus networks[ J]. ACM

可伸缩视频传输系统$在该系统中，基于LDP原理 对未来链路拥塞概率进行估计并提出相应的码率自

SIECOMM Computer Communication Review,2008,38 (2): 69-74.[ 10 ] Open Netwoeking Foundation.OpenFlow managementand

适应切换算法$实验结果表明,与基线算法相比,该 算法使用户收到的视频质量更高,网络丢包率更低$ 下一步将研究多用户场景下的WMN可伸缩视频传 输方案$参考文献[1 ] AKYILDIZ I F, WANG Xudong, WANG Weilin. Wireless

Mesh networks: a survey [ J ]. Computer Networks, 2005 , 47 (4) *445 -487.[2 ] JACQUET P,MUHLETHALER P, CLAUSEN T, at al.

Optimized link state routing protocol for ad hoc networks[ C]//Proceedings of 2001 IEEE InWrnationai Multi Topic Conference. Washington D. C. , USA: IEEE Press ,2001 *62 -68.[ 3 ] PERKENSC, BELDENG-ROYER E, DAS S$Ad hoe on- demand distance vector (AODV) routing [EB/OL]. [ 2018 - 06-15 ]. http：//rsync5. jp. gentoo. org/pub/IETF/RFC/pdf rfc/rfc3561. txt. pdf.[ 4 ] ABOLHASAN M, HAGELSTEEN B, WANG J C P$confipuration protocol [ EB/OL ]. [ 2018-06-30 ]. htt://

book. itep. ru/depositor/open_flow/of-config-1 • 1 • pdf.[ 11 ] WE EDachuan. An optimieed Floyd algoeithm foethe

shoetestpath peoblem[ J] $JouenalofNetwoeks,2010, 5 (12):1485-1496$[12 ] MANDJES M. Large deviations for Gaussian queues:

modeling communication netwoeks [ M ] $Hoboken, USA: John Wiley and Sons,2007 $[ 13] FONTES R R, AFZAL S, BRETO S H B, etalMininet-

Witi*emulating software-defined wpeless networks] C]//

Peoceedings of the 11th Enteenational Confeeence on

Netwoek and SeeviceManagementWashington D$C$, USA* EEEE Compute eSociety,2015 *384-389$[14 ] LIECHTY L C. Path loss measuremenw and modal

analysis of a 2. 4 GHz wireless network in an outdoor environment [ EB/OL]. [ 2018-06-25 ]. http：//propaga

tion. ace. gatach. edu/Archpa/PG_TR_070512 _LCL/

PG_TR_070512_LCL. pdf.[15 ] TANCHENKO A. Visut-PSNR measure of pnaga quatp [J].

Real-woeld peefoemaneeofeu eent p eoa etive multi-hop Mesh protocols [ C]//Proceedings of tha 15th Asia-Pacific Conference on Communications. Washington D. C. ,USA： IEEE Press,2009 ：42-45.[5 ]董超，陈贵海，王海•无线网状网的QoS研究[J].软件

学报,2009 ,20 (6) *1539-1552.[ 6 ] SCHWARZH, MARPE D, WEEGAND T Oveeview ofJoumt of Visut Communication and Enaga RepresenWtion,

2014,25( 5) *874-878.[ 16] MOLDOVAN A N, GHERGULESCU E, MUNTEAN C H.

VQAMap: a novel mechanism for mapping objective video

quality metrics to subjective MOS scale [ J ]. IEEE Transactions on Broadcasting,2016,62(3) *610-627.编辑吴云芳(上接第225页)[ 14] WEESSY, TORRALBA A, FERGUS R Speeteal

Recognition. Washington D. C. , USA : IEEE Computer Society,2013 *2938-2945.Hashing [ C ] //Proceedings of tha 21 st International

Confeeeneeon NeuealEnfoemation Peoeessing Systems$

[S. a ] : Curran Associates Inc. ,2008 : 1753-1760.[16] GONG Yunchao, LAZEBNIK S, GORDO A, et al.

Lerative quantizetion*a procrustean approach to learning binary codes for large-scale image retrieval [ J ]. IEEE

Transactions on Pattern Analysis and Machine

[15 ] HE Kaiming,WEN Fang, SUN Jian. K-means hashing：

an affPity-pssasPg quantizetion method for learning

binary compaci codas [ C ] //Proceedings of IEEE Confeeenee on Computee Viion and Pateen

Intelligence,2013 ,35 (12) *2916-2929.编辑赵辉