視頻目標檢測演算法

『壹』 計算機視覺中，目前有哪些經典的目標跟蹤演算法

第一章介紹運動的分類、計算機視覺領域中運動分析模型、計算機視覺領域運動檢測和目標跟蹤技術研究現狀、計算機視覺領域中運動分析技術的難點等內容；
第二章介紹傳統的運動檢測和目標跟蹤演算法，包括背景差分法、幀間差分法、光流場評估演算法等；
第三章介紹具有周期性運動特徵的低速目標運動檢測和跟蹤演算法，並以CCD測量系統為例介紹該演算法的應用；
第四章介紹高速運動目標識別和跟蹤演算法，並以激光通信十信標光捕獲和跟蹤系統為例介紹該演算法的應用；
第五章介紹具有復雜背景的目標運動檢測過程中採用的光流場演算法，包括正規化相關的特性及其改進光流場評估演算法，並介紹改進光流場演算法的具體應用；
第六章介紹互補投票法實現可信賴運動向量估計。

『貳』 目標檢測演算法（R-CNN，fast R-CNN，faster R-CNN，yolo，SSD，yoloV2，yoloV3）

深度學習目前已經應用到了各個領域，應用場景大體分為三類：物體識別，目標檢測，自然語言處理。  目標檢測可以理解為是物體識別和物體定位的綜合 ，不僅僅要識別出物體屬於哪個分類，更重要的是得到物體在圖片中的具體位置。

2014年R-CNN演算法被提出，基本奠定了two-stage方式在目標檢測領域的應用。它的演算法結構如下圖

演算法步驟如下：

R-CNN較傳統的目標檢測演算法獲得了50%的性能提升，在使用VGG-16模型作為物體識別模型情況下，在voc2007數據集上可以取得66%的准確率，已經算還不錯的一個成績了。其最大的問題是速度很慢，內存佔用量很大，主要原因有兩個

針對R-CNN的部分問題，2015年微軟提出了Fast R-CNN演算法，它主要優化了兩個問題。

R-CNN和fast R-CNN均存在一個問題，那就是 由選擇性搜索來生成候選框，這個演算法很慢 。而且R-CNN中生成的2000個左右的候選框全部需要經過一次卷積神經網路，也就是需要經過2000次左右的CNN網路，這個是十分耗時的（fast R-CNN已經做了改進，只需要對整圖經過一次CNN網路）。這也是導致這兩個演算法檢測速度較慢的最主要原因。

faster R-CNN 針對這個問題， 提出了RPN網路來進行候選框的獲取，從而擺脫了選擇性搜索演算法，也只需要一次卷積層操作，從而大大提高了識別速度 。這個演算法十分復雜，我們會詳細分析。它的基本結構如下圖

主要分為四個步驟：

使用VGG-16卷積模型的網路結構：

卷積層採用的VGG-16模型，先將PxQ的原始圖片，縮放裁剪為MxN的圖片，然後經過13個conv-relu層，其中會穿插4個max-pooling層。所有的卷積的kernel都是3x3的，padding為1，stride為1。pooling層kernel為2x2, padding為0，stride為2。

MxN的圖片，經過卷積層後，變為了(M/16) x (N/16)的feature map了。

faster R-CNN拋棄了R-CNN中的選擇性搜索（selective search）方法，使用RPN層來生成候選框，能極大的提升候選框的生成速度。RPN層先經過3x3的卷積運算，然後分為兩路。一路用來判斷候選框是前景還是背景，它先reshape成一維向量，然後softmax來判斷是前景還是背景，然後reshape恢復為二維feature map。另一路用來確定候選框的位置，通過bounding box regression實現，後面再詳細講。兩路計算結束後，挑選出前景候選框（因為物體在前景中），並利用計算得到的候選框位置，得到我們感興趣的特徵子圖proposal。

卷積層提取原始圖像信息，得到了256個feature map，經過RPN層的3x3卷積後，仍然為256個feature map。但是每個點融合了周圍3x3的空間信息。對每個feature map上的一個點，生成k個anchor（k默認為9）。anchor分為前景和背景兩類（我們先不去管它具體是飛機還是汽車，只用區分它是前景還是背景即可）。anchor有[x,y,w,h]四個坐標偏移量，x,y表示中心點坐標，w和h表示寬度和高度。這樣，對於feature map上的每個點，就得到了k個大小形狀各不相同的選區region。

對於生成的anchors，我們首先要判斷它是前景還是背景。由於感興趣的物體位於前景中，故經過這一步之後，我們就可以舍棄背景anchors了。大部分的anchors都是屬於背景，故這一步可以篩選掉很多無用的anchor，從而減少全連接層的計算量。

對於經過了3x3的卷積後得到的256個feature map，先經過1x1的卷積，變換為18個feature map。然後reshape為一維向量，經過softmax判斷是前景還是背景。此處reshape的唯一作用就是讓數據可以進行softmax計算。然後輸出識別得到的前景anchors。

另一路用來確定候選框的位置，也就是anchors的[x,y,w,h]坐標值。如下圖所示，紅色代表我們當前的選區，綠色代表真實的選區。雖然我們當前的選取能夠大概框選出飛機，但離綠色的真實位置和形狀還是有很大差別，故需要對生成的anchors進行調整。這個過程我們稱為bounding box regression。

