四階張量分解在視頻壓縮領(lǐng)域的應(yīng)用

徐嬌嬌， 楊志霞， 姚 瑞

(1. 昌吉學院 數(shù)學系， 新疆 昌吉 831100； 2. 新疆大學 數(shù)學與系統(tǒng)科學學院，新疆 烏魯木齊 830046；3.新疆師范大學 數(shù)學科學學院， 新疆 烏魯木齊 830000)

0 引言

以四階張量為主要展現(xiàn)形式的數(shù)據(jù)廣泛存在于各種實際問題中，例如不同患者在不同藥物劑量下的EGG數(shù)據(jù)、各種視頻數(shù)據(jù)、單鏡頭的人臉識別問題等.尤其視頻數(shù)據(jù)作為四階張量的表現(xiàn)形式，引起了廣大學者的注意，如視頻壓縮[1]、視頻恢復[2]、視頻分類[3]等.數(shù)字圖像壓縮技術(shù)在多媒體、通信、醫(yī)學等諸多領(lǐng)域有著廣泛的應(yīng)用.我們知道，奇異值分解(SVD)[4]和非負矩陣分解[5]在圖像壓縮理論中非常重要.與灰度圖像相比，彩色圖像和視頻具有更多的信息和識別特征，對彩色圖像和視頻進行處理，具有廣泛的潛在應(yīng)用.目前存在很多數(shù)據(jù)描述方法[6]，使用向量或矩陣存儲彩色圖像和視頻數(shù)據(jù)信息、壓縮或處理數(shù)據(jù)時，不僅占用了大量的存儲容量，而且破壞了數(shù)據(jù)的原始結(jié)構(gòu)信息.因此，彩色圖像和視頻被表示為多維數(shù)組，多維數(shù)組通常稱為高階張量.以高階張量的形式保存彩色圖像，可更多保護數(shù)據(jù)的原始結(jié)構(gòu).因此，使用張量存儲更復雜的數(shù)據(jù)也更加合理.

事實上，張量可以看作是矩陣的推廣，關(guān)于張量的研究方向有很多，如張量逼近[7-9]、張量完備[10-13]、張量特征值問題[14-15]、支持張量機[16]以及張量分解等問題.特別是張量分解問題廣受關(guān)注.現(xiàn)有的張量分解包括Tucker分解[17-18]、高階奇異值分解(HOSVD)[19]、CANDECOMP/PARAFAC(CP)分解[20]、張量稀疏分解[21]等.Tucker分解通常表示為向量的外積之和，它也可以表述為張量模乘[22].特別地，高階奇異值分解具有與Tucker分解相同的結(jié)構(gòu)形式，可以看作是矩陣奇異值分解的拓展.類似于Tucker分解，CP分解被定義為向量的外積之和.另一個重要的分解是對稱張量的低秩分解[23].此外，文獻[24]還構(gòu)建了一個新穎的多線性張量空間.具體地，不僅給出了任意多維離散變換，而且給出了矩陣空間上的四階張量雙線性算子；還定義了四階張量的L-奇異值分解和張量L-QR分解.它們都具有精度高、收斂速度快、計算量小的特點.值得注意的是，Kilmer等[25]和Golub等[26]通過塊循環(huán)矩陣和展開算子定義了兩個三階張量之間的乘法運算.在此基礎(chǔ)上，對塊循環(huán)矩陣進行離散傅里葉變換(DFT)，得到T-奇異值分解.由于矩陣可視為張量，因此矩陣的T-奇異值分解與矩陣奇異值分解一致.可見該三階張量的分解算法不僅具有很好的稀疏性，而且具有很好的保結(jié)構(gòu)性.因此，將其推廣到四階張量是一個亟待解決的問題.

另一方面，彩色視頻可視為四階張量，其維數(shù)高于三階張量.因此，研究四階張量的分解具有重要意義.為了節(jié)省計算資源和保持數(shù)據(jù)結(jié)構(gòu)，可以通過截斷的方法在保持原數(shù)據(jù)特征不變的前提下，壓縮四階張量的數(shù)據(jù)量.然而，由于維度增加，四階張量的數(shù)據(jù)結(jié)構(gòu)比三階張量更復雜.此外，四階張量的研究相對少于三階張量，包括乘法和分解.我們探索了一種新的四階張量分解以及截斷的四階壓縮算法.

本文主要研究四階張量分解在視頻壓縮領(lǐng)域的應(yīng)用.首先，研究了塊循環(huán)三階張量和離散傅里葉變換，定義了四階張量之間的乘法.基于以上定義，提出了一個新的四階張量分解及其算法.具體地，原始的四階張量被分解為兩個T-正交張量和一個對角張量的乘法.經(jīng)過適當?shù)慕財?，壓縮了原始四階張量的存儲量.通過數(shù)值實驗表明了本文提出的四階張量分解算法的有效性和可行性.

