research►note

[Notes]Unsupervised Discovery of Mid-Level Discriminative Patches

本期论文的题目是”Unsupervised Discovery of Mid-Level Discriminative Patches”, 发表于ECCV2012，幕后老板是CMU的Efros。
有主页有代码神马的paper最友好了。

在Tomasz Malisiewicz(Exemplar的作者)的CVPR2013感想中提到了计算机视觉研究的三大趋势，其中之一就是“Mid-Level Patches”，其中就提到了这篇文章，觉得mid-level patch这个概念很新鲜，于是找来读了一下。

Overview

“Mid-Level Patches”是一种介于low-level和semantic特征之间的一种特征，具有两大特性: representative and discriminative(有点类似于NLP里的TF-IDF的概念)

  • representative(代表性): 出现频率高
  • discriminative(区分度): 必须和其他的patch不同

用完全非监督式的方法进行学习，不断在“聚类”-“训练判别式的分类器”这两个阶段迭代，最终达到收敛. 将学习结果应用于场景分类(scene classification)问题，AUC超过了之前最好的方法。

  • 我们需要怎样的特征？

    • low-level (bottom-up): 不能提供足够的信息，有可能在图像的任何位置产生响应，泛化能力差
    • semantic (top-down): 把整幅图像当作特征的基本单位，需要大量的训练样本，区分度不够

  • 主要相关工作: Poselet

    • Poselet是一种heavily-supervised算法

  • Intuitive Solutions

    • 说到非监督学习，当然首先会想到像K-means这样的聚类算法了，很遗憾的是，K-means的效果并不好。K-means的分类判据(如欧式距离，L1范数等等)并不一定能够反映visual similarity. 如果想要得到visual similar patch，就必须使用判别式的分类器，比如SVM. 这样就形成了“先有鸡还是先有蛋”的悖论。好的聚类结果依赖于准确的相似性度量准则，而相似性度量准则又依赖于好的聚类结果。虽然这个“鸡蛋”问题可以通过判别式的迭代聚类(iterative discriminative clustering)得到解决，但聚类会产生过多的类别，这个算法不适用于海量真实数据。

    • 本文所采用的方法是用”detection”来替代判别式的聚类，对每个类别训练一个分类器，用于检测与其相似的patch. 这个方法与DPM很类似，但是取消了patch必须和原始模型相差无几的限制条件。

    • SVM的缺点是具有“记忆”，为了增强泛化能力，采用了”cross validation”策略，将训练集分成相同大小无交集的两个子集合，交替进行训练和检测，直到收敛。

算法

  • Goal: discover a relative small number of discriminative patches at arbitrary resolution which can capture the “essensce” of that data

algorithm

  • Initialization (line1-3)
    将数据分为“discovery dataset” $$D$$和”natural world dataset” $$N$$. 为了进行cross-validation training, 将$$D$$和$$N$$进一步分为$$D_1, D_2, N_1, N_2$$.
    对$$D_1$$中的所有元素，计算其HOG特征金字塔(level = 7)。 从$$D_1$$中随机选择$S$个样本（不包括高度重合的样本和gradient energy低的样本），在HOG特征空间内进行k-means聚类（将K设定为一较高的值），得到聚类结果，将样本数小于3的类去除(pruning)
  • Iterative (line 4-10)
    对K个cluster分别训练SVM分类器，将cluster内的样本作为正样本，$$N_1$$中的样本作为负样本。在$$D_2$$集合上使用SVM分类器进行检测top m instances. 交换训练集合，进行迭代训练，直到聚类结果收敛

Ranking discriminative patches

$$score = \alpha \cdot purity + \beta \cdot discriminativeness$$

  • Purity
    classifer confidence of the cluster members, i.e. top r成员的svm的输出prob_estimation之和
  • Discriminativeness
    具有discriminativeness的patch不易出现在natural world $$N$$中，即firing in $D$与firing in $$D \cap N$$的比值

Doublets

A cluster converges to two or more “concepts”. 例如，一个cluster的patch同时包含”摩托车手”和”摩托车”这两个视觉元素。一张图像上的所有的firing, doublets candidates通常具有很高的空间相关性。为了消除”doublets”, 采用second-order spatial co-occurrence relationships方法.

Evaluation

Experiment Result

Pascal VOC 2007

使用clustering的评测指标purity和coverage, 参见论文Fig. 5.

  • purity: cluster member确实属于同一cluster的比例
  • coverage: number of images in dataset fired on by a given cluster

MIT Indoor-67

Outperforms current state-of-the-art method (GIST+SP+DPM), see Table 1.