改進YOLOv3和Deep Sort的多目標跟蹤算法

胡 漫，曹繼華，李士心，彭芙蓉

（天津職業技術師范大學電子工程學院，天津 300222）

隨著計算機和人工智能的發展，目標檢測和跟蹤成為人們關注的熱點，在自動駕駛、智能交通和視頻監測等場景有著越來越重要的作用。目標檢測是在圖像中確定目標物體的位置和類別。傳統的目標檢測算法是在圖像上先作選擇區域，再人為設定特征提取，最后根據提取的特征進行目標分類。而基于深度學習的目標檢測則是通過神經網絡來提取特征。神經網絡在訓練學習后有很強大的特征提取能力，使得檢測精度更高。基于神經網絡的目標檢測包含一階段目標檢測（One-stage）和兩階段目標檢測（Two-stage）。Onestage中經典的算法有SSD、CornerNet、YOLO系列等，Two-stage中經典的算法有R-CNN、Faster R-CNN、Fast R-CNN等。目標跟蹤是估計視頻序列中的目標運動狀態，得到目標在每一幀即每個時刻的位置。隨著目標檢測精度的提高，目標跟蹤也得到發展。基于檢測的目標跟蹤分為2步：通過目標檢測，檢測出每一幀圖像中的目標物體；用數據關聯算法將目標物體跟蹤預測的邊界框（bounding BOX，BBOX）和目標檢測出的目標物體邊界框相關聯，之后用檢測的邊界框代表成功跟蹤的物體。

近年來，單目標跟蹤算法已發展得相對成熟，但在實際的場景中，如交通、自動駕駛、智能監控中跟蹤算法是多目標問題，多目標跟蹤算法還面臨著許多問題，如目標間的遮擋導致遮擋后目標發生變換，即目標ID切換，目標漏檢或誤檢，未知的目標類別等。針對多目標跟蹤問題，Bewley等[1]提出了SORT算法，該算法用卡爾曼和匈牙利算法實現多目標跟蹤，但在有遮擋情況下效果較差；Wojke等[2-3]提出DeepSort算法，在SORT算法基礎上加入了關聯匹配，改善了遮擋問題，但依然存在漏檢追蹤不到的問題。YOLO系列在檢測方面也得到了很大發展，李珣等[4]通過對道路場景分析改進YOLO-voc網絡，改善目標檢測率低的問題；黎洲等[5]改進YOLOv2解決檢測實時性問題；劉軍等[6]加強了Ting YOLOv3網絡，并與卡爾曼和匈牙利算法結合實現跟蹤；柳長源等[7]把YOLOv3的主干輕量化并重新K-means聚類提高檢測效率。針對現實場景中有遮擋檢測時目標漏檢和跟蹤時目標ID切換現象，本文對YOLOv3進行改進，用完全交并比（complete intersection over union，CIOU）損失代替原算法中的邊界框損失函數，同時對先驗框（Anchor BOX）用K-means++算法重新聚類選取適合的Anchor BOX；將DeepSort算法中第二次匹配的交并比（intersection over union，IOU）匹配用廣義交并比（generalized intersection over union，CIOU）匹配代替，提高匹配性能；將改進的YOLOv3與DeepSort結合，實現目標跟蹤，減少遮擋時目標ID切換現象。

1 YOLOv3算法及改進

1.1 YOLOv3算法

YOLO是一種端到端的目標檢測，將檢測目標簡化成回歸問題，求解包含有目標的框和目標分類的概率。YOLOv2是YOLO的改進，YOLOv3在YOLOv2的基礎上融合添加了特征金字塔網絡（feature pyramid network，FPN）[8]和殘差網絡（ResNet）[9]等提高分類準確度和速度。

YOLOv3主要由特征提取網絡和預測網絡構成。YOLOv2使用Darknet-19網絡提取特征，YOLOv3的特征提取網絡是在YOLOv2的基礎上加入殘差網絡中的殘差（residual）結構。該特征提取網絡中加入了直連（shortcut）并使用了許多3×3和1×1的卷積層連接，結構復雜。因為總體有53個卷積層，所以其也被稱為Darknet-53，其和CNN網絡結構的不同之處在于Darknet-53是一個全卷積網絡。在YOLOv3的前向傳播中，通過變換卷積核的步長來改變張量的尺寸，卷積步長為2，每卷積一次圖像邊長減少1/2，Darknet-53中有5次卷積，特征圖經過5次卷積后減小到原來的1/32。