本文安排如下：第一節(jié)，描述了一些符號，并回顧了一些張量背景知識；第二節(jié)，定義了兩個四階張量的乘法，并基于塊循環(huán)三階張量的離散傅里葉變換提出了四階張量分解；第三節(jié)，分別通過隨機數(shù)據(jù)和真實照片數(shù)據(jù)進行數(shù)值實驗，驗證了本文提出的張量分解和視頻壓縮算法的有效性；最后，總結(jié)了本文的主要結(jié)論.

1 符號和張量背景

在本文中，我們用大寫手寫體字母表示張量(例如：X)，用大寫字母表示矩陣(例如：A)，而黑體小寫字母和小寫字母分別表示向量和標量.

一個N階張量是具有N個向量空間的張量積空間中的一個元素，即一個N維數(shù)組

X=(xi1,i2,…,in)∈Rd1×d2×…×dN，

其中“×”表示笛卡爾積，dn表示張量X第n維的大小.特別地，向量是一階張量，矩陣是二階張量.當一個張量的階數(shù)不小于3時，稱其為高階張量，若N=3，則X稱為3階張量，若N=4，則X稱為4階張量.

下面，先介紹循環(huán)矩陣的定義.給定向量v=(v0v1v2v3)T∈R4，稱矩陣

若三階張量中的每一個前后矩陣片由循環(huán)矩陣代替，可得三階張量的塊循環(huán)矩陣，下面以1-模展開塊循環(huán)矩陣為例，具體定義如下：

定義1.1(循環(huán)三階張量)形式為

的三階張量C，稱為循環(huán)三階張量，其中ci為循環(huán)矩陣中的一個元素.

為了方便后文引入四階張量的離散傅里葉變換，這里首先給出兩個與三階張量相關(guān)的定義.

定義1.2(Face-wise乘積[27])設(shè)三階張量X∈Rd1×d2×d3， Y∈Rd2×m×d3.那么X和Y的Face-wise乘積定義為

X*Y=

(X(1)Y(1)|X(2)Y(2)|…|X(d3)Y(d3))，

其中X(i)和Y(i)(i=1,2,…,d3)分別表示X和Y的前后矩陣片.

定義1.3(Kronecker積)設(shè)矩陣X∈RI1×I2，張量Y∈RJ1×J2×J3，則X和Y的Kronecker積定義為

X?Y=(Yj1,j2,j3?X)，?jm∈Jm，m=1,2,3,

其中

X?Y∈R(I1J1)×(I2J2)×J3.

顯然，當三階張量降階為二階張量(矩陣)，張量的Kronecker積即為矩陣的Kronecker積.

2 四階張量乘法及其分解

本節(jié)，我們首先提出四階張量的1-模展開和折疊算子.接下來，給出塊循環(huán)的三階張量與其相應(yīng)的離散傅里葉變換.隨后，定義兩個四階張量間的乘法和一些特殊的四階張量乘法.最后，建立一種新的四階張量分解方法，并提出相應(yīng)的算法.

2.1 四階張量算子

本小節(jié)，依次介紹四階張量的Frobenious范數(shù)、1-模展開算子以及1-模折疊算子的定義.為了敘述方便，本文主要討論四階實張量.若向量空間V1、V2、V3、V4的維數(shù)分別是d1、d2、d3、d4，則張量積空間V1°V2°V3°V4中任意一個四階張量X表示為

其中

v1i°v2j°v3k°v4k(1≤i≤d1,1≤j≤d2,

1≤k≤d3,1≤l≤d4)

是張量積空間V1°V2°V3°V4的一組基.對于四階張量X=[|xi,j,k,l|]∈Rd1×d2×d3×d4，其Frobenious-范數(shù)定義為

對于張量X∈Rd1×d2×d3×d4，X的1-模展開算子為

(·)〈1〉∶Rd1×d2×d3×d4→R(d1d4)×d2×d3

X→X〈1〉.

折疊算子記作(·)〈1〉，定義為

(·)〈1〉∶R(d1d4)×d2×d3→Rd1×d2×d3×d4

X〈1〉→X.

類似地，也可以定義n-模(n=2,3,4)展開及其折疊算子.

利用上述描述，我們得到下面的定義．

定義2.1(四階張量的1-模展開)給定四階張量X={xi,j,k,l}∈Rd1×d2×d3×d4，若按照X的1-模的方向排列其每一個子三階張量，則得到X的1-模展開三階張量