假設紅色框的坐標為[x,y,w,h], 綠色框，也就是目標框的坐標為[Gx, Gy,Gw,Gh], 我們要建立一個變換，使得[x,y,w,h]能夠變為[Gx, Gy,Gw,Gh]。最簡單的思路是，先做平移，使得中心點接近，然後進行縮放，使得w和h接近。如下：

我們要學習的就是dx dy dw dh這四個變換。由於是線性變換，我們可以用線性回歸來建模。設定loss和優化方法後，就可以利用深度學習進行訓練，並得到模型了。對於空間位置loss，我們一般採用均方差演算法，而不是交叉熵（交叉熵使用在分類預測中）。優化方法可以採用自適應梯度下降演算法Adam。

得到了前景anchors，並確定了他們的位置和形狀後，我們就可以輸出前景的特徵子圖proposal了。步驟如下：

1，得到前景anchors和他們的[x y w h]坐標。

2，按照anchors為前景的不同概率，從大到小排序，選取前pre_nms_topN個anchors，比如前6000個

3，剔除非常小的anchors。

4，通過NMS非極大值抑制，從anchors中找出置信度較高的。這個主要是為了解決選取交疊問題。首先計算每一個選區面積，然後根據他們在softmax中的score（也就是是否為前景的概率）進行排序，將score最大的選區放入隊列中。接下來，計算其餘選區與當前最大score選區的IOU（IOU為兩box交集面積除以兩box並集面積，它衡量了兩個box之間重疊程度）。去除IOU大於設定閾值的選區。這樣就解決了選區重疊問題。

5，選取前post_nms_topN個結果作為最終選區proposal進行輸出，比如300個。

經過這一步之後，物體定位應該就基本結束了，剩下的就是物體識別了。

和fast R-CNN中類似，這一層主要解決之前得到的proposal大小形狀各不相同，導致沒法做全連接。全連接計算只能對確定的shape進行運算，故必須使proposal大小形狀變為相同。通過裁剪和縮放的手段，可以解決這個問題，但會帶來信息丟失和圖片形變問題。我們使用ROI pooling可以有效的解決這個問題。

ROI pooling中，如果目標輸出為MxN，則在水平和豎直方向上，將輸入proposal劃分為MxN份，每一份取最大值，從而得到MxN的輸出特徵圖。

ROI Pooling層後的特徵圖，通過全連接層與softmax，就可以計算屬於哪個具體類別，比如人，狗，飛機，並可以得到cls_prob概率向量。同時再次利用bounding box regression精細調整proposal位置，得到bbox_pred，用於回歸更加精確的目標檢測框。

這樣就完成了faster R-CNN的整個過程了。演算法還是相當復雜的，對於每個細節需要反復理解。faster R-CNN使用resNet101模型作為卷積層，在voc2012數據集上可以達到83.8%的准確率，超過yolo ssd和yoloV2。其最大的問題是速度偏慢，每秒只能處理5幀，達不到實時性要求。

針對於two-stage目標檢測演算法普遍存在的運算速度慢的缺點， yolo創造性的提出了one-stage。也就是將物體分類和物體定位在一個步驟中完成。 yolo直接在輸出層回歸bounding box的位置和bounding box所屬類別，從而實現one-stage。通過這種方式， yolo可實現45幀每秒的運算速度，完全能滿足實時性要求 （達到24幀每秒，人眼就認為是連續的）。它的網路結構如下圖：

主要分為三個部分：卷積層，目標檢測層，NMS篩選層。

採用Google inceptionV1網路，對應到上圖中的第一個階段，共20層。這一層主要是進行特徵提取，從而提高模型泛化能力。但作者對inceptionV1進行了改造，他沒有使用inception mole結構，而是用一個1x1的卷積，並聯一個3x3的卷積來替代。（可以認為只使用了inception mole中的一個分支，應該是為了簡化網路結構）

先經過4個卷積層和2個全連接層，最後生成7x7x30的輸出。先經過4個卷積層的目的是為了提高模型泛化能力。yolo將一副448x448的原圖分割成了7x7個網格，每個網格要預測兩個bounding box的坐標(x,y,w,h)和box內包含物體的置信度confidence，以及物體屬於20類別中每一類的概率（yolo的訓練數據為voc2012，它是一個20分類的數據集）。所以一個網格對應的參數為（4x2+2+20) = 30。如下圖

其中前一項表示有無人工標記的物體落入了網格內，如果有則為1，否則為0。第二項代表bounding box和真實標記的box之間的重合度。它等於兩個box面積交集，除以面積並集。值越大則box越接近真實位置。

分類信息： yolo的目標訓練集為voc2012，它是一個20分類的目標檢測數據集 。常用目標檢測數據集如下表：

| Name | # Images (trainval) | # Classes | Last updated |

| --------------- | ------------------- | --------- | ------------ |

| ImageNet | 450k | 200 | 2015 |

| COCO | 120K | 90 | 2014 |

| Pascal VOC | 12k | 20 | 2012 |

| Oxford-IIIT Pet | 7K | 37 | 2012 |

| KITTI Vision | 7K | 3 | |

每個網格還需要預測它屬於20分類中每一個類別的概率。分類信息是針對每個網格的，而不是bounding box。故只需要20個，而不是40個。而confidence則是針對bounding box的，它只表示box內是否有物體，而不需要預測物體是20分類中的哪一個，故只需要2個參數。雖然分類信息和confidence都是概率，但表達含義完全不同。

