卷積視角下循環矩陣對角化證明新方法及其應用

唐毅鋆,陳穎頻,陳 惠,喬嘉琪,陳振雕,李一凡

(1.漳州職業技術學院電子信息學院,福建 漳州 363000;2.閩南師范大學物理與信息工程學院,福建 漳州 363000)

0 引言

在圖像處理和計算機視覺的眾多應用中廣泛存在具有列循環結構或行循環結構的循環矩陣,例如圖像處理中的差分矩陣[1-2]和相關跟蹤濾波中由基向量循環移位得到的預測樣本矩陣[3-8]。由于循環矩陣在空間上存在明顯的循環移位關系,其信息存在冗余性,因此若直接在空域上處理循環結構矩陣會導致產生較高的計算復雜度。為解決這一問題,學者們將傅里葉變換引入循環矩陣,并將大型的矩陣相乘和求逆運算轉換為向量的點乘與點除運算,其核心原理就是循環矩陣的對角化性質。然而,傳統的循環矩陣對角化性質的證明較難理解和掌握,為此,本文從卷積視角提出一種全新的列循環矩陣對角化證明方法,進而證明行循環矩陣的對角化性質。

1 預備知識

1.1 傳統的列循環矩陣對角化證明方法

循環矩陣對角化問題描述如下:

(1)

根據復數信號的周期不變性,

ekj2π/N=ekj2π/N·e-2πkj=e-kj2π(N-1)/N.

(2)

同理,

ekj2π(N-1)/N=ekj2π(N-1)/N·e-2πkj=e-kj2π/N.

(3)

因此,

(4)

g(1,k)=x1+x0ekj(N-1)2π/N+…+x2ekj2π/N=ejk2π/Ng(0,k).

(5)

則

(6)

故有

(7)

1.2 離散信號卷積定義

z=x*y∈N×1,

(8)

1.3 列循環矩陣的一個性質

將列循環矩陣C(x)乘以一個信號y,根據1.2節中介紹的離散卷積定義,則有

(9)

2 卷積視角下列循環矩陣對角化證明

2.1 列循環矩陣對角化性質證明

根據式(9),在兩邊乘以離散傅里葉變換矩陣FN,則有

FNC(x)y=FN(x*y).

(10)

首先分析式(10)右邊,根據卷積定理,空域卷積信號的頻譜將等于兩個信號頻譜的點乘[10-11],即

(11)

然后分析式(10)左邊,將C(x)y看作C(x)INy,其中,IN∈N×N表示單位矩陣,可被拆分為則有

(12)

由于式(10)成立,必有

(13)

2.2 列循環矩陣對角化性質驗證

本節提供代碼1對列循環矩陣對角化性質加以驗證,代碼如下:

%代碼1

clear all;

N=4;

DFT=zeros(N,N);

n=[0:N-1]; k=[0:N-1];

Wn=exp(-j*2*pi/N);

nk=n’*k;

DFT=Wn.^nk;

C=[-1 1 0 0; 0 -1 1 0; 0 0 -1 1; 1 0 0 -1];

x=[-1,0,0,1].’;

X=fft(x);

D=DFT*C*inv(DFT);

for i=1∶N

Y(i)=D(i,i);

end

Y-X.’

經Matlab運行,代碼1運行結果約等于0。該結果表明,運用卷積定理進行列循環矩陣對角化與通過傳統數學方法計算的誤差極小,可見式(7)成立。

3 行循環矩陣對角化性質證明

3.1 利用列循環矩陣對角化性質證明行循環矩陣對角化性質

證明 因(7)式恒成立,對該式兩邊同時轉置,則有

(14)

(15)

(16)

(17)

3.2 行循環矩陣對角化性質的編程驗證

本節提供代碼2對行循環矩陣對角化性質加以驗證,代碼如下:

%代碼2

N=8;

DFT=zeros(N,N);

n=[0∶N-1];

k=[0∶N-1];

Wn=exp(-j*2*pi/N);

nk=n’*k;

DFT=Wn.^nk;

Fn=DFT./sqrt(N);

C=[0 7 6 5 4 3 2 1;

1 0 7 6 5 4 3 2;

2 1 0 7 6 5 4 3;

3 2 1 0 7 6 5 4;

4 3 2 1 0 7 6 5;

5 4 3 2 1 0 7 6;

6 5 4 3 2 1 0 7;

7 6 5 4 3 2 1 0];

D=inv(Fn)*C*(Fn);

