鄧子云

(長沙商貿(mào)旅游職業(yè)技術學院 經(jīng)濟貿(mào)易學院,長沙 410116)

圖像壓縮是計算機學科學術界和工程界關注的熱門研究領域之一[1,2].目前已有很多成熟的壓縮算法,也產(chǎn)生了各種圖像壓縮格式,如JPG、GIF 等[3].還有一些通用的文件壓縮算法,進而產(chǎn)生了各種文件壓縮格式,如ZIP、RAR 等[4].奇異值分解方法是線性代數(shù)數(shù)學學科中一種數(shù)據(jù)壓縮方法,可以將大規(guī)模的矩陣在分解為矩陣的乘法表示后,用一定比例的特征數(shù)據(jù)矩陣來表示原來的大規(guī)模矩陣,從而達到壓縮的目的.奇異值分解方法可以運用到圖像壓縮領域,并起到良好的壓縮效果.

已有一些學者、工程技術人員將奇異值分解方法運用到特定的圖像壓縮應用上,如視頻監(jiān)控圖像、遙感圖像等[5,6].還有的研究人員結合奇異值分解方法和其它的算法來提升圖像的壓縮比[7],絕大多數(shù)研究工作采用的是Matlab 開發(fā)工具[8,9].考慮到圖像壓縮算法多已成熟,本文并不打算提出新的算法,而是深入研究基于奇異值分解的技術原理,提出2 種運用奇異值分解作圖像壓縮的方法,用Python 編程實現(xiàn)并展開實驗,再對JPG、PNG 這2 種通用的圖像格式作出壓縮效果的示例和對比分析.

1 奇異值分解的原理

奇異值分解可以針對任意形態(tài)的矩陣作特征值分解.現(xiàn)實應用場景中的數(shù)據(jù)確實不太可能都是方陣,而多是行數(shù)、列數(shù)不等的數(shù)據(jù)矩陣,因此,奇異值分解具有廣泛的應用價值[10].

奇異值分解的通用形式如式(1)所示[11–13]:

式(1)中的Um×m被稱為左奇異向量組成的標準正交基矩陣,Dm×n被 稱為特征值對角矩陣,被稱為右奇異向量組成的標準正交基矩陣.不論是m＞n,還是m≤n,式(1)都會成立.式(1)可用更為形象的圖形來表述,如圖1(a)和圖1(b)所示[14].

2 用奇異值分解壓縮圖像的原理

根據(jù)式(1),如果將r個特征值從大到小排序,并調動對應的Um×m和中的向量位置,可以得到數(shù)據(jù)矩陣A的奇異值分解排序后的結果,這個分解結果即可用于壓縮數(shù)據(jù)矩陣A.

2.1 如何壓縮矩陣數(shù)據(jù)

具體壓縮方法是取前k個特征值,及矩陣Um×m和矩陣中的前k個向量,可得到:

以圖1(a)為例,這種數(shù)據(jù)壓縮的思想示意如圖2所示.

圖1 奇異值分解的圖示

圖2 數(shù)據(jù)壓縮的思想圖示

這種數(shù)據(jù)壓縮的思想體現(xiàn)的就是用數(shù)據(jù)的主要成份來代表整體數(shù)據(jù),從而實現(xiàn)只要存儲較少的數(shù)據(jù),可見這其實是一種有損數(shù)據(jù)壓縮,因此需要將數(shù)據(jù)的壓縮控制在可以接受的范圍[15].

2.2 壓縮比的計算

經(jīng)過如圖2所示的變換后,數(shù)據(jù)矩陣A的近似矩陣的行數(shù)和列數(shù)并沒有變,那又怎么是節(jié)約空間了呢?

這是因為奇異值分解后,不必再存儲數(shù)據(jù)矩陣A,而是存儲矩陣Um×m的前k列、矩陣Dm×n中的前k個特征值,矩陣的前k行,通過式(2)計算再得到數(shù)據(jù)矩陣A的近似矩陣.這樣,要存儲的數(shù)據(jù)遠比存儲數(shù)據(jù)矩陣A要使用的存儲空間少得多.

