⑴ 目標檢測中的樣本不平衡處理方法——OHEM, Focal Loss, GHM, PISA
GitHub
CSDN
目前。計算機視覺中的性能最好的目標檢測方法主要分為兩種: one-stage 和two-stage 方法。two-stage方法分為兩步，第一步為候選區域生成階段(Proposal stage),通過如Selective Search、EdgeBoxes等方法可以生成數量相對較小候選目標檢測框；第二步為分類與回歸階段，對第一階段生成的 Candiate Proposal 進行分類和位置回歸。one-stage 代表性的方法是R-CNN系列，如 R-CNN， Fast R-CNN, Faster R-CNN。 而one-stage 方法直接對圖像的大量 Candiate Proposals 進行分類與回歸。
這兩類方法中均存在類別不平衡問題，two-stage 方法通過第一步已經將當量的候選區域降低到一個數量較小的范圍，同時又在第二步通過一些啟發式原則，將正負樣本的比例降低到一定程度。而 one-stage 優於沒有這降低候選框的步驟，因此，候選區域的數量大大超過 two-stage 方法，因此，在精度上，two-stage 仍然優於 one-stage 方法，但是在速度和模型復雜度上， one-stage 占優勢。
類別不平衡會使檢測器評估 的候選位置，但是通常只有少量的位置存在目標，這回導致兩個問題:
因此，解決樣本不平衡問題是提高目標檢測精度的一個關鍵技術之一。
論文題目： Training Region-based Object Detectors with Online Hard Example Mining
OHEM 是通過改進 Hard Example Mining 方法，使其適應online learning演算法特別是基於SGD的神經網路方法。Hard Example Mining 通過交替地用當前樣本集訓練模型，然後將模型固定，選擇 False Positive 樣本來重新組建用於下一次模型訓練的樣本集。但是因為訓練神經網路本事就是一個耗時的操作，這樣在訓練中固定模型，這樣會急劇降低模型的訓練進程。
Hard Examples Mining通常有兩種方法：
OHEM演算法的大致流程是: 首先計算出每個ROI的loss， 然後按loss從高到低來排列每個 ROI， 然後為每張圖片選擇 個損失最高的 ROI 作為Hard Examples，其中 B 表示總的 ROI 數量， 表示batch-size 的大小，在 Fast R-CNN 中， N=2， B=128時，效果很好。
但是如果直接按照 loss 對所有的 ROI 進行選擇，會有一個缺點，由於 ROI 很多，這樣 很多 ROI 的位置就會相關並重疊，如果和某個高 Loss 的 ROI 重合度很高的其它 ROI很多， 這樣， 這些 ROI 的 Loss 通常也會很多，這樣這些樣本都會被選擇，但是它們可以近似認為時同一個，這樣就會給其它較低 Loss 的 ROI 更少的選擇餘地，這樣就會存在冗餘。為了消除這種冗餘，作者提出先使用 NMS (non-maximum suppression) 刪除部分重合度很高的 ROI， 在使用上述方法進行 選擇 Hard Example。
實現技巧:
論文，作者將該方法是現在 Fsat R-CNN 目標檢測方法中。最簡單做法是更改損失函數層，損失函數層首先計算所有 ROI 的 loss， 然後根據 loss 對 ROI 進行排序，並選擇 hard RoIs， 讓 那些 non-RoIs的損失變為0. 這種方法雖然很簡單，但是非常不高效，因為還需要為所有的 RoIs 分配進行反向傳播時需要的內存空間。
為了克服這個缺點，作者對下面的 Figure 1 進行改進， 如下面的 Figure 2.該改進時使用兩份同樣的 RoI network。 其中一個是只讀的(readonly), 即只進行前向計算，不進行反向傳播優化，所以只需要為前向傳播分配內存，它的參數實時保持和另一個 RoI network（regular RoI network)保持一樣。在每次迭代時，首先使用 readonly RoI network 對每個 ROI 計算起 loss，然後用上面描述的選擇 hard RoIs 的方法選擇 hard RoIs. 然後利用 regular RoI network來對選擇的 hard RoIs 進行前向和後向計算來優化網路。
論文題目 Focal Loss for Dense Object Detection
在改論文中，作者認為樣本類別的不平衡可以歸結為難易樣本的不平衡，從而更改交叉熵損失函數，重新對樣本賦予不同的權值，之前的模型這些樣本都是同等重要的，從而使模型訓練更加關注 hard examples。
首先引入交叉熵的公式:
其中， ,表示真實類別， 表示我們預測的概率，為了方便，我們定義:
因此， ,該方法在 較大時，該loss是一個較小的量級， 如下圖的連線所示所示，因為存在大量的易分類樣本，相加後會淹沒正樣本的loss。
一個常見的解決類別不平衡的方式是引入一個加權因子 來表示正樣本的權重， 表示負樣本的權重。我們按照定義 的方法重新定義 為 , 定義如下:
雖然可以平衡 positive和negative的重要性，但是對 easy/hard 樣本還是無法區分， Focal loss 通過更 Cross loss來達到區分easy/hard的目的:
上圖展示了不同 取值對應的 loss，通過分析上述公式，我們發現，當 非常小時，即樣本被分類錯誤，此時 接近1， loss幾乎不受影響，當 接近於1時，即樣本被分類正確，此時 接近0，此時降低了該樣本的權重，比如，取 , 當時 時，該樣本的 loss 會降低100倍，
在實際應用中，作者使用了該 Focal loss的變體，即加入了 平衡因子:
作者提出，對於二分類，一般模型的模型初始化會同概率的對待正負樣本，由於類別不平衡，負樣本的 loss 會佔主導，作者提出在訓練初始階段對正樣本的概率估計「prior」的概念，用 表示， 通過設置它來達到正樣本的輸出概率低的效果，比如為0.01，從而使模型更加關注正樣本。實際操作中，出了最後一個用於分類的卷積層，其餘卷積層的參數初始化為bias ，而最後一層 , 實驗中設置為 0.01.
兩個實現細節
論文題目: Gradient Harmonized Single-stage Detector
改論文提出 Focal Loss 存在兩個缺點:
該論文有一句概括該篇論文的核心思想的一句話: 類別的不平衡可以歸結為難易樣本的不平衡，難易樣本的不平衡可以歸結為梯度的不平衡原話如下:
如下圖所示:
左邊是樣本數量關於梯度的分布，中間表示各個修正後的函數的梯度（使用了log scale）對原始梯度的，右邊表示所有樣本集的梯度貢獻的分布。
定義 是模型未經過 sigmoid 之前的輸出， 則 ,得出該損失函數對 的梯度為:
定義梯度的模長(norm) 為：
訓練樣本的梯度密度(Gradient Density)定義如下:
其中， 是第 k 個樣本的gradient norm，
這個公式可以理解為，以梯度 為中心，寬度為 的區域內的樣本密度。
梯度密度協調參數:
分母是對梯度位於 范圍的部分樣本進行歸一化，如果所有樣本的梯度時均分分布，那麼對於任意 都有 .(這里不是很理解為什麼N，可以理解它們相等)
通過將梯度密度協調參數將 GHM 嵌入到損失函數中，則 GHM-C Loss 為:
計算公式11時，求和有一個N，再求 時會遍歷所有的樣本，因此該公式的時間復雜度為 .如果並行的化，每個計算單元也有N的計算量。對gradient norm進行排序的最好的演算法復雜度為 ，然後用一個隊列去掃描樣本得到梯度密度的時間復雜度為 n 。基於排序的方法即使並行也不能較快的計算，因為N往往是 甚至 ，仍然是非常耗時的.
作者提出的近似求解的方法如下:
根據上述定義，得出近似梯度密度函數為:
利用上面的公式，由於我們可以事先求好 , 在求和時只需查找 即可，因此時間復雜度為 .
因為loss的計算是基於梯度密度函數，而梯度密度函數根據一個batch中的數據得到，一個batch的統計結果是有雜訊的。與batch normalization相同，作者用Exponential moving average來解決這個問題，也就是
將模型魚的的偏移量定義為 , 將真實的偏移量定義為 ,回歸loss採用 Smooth L1 loss:
其中
則 關於 的梯度為:
從公式可以看出，當樣本操作 時， 所有樣本都有相同的梯度 1， 這就使依賴梯度范數來區分不同樣本是不可能的， 一種簡單的替代方法時直接使用 作為衡量標准，但是該值理論上無限大，導致 無法實現，
為了將 GHM 應用到回歸損失上，作者修改了原始的 損失函數:
該函數和 具有類似的屬性，當d的絕對值很小時，近似 L2 loss， 當d的絕對值比較大時， 近似 L1 loss， 關於d的梯度為:
這樣就將梯度值限制在
定義 , 則 GHM-R Loss 為:
論文題目: Prime Sample Attention in Object Detection
PISA 方法和 Focal loss 和 GHM 有著不同， Focal loss 和 GHM 是利用 loss 來度量樣本的難以程度，而本篇論文作者從 mAP 出法來度量樣本的難易程度。
作者提出提出改論文的方法考慮了兩個方面:
Prime Samples 是指那些對檢測性能有著巨大影響的樣本。作者研究表明樣本的重要程度依賴於它和ground truth 的 IoU值，因此作者提出了一種 IOU-HLR 排序。
在目標檢測中時如何定義正樣本（True Positive)的呢？
剩餘的標注為負樣本。
mAP 的原理揭露了對目標檢測器更重要的 兩個准則 :
基於上述分析，作者提出了一種稱為 IoU-HLR 的排序方法，它既反映了局部的IoU關系(每個ground truth目標周圍)，也反映了全局的IoU關系(覆蓋整個圖像或小批圖像)。值得注意的是，不同於回歸前的邊界框坐標，IoU-HLR是根據樣本的最終定位位置來計算的，因為mAP是根據回歸後的樣本位置來計算的。
該排序方法的大致流程如下圖所示，其原理如下:
IoU-HLR遵循上述兩個准則。首先，它通過局部排序（即上面的步驟2）將每個單獨的 GT 的 對應的樣本中 IoU 較高的樣本放在前面，其次通過重采樣和排序(步驟3， 4)將不同 GT 的 對應的樣本中， 將 IoU 較高的放在了前面。
作者提出Prime Sample Attention，一種簡單且有效的采樣策略，該采樣策略將更多的注意力集中到 Prime examples 上， PISA 由兩部分組成: Importance- based Sample Reweighting(ISR)和Classification Aware Regression Loss(為CARL).
PISA 的訓練過程是基於 prime samples 而不是同等對待所有樣本。
作者提出一種基於 soft sampling 的方法: Importance-based Sample Reweighting (ISR), 他給不同樣本根據重要性賦予不同的權重。首先它將Iou-HLR排序轉化為線性映射的真實值。 IoU-HLR在每個類中分別進行計算。對於類 , 假設總共有 個樣本， 通過 IoU-HLR 表示為 . 其中 ,使用一個線性轉換函數將 轉換為 , 表示第 類中的第 個樣本的重要程度:
採用指數函數的形式來京一部將樣本重要性 轉換為 loss 的權值 , 表示對重要樣本給予多大的優先權的程度因子， 決定最小樣本權值的偏差(感覺就是一個決定最小的權值大小的一個變數)。
根據上面得到的權重值，重寫交叉熵:
其中 n 和 m 分別表示真樣本和負樣本的數量， 和 分別表示預測分數和分類目標，需要注意的是，如果只是簡單的添加 loss 權值將會改變 loss 的值，並改變正負樣本的比例，因此為了保持正樣本的總的 loss 值不變， 作者將 歸一化為
(這里不是很理解，歡迎大家解惑)
5.3.1 已經介紹如何染個分類器知道 prime samples， 那麼如何讓回歸其也知道 prime sample，作者提出了 Classification-Aware Regression Loss（CARL) 來聯合優化分類器和回歸其兩個分支。CARL可以提升主要樣本的分數，同時抑制其他樣本的分數。回歸質量決定了樣本的重要性，我們期望分類器對重要樣本輸出更高的分數。兩個分支的優化應該是相互關聯的，而不是相互獨立的。
作者的方法是讓回歸器知道分類器的分數，這樣梯度就可以從回歸器傳播到分期其分支。公式如下:
表示相應類別的預測分數， 表示輸出的回歸偏移量。利用一個指數函數將 轉化為 ，隨後根據所有樣本的平均值對它進行縮放。為了保持損失規模不變，對具有分類感知的 進行歸一化。 是常用的smooth L1 loss。
關於 的梯度與原回歸損失 成正比。 p_i mathcal{L}(d_i, hat d_i) mathcal{L}(d_i, hat d_i)$ 反映了樣本i的定位質量，因此可以認為是一個IoU的估計，進一步可以看作是一個IoU-HLR的估計。可以近似認為，排序靠前的樣本有較低的回歸損失，於是分類得分的梯度較小。對於CARL來說，分類分支受到回歸損失的監督。 不重要樣本的得分被極大的抑制掉，而對重要樣本的關注得到加強。
待續。。。
上面的方法大致可以分為兩種：
Focal Loss認為正負樣本的不平衡，本質上是因為難易樣本的不平衡，於是通過修改交叉熵，使得訓練過程更加關注那些困難樣本，而GHM在Focal Loss的基礎上繼續研究，發現難易樣本的不平衡本質上是因為梯度范數分布的不平衡，和Focal Loss的最大區別是GHM認為最困難的那些樣本應當認為是異常樣本，讓檢測器強行去擬合異常樣本對訓練過程是沒有幫助的。PISA則是跳出了Focal Loss的思路，認為采樣策略應當從mAP這個指標出發，通過IoU Hierarchical Local Rank (IoU-HLR)，對樣本進行排序並權值重標定，從而使得recall和precision都能夠提升。
⑵ 目標跟蹤檢測演算法（一）——傳統方法
姓名：劉帆；學號：20021210609；學院：電子工程學院
https://blog.csdn.net/qq_34919792/article/details/89893214
【嵌牛導讀】目標跟蹤演算法研究難點與挑戰在於實際復雜的應用環境 、背景相似干擾、光照條件的變化、遮擋等外界因素以及目標姿態變化，外觀變形，尺度變化、平面外旋轉、平面內旋轉、出視野、快速運動和運動模糊等。而且當目標跟蹤演算法投入實際應用時，不可避免的一個問題——實時性問題也是非常的重要。正是有了這些問題，才使得演算法研究充滿著難點和挑戰。
【嵌牛鼻子】目標跟蹤演算法，傳統演算法
【嵌牛提問】利用目標跟蹤檢測演算法要達到何目的?第一階段的單目標追蹤演算法包括什麼?具體步驟有哪些?它們有何特點?
【嵌牛正文】
第一階段
目標跟蹤分為兩個部分，一個是對指定目標尋找可以跟蹤的特徵，常用的有顏色，輪廓，特徵點，軌跡等，另一個是對目標特徵進行跟蹤。
1、靜態背景
1）背景差： 對背景的光照變化、雜訊干擾以及周期性運動等進行建模。通過當前幀減去背景圖來捕獲運動物體的過程。
2）幀差： 由於場景中的目標在運動，目標的影像在不同圖像幀中的位置不同。該類演算法對時間上連續的兩幀或三幀圖像進行差分運算，不同幀對應的像素點相減，判斷灰度差的絕對值，當絕對值超過一定閾值時，即可判斷為運動目標，從而實現目標的檢測功能。
與二幀差分法不同的是，三幀差分法（交並運算）去除了重影現象，可以檢測出較為完整的物體。幀間差分法的原理簡單，計算量小，能夠快速檢測出場景中的運動目標。但幀間差分法檢測的目標不完整，內部含有「空洞」，這是因為運動目標在相鄰幀之間的位置變化緩慢，目標內部在不同幀圖像中相重疊的部分很難檢測出來。幀間差分法通常不單獨用在目標檢測中，往往與其它的檢測演算法結合使用。
3）Codebook
演算法為圖像中每一個像素點建立一個碼本，每個碼本可以包括多個碼元（對應閾值范圍），在學習階段，對當前像素點進行匹配，如果該像素值在某個碼元的學習閾值內，也就是說與之前出現過的某種歷史情況偏離不大，則認為該像素點符合背景特徵，需要更新對應點的學習閾值和檢測閾值。
如果新來的像素值與每個碼元都不匹配，則可能是由於動態背景導致，這種情況下，我們需要為其建立一個新的碼元。每個像素點通過對應多個碼元，來適應復雜的動態背景。
在應用時，每隔一段時間選擇K幀通過更新演算法建立CodeBook背景模型，並且刪除超過一段時間未使用的碼元。
4）GMM
混合高斯模型（Gaussian of Micture Models，GMM）是較常用的背景去除方法之一（其他的還有均值法、中值法、滑動平均濾波等）。
首先我們需要了解單核高斯濾波的演算法步驟：
混合高斯建模GMM（Gaussian Mixture Model）作為單核高斯背景建模的擴展，是目前使用最廣泛的一種方法，GMM將背景模型描述為多個分布，每個像素的R、G、B三個通道像素值的變化分別由一個混合高斯模型分布來刻畫，符合其中一個分布模型的像素即為背景像素。作為最常用的一種背景建模方法，GMM有很多改進版本，比如利用紋理復雜度來更新差分閾值，通過像素變化的劇烈程度來動態調整學習率等。
5）ViBe（2011）
ViBe演算法主要特點是隨機背景更新策略，這和GMM有很大不同。其步驟和GMM類似。具體的思想就是為每個像素點存儲了一個樣本集，樣本集中采樣值就是該像素點過去的像素值和其鄰居點的像素值，然後將每一個新的像素值和樣本集進行比較來判斷是否屬於背景點。
其中pt（x）為新幀的像素值，R為設定值，p1、p2、p3….為樣本集中的像素值，以pt（x）為圓心R為半徑的圓被認為成一個集，當樣本集與此集的交集大於設定的閾值#min時，可認為此為背景像素點（交集越大，表示新像素點與樣本集越相關）。我們可以通過改變#min的值與R的值來改變模型的靈敏度。
Step1：初始化單幀圖像中每個像素點的背景模型。假設每一個像素和其鄰域像素的像素值在空域上有相似的分布。基於這種假設，每一個像素模型都可以用其鄰域中的像素來表示。為了保證背景模型符合統計學規律，鄰域的范圍要足夠大。當輸入第一幀圖像時，即t=0時，像素的背景模型。其中，NG（x,y）表示空域上相鄰的像素值，f(xi,yi)表示當前點的像素值。在N次的初始化的過程中，NG（x,y）中的像素點(xi,yi)被選中的可能次數為L=1,2,3,…,N。
Step2：對後續的圖像序列進行前景目標分割操作。當t=k時，像素點(x,y)的背景模型為BKm(x,y)，像素值為fk(x,y)。按照下面判斷該像素值是否為前景。這里上標r是隨機選的；T是預先設置好的閾值。當fk(x,y)滿足符合背景#N次時，我們認為像素點fk(x,y)為背景，否則為前景。
Step3：ViBe演算法的更新在時間和空間上都具有隨機性。每一個背景點有1/ φ的概率去更新自己的模型樣本值，同時也有1/ φ的概率去更新它的鄰居點的模型樣本值。更新鄰居的樣本值利用了像素值的空間傳播特性，背景模型逐漸向外擴散，這也有利於Ghost區域的更快的識別。同時當前景點計數達到臨界值時將其變為背景，並有1/ φ的概率去更新自己的模型樣本值（為了減少緩慢移動物體的影響和攝像機的抖動）。
可以有如下總結，ViBe中的每一個像素點在更新的時候都有一個時間和空間上隨機影響的范圍，這個范圍很小，大概3x3的樣子，這個是考慮到攝像頭抖動時會有坐標的輕微來回變化，這樣雖然由於ViBe的判別方式仍認為是背景點，但是也會對後面的判別產生影響，為了保證空間的連續性，隨機更新減少了這個影響。而在樣本值保留在樣本集中的概率隨著時間的增大而變小，這就保證了像素模型在時間上面的延續特性。
6）光流
光流是由物體或相機的運動引起的圖像對象在兩個連續幀之間的視在運動模式。它是2D矢量場，其中每個矢量是一個位移矢量，顯示點從第一幀到第二幀的移動。
光流實際上是一種特徵點跟蹤方法，其計算的為向量，基於三點假設：
1、場景中目標的像素在幀間運動時亮度（像素值或其衍生值）不發生變化；2、幀間位移不能太大；3、同一表面上的鄰近點都在做相同的運動；
光流跟蹤過程：1）對一個連續視頻幀序列進行處理；2）對每一幀進行前景目標檢測；3）對某一幀出現的前景目標，找出具有代表性的特徵點（Harris角點）；4）對於前後幀做像素值比較，尋找上一幀在當前幀中的最佳位置，從而得到前景目標在當前幀中的位置信息；5）重復上述步驟，即可實現目標跟蹤
2、運動場（分為相機固定，但是視角變化和相機是運動的）
1）運動建模（如視覺里程計運動模型、速度運動模型等）
運動學是對進行剛性位移的相機進行構型，一般通過6個變數來描述，3個直角坐標，3個歐拉角（橫滾、俯仰、偏航）。
Ⅰ、對相機的運動建模
由於這個不是我們本次所要討論的重點，但是在《概率機器人》一書中提出了很多很好的方法，相機的運動需要對圖像內的像素做位移矩陣和旋轉矩陣的坐標換算。除了對相機建立傳統的速度運動模型外，也可以用視覺里程計等通關過置信度的更新來得到概率最大位置。
Ⅱ、對於跟蹤目標的運動建模
該方法需要提前通過先驗知識知道所跟蹤的目標對象是什麼，比如車輛、行人、人臉等。通過對要跟蹤的目標進行建模，然後再利用該模型來進行實際的跟蹤。該方法必須提前知道要跟蹤的目標對象是什麼，然後再去跟蹤指定的目標，這是它的局限性，因而其推廣性相對比較差。（比如已知跟蹤的物體是羽毛球，那很容易通過前幾幀的取點，來建立整個羽毛球運動的拋物線模型）
2）核心搜索演算法（常見的預測演算法有Kalman(卡爾曼)濾波、擴展卡爾曼濾波、粒子濾波）
Ⅰ、Kalman 濾波
Kalman濾波器是通過前一狀態預測當前狀態，並使用當前觀測狀態進行校正，從而保證輸出狀態平穩變化，可有效抵抗觀測誤差。因此在運動目標跟蹤中也被廣泛使用。
在視頻處理的運動目標跟蹤里，每個目標的狀態可表示為(x,y,w,h)，x和y表示目標位置，w和h表示目標寬高。一般地認為目標的寬高是不變的，而其運動速度是勻速，那麼目標的狀態向量就應該擴展為(x,y,w,h,dx,dy)，其中dx和dy是目標當前時刻的速度。通過kalman濾波器來估計每個時刻目標狀態的大致過程為：
對視頻進行運動目標檢測，通過簡單匹配方法來給出目標的第一個和第二個狀態，從第三個狀態開始，就先使用kalman濾波器預測出當前狀態，再用當前幀圖像的檢測結果作為觀測值輸入給kalman濾波器，得到的校正結果就被認為是目標在當前幀的真實狀態。(其中，Zt為測量值，為預測值，ut為控制量，Kt為增益。)
Ⅱ、擴展卡爾曼濾波（EKF）和無跡卡爾曼濾波（UKF）
由於卡爾曼濾波的假設為線性問題，無法直接用在非線性問題上，EKF和UKF解決了這個問題（這個線性問題體現在用測量量來計算預測量的過程中）。EKF是通過構建線性函數g(x)，與非線性函數相切，並對每一時刻所求得的g（x）做KF，如下圖所示。
UKF與EKF去求解雅可比矩陣擬合線性方程的方法不同，通過對那個先驗分布中的採集點，來線性化隨機變數的非線性函數。與EKF所用的方法不同，UKF產生的高斯分布和實際高斯分布更加接近，其引起的近似誤差也更小。
Ⅲ、粒子濾波
1、初始狀態：基於粒子濾波的目標追蹤方法是一種生成式跟蹤方法，所以要有一個初始化的階段。對於第一幀圖像，人工標定出待檢測的目標，對該目標區域提出特徵；
2、搜索階段：現在已經知道了目標的特徵，然後就在目標的周圍撒點(particle), 如：a)均勻的撒點;b)按高斯分布撒點，就是近的地方撒得多，遠的地方撒的少。論文里使用的是後一種方法。每一個粒子都計算所在區域內的顏色直方圖，如初始化提取特徵一樣，然後對所有的相似度進行歸一化。文中相似性使用的是巴氏距離；
3、重采樣：根據粒子權重對粒子進行篩選，篩選過程中，既要大量保留權重大的粒子，又要有一小部分權重小的粒子；
4、狀態轉移：將重采樣後的粒子帶入狀態轉移方程得到新的預測粒子；
5、測量及更新：對目標點特徵化，並計算各個粒子和目標間的巴氏距離，更新粒子的權重；
6、決策階段：每個粒子都獲得一個和目標的相似度，相似度越高，目標在該范圍出現的可能性越高，將保留的所有粒子通過相似度加權後的結果作為目標可能的位置。
3）Meanshift演算法
MeanShift演算法屬於核密度估計法，它不需要任何先驗知識而完全依靠特徵空間中樣本點的計算其密度函數值。對於一組采樣數據，直方圖法通常把數據的值域分成若干相等的區間，數據按區間分成若干組，每組數據的個數與總參數個數的比率就是每個單元的概率值；核密度估計法的原理相似於直方圖法，只是多了一個用於平滑數據的核函數。採用核函數估計法，在采樣充分的情況下，能夠漸進地收斂於任意的密度函數，即可以對服從任何分布的數據進行密度估計。
Meanshift演算法步驟
1、通過對初始點（或者上一幀的目標點）為圓心，繪制一個半徑為R的圓心，尋找特徵和該點相似的點所構成的向量；
2、所有向量相加，可以獲得一個向量疊加，這個向量指向特徵點多的方向；
3、取步驟二的向量終點為初始點重復步驟一、二，直到得到的向量小於一定的閾值，也就是說明當前位置是特徵點密度最密集的地方，停止迭代，認為該點為當前幀的目標點；
4）Camshift演算法
Camshift演算法是MeanShift演算法的改進，稱為連續自適應的MeanShift演算法。Camshift 是由Meanshift 推導而來 Meanshift主要是用在單張影像上，但是獨立一張影像分析對追蹤而言並無意義，Camshift 就是利用MeanShift的方法，對影像串列進行分析。
1、首先在影像串列中選擇目標區域。
2、計算此區域的顏色直方圖（特徵提取）。
3、用MeanShift演演算法來收斂欲追蹤的區域。
4、通過目標點的位置和向量信息計算新的窗口大小，並標示之。
5、以此為參數重復步驟三、四。
Camshift 關鍵就在於當目標的大小發生改變的時候，此演算法可以自適應調整目標區域繼續跟蹤。
3、小結
第一階段的單目標追蹤演算法基本上都是傳統方法，計算量小，在嵌入式等設備中落地較多，opencv中也預留了大量的介面。通過上面的兩節的介紹，我們不難發現，目標檢測演算法的步驟分為兩部分，一部分是對指定目標尋找可以跟蹤的特徵，常用的有顏色，輪廓，特徵點，軌跡等，另一部分是對目標特徵進行跟蹤，如上文所提及的方法。所以目標檢測方法的發展，也可總結為兩個方面，一個是如何去獲得更加具有區分性的可跟蹤的穩定特徵，另一個是如何建立幀與幀之間的數據關聯，保證跟蹤目標是正確的。
隨著以概率為基礎的卡爾曼濾波、粒子濾波或是以Meanshift為代表向量疊加方法在目標檢測的運用，使得目標檢測不再需要假設自身的一個狀態為靜止的，而是可以是運動的，更加符合復雜場景中的目標跟蹤。
⑶ 目標檢測演算法（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
項目實踐貼個圖。