在技術(shù)日新月異的時(shí)代，今天的技術(shù)可能在明天就會(huì)被新的技術(shù)取代，例如現(xiàn)在爆火的大模型。但目前看來，大模型還不能做到無所不能。
所以這篇博客還是來考古一下，寫一下傳統(tǒng)的跟蹤算法。這里不是為了懟大模型而為了寫一篇傳統(tǒng)算法而寫傳統(tǒng)算法。只是覺得這個(gè)算法有個(gè)思想非常有意思，所以記錄一下。
該算法在2010年發(fā)表在ICPR上，它主要是提出了Forward-Backward errors這種跟蹤點(diǎn)的校驗(yàn)思想，使得跟蹤點(diǎn)更為可靠。但博主這里認(rèn)為，這篇文章其實(shí)還有一個(gè)比較有意思的一點(diǎn)，就是文章后面提出的MedianFlow跟蹤算法，里面利用了中位數(shù)來估計(jì)待跟蹤目標(biāo)的位移和縮放尺度。接下來大概按照文章結(jié)構(gòu)對(duì)該跟蹤算法進(jìn)行詳細(xì)說明。
一、Forward-Backwark errors（FB errors）
從名字上可以看出，F(xiàn)orward-Backwark errors其實(shí)就是根據(jù)跟蹤點(diǎn)前向和后向的結(jié)果來計(jì)算跟蹤點(diǎn)的偏差。如下圖所示：
從上圖上半部分可以看出算法流程是這樣的：
首先在第一幀輸入的圖片中定義需要跟蹤的點(diǎn)，例如圖中的點(diǎn)1和點(diǎn)2。為了這些點(diǎn)能夠更穩(wěn)定的被跟蹤，通常會(huì)采用像Harris角點(diǎn)檢測(cè)算法或者像FAST特征點(diǎn)檢測(cè)算法來提取圖片中特征明顯的點(diǎn)
利用點(diǎn)跟蹤算法，跟蹤第一幀的點(diǎn)在第二幀的位置。通常這里會(huì)采用Lucas-Kanade稀疏光流算法
通過第2步獲取到當(dāng)前幀的點(diǎn)后，再將這些點(diǎn)再次利用點(diǎn)跟蹤算法，計(jì)算出它們?cè)谇耙粠奈恢?/p>
利用第3步獲得的前一幀的點(diǎn)的位置和第1步初始化的點(diǎn)的位置計(jì)算點(diǎn)的偏差，這樣就得到了所謂的FB errors
根據(jù)FB errors就可以過濾掉位移較大的點(diǎn)，也就是跟蹤失敗的點(diǎn)
上圖中的下半部分是采用符號(hào)的形式來表示這個(gè)流程：
假設(shè)目前有k的圖片幀，用符號(hào)表示為S=(I_t, I_{t+1}...,I_{t+k}), x_t為在時(shí)刻t這一幀中待跟蹤的點(diǎn)
采用某種點(diǎn)跟蹤算法，跟蹤點(diǎn)x_t在后面k幀中的位置，這樣就可以得到一條點(diǎn)x_t的移動(dòng)軌跡T^{k}{f}=(x_t, x{t+1}, ..., x_{t+k})。這一步就稱為Forward
同理根據(jù)相同的跟蹤算法，將t+k幀中的跟蹤點(diǎn)x_{t+k}反向跟蹤回第t幀，這樣又可以得到一條移動(dòng)軌跡T^{k}=(\hat{x}t, \hat{x}{t+1},...,\hat{x}{t+k})，這里\hat{x}{t+k}=x{t+k}
FB errors用公式表示為FB(T{k}_{f}|S)=distance(T{k}{f}, T^{k})，文章為了簡單定義=distance(T^{k}{f}, T^{k})=||x_t-\hat{x}_t||。也就是說FB errors文章采用初始點(diǎn)和反向跟蹤到t幀的點(diǎn)之間的距離來表示
二、MedianFlow跟蹤算法
MedianFlow算法是在利用上述提出的FB errors基礎(chǔ)上獲取可靠的跟蹤點(diǎn)，進(jìn)而來跟蹤物體。MedianFlow跟蹤算法如下圖所示
如上圖中上半部分所示，現(xiàn)在有兩幀圖片I_t和I_{t+1}，現(xiàn)在想利用MedianFlow算法來跟蹤圖中的小車。也即輸入圖片I_t和I_{t+1}，bounding box \beta_t，跟蹤器輸出\beta_{t+1}。
算法流程如上圖中下半部分所示
根據(jù)輸入的bounding box \beta_t，在框中初始化一些待跟蹤點(diǎn)。這里的初始化方式跟第一部分所述有點(diǎn)不同。這里不采用角點(diǎn)或者特征點(diǎn)來初始化，而是簡單的采用在框中間距相同的點(diǎn)作為待跟蹤點(diǎn)
利用某種跟蹤點(diǎn)的算法，例如Lucas-Kanade稀疏光流算法跟蹤在t+1幀中點(diǎn)的位置
利用某種過濾算法將跟蹤失敗的點(diǎn)進(jìn)行過濾，當(dāng)然這里采用的就是FB errors將50%的誤差較大的點(diǎn)進(jìn)行過濾。文章其實(shí)還增加了一個(gè)叫NCC的方法（后面會(huì)做簡單說明），也將誤差較大的50%的點(diǎn)過濾掉。最終得到的點(diǎn)集就為跟蹤到的點(diǎn)
利用跟蹤到的點(diǎn)進(jìn)行t+1幀bounding box的預(yù)估
上面流程中有兩點(diǎn)需要待解釋，一個(gè)是NCC，一個(gè)是bounding box的預(yù)估。下面分別做一下介紹
2.1 Normalized Cross Correlation(NCC)
從名字可以看出這里就是去求兩個(gè)圖之間的歸一化互相關(guān)系數(shù)。
具體的對(duì)于輸入的兩個(gè)圖S_1和S_2，兩張圖的大小都為m\times n，它們之間的互相關(guān)系數(shù)用公式表示如下：
\rho=\frac{\frac{1}{mn}\summ_{i=1}\sum{n}{j=1}(S_1(i,j)-\overline{S}1)(S_2(i,j)-\overline{S}2)}{\sqrt{\frac{1}{mn}\sum^m{i=1}\sum^{n}{j=1}(S_1(i,j)-\overline{S}1)2}\sqrt{\frac{1}{mn}\summ{i=1}\sum^{n}{j=1}(S_2(i,j)-\overline{S}_2)^2}}
其中\(zhòng)overline{x}表示求平均操作。
所以NCC操作就是兩圖的協(xié)方差除以兩圖標(biāo)準(zhǔn)差的結(jié)果，又稱為Pearson相關(guān)系數(shù)。在MedianFlow兩個(gè)圖來源于對(duì)應(yīng)跟蹤點(diǎn)周邊一定大小的圖片塊。
2.2 bounding box的預(yù)估
要預(yù)估一個(gè)bounding box，我們只需要預(yù)估出新的bounding box的位移以及對(duì)應(yīng)的縮放尺寸。
我們通過下面兩步來分別預(yù)估這兩個(gè)參數(shù)
在得到可靠的跟蹤點(diǎn)后，計(jì)算所有可靠的跟蹤點(diǎn)的在x和y方向的移動(dòng)位置，分別取x方向移動(dòng)值的中位數(shù)和y方向移動(dòng)值的中位數(shù)作為新的bounding box相對(duì)之前bounding box的位移
在得到可靠的跟蹤點(diǎn)后，計(jì)算這些跟蹤點(diǎn)兩兩之間的距離以及在t幀中對(duì)應(yīng)點(diǎn)兩兩之間的距離，這些距離各自相除，出所有除數(shù)的中位數(shù)作為bounding box的縮放比例。
上面第2點(diǎn)可能有點(diǎn)繞，這里舉個(gè)例子來說明。假設(shè)在t+1幀中，通過過濾得到的跟蹤點(diǎn)有n個(gè)，那么對(duì)應(yīng)t幀中也有n個(gè)。計(jì)算t+1幀中n個(gè)點(diǎn)的兩兩之間的距離，得到nn個(gè)值，同理t幀對(duì)應(yīng)的點(diǎn)也可以得到nn個(gè)值，對(duì)應(yīng)兩幀中nn個(gè)值相除，得到nn個(gè)除數(shù)，這n*n個(gè)除數(shù)取其中的中位數(shù)就為新的bounding box的縮放尺寸。
MedianFlow算法在opencv中是有開源代碼的，可以路徑https://github.com/opencv/opencv_contrib/blob/3.4/modules/tracking/src/trackerMedianFlow.cpp
