透彻理解RPN: 从候选区域搜索到候选区域提取网络
? ? ? ? ? 在目標檢測、目標跟蹤領域，提取region proposal都是最基本環節。本文概述了從 sliding window 到 selective search， 然后升級到 region proposal network的過程。 核心在于理解 selective search算法 和 region proposal network的設計思想。
1. 從sliding window 到 selective search 的候選區域提取
- 目標檢測 vs. 目標識別
? ? ? ? ?目標識別算法是指在一張給定的圖像中識別出給定的物體。他將整張圖像作為輸入，然后輸出類別的標簽并給出圖像中出現物體的概率。如上圖，直接輸入objection recognition算法中，算法會反饋圖像的類別dog, confident score 0.9987.
目標檢測返回類別和邊界框? ? ? ? ? 目標檢測任務不僅僅要返回圖像中主要包含那些物體，而且還要返回該圖像中包含了多少物體？ 他們在哪里（一般用BoundingBox進行標注）？
? ? ? ? ? 目標識別算法是所有目標檢測算法的核心。假設我們已經擁有了非常強大的目標識別算法，但是該算法也僅僅能夠告訴我們目標(如狗)是什么， 卻不能告訴我們目標在哪里？ 有多少個目標？
? ? ? ? ? 為了完成目標檢測任務，我們需要選擇一個更小的區域（sub-regions，patches）,然后利用目標識別算法去識別各個patches是否包含high confident score的objections。
? ? ? ? ? 因此，一個非常基礎但很重要的環節在于：如何從一張圖像中又快又好地提取出這樣的patches?其實最直接的方法提取region proposal(候選區域)的方式就是采用滑窗方法。但是sliding window方法非常消耗時間，因此研究學者提出了基于selective search策略的區域候選算法。
note1：提取patches算法更學術一點叫做region proposal algorithm
note2：好，指的是patches中盡可能恰好包括objects
note3：快，指的是有效速度。因為不同目標之前存在位置和尺度差異，如果采用遍歷法，明顯就是不合理的。
- Sliding window 滑窗技術
? ? ? ? ?使用sliding window方法中，我們使用window對整幅圖像進行遍歷，然后利用目標識別算法所有的patches進行檢查。這實際上就是一個窮舉的過程。此外，在遍歷搜索過程中，我們不僅僅要遍歷單個尺度的window，還有對多尺度的window進行檢測。 因此，sliding window策略是非常消耗時間的。還有就是，sliding window算法對固定比例patches提取非常適合，但是由于projection的時間原因，固定的比例是很難保證的。 如果要將不同比例考慮進去，sliding window的時間效益又將大打折扣。
- region proposal algorithm
? ? ? ? ? sliding window （受平移、尺度、比例影響）存在的根本問題就是漫無目的性的搜索， 恰恰region proposal algorithm就是為了解決這個問題。候選區域提取算法將圖像作為輸入，并輸出邊界框BoundingBox，該邊界框對應于圖像中最有可能是對象的所有patches。這些BoundingBox可能存在噪聲、重疊，也可能偏離了目標，但是大多數候選區域應該與圖像中的目標非常接近。這樣，我們在后面直接對這些BoundingBox進行目標識別就好了。 在所有的region proposal algorithms中， selective search based 非常有代表性（快，有很高的召回率recall），進而提取BoundingBox。
- selective search
? ? ? ? ? selective search最核心的點在于通過顏色、文理、形狀或者大小等 將原始的輸入圖像劃分成等級區域(實質就是分割，如上圖所示)。但是直接分割的圖片不能用來做物體檢測，原因有二：
1 大多數物體包含倆種以上的顏色（尤其受到光照影響，一個物體可能包含更豐富的顏色信息）
2 如果物體之間有重疊，這種方法無法處理，比如杯子放在盤子上的情況
? ? ? ? ? 為了更好地解決上面的兩個問題，自然而然的我們想到了使用更好的分割方法，但是這并不是我們的目標（圖像分割本來就是一個非常大的領域）。 我們這里需要的是一個不錯的分割結果就好，至少需要滿足分割后的區域可以盡可能的覆蓋原圖像中的物體。所以，selective search中使用了[1]中的分割算法進行過分割（如上圖所示）。selective search將過分割圖像作為初始輸入，并執行以下步驟：
step 1:根據論文[1]分割的圖片畫出多個框，把所有框放入列表Region中
step 2:根據相似程度（顏色，紋理，大小，形狀等），計算Region中框之間的倆倆形似度，把相似度放入列表A中
step 3:從列表A中找出相似度最大的倆個框a,b并且合并
Step 4:把合并的框加入列表Region中，從A中刪除和a，b相關的相似度，重復步驟2，直至清空A
最終只需要對Region中的框進行圖片分類，就可以得到原圖的檢測結果。候選框從數十萬降到幾千（R-CNN中倆千左右）。
graph-base過分割后形成Hierarchy - bottom-up 策略。它顯示了等級分割過程的初始、中間和最后一步綠框：生成的真陽性邊界框 true positive BoundingBox 藍框：生成的假陽性邊界框 false positive BoundingBox
- selective search 區域歸并
? ? ? ? ? 那么如何計算兩個區域之間的相似性？ selective search運用了基于顏色、文理、形狀、大小進行相似性度量。
? ? ? ? ? 顏色相似性：A color histogram of 25 bins is calculated for each channel of the image and histograms for all channels are concatenated to obtain a color descriptor resulting into a 25×3 = 75-dimensional color descriptor.?對于圖像的每一個通道我們需要計算25bin的顏色直方圖，然后每一個顏色通道的直方圖拼接在一起，形成顏色描述子（75維）。
? ? ? ? ?紋理相似性：對于圖像的每個通道，利用高斯差分對8個方向進行計算提取紋理特征。對于每個顏色通道的每個方向，利用10-bin直方圖進行表示，這樣便形成了紋理描述子（10*8*3=240維）。
? ? ? ? ?尺寸相似性：尺度相似性鼓勵更小的區域早日合并。它確保在圖像的所有部分形成所有尺度的候選區域。如果沒有考慮這個相似度測度，那么一個區域會一個一個地吞噬所有較小的相鄰區域，那么，多個比例的候選區域將只在特定的位置產生。
? ? ? ? ?形狀兼容性相似性：兩個區域重合比例程度。
兩個區域之間的最終相似度定義為上述4個相似點的線性組合。
Python+OpenCV的代碼實現：https://download.csdn.net/download/shenziheng1/10751868。示例結果如下：
selective search采用graph-based過分割生成的候選區域（region proposal）: ?降低了時間消耗，提升了候選區域的質量 selective search采用graph-based過分割生成的候選區域（region proposal）: ?降低了時間消耗，提升了候選區域的質量?
2. 從selective search 到 region proposal network的候選區域提取
- CNN對目標識別算法的革新
? ? ? ? ? 2012年論文[6]再次引燃神經網絡并且開啟以深度學習為主導的人工智能時代。[6]提出的AlexNet網絡結構在ImageNet ILSVRC圖片分類的比賽中奪得冠軍，top-1的準確率達到57.1%,top-5 達到80.2%，突然之間手工設計的特征提取方法顯得羸弱不堪，用卷積神經網絡（CNN）來做特征提取成了大家的共識。 受到AlexNet影響[7]把CNN引入物體檢測的領域，為了方便，研究學者把[7]方法簡稱為regions with CNN features，也就是R-CNN。
Region-CNN 目標檢測框架示意圖對輸入的圖片進行區域提取，文中用selective search。然后對每一塊提取出來的區域縮放到統一的大小，輸出CNN特征向量，用分類器（SVM，討論了softmax的可行性）判斷該區域是不是某類物體，接著對選出的區域做了框回歸（bounding box regression）處理得到最后的結果：物體種類和框的位置。
這篇論文在當時也引起了轟動，主要在于兩個方面：
1.利用CNN代替傳統的手工特征，并證明了不同的CNN結構對檢測效果很非常大的影響。如VGG-16的檢測性能要比AlexNet效果好得多。
2.加入了根據CNN特征對邊界框進行回歸的方法。對比表明在SVM分類的結果上做框回歸之后會把mAP再提高4個百分點。
網絡訓練采用的還是分段訓練（這為后來的fast-RCNN 和 faster-RCNN提供了研究方向）：
1.在ImageNet上pre-train一個圖片分類的CNN（也可以用別人提供的比如AlexNet）
2.替換訓練好的CNN分類層，比如從AlexNet的1000 類物體換成VOC的20+1類，繼續fine tune訓練
3.針對每一類目標物體訓練一個one vs rest的SVM
4.使用CNN的輸出做輸入，訓練一組參數做bounding-box regressor修正位置
關于為什么用SVM而不是直接采用Softmax進行分類？作者是利用大量的實驗進行證明，但是由于起初訓練沒有關注正負樣本均衡，所以在后面的Fast-RCNN算法中，直接又用Softmax替代了SVM，性能更好。
- BoundingBox回歸
? ? ? ? ? 這里可能會好奇，講了RCNN變更了目標識別算法，又講到了BoundingBox回歸網絡，怎么還不講Region Proposal Network？ 其實，算法領域都是基于一個baseline進行一步一步改進的。所以非常有必要理解一下BoundingBox優化。
? ? ? ? ??如果不BoundingBox Regression，輸出的位置就是selective search選出的那個區域的位置，實際中是會存在偏差的如下圖所示：
紅框： selective search 提供的 候選區域，該區域經過目標識別算法得到的置信值最大。 綠框：我們期待的結果，也是真實標注與selective search之間的差別。 改圖說明了BoundingBox Regression模塊的重要性。? ? ? ? ? selective search選出的可能是紅色的框，ground truth是綠色的框，判斷是否正確是用IoU的值來判斷，輸出紅色框會影響到結果判斷，但是已經把飛機檢測出來了只要對紅色框做線性變換（縮放+平移），就可以了。[7]認為，CNN輸出的特征向量里包含了信息，所以在CNN輸出的特征向量上做了一個loss計算，調整原來框的位置（相當于對原來的框加上縮放和平移操作）。所以每一個種類都設計了邊界框回歸BoundingBox Regression，只要設計一個好的loss函數，能學習到一組參數使loss收斂就可以啊。因此，loss的設計是關鍵。對于BoundingBox Regression 回歸的具體做法，會單獨研究。
- RCNN的弊端和改進方案
? ? ? ? ?通過上面分析，我們就會發現，RCNN和之前的目標檢測方法相比已經取得了長足的發展，但是仍然存在模型訓練不合理、檢測速度慢弊端。對于這樣一個新奇的策略，必定會引起很多研究學者跟進。緊跟著就出現了SSPNet和Fast-RCNN的改進算法。
SSPnet：很好的解決了不同尺寸圖像的訓練問題，但是很可惜，該網絡不能反向傳播，所以前面的特征提取層和后圈的全連接分類層都需要單獨訓練。所以，SPP Net的設計讓特征提取的時間成百上千倍的加快，缺點就是訓練步驟麻煩。
Fast R-CNN：主要在訓練步驟上做了優化，主要是倆個方面： 根據SPPNet 中的spp層改進設計了RoI Pooling，使用muti-task loss同時訓練物體種類和位置。之前提到spp層不能進行反向傳播，是由于金字塔的結構，Fast R-CNN就化用了SPPNet的方法，使用RoI Pooling，其實就是只用spp中金字塔的一層做池化，這樣也能產生固定長度的特征向量，用來做分類。而且只用金字塔的一層做池化，就是一個池化操作了，那就可以做反向傳播了。Fast R-CNN最大的貢獻在于將目標分類和邊界框回歸一起做，用作者的觀點就是：multi-task 。 核心還在如何設計 multi-task loss。?分類直接在原來CNN的基礎上加入FC層和softmax即可; 框回歸是讓CNN的輸出直接是bounding box regressor需要的4個比例。
Fast R-CNN 檢測：分類與位置同時執行的多任務框架做到這里了，其實感覺已經很完美了。但是2015年，很多學者意識到 Most algorithms can benefit from end-to-end training. 其實這是很好理解的，深度學習本身就是基于數據驅動完成了算法的性能提升。如果算法框架是End-to-End的，那么各組分（諸如區域候選提取、特征提取、邊界框回歸等）應該耦合的更緊密。
回頭看看，無論是SSP net 還是 Fast R-CNN改進，都沒有對區域候選環節Region Proposal進行改變，都不約而同的采用了Selective search算法。以現在的眼光去比喻，有點像造好了一輛汽車(CNN)，但是在用馬(selective search)拉著跑的感覺。因為selective search的計算太慢了，想讓物體檢測達到實時，就得改造候選框提取的方法。 這都是Faster CNN要做的，統一區域候選提取、分類和邊界框回歸，實現檢測算法的End-to-End.
- ?錨點機制和區域候選網絡設計
? ? ? ? ? Faster RCNN[10]提出了一種方法，在網絡中設計一個模塊來提取候選框(region proposal networks)，為什么要用網絡實現？因為最初作者就抱著和分類網絡共用部分CNN的目的。[10]有個很重要的概念：錨點。理解RPN的關鍵也就在錨點上。
? ? ? ? ? 錨點，字面理解就是標定位置的固定的點。在提框機制中，是預先設定好一些固定的點(anchor)和框(anchor box)的意思。如下圖所示：
Faster R-CNN中anchor的解釋：假設圖像上設定4個錨點(2x2)，那么就可以看作2x2的格子，每個格子的中心叫做錨點。以錨點為中心，給定倆個寬高比(1:2, 2:1)，畫倆個框。綠色和紅色的框就是錨點框(anchor box)。也就是說，每一個錨點都可以產生倆個錨點框，這些框就是固定在這里存在的，不會變也不會動。當模型輸出的預測位置是棕色虛線框時，計算預測框和每一個錨點框的誤差。方法是：首先用bounding box regression的方法計算每一個anchor box 到真值框的偏移量t1，每一個scale的anchor box都需要bounding box regressor; 再計算預測框到每一個anchor box的偏移量t2 , 最后使回歸損失L1(t1-t2)最小。
? ? ? ? ? 這里可能會產生一個問題，為什么不直接計算預測框和真值框的誤差，而是要通過anchor作為中間傳導呢？這和模型的輸出有關系，RPN的輸出位置信息并不是框的位置?（x, y, w, h），而是錨點框的偏移量?t2。因此需要學習?t2和?t1的誤差最小。以上圖為例，全圖共4個錨點，每個錨點產生2個錨點框。所以一張圖產生4×2=8個錨點框，RPN的輸出是對每一個錨點框輸出種類(前景后景)置信度?+ 位置偏移量?t2，共8×(2+4)個值。
? ? ? ? ? 所以整個Fast R-CNN的算法流程為：
Faster R-CNN檢測框架流圖： 整個網絡分為兩個部分RPN + Detection。1. 輸入圖像，用CNN提特征，在CNN輸出的特征圖(feature map)上做anchor處理。2. 假設特征圖通道數是256。那么特征圖的尺寸就相當于設定了多少個錨點。例如，特征圖長寬是13x13, 那就有169個錨點，每一個錨點按照論文中的說法可以產生9個錨點框，這9個錨點框共用一組1×256的特征，即錨點所在位置上所有通道的數據，接一個1×1的卷積核控制維度，做位置回歸和前后景判斷，這就是RPN的輸出。3. 在RPN的輸出基礎上，對所有anchor box的前景置信度排序，挑選出前top-N的框作為預選框proposal， 繼續CNN做進一步特征提取，最后再進行位置回歸和物體種類判斷。Faster R-CNN的訓練方法有好幾種，主要分為拆分訓練和端到端訓練。
拆分訓練：先訓練RPN，從所有anchor box中隨機挑選256個，保持正樣本負樣本比例1：1(正樣本不夠時用負樣本補)；再從RPN的輸出中，降序排列所有anchor box的前景置信度，挑選top-N個候選框叫做proposal, 做分類訓練。
端到端訓練：理論上可以做端到端的訓練，但是由于anchor box提取的候選框中負樣本占大多數，有的圖中負樣本和正樣本的比例可以是1000：1, 導致直接訓練難度很大。真正的端到端的目標檢測網絡還是有的，例如one-stage中代表的YOLO、SSD算法。速度很快，但是精度差了點。
Faster R-CNN最核心的工作在于在提取特征的過程中完成候選框提取的操作，大大加快了物體檢測的速度。
3. 參考資料
1. 基于圖的高效分割算法：Efficient Graph-Based Image Segmentation | IJCV2004
- http://cs.brown.edu/people/pfelzens/segment/
2. selective search 策略用于目標識別：Selective Search for Object Recognition | IJCV2013
- https://ivi.fnwi.uva.nl/isis/publications/2013/UijlingsIJCV2013/UijlingsIJCV2013.pdf
3. selective search策略用于目標檢測：Selective Search for Object Detection | LearnOpenCV2017
- https://www.learnopencv.com/selecti-search-for-object-detection-cpp-python/
4. sliding window策略用于目標檢測：Sliding Windows for Object Detection | PyimageSearch2015
5. 其他常用的region proposal algorithms：
- Objectness measure：http://groups.inf.ed.ac.uk/calvin/objectness/
- CPMC: Constrained Parametric Min-Cuts for Automatic Object Segmentation：?http://www.maths.lth.se/matematiklth/personal/sminchis/code/cpmc/index.html
- Category Independent Object Proposals：http://vision.cs.uiuc.edu/proposals/
6. 神經網絡邁向深度學習的大作：ImageNet Classification with Deep Convolution Neural Network | NIPS2012
- http://dblp.uni-trier.de/db/conf/nips/nips2012.html#KrizhevskySH12
7. RCNN用于目標檢測論文：Rich features hierarchies for accurate object detection and semantic segmentation | CVPR2014
- http://128.84.21.199/abs/1311.2524
8. BoundingBox Regression：http://caffecn.cn/?/question/160
9. RCNN的第一批改進算法：
- SSPNet:?Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition | ECCV2014 + PAMI2015
- Fast R-CNN | ICCV2015?https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7410526
10. End-to-End檢測框架： Faster R-CNN | NIPS2016
- https://dl.acm.org/citation.cfm?id=2969239.2969250
- YOLO v1:?You Only Look Once: Unified, Real-Time Object Detection | CVPR2016
- YOLO v2:?YOLO9000: Better, Faster, Stronger | CVPR2017
- YOLO v3:?YOLOv3: An Incremental Improvement | CVPR2018
- SSD: SSD: Single Shot MultiBox Detector | ECCV2016
- FPN:?Feature Pyramid Networks for Object Detection | CVPR2017
總結
以上是生活随笔為你收集整理的透彻理解RPN: 从候选区域搜索到候选区域提取网络的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python迭代器生成器使用技巧(2)：
- 下一篇： VC下发布的Release版程序的异常捕