篩選層是為了在多個結果中（多個bounding box）篩選出最合適的幾個，這個方法和faster R-CNN 中基本相同。都是先過濾掉score低於閾值的box，對剩下的box進行NMS非極大值抑制，去除掉重疊度比較高的box（NMS具體演算法可以回顧上面faster R-CNN小節）。這樣就得到了最終的最合適的幾個box和他們的類別。

yolo的損失函數包含三部分，位置誤差，confidence誤差，分類誤差。具體公式如下：

誤差均採用了均方差演算法，其實我認為，位置誤差應該採用均方差演算法，而分類誤差應該採用交叉熵。由於物體位置只有4個參數，而類別有20個參數，他們的累加和不同。如果賦予相同的權重，顯然不合理。故yolo中位置誤差權重為5，類別誤差權重為1。由於我們不是特別關心不包含物體的bounding box，故賦予不包含物體的box的置信度confidence誤差的權重為0.5，包含物體的權重則為1。

Faster R-CNN准確率mAP較高，漏檢率recall較低，但速度較慢。而yolo則相反，速度快，但准確率和漏檢率不盡人意。SSD綜合了他們的優缺點，對輸入300x300的圖像，在voc2007數據集上test，能夠達到58 幀每秒( Titan X 的 GPU )，72.1%的mAP。

SSD網路結構如下圖：

和yolo一樣，也分為三部分：卷積層，目標檢測層和NMS篩選層

SSD論文採用了VGG16的基礎網路，其實這也是幾乎所有目標檢測神經網路的慣用方法。先用一個CNN網路來提取特徵，然後再進行後續的目標定位和目標分類識別。

這一層由5個卷積層和一個平均池化層組成。去掉了最後的全連接層。SSD認為目標檢測中的物體，只與周圍信息相關，它的感受野不是全局的，故沒必要也不應該做全連接。SSD的特點如下。

每一個卷積層，都會輸出不同大小感受野的feature map。在這些不同尺度的feature map上，進行目標位置和類別的訓練和預測，從而達到 多尺度檢測 的目的，可以克服yolo對於寬高比不常見的物體，識別准確率較低的問題。而yolo中，只在最後一個卷積層上做目標位置和類別的訓練和預測。這是SSD相對於yolo能提高准確率的一個關鍵所在。

如上所示，在每個卷積層上都會進行目標檢測和分類，最後由NMS進行篩選，輸出最終的結果。多尺度feature map上做目標檢測，就相當於多了很多寬高比例的bounding box，可以大大提高泛化能力。

和faster R-CNN相似，SSD也提出了anchor的概念。卷積輸出的feature map，每個點對應為原圖的一個區域的中心點。以這個點為中心，構造出6個寬高比例不同，大小不同的anchor（SSD中稱為default box）。每個anchor對應4個位置參數(x,y,w,h)和21個類別概率（voc訓練集為20分類問題，在加上anchor是否為背景，共21分類）。如下圖所示：

另外，在訓練階段，SSD將正負樣本比例定位1：3。訓練集給定了輸入圖像以及每個物體的真實區域（ground true box），將default box和真實box最接近的選為正樣本。然後在剩下的default box中選擇任意一個與真實box IOU大於0.5的，作為正樣本。而其他的則作為負樣本。由於絕大部分的box為負樣本，會導致正負失衡，故根據每個box類別概率排序，使正負比例保持在1：3。SSD認為這個策略提高了4%的准確率

另外，SSD採用了數據增強。生成與目標物體真實box間IOU為0.1 0.3 0.5 0.7 0.9的patch，隨機選取這些patch參與訓練，並對他們進行隨機水平翻轉等操作。SSD認為這個策略提高了8.8%的准確率。

和yolo的篩選層基本一致，同樣先過濾掉類別概率低於閾值的default box，再採用NMS非極大值抑制，篩掉重疊度較高的。只不過SSD綜合了各個不同feature map上的目標檢測輸出的default box。

SSD基本已經可以滿足我們手機端上實時物體檢測需求了，TensorFlow在Android上的目標檢測官方模型ssd_mobilenet_v1_android_export.pb，就是通過SSD演算法實現的。它的基礎卷積網路採用的是mobileNet，適合在終端上部署和運行。

針對yolo准確率不高，容易漏檢，對長寬比不常見物體效果差等問題，結合SSD的特點，提出了yoloV2。它主要還是採用了yolo的網路結構，在其基礎上做了一些優化和改進，如下

網路採用DarkNet-19：19層，裡麵包含了大量3x3卷積，同時借鑒inceptionV1，加入1x1卷積核全局平均池化層。結構如下

yolo和yoloV2隻能識別20類物體，為了優化這個問題，提出了yolo9000，可以識別9000類物體。它在yoloV2基礎上，進行了imageNet和coco的聯合訓練。這種方式充分利用imageNet可以識別1000類物體和coco可以進行目標位置檢測的優點。當使用imageNet訓練時，只更新物體分類相關的參數。而使用coco時，則更新全部所有參數。

YOLOv3可以說出來直接吊打一切圖像檢測演算法。比同期的DSSD(反卷積SSD), FPN（feature pyramid networks）准確率更高或相仿，速度是其1/3.。

YOLOv3的改動主要有如下幾點：

