馬志勇，方 瓏

(上海第二工業(yè)大學(xué)理學(xué)院，上海201209)

矩陣特征值求解及其在圖像壓縮中的應(yīng)用

馬志勇，方 瓏

(上海第二工業(yè)大學(xué)理學(xué)院，上海201209)

在簡單闡述了矩陣特征值的數(shù)值求解理論之后，介紹了幾種常用的求解矩陣特征值的方法，并最終將特征值計(jì)算應(yīng)用到圖像壓縮中。

特征值數(shù)值算法；矩陣壓縮；圖像處理

0 引言

矩陣的特征值計(jì)算雖然有比較可靠的理論方法，但是，理論方法只適合于矩陣規(guī)模很小或者只是在理論證明中起作用，而實(shí)際問題的數(shù)據(jù)規(guī)模都比較大，不太可能采用常規(guī)的理論解法。計(jì)算機(jī)擅長處理大量的數(shù)值計(jì)算，所以通過適當(dāng)?shù)臄?shù)值計(jì)算理論[1-3]，寫成程序，讓計(jì)算機(jī)處理，是一種處理大規(guī)模矩陣的方法，而且是一種好的方法。常用的特征值數(shù)值方法包括冪法、反冪法、雅克比方法、QR分解法等。其中，冪法適用于求解矩陣絕對(duì)值最大的特征值，反冪法適合求解矩陣的逆矩陣的特征值，雅克比方法適合求解對(duì)稱矩陣的特征值，QR分解法主要使用于求中小型矩陣以及對(duì)稱矩陣的全部特征值。

矩陣乘以一個(gè)向量的結(jié)果仍是同維數(shù)的一個(gè)向量。因此，矩陣乘法對(duì)應(yīng)了一個(gè)變換，把一個(gè)向量變成同維數(shù)的另一個(gè)向量，變換的效果當(dāng)然與方陣的構(gòu)造有密切關(guān)系。比如，可以取適當(dāng)?shù)亩S方陣，使得這個(gè)變換的效果就是將平面上的二維向量逆時(shí)針旋轉(zhuǎn)30度，這時(shí)我們可以問一個(gè)問題，有沒有向量在這個(gè)變換下不改變方向呢？可以想一下，除了零向量，沒有其他向量可以在平面上旋轉(zhuǎn)30度而不改變方向，所以這個(gè)變換對(duì)應(yīng)的矩陣（或者說這個(gè)變換自身）沒有特征向量（注意：特征向量不能是零向量），所以一個(gè)特定的變換特征向量是這樣一種向量，它經(jīng)過這種特定的變換后保持方向不變，只是進(jìn)行長度上的伸縮而已。矩陣論在圖像中的應(yīng)用比如選取特征值最高的k個(gè)特征向量來表示一個(gè)矩陣，從而達(dá)到降維分析-特征顯示的方法。一般而言，這一方法的目的是將原始數(shù)據(jù)集合變換到主分量空間，使單一數(shù)據(jù)樣本的互相關(guān)性降低到最低點(diǎn)。圖像壓縮處理就是通過矩陣?yán)碚摐p少表示數(shù)字圖像時(shí)需要的數(shù)據(jù)量，從而達(dá)到有效壓縮。

1 特征值求解的數(shù)值方法

我們首先介紹幾種常用的求解特征值的數(shù)值方法。

（1）冪法。冪法就是求矩陣的絕對(duì)值最大的特征值和相應(yīng)特征向量的方法。

如果1λ是矩陣A的特征值，并且其絕對(duì)值比A的任何其他特征值的絕對(duì)值大，則稱它為主特征值。相應(yīng)于主特征值1λ的特征向量1V稱為主特征向量。如果特征向量V中絕對(duì)值最大的分量為1，則稱其是歸一化的。

注：如果0X是一個(gè)特征向量且0XV≠, 則必須選擇其他初始向量。

（2）反冪法。反冪法可以用來計(jì)算矩陣絕對(duì)值最小的特征值及其對(duì)應(yīng)的特征向量。