以一個1000×2000 的數(shù)據(jù)矩陣為例,則要存儲2 000 000 個數(shù)據(jù),假定每個數(shù)據(jù)占用的存儲空間數(shù)量相同.假定運用奇異值分解共需使用50 個特征值來作數(shù)據(jù)壓縮,存儲矩陣Um×m的前50 列需存儲1000×50=50 000個 數(shù)據(jù),存儲矩陣的前k行需存儲2000×50=100 000個 數(shù)據(jù),則總計需要存儲50 000+100 000+50=150 050個數(shù)據(jù),這遠比存儲2 000 000 個數(shù)據(jù)要節(jié)約存儲空間.

衡量這種節(jié)約的程度可用壓縮比來表示,按式(3)所示的公式計算:

式(3)中,P表示壓縮比,S原表示原始數(shù)據(jù)占用的存儲空間,S壓表示壓縮后的數(shù)據(jù)占用的存儲空間.因此在上述例子中:

2.3 k 取值的2 種方法

k取值應為多少合適呢?那得看對數(shù)據(jù)壓縮的目標需求了,k越大,數(shù)據(jù)就壓縮得越少,需要的存儲空間也越多,需要找到一個合適的平衡點.有2 種方法:

(1)按特征值個數(shù)占比閾值取特征值個數(shù).設定一個比例閾值f,如果k與特征值總個數(shù)之比的值超過閾值f,則取前k個特征值.

(2)按特征值之和占比閾值取特征值個數(shù).設定一個比例閾值f,如果前k個特征值之和與所有特征值之和的比的值超過閾值f,則取前k個特征值.

2.4 圖像壓縮的原理

以常用的PNG 和JPG 格式的圖像為例,讀取它們的圖像數(shù)據(jù)可得到一個3 維的數(shù)據(jù)矩陣.第1 維表示的橫向的像素,第2 維表示縱向的像素,第3 維表示圖像的通道,用0～255 范圍的數(shù)據(jù)表示數(shù)據(jù)值.

PNG 和JPG 兩種格式不同的是,PNG 格式圖像的第3 維有4 個通道,分別表示R (Red,紅色)、G (Green,綠色)、B (Blue,藍色)、A (Alpha,透明度);而JPG 格式圖像只有R、G、B 這3 個通道,沒有A 這個通道[16].這也是JPG 格式圖像比PNG 格式圖像占用空間更小的根本原因.此外,兩種格式對數(shù)據(jù)均有壓縮的算法.這里不討論并忽略兩種格式本身的數(shù)據(jù)壓縮算法.

在分離得到PNG 格式圖像的R、G、B、A 這4 個通道的數(shù)據(jù)矩陣后,可對這4 個2 維數(shù)據(jù)矩陣分別作奇異值分解,再根據(jù)使用的k取值的方法和閾值f,可得到這4 個數(shù)據(jù)矩陣的前k個特征值、Um×k和.JPG 格式圖像則不需要對A 通道的數(shù)據(jù)矩陣作奇異值分解.

要查看壓縮后的PNG 格式圖像,則可將4 個通道的前k個特征值、Um×k和根據(jù)式(2)分別計算得到近似的數(shù)據(jù)矩陣,組合這4 個2 維數(shù)據(jù)矩陣形成PNG格式圖像的3 維數(shù)據(jù),即可顯示圖像.JPG 格式圖像則計算并組合R、G、B 這3 個通道的壓縮后數(shù)據(jù)得到圖像的3 維數(shù)據(jù).

3 圖像壓縮應用示例

這里以一張原圖的PNG、JPG 2 種格式為例,用k取值的2 種方法來展開圖像壓縮實驗.

3.1 圖像原圖

使用的圖像原圖如圖3所示.

圖3 原圖