不過如果要求更精準的預測邊框，採用COCO AP做評估標準的話，YOLO3在精確率上的表現就弱了一些。如下圖所示。

當前目標檢測模型演算法也是層出不窮。在two-stage領域， 2017年Facebook提出了mask R-CNN 。CMU也提出了A-Fast-RCNN 演算法，將對抗學習引入到目標檢測領域。Face++也提出了Light-Head R-CNN，主要探討了 R-CNN 如何在物體檢測中平衡精確度和速度。

one-stage領域也是百花齊放，2017年首爾大學提出 R-SSD 演算法，主要解決小尺寸物體檢測效果差的問題。清華大學提出了 RON 演算法，結合 two stage 名的方法和 one stage 方法的優勢，更加關注多尺度對象定位和負空間樣本挖掘問題。

目標檢測領域的深度學習演算法，需要進行目標定位和物體識別，演算法相對來說還是很復雜的。當前各種新演算法也是層不出窮，但模型之間有很強的延續性，大部分模型演算法都是借鑒了前人的思想，站在巨人的肩膀上。我們需要知道經典模型的特點，這些tricks是為了解決什麼問題，以及為什麼解決了這些問題。這樣才能舉一反三，萬變不離其宗。綜合下來，目標檢測領域主要的難點如下：

一文讀懂目標檢測AI演算法：R-CNN，faster R-CNN，yolo，SSD，yoloV2

從YOLOv1到v3的進化之路

SSD-Tensorflow超詳細解析【一】：載入模型對圖片進行測試  https://blog.csdn.net/k87974/article/details/80606407

YOLO    https://pjreddie.com/darknet/yolo/      https://github.com/pjreddie/darknet   

C#項目參考：https://github.com/AlturosDestinations/Alturos.Yolo

項目實踐貼個圖。

『叄』 視覺追蹤的典型演算法

（1）基於區域的跟蹤演算法
基於區域的跟蹤演算法基本思想是：將目標初始所在區域的圖像塊作為目標模板，將目標模板與候選圖像中所有可能的位置進行相關匹配，匹配度最高的地方即為目標所在的位置。最常用的相關匹配准則是差的平方和准則，(Sum of Square Difference，SSD)。
起初，基於區域的跟蹤演算法中所用到的目標模板是固定的，如 Lucas 等人提出 Lucas-Kanade 方法，該方法利用灰度圖像的空間梯度信息尋找最佳匹配區域，確定目標位置。之後，更多的學者針對基於區域方法的缺點進行了不同的改進，如：Jepson 等人提出的基於紋理特徵的自適應目標外觀模型[18],該模型可以較好的解決目標遮擋的問題，且在跟蹤的過程中採用在線 EM 演算法對目標模型進行更新；Comaniciu 等人[19]提出了基於核函數的概率密度估計的視頻目標跟蹤演算法，該方法採用核直方圖表示目標，通過 Bhattacharya 系數計算目標模板與候選區域的相似度，通過均值漂移(MeanShift)演算法快速定位目標位置。
基於區域的目標跟蹤演算法採用了目標的全局信息，比如灰度信息、紋理特徵等，因此具有較高的可信度，即使目標發生較小的形變也不影響跟蹤效果，但是當目標發生較嚴重的遮擋時，很容易造成跟蹤失敗。
（2）基於特徵的跟蹤方法
基於特徵的目標跟蹤演算法通常是利用目標的一些顯著特徵表示目標，並通過特徵匹配在圖像序列中跟蹤目標。該類演算法不考慮目標的整體特徵，因此當目標被部分遮擋時，仍然可以利用另一部分可見特徵完成跟蹤任務，但是該演算法不能有效處理全遮擋、重疊等問題。
基於特徵的跟蹤方法一般包括特徵提取和特徵匹配兩個過程：
a) 特徵提取
所謂特徵提取是指從目標所在圖像區域中提取合適的描繪性特徵。這些特徵不僅應該較好地區分目標和背景，而且應對目標尺度伸縮、目標形狀變化、目標遮擋等情況具有魯棒性。常用的目標特徵包括顏色特徵、灰度特徵、紋理特徵、輪廓、光流特徵、角點特徵等。D.G. Lowe 提出 SIFT(Scale Invariant Feature Transform)演算法[20]是圖像特徵中效果較好的一種方法，該特徵對旋轉、尺度縮放、亮度變化具有不變性，對視角變化、仿射變換、雜訊也具有一定的穩定性。
b) 特徵匹配
特徵匹配就是採用一定的方式計算衡量候選區域與目標區域的相似性，並根據相似性確定目標位置、實現目標跟蹤。在計算機視覺領域中，常用的相似性度量准則包括加權距離、Bhattacharyya 系數、歐式距離、Hausdorff 距離等。其中，Bhattacharyya 系數和歐式距離最為常用。
Tissainayagam 等人提出了一種基於點特徵的目標跟蹤演算法[21]。該演算法首先在多個尺度空間中尋找局部曲率最大的角點作為關鍵點，然後利用提出的MHT-IMM 演算法跟蹤這些關鍵點。這種跟蹤演算法適用於具有簡單幾何形狀的目標，對於難以提取穩定角點的復雜目標，則跟蹤效果較差。
Zhu 等人提出的基於邊緣特徵的目標跟蹤演算法[22]，首先將參考圖像劃分為多個子區域，並將每個子區域的邊緣點均值作為目標的特徵點，然後利用類似光流的方法進行特徵點匹配，從而實現目標跟蹤。
（3）基於輪廓的跟蹤方法
基於輪廓的目標跟蹤方法需要在視頻第一幀中指定目標輪廓的位置，之後由微分方程遞歸求解，直到輪廓收斂到能量函數的局部極小值，其中，能量函數通常與圖像特徵和輪廓光滑度有關。與基於區域的跟蹤方法相比，基於輪廓的跟蹤方法的計算復雜度小，對目標的部分遮擋魯棒。但這種方法在跟蹤開始時需要初始化目標輪廓，因此對初始位置比較敏感，跟蹤精度也被限制在輪廓級。
Kass 等人[23]於 1987 年提出的活動輪廓模型(Active Contour Models，Snake)，通過包括圖像力、內部力和外部約束力在內的三種力的共同作用控制輪廓的運動。內部力主要對輪廓進行局部的光滑性約束，圖像力則將曲線推向圖像的邊緣，而外部力可以由用戶指定，主要使輪廓向期望的局部極小值運動，。
Paragios 等人[24]提出了一種用水平集方法表示目標輪廓的目標檢測與跟蹤演算法，該方法首先通過幀差法得到目標邊緣，然後通過概率邊緣檢測運算元得到目標的運動邊緣，通過將目標輪廓向目標運動邊緣演化實現目標跟蹤。
（4）基於模型的跟蹤方法[25]
在實際應用中，我們需要跟蹤的往往是一些特定的我們事先具有認識的目標，因此，基於模型的跟蹤方法首先根據自己的先驗知識離線的建立該目標的 3D 或2D 幾何模型，然後，通過匹配待選區域模型與目標模型實現目標跟蹤，進而在跟蹤過程中，根據場景中圖像的特徵，確定運動目標的各個尺寸參數、姿態參數以及運動參數。
Shu Wang 等人提出一種基於超像素的跟蹤方法[26]，該方法在超像素基礎上建立目標的外觀模板，之後通過計算目標和背景的置信圖確定目標的位置，在這個過程中，該方法不斷通過分割和顏色聚類防止目標的模板漂移。
（5）基於檢測的跟蹤演算法
基於檢測的跟蹤演算法越來越流行。一般情況下，基於檢測的跟蹤演算法都採用一點學習方式產生特定目標的檢測器，即只用第一幀中人工標記的樣本信息訓練檢測器。這類演算法將跟蹤問題簡化為簡單的將背景和目標分離的分類問題，因此這類演算法的速度快且效果理想。這類演算法為了適應目標外表的變化，一般都會採用在線學習方式進行自更新，即根據自身的跟蹤結果對檢測器進行更新。

