目前在online visual tracking這個(gè)領(lǐng)域，已經(jīng)涌現(xiàn)出很多的跟蹤算法，比較知名如TLD，Struck，OAB，CT等等。但是能做到非常快速而且效果還不錯(cuò)的相對就較少了，好多算法都是剛剛能實(shí)時(shí)，而且還是在圖像分辨率不是很大的情況下。之前在博客里提到一篇該領(lǐng)域的測評綜述1，對該領(lǐng)域大部分算法進(jìn)行了一個(gè)總結(jié)和評估，作者在一個(gè)有50個(gè)視頻的數(shù)據(jù)集上測試了29個(gè)算法，其中速度和效果都還不錯(cuò)的算法有TLD2和Struck3。Struck的評價(jià)運(yùn)行速度大概是20幀/s，TLD相對快一點(diǎn),，大概28幀/s。但這個(gè)速度仍然不是很快，而14年的一篇paper提出了一種叫做KCF(Kernerlized Correlation Filter)4的跟蹤算法使得速度有了很大提升，在同樣的測試數(shù)據(jù)集上，平均運(yùn)行速度達(dá)到172幀/s(使用HOG特征的情況下)。而且據(jù)paper的實(shí)驗(yàn)結(jié)果顯示，準(zhǔn)確率比Struck和TLD都高。之所以能有這么快的速度，得益于作者巧妙地通過循環(huán)偏移構(gòu)建出了分類器的訓(xùn)練樣本，從而使得數(shù)據(jù)矩陣變成了一個(gè)循環(huán)矩陣。然后基于循環(huán)矩陣的特性把問題的求解變換到了傅里葉變換域，從而避免了矩陣求逆的過程，大大降低了算法的復(fù)雜度。

問題闡述

目前跟蹤算法主流的思想還是基于tracking by detection，而訓(xùn)練樣本的選擇基本上就以目標(biāo)中心為提取正樣本，然后基于周圍的圖像提取負(fù)樣本。大部分算法都是采用非正即負(fù)的方法來標(biāo)記訓(xùn)練樣本，即正樣本標(biāo)簽為1，負(fù)樣本為0。這種標(biāo)記樣本的方法有一個(gè)問題就是不能很好的反應(yīng)每個(gè)負(fù)樣本的權(quán)重，即對離中心目標(biāo)遠(yuǎn)的樣本和離中心目標(biāo)的近的樣本同等看待。所以就有算法提出使用連續(xù)的標(biāo)簽進(jìn)行標(biāo)記樣本，即根據(jù)樣本中心里目標(biāo)的遠(yuǎn)近分別賦值[0,1]范圍的數(shù)。離目標(biāo)越近，值越趨向于1，離目標(biāo)越遠(yuǎn)，值越趨向于0。事實(shí)也證明這種標(biāo)記樣本的方法能得到更好的效果，比如Struck和KCF。Struck是通過一種loss函數(shù)隱式地采用了這種連續(xù)的樣本標(biāo)記方法，而KCF則通過使用[0,1]范圍的值作為樣本的回歸值，從而給不同偏移下得到的樣本不同的權(quán)重。

首先，我們先介紹一個(gè)簡單的線性回歸模型，然后再討論引入kernel之后的情況。樣本訓(xùn)練過程實(shí)際上是一個(gè)嶺回歸問題，或者叫做正則化最小二乘問題，它有一個(gè)閉式的解。假設(shè)給定一些訓(xùn)練樣本及其回歸值 {(x1,y1),(x2,y2),...,(xi,yi),...}{(x1,y1),(x2,y2),...,(xi,yi),...} ，其訓(xùn)練的最終目標(biāo)是找到一個(gè)函數(shù) f(z)=wTzf(z)=wTz 使得如下殘差函數(shù)最小，

minw∑i(f(xi)?yi)2+λ∥w∥2(1)(1)minw∑i(f(xi)?yi)2+λ∥w∥2

