本文共 2071 字,大约阅读时间需要 6 分钟。
查询相关性的判断:准确率(precision)、召回率(recall)
有多种划分方式
基于传统向量空间模型进行相似匹配,其中有两个比较常见的术语,TD-IDF值和余弦相似性。
单词的多义性和同义性(不同单词表示相同意思)对基于传统单词统计的信息检索有很大阻碍,需要去除单词间的相关性,一种常用的技术是潜在语义分析(Latent Semantic Analysis,LSA)。
LSA(LSI)使用SVD来对单词-文档矩阵进行分解。SVD可以看作是从单词-文档矩阵中发现不相关的索引变量(因子),将原来的数据映射到语义空间内。在单词-文档矩阵中不相似的两个文档,可能在语义空间内比较相似。将特征向量以树结构的方法组织起来,使得在检索的时候其计算复杂度降到关于样本数目n的对数的复杂度,具体算法可看《统计学习方法》K-近邻一章,适合于低维的情况,特征维数过高也不太适用,一种改进是multiple randomized k-d trees。
基于哈希的检索方法其关键之处在于设计一个有效的哈希函数集,使得原空间中的数据经过该哈希函数集映射后,在汉明空间其数据间的相似性能够得到较好的保持或增强。
基于哈希的检索过程包括:特征提取、哈希编码、汉明距离排序和重排(重排的目的是在相似样本集中进行精细检索) 上图为一种局部敏感哈希方法的示意图,它用随机生成的超平面去分割数据集,并为它们编码, 最后将编码结果串接在一起形成哈希码。原空间中相似的数据在很大概率上会被编成相同的哈希码(落入同一个“桶”中)。谷歌搜索早期的核心算法,由Larry Page发明,它的主要思想是网页文档间含有大量的有向连接,重要的文档往往有很多链接指向它们.
将图像类比成文档,将图像局部类比成单词的优点是可以使用前面介绍的信息检索的标准策略。
词袋模型的基本思想是提取图像的局部特征描述子(如SIFT),然后将其聚类量化成视觉词(Visual words),并对整幅图像的视觉词进行词频统计,乘上TD-IDF值组成加权词频向量,作为最终用于相似性匹配的特征向量,最后按计算出的相似性大小排序返回检索的结果。
词袋模型示意图可先根据余弦相似性进行初步检索,然后再检查检索结果与查询图像的空间一致性
由于视觉单词中的向量量化会抑制一些可能重要的细节,可以尝试采用以下策略进行改进量化的匹配。
策略1:计算多个不同的向量量化(使用不同的k-means聚类建立多个相似排序列表,然后对每张检索出的图像在不同列表中的排序求中位数) 策略2:使用大规模的词库(利用层级k-means(树形结构)等方法提高搜索效率) 策略3:搜索所有匹配查询图像的兴趣点可根据空间一致性采用RANSAC(随机采样一致)等算法进行重排
可采用多维缩放(MDS)等技术(类似谷歌地球地图放大的效果)