原圖寬度為4928 像素,高度為3264 像素,用8 位整數(shù)表示各通道的值.則PNG 原圖占用的存儲空間為(不考慮PNG 格式本身的壓縮效果):

4928×3264×4×8=514 719 744 bits ≈61.36 MB

JPG 原圖占用的存儲空間為(不考慮JPG 格式本身的壓縮效果):

4928×3264×3×8=386 039 808 bits ≈46.02 MB

在Python 中,可用代碼1 的源代碼獲取PNG 原圖4個通道數(shù)據(jù)矩陣.

代碼1.獲取PNG 原圖4通道數(shù)據(jù)矩陣import numpy as np from PIL import Image#加載圖像,第1 個參數(shù)為原圖的完整路徑orignImage=Image.open(r'原圖.png','r')imageArray=np.array(orignImage)#得到R 通道數(shù)據(jù)矩陣R=imageArray[:,:,0]#得到G 通道數(shù)據(jù)矩陣G=imageArray[:,:,1]#得到B 通道數(shù)據(jù)矩陣B=imageArray[:,:,2]#得到A 通道數(shù)據(jù)矩陣#原圖為JPG 時應注釋此句源代碼A=imageArray[:,:,3]

PIL 為Python 的一個第三方圖像處理類庫,事先應在操作系統(tǒng)的命令界面用語句“pip install pillow”來安裝.

3.2 按特征值個數(shù)占比閾值取特征值個數(shù)

在Python 中,用代碼2 即可得到一個數(shù)據(jù)矩陣的奇異值分解結果.

代碼2.數(shù)據(jù)矩陣奇異值分解import numpy as np#對R 通道數(shù)據(jù)矩陣作奇異值分解U_R,sigma_R,V_T_R=np.linalg.svd(R)#對G 通道數(shù)據(jù)矩陣作奇異值分解U_G,sigma_G,V_T_G=np.linalg.svd(G)#對B 通道數(shù)據(jù)矩陣作奇異值分解U_B,sigma_B,V_T_B=np.linalg.svd(B)#對A 通道數(shù)據(jù)矩陣作奇異值分解#為JPG 原圖時應注釋此句源代碼U_A,sigma_A,V_T_A=np.linalg.svd(A)

可以發(fā)現(xiàn),在作奇異值分解后,sigma_R、sigma_G、sigma_B、sigma_A 均為一維數(shù)組,其元素個數(shù)均為3264,則表明均有3264 個特征值.需要注意的是,Python中的0 會表示為一個很小的值,而不會表示為整型的0,因此有的通道數(shù)據(jù)矩陣可能并沒有3264 個特征值,需要編程判斷,可以用特征值與一個很小的值(如0.0001)比較,如果小于這個很小的值,則將特征時判斷為0.結果發(fā)現(xiàn),sigma_A 的特征值只有1 個.為什么會這樣呢?說明A 通道數(shù)據(jù)是冗余的.

設計一個函數(shù),用于生成指定的比例閾值下,用通道的壓縮后數(shù)據(jù)來生成圖像的近似數(shù)據(jù)矩陣,如代碼3 所示.

代碼3.指定比例閾值下的圖像近似數(shù)據(jù)矩陣生成#功能:針對某個通道的數(shù)據(jù)矩陣作奇異值分解得到的U 矩陣、sigma#數(shù)組、V_T 矩陣,根據(jù)percent(百分比)取前若干個特征值來生成#該通道的近似數(shù)據(jù)矩陣#參數(shù):U,對某個通道的數(shù)據(jù)作矩陣奇異值分解后得到的U 矩陣;sigma,#對某個通道的數(shù)據(jù)作矩陣奇異值分解后得到的sigma 數(shù)組;V_T,對#某個通道的數(shù)據(jù)作矩陣奇異值分解后得到的V_T 矩陣;percent,特#征值個數(shù)占比閾值.#返回值:圖像的某個通道的近似數(shù)據(jù)矩陣def genCompressData(U,sigma,V_T,percent):m=U.shape[0]n=V_T.shape[0]reChannel=np.zeros((m,n))for k in range(len(sigma)):#以得到該通道的近似數(shù)據(jù)矩陣#逐個累加reChannel=reChannel+sigma[k]*np.dot(U[:,k].reshape(m,1),V_T[k,:].reshape(1,n))