其中， λλ 是正則化參數(shù)，防止過擬合的。上式的閉式解可以參考線性最小二乘的求解得出如下，

w=(XTX+λI)?1XTy(2)(2)w=(XTX+λI)?1XTy

這里 XX 是由一個(gè)樣本的特征向量占一行組成的樣本矩陣。 yy 是對應(yīng)每個(gè)樣本的回歸值 yiyi 組成的列向量。 II 是個(gè)單位矩陣。 因?yàn)榭紤]到后面要在傅里葉域進(jìn)行計(jì)算，這里給出一個(gè)復(fù)數(shù)情況下的求解結(jié)果，其中 XHXH 是 XX 的共軛轉(zhuǎn)置， w?w? 是 ww 的共軛。

w?=(XHX+λI)?1XHy(3)(3)w?=(XHX+λI)?1XHy

現(xiàn)在問題來了，如果直接求解上述閉式解，其中的求逆計(jì)算隨著樣本數(shù)的增大是非常耗時(shí)的。顯然直接求解的方式是不靠譜的，這里這篇paper的作者通過巧妙地把上述閉式解變換到傅里葉變換域的方式，從而避開了矩陣求逆的運(yùn)算，大大節(jié)省了運(yùn)行時(shí)間。而這也是這篇paper的主要貢獻(xiàn)所在。

DFT下的線性回歸

為了解釋的簡明性，這里僅僅就一維的單通道信息做分析，也就是說這里的 xx 都是一維向量，當(dāng)然推廣到二維也是適用的，而且實(shí)際上代碼中也的確就是在二維上做的。我們看到式 (3)(3) 中的樣本矩陣 XX 如果是一個(gè)循環(huán)矩陣的話，該式子的計(jì)算就會變得容易很多。即，

X=C(x)=?????????x1xnxn?1?x2x2x1xn?x3x3x2x1?x4?????xnxn?1xn?2?x1?????????(4)(4)X=C(x)=[x1x2x3?xnxnx1x2?xn?1xn?1xnx1?xn?2?????x2x3x4?x1]

其中， xx 是矩陣的第一行，整個(gè)矩陣式由這一行的循環(huán)偏移得到的。那我們假設(shè)存在這么一個(gè)循環(huán)矩陣，看看接下來式 (3)(3) 會變成怎樣。首先列出一個(gè)循環(huán)矩陣擁有的一個(gè)性質(zhì)5如下：

X=FHdiag(x^)F(5)(5)X=FHdiag(x^)F

其中， xx 頭上的那個(gè)小帽 x^x^ 代表 xx 的傅里葉變換， FF 是離散傅里葉變換矩陣，即滿足 x^=Fxx^=Fx 。這樣把式 (5)(5) 代入式 (3)(3) 中得，

w?=(FHdiag(x^?)FFHdiag(x^)F+λI)?1FHdiag(x^?)Fy=F?1(diag(x^?⊙x^)+λI)?1diag(x^?)Fy=F?1diag(x^?x^?⊙x^+λ)Fy(6)(6)w?=(FHdiag(x^?)FFHdiag(x^)F+λI)?1FHdiag(x^?)Fy=F?1(diag(x^?⊙x^)+λI)?1diag(x^?)Fy=F?1diag(x^?x^?⊙x^+λ)Fy

其中， ⊙⊙ 代表向量對應(yīng)元素相乘，然后兩邊同時(shí)左乘 FF 得，

w^?=x^?⊙y^x^?⊙x^+λ(7)(7)w^?=x^?⊙y^x^?⊙x^+λ

至此，我們可以看出通過上述變換后，權(quán)重向量 ww 的求解變換到了傅里葉變換域，而且計(jì)算量大大降低。

構(gòu)建循環(huán)樣本矩陣

不同的提取訓(xùn)練樣本方法：左圖是以base圖像為中心，向周圍偏移得到的樣本作為負(fù)樣本；右圖是基于base圖像，做循環(huán)偏移得到的樣本作為負(fù)樣本。

