BOW词袋模型.ppt

HashingBoWBig Data 1/30BoW词袋模型时间：2015/07/06HashingBoWBig Data 2/30提纲提纲背景SIFT特征总结BoW模型HashingBoWBig Data 3/30背景背景图像匹配难点1HashingBoWBig Data 4/30背景背景图像匹配难点2HashingBoWBig Data 5/30SIFTSIFT1.尺度空间的生成尺度空间理论目的是模拟图像数据的多尺度特征，高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像的尺度空间定义为：其中 是尺度可变高斯函数，(x,y)是空间坐标，是尺度坐标。的大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的值对应粗构高斯差分尺度空间(DOG scale-space)：HashingBoWBig Data 6/30关于尺度空间的理解说明：图中的2是必须的，尺度空间是连续的。在 Lowe的论文中，将第0层的初始尺度定为1.6，图片的初始尺度定为0.5.在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以 Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。HashingBoWBig Data 7/302.检测尺度空间极值点同一组中的相邻尺度（由于K的取值关系，肯定是上下层）之间进行寻找在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了 3 幅图像，高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像。HashingBoWBig Data 8/303.精确定位极值点通过拟合三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点（DoG算子会产生较强的边缘响应），以增强匹配稳定性，提高抗噪声能力。空间尺度函数 (1)求导，并令其为0，得到精确的位置 (2)在已经检测到的特征点中，要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点：把公式(2)带入公式(1)，只取前两项可得：若 ，该特征点就保留下来，否则丢弃。HashingBoWBig Data 9/30D的主曲率和H的特征值成正比，令为最大特征值，则令=，则：Dxx表示DOG金字塔中某一尺度的图像x方向求导两次通过拟合三维二次函数以精确确定关键点的位置和尺度。边缘响应的去除，一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个22的Hessian矩阵H求出：导数由采样点相邻差估计得到。HashingBoWBig Data 10/304.为每个关键点指定方向参数利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT特征区域。HashingBoWBig Data 11/305.关键点描述子的生成首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以特征点为中心取88的邻域作为采样窗口，将采样点与特征点的相对方向通过高斯加权后归入包含8个方向直方图，最后获得228的32维特征描述子。HashingBoWBig Data 12/30HashingBoWBig Data 13/30BoWBoW模型模型US Presidential Speeches Tag Cloudhttp:/chir.ag/phernalia/preztags/HashingBoWBig Data 14/30BoWBoW模型模型Bag of wordsBag of words:最初被用在文本分类文本分类中，将文档表示成特征矢量。基本思想基本思想:假定对于一个文本，忽略忽略其词序和语法、句法，仅仅将其看做是一些词汇的集合，而文本中的每个词汇都是独立的。简单说就是讲每篇文档都看成一个袋子（因为里面装的都是词汇，所以称为词袋，Bag of words即因此而来），然后看这个袋子里装的都是些什么词汇，将其分类。如果文档中猪、马、牛、羊、山谷、土地、拖拉机这样的词汇多些，而银行、大厦、汽车、公园这样的词汇少些，我们就倾向于判断它是一篇描绘乡村的文档，而不是描述城镇的。举个例子，有如下两个文档：文档一：Bob likes to play basketball,Jim likes too.文档二：Bob also likes to play football games.基于这两个文本文档，构造一个词典：Dictionary=1:”Bob”,2.“like”,3.“to”,4.“play”,5.“basketball”,6.“also”,7.“football”，8.“games”,9.“Jim”,10.“too”。这个词典一共包含10个不同的单词，利用词典的索引号，上面两个文档每一个都可以用一个10维向量表示（用整数数字0n（n为正整数）表示某个单词在文档中出现的次数）：1：1,2,1,1,1,0,0,0,1,12：1,1,1,1,0,1,1,1,0,0HashingBoWBig Data 15/30BoWBoW模型模型为什么要用BOW模型描述图像：SIFT特征虽然也能描述一幅图像，但是每个SIFT矢量都是128维的，而且一幅图像通常都包含成百上千个SIFT矢量，在进行相似度计算时，这个计算量是非常大的，通行的做法是用聚类算法对这些矢量数据进行聚类，然后用聚类中的一个簇代表BOW中的一个视觉词，将同一幅图像的SIFT矢量映射到视觉词序列生成码本，这样每一幅图像只用一个码本矢量来描述，这样计算相似度时效率就大大提高了。HashingBoWBig Data 16/30BoWBoW模型模型1.Extract features2.Learn“visual vocabulary”3.Quantize features using visual vocabulary 4.Represent images by frequencies of“visual words”HashingBoWBig Data 17/22BoWBoW模型模型BoW计算过程BoW编码过程HashingBoWBig Data 18/30BoWBoW模型模型TF第一个例子在介绍BoW词袋模型时一般资料里会经常使用到，就是将图像类比成文档，即一幅图像类比成一个文档，将图像中提取的诸如SIFT特征点类比成文档中的单词，然后把从图像库中所有提取的所有SIFT特征点弄在一块进行聚类，从中得到具有代表性的聚类中心(单词)，再对每一幅图像中的SIFT特征点找距离它最近的聚类中心(单词)，做词频(TF)统计（聚类中心）单词 x1 x2 x3128提取sift图像im假设提取到了三个特征点假设计算得x1与c10最近，x2与c7最近，x3与c7最近，则words=10,7,7HashingBoWBig Data 19/30BoWBoW模型模型TF词频（term frequency，TF）指的是某一个给定的词语在该文件中出现的次数。假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是 0.03(3/100)。（聚类中心）单词 x1 x2 x3128提取sift图像im假设提取到了三个特征点假设计算得x1与c10最近，x2与c7最近，x3与c7最近，则words=10,7,7HashingBoWBig Data 20/30BoWBoW模型模型IDF做完词频(TF)统计后，为了降低停用词带来的干扰，可以再算个逆文档词频(IDF)，也就是给TF乘上个权重。x1 x2 .xi x13331000 .词频1 2 i 1333统计每个单词的文档数目1000*1333设单词数目为1000个，文档数目（即图像）个数为1333个2110 c1 .1 +1 +.0 +0 +1以统计第一个单词文档数为例包括单词c1的文档数x1即图像x1包括单词c1，故该文档计入加1，没有包含c1的为0，概括起来：统计非零元素的个数。HashingBoWBig Data 21/30BoWBoW模型模型IDF一个计算文件频率(DF)的方法是测定有多少份文件出现过“母牛”一词，然后除以文件集里包含的文件总数。所以，如果“母牛”一词在1,000份文件出现过，而文件总数是10,000,000份的话，其逆向文件频率就是 9.21(ln(10,000,000/1,000)。最后的TF-IDF的分数为0.28(0.03*9.21)。x1 x2 .xi x13331000 .词频1 2 i 1333统计每个单词的文档数目1000*1333设单词数目为1000个，文档数目（即图像）个数为1333个2110 c1 .1 +1 +.0 +0 +1以统计第一个单词文档数为例包括单词c1的文档数x1即图像x1包括单词c1，故该文档计入加1，没有包含c1的为0，概括起来：统计非零元素的个数。HashingBoWBig Data 22/30BoWBoW模型模型TF*IDF对于上传上来的查询图像，提取SIFT然后统计tf后乘上上面的idf便可得到id-idf向量，然后进行L2归一化，用内积做相似性度量。HashingBoWBig Data 23/30BoWBoW模型模型实验数据库:Benchmark ImagesThe set consists of N groups of 4 images each.All the images are 640 x480.http:/vis.uky.edu/stewe/ukbench/HashingBoWBig Data 24/30BoWBoW模型模型在线查询HashingBoWBig Data 25/30BoWBoW模型模型在线查询HashingBoWBig Data 26/30BoWBoW模型模型Demo演示在CMD中输入以下代码：python search.py-i dataset/train/ukbenchxxxxx.jpgHashingBoWBig Data 27/30BoWBoW模型模型缺点：1 没有考虑位置因素 2 是特征的0阶统计HashingBoWBig Data 28/30BoWBoW模型模型缺点：1 没有考虑位置因素 2 是特征的0阶统计 VLAD Fisher VectorHashingBoWBig Data 29/30END