其中X(1)=X(:,:,:,l)∈Rd1×d2×d3(l=1,2,…,d4) 是第l個1-模展開子三階張量.類似地，也可以定義n-模(n=2,3,4)展開和折疊算子.

2.2 塊循環(huán)三階張量和離散傅里葉變換

有了上述循環(huán)三階張量的定義，下面我們給出塊循環(huán)三階張量的定義.

定義2.2(四階張量的塊循環(huán)三階張量)對于四階張量X∈Rd1×d2×d3×d4，X(j)(j=1,2,…,d4) 是張量X的1-模展開三階張量X〈1〉的第j個三階子張量，把形式為

∈Rd1d4×d2d4×d3d4

的三階張量稱為四階張量X的塊循環(huán)三階張量，記為Circ(X).

下面，以四階張量X∈Rd1×d2×d3×3為例，給出其塊循環(huán)三階張量(見圖1).

圖1 四階張量X∈Rd1×d2×d3×3的塊循環(huán)三階張量

換個角度，Circ(X)可以看作d4個維數(shù)為d1d4×d2d4×d3的塊三階張量的排列.進一步，通過張量的3-模展開，塊循環(huán)三階張量Circ(X)的每一個三階子張量都可轉(zhuǎn)化為矩陣.也就是將維數(shù)為d1d4×d2d4×d3d4的塊循環(huán)張量Circ(X)轉(zhuǎn)化為一個維數(shù)d1d4×d2d3d4×d4的三階張量，記作TenMat(X)，即

我們知道，利用離散傅里葉變換，循環(huán)矩陣能夠被對角化.類似地，下面給出塊循環(huán)三階張量的塊對角化過程.給定四階張量X∈Rd1×d2×d3×d4離散傅里葉矩陣Fd1∈Rd1×d1，則有

其中Jd4∈Rd4×d4×d4為對角線元素全為1的三階張量，*表示兩個三階張量的Face-wise乘.值得注意的是，每個矩陣Dl∈Rd1×d2d3(l=1,2,…,d4) 應(yīng)該是稠密的.相反地，通過離散傅里葉逆變換，TenMat(X)能夠被計算出來，即

特別地，上述兩個過程分別記作fft{TenMat(X)}和ifft{TenMat(X)}.

2.3 張量乘法

在本小節(jié)，我們給出四階張量的乘法，這也是本文的主要貢獻之一.下面，主要給出一個新的四階張量乘法的相關(guān)定義和張量模乘的定義.此外，還定義了一些特殊的四階張量.

定義2.3(B-乘)對于四階張量X∈Rd1×d2×d3×d4和Y∈Rn1×n2×n3×n4，且d2d3=n1n4，四階張量的B-乘為

X*BY=(X〈1〉〈3〉Y〈1〉〈3〉)〈1〉〈3〉∈Rd1×n2×n3×d4，

其中X〈1〉〈3〉是X〈1〉的3-模展開矩陣，·〈1〉〈3〉是折疊算子.

容易看出，四階張量的B-乘基于展開矩陣X〈1〉〈3〉和Y〈1〉〈3〉之間的乘法.下面，給出張量B-乘與張量模乘之間的關(guān)系.

命題1對于張量B-乘，矩陣A∈Rn1×n2能夠視為一個四階張量，且n3=n4=1.此時，定義2.3退化為矩陣乘法.進一步，設(shè)四階張量X∈Rd1×d2×d3×d4，矩陣A∈Rn1×n2且d2d3=n1,則

X*BA=X〈3〉×2AT∈Rd1×n2×d4，

其中×n表示張量和矩陣之間的n-模乘法.

證明已知四階張量X的3-模展開張量為X〈3〉，其第k個前后片為d1×d2d3的矩陣X(k)(k=1,2,…,d4).由張量的B-乘的定義知，張量X與矩陣A的B-乘，即為三階張量X〈3〉的每個前后片與矩陣A=(amn)n1×n2相乘.

具體如下：

進一步，有

另一方面

因此，通過2-模乘法的定義，命題1成立.

現(xiàn)在，提出幾個具體的四階張量相關(guān)的定義.基于四階張量B-乘，給出四階Tb-正交張量的定義.

下面，將給出Tb-正交張量、單位張量以及張量的Tb-轉(zhuǎn)置的定義.

定義2.5(單位張量)若四階張量J∈Rd1×d1×d3×d4的第i(i=1,2,…,d4)個子三階張量的第i個前后片是一個d1×d1的單位矩陣,則稱F為四階單位張量.

定義2.6(Tb轉(zhuǎn)置)設(shè)四階張量X∈Rd1×d2×d3×d4，其Tb轉(zhuǎn)置定義為