通過上面的計(jì)算我們可以看出，如果能構(gòu)建一個(gè)循環(huán)矩陣，那么就能極大的加速樣本的訓(xùn)練過程。那到底能不能呢，我們先來看一組基于目標(biāo)中心周圍偏移提取的正負(fù)訓(xùn)練樣本。

通過右圖可以看出，常規(guī)的方法是以目標(biāo)圖像為base圖像，基于該圖像左右上下偏移得出一系列的圖像塊作為負(fù)樣本進(jìn)行訓(xùn)練(左圖所示)。而通過對base圖像進(jìn)行循環(huán)偏移的方法可以得到一些近似的的負(fù)樣本作為訓(xùn)練樣本進(jìn)行訓(xùn)練(右圖所示)。這里我們發(fā)現(xiàn)通過循環(huán)偏移得到的圖像在邊界處并不是很平滑，消除這種現(xiàn)象的方式就是通過對base圖像乘以一個(gè)漢寧窗來降低邊緣圖像的權(quán)重。這樣，訓(xùn)練樣本構(gòu)成的樣本矩陣就變成了一個(gè)循環(huán)矩陣(如式 (4)(4) 所示)。

引入核函數(shù)

以上介紹的都是線性回歸的情況，如果能引入核函數(shù)，分類器的性能將會更好。核函數(shù)的引入是把特征空間映射到一個(gè)更高維的空間去，這里我們假設(shè)這個(gè)映射函數(shù)為 φ(x)φ(x) ，則分類器的權(quán)重向量變?yōu)?#xff0c;

w=∑iαiφ(x)(8)(8)w=∑iαiφ(x)

這樣我們最終要求解的參數(shù)就由 ww 變?yōu)?αα ，這里 α={α1,α2,...,αi,...}Tα={α1,α2,...,αi,...}T 。因?yàn)槠鋵?shí)我們并不知道核函數(shù)映射的高維空間是什么，我們只是知道高維空間下的兩個(gè)向量的乘積可以通過一個(gè)映射函數(shù)把其在低維空間下的乘積映射到高維空間，也就是核函數(shù)。這里設(shè)不同樣本之間的乘積的核函數(shù)結(jié)果組成的矩陣為

Kij=κ(xi,xj)(9)(9)Kij=κ(xi,xj)

這樣最終的回歸函數(shù)變?yōu)?#xff0c;

f(z)=wTz=∑i=1nαiκ(z,xi))(10)(10)f(z)=wTz=∑i=1nαiκ(z,xi))

直接計(jì)算上述函數(shù)相對來說是很耗時(shí)的，下面還是結(jié)合循環(huán)矩陣的特性實(shí)現(xiàn)一種快速的核函數(shù)計(jì)算方法。

快速訓(xùn)練

基于核函數(shù)下的嶺回歸的解為6，

α=(K+λI)?1y(11)(11)α=(K+λI)?1y

其中， KK 核函數(shù)矩陣，如式 (9)(9) 所示。如果我們能夠證明 KK 是循環(huán)矩陣，則上式的求解就可以轉(zhuǎn)換到DFT域，即，

α^?=y^k^xx+λ(12)(12)α^?=y^k^xx+λ

這里， kxxkxx 是核函數(shù)矩陣 KK 的第一行元素組成的向量。

如果兩個(gè)向量的元素的次序發(fā)生變化不影響最終通過核函數(shù)計(jì)算的結(jié)果，則該核函數(shù)構(gòu)成的矩陣就是一個(gè)循環(huán)矩陣，像高斯核函數(shù)，多項(xiàng)式核函數(shù)都是滿足上面條件的。

快速檢測

上面已經(jīng)提到直接計(jì)算式 (10)(10) 是非常耗時(shí)的，快速的解法是像式 (9)(9) 那樣，通過構(gòu)建測試樣本和訓(xùn)練樣本的核函數(shù)矩陣如下，

