低空间复杂度的LSH算法及其在图像检索中的应用

J4 ›› 2015, Vol. 37 ›› Issue (02): 379-383.

低空间复杂度的LSH算法及其在图像检索中的应用

曹玉东，刘艳洋，孙福明，贾旭

（辽宁工业大学电子与信息工程学院，辽宁锦州 121001）

收稿日期:2013-05-10 修回日期:2013-11-21 出版日期:2015-02-25 发布日期:2015-02-25
基金资助:
国家自然科学基金资助项目（61272214）；辽宁省自然科学基金资助项目（2013020020）；辽宁省教育厅一般项目（L2013241）；辽宁工业大学教师科研启动基金（X201216）

LSH with low space complexity for image retrieval

CAO Yudong，LIU Yanyang，SUN Fuming,JIA Xu

（College of Electronics & Information Engineering,Liaoning University of Technology,Jinzhou 121001,China）

Received:2013-05-10 Revised:2013-11-21 Online:2015-02-25 Published:2015-02-25

摘要/Abstract

摘要：

局部敏感哈希LSH算法是有效的高维数据索引方法，如何生成哈希函数是算法的关键部分。LSH算法的哈希函数是基于p稳态分布随机生成的，为了提高算法性能就需要增加哈希表的数量，但这会增加算法的空间复杂度。改进后的LSH算法(ILSH)在生成哈希函数时不需要有标记的训练样本，而是仅仅利用数据点的分布信息构造投影方向。实验结果表明，在不显著降低检索性能的情况下，ILSH有效地降低了内存的使用量，适合处理大规模数据。

关键词: 高维数据索引, 局部敏感哈希索引, 图像检索, Gist特征

Abstract:

Locality sensitive hashing (LSH) is quite popular in high dimensional data indexing.The Hash function in the original LSH algorithm is generated based on pstable distribution.So the number of hash tables must be increased in order to improve the performance of the algorithm,which however leads to a high space complexity.An improved LSH (ILSH) algorithm is proposed,which does not require the labeled samples but only uses the distribution of data to construct the projection direction.The experimental results show that ILSH can greatly save the memory without degrading its retrieval performance.

Key words: high data indexing;LSH indexing;image retrieval;Gist feature

曹玉东，刘艳洋，孙福明，贾旭. 低空间复杂度的LSH算法及其在图像检索中的应用[J]. J4, 2015, 37(02): 379-383.

CAO Yudong，LIU Yanyang，SUN Fuming,JIA Xu. LSH with low space complexity for image retrieval [J]. J4, 2015, 37(02): 379-383.

[1]	韩辉, 麦合甫热提, 吾尔尼沙·买买提, 朱亚俐, 库尔班·吾布力, . 基于Gist和IPCA算法的多文种离线手写签名识别[J]. 计算机工程与科学, 2022, 44(11): 2048-2055.
[2]	强梓林, 刘建国, 刘云峰, 卫栋, 强彦. 基于时域-频域哈希编码的电网图像检索方法[J]. 计算机工程与科学, 2022, 44(10): 1877-1884.
[3]	姬子恒, 王斌. 基于深度学习的草图检索方法研究进展[J]. 计算机工程与科学, 2021, 43(12): 2190-2205.
[4]	贺周雨1,冯旭鹏2,刘利军1,黄青松1,3. 基于SHN模型的商品图像检索方法[J]. 计算机工程与科学, 2019, 41(11): 1991-1999.
[5]	李秋珍1，白兴强2，李立夏1，王赢1. 量化编码的分层可通航小世界图算法[J]. 计算机工程与科学, 2019, 41(04): 618-625.
[6]	袁晖1，廖开阳1,3，郑元林1,2，曹从军1,3，汤梓伟1，邓轩1. 基于CNN特征加权和区域整合的图像检索[J]. 计算机工程与科学, 2019, 41(01): 113-121.
[7]	张南1,韩晓军1,2. 融合颜色词袋特征的视觉词汇树图像检索[J]. 计算机工程与科学, 2018, 40(03): 487-493.
[8]	欧新宇1，2，伍嘉3，朱恒4，李佶5. 基于深度自学习的图像哈希检索方法[J]. J4, 2015, 37(12): 2386-2392.
[9]	彭晏飞1，尚永刚1,王德建2. 一种新的基于SVM和主动学习的图像检索方法[J]. J4, 2014, 36(07): 1371-1376.
[10]	张振华,朱信忠,赵建民,徐慧英. 一种基于局部保形映射（LPP）的相关反馈方法[J]. J4, 2012, 34(6): 101-105.
[11]	张静,许高锋. 基于优化分块颜色直方图及模糊C聚类的彩色图像检索方法[J]. J4, 2011, 33(8): 106-111.
[12]	任小康，白勇峰，范丽，李颜瑞. 基于改进的SVM的甲状腺图像检索[J]. J4, 2011, 33(1): 127-131.
[13]	赵建民, 文春勇, 朱信忠, 徐慧英. 一种基于记忆的图像检索相关反馈策略[J]. J4, 2010, 32(2): 67-71.
[14]	肖来元, 闭彬. 文本检索方法驱动的海量图像数据库目标匹配研究[J]. J4, 2010, 32(2): 91-94.
[15]	徐果毅朱宁波朱晓林卢晓阳. 基于颜色直方图熵值及分块主色的图像检索[J]. J4, 2008, 30(9): 44-46.