Efficient Subwindow Search论文笔记

1. Introduction

文章介绍了一种称为Efficient Subwindow Search(ESS)的方法,用来定位物体在图像中的位置。该方法比滑动窗(Sliding Window)方法更加高效,具有线性的时间复杂度。而滑动窗方法的时间复杂度为$o(n^4)$。
该方法是在图像中找到目标的位置,画出边界框(bounding box)。

1.1 Sliding Window

我们首先来看看Sliding Wondow是如何操作的。简单的说,就是对每一个候选区域$R$,通过quality function $f$,计算出一个分类的分数。然后选取所有候选区域中分数最高的那个区域。用公式来表示就是:
$$R_{obj} = argmax_{R\subseteq I} f(R)$$
但是刚才提到了, 滑动窗方法的时间复杂度为$o(n^4)$,实在太耗时,就提出了很多减小时间复杂度的方法来加快搜索,比如粗略地只搜索合理的区域,或者只把特定大小的区域作为候选窗口。这些方法虽然缩短了时间,但都牺牲了鲁棒性,也就是准确率肯定下降了。那么下面就来看看作者的ESS算法好在哪里

2. Efficient Subwindow Search (ESS)

ESS是基于branch-and-bound search分支定界搜索的,但是又跟以往的分支定界搜索不太一样。因为它在quality function的选择上更加灵活。

ESS直观理解的思想是这样的:

虽然存在着大量的候选区域,但是在这些候选区域中却只有几个包含目标物体的区域。所以说,对于每一个候选区域都计算quality function是完全没有必要的。我们应该直接定位到包含最高分的那个区域,而忽略其他搜索空间。

一个矩形可以用四元坐标表示$(t, b, l, r)$,也就是top, bottom, left和right
在此基础上我们增加一些改动,用$T$来替换$t$,这里$T = [t_{low}, t_{high}]$,表示一个范围。其它三个元素b、l、r也是如此。
如此一来,原来仅仅能表示一个矩形的四元坐标就变成了能够表示一个矩形范围的集合的四元坐标$T=[T, B, L, R]$,如下图所示:
Alt text

有了这种矩形集合的表示方法之后,我们对每一个集合,在集合中计算出最高的quality score。当ESS算法识别出一个矩阵的quality score能够作为所有剩下候选区域的上界的时候,算法就终止了。

ESS使用最佳优先原则(best-first manner)来对候选区域进行搜索。这可以使用优先队列(priority queue)来实现。伪代码如下:
Alt text

2.2 Bounding the Quality Function

对于一个指定的quality function $f$, 我们还需要另一个函数$\widehat{f}$来规定$f$的上界。这里$\widehat{f}$的选择需要满足两个条件:
Alt text

为了满足$i)$式,一方面我们可以通过穷举法来选取$\widehat{f}$,另一方面我们可以直接设定一个很大的$\widehat{f}$。下文就举了三个例子来说明对于不同的quality function,我们如何来选取合适的$\widehat{f}$。

3.Application I: Localization of non-rigid objects using a bag of visual words kernel

首先我们从训练图像中提取出特征,如SIFT特征,用codebook可以量化为矢量。
然后我们用直方图集群(cluster histgorams)来表示图片或者某个区域,每个直方图表示每个集群出现的特征点数。然后这些直方图被拿来去训练SVM。

3.1. Construction of a Quality Bound

一个典型的线性SVM的decision function如下:

$$f(I) = \beta + \sum_i \alpha_i < h, h^i >$$

设$w_{j} = \sum_i \alpha_{i} h_j^i$,然后我们可以重写这个公式:

$$f(I) = \beta + \sum_{j=1}^n w_{c_j}$$

要获得$\widehat{f}$,由于$ f= f^+ + f^-$,而$ f^+$均为正,$f^-$均为负。故我们可以得到:

$\widehat{f}(\Re) := f^+(R_{max}) + f^-(R_{min})$

用积分图像的方法可以使得时间复杂度变成 $o(1)$