selective search算法是一種圖像分割的算法，能夠找到圖像中可能存在目标物體的區域，是RCNN算法的基礎。
參考：
- 《Selective Search for Object Recognition》代碼及論文 https://www.koen.me/research/selectivesearch/
- 算法python實作 https://github.com/AlpacaDB/selectivesearch
- https://www.cnblogs.com/zyly/p/9259392.html
1、快速開始
作者首頁上給出了算法的MATLAB實作，github上有一個較為簡單的實作，https://github.com/AlpacaDB/selectivesearch。下面的例子基于github上的實作，可以通過 pip install selectivesearch 安裝。
測試代碼如下，用的是http://www.lenna.org/下載下傳的lenna圖檔。
# coding:utf-8
from selectivesearch import selective_search
import cv2
img = cv2.imread("len_std.jpg")
img_lbl, regions = selective_search(img, scale=500, sigma=0.3, min_size=10)
print("regions counts", len(regions))
candidates = set()
for r in regions:
# lenna标準圖的大小是256乘256，這裡選取像素個數在(5000,6000)的候選框
if r['size'] < 5000 or r['size'] > 6000:
continue
candidates.add(r['rect'])
print("candidates number",len(candidates))
for x,y,w,h in candidates:
cv2.rectangle(img,(x,y),(x+w,y+h),color=(0,255,0),thickness=2)
cv2.imwrite("lena_out.png",img)
cv2.imshow("",img)
cv2.waitKey(0)
程式運作後找到了123個區域，在這些候選區域中限制像素個數處于(5000,6000)，經過過濾剩下了3個候選框，如下圖所示。可以看出中間的框基本上完整的包括了lenna的臉部。
2、selective search基本流程
selective search算法的基本思想是先将整張圖檔分成多個較小的區域，然後再通過計算這些區域之間的相似度，将比較相似的兩個區域融合在一起，以此類推。算法流程如下所示。
上面算法中提到的文獻[13]是Efficient Graph-Based Image Segmentation，這篇論文提出了一個圖像分割的方法，具體細節可以參考https://blog.csdn.net/root_clive/article/details/93973621。
上述算法中的要點在于如何計算兩個區域之間的相似度
，論文中給出的計算公式為：
其中
，為了保證多樣性，一般
取1。兩個區域的相似度考慮了4個不同的角度，分别為：
(1) 顔色相似度
将某個區域
内的像素值分成25個bins，那麼3個通道就組成了長度為75的特征向量
，然後對
進行L1歸一化(也就是給
的每一個值除以區域
内像素點的個數)，特征向量
實際上表示了像素值的分布，于是區域
和區域
的顔色相似度為：
上面這個計算式度量了兩個區域像素值分布的重疊程度。當兩個區域合并之後，新的區域的特征向量
就是合并前各個特征向量之和，但是由于特征向量
進行了L1歸一化，是以沒有歸一化的特征向量為
，是以下面的公式用來計算合并後的特征向量。
(2) 紋理相似度
論文中參考了《Exploring features in a bayesian framework for material recognition》中的做法(沒有仔細研究，大意是選取了8個方向，使用方差為1的高斯濾波，然後将結果分成10個bins，那麼每個通道就會有80個bins，3個通道總共240個bins，然後進行L1歸一化)。紋理相似度的計算方法和顔色相似度的計算方法相同，如下所示：
兩個區域合并後的紋理特征向量計算方法也和顔色特征合并計算方法類似。
(3) 讓較小的區域較早的融合
如果兩個區域比較小的話，這個值相應會比較大。
(4) 度量兩個區域的比對程度
如果某一個區域被另一個區域完全包裹的話，那麼這兩個區域就應該被融合，或者兩個區域幾乎不接觸，這兩個區域應該就屬于不同的區域，根據這樣的思想，論文中給出了一種簡單的計算公式。
其中
是區域
和區域
的外接矩。
2、候選框過濾
在文章開始部分我們通過selective search從一張圖中提取出來123個候選框，數量顯然是太多了，不便于後面的特征提取和分類，論文中提出了一種過濾的政策。
首先論文提出了3種不同的方案，如下圖所示，第一種方案使用HSV顔色空間，C+T+S+F分别是前面介紹的四種相似度
，
，
，
，第二種方案是Selective Search Fast(RCNN論文中就是用的這種方案)，分别用了HSV和Lab兩種顔色空間，然後使用了C+T+S+F和T+S+F兩種相似度計算方法，超參數k使用了50和100兩個不同的值，是以總共會有
個分割結果。同理第三種方案會産生80個分割結果。
那麼怎麼将80種結果綜合在一起呢？首先可以給不同的層級賦予不同的權重，這個算法是先将原圖分割成很多個小區域然後再融合的，将最後一次融合的層級記為
，層級
的時候權重為1，以此類推。将80個不同方案中不同層級的分割區域的權重相加，然後按照權重排序，排在前面的就是最可能存在有效目标的區域。
這裡有個疑點，論文中沒有明确指出，就是怎麼尋找不同分割方案中的相同區域，如果要求兩個區域必須所有像素位置相同似乎有些不可行，或者可以采用IOU來判斷？
上面的方法存在一個問題，區域越大，在不同方案中出現的頻率越高，疊加之後的機率越大，是以這種方法排序之後會傾向于找到較大的區域。論文中提出給權重乘以一個系數
，其中RND是[0,1]之間的随機數。引入了随機之後，可以一定程度上避免較大區域一定排在前面的問題。
3、selective search應用于目辨別别
在通過selective search算法将圖形分割成多個區域之後，論文中提出了一種基于SVM的目辨別别方法，下面的流程圖來自論文。
在訓練階段，初始的正樣本是ground-truth标注的框，用selective search從圖中選出候選框，然後将這些候選框中和ground-truth重疊20%~50%的框作為負樣本，将選出的負樣本中重疊超過70%的隻保留一個，論文中通過随機删除負樣本使得每個類别的負樣本數量在2000以下。然後從每個樣本中提取360000個特征 (圖像特征提取這一部分不是很了解，大意是提取SIFT特征和四層空間金字塔特征等)，送入SVM(togram intersection kernel，這個核函數在圖像分類中比徑向基效果好)進行訓練，訓練中會疊代add hard negative examples。
在推斷階段，将selective search産生的候選區域提特征送入模型，按照得分高低排序，和最高得分框重疊超過30%的框将被删除。(SVM算法輸出的是樣本屬于正樣本或負樣本，這個得分是怎麼得出的？)