在預測方面，YOLOv3使用多尺度結合的方式把一個圖片分為13×13、26×26、52×52的網格，各網格負責自身網格范圍的檢測。預測任務輸出的特征大小為N×N×[3×（4+1+C）]，其中：N為網格大小；3為每個網格的邊界框數目；4為邊界框的坐標數目；1為目標預測的值；C為預測的類別數目。類別預測上YOLOv3把單標簽分類的softmax層變為多標簽分類的邏輯回歸層，使用邏輯回歸分類器中sigmoid函數將輸出范圍限制到0～1，對各個類做二分類處理，當輸出值＞0.5表示檢測的物體屬于目標類。

YOLOv3沿用了YOLOv2預測的方法，利用Kmeans聚類的方法在訓練集中聚類出9個先驗框作為初始邊框。邊界框是通過回歸得到4個偏移值tx、ty、tw、th后在先驗框的基礎上進行變換得到的邊框。變換公式為

式中：bx、by為邊界框在特征圖中心點的坐標；bw、bh分別為邊界框的高和寬；cx、cy為特征圖現在中心左上角的網格高和寬；pw、ph分別為Anchor Box的高和寬；σ（）為sigmoid函數。

YOLOv3的損失函數是把YOLOv2中分類損失變成二分交叉熵。損失函數由中心坐標誤差、寬高坐標誤差、置信度誤差和分類誤差4部分組成。損失函數為

式中：第1項為中心坐標誤差；λcoord為5，表示邊界框損失的權重；k×k為網格的大小，即13×13、26×26和52×52；M為3表示候選框的個數；Iijobj為第i個網格中第j個先驗框是否負責檢測目標，負責Iijobj為1，否則為0；xi、yi為橫縱坐標。第2項為寬高坐標誤差，wi、hi為高度和寬度。第3項和第4項為置信度誤差，λnoobj為0.5，表示置信度損失的函數；為真實值，取值決定于邊界框是否負責預測目標，若是則取1，否則為0；Iijnoobj與Iijobj相反，為第i個網格中第j個先驗框不負責檢測目標。最后一項為分類誤差，pi為類別預測值，為其真實值。

1.2 改進的YOLOv3

1.2.1 先驗框改進

YOLOv3共使用9組Anchor Box進行預測，當數據集變化時，Anchor Box的尺寸也需變化以更好地檢測目標，提高檢測精度。初始YOLOv3中的Anchor Box是針對COCO數據集聚類得到的，因為COCO數據集有80類且大小不一，所以聚類出來的Anchor Box形狀不同。初始YOLOv3使用K-means算法聚類Anchor Box，但K-means算法初始點的選擇對聚類結果有很大的影響，不能保證是全局最優。為降低初始點選取對結果的影響，本文采用K-means++[10]算法對初始點選取進行改進，逐個選取初始點，對KITTI數據集中行人和車輛2類重新聚類先驗框。K-means++算法的步驟為：①從輸入的數據集Y中隨機選個樣本點當作開始的聚類中心Cj；②對每一個樣本點Yj分別計算其與已選取聚類中心的距離D（Yj），D（Yj）=1-GIOU（Yj，Cj）；③按輪盤法選取新的聚類中心，距離即D（Yj）大的點被選取的概率較大；④重復迭代步驟②和步驟③，直到選出9個聚類中心點；⑤利用選出的9個聚類中心點作為初始點運行K-means算法。

1.2.2 邊界框損失函數改進

YOLOv3算法中用IOU來評價2個邊界框的相似程度，IOU為2個邊界寬度交并比，表達式為

式中：A、B分別為預測框和真實框。

YOLOv3對1和IOU的差值梯度回歸表達式為

該損失函數能有效訓練網絡，但當預測框和真實框沒有交集時，不能表示2個框的遠近，此時沒有梯度回傳不能進行訓練。針對該問題Rezatofighi等[11]提出了GIOU的新方法，在IOU的基礎上為2個框加上了最小外接矩形，從而避免了IOU的缺點。GIOU首先計算預測框、真實框和其最小外接矩形的面積S及其IOU，再用最小外接面積減去2個框的并集的差除以S，最后用IOU減去除數，即