『肆』 目標檢測：IOU計算

  在目標檢測中，經常需要計算預測回歸框和真實回歸框的交並比（Intersection Over Union，IOU），也稱重疊度,計算公式如下。
​
​   由於回歸框只是確定物體的位置，不需要考慮物體的傾斜、旋轉等情況。那麼已知兩個回歸框A,B各自左上頂點右下頂點的坐標，如何計算二者的交集和並集。假定回歸框A的左上頂點和右下頂點的坐標分為 ,回歸框B的左上頂點和右下頂點的坐標分為 。為方便理解，將回歸框用集合語言來描述：
​

則可得到不等式組:

成立時，集合A、B交集非空，且當不等式組成立時，交集C為：

  求得預測回歸框和真實回歸框的交集和並集之後，可以很容易計算出IOU的值：

關於交並比計算的更詳細內容，可以參考以下鏈接：

Yolo V1演算法詳解

『伍』 經典目標檢測演算法介紹

姓名：牛曉銀；學號：20181213993；學院：計算機科學與技術

轉自：https://zhuanlan.hu.com/p/34142321

【嵌牛導讀】：目標檢測，也叫目標提取，是一種基於目標幾何和統計特徵的圖像分割。隨著計算機技術的發展和計算機視覺原理的廣泛應用，利用計算機圖像處理技術對目標進行實時跟蹤研究越來越熱門，對目標進行動態實時跟蹤定位在智能化交通系統、軍事目標檢測及醫學導航手術中手術器械定位等方面具有廣泛的應用價值。

【嵌牛鼻子】：目標檢測、檢測模型、計算機視覺

【嵌牛提問】：你知道或者用過哪些目標檢測演算法？

【嵌牛正文】：

（一）目標檢測經典工作回顧

本文結構

兩階段模型因其對圖片的兩階段處理得名，也稱為基於區域（Region-based）的方法，我們選取R-CNN系列工作作為這一類型的代表。

R-CNN: R-CNN系列的開山之作

論文鏈接：  Rich feature hierarchies for accurate object detection and semantic segmentation

本文的兩大貢獻：1）CNN可用於基於區域的定位和分割物體；2）監督訓練樣本數緊缺時，在額外的數據上預訓練的模型經過fine-tuning可以取得很好的效果。第一個貢獻影響了之後幾乎所有2-stage方法，而第二個貢獻中用分類任務（Imagenet）中訓練好的模型作為基網路，在檢測問題上fine-tuning的做法也在之後的工作中一直沿用。

