# Selective Search for Object Recognition Paper Note
###### tags: `paper notes` `deep learning`
## 1.Intro:
* 長久以來 在做圖片辨識前都要先做劃分圖片區域(segmentation)
* **Semention的目的在於將圖片中的每一個物件劃分開來，以便對各個物件做更進一步的分析**
* 4張圖片的各個Region都有不同的特性
* 由於圖片本身是有層次(hierarchical)的，分析的方法當然也是，因此不存在用一個單一策略去解決所有的情況。
* Exhaustive serach雖然不會漏掉任何一個object，但它所需要的計算量太大了，因此常常會做一些限制 (使用粗略的搜尋框、固定的長寬比等等)來讓它**可達成**
* **但是在大部分情況，仍然還是有太多window需要search。**
---
* Segmentation使用圖片的結構來產生物件的可能位置
* Exhaustive serach則抓取了所有可能的位置
* 這篇paper的目的就在於結合這兩個方法，並且增加技巧的多樣性，以應付盡可能多的情況
---
* 使用Pascal VOC detection challenge的數據集來評估SS
* 主要是根據bounding boxes這方面來評估quality
---
### Main research questions
* (1) 作為SS實作segmentation時，什麼是一個好的多樣化方法呢?
* (2) SS在圖片中創造一小群高品質區域的時候有多有效率?
* (3) 在物件辨識上，我們可以利用SS去使用更強大的分類器和appearance models嗎?
---
## 2.Related work:

### Exhaustive Search
* 在本篇論文提出之前，通常使用HOG+SVM做物件辨識
* 雖然有很多[緩解其限制的方法](https://www.robots.ox.ac.uk/~vgg/publications/2009/Lampert09a/lampert09a.pdf)提出來，但每張圖片需要掃過的window至少還是有10萬個
* **物件辨識還是一直圍繞在HOG+SVM**

* 補充:
[HOG:通常用於物件檢測的特徵描述符號。依賴於影像內物件本身的特性而擁有梯度或邊緣方向的分佈。在每個區塊的影像內計算梯度。區域被認為是畫素網格，其中梯度由區塊內畫素強度的變化幅度和方向構成](http://alex-phd.blogspot.com/2014/03/hog.html)

### Segmentation
* 之前的方法是使用單一且強大的策略來應付各種情況

* SS則是利用多種策略來應付、分割，不僅有較低的運算需求而且分別處理不同的圖片條件會使得結果更一致、更好，還因為結果一致的關係讓它是可以被評估的。

### Other sampling method (不太重要)

* 1.隨機抽樣boxes，挑選出擁有最高物件性(objectness)的當成物件，用來減少windows的數量
* 2.使用visual words的Bags-of-words model，學習各個viusal words和物件位置的關係，以預測新圖片的物件位置

小結.
--
**不同於exhaustive serach, SS產生一小群類別不同的獨立物件位置**
**不同於Segmentation專注在單一個最好的演算法，SS使用多種策略去處理**
**不同於在隨機抽樣的boxes上學習objectness, SS使用bottom-up的分組流程去產生更好的物件位置**

---
## 3.Selective Search

**核心理念:**

**Capture all scales**
- Selective search 把任何大小的物件都考慮進去

**Diversification**
- diverse set of strategies to deal with all cases

**Fast to Compute**

- The goal of selective search is to yield a set of possible object locations for use in a practical object recognition framework
---
### 3-1 Selective Search by Hierarchical Grouping

**起始狀態:使用[另一篇論文的方法](http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf)拿到一小群的起始$R$(starting regions)**

接下來使用貪心演算法迭代進行:

1.計算所有鄰近區域之間的相似度 把所有相似度都放到集合$S$中

2.把兩個最相似的區域($ri$和$rj$)合併在一起 並把原本$ri$和$rj$的相似度從$S$中刪掉

3.計算已合併區域($rt$)和鄰近區域的相似度 把新的相似度放到$S$中並把$rt$放入$R$中

結束迭代後從所有$R$中輸出$L$

* $S$(similarity):所有的相似度集合
* $R$(Regions):可能有物件的區域集合
* $ri$ , $rj$是兩個相似區域
* $rt$是合併$ri$和$rj$之後的合併區域
* $L$:物件位置的可能結果(最終輸出)

### 3-2 Diversification Strategies

利用以下三種方法來達成SS的Diversification
(1) a variety of colour spaces with different invariance properties
(2) different similarity measures $sij$
(3) by varying our starting regions

---
#### **(1).為了能在不同的場景和亮度條件下都能解釋圖片，把前面提到Hierarchical Grouping algorithm在相同的其他性質下用在不同的顏色空間結果出來就會是這個圖**

* +是不變
* -是會變
* +/-是局部變
* 分數就是有3個顏色通道中有幾個不變 例如1/3就是3個通道有1個不變

---
#### **(2)-1 把顏色做成直方圖 每個通道都做一個 而每個直方圖都做出25個區間(bins)**

* The size of a resulting region is simply the sum of its constituents: size($rt$) =size($ri$) +size($rj$).

**(2)-2 測量texture similarity**

在不同區塊上使用SIFT-like演算法:

* 對每個colour channel的八個方向都做高斯微分 得到梯度統計
* 對每個方向和每個colour channel都使用size=10的bin擷取出來做成直方圖



**(2)-3 小區域優先合併**

**(2)-4 $ri$ 和$rj$ fit得有多好?**

**(2)-5 把上述四種方法的結果都合起來**

* a1,a2,a3,a4都是0或者1 (有用到這個性質或沒用到)

#### **(3)改變Starting region**
* Different colour space
* Different threshold parameter K(影響分割後的圖片大小)[(another paper)](http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf)

---

## 4.Object Recognition using SelectiveSearch
* Selective search + SIFT + bag-of-words + SVM

這是作者在這篇paper中提出的SS實作Object recognition方法
* 先透過SIFT等等方法提出出圖片特徵
* 再把包含ground truth的當成Positive example 與positive example重疊20-50%的當成negative sample
* 為了避免near-duplicate, negative examples在選擇過程中會剔除掉彼此重疊70%的negative sample
* 開始使用SVM後 加入Hard negative example (特別強的negative example)來限制

* SS用來篩選出可能位置
* SIFT用來找相似度
* 詞袋用來辨識物件
* SVM用來分類物件
## 5.Evaluation

對於每一個固定的class c 每個真實情況G 每個計算出來的L為l
比較bounding box(L) 和真實區塊(G)的最大重疊情況來算出Overlap scores

最後把這些ABO在平均起來就變成所有class的ABO (MeanABO)了

---

### Flat versus Hierarchy:

<br></br>

### Individual diversification stategies:

## 6.Conclusion

* Use a diverse set of complementary and hierarchical grouping strategies
* Result show that SS superior to “objectness”
* Considerable jump in quality in term of object regions
* Can be successfully used to create a good Bag-of-Words based localisation and recognition system