設(shè)A是n階非奇異矩陣，有n個(gè)線性無關(guān)的特征向量X1,X2,…,Xn, 它們對(duì)應(yīng)于特征值λ1, λ2,…,λn, 滿足不等式，其中AXi=λiXi( i=1,2,…,n)。因?yàn)锳非奇異，所以λi≠0, 由AXi=λiXi得A?1Xi=Xi/λi。

所以A?1的特征值是A的特征值的倒數(shù)。計(jì)算A的絕對(duì)值最小的特征值λn的問題就是計(jì)算A?1絕對(duì)值最大的特征值1/λn的問題，于是可用冪法求出A?1的絕對(duì)值最大的特征值，即A的絕對(duì)值最小的特征值。計(jì)算方法如下。

其中0V為初始向量。

（3）雅克比方法。雅克比方法的基本思想是通過一系列的由平面旋轉(zhuǎn)矩陣構(gòu)成的正交變換將實(shí)對(duì)稱矩陣逐步化為對(duì)角陣，從而得到全部特征值及其相應(yīng)的特征向量。

2 矩陣的特征值求解在圖像壓縮中的應(yīng)用

利用矩陣分解以及矩陣特征值的求解方法，可以將其應(yīng)用到很多方面[4-5]，例如矩陣壓縮、馬爾科夫過程、天氣預(yù)報(bào)等等，我們這里簡單介紹其在圖像壓縮方面的應(yīng)用。矩陣的壓縮是指利用矩陣的分解之后，提取特征值較大的特征值，舍棄比較小的特征值。還是因?yàn)樵诰仃嚴(yán)碚撝?，特征值代表了信息量，所以保留比較大的特征值、舍棄比較小的特征值，可以達(dá)到矩陣壓縮的目的。而圖像壓縮由于使用特征值分解壓縮圖片存在著不可靠性，所以采用一種新的矩陣分解方法來提取數(shù)字圖像的特征信息，那就是矩陣的奇異值分解。奇異值分解非常有用，對(duì)于矩陣Am×n, 存在Um×n, Vm×n, Sm×n, 滿足A=U×S×V 。U和V中分別是A的奇異向量，而S是A的奇異值。AA'的正交單位特征向量組成U，特征值組成S'S，A'A的正交單位特征向量組成V, 特征值（與AA'相同）組成SS'。因此，奇異值分解和特征值問題緊密聯(lián)系。

把獲得的奇異值，取其中比較大的（類同特征值的提取壓縮方法）奇異值，然后使用同樣的方法，進(jìn)行壓縮，其本質(zhì)其實(shí)還是使用類似矩陣分解，然后提取特征的方法，讓比較小的奇異值舍去，以達(dá)到數(shù)字圖像壓縮的目的。

使用普通相機(jī)拍攝的圖像A(見圖1)，大小為256×256。

圖1 使用普通相機(jī)拍攝的圖像AFig. 1 Using an ordinary camera, the image A

以下是不同壓縮比例的圖像。

提取500個(gè)奇異值后的壓縮圖像如圖2；提取300個(gè)奇異值后的壓縮圖像如圖3；提取100個(gè)奇異值后的壓縮圖像如圖4，圖像比較模糊，說明奇異值個(gè)數(shù)不可以取得過少。

圖2 提取500個(gè)奇異值后的壓縮圖像Fig. 2 The compressed image after extraction 500 singular value

圖3 提取300個(gè)奇異值后的壓縮圖像Fig. 3 The compressed image after extraction 300 singular value

圖4 提取100個(gè)奇異值后的壓縮圖像Fig. 4 The compressed image after extraction 100 singular value

3 圖像壓縮效果的評(píng)估

經(jīng)典的視頻壓縮算法已漸形成一系列的國際標(biāo)準(zhǔn)體系，如H.26x系列建議、H.320系列建議以及MPEG系列建議等。壓縮方法的質(zhì)量經(jīng)常使用峰值信噪比來衡量，峰值信噪比則用來表示圖像有損壓縮帶來的噪聲。但是，觀察者的主觀判斷也被認(rèn)為是一個(gè)重要的、或許是最重要的衡量標(biāo)準(zhǔn)。