傳統的計算機視覺方法常用精心設計的手工特徵(如SIFT, HOG)描述圖像，而深度學習的方法則倡導習得特徵，從圖像分類任務的經驗來看，CNN網路自動習得的特徵取得的效果已經超出了手工設計的特徵。本篇在局部區域應用卷積網路，以發揮卷積網路學習高質量特徵的能力。

R-CNN將檢測抽象為兩個過程，一是基於圖片提出若干可能包含物體的區域（即圖片的局部裁剪，被稱為Region Proposal），文中使用的是Selective Search演算法；二是在提出的這些區域上運行當時表現最好的分類網路（AlexNet），得到每個區域內物體的類別。

另外，文章中的兩個做法值得注意。

一是數據的准備。輸入CNN前，我們需要根據Ground Truth對提出的Region Proposal進行標記，這里使用的指標是IoU（Intersection over Union，交並比）。IoU計算了兩個區域之交的面積跟它們之並的比，描述了兩個區域的重合程度。

文章中特別提到，IoU閾值的選擇對結果影響顯著，這里要談兩個threshold，一個用來識別正樣本（如跟ground truth的IoU大於0.5），另一個用來標記負樣本（即背景類，如IoU小於0.1），而介於兩者之間的則為難例（Hard Negatives），若標為正類，則包含了過多的背景信息，反之又包含了要檢測物體的特徵，因而這些Proposal便被忽略掉。

另一點是位置坐標的回歸（Bounding-Box Regression），這一過程是Region Proposal向Ground Truth調整，實現時加入了log/exp變換來使損失保持在合理的量級上，可以看做一種標准化（Normalization)操作。

小結

R-CNN的想法直接明了，即將檢測任務轉化為區域上的分類任務，是深度學習方法在檢測任務上的試水。模型本身存在的問題也很多，如需要訓練三個不同的模型（proposal, classification, regression）、重復計算過多導致的性能問題等。盡管如此，這篇論文的很多做法仍然廣泛地影響著檢測任務上的深度模型革命，後續的很多工作也都是針對改進這一工作而展開，此篇可以稱得上"The First Paper"。

Fast R-CNN: 共享卷積運算

論文鏈接： Fast R-CNN

文章指出R-CNN耗時的原因是CNN是在每一個Proposal上單獨進行的，沒有共享計算，便提出將基礎網路在圖片整體上運行完畢後，再傳入R-CNN子網路，共享了大部分計算，故有Fast之名。

上圖是Fast R-CNN的架構。圖片經過feature extractor得到feature map, 同時在原圖上運行Selective Search演算法並將RoI（Region of Interset，實為坐標組，可與Region Proposal混用）映射到到feature map上，再對每個RoI進行RoI Pooling操作便得到等長的feature vector，將這些得到的feature vector進行正負樣本的整理（保持一定的正負樣本比例），分batch傳入並行的R-CNN子網路，同時進行分類和回歸，並將兩者的損失統一起來。

RoI Pooling 是對輸入R-CNN子網路的數據進行准備的關鍵操作。我們得到的區域常常有不同的大小，在映射到feature map上之後，會得到不同大小的特徵張量。RoI Pooling先將RoI等分成目標個數的網格，再在每個網格上進行max pooling，就得到等長的RoI feature vector。

文章最後的討論也有一定的借鑒意義：

multi-loss traing相比單獨訓練classification確有提升

multi-scale相比single-scale精度略有提升，但帶來的時間開銷更大。一定程度上說明CNN結構可以內在地學習尺度不變性

在更多的數據(VOC)上訓練後，精度是有進一步提升的

Softmax分類器比"one vs rest"型的SVM表現略好，引入了類間的競爭

更多的Proposal並不一定帶來精度的提升

小結

Fast R-CNN的這一結構正是檢測任務主流2-stage方法所採用的元結構的雛形。文章將Proposal, Feature Extractor, Object Classification&Localization統一在一個整體的結構中，並通過共享卷積計算提高特徵利用效率，是最有貢獻的地方。

Faster R-CNN: 兩階段模型的深度化

論文鏈接： Faster R-CNN: Towards Real Time Object Detection with Region Proposal Networks

Faster R-CNN是2-stage方法的奠基性工作，提出的RPN網路取代Selective Search演算法使得檢測任務可以由神經網路端到端地完成。粗略的講，Faster R-CNN = RPN + Fast R-CNN，跟RCNN共享卷積計算的特性使得RPN引入的計算量很小，使得Faster R-CNN可以在單個GPU上以5fps的速度運行，而在精度方面達到SOTA（State of the Art，當前最佳）。

本文的主要貢獻是提出Regional Proposal Networks，替代之前的SS演算法。RPN網路將Proposal這一任務建模為二分類（是否為物體）的問題。

第一步是在一個滑動窗口上生成不同大小和長寬比例的anchor box（如上圖右邊部分），取定IoU的閾值，按Ground Truth標定這些anchor box的正負。於是，傳入RPN網路的樣本數據被整理為anchor box（坐標）和每個anchor box是否有物體（二分類標簽）。RPN網路將每個樣本映射為一個概率值和四個坐標值，概率值反應這個anchor box有物體的概率，四個坐標值用於回歸定義物體的位置。最後將二分類和坐標回歸的損失統一起來，作為RPN網路的目標訓練。

由RPN得到Region Proposal在根據概率值篩選後經過類似的標記過程，被傳入R-CNN子網路，進行多分類和坐標回歸，同樣用多任務損失將二者的損失聯合。

