今天介绍 IJCV 2013 年的一篇文章，Selective Search for Object Recognition，这个是后面著名的DL架构 R-CNN 的基础，后续介绍 R-CNN 的时候，会发现 R-CNN 和这篇文章里介绍的算法非常类似。
做模式识别的人都知道，目标识别与目标检测是两个不同的东西，目标检测比目标识别要难得多，目标识别可以看做是一个分类问题，给定一张测试图，我们只要判断这张图里有没有某一特定的物体，而目标检测，需要在这张图上标出物体的具体位置，这可以看做是一个回归问题，不仅需要判断有没有，而且还要判断在哪里。
我们知道，同一类物体，在不同的图像中，会有不同的尺度，不同的位置，甚至会有不同的形状，所以，目标检测是要解决这样一个问题：
- 如何在任意给定的一张图像中检测到某一物体，这种检测要克服尺度的变化，位置的变化以及形状的变化。
一种最直观的方案就是利用图像的分割，先把图像分割成一个个的区域，然后对分割之后的区域做判别，所以这篇文章最重要的贡献就是把一个回归问题转换成一个分类问题，结合了分割与搜索。
图像分割一直是图像处理领域非常基础却又非常重要的一个应用，简单来说，图像的分割就是一种聚类，把相似的像素聚到一起，这样就形成一个个不规则的区域。图像分割最大的难点就在于确定聚类的准则，因为不同的准则，最终得到的结果会不同。
图像分割的精准与否，又会影响到最终的检测结果，所以这篇文章利用了一个 Hierarchical Grouping 的策略对图像进行聚类分割，简单来说，就是先对图像做一个初步的分割，把图像先分割成很多细碎的小区域，然后利用一些准则，将这些小区域再合并成大区域。文章里面，考虑了区域的相似性，设计了四种判别准则，分别是颜色，纹理，尺寸以及填充度。
颜色相似性
为了统计颜色的相似性，这里还是要用到颜色直方图的概念，我们知道彩色图像有 R,G,B 三个通道，每个通道应该是 0−255 共 256 个灰阶，为了简化运算，文章将 256 个灰阶先合并成 25 个灰阶，所以每个颜色通道是 25 个灰阶，三个颜色通道一共 75 个灰阶，将这75个灰阶先做一个统计，然后做一个归一化，就是这个区域的颜色直方图。两个区域的颜色相似性，就是比较两个区域的颜色直方图，将值较小的进行累加，得到最终的相似度，如下所示：
Scolor(ri,rj)=∑nk=1min(cki,ckj)
颜色直方图的一个好处是当两个区域合并的时候，新合并的区域的颜色直方图可以很快速的计算得到：
Ct=Nri×Ci+Nrj×CjNri+Nrj
Nri,Nrj 表示区域 ri,rj 的像素个数，
纹理相似性
为了统计纹理的相似性，文章用了高斯滤波，对每个区域做一个高斯滤波，高斯滤波一共有 8 个方向，将滤波后的区域做一个直方图统计，合并成 10 个 灰阶，所以 8个方向的高斯滤波生成了 80个灰阶，三个通道一共是 240个灰阶，同样要做归一化，再利用类似的公式计算纹理相似性：
Stexture(ri,rj)=∑nk=1min(tki,tkj)
尺寸相似性
这个准则是为了让小区域先合并，尺寸相似性的计算如下：
Ssize(ri,rj)=1−Nri+NrjNimg
Nri,Nrj 表示区域 ri,rj 的像素个数，Nimg 表示整张图像的像素个数。
重叠度
这个准则衡量两个区域的交集，重叠的部分有多少，这个准则的计算如下：
Sfill(ri,rj)=1−NBBij−Nri−NrjNimg
NBBij 表示包围区域 ri,rj 的最小区域， 从这个表达式可以看出，如果两个区域靠的越近，则 Sfill 越大，说明这两个区域越应该被合并。
最终的相似度，是这四个准则的线性叠加：
S(ri,rj)=a1Scolor(ri,rj)+a2Stexture(ri,rj)+a3Ssize(ri,rj)+a4Sfill(ri,rj)
确定了相似性的度量准则，接下来，我们就是要对区域进行合并，具体的算法如下所示：
先利用一个分割算法，对图像进行初步的分割，得到一个分割区域的集合 R={r1,r2,...,rn}，然后把所有的分割区域进行标记，接下来，对所有的区域两两之间计算相似性，所有的相似性度量可以组成一个集合 S。
接下来：
1） 从集合 S 中挑选相似性度量最大的一个 s(ri,rj)
2） 将区域 ri,rj 进行合并得到 rt
3） 将集合中含有 ri，rj 的的相似性度量都去除
4） 计算 rt 与其相邻区域的相似性，得到一个有关 rt 与其相邻区域的相似性度量集合 St
5） 将 St 与剩下的 S 合并
6） 将 R 与 rt 合并
如果 S 为非空集合，返回第一步，继续计算。
最后，可以提取出目标物体的一个矩形区域。
接下来，就是特征提取和训练了，这里用到的特征是 SIFT 加 BoW, 具体的流程如下所示：