在學習KCF目標跟蹤算法時，會用到一個數(shù)學概念：循環(huán)矩陣，其對KCF的速度提升起到了非常關(guān)鍵的作用，值得了解下。

1. 傅里葉矩陣(DFT Matrix)

　在了解循環(huán)矩陣的定義前，需要先了解下離散傅里葉矩陣：

2. 循環(huán)矩陣定義

形狀如下的矩陣(X)稱為循環(huán)矩陣，(x)為循環(huán)矩陣(X)的生成向量，為矩陣第一行, 其他行都是(x)向右循環(huán)位移得到。

[X=C(x) = egin{bmatrix}
x_1 &x_2 &x_3 &x_4\
x_4 &x_1 &x_2 &x_3\
x_3 &x_4 &x_1 &x_2\
x_2 &x_3 &x_4 &x_1\
end{bmatrix}
]

通過(x)生成(X), 可以由排列矩陣和(x)相乘，連續(xù)平移(x)得到，示例代碼如下：

import numpy as np
x = np.array(
    [[1, 2, 3, 4]]
)
P = np.array(
    [[0, 0, 0, 1],
     [1, 0, 0, 0],
     [0, 1, 0, 0],
     [0, 0, 1, 0]]
)
X = np.zeros((4, 4))
X[0, :] = x
for i in range(1, 4):
    X[i, :] = np.dot(P, X[i-1, :]).T  # 排列矩陣P每作用一次x，x向右移動一位
print(X)

輸出：
[[1. 2. 3. 4.]
 [4. 1. 2. 3.]
 [3. 4. 1. 2.]
 [2. 3. 4. 1.]]

3. 循環(huán)矩陣性質(zhì)

循環(huán)矩陣很多優(yōu)秀的性質(zhì)，其中最重要的幾個性質(zhì)為如下：

1. 任意循環(huán)矩陣可以被傅里葉變換矩陣對角化

一般用如下方式表達這一概念：

[X=C(x)=Fcdot diag(widehat{x})cdot F^{H}
]

其中(X)是一個循環(huán)矩陣，(x)是(X)的生成向量, (hat x)（讀作x hat）為原向量(x)的傅里葉變換；(F)是傅里葉變換矩陣，(F^H)表示共軛轉(zhuǎn)置: (F^H=(F^*)^T)。換句話說，(X)相似于對角陣，(X)的特征值是(hat x) 的元素。
另一方面，如果一個矩陣能夠表示成兩個傅里葉矩陣夾一個對角陣的乘積形式，則它是一個循環(huán)矩陣。其生成向量是對角元素的傅里葉逆變換：

[Fcdot diag({y})cdot F^{H} = C(mathcal{F}^{-1}(y)) ，（mathcal{F}^{-1}(y)表示y的傅里葉逆變換）
]

2. 循環(huán)矩陣乘向量等價于生成向量的逆序和該向量卷積

數(shù)學表示如下：

[mathcal{F}(Xy) = mathcal{F}(C(x)y) = mathcal{F}(ar x*y) = mathcal{F}^*(x)odotmathcal{F}(y)
]

這里(ar x)表示(x)的逆序排列，?表示卷積。

注意：卷積本身也包含逆序操作。此外，這里最后一個等號利用了信號與系統(tǒng)中的“時域卷積，頻域相乘”，即時域卷積定理，它表明兩信號在時域的卷積積分對應(yīng)于在頻域中該兩信號的傅里葉變換的乘積。

3. 循環(huán)矩陣的乘積仍是循環(huán)矩陣，可以以較低的復雜度計算循環(huán)矩陣的乘積

數(shù)學表示如下：

[X^HX = Fcdot diag(widehat{x}odotwidehat{x}^*)cdot F^{H}=C(mathcal{F}^{-1}(widehat{x}odotwidehat{x}^*))
]

公式中最終所得的乘積也是循環(huán)矩陣，其生成向量是原生成向量對位相乘的傅里葉逆變換。

以K表示的是矩陣的尺寸，可以發(fā)現(xiàn)計算速度提升非常明顯， KCF主要就是利用了這條性質(zhì)：

原始計算量：兩個方陣相乘(O(K^3))

轉(zhuǎn)化后的計算量：反向傅里葉(O(Klog(K)))+向量點乘（(K)）

在非線形的情況下，當引入了核之后，也可以得到同樣的一個情況。此時需要這個核滿足一定的條件，它是可以具備循環(huán)矩陣的一些性質(zhì)的，例如常用的高斯核、線性核都滿足這個條件，因此可以直接拿來用。

4. KCF中的循環(huán)矩陣

關(guān)于KCF的理論推導有很多文章描述了，請參考：

https://blog.csdn.net/shenxiaolu1984/article/details/50905283

https://blog.csdn.net/weixin_38128100/article/details/95729653

https://zhuanlan.zhihu.com/p/48249974

https://gsy00517.github.io/computer-vision20200120120823/

4.1核矩陣K是循環(huán)矩陣