#如果已經(jīng)超過設定的比例閾值if (float(k)/len(sigma)>percent):#將數(shù)據(jù)值規(guī)范到0-255 范圍內reChannel[reChannel＜0]=0 reChannel[reChannel>255]=255 break#將返回的近似數(shù)據(jù)矩陣的元素數(shù)據(jù)類型規(guī)范#為uint8 return np.rint(reChannel).astype("uint8")

取特征值個數(shù)占比閾值f分別為0.001、0.005、0.01、0.02、0.03、0.04、0.05、0.1.可用代碼4 逐個形成并保存壓縮后再生成的圖像.

代碼4.形成并保存過程for p in [0.001,0.005,0.01,0.02,0.03,0.04,_0.05,0.1]:#生成R 通道近似數(shù)據(jù)矩陣reR=genCompressData(U_R,sigma_R,V_T_R,p)#生成G 通道近似數(shù)據(jù)矩陣reG=genCompressData(U_G,sigma_G,V_T_G,p)#生成B 通道近似數(shù)據(jù)矩陣reB=genCompressData(U_B,sigma_B,V_T_B,p)#生成A 通道近似數(shù)據(jù)矩陣,為JPG 原圖時應注釋此句源代碼reA=genCompressData(U_A,sigma_A,V_T_A,p)#生成完整的近似數(shù)據(jù)3 維矩陣,原圖為JPG 時則轉而使用下面的#注釋語句reI=np.stack((reR,reG,reB,reA),2)# reI=np.stack((reR,reG,reB),2)reI=np.stack((reR,reG,reB,reA),2)Image.fromarray(reI).save("{}".format(p)+"img.png")

為簡便起見,取比例閾值f值為0.001、0.01、0.05、0.1 時的4 幅壓縮效果圖作出展示,如圖4所示.從圖中可以看出,比例閾值f值為0.001 圖不清楚,為0.01 值時可以大致看出輪廓,為0.05 時圖像基本可辨,為0.1 時圖像與原圖相差無幾,人眼分辨不出是否壓縮過.

對JPG 格式圖像的實驗結果這里不再重復羅列分析.在計算出取不同的比例閾值下的壓縮比后,列出結果如表1所示.

從表1可以看到,即使是取比例閾值f為0.1,壓縮比都還能達到5.99,因此,壓縮效果良好.如果對壓縮后的圖像清晰度要求可以降低,則還可以得到更高的壓縮比.

表1中的兩種格式的圖像的壓縮比相同的原因是,不管是3 個通道還是4 個通道,在同一比例閾值下,針對各個通道取特征值的個數(shù)相同,故壓縮比就會相同.

圖4 按特征值個數(shù)占比閾值取特征值個數(shù)時的壓縮效果圖

表1 按特征值個數(shù)占比閾值取特征值個數(shù)時的壓縮比(4 個通道均相同)

3.3 按特征值之和占比閾值取特征值個數(shù)

設計一個函數(shù)(代碼5),用于生成指定的比例閾值下,用各通道的壓縮后數(shù)據(jù)來生成圖像的近似數(shù)據(jù)矩陣.

代碼5.圖像近似數(shù)據(jù)矩陣生成#功能:針對某個通道的數(shù)據(jù)矩陣作奇異值分解得到的U 矩陣、sigma#數(shù)組、V_T 矩陣,根據(jù)percent(百分比)取前若干個特征值來生成#圖像的該通道的近似數(shù)據(jù)矩陣;#參數(shù):U,對某個通道的數(shù)據(jù)做矩陣奇異值分解后得到的U 矩陣;#sigma,對某個通道的數(shù)據(jù)作矩陣奇異值分解后得到的sigma 數(shù)組;#V_T,對某個通道的數(shù)據(jù)作矩陣奇異值分解后得到的V_T 矩陣;

