《计算机视觉-一种现代方法(第2版)》读书笔记六:应用之图像搜索和检索
本篇思维导图
1 应用内容
1.1 应用领域
- 找寻相近副本:相似图片搜索,可用在电子商务以及商标、摄影作品等版权保护中
- 语义搜索:搜寻某种语义的图片
- 图像数据挖掘:如对卫星图像进行数据挖掘以回答城市扩张程度、还剩下多少热带雨林等
1.2 用户需求
查询相关性的判断:准确率(precision)、召回率(recall)
1.3 查询图像的类型
有多种划分方式
一种划分
- 独特的物体:如埃菲尔铁塔
- 带限定的独特物体:如1950年的埃菲尔铁塔
- 非独特的物体:类别,如狗
- 带限定的非独特物体:修饰的类别,如趴在地上吐舌头的狗
另一种划分
- Specific:类的一个实例,如某个邻居家的猫
- general:类的一个个体,如一只猫
- subjective:情感或抽象的内容,如猫
2 来自信息检索的基本技巧
2.1 单词统计
基于传统向量空间模型进行相似匹配,其中有两个比较常见的术语,TD-IDF值和余弦相似性。
- TF-IDF(term frequency-inverse document frequency)值:词频-逆文档频率值,信息检索中常见的术语,详见此处
- 余弦相似性:通过两向量的夹角大小来判断向量的相似程度,夹角越小,余弦值越大,向量越相似。详见此处
2.2 平滑单词统计
单词的多义性和同义性(不同单词表示相同意思)对基于传统单词统计的信息检索有很大阻碍,需要去除单词间的相关性,一种常用的技术是潜在语义分析(Latent Semantic Analysis,LSA)。
LSA(LSI)使用SVD来对单词-文档矩阵进行分解。SVD可以看作是从单词-文档矩阵中发现不相关的索引变量(因子),将原来的数据映射到语义空间内。在单词-文档矩阵中不相似的两个文档,可能在语义空间内比较相似。
2.3 最近邻估计和哈希技术
2.3.1 K-D树用于最近邻估计
将特征向量以树结构的方法组织起来,使得在检索的时候其计算复杂度降到关于样本数目n的对数的复杂度,具体算法可看《统计学习方法》K-近邻一章,适合于低维的情况,特征维数过高也不太适用,一种改进是multiple randomized k-d trees。
2.3.2 哈希技术之局部敏感哈希(LSH)
基于哈希的检索方法其关键之处在于设计一个有效的哈希函数集,使得原空间中的数据经过该哈希函数集映射后,在汉明空间其数据间的相似性能够得到较好的保持或增强。
基于哈希的检索过程包括:特征提取、哈希编码、汉明距离排序和重排(重排的目的是在相似样本集中进行精细检索)
上图为一种局部敏感哈希方法的示意图,它用随机生成的超平面去分割数据集,并为它们编码, 最后将编码结果串接在一起形成哈希码。原空间中相似的数据在很大概率上会被编成相同的哈希码(落入同一个“桶”中)。
2.4 文档排序
网页排序Pagerank
谷歌搜索早期的核心算法,由Larry Page发明,它的主要思想是网页文档间含有大量的有向连接,重要的文档往往有很多链接指向它们.
p表示文档重要性,Nk表示与文档相连的外部链接数
3 将图像作为文档
3.1 概述
3.1.1 意义
将图像类比成文档,将图像局部类比成单词的优点是可以使用前面介绍的信息检索的标准策略。
3.1.2 经典模型——词袋模型
词袋模型的基本思想是提取图像的局部特征描述子(如SIFT),然后将其聚类量化成视觉词(Visual words),并对整幅图像的视觉词进行词频统计,乘上TD-IDF值组成加权词频向量,作为最终用于相似性匹配的特征向量,最后按计算出的相似性大小排序返回检索的结果。
词袋模型示意图
3.1.3 图像与文档的不同点
- 图像局部兴趣点间的关系比单词间的关系要丰富的多(图像有空间布局)
- 图像支持复杂布局的浏览而文档不行,因为图像具有即视性
3.1.4 策略
可先根据余弦相似性进行初步检索,然后再检查检索结果与查询图像的空间一致性
3.2 改进量化的匹配
由于视觉单词中的向量量化会抑制一些可能重要的细节,可以尝试采用以下策略进行改进量化的匹配。
策略1:计算多个不同的向量量化(使用不同的k-means聚类建立多个相似排序列表,然后对每张检索出的图像在不同列表中的排序求中位数)
策略2:使用大规模的词库(利用层级k-means(树形结构)等方法提高搜索效率)
策略3:搜索所有匹配查询图像的兴趣点
3.3 对图像搜索结果重排
可根据空间一致性采用RANSAC(随机采样一致)等算法进行重排
3.4 布局图像用于浏览
可采用多维缩放(MDS)等技术(类似谷歌地球地图放大的效果)
3.5 给图像预测标注
- Annotations from Nearby Words:将网页中图像周围的某些词作为关键词
- Anatations from the Whole Image:根据整个图像来预测多个标注词(方法可以是k近邻聚类)
- 用分类器预测相关词
- 将图像切分成很多块,对块预测标注(应用如新闻中的名字和脸匹配)
- 用分割生成标签