徐嬌嬌, 楊志霞, 姚 瑞
(1. 昌吉學(xué)院 數(shù)學(xué)系, 新疆 昌吉 831100; 2. 新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,新疆 烏魯木齊 830046;3.新疆師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 新疆 烏魯木齊 830000)
以四階張量為主要展現(xiàn)形式的數(shù)據(jù)廣泛存在于各種實(shí)際問(wèn)題中,例如不同患者在不同藥物劑量下的EGG數(shù)據(jù)、各種視頻數(shù)據(jù)、單鏡頭的人臉識(shí)別問(wèn)題等.尤其視頻數(shù)據(jù)作為四階張量的表現(xiàn)形式,引起了廣大學(xué)者的注意,如視頻壓縮[1]、視頻恢復(fù)[2]、視頻分類[3]等.數(shù)字圖像壓縮技術(shù)在多媒體、通信、醫(yī)學(xué)等諸多領(lǐng)域有著廣泛的應(yīng)用.我們知道,奇異值分解(SVD)[4]和非負(fù)矩陣分解[5]在圖像壓縮理論中非常重要.與灰度圖像相比,彩色圖像和視頻具有更多的信息和識(shí)別特征,對(duì)彩色圖像和視頻進(jìn)行處理,具有廣泛的潛在應(yīng)用.目前存在很多數(shù)據(jù)描述方法[6],使用向量或矩陣存儲(chǔ)彩色圖像和視頻數(shù)據(jù)信息、壓縮或處理數(shù)據(jù)時(shí),不僅占用了大量的存儲(chǔ)容量,而且破壞了數(shù)據(jù)的原始結(jié)構(gòu)信息.因此,彩色圖像和視頻被表示為多維數(shù)組,多維數(shù)組通常稱為高階張量.以高階張量的形式保存彩色圖像,可更多保護(hù)數(shù)據(jù)的原始結(jié)構(gòu).因此,使用張量存儲(chǔ)更復(fù)雜的數(shù)據(jù)也更加合理.
事實(shí)上,張量可以看作是矩陣的推廣,關(guān)于張量的研究方向有很多,如張量逼近[7-9]、張量完備[10-13]、張量特征值問(wèn)題[14-15]、支持張量機(jī)[16]以及張量分解等問(wèn)題.特別是張量分解問(wèn)題廣受關(guān)注.現(xiàn)有的張量分解包括Tucker分解[17-18]、高階奇異值分解(HOSVD)[19]、CANDECOMP/PARAFAC(CP)分解[20]、張量稀疏分解[21]等.Tucker分解通常表示為向量的外積之和,它也可以表述為張量模乘[22].特別地,高階奇異值分解具有與Tucker分解相同的結(jié)構(gòu)形式,可以看作是矩陣奇異值分解的拓展.類似于Tucker分解,CP分解被定義為向量的外積之和.另一個(gè)重要的分解是對(duì)稱張量的低秩分解[23].此外,文獻(xiàn)[24]還構(gòu)建了一個(gè)新穎的多線性張量空間.具體地,不僅給出了任意多維離散變換,而且給出了矩陣空間上的四階張量雙線性算子;還定義了四階張量的L-奇異值分解和張量L-QR分解.它們都具有精度高、收斂速度快、計(jì)算量小的特點(diǎn).值得注意的是,Kilmer等[25]和Golub等[26]通過(guò)塊循環(huán)矩陣和展開(kāi)算子定義了兩個(gè)三階張量之間的乘法運(yùn)算.在此基礎(chǔ)上,對(duì)塊循環(huán)矩陣進(jìn)行離散傅里葉變換(DFT),得到T-奇異值分解.由于矩陣可視為張量,因此矩陣的T-奇異值分解與矩陣奇異值分解一致.可見(jiàn)該三階張量的分解算法不僅具有很好的稀疏性,而且具有很好的保結(jié)構(gòu)性.因此,將其推廣到四階張量是一個(gè)亟待解決的問(wèn)題.
另一方面,彩色視頻可視為四階張量,其維數(shù)高于三階張量.因此,研究四階張量的分解具有重要意義.為了節(jié)省計(jì)算資源和保持?jǐn)?shù)據(jù)結(jié)構(gòu),可以通過(guò)截?cái)嗟姆椒ㄔ诒3衷瓟?shù)據(jù)特征不變的前提下,壓縮四階張量的數(shù)據(jù)量.然而,由于維度增加,四階張量的數(shù)據(jù)結(jié)構(gòu)比三階張量更復(fù)雜.此外,四階張量的研究相對(duì)少于三階張量,包括乘法和分解.我們探索了一種新的四階張量分解以及截?cái)嗟乃碾A壓縮算法.
本文主要研究四階張量分解在視頻壓縮領(lǐng)域的應(yīng)用.首先,研究了塊循環(huán)三階張量和離散傅里葉變換,定義了四階張量之間的乘法.基于以上定義,提出了一個(gè)新的四階張量分解及其算法.具體地,原始的四階張量被分解為兩個(gè)T-正交張量和一個(gè)對(duì)角張量的乘法.經(jīng)過(guò)適當(dāng)?shù)慕財(cái)?,壓縮了原始四階張量的存儲(chǔ)量.通過(guò)數(shù)值實(shí)驗(yàn)表明了本文提出的四階張量分解算法的有效性和可行性.
本文安排如下:第一節(jié),描述了一些符號(hào),并回顧了一些張量背景知識(shí);第二節(jié),定義了兩個(gè)四階張量的乘法,并基于塊循環(huán)三階張量的離散傅里葉變換提出了四階張量分解;第三節(jié),分別通過(guò)隨機(jī)數(shù)據(jù)和真實(shí)照片數(shù)據(jù)進(jìn)行數(shù)值實(shí)驗(yàn),驗(yàn)證了本文提出的張量分解和視頻壓縮算法的有效性;最后,總結(jié)了本文的主要結(jié)論.
在本文中,我們用大寫手寫體字母表示張量(例如:X),用大寫字母表示矩陣(例如:A),而黑體小寫字母和小寫字母分別表示向量和標(biāo)量.
一個(gè)N階張量是具有N個(gè)向量空間的張量積空間中的一個(gè)元素,即一個(gè)N維數(shù)組
X=(xi1,i2,…,in)∈Rd1×d2×…×dN,
其中“×”表示笛卡爾積,dn表示張量X第n維的大小.特別地,向量是一階張量,矩陣是二階張量.當(dāng)一個(gè)張量的階數(shù)不小于3時(shí),稱其為高階張量,若N=3,則X稱為3階張量,若N=4,則X稱為4階張量.
下面,先介紹循環(huán)矩陣的定義.給定向量v=(v0v1v2v3)T∈R4,稱矩陣
若三階張量中的每一個(gè)前后矩陣片由循環(huán)矩陣代替,可得三階張量的塊循環(huán)矩陣,下面以1-模展開(kāi)塊循環(huán)矩陣為例,具體定義如下:
定義1.1(循環(huán)三階張量)形式為
的三階張量C,稱為循環(huán)三階張量,其中ci為循環(huán)矩陣中的一個(gè)元素.
為了方便后文引入四階張量的離散傅里葉變換,這里首先給出兩個(gè)與三階張量相關(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.
顯然,當(dāng)三階張量降階為二階張量(矩陣),張量的Kronecker積即為矩陣的Kronecker積.
本節(jié),我們首先提出四階張量的1-模展開(kāi)和折疊算子.接下來(lái),給出塊循環(huán)的三階張量與其相應(yīng)的離散傅里葉變換.隨后,定義兩個(gè)四階張量間的乘法和一些特殊的四階張量乘法.最后,建立一種新的四階張量分解方法,并提出相應(yīng)的算法.
本小節(jié),依次介紹四階張量的Frobenious范數(shù)、1-模展開(kāi)算子以及1-模折疊算子的定義.為了敘述方便,本文主要討論四階實(shí)張量.若向量空間V1、V2、V3、V4的維數(shù)分別是d1、d2、d3、d4,則張量積空間V1°V2°V3°V4中任意一個(gè)四階張量X表示為
其中
v1i°v2j°v3k°v4k(1≤i≤d1,1≤j≤d2,
1≤k≤d3,1≤l≤d4)
是張量積空間V1°V2°V3°V4的一組基.對(duì)于四階張量X=[|xi,j,k,l|]∈Rd1×d2×d3×d4,其Frobenious-范數(shù)定義為
對(duì)于張量X∈Rd1×d2×d3×d4,X的1-模展開(kāi)算子為
(·)〈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)展開(kāi)及其折疊算子.
利用上述描述,我們得到下面的定義.
定義2.1(四階張量的1-模展開(kāi))給定四階張量X={xi,j,k,l}∈Rd1×d2×d3×d4,若按照X的1-模的方向排列其每一個(gè)子三階張量,則得到X的1-模展開(kāi)三階張量
其中X(1)=X(:,:,:,l)∈Rd1×d2×d3(l=1,2,…,d4) 是第l個(gè)1-模展開(kāi)子三階張量.類似地,也可以定義n-模(n=2,3,4)展開(kāi)和折疊算子.
有了上述循環(huán)三階張量的定義,下面我們給出塊循環(huán)三階張量的定義.
定義2.2(四階張量的塊循環(huán)三階張量)對(duì)于四階張量X∈Rd1×d2×d3×d4,X(j)(j=1,2,…,d4) 是張量X的1-模展開(kāi)三階張量X〈1〉的第j個(gè)三階子張量,把形式為
∈Rd1d4×d2d4×d3d4
的三階張量稱為四階張量X的塊循環(huán)三階張量,記為Circ(X).
下面,以四階張量X∈Rd1×d2×d3×3為例,給出其塊循環(huán)三階張量(見(jiàn)圖1).
圖1 四階張量X∈Rd1×d2×d3×3的塊循環(huán)三階張量
換個(gè)角度,Circ(X)可以看作d4個(gè)維數(shù)為d1d4×d2d4×d3的塊三階張量的排列.進(jìn)一步,通過(guò)張量的3-模展開(kāi),塊循環(huán)三階張量Circ(X)的每一個(gè)三階子張量都可轉(zhuǎn)化為矩陣.也就是將維數(shù)為d1d4×d2d4×d3d4的塊循環(huán)張量Circ(X)轉(zhuǎn)化為一個(gè)維數(shù)d1d4×d2d3d4×d4的三階張量,記作TenMat(X),即
我們知道,利用離散傅里葉變換,循環(huán)矩陣能夠被對(duì)角化.類似地,下面給出塊循環(huán)三階張量的塊對(duì)角化過(guò)程.給定四階張量X∈Rd1×d2×d3×d4離散傅里葉矩陣Fd1∈Rd1×d1,則有
其中Jd4∈Rd4×d4×d4為對(duì)角線元素全為1的三階張量,*表示兩個(gè)三階張量的Face-wise乘.值得注意的是,每個(gè)矩陣Dl∈Rd1×d2d3(l=1,2,…,d4) 應(yīng)該是稠密的.相反地,通過(guò)離散傅里葉逆變換,TenMat(X)能夠被計(jì)算出來(lái),即
特別地,上述兩個(gè)過(guò)程分別記作fft{TenMat(X)}和ifft{TenMat(X)}.
在本小節(jié),我們給出四階張量的乘法,這也是本文的主要貢獻(xiàn)之一.下面,主要給出一個(gè)新的四階張量乘法的相關(guān)定義和張量模乘的定義.此外,還定義了一些特殊的四階張量.
定義2.3(B-乘)對(duì)于四階張量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-模展開(kāi)矩陣,·〈1〉〈3〉是折疊算子.
容易看出,四階張量的B-乘基于展開(kāi)矩陣X〈1〉〈3〉和Y〈1〉〈3〉之間的乘法.下面,給出張量B-乘與張量模乘之間的關(guān)系.
命題1對(duì)于張量B-乘,矩陣A∈Rn1×n2能夠視為一個(gè)四階張量,且n3=n4=1.此時(shí),定義2.3退化為矩陣乘法.進(jìn)一步,設(shè)四階張量X∈Rd1×d2×d3×d4,矩陣A∈Rn1×n2且d2d3=n1,則
X*BA=X〈3〉×2AT∈Rd1×n2×d4,
其中×n表示張量和矩陣之間的n-模乘法.
證明已知四階張量X的3-模展開(kāi)張量為X〈3〉,其第k個(gè)前后片為d1×d2d3的矩陣X(k)(k=1,2,…,d4).由張量的B-乘的定義知,張量X與矩陣A的B-乘,即為三階張量X〈3〉的每個(gè)前后片與矩陣A=(amn)n1×n2相乘.
具體如下:
進(jìn)一步,有
另一方面
因此,通過(guò)2-模乘法的定義,命題1成立.
現(xiàn)在,提出幾個(gè)具體的四階張量相關(guān)的定義.基于四階張量B-乘,給出四階Tb-正交張量的定義.
下面,將給出Tb-正交張量、單位張量以及張量的Tb-轉(zhuǎn)置的定義.
定義2.5(單位張量)若四階張量J∈Rd1×d1×d3×d4的第i(i=1,2,…,d4)個(gè)子三階張量的第i個(gè)前后片是一個(gè)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的展開(kāi)矩陣.
有了四階單位張量和張量的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-正交張量也具有保范性,也就是說(shuō),如果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).
本小節(jié),基于四階張量B-乘,我們提出一個(gè)新的四階張量分解方法.當(dāng)四階張量退化為矩陣時(shí), 該分解即為矩陣的奇異值分解.同時(shí)本小節(jié)也給出對(duì)應(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是對(duì)角張量.四階張量的奇異值分解簡(jiǎn)記為B-TD.
證明首先,對(duì)TenMat(X)做離散傅里葉變換.也就是說(shuō),存在兩個(gè)傅里葉矩陣Fd1∈Rd1×d1和Fd2d3∈Rd2d3×d2d3使得
其中Di∈Rd1×d2d3,i=1,2,…,d4.
接下來(lái),將上式中所有的稠密矩陣排列成一個(gè)三階張量,即
D=(D1|D2|…|Dd4)∈Rd1×d2d3×d4.
也就是說(shuō)
令
且i,j=1,2,…,d4,有
其中k=1,2,…,d4.進(jìn)而有
因此,有
這意味著X=U*BS*BVTb.顯然, U、V均是Tb-正交張量,且S是對(duì)角張量.
注釋2:值得一提的是,對(duì)于四階張量X∈Rd1×d2×d3×d4,當(dāng)d3=d4=1時(shí),分解式X=U*BS*BVTb退化為矩陣的奇異值分解.此時(shí),U和V是正交矩陣,S是對(duì)角矩陣.
為了獲得四階張量X∈Rd1×d2×d3×d4的奇異值分解,根據(jù)定理1的證明過(guò)程可總結(jié)出如下算法:
算法1四階張量分解(B-TD)
輸入:X∈Rd1×d2×d3×d4
輸出:U,S,V
bodydiag(D1,D2,…,Dd4)=fft(TenMat(X))
D=(D1|D2|…|Dd4)
本節(jié),通過(guò)兩個(gè)數(shù)值試驗(yàn)來(lái)驗(yàn)證本文提出的四階張量的奇異值分解算法(B-TD)的可行性.第一部分?jǐn)?shù)值算例,將本文四階張量的奇異值算法應(yīng)用在一個(gè)人造數(shù)據(jù)中,驗(yàn)證了本文提出的算法不僅是可行的,同時(shí)也具有較高的計(jì)算精度.第二部分?jǐn)?shù)值算例是針對(duì)實(shí)際的視頻數(shù)據(jù),執(zhí)行了本文所提的算法,通過(guò)不同的壓縮比對(duì)視頻數(shù)據(jù)進(jìn)行不同的壓縮效果,從而表明了本文所提算法的實(shí)用性.
算例1本例中,X是由Matlab隨機(jī)產(chǎn)生的維數(shù)為3×3×3×3的四階張量,下面通過(guò)三個(gè)三階子張量拼接的形式,將四階張量X中展示如下:
X=(X(1)|X(2)|X(3))∈R3×3×3×3.
這里具體給出三個(gè)三階子張量.
通過(guò)我們的B-TD算法,得到張量S=(S(1)|S(2)|S(3)),其三階子張量分別為
顯然S是對(duì)角張量.類似地,同樣能夠計(jì)算出Tb正交張量U和V,這里不再一一列舉.除此之外,我們也能計(jì)算原始張量X與分解后的張量之間的誤差,即
‖X-U*BS*BVTb‖F(xiàn)=3.9146e-14.
上述誤差表明,B-TD算法具有較高的誤差精度,也表明了方法的可行性.
我們知道,實(shí)際的計(jì)算機(jī)視頻處理問(wèn)題中,關(guān)鍵技術(shù)是海量數(shù)據(jù)的表示和傳輸.因此,如何有效地存儲(chǔ)和傳輸視頻數(shù)據(jù)成為信息社會(huì)迫切需要解決的問(wèn)題.視頻數(shù)據(jù)壓縮的原理是將稠密的視頻數(shù)據(jù)轉(zhuǎn)換成具有相同特征的稀疏數(shù)據(jù).
實(shí)際數(shù)據(jù)中的彩色圖片是三階張量,無(wú)聲的視頻是以時(shí)間為第四個(gè)維度的四階張量.為了清晰地顯示數(shù)據(jù)壓縮的結(jié)果,我們將本章提出的新的四階張量分解理論應(yīng)用于視頻數(shù)據(jù).具體地,將B-TD方法應(yīng)用在圖像壓縮問(wèn)題上.考慮到這些照片的質(zhì)量隨曝光時(shí)間、光線和視點(diǎn)的不同而變化.因此,首先考慮將已有的圖像數(shù)據(jù)做歸一化處理.具體做法如下:
Pl(l=1,2,…,d4)是一個(gè)d1×d2×d3維的三階張量.Pl是由d3個(gè)d1×d2的矩陣片構(gòu)成,其中每個(gè)矩陣片表示第l個(gè)人的一張人臉圖像.做歸一化處理,即每個(gè)Pl減去其均值.把處理過(guò)后的張量記作X(:,:,:,l),即X(:,:,:,l)=Pl-Ψ,其中
算法2視頻壓縮算法(TDVC)
輸入:實(shí)驗(yàn)數(shù)據(jù)Pl(l=1,2,…,d4),截?cái)鄥?shù)M,N,L,P
對(duì)圖像做歸一化處理,Ψ;
forl=1,2,…,d4X(:,:,:,l)=Pl-Ψ;
End
下面給出用來(lái)衡量壓縮效果的視頻壓縮率的計(jì)算方法.X∈Rd1×d2×d3×d4表示原始的視頻壓縮數(shù)據(jù).可以看出X具有d1d2d3d4個(gè)像素.利用算法2對(duì)X進(jìn)行截?cái)啵財(cái)嗪蟮臄?shù)據(jù)像素為d1MPd4+NL+Nd2d3L.數(shù)據(jù)壓縮率定義為截?cái)嗲暗南袼刂蹬c截?cái)嗪蟮南袼刂档谋戎?,?/p>
顯然,大的壓縮比可以大大節(jié)省數(shù)據(jù)的存儲(chǔ)空間.此外,圖像的視覺(jué)效果也是很重要的.基于此,下面給出一個(gè)基于不同視頻壓縮比的例子.
a原始圖像 b M=40,N=30 c M=20,N=20 d M=10,N=10 ρ=4.2637 ρ=7.5641 ρ=15.1282圖2 原始圖像與對(duì)應(yīng)于不同的截?cái)鄥?shù)和壓縮比的重構(gòu)圖像對(duì)比
a原始圖像 b M=100,N=100 c M=40,N=20 d M=10,N=10 ρ=5.1404 ρ=14.9938 ρ=51.4041圖3 原始圖像與對(duì)應(yīng)于不同的截?cái)鄥?shù)和壓縮比的重構(gòu)圖像對(duì)比
通過(guò)原始圖像與選擇不同的截?cái)鄥?shù)M,N,L,P得到后面三列不同的重構(gòu)圖像.可以發(fā)現(xiàn),L和P的值并不影響壓縮后照片的清晰度,故上述過(guò)程取L=P=1.該方法不僅可以壓縮數(shù)據(jù)的存儲(chǔ)量,而且保留了原始數(shù)據(jù)的主要特征.由此表明本文的分解方法不僅可節(jié)省計(jì)算時(shí)間,而且減少圖像的存儲(chǔ)空間.
算例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)的圖片的清晰度越高.
本文提出了一個(gè)新的四階張量乘法和四階張量奇異值分解算法(B-TD),該方法具有很好的稀疏性和保范性.我們將所提算法應(yīng)用到視頻壓縮領(lǐng)域,通過(guò)選取不同的截?cái)鄥?shù),計(jì)算視頻數(shù)據(jù)的壓縮比,以成組的黑白照片、彩色照片構(gòu)造成四階張量進(jìn)行分解.壓縮后的視頻數(shù)據(jù)表明,不同的壓縮比會(huì)得到清晰度不同的視覺(jué)效果. 數(shù)值實(shí)驗(yàn)?zāi)芎芎玫卣f(shuō)明本文提出的四階張量分解方法的可行性.在后期的研究工作中,我們將繼續(xù)以高階張量分解為研究課題,進(jìn)一步探討更多的應(yīng)用領(lǐng)域.