XTb=((X〈1〉〈3〉)T)〈1〉〈3〉∈Rd2×d1×d4×d3，

其中，X〈1〉〈3〉∈Rd2d3×d1d4表示X的展開矩陣.

有了四階單位張量和張量的Tb轉(zhuǎn)置的定義，下面給出四階Tb-正交張量的定義.

定義2.7(Tb-正交張量)四階張量Q∈Rd1×d2×d3×d4稱作Tb-正交張量，如果

Q*BQTb=J，

其中J∈Rd1×d1×d4×d4是單位張量.

注釋1：我們知道正交矩陣和三階正交張量都能確保Frobenius范數(shù)不變性.本文定義的Tb-正交張量也具有保范性，也就是說，如果Q∈Rd1×d2×d3×d4是Tb-正交張量，且X∈Rn1×n2×n3×n4滿足d2d3=n1n4，則 ‖Q*BX‖F(xiàn)=‖X*BQ‖F(xiàn)=‖X‖F(xiàn).

2.4 四階張量分解

本小節(jié)，基于四階張量B-乘，我們提出一個新的四階張量分解方法.當四階張量退化為矩陣時, 該分解即為矩陣的奇異值分解.同時本小節(jié)也給出對應(yīng)的算法.

定理1(B-TD)設(shè)四階張量X∈Rd1×d2×d3×d4，X的奇異值分解為

X=U*BS*BVTb，

其中U∈Rd1×d1×d4×d4，V∈Rd2×d2×d3×d3是Tb-正交張量， S∈Rd1×d2×d3×d4是對角張量.四階張量的奇異值分解簡記為B-TD.

證明首先，對TenMat(X)做離散傅里葉變換.也就是說，存在兩個傅里葉矩陣Fd1∈Rd1×d1和Fd2d3∈Rd2d3×d2d3使得

其中Di∈Rd1×d2d3，i=1,2,…,d4.

接下來，將上式中所有的稠密矩陣排列成一個三階張量，即

D=(D1|D2|…|Dd4)∈Rd1×d2d3×d4.

也就是說

令

且i,j=1,2,…,d4，有

其中k=1,2,…,d4.進而有

因此，有

這意味著X=U*BS*BVTb.顯然， U、V均是Tb-正交張量,且S是對角張量.

注釋2：值得一提的是，對于四階張量X∈Rd1×d2×d3×d4，當d3=d4=1時，分解式X=U*BS*BVTb退化為矩陣的奇異值分解.此時，U和V是正交矩陣，S是對角矩陣.

為了獲得四階張量X∈Rd1×d2×d3×d4的奇異值分解，根據(jù)定理1的證明過程可總結(jié)出如下算法：

算法1四階張量分解(B-TD)

輸入：X∈Rd1×d2×d3×d4

輸出：U，S，V

bodydiag(D1,D2,…,Dd4)=fft(TenMat(X))

D=(D1|D2|…|Dd4)

3 數(shù)值實驗

本節(jié)，通過兩個數(shù)值試驗來驗證本文提出的四階張量的奇異值分解算法(B-TD)的可行性.第一部分數(shù)值算例，將本文四階張量的奇異值算法應(yīng)用在一個人造數(shù)據(jù)中，驗證了本文提出的算法不僅是可行的，同時也具有較高的計算精度.第二部分數(shù)值算例是針對實際的視頻數(shù)據(jù)，執(zhí)行了本文所提的算法，通過不同的壓縮比對視頻數(shù)據(jù)進行不同的壓縮效果，從而表明了本文所提算法的實用性.

3.1 人造數(shù)據(jù)

算例1本例中，X是由Matlab隨機產(chǎn)生的維數(shù)為3×3×3×3的四階張量，下面通過三個三階子張量拼接的形式，將四階張量X中展示如下：

X=(X(1)|X(2)|X(3))∈R3×3×3×3.

這里具體給出三個三階子張量.

通過我們的B-TD算法，得到張量S=(S(1)|S(2)|S(3))，其三階子張量分別為

顯然S是對角張量.類似地，同樣能夠計算出Tb正交張量U和V，這里不再一一列舉.除此之外，我們也能計算原始張量X與分解后的張量之間的誤差，即

‖X-U*BS*BVTb‖F(xiàn)=3.9146e-14.

上述誤差表明，B-TD算法具有較高的誤差精度，也表明了方法的可行性.

3.2 圖像壓縮應(yīng)用

