一种基于局部相似哈希算法的大规模图像库检索方法

1.一种基于局部相似哈希算法的大规模图像库检索方法，包括下列步骤：
提取查询图像和待检索图像库中训练集图像的特征，具体包括以下步骤：
对所述待检索图像库中训练集的图像提取SIFT特征；
对提取的所述SIFT特征进行K均值聚类得到码本；
计算码本中每一码字的逆频率；
计算每一码字的局部敏感哈希编码；
将所述SIFT特征映射到汉明空间；
利用码本中每一码字的逆频率计算每一码字的权重，并利用所述每一码字的权重和所述每一码字的局部敏感哈希编码计算所述查询图像的局部相似哈希编码和所述待检索图像库中每一幅图像的局部相似哈希编码；计算所述查询图像的局部相似哈希编码与所述待检索图像库中每一幅图像的局部相似哈希编码之间的汉明距离，利用距离大小来衡量所述查询图像与所述待检索图像库中图像之间的相似性，返回相似度高的图像。
2.一种基于局部相似哈希算法的大规模图像库检索方法，包括下列步骤：
步骤S1，对待检索图像库中选作为训练集的全部图像提取SIFT特征，对其进行K均值聚类得到码本，再计算每一码字的逆频率；
步骤S2，利用步骤S1得到的所述码本计算待检索图像库中每一幅图像的局部相似哈希编码；
步骤S3，利用步骤S1得到的所述码本计算查询图像的局部相似哈希编码，并由此计算所述查询图像的局部相似哈希编码与所述待检索图像库中每一幅图像的局部相似哈希编码之间的汉明距离，返回所述待检索图像库中与所述查询图像汉明距离最小的S个图像作为检索结果，其中S为由用户预先设定的正整数。
3.根据权利要求2所述的基于局部相似哈希算法的大规模图像库检索方法，其中所述步骤S1进一步包括以下步骤：
步骤S11：从待检索图像库D＝{D1，D2，...，DN}中选取部分图像T＝{T1，T2，...Tn}作为训练集，其中N为待检索图像库的大小，n为训练集的大小，n≤N；
步骤S12：对所述训练集T中的全部图像分别提取SIFT特征，构成SIFT特征集合V＝{Vi}，
1≤i≤z，z为训练集图像中提取的SIFT特征总数；
步骤S13：对提取的所述SIFT特征进行K均值聚类，得到码本C＝{ci}，其中1≤i≤q，q为码本的大小，即码字的个数； 为d维的列向量；
步骤S14：通过下式计算每一码字ci的逆频率IDFi：
其中1≤i≤q，n为训练集的大小，ni为包含码字ci的图像的数量，lg表示以10为底计算对数值；
步骤S15：计算每一码字ci的局部敏感哈希编码Li，其中Li∈{-1，1}k，k是总的编码位数。
4.根据权利要求3所述的方法，其中步骤S13中所述的K均值聚类步骤进一步包括以下步骤：
步骤131：从V中随机选取q个SIFT特征作为初始聚类中心μi，1≤i≤q；
步骤132：将训练集中提取的SIFT特征按照欧氏距离最近的准则分配给q个聚类中心的某一个μi，这样所有的SIFT特征形成q个簇；计算每个簇中所有SIFT特征的均值，并将该均值作为该簇新的聚类中心μi；计算每个簇中的误差平方和，进而得到q个簇总的误差平方和；
步骤133：重复步骤132，直到总的误差平方和小于给定阈值时，K均值算法结束，并将得到的q个簇的聚类中心μi作为码本C。
5.根据权利要求3所述的方法，其中步骤S15进一步包括步骤：
步骤S151：由高斯分布随机产生k个d维列向量rj，其中
步骤S152：根据下式分别计算Li的每一位，
其中，Lij是Li的第j位，1≤j≤k。
6.根据权利要求3所述的基于局部相似哈希算法的大规模图像库检索方法，其中所述步骤S2进一步包括以下步骤：
步骤S21：对所述待检索图像库中的图像Di提取SIFT特征，其中1≤i≤N：
步骤S22：利用步骤S13中训练得到的所述码本，计算所述待检索图像库中的图像Di中每个码字的词频TFi，其中1≤i≤q；
步骤S23：根据下式计算所述待检索图像库中的所述图像中每个码字的权重wi：
wi＝TFi·IDFi；
其中，1≤i≤q；
步骤S24：根据下式计算所述待检索图像库中的所述图像的局部相似哈希编码H(Di)：
其中，1≤i≤N，H(Di)[j]为H(Di)的第j位，Lmj为Lm的第j位，1≤j≤k；sign函数满足如下性质：
7.根据权利要求3所述的基于局部相似哈希算法的大规模图像库检索方法，其中所述步骤S3进一步包括以下步骤：
步骤S31：对查询图像Q提取SIFT特征；
步骤S32：利用步骤S13中训练得到的所述码本，计算查询图像中每个码字的词频TFi，其中1≤i≤q；
步骤S33：根据下式计算查询图像中每个码字的权重wi：
wi＝TFi·IDFi；
其中，1≤i≤q；
步骤S34：根据下式计算查询图像的局部相似哈希编码H(Q)：
其中，H(Q)[j]为H(Q)的第j位，1≤j≤k；
步骤S35：根据下式计算查询图像编码H(Q)与待检索图像库中每一幅 图像编码H(Di)之间的汉明距离Dh(H(Q)，H(Di))：
其中，1≤i≤N，H(Q)[j]和H(Di)[j]分别表示H(Q)和H(Di)的第j位， 表示异或操作；
步骤S36：根据查询图像编码H(Q)与待检索图像库中图像编码H(Di)之间的汉明距离Dh(H(Q)，H(Di))，返回待检索图像库中与查询图像汉明距离最小的S个图像作为检索结果。
8.根据权利要求2所述的基于局部相似哈希算法的大规模图像库检索方法，其中S＝
10。