小結

Faster R-CNN的成功之處在於用RPN網路完成了檢測任務的"深度化"。使用滑動窗口生成anchor box的思想也在後來的工作中越來越多地被採用（YOLO v2等）。這項工作奠定了"RPN+RCNN"的兩階段方法元結構，影響了大部分後續工作。

單階段（1-stage）檢測模型

單階段模型沒有中間的區域檢出過程，直接從圖片獲得預測結果，也被成為Region-free方法。

YOLO

論文鏈接： You Only Look Once: Unified, Real-Time Object Detection

YOLO是單階段方法的開山之作。它將檢測任務表述成一個統一的、端到端的回歸問題，並且以只處理一次圖片同時得到位置和分類而得名。

YOLO的主要優點：

快。

全局處理使得背景錯誤相對少，相比基於局部（區域）的方法， 如Fast RCNN。

泛化性能好，在藝術作品上做檢測時，YOLO表現比Fast R-CNN好。

YOLO的工作流程如下：

1.准備數據：將圖片縮放，劃分為等分的網格，每個網格按跟Ground Truth的IoU分配到所要預測的樣本。

2.卷積網路：由GoogLeNet更改而來，每個網格對每個類別預測一個條件概率值，並在網格基礎上生成B個box，每個box預測五個回歸值，四個表徵位置，第五個表徵這個box含有物體（注意不是某一類物體）的概率和位置的准確程度（由IoU表示）。測試時，分數如下計算：

等式左邊第一項由網格預測，後兩項由每個box預測，以條件概率的方式得到每個box含有不同類別物體的分數。 因而，卷積網路共輸出的預測值個數為S×S×(B×5+C)，其中S為網格數，B為每個網格生成box個數，C為類別數。

3.後處理：使用NMS（Non-Maximum Suppression，非極大抑制）過濾得到最後的預測框

損失函數的設計

損失函數被分為三部分：坐標誤差、物體誤差、類別誤差。為了平衡類別不均衡和大小物體等帶來的影響，損失函數中添加了權重並將長寬取根號。

小結

YOLO提出了單階段的新思路，相比兩階段方法，其速度優勢明顯，實時的特性令人印象深刻。但YOLO本身也存在一些問題，如劃分網格較為粗糙，每個網格生成的box個數等限制了對小尺度物體和相近物體的檢測。

SSD: Single Shot Multibox Detector

論文鏈接： SSD: Single Shot Multibox Detector

SSD相比YOLO有以下突出的特點：

多尺度的feature map：基於VGG的不同卷積段，輸出feature map到回歸器中。這一點試圖提升小物體的檢測精度。

更多的anchor box，每個網格點生成不同大小和長寬比例的box，並將類別預測概率基於box預測（YOLO是在網格上），得到的輸出值個數為(C+4)×k×m×n，其中C為類別數，k為box個數，m×n為feature map的大小。

小結

SSD是單階段模型早期的集大成者，達到跟接近兩階段模型精度的同時，擁有比兩階段模型快一個數量級的速度。後續的單階段模型工作大多基於SSD改進展開。

檢測模型基本特點

最後，我們對檢測模型的基本特徵做一個簡單的歸納。

檢測模型整體上由基礎網路（Backbone Network）和檢測頭部（Detection Head）構成。前者作為特徵提取器，給出圖像不同大小、不同抽象層次的表示；後者則依據這些表示和監督信息學習類別和位置關聯。檢測頭部負責的類別預測和位置回歸兩個任務常常是並行進行的，構成多任務的損失進行聯合訓練。

相比單階段，兩階段檢測模型通常含有一個串列的頭部結構，即完成前背景分類和回歸後，把中間結果作為RCNN頭部的輸入再進行一次多分類和位置回歸。這種設計帶來了一些優點：

對檢測任務的解構，先進行前背景的分類，再進行物體的分類，這種解構使得監督信息在不同階段對網路參數的學習進行指導

RPN網路為RCNN網路提供良好的先驗，並有機會整理樣本的比例，減輕RCNN網路的學習負擔

這種設計的缺點也很明顯：中間結果常常帶來空間開銷，而串列的方式也使得推斷速度無法跟單階段相比；級聯的位置回歸則會導致RCNN部分的重復計算（如兩個RoI有重疊）。

另一方面，單階段模型只有一次類別預測和位置回歸，卷積運算的共享程度更高，擁有更快的速度和更小的內存佔用。讀者將會在接下來的文章中看到，兩種類型的模型也在互相吸收彼此的優點，這也使得兩者的界限更為模糊。

『陸』 yolo演算法是什麼

Yolo演算法採用一個單獨的CNN模型實現end-to-end的目標檢測。

首先將輸入圖片resize到448x448，然後送入CNN網路，最後處理網路預測結果得到檢測的目標。相比R-CNN演算法，其是一個統一的框架，其速度更快，而且Yolo的訓練過程也是end-to-end的。

相關信息：

Yolo採用卷積網路來提取特徵，然後使用全連接層來得到預測值。網路結構參考GooLeNet模型，包含24個卷積層和2個全連接層，如圖8所示。對於卷積層，主要使用1x1卷積來做channle rection，然後緊跟3x3卷積。

『柒』 目標檢測演算法是什麼