我們知道，實際的計算機視頻處理問題中，關(guān)鍵技術(shù)是海量數(shù)據(jù)的表示和傳輸.因此，如何有效地存儲和傳輸視頻數(shù)據(jù)成為信息社會迫切需要解決的問題.視頻數(shù)據(jù)壓縮的原理是將稠密的視頻數(shù)據(jù)轉(zhuǎn)換成具有相同特征的稀疏數(shù)據(jù).

實際數(shù)據(jù)中的彩色圖片是三階張量，無聲的視頻是以時間為第四個維度的四階張量.為了清晰地顯示數(shù)據(jù)壓縮的結(jié)果，我們將本章提出的新的四階張量分解理論應(yīng)用于視頻數(shù)據(jù).具體地，將B-TD方法應(yīng)用在圖像壓縮問題上.考慮到這些照片的質(zhì)量隨曝光時間、光線和視點的不同而變化.因此，首先考慮將已有的圖像數(shù)據(jù)做歸一化處理.具體做法如下：

Pl(l=1,2,…,d4)是一個d1×d2×d3維的三階張量.Pl是由d3個d1×d2的矩陣片構(gòu)成，其中每個矩陣片表示第l個人的一張人臉圖像.做歸一化處理，即每個Pl減去其均值.把處理過后的張量記作X(:,:,:,l)，即X(:,:,:,l)=Pl-Ψ，其中

算法2視頻壓縮算法(TDVC)

輸入：實驗數(shù)據(jù)Pl(l=1,2,…,d4)，截斷參數(shù)M，N，L，P

對圖像做歸一化處理，Ψ；

forl=1,2,…,d4X(:,:,:,l)=Pl-Ψ；

End

下面給出用來衡量壓縮效果的視頻壓縮率的計算方法.X∈Rd1×d2×d3×d4表示原始的視頻壓縮數(shù)據(jù).可以看出X具有d1d2d3d4個像素.利用算法2對X進行截斷，截斷后的數(shù)據(jù)像素為d1MPd4+NL+Nd2d3L.數(shù)據(jù)壓縮率定義為截斷前的像素值與截斷后的像素值的比值，即

顯然，大的壓縮比可以大大節(jié)省數(shù)據(jù)的存儲空間.此外，圖像的視覺效果也是很重要的.基于此，下面給出一個基于不同視頻壓縮比的例子.

a原始圖像 b M=40,N=30 c M=20,N=20 d M=10,N=10 ρ=4.2637 ρ=7.5641 ρ=15.1282圖2 原始圖像與對應(yīng)于不同的截斷參數(shù)和壓縮比的重構(gòu)圖像對比

a原始圖像 b M=100,N=100 c M=40,N=20 d M=10,N=10 ρ=5.1404 ρ=14.9938 ρ=51.4041圖3 原始圖像與對應(yīng)于不同的截斷參數(shù)和壓縮比的重構(gòu)圖像對比

通過原始圖像與選擇不同的截斷參數(shù)M，N，L，P得到后面三列不同的重構(gòu)圖像.可以發(fā)現(xiàn)，L和P的值并不影響壓縮后照片的清晰度，故上述過程取L=P=1.該方法不僅可以壓縮數(shù)據(jù)的存儲量，而且保留了原始數(shù)據(jù)的主要特征.由此表明本文的分解方法不僅可節(jié)省計算時間，而且減少圖像的存儲空間.

算例3本例中，我們從AbsFreepic網(wǎng)站下載了三張彩色照片.每張彩色照片大小為Pl∈R300×400×3(l=1,2,3)，利用算法2TDVC分解四階張量P∈R300×400×3×3，效果如圖3所示.

圖3中，最左側(cè)第1列為原始圖像，其他三列是在不同的壓縮比下，由算法2 TDVC壓縮后的圖像.同樣地，設(shè)L=P=1，不難看出重構(gòu)的圖像同樣保存了原始數(shù)據(jù)的主要特征，且N和M的值越大，重構(gòu)的圖片的清晰度越高.

4 總結(jié)

本文提出了一個新的四階張量乘法和四階張量奇異值分解算法(B-TD)，該方法具有很好的稀疏性和保范性.我們將所提算法應(yīng)用到視頻壓縮領(lǐng)域，通過選取不同的截斷參數(shù)，計算視頻數(shù)據(jù)的壓縮比，以成組的黑白照片、彩色照片構(gòu)造成四階張量進行分解.壓縮后的視頻數(shù)據(jù)表明，不同的壓縮比會得到清晰度不同的視覺效果. 數(shù)值實驗?zāi)芎芎玫卣f明本文提出的四階張量分解方法的可行性.在后期的研究工作中，我們將繼續(xù)以高階張量分解為研究課題，進一步探討更多的應(yīng)用領(lǐng)域.