Object Detection vs. Object Recognition

        目标识别算法就是识别出一幅图中的目标。它将一整幅图像作为输入，并且输出图像中目标的类标签和类概率。例如，一个类标签可以是“狗”，并且相关的类概率是97%。另一方面，目标检测算法不仅可以告诉你图像中出现的目标，还可以输出图像中目标的位置即边界框（x，y，width，height）。目标检测算法的核心就是目标识别算法。假设我们训练了一个目标识别模型，它可以识别图像块（patch即sub-regions，将一幅图像分成许多小块）中的狗。这个模型可以告诉我们图像中是否有狗，但它不会告诉我们狗的位置。为了定位这个目标，我们必须挑选图像的patch，然后对这些patches应用目标识别算法。目标的位置由目标识别算法返回的类概率高的图像的patch位置给出。生成较小patches的最直接方法称为滑动窗口法（sliding window approch）。滑动窗口法有几个限制，但这些限制被一类称为“区域建议”法（Region Proposal algorithm）所克服，选择性搜索（selective search）是目前最流行的region proposal algorithm之一。

Sliding Window Algorithm

        在滑动窗口方法中，我们在图像上滑动一个框或窗口来选择一个patch，并且使用对象识别模型来对窗口覆盖的每个图像patch进行分类，它是对整个图像进行彻底搜索。我们不仅需要搜索图像中所有可能的位置，还需要在不同scale内搜索。这是因为目标识别模型一般在一个特定的scale（或尺度范围）下进行训练。这导致需要对成千上万个图像patches进行分类。问题还不止于此。滑动窗口适用于固定长宽比的物体，例如人脸或行人。图像是三维物体的二维投影。根据拍摄角度，物体的长宽比和形状等特征会发生显著的变化。当我们使用多个长宽比进行搜索时，滑动窗口法在计算上非常昂贵。

Region Proposal Algorithm

      目前我们使用region proposal algorithms来解决这个问题。这些方法将图像作为输入，将对应于图像中最有可能是目标的所有patches的边界框作为输出。这些region proposals可能是嘈杂的、重叠的，并可能不完美地包含目标，但在这些region proposals中，将会有一个非常接近于图像中的实际目标。我们可以使用目标分类模型对这些proposals进行分类，概率得分高的region proposal是目标的位置。region proposal algorithms使用分割来识别图像中的目标。在分割中，我们根据颜色、纹理等标准对相邻的相似区域进行分组。与我们在所有像素位置和所有scales下寻找目标的滑动窗口方法不同，region proposal algorithm通过将像素分组为较少数量的片段来工作。因此，最终生成的proposal的数量要比滑动窗口方法少很多倍，可以减少我们需要分类的图像patches的数量，这些生成的region proposal具有不同的scales和宽高比。region proposal method的一个重要特性是具有非常高的召回率。这是一种奇特的说法，即我们的list of region proposals中必须包含我们正在寻找的目标区域。为了完成这一目标，我们的regional proposal list可能会包含许多非目标区域。换言之，region proposal algorithm捕捉到所有的目标区域的同时也会捕捉到大量的非目标区域，这些误报大多会被目标识别算法拒绝。当我们有更多的误报并且精度受到轻微的影响时，检测所需的时间就会增加。但是高召回率仍然是一个好主意，因为缺少包含实际目标的区域会严重影响检测率。已有一些region proposal方法被提出，例如objectness、Constrained Parametric Min-Cuts for Automatic Object Segmentation、Category Independent Object Proposals、Randomized Prim和Selective Search，其中Selective Search最为普遍，因为它快速又具有很高的召回率。

What is Selective Search?

        选择性搜索是一种用于目标检测的区域建议算法。它的设计速度很快，召回率很高。它是基于颜色纹理、大小和形状兼容性计算相似区域的层次分组。选择性搜索首先使用Felzenszwalb和Huttenlocher基于图的分割方法，根据像素的强度对图像进行过度分割，算法的输出如下图所示，右边的图像包含使用纯色表示的分割区域。

     我们可以在这个图像中使用分割部分作为region proposals吗？答案是不能，原因如下：

    1、在原图中的大部分实际目标包含两个或多个分割部分。
    2、使用此方法无法为遮挡对象生成region proposals，例如被杯子覆盖的盘子或装满咖啡的杯子。      

       如果我们试图通过进一步合并相邻的相似区域来解决第一个问题，我们将得到一个包含两个目标的分割区域。完美的分割不是我们的目标，我们只是想预测许多region proposals，例如使其中一些region proposals与实际目标有很高的重叠。选择性搜索使用来自Felzenszwalb和Huttenlocher的过度分割方法作为初始种子，一个过度分割的图像看起来像这个样子。

        选择性搜索算法会将这些过度分割作为初始输入，并且执行以下操作：

      1、为分割部分对应的所有边界框添加到区域建议列表中。     
      2、根据相似度对相邻分割部分进行分组。         
      3、转到第1步。       
       在每次迭代中，将形成的更大的分割部分添加到区域建议列表中。因此，我们采用自底向上的方法，从较小的分割部分创建到较大的分割部分，这就是我们所说的使用Felzenszwalb和Huttenlocher的过度分割方法来计算分层分割。

      这幅图显示了分层分割过程的初始、中间和最后一步。

Similarity

      让我们更深入地研究如何计算两个区域之间的相似性。选择性搜索使用4种基于颜色、纹理、大小和形状兼容性的相似性度量方法。

Color Similarity

      对图像的每个通道计算25个bin的颜色直方图，并将所有通道的直方图串联起来，得到一个25*3=75维的颜色描述符，两个区域的颜色相似性基于直方图的交集，可以计算为：
                                                           

​是颜色描述符中​bin的直方图值。

Texture Similarity

        对每个通道提取8个方向的高斯导数来计算纹理特征，对每个方向和每个颜色通道计算一个10-bin的直方图，得到10 * 8 * 3 = 240维特征描述符。利用直方图交集计算两个区域的纹理相似度。

                                                        
是纹理描述符中bin的直方图值。

Size Similarity

      大小相似性鼓励较小的区域尽早合并，它确保在图像的所有部分形成所有尺度的region proposals。如果不考虑这种相似性度量，单个区域将会逐个吞噬所有较小的邻近区域，因此仅在该位置生成多个尺度上的region proposal。大小相似性定义为：
                                                        

size(im)是图像的像素大小。

Shape Compatibility

      形状兼容性度量两个区域(和)相互匹配的程度。如果符合，则合并它们以填补空白，如果它们甚至没有相互接触，就不应该合并。形状兼容性定义为：
                                             

是围绕和的包围框。

Final Similarity

      两个区域的最终相似性定义为上述4个相似性的线性组合。
              
               

其中和是图像中的两个区域或分段，表示是否使用相似性度量。

选择性搜索的优点

1、计算效率优于滑动窗口。
2、采用子区域合并策略，有不同的scale。
3、具有较高的召回率。

参考资料
Selective Search for Object Detection (C++ / Python) | Learn OpenCV

名词解释

What is pixel intensity？

        像素强度是像素亮度， 每个象素都有相应的亮度，这个亮度和色相是没有关系的，同样的亮度既可以是红色也可以是绿色，就如同黑白(灰度)电视机中的图像一样，单凭一个灰度并不能确定是红色还是绿色。 所以，像素的亮度和色相是无关的。 像素的亮度值在0至255之间，靠近255的像素亮度较高，靠近0的亮度较低，其余部分就属于中间调。这种亮度的区分是一种绝对区分，即255附近的像素是高光，0附近的像素是暗调，中间调在128左右。