#percent,特征值之和占比閾值.#返回值:圖像的該通道的近似數(shù)據(jù)矩陣def genCompressDataFromSum(U,sigma,V_T,percent):m=U.shape[0]n=V_T.shape[0]reChannel=np.zeros((m,n))sum=0.0 #sum 為特征值總和for i in sigma:sum+=i# sumcurrent 為已累加的特征值的和sumcurrent=0.0 for k in range(len(sigma)):#逐個累加,以得到該通道的近似數(shù)據(jù)矩陣reChannel=reChannel+sigma[k]*np.dot(U[:,k].reshape(m,1),V_T[k,:].reshape(1,n))#累加特征值sumcurrent+=sigma[k]#如果已經(jīng)超過設定的比例閾值if (sumcurrent/sum>percent):#將數(shù)據(jù)值規(guī)范到0-255 范圍內reChannel[reChannel＜0]=0 reChannel[reChannel>255]=255 break#將返回的近似數(shù)據(jù)矩陣的元素數(shù)據(jù)類型規(guī)范為uint8 return np.rint(reChannel).astype("uint8")

取特征值之和占比閾值f分別為0.5、0.6、0.7、0.8、0.9,可用代碼6 逐個形成并保存壓縮后再生成的圖像.

代碼6.形成并保存過程for p in[0.3,0.4,0.5,06,0.7,0.8,0.85,0.9]:#生成R 通道近似數(shù)據(jù)矩陣reR=genCompressDataFromSum(U_R,sigma_R,V_T_R,p)#生成G 通道近似數(shù)據(jù)矩陣reG=genCompressDataFromSum(U_G,sigma_G,V_T_G,p)#生成B 通道近似數(shù)據(jù)矩陣reB=genCompressDataFromSum(U_B,sigma_B,V_T_B,p)#生成A 通道近似數(shù)據(jù)矩陣,為原圖JPG 時應注釋此句源代碼reA=genCompressDataFromSum(U_A,sigma_A,V_T_A,p)#生成完整的近似數(shù)據(jù)3 維矩陣,原圖為JPG 時則轉而使用下面的#注釋語句reI=np.stack((reR,reG,reB,reA),2)# reI=np.stack((reR,reG,reB),2)#保存圖像,參數(shù)為圖像的完整路徑Image.fromarray(reI).save(“{}”.format(p)+“img.png”)

為簡便起見,取比例閾值f值為0.6、0.7、0.8、0.85 時的4 幅壓縮效果圖作出展示,如圖5所示.可以看到,當比例閾值f值為0.7 時,已基本可辨;當比例閾值f值為0.85 時,圖片已經(jīng)比較清晰.表2還給出了取不同的閾值f值時,對應的各個通道的特征值個數(shù),以及針對PNG 格式圖像、針對JPG 格式圖像的存儲空間和壓縮比.

表2中PNG 格式圖像的存儲空間和JPG 格式圖像的存儲空間相同,且A 通道的k值為1 的原因是,PNG格式圖像原圖的A 通道中的值都是等值的255,相當于這個通道的數(shù)據(jù)是冗余的,其圖片顯示效果與JPG 格式圖像相當.

圖5 按特征值之和占比閾值取特征值個數(shù)時的壓縮效果圖

3.4 壓縮比變化趨勢分析

根據(jù)表1和表2,作比例閾值和壓縮比之間的關系圖,如圖6所示.

從圖6(a)來看,對PNG 格式圖像的壓縮比和對JPG 格式圖像的壓縮比的變化曲線相同.在比例閾值為0.01 時出現(xiàn)曲線拐點,這表明在前1%的特征值里,較大值的特征值比較集中;之后曲線變緩,在比例閾值為0.1 以后,曲線已經(jīng)非常平緩,表明增加特征值已很難再改善圖像質量.