Kz=C(kxz)(13)(13)Kz=C(kxz)

其中， kxzkxz 是這個(gè)循環(huán)矩陣的第一行組成的向量。這樣就可以同時(shí)計(jì)算基于測試樣本 zz 的循環(huán)偏移構(gòu)成的所有測試樣本的響應(yīng)，即，

f(z)=(Kz)Tα(14)(14)f(z)=(Kz)Tα

注意這里 f(z)f(z) 不同于式 (10)(10) ，它是一個(gè)向量，由基于base樣本 zz 不同循環(huán)偏移下的響應(yīng)值組成。根據(jù)循環(huán)矩陣的性質(zhì)(如式 (5)(5) 所示)，上式變換到DFT域后，

f^(z)=(k^xz)?⊙α^(15)(15)f^(z)=(k^xz)?⊙α^

快速計(jì)算核函數(shù)相關(guān)性

到現(xiàn)在為止，只剩下前面部分提到的 kxxkxx 和 kxzkxz 沒有闡明如何計(jì)算了。首先列出 kxx^'kxx^' 的計(jì)算公式如下，

kxx′=g(C(x′)x)(16)(16)kxx′=g(C(x′)x)

其中， g(x)g(x) 是核函數(shù)， C(x′)C(x′) 是基于 x′x′ 為第一行的循環(huán)矩陣。參考式 (5)(5) 所示循環(huán)矩陣的特性，代入上式得，

kxx′=g(F?1(x^⊙x^?))(17)(17)kxx′=g(F?1(x^⊙x^?))

所以，對于多項(xiàng)式核函數(shù)，其計(jì)算公式如下，

kxx′=(F?1(x^⊙x^?)+a)b(18)(18)kxx′=(F?1(x^⊙x^?)+a)b

對于高斯核函數(shù)，其計(jì)算公式如下，

kxx′=exp(?1σ2(∥x∥2+∥x′∥2?2F?1(x^⊙x^?)))(19)(19)kxx′=exp(?1σ2(∥x∥2+∥x′∥2?2F?1(x^⊙x^?)))

總結(jié)

KCF的最大優(yōu)勢在于速度很快，但是每幀訓(xùn)練的權(quán)重向量更新問題并沒有很好的解決，目前算法采用的是按照一定比例更新最新的訓(xùn)練的權(quán)重向量到現(xiàn)有的權(quán)重向量中去。此外作者在其主頁上公布了Matlab源代碼，我根據(jù)其代碼也寫了一個(gè)C++版的，具體可以參考這里。

ReferencesY. Wu, J. Lim, and M.-H. Yang, "Online object tracking: A benchmark," in Computer vision and pattern recognition (CVPR), 2013 IEEE Conference on, 2013, pp. 2411-2418.

Z. Kalal, K. Mikolajczyk, and J. Matas, "Tracking-Learning-Detection," Pattern Analysis and Machine Intelligence, IEEE Transactions on,pp. 1-1, 2011.

S. Hare, A. Saffari, and P. H. S. Torr, "Struck: Structured Output Tracking with Kernels," 2011 IEEE International Conference on Computer Vision (ICCV),pp. 263-270, 2011.

J. F. Henriques, R. Caseiro, P. Martins, and J. Batista, "High-Speed Tracking with Kernelized Correlation Filters," IEEE Transactions on Pattern Analysis and Machine Intelligence,2014.

R. M. Gray, Toeplitz and circulant matrices: A review: now publishers inc, 2006.

R. Rifkin, G. Yeo, and T. Poggio, "Regularized least-squares classification," Nato Science Series Sub Series III Computer and Systems Sciences,vol. 190, pp. 131-154, 2003.

總結(jié)

以上是生活随笔為你收集整理的matlab求kcf算法响应图_Kernelized Correlation Filters(KCF)算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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