目標檢測演算法是先通過訓練集學習一個分類器，然後在測試圖像中以不同scale的窗口滑動掃描整個圖像；每次掃描做一下分類，判斷一下當前的這個窗口是否為要檢測的目標。檢測演算法的核心是分類，分類的核心一個是用什麼特徵，一個是用哪種分類器。

(7)視頻目標檢測演算法擴展閱讀：

目標檢測演算法可以分為：

1、背景建模法，包含時間平均模型、混合高斯模型、動態紋理背景、PCA模型、時一空聯合分布背景模型

2、點檢測法，包含Moravec檢測器、Harris檢測器 、仿射不變點檢測、S IFT

3、圖像分割法，包含Mean Shift方法 、Graph-cut方法、Active Contours方法

4、聚類分析法，包含支持向量機、神經網路、Adaptive Boosting

5、運動矢量場法，包含基於運動矢量場的方法

『捌』 計算機視覺——典型的目標檢測演算法(Fast R-CNN演算法)（五）

【嵌牛導讀】目標檢測在現實中的應用很廣泛，我們需要檢測數字圖像中的物體位置以及類別，它需要我們構建一個模型，模型的輸入一張圖片，模型的輸出需要圈出圖片中所有物體的位置以及物體所屬的類別。在深度學習浪潮到來之前，目標檢測精度的進步十分緩慢，靠傳統依靠手工特徵的方法來提高精度已是相當困難的事。而ImageNet分類大賽出現的卷積神經網路（CNN）——AlexNet所展現的強大性能，吸引著學者們將CNN遷移到了其他的任務，這也包括著目標檢測任務，近年來，出現了很多目標檢測演算法。

【嵌牛鼻子】計算機視覺

【嵌牛提問】如何理解目標檢測演算法——Fast R-CNN

【嵌牛正文】

        為克服SPP-Net 存衡基在的問題，2015 年Girshick 等提出基於邊界框和多任務損失分類的Fast R-CNN[31]演算法。該演算法將SPP 層簡化，設計出單尺度的ROI Pooling 池化層結構；將整張圖像的候選區域采樣成固定大小，生成特徵圖後作SVD分解，通過RoI Pooling層得到Softmax的分類得分和BoundingBox 外接矩形框的窗口回歸兩個向量；用Softmax 代替SVM 提出多任務損失函數思想，將深度網路和SVM分類兩個階段整合，即將分類問題和邊框回歸問題進行合並。

演算法詳解：

Fast R-CNN的流程圖如下，網路有兩個輸入： 圖像和對應的region proposal 。其中region proposal由selective search方法得到，沒有表示在流程圖中。對每個類別都訓練一個回歸器，且只有非背景的region proposal才需要進行回歸。

ROI pooling：ROI Pooling的作用是對不同大小的region proposal，從最後卷積層輸出的feature map提取大小固定的feature map。簡單講可以看做是SPPNet的簡化版本，因為全連接層的輸入需要尺寸大小一樣，所以不能直接將不同大小的region proposal映射到feature map作為輸出，需要做尺寸變換。在文章中，VGG16網路使用搭中H=W=7的參數，即將一個h*w的region proposal分割成H*W大小的網格，然後知攔山將這個region proposal映射到最後一個卷積層輸出的feature map，最後計算每個網格里的最大值作為該網格的輸出，所以不管ROI pooling之前的feature map大小是多少，ROI pooling後得到的feature map大小都是H*W。

因此可以看出Fast RCNN主要有3個改進：1、卷積不再是對每個region proposal進行，而是直接對整張圖像，這樣減少了很多重復計算。原來RCNN是對每個region proposal分別做卷積，因為一張圖像中有2000左右的region proposal，肯定相互之間的重疊率很高，因此產生重復計算。2、用ROI pooling進行特徵的尺寸變換，因為全連接層的輸入要求尺寸大小一樣，因此不能直接把region proposal作為輸入。3、將regressor放進網路一起訓練，每個類別對應一個regressor，同時用softmax代替原來的SVM分類器。

在實際訓練中，每個mini-batch包含2張圖像和128個region proposal（或者叫ROI），也就是每張圖像有64個ROI。然後從這些ROI中挑選約25%的ROI，這些ROI和ground truth的IOU值都大於0.5。另外只採用隨機水平翻轉的方式增加數據集。

測試的時候則每張圖像大約2000個ROI。

損失函數的定義是將分類的loss和回歸的loss整合在一起，其中分類採用log loss，即對真實分類（下圖中的pu）的概率取負log，而回歸的loss和R-CNN基本一樣。分類層輸出K+1維，表示K個類和1個背景類。

這是回歸的loss，其中t^u表示預測的結果，u表示類別。v表示真實的結果，即bounding box regression target。

採用SVD分解改進全連接層。如果是一個普通的分類網路，那麼全連接層的計算應該遠不及卷積層的計算，但是針對object detection，Fast RCNN在ROI pooling後每個region proposal都要經過幾個全連接層，這使得全連接層的計算占網路的計算將近一半，如下圖，所以作者採用SVD來簡化全連接層的計算。另一篇博客鏈接講的R-FCN網路則是對這個全連接層計算優化的新的演算法。

稍微總結下訓練和測試的結構，如下面兩個圖，對演算法的理解會更清晰。

test結構圖在ROI Pooling層是怎麼輸出的畫得比較容易理解。