for i=1∶N

y(i)=D(i,i);

end

x=[0 7 6 5 4 3 2 1];

FTx=fft(x);

y-FTx

以上代碼中,C以(0, 7, 6, 5, 4, 3, 2, 1)作為第一行,經循環移位擴展得到行循環結構矩陣。代碼2運行結果趨近于0,該結果表明,運用卷積定理進行行循環矩陣對角化與通過傳統數學方法計算的誤差極小,可驗證式(17)成立。

3.3 行循環矩陣在視頻目標跟蹤中的應用

在相關濾波跟蹤算法中,常將二維目標面片X∈h×w拉成行向量xT∈1×N(N=h×w),并循環移位擴展為行循環矩陣,以此建模目標在空間中移動的各種可能性,如圖1所示。

(a)循環移位得到的預測樣本1

(b) 基樣本

(c)循環移位得到的預測樣本2

然后以嶺回歸的機器學習建模方法訓練濾波器w∈N×1,使得濾波器回歸的響應盡可能接近預先定義的教師信號N×1(該信號為二維高斯窗函數的拉列信號),如式(18)所示。

(18)

目標函數在空域上對濾波器w進行求導:

(19)

則w的空域最優解為

(20)

若樣本尺寸較大,在空域上直接求解濾波器w的復雜度很高。行循環矩陣的對角化性質則可較好地解決這一問題。

將式(20)中的C(xT)對角化:

根據卷積定理可將式(21)轉換到頻域中計算,則有

(22)

其中,real表示取復數的實部。

圖2展示了利用式(20)和(22)設計濾波器得到的響應圖,從圖2可以看出,兩種算法效果上完全等效。通過上述方法可將濾波器利用快速傅里葉變換加以計算,運算效率會有顯著提高。

(a)利用式(20)設計濾波器得到的響應圖

(b)利用式(22)設計濾波器得到的響應圖

本節提供代碼3以反映式(20)與(22)計算效率上的差別。代碼如下:

%代碼3

clc

clear all;

N=4096;

X1=[1∶1∶sqrt(N)];

X2=[1∶1∶sqrt(N)];

[X,Y]=meshgrid(X1,X2);

y=exp(-((X-sqrt(N)/2).*(X-sqrt(N)/2)+(Y-sqrt(N)/2).*(Y-sqrt(N)/2))/10);

C=zeros(N,N);

x=linspace(1,N,N);

C(1,:)=x.’;

for i=1∶N-1

C(i+1,:)=circshift(x,i).’;

end

tic

w=inv(C.’*C+0.1)*C.’*y(:);

toc

r1=C*w;

figure(1)

R1=reshape(r1,sqrt(N),sqrt(N));

imagesc(R1);

colorbar;

tic

w2=real(ifft(fft(x.’).*fft(y(:))./(fft(x.’).*conj(fft(x.’))+0.1)));

toc

r2=C*w2;

figure(2)

R2=reshape(r2,sqrt(N),sqrt(N));

imagesc(R2);

colorbar;

r1-r2

通過改變代碼3中N的數值,對比兩種算法的運行時間,如表1所示。

表1 式(20)與式(22)的耗時對比

從表1可以看出,當N值較大時,以式(22)計算濾波器的運算耗時遠遠低于以式(20)計算濾波器的運算耗時。這是因為式(20)涉及大型矩陣C(xT)∈N×N的相乘運算和求逆運算,其復雜度高達(N3),而式(22)中用到的快速傅里葉變換和快速逆傅里葉變換復雜度僅為(Nlog2N),且向量的點乘運算復雜度僅為(N2),故式(22)復雜度為(N2+2Nlog2N)。因此,利用循環矩陣對角化將濾波器轉換為頻域求解的效率較高。

4 結語

循環矩陣對角化性質廣泛應用于各類圖像處理和計算機視覺領域。然而,傳統的循環矩陣對角化證明方法往往晦澀難懂,需要用到大量數學技巧。為解決這一問題,本文從列循環矩陣的性質C(x)y=x*y出發,結合離散卷積定義和卷積定理,從卷積視角巧妙證明了列循環矩陣的對角化性質,避免傳統證明方法中涉及的復雜運算,證明思路易于理解,最后通過行循環矩陣與列循環矩陣的轉置關系進一步討論行循環矩陣的對角化性質,并給出一組實驗以反映行循環矩陣對角化性質在視頻目標跟蹤中的重要應用。