GIOU依然依賴IOU導致GIOU在2個垂直方向上誤差大，難以收斂，回歸效果差。Zheng等[12]提出了距離交并比（distance intersection over union，DIOU）的想法，與GIOU相比，用DIOU最小化預測框和真實框中心點的距離來加速收斂過程，表達式為式中：d2（A，B）為兩框中心點之間的歐氏距離的平方；C為能同時包含2個框的最小區域的對角線的距離。

DIOU直接最小化預測框和真實框的距離，所以收斂速度很快。但是，DIOU沒有考慮預測框和真實框的縱橫比。文章還提出CIOU LOSS，即在DIOU的基礎上添加一個αv因子，把預測框橫縱比擬合真實框橫縱比將框的橫縱比考慮進去，提高了精度。表達式為

綜上對比，本文選用CIOU損失函數來改進邊界框損失函數。完整CIOU損失函數為

改進后的YOLOv3損失函數為

2 DeepSort目標跟蹤

DeepSort跟蹤算法框架如圖1所示。在YOLOv3檢測出目標后使用卡爾曼濾波算法預測跟蹤目標，使用匈牙利算法進行計算，關聯匹配時融合運動特征和外觀特征。

圖1 跟蹤算法框架

2.1 卡爾曼濾波和匈牙利算法

卡爾曼濾波可以基于當前幀的目標位置來預測下一幀的目標位置。在任一視頻幀中將狀態向量

X=[u，v，r，h，u′，v′，r′，h′]作為目標軌跡模型，其中：u、v分別為目標邊界框中心的水平和垂直位置；r、h分別為目標邊界框的長寬比和高度；其余4個參數為對應的速度信息。通過卡爾曼濾波器進行預測和更新，預測是利用上一幀檢測框和運動速度等預測當前幀相應信息，預測方程和協方差方程為

式中：X（k|k-1）為k-1時預測到k時的狀態向量；X（k-1|k-1）為k-1時刻的最優狀態向量；P（k|k-1）和P（k-1|k-1）分別為前者的協方差矩陣；Q為噪聲的協方差。更新是對預測值和觀測值線性加權來得到接近真實狀態的預測值。更新k時刻的協方差，使更新重復運行，表達式為

式中：X（k|k）為k時刻協方差的更新結果；Kk為k時刻卡爾曼增益矩陣。

匈牙利算法主要解決檢測目標和預測目標的匹配，該算法對融合運動特征和外觀特征級聯匹配整合得到代價矩陣求解得到線性匹配，從而完成上下2幀檢測和預測目標的匹配。

2.2 融入外觀特征的關聯匹配

目標跟蹤的一個關鍵問題便是將檢測目標與跟蹤預測目標進行關聯匹配，本文的關聯匹配融合了運動特征，即空間坐標信息和外觀特征。

對于運動特征，采用馬氏距離計算改進YOLOv3網絡檢測得到的目標和卡爾曼跟蹤預測目標之間的距離為

采用二值函數公式如式（13）對式（12）進行匹配限制，當二者間距離≤特定閾值時，表示關聯匹配成功。

由于跟蹤過程中，目標容易被遮擋或出現目標交叉而導致跟蹤目標丟失或發生錯配，只用運動特征來關聯匹配，很大可能會出現目標丟失或錯配，需加入外觀特征來減少這種情況。

對于外觀特征，由于同一個物體在不同圖像中生成的特征向量間余弦值很小，所以采用余弦度量距離計算第i個跟蹤預測目標的所有特征向量和第j個檢測目標特征向量間余弦距離的最小值，余弦度量計算式為

同樣采用二值函數公式（15）對式（14）作匹配限制，當最小值≤特定閾值時，表示關聯匹配成功。

對運動特征和外觀特征進行線性加權作為最終的關聯匹配，表達式為

2.3 GIOU匹配

在關聯匹配后，把未成功匹配和沒有匹配的預測目標放在一起與未匹配的檢測目標繼續GIOU匹配，用來減少因動作突然變化或一部分被遮擋而造成的匹配錯誤。由于是在關聯匹配后繼續防止匹配錯誤，使用GIOU加入最小外接矩形面積匹配可以達到較好的效果。首先計算預測框和檢測框間的GIOU如式（5），經過1-GIOU后得到1個代價矩陣，然后將代價矩陣輸入匈牙利算法，從而得出線性匹配的結果。最后篩選匹配結果，刪去GIOU較小的區域。合并關聯匹配和GIOU匹配的結果為最終的匹配結果。