一种基于局部相似哈希算法的大规模图像库检索方法\n技术领域\n[0001] 本发明属于图像检索技术领域，更具体地涉及一种基于内容的图像检索方法，尤其是一种基于局部相似哈希算法的大规模图像库检索方法。\n背景技术\n[0002] 随着互联网的快速发展，互联网上的图片数据日益增多。如何快速、准确地为用户提供所需要的图片资源显得越来越重要。基于内容的图像检索(content-based image retrieval，CBIR)技术应运而生，受到了许多研究者的关注。一般来说CBIR系统主要包括两部分的核心研究内容，一是有效的图像特征表述，二是高效检索算法。\n[0003] 图像特征表述方面，最初的CBIR系统利用图像的全局底层特征，例如颜色、纹理、形状等来表述图像。但是这类全局特征不能很好地捕捉到图像的局部信息，因此判别性不高。基于SIFT(Scale Invariant Feature Transform，尺度不变特征转换，具体含义例如参见文章David G.Lowe，“Distinctive image features from scale invariant keypoints”，International Journal ofComputer Vision，66(2)，2004)局部特征的词袋模型(BOW)  (相关内容例如参见文章Josef Sivic and Andrew Zisserman，“Video google： A text retrieval approach to object matching in videos”，In Proceedings of International Conference on Computer Vision，2003)，是一种新颖的图像表述方法。在BOW中，首先提取图像的局部SIFT特征，然后将SIFT特征量化成码本(codebook)，最后利用码本的信息来表示图像。\n[0004] 检索算法方面主要包括基于树的检索算法和基于哈希的检索算法。基于树的检索算法利用超平面递归地划分整个数据空间，在数据比较低维的情况下效果很好，但是当数据维度比较高的时候，基于树的检索算法会退化成穷尽搜索。基于哈希的检索算法的主要思想是将原始数据映射成汉明空间中的二进制数值串(binary string)，数据之间的相似度可以利用它们在汉明空间的二进制数值串之间的汉明距离来度量。基于哈希的高效检索算法有两个主要优点：一是可以减少数据存储空间；二是可以提高检索效率。\n[0005] 局部敏感哈希(1ocality-sensitive hashing，LSH，例如可以参考文章 Mayur Datar，Nicole Immorlica，Piotr Indyk and Vahab S.Mirrokni，“Locality-sensitive hashing scheme based on p-stable distributions”，In Proceedings of the twentieth annual sympo sium on computational geometry， ACM，2004)利用从满足p-stable的分布上随机产生投影函数来对原始数据分别进行投影，再把投影后的数据阈值化为0和1，这样就得到了原始数据的编码。但是由于LSH的投影函数是数据无关(data-independent)、随机产生的，并且产生的投影函数可能彼此是相关的，因此LSH编码的效果不是很理想。为了克服LSH的缺点，谱哈希(Spectral Hashing，SH，例如可以参考文章Yair Weiss，Antonio Torralba，and Rob Fergus，“Spectral Hashing”，In NIPS，2008)基于谱图分割，利用机器学习的方法通过阈值化数据的相似图拉普拉斯的特征向量的子集来计算哈希编码。\n[0006] 常用基于哈希的CBIR方法首先提取图像的全局特征，然后利用检索算法进行哈希编码。这将导致此类CBIR方法存在两个缺陷：首先，全局特征对图像的特征描述能力有限，判别性差；其次，对全局特征进行哈希会进一步降低特征的判别性。这两个缺陷大大降低了CBIR的性能。\n发明内容\n[0007] 有鉴于此，本发明的发明目的是提出一种基于局部相似哈希算法的大规模图像库检索方法，以解决海量图像检索中存在的图像特征库存储空间大、检索速度慢的问题。\n[0008] 为了实现上述目的，作为本发明的一个方面，本发明提出了一种基于局部相似哈希算法的大规模图像库检索方法，包括下列步骤：\n[0009] 提取查询图像和待检索图像库中训练集图像的特征，\n[0010] 将特征映射到汉明空间，\n[0011] 计算所述查询图像的哈希编码与所述待检索图像库中每一幅图像的哈希编码之间的汉明距离，利用距离大小来衡量所述查询图像与所述待检索图像库中图像之间的相似性，返回相似度高的图像。\n[0012] 其中，所述提取待检索图像库中训练集图像的特征的步骤包括：\n[0013] 对所述待检索图像库中训练集的图像提取SIFT特征；\n[0014] 对提取的所述SIFT特征进行K均值聚类得到码本；\n[0015] 计算码本中每一码字的逆频率；\n[0016] 计算每一码字的局部敏感哈希编码。\n[0017] 作为本发明的另一个方面，本发明还提出了一种基于局部相似哈希算法的大规模图像库检索方法，包括下列步骤：\n[0018] 训练过程，对待检索图像库中选作为训练集的全部图像提取SIFT特征，对其进行K均值聚类得到码本，再计算每一码字的逆频率和局部敏感哈希编码；\n[0019] 待检索图像库编码过程，利用所述训练过程得到的所述码本计算待检索图像库中每一幅图像的局部相似哈希编码；\n[0020] 查询过程，利用所述训练步骤得到的所述码本计算查询图像的局部相似哈希编码，并由此计算所述查询图像的哈希编码与所述待检索图像库中每一幅图像的哈希编码之间的汉明距离，返回所述待检索图像库中与所述查询图像汉明距离最小的S个图像作为检索结果，其中S为由用户预先设定的正整数。\n[0021] 其中，所述训练过程进一步包括步骤：\n[0022] 步骤S11：从待检索图像库D＝{D1，D2，...，DN}中选取部分图像T＝{T1， T2，...Tn}作为训练集，其中N为待检索图像库的大小，n为训练集的大小， n≤N；\n[0023] 步骤S12：对所述训练集T中的全部图像分别提取SIFT特征vi，1≤i ≤z，z为训练集图像中提取的SIFT特征总数\n[0024] 步骤S13：对提取的所述SIFT特征进行K均值聚类，得到码本C＝{ci}，其中1≤i≤q，q为码本的大小，即码字的个数； 为d维的列向量；\n[0025] 步骤S14：通过下式计算每一码字ci的逆频率IDFi：\n[0026]\n[0027] 其中1≤i≤q，n为训练集的大小，ni为包含码字ci的图像的数量，lg 表示以10为底计算对数值。\n[0028] 步骤S15：计算每一码字ci的局部敏感哈希编码Li，其中Li∈{-1，1}k， k是总的编码位数。\n[0029] 其中，步骤S13中所述的K均值聚类步骤进一步包括：\n[0030] 步骤131：从vi中随机选取q个SIFT特征作为初始聚类中心μi，1≤i ≤q；\n[0031] 步骤132：将训练集中提取的SIFT特征按照欧氏距离最近的准则分配给q个聚类中心的某一个μi，这样所有的SIFT特征形成q个簇；计算每个簇中所有SIFT特征的均值，并将该均值作为该簇新的聚类中心μi；计算每个簇中的误差平方和，进而得到q个簇总的误差平方和；\n[0032] 步骤133：重复步骤132，直到总的误差平方和小于给定阈值时，K 均值算法结束，并将得到的q个簇的聚类中心μi作为码本C。\n[0033] 其中，步骤S15进一步包括步骤：\n[0034] 步骤S151：由高斯分布随机产生k个d维列向量rj，其中 1≤ j≤k；\n[0035] 步骤S152：根据下式分别计算Li的每一位，\n[0036]\n[0037] 其中，Lij是Li的第j位，1≤j≤k。\n[0038] 其中，所述待检索图像库编码过程进一步包括下列步骤：\n[0039] 步骤S21：对所述待检索图像库中的图像Di提取SIFT特征，其中1≤ i≤N；\n[0040] 步骤S22：利用步骤S13中训练得到的所述码本，计算所述待检索图像库中的图像Di中每个码字的词频TFi，其中1≤i≤q；\n[0041] 步骤S23：根据下式计算所述待检索图像库中的所述图像中每个码字的权重wi：\n[0042] wi＝TFi·IDFi\n[0043] 其中，1≤i≤q；\n[0044] 步骤S24：根据下式计算所述待检索图像库中的所述图像的局部相似哈希编码H(Di)：\n[0045]\n[0046] 其中，1≤i≤N，H(Di)[j]为H(Di)的第j位，Lmj为Lm的第j位， 1≤j≤k；sign函数满足如下性质：\n[0047]\n[0048] 其中，所述查询过程进一步包括步骤：\n[0049] 步骤S31：对查询图像Q提取SIFT特征；\n[0050] 步骤S32：利用步骤S13中训练得到的所述码本，计算查询图像中每个码字的词频TFi，其中1≤i≤q；\n[0051] 步骤S33：根据下式计算查询图像中每个码字的权重wi：\n[0052] wi＝TFi·IDFi\n[0053] 其中，1≤i≤q；\n[0054] 步骤S34：根据下式计算查询图像的局部相似哈希编码H(Q)：\n[0055]\n[0056] 其中，H(Q)[j]为H(Q)的第j位，1≤j≤k；\n[0057] 步骤S35：根据下式计算查询图像编码H(Q)与待检索图像库中每一幅 图像编码H(Di)之间的汉明距离Dh(H(Q)，H(Di))：\n[0058]\n[0059] 其中，1≤i≤N，H(Q)[j]和H(Di)[j]分别表示H(Q)和H(Di) 的第j位， 表示异或操作；\n[0060] 步骤S36：根据查询图像编码H(Q)与待检索图像库中图像编码H (Di)之间的汉明距离Dh(H(Q)，H(Di))，返回待检索图像库中与查询图像汉明距离最小的S个图像作为检索结果。\n[0061] 其中，优选S＝10。\n[0062] 本发明的基于局部相似哈希算法的大规模图像库检索方法能够将图像的特征表述和检索算法自然地结合在一起，根据局部特征的相似性和编码来得到对整个图像的编码，使得内容相似的图像最后得到的局部相似哈希编码也是相似的。本发明利用图像局部特征判别性好的特点，首先利用局部敏感哈希算法对图像SIFT特征进行编码，然后利用局部特征的编码得到最后图像的局部相似哈希编码。本发明中所述方法更充分地利用了图像的局部特征信息，保持了局部特征的判别性，这样得到的对图像的编码也具有比较好的判别性。通过本发明的检索方法，能够减少图像特征的存储空间，同时也能够极大地提高检索效率。\n附图说明\n[0063] 图1是本发明的基于局部相似哈希算法的大规模图像检索方法的流程示意图；\n[0064] 图2是本发明用于建立训练集的部分样本的图像；\n[0065] 图3是4幅查询图像在k＝512位编码时的检索结果，其中最左边的是查询图像，右边只显示了检索到的汉明距离最小的10幅图像。\n具体实施方式\n[0066] 为使本发明的目的、技术方案和优点更加清楚明白，以下结合技术方案和附图详细叙述本发明的具体实施方式。其中，以FLICKR1M(例如参见文章Mark J.Huiskes，Michael S.Lew，“The  MIR Flickr  retrieval evaluation”，In Proceedings of ACM International Conference on Multimedia Information Retrieval，2008的介绍)数据集为例进行说明。FLICKR1M包含100万张图片，都是从Flickr网站下载的，图片的内容千差万别，尺寸也是多种多样。\n[0067] 本发明提出的一种基于局部相似哈希算法的大规模图像库检索方法，包括以下步骤：\n[0068] 对于图像库中的图像，选取一部分图像作为训练图像集；\n[0069] 对于图像库和训练集，提取SIFT局部特征；\n[0070] 然后，利用训练图像集的SIFT特征，来训练得到码本，之后计算码本中每个码字(codeword)的逆频率IDF，并利用局部敏感哈希对码本进行编码；\n[0071] 根据训练得到的码本，计算图像库中的每一幅 图像中的码字的词频 TF和权重w，之后对图像进行局部相似哈希编码；\n[0072] 对于查询图像，首先提取其SIFT特征，然后根据训练得到的码本用同样的方法对查询图像进行局部相似哈希编码，之后计算查询图像编码与图像库中图像编码之间的汉明距离，利用距离大小来衡量查询图像与图像库中待检索图像之间的相似性，返回相似度高的图像。\n[0073] 更具体地，下面结合附图对本发明的基于局部相似哈希算法的大规模图像库检索方法进行详细的描述。\n[0074] 图1的左边部分S1表示本发明实施例的训练过程的主要流程图，如图所示，[0075] 步骤S11：将FLICKR1M数据集分为两部分：待检索图像库D(99 万5千张)和查询图像集(5千张)。并从待检索图像库中随机选取10万张图片作为训练集T。部分训练图像样本如图2所示。\n[0076] 步骤S12：对训练集T中的图像提取SIFT特征vi， d＝128， 1≤i≤z，z为训练集图像中提取的SIFT特征总数。\n[0077] 步骤S13：对训练集中图像的SIFT特征进行K均值聚类得到码本 C＝{ci}，1≤i≤q，其中q为码本的大小，即码字的个数，取q＝1000， 其中ci为d维的列向量，d＝\n128。\n[0078] K均值算法流程如下：1、从vi中随机选取q个SIFT特征作为初始聚类中心μi，1≤i≤q；2、将训练集中提取的SIFT特征按照欧氏距离最近的准则分配给q个聚类中心的某一个μi，这样所有的SIFT特征形成q个簇；计算每个簇中所有SIFT特征的均值，并将该均值作为该簇新的聚类中心μi；计算每个簇中的误差平方和，进而得到q个簇总的误差平方和；3、重复过程2，直到总的误差平方和小于给定阈值时，K均值算法结束，并将得到的q个簇的聚类中心μi作为码本C。\n[0079] 步骤S14：按下式计算每一个码字ci的逆频率IDFi，1≤i≤1000。\n[0080]\n[0081] 其中，n为训练集的大小，n＝100000，ni为包含码字ci的图像的数量，上式中lg表示以10为底计算对数值。\n[0082] 步骤S15：训算每一个码字ci的局部敏感哈希编码Li，Li∈{-1，1}k，其中k是总的编码位数。首先由高斯分布随机产生k个d维列向量  1≤j≤k。然后按下式分别计算Li的每一位，\n[0083]\n[0084] Lij是Li的第j位，1≤j≤k。本实施例中k取值512。\n[0085] 图1的中间部分S2表示本发明实施例的待检索图像库编码过程的主要流程图，如图所示，\n[0086] 步骤S21：对D中的图像Di，1≤i≤995000，提取其SIFT特征。\n[0087] 步骤S22：利用步骤S13中训练得到的码本，计算图像中每个码字的词频(TF)，即出现的个数。记码字ci的词频为TFi，1≤i≤1000。\n[0088] 步骤S23：按下式计算图像中每个码字的权重w，记码字ci的权重为 wi，1≤i≤\n1000。\n[0089] wi＝TFi·IDFi\n[0090] 步骤S24：按下式计算图像的局部相似哈希编码H(Di)，1≤i≤995000：\n[0091]\n[0092] 其中，Lm表示第m个码字的局部敏感哈希编码，1≤m≤1000，H(Di) [j]为H(Di)的第j位，Lmj为Lm的第j位，1≤j≤512。sign函数满足如下性质：\n[0093]\n[0094] 图1的右边部分S3表示本发明实施例的查询过程的主要流程图，如图所示，[0095] 步骤S31：对查询图像提取其SIFT局部特征。\n[0096] 步骤S32：利用步骤S13中训练得到的码本，计算查询图像中每个码字的词频TFi，1≤i≤1000。\n[0097] 步骤S33：计算查询图像中每个码字ci的权重为wi，1≤i≤1000。具体计算方法同S23。\n[0098] 步骤S34：按下式计算查询图像的局部相似哈希编码H(Q)：\n[0099]\n[0100] 其中，H(Q)[j]为H(Q)的第j位，1≤j≤512。\n[0101] 步骤S35：按下式计算查询图像编码H(Q)与待检索图像库中每一个图像编码H(Di)(1≤i≤995000)之间的汉明距离Dh(H(Q)，H(Di))：\n[0102]\n[0103] 其中，H(Q)[j]和H(Di)[j]分别表示H(Q)和H(Di)的第j位， 表示异或操作。\n[0104] 步骤S36：根据查询图像编码H(Q)与待检索图像库中图像编码H (Di)(1≤i≤\n995000)之间的汉明距离Dh(H(Q)，H(Di))，返回待检索图像库中与查询图像汉明距离最小图像作为检索结果。\n[0105] 限于篇幅，图3中只给出了4幅查询图像，并显示了排序前十的检索结果。通过实际操作可知，本发明的检索方法能够减少图像特征的存储空间，同时也能够极大地提高检索效率，获得比较准确的检索结果。\n[0106] 以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。