Charles Z.

相似图像搜索入门指南

Filed under Computer Vision on 26 Mar, 2014


Object retrieval with large vocabularies and fast spatial matching 这篇文章讲述的是近似k聚类，Approximate k-means方法，首先我们考虑的是如下这个问题： 有一篇文本A，怎样在库中找到与它最匹配的一篇文章？

在信息检索中的重要发明TF-IDF

  • TF(Term frequency)-关键词词频
    • 是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词
    • TF = M / N
  • IDF(Inverse document frequency)-逆向文本频率
    • 是用于衡量关键词权重的指数
    • IDT = log(D / Dw)
    • D为文章总数，Dw为关键词出现过的文章数

基于空间向量的余弦算法

预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。

  • 预处理

    • 主要是进行中文分词和去停用词
    • 去停用词按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。
    • 使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除

  • 文本特征项选择与加权

    • 根据剩下词的频度确定若干关键词
    • 频度计算参照TF公式
    • 加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值计算参照IDF公式

  • 向量空间模型VSM及余弦计算

    • 向量空间模型的基本思想是把文档简化为以特征项（关键词）的权重为分量的N维向量表示
    • 模型假设词与词间不相关，用向量来表示文本，从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性
    • 上述词与词间不相关的假设造成这个模型无法进行语义相关的判断，向量空间模型的缺点在于关键词之间的线性无关的假说前提
    • 假设一篇文档D中有a、b、c、d四个特征项，那么这篇文档就可以表示为D（a，b，c，d）
    • 在向量空间模型中，两个文本D1和D2之间的内容相关度Sim(D1，D2)常用向量之间夹角的余弦值表示

图像相似度计算

  • 最简单的计算文本相似度的问题基本就是这样，那么现在又有一个问题 如何计算两幅图像之间的相似度？

  • 搞CV的大师们请搞NLP的大师们吃了个饭，学会了TF-IDF！

  • 我们知道一幅图像可以有很多特征，这个特征就可以就构上述TF-IDF的中T（term），但是有一个问题需要解决，就是文本中的词是相对固定的。但是图像的特征之间没有完全一致，这就需要我们将特征进行归类，在多维空间上，把相邻的特征归成一堆一堆的，专业名词叫做聚类！比方说我们聚类成了M堆，下次再有一个新的特征Q来了，我们可以分别比较Q和M堆依次比较距离的远近，将Q纳入最近的那一个类别里。

  • 聚类后的特征向量还是以一串数值表示的(它不像词频向量有显著的含义),我们叫它视觉词，Visual Word
  • 聚类算法有很多，其中最经典的最简洁的是k-means。我们今天就是谈对它的改进

k-means算法过程

输入：k, data[n];

  1. 选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1]；
  2. 对于data[0]….data[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；
  3. 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数；
  4. 重复(2)(3)，直到所有c[i]值的变化小于给定阈值。

时间复杂度分析：

  • 第2步的时间复复杂度是O(nk),第3步的时间复杂度是O(n)
  • k-means的时间复杂度是O(nk+n) = O(nk),其中n是样本数，k是聚类的数量

通常k不会太小，（我正在做的一个应用，在50m随机选择聚类成2m个）所以时间复杂度相当之高！带来一个问题，如何进行简化？

Approximate K Means

  • AKM是传统k-means的一种替代，KM中，时间主要花费在计算每一个point和每一个cluster之间的距离。
  • 我们使用相似最近邻（Approximate Nearest Neighbor）方法替代上述的计算
  • 使用一个包含8颗Random kd-tree的森林
  • 在Random kd-tree中的随机体现在维度划分的值是在中值附近随机选择，这样8颗树所形成的划分互相交叠，能够减弱量化效应
  • 所谓量化效应指的是落在两个分界边界的这些特征容易被划分到错误的区域中。（高位特征非常容易落在边界上，原因是curse of dimensionality,Nearest neighbours query performance,U. Shaft,J. Goldstein,K. Beyer文章中提到）
  • 一个新的数据点通过如下方式被安排在一个类中心上：最开始，每一棵树都下降到一个叶子节点上，到每一个可分边界的距离记录在一个优先队列中，我们迭代的从所有树种选择最最可靠的分支，持续将unseen nodes添加到优先级队列中。当已经遍历过的树的路径达到一个指定的值的时候，我们就停止。
  • 通过这样的方法，我们可以使用更多的树而不会显著的增加搜索时间

附：KD-TREE

  • 表现形式上是一颗二叉查找树
  • 每一个分支点在不同的维度上进行划分，维度的查找是当前点集中方差最大的一个维度
  • 维度划分的值可以是该维度上的中值，也可以是平均值

参考

Show Comments