從圖6(b)來看,對JPG 格式圖像的壓縮比要比對PNG 格式圖像的壓縮比低一點.在比例閾值為0.9 后,曲線變得更為平緩,這表明增加特征值已很難再改善圖像質量.

表2 按特征值之和占比閾值取特征值個數(shù)時的壓縮比(通道R,G,B,A)

圖6 比例閾值和壓縮比之間的關系圖

相對來說,按特征值之和占比閾值取特征值個數(shù)的方法更為實用.因為首先,它考慮的是特征值的重要程度,而不是個數(shù);其次這種方法可以應對個別通道數(shù)據(jù)冗余的問題.更為重要的是,這種方法可以用于進行大規(guī)模數(shù)量的圖像文件壓縮,因為這種方法可以劃定一個統(tǒng)一的可以接受的特征值之和占比閾值,這個閾值就直接代表著圖像的清晰度.鑒于前述對占比閾值的分析,認為這個統(tǒng)一的占比閾值如要基本可辨取0.7,如要比較清晰取0.85.但按特征值個數(shù)占比閾值取特征值個數(shù)的方法不能劃定一個統(tǒng)一的比例閾值,因為在同一個閾值下,不同的圖像文件的清晰程度可能不同.

3.5 壓縮算法對比分析

現(xiàn)已有很多經(jīng)典的圖像壓縮算法.以經(jīng)典的PNG[5]、JPG[6]圖像格式為對比,仍以本文的圖片作為示例,與本文的壓縮方法在壓縮比上的對比分析如表3所示.由此可見,在對PNG 按特征值之和占比閾值取特征值個數(shù)(f=0.7)時可以取得最高的壓縮比.

表3 對不同圖像格式處理算法的壓縮比對比

鑒于各種算法的原理不同,Python 已經(jīng)提供了成熟的軟件包PIL,直接用保存功能即可將圖片存儲為JPG或PNG 格式,不便計算時間效率.而本文給出的算法關鍵之處在于做奇異值分解所耗費的時間,仍以本文的圖片作為示例,實驗結果如表4所示.可見,對JPG 做奇異值分解效率明顯較高,但顯然處理一個圖片已超過1 分鐘,效率有待提升.

表4 奇異值分解時間效率

4 結束語

通過奇異值分解,可以得到3 個分解結果,即左奇異向量組成的標準正交基矩陣Um×m、特征值對角矩陣Dm×n、右奇異向量組成的標準正交基矩陣.有按特征值個數(shù)占比閾值取特征值個數(shù)和按特征值之和占比閾值取特征值個數(shù)2 種方法來做圖像壓縮,從而得到Dm×n中的前k個特征值、Um×m的前k列、的前k行作為要存儲的數(shù)據(jù)來代表數(shù)據(jù)矩陣.通過對PNG、JPG 兩種格式圖像作壓縮實驗發(fā)現(xiàn),在本實驗個例中,特征值個數(shù)占比閾值取0.1 時,圖片清晰,壓縮比達到5.99;特征值之和占比閾值取0.85 時,圖片清晰,對PNG 格式圖像的壓縮比達到7.89,對JPG 格式圖像的壓縮比達到5.92.認為相對來說,按特征值之和占比閾值取特征值個數(shù)的做法更為實用,可用于大規(guī)模數(shù)量的圖像文件壓縮.

本文研究的局限性在于僅限于奇異值分解本身并應用于圖像壓縮領域,沒有將奇異值分解和其它壓縮算法相結合開展研究.下一步的研究可結合包括奇異值分解在內的多種壓縮算法提出新的組合算法,并作大規(guī)模數(shù)量的圖像文件處理實驗、對比分析,以尋求具有更高壓縮比、能普適應用的圖像壓縮方法.