3 實驗與分析

3.1 實驗準備

選用KITTI數據集[13]作為本文的檢測數據集，KITTI是當前自動駕駛場景下最全面的數據集，包含市區、高速公路、鄉村等地方采集的數據。其中，KITTI目標檢測數據集中訓練集、測試集分別包含7 481張和7 518張圖片；KITTI目標跟蹤集中，訓練集有21個視頻序列，測試集有29個視頻序列。目標檢測數據集 中 原 有 標 簽 為8類，即Car、Van、Truck、Tram、Pedestrain、Person（sit-ting）、Cyclist、Misc；根據本文需要，把這8類合并為車輛和行人2類，將Misc類刪除。訓練集按8∶2分為訓練集和測試集。實驗使用Windiows 10操作系統、Pycharm軟件、Python語言、TensorFlow框架搭建環境完成。

3.2 評價指標

目標檢測選用均值平均精度（mean Average Precision，mAP）和F1-score（F1）來評價。mAP計算前需知精確率P和召回率R這2個指標，計算式為

精確率代表其中1類在預測目標時，預測正確的樣本占總體正確樣本的比例，召回率代表其中1類預測目標時，正確樣本占總預測樣本的比例。AP為用準精確率作縱坐標、召回率作橫坐標畫出的P-R曲線。AP為曲線下的面積，mAP為AP的平均值，本文數據集中只包含2個類別，mAP計算式為

F1-score為對精準度和召回率的調和平均，該值能夠更好地表示模型的好壞。

3.3 實驗結果分析

選取KITTI-Tracking中序號00中的80～100幀圖像、序號02中100～120幀圖像、序號15中110～135幀圖像，因為這些序號的視頻段中車輛行人較多且有不同程度的遮擋。將圖像合成視頻輸入到整個算法中，檢測跟蹤并把輸出的結果視頻分解為幀照片。圖2為原YOLOv3與改進后的算法檢測對比圖。

圖2 算法檢測對比

圖2（a）中左面白色汽車和右方黃色汽車沒有被檢測到，而圖2（b）中改進后算法能夠檢測出圖2（a）中未檢測到的車輛。

序列15的原YOLOv3-DeepSort的跟蹤結果與序列15的改進后算法的跟蹤結果分別如圖3和圖4所示。

圖3 原YOLOv3-DeepSort跟蹤檢測結果

圖4 改進后算法跟蹤檢測結果

對比圖3、圖4可知，由于長時間遮擋，圖3（b）中2個行人在跟蹤時丟失1個，只匹配跟蹤到1人，而改進后的算法在同一幀時依然能夠匹配跟蹤到2個行人，沒有丟失目標。

圖5為序列02的原YOLOv3-DeepSort的跟蹤結果，圖6為序列02的改進后算法的跟蹤結果。

圖5 原YOLOv3-DeepSort跟蹤檢測結果

圖6 改進后算法跟蹤檢測結果

對比圖5、圖6可知，由于兩車交匯遮擋，圖5（b）中的車輛17沒有被匹配跟蹤到而丟失目標，而圖6（b）中改進后算法依然能夠匹配跟蹤到車輛沒有丟失目標。

改進后的算法與原YOLO算法的實驗數據對比結果如表1所示。

表1 改進后算法與原YOLO算法的實驗數據對比

從表1可知，改進的YOLOv3比原YOLOv3在KITTI數據集的mAP提高2.19%，F1提高1.23%。

4 結語

本文提出一種基于改進YOLOv3和DeepSort的跟蹤算法，用于提高現實場景有遮擋情況中檢測跟蹤車輛、行人等目標的漏檢和目標ID切換的誤檢。通過使用K-means++算法重新聚類選取適合的先驗框，改變邊界框損失函數對YOLOv3改進提高精度，再結合DeepSort算法，將未成功匹配及未匹配的檢測結果用GIOU匹配代替IOU匹配。最終算法在KITTI數據集上的mAP提高2.19%，F1-score提高1.23%，能夠在部分遮擋時，較少漏檢和目標ID切換的誤檢。本文雖在此方面取得一定的成果，但仍有繼續研究的地方，如考慮復雜場景（雨雪大霧天氣）中的檢測跟蹤，可結合暗通道去霧算法或其他方法。