在上述KCF的理論推導中有一個前提：即下面表達式中的核矩陣K是循環(huán)矩陣

[優(yōu)化函數(shù)最優(yōu)解：alpha=(phi(X)^Tphi(X)+lambda I)^{-1}y=(K+lambda I)^{-1}y
]

這個前提條件是怎么來的呢？滿足什么條件時K是循環(huán)矩陣呢？

K為核矩陣，其形式如下：（若(X)為nxm的矩陣，表示有n條數(shù)據(jù)，每一條數(shù)據(jù)的維度為m, 那么對應(yīng)的核矩陣為nxn的矩陣，每一個元素表示兩條數(shù)據(jù)的內(nèi)積）

[核矩陣K = egin{bmatrix} k(x_1,x_1) & k(x_1,x_2) & dots & k(x_1,x_n) \
k(x_2,x_1) & k(x_2,x_2) & dots & k(x_2,x_n) \ vdots &vdots & &vdots\
k(x_n,x_1) & k(x_n,x_2) & dots & k(x_n,x_n) end{bmatrix}=egin{bmatrix} phi(x_1)phi(x_1) & phi(x_1)phi(x_2) & dots & phi(x_1)phi(x_n) \
phi(x_2)phi(x_1) & phi(x_2)phi(x_2) & dots & phi(x_2)phi(x_n) \ vdots &vdots & &vdots\
phi(x_n)phi(x_1) & phi(x_n)phi(x_2) & dots & phi(x_n)phi(x_n) end{bmatrix} = phi(X)phi(X)^T
]

K為循環(huán)矩陣的條件就是X為循環(huán)矩陣，通過循環(huán)矩陣的幾條性質(zhì)可以得到：

循環(huán)矩陣的轉(zhuǎn)置是循環(huán)矩陣: 若(X)是循環(huán)矩陣，(X^T)也是循環(huán)矩陣
循環(huán)矩陣乘以循環(huán)矩陣，還是循環(huán)矩陣:(X)和 (X^T)都是循環(huán)矩陣，則(XX^T)也是循環(huán)矩陣
相比于(XX^T)，(phi(X)phi(X)^T)多了一層核函數(shù)，但對于滿足一定條件的核函數(shù)，高斯核，多項式核，對應(yīng)的矩陣仍然是循環(huán)矩陣

我們可以舉個例子驗證下，測試代碼和結(jié)果如下：

def GaussianKernel(X, Y, gamma=1.0):
    n = X.shape[0]
    ret = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            ret[i,j] = np.sum(np.power((X[i, :] - Y[:, j].T), 2))
    ret = np.exp(ret/(-2*gamma*gamma))
    return ret
    
def recycle_matrix():
    X = np.array(
        [[1, 2, 3, 4],
         [4, 1, 2, 3],
         [3, 4, 1, 2],
         [2, 3, 4, 1]]
    )
    print("*********X*********")
    print(X)

    print("*********X^TX*********")
    print(np.dot(X, X.T))

    print("*********K*********")
    K = GaussianKernel(X, X.T)
    print(K)

    # 調(diào)用sklearn中的高斯核函數(shù)
    # from sklearn.gaussian_process.kernels import RBF
    # kernel = RBF()
    # K = kernel(X, X.T)
    # print(K)
if __name__ == "__main__":
    recycle_matrix()

4.2 樣本X是循環(huán)矩陣

上面已經(jīng)得到：樣本(X)是循環(huán)矩陣，則核矩陣(K)是循環(huán)矩陣的。那么(X)怎樣才能成為循環(huán)矩陣呢？論文中描述如下：

一維樣本構(gòu)成循環(huán)矩陣

論文中，作者先用一維樣本舉例，如下圖所示，循環(huán)矩陣的生成向量(base sample)是一個一維的向量(1*m)，這個向量向右循環(huán)移動n-1次，生成n-1個向量，所有向量組成一個nxm的循環(huán)矩陣

二維樣本構(gòu)成循環(huán)矩陣

論文接下來以二維樣本為例，如下圖所示，循環(huán)矩陣的生成向量是一張二維圖片(假設(shè)為m*m)，每移動一次就會生成一個mxm的矩陣，所有這些mxm的矩陣最后拼接起來組成一個大的循環(huán)矩陣，下面是其移動示例過程：

這里是一個循環(huán)圖片的示例，使用base sample，若我們向下移動15個像素，也就是從下面剪切15個像素拼到上面，就會變成左二圖，若移動30個就可以生成左一圖，右側(cè)的圖片是上移生成的。這就是在做tracking時循環(huán)采樣的樣本，一般會在目標周圍取一個比目標更大的一個框，然后對大框框取的圖像區(qū)域進行循環(huán)采樣，那么就會生成這樣一些新的樣本來模擬我們的正樣本并用于訓練

參考：https://blog.csdn.net/shenxiaolu1984/article/details/50884830

總結(jié)

以上是生活随笔為你收集整理的KCF中的循环矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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