目標跟蹤算法

一．互相關(guān)運算

給你一張我的正臉照（沒有經(jīng)過美顏處理的），你該如何在人群中找到我呢？一種最直觀的方案就是：“誰長得最像就是誰”。但是對于計算機來說，如何衡量“長得像”，并不是個簡單的問題。這就涉及一種基本的運算——互相關(guān)（cross-correlation）。互相關(guān)運算可以用來度量兩個信號之間的相似性。在離散的圖像空間中，它的數(shù)學(xué)定義是這樣的：

h和 f分別為核和圖像，代表著要搜索的目標模版和存在要搜索的目標的圖像。如果這個公式對你來說有點難以理解，那你又能否記起離散圖像空間卷積運算的定義：

從公式看，它倆不就是把 h水平、垂直分別翻轉(zhuǎn)一下的關(guān)系嘛！實際上，在很多機器學(xué)習(xí)庫的實現(xiàn)中，所謂的“卷積”就是通過互相關(guān)運算來實現(xiàn)的——反正卷積核中的所有參數(shù)都是通過優(yōu)化得到的、物理意義不明的值，它要做的僅僅是“在卷積核合適的位置學(xué)習(xí)合適的值”。嚴格使用卷積運算學(xué)習(xí)得到的核，等價于使用互相關(guān)運算學(xué)習(xí)到的核的180度翻轉(zhuǎn)。

互相關(guān)運算讓得以衡量 h與 f的相似度，互相關(guān)得到的響應(yīng)圖中每個像素的響應(yīng)高低代表著每個位置相似度的高低。假設(shè)目標存在于新一幀圖像
f中的話，那么在 h和 f對得最齊的地方就應(yīng)該是目標中心的位置了！

一些難點：目標的形狀、大小甚至身處的環(huán)境都是在不斷發(fā)生變化的。在考慮這些變數(shù)的同時，如何學(xué)習(xí)目標不變的那些特性，從而準確地進行定位呢？或者說，如何讓核
h能夠通過與 f的互相關(guān)運算來最有效地得到響應(yīng)呢？這也就是單目標跟蹤主流方法所嘗試的思路。

定義則是響應(yīng)圖的ground truth。因為處理的是一個連續(xù)的圖像序列，所以還存在下標
i通過對上式中的 h對整個圖像序列進行優(yōu)化，可以讓目標跟蹤算法學(xué)習(xí)一個最優(yōu)的相關(guān)濾波器。為了提升優(yōu)化的速度，還可以把
h和f 投射到傅里葉頻域。空域中的互相關(guān)運算在頻域中變成了逐項相乘，優(yōu)化目標也就變了。

它等價于：

那么對于整個序列而言，可以解出最優(yōu)的：

但這并不一定對于每一幀圖像都是最優(yōu)的。為了讓隨著序列的進行而適應(yīng)性地進行更新，可以遞歸式地定義不斷更新中的：

二．在線跟蹤（Online Tracking）和離線跟蹤（Offline Tracking）

通過調(diào)整更新學(xué)習(xí)率參數(shù)
η，可以讓算法學(xué)得具有高魯棒性并且能夠快速適應(yīng)目標外觀變化的。上述的過程就是首次在單目標跟蹤問題上使用相關(guān)濾波的工作——MOSSE[1])（Minimum Output Sum of Squared Error, CVPR10, F. Henriques et al.）的基本思路。

多目標跟蹤算法又可分為在線跟蹤（Online Tracking）和離線跟蹤（Offline Tracking）。在線跟蹤要求處理每一幀時，決定當(dāng)前幀的跟蹤結(jié)果時只能利用當(dāng)前幀和之前的幀中的信息，也不能根據(jù)當(dāng)前幀的信息來修改之前幀的跟蹤結(jié)果。離線跟蹤則允許利用之后的幀的信息從而獲得全局最優(yōu)解。離線追蹤的設(shè)定也不太適合實際應(yīng)用場景，但是以一種“batch”的形式進行的離線跟蹤（每次得到若干幀，在這些幀中求全局最優(yōu)）也是可行的，只是會導(dǎo)致一點延遲。

按照處理方式分類。上：在線跟蹤；下：離線跟蹤

三．匈牙利與Kalman filter

主流的目標跟蹤算法都是基于Tracking-by-Detecton策略，即基于目標檢測的結(jié)果來進行目標跟蹤。DeepSORT運用的就是這個策略，DeepSORT對人群進行跟蹤，每個bbox左上角的數(shù)字是用來標識某個人的唯一ID號。

這里就有個問題，如果視頻中不同時刻的同一個人，位置發(fā)生了變化，那么是如何關(guān)聯(lián)上的呢？答案就是匈牙利算法和卡爾曼濾波。

· 匈牙利算法可以告訴當(dāng)前幀的某個目標，是否與前一幀的某個目標相同。

· 卡爾曼濾波可以基于目標前一時刻的位置，來預(yù)測當(dāng)前時刻的位置，并且可以比傳感器（在目標跟蹤中即目標檢測器，比如Yolo等）更準確的估計目標的位置。

匈牙利算法（Hungarian Algorithm）

首先，先介紹一下什么是分配問題（Assignment Problem）：假設(shè)有N個人和N個任務(wù)，每個任務(wù)可以任意分配給不同的人，已知每個人完成每個任務(wù)要花費的代價不盡相同，那么如何分配可以使得總的代價最小。

舉個例子，假設(shè)現(xiàn)在有3個任務(wù)，要分別分配給3個人，每個人完成各個任務(wù)所需代價矩陣（cost matrix）如下所示（這個代價可以是金錢、時間等等）：

怎樣才能找到一個最優(yōu)分配，使得完成所有任務(wù)花費的代價最小呢？

匈牙利算法（又叫KM算法）就是用來解決分配問題的一種方法，它基于定理：

如果代價矩陣的某一行或某一列同時加上或減去某個數(shù)，則這個新的代價矩陣的最優(yōu)分配仍然是原代價矩陣的最優(yōu)分配。

算法步驟（假設(shè)矩陣為NxN方陣）：

1. 對于矩陣的每一行，減去其中最小的元素

2. 對于矩陣的每一列，減去其中最小的元素

3. 用最少的水平線或垂直線覆蓋矩陣中所有的0

4. 如果線的數(shù)量等于N，則找到了最優(yōu)分配，算法結(jié)束，否則進入步驟5

5. 找到?jīng)]有被任何線覆蓋的最小元素，每個沒被線覆蓋的行減去這個元素，每個被線覆蓋的列加上這個元素，返回步驟3

卡爾曼濾波（Kalman Filter）

卡爾曼濾波被廣泛應(yīng)用于無人機、自動駕駛、衛(wèi)星導(dǎo)航等領(lǐng)域，簡單來說，其作用就是基于傳感器的測量值來更新預(yù)測值，以達到更精確的估計。

假設(shè)要跟蹤小車的位置變化，如下圖所示，藍色的分布是卡爾曼濾波預(yù)測值，棕色的分布是傳感器的測量值，灰色的分布就是預(yù)測值基于測量值更新后的最優(yōu)估計。

在這里插入圖片描述

協(xié)方差(Covariance )：表示目標位置信息的不確定性，由8x8的對角矩陣表示，矩陣中數(shù)字越大則表明不確定性越大，可以以任意值初始化。

·
卡爾曼濾波分為兩個階段：(1) 預(yù)測track在下一時刻的位置，(2) 基于detection來更新預(yù)測的位置。

下面將介紹這兩個階段用到的計算公式。（這里不涉及公式的原理推導(dǎo)，因為我也不清楚原理(?_?) ，只是說明一下各個公式的作用）

總結(jié)

以上是生活随笔為你收集整理的目标跟踪算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。