特征值的應(yīng)用不僅僅在于圖像處理上，在物理、材料、力學(xué)等方面都有各種應(yīng)用。有人曾在書里這樣說過“有振動(dòng)的地方就有特征值和特征向量”，以后我們將進(jìn)一步探討矩陣?yán)碚摷捌湎嚓P(guān)應(yīng)用。

4 圖像壓縮的相關(guān)步驟

clear,clc

infile='C:psu4.jpg';

A=imread(infile); % 讀取圖像

A(:,:,1)

imshow(A);xlabel('原始圖像');

A=double(A); % 數(shù)據(jù)格式轉(zhuǎn)換

A(:,:,1);

[U1 S1 V1]=svd(A(:,:,1));

[U2 S2 V2]=svd(A(:,:,2));

[U3 S3 V3]=svd(A(:,:,3));

U1*S1*V1';

A(:,:,1)-U1(:,1:500)*S1(1:500,1:500)*V1(:,1:500)';

W(:,:,1)=U1(:,1:500)*S1(1:500,1:500)*V1(:,1:500)';

W(:,:,2)=U2(:,1:500)*S2(1:500,1:500)*V2(:,1:500)';

W(:,:,3)=U3(:,1:500)*S3(1:500,1:500)*V3(:,1:500)';

imshow(uint8(W))

pause

A(:,:,1)-U1(:,1:300)*S1(1:300,1:300)*V1(:,1:300)';

W(:,:,1)=U1(:,1:300)*S1(1:300,1:300)*V1(:,1:300)';

W(:,:,2)=U2(:,1:300)*S2(1:300,1:300)*V2(:,1:300)';

W(:,:,3)=U3(:,1:300)*S3(1:300,1:300)*V3(:,1:300)';

imshow(uint8(W))

pause

A(:,:,1)-U1(:,1:10)*S1(1:10,1:10)*V1(:,1:10)';

W(:,:,1)=U1(:,1:10)*S1(1:10,1:10)*V1(:,1:10)';

W(:,:,2)=U2(:,1:10)*S2(1:10,1:10)*V2(:,1:10)';

W(:,:,3)=U3(:,1:10)*S3(1:10,1:10)*V3(:,1:10)';

imshow(uint8(W))

[1] MATHEWS J H, FINK K D, 著. 周璐, 陳渝, 錢方, 等譯. 數(shù)值方法(MATLAB版)[M]. 第四版. 北京: 電子工業(yè)出版社, 2005.

[2] 林成森. 數(shù)值分析[M]. 北京: 科學(xué)出版社, 2006.

[3] 奚梅成, 劉儒勛. 數(shù)值分析方法[M]. 合肥: 中國科學(xué)技術(shù)大學(xué)出版社, 2003.

[4] 張汗靈. Matlab在圖像處理中的應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2008.

[5] 張賢達(dá). 矩陣分析與應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2004.

Matrix Eigenvalue and Its Application in Image Compression

MA Zhi-yong, FANG Long
( School of Science, Shanghai Second Polytechnic University, Shanghai 201209, P. R. China )

The theory of the numerical solution of the matrix decomposition and eigenvalue was briefly discussed. And then, several special matrix eigenvalue solution methods was introducted which was commonly used. Finally, image compression reached a new height of matrix decomposition and application of the corresponding eigenvalue.

eigenvalue numerical algorithms; matrix compression; image compression

O29

A

1001-4543(2012)04-0315-04

2012-09-15;

2012-10-09

馬志勇（1980－），男，河南人，講師，博士，主要研究方向?yàn)槠⒎址匠碳捌鋭?dòng)力系統(tǒng)，電子郵箱zyma@sf.sspu.cn。

校重點(diǎn)課程高等代數(shù)基金項(xiàng)目（No. A20KC110002）