基于奇異值分解和雙三次插值的圖像縮放算法改進

岳 鑫，肖 晨

(1.西安工業(yè)大學光電工程學院，陜西西安710021;2.電子信息現場勘驗應用技術公安部重點實驗室，陜西西安710121;3.西安工業(yè)大學學報編輯部，陜西西安710021)

由于視頻及圖像中包含豐富的信息，公安機關經常將其作為案件的證據或者線索?，F勘圖像是刑偵人員為發(fā)現和收集證據而對案件有關的場所、物品等進行勘查和檢驗時拍攝的照片［1-2］。在現勘圖像采集時，圖像分辨率高、占用空間大，這些原始圖片中存在過多的冗余信息，并不利于傳輸與處理，一般都需要采用性能良好的縮放算法進行預處理。

目前，傳統(tǒng)的圖像縮放算法主要是基于插值的算法，使用最近鄰插值、雙線性插值［3］或者三次樣條插值［4］等技術來改變圖像大小。Parker、Kenyon等人分析了各類經典空間域插值方法的性能，發(fā)現這類方法運算速度快，同時縮放后的圖像視覺效果較好［5-6］。但這些算法常常無法對紋理信息或者圖中相鄰像素間的較大變化進行很好的處理，容易造成邊緣的模糊或形成鋸齒狀，且傳統(tǒng)算法多專注于對圖像像素的改變，而對圖像壓縮改進不大。

提出一種改進的算法，對圖像進行奇異值分解［7-10］，使用分解產生的矩陣進行重采樣［11-12］，從而達到提高縮放圖像質量且壓縮圖像大小的目的。

1 奇異值分解與重采樣算法

1.1 奇異值分解算法

λ1≥ λ2≥ …≥ λr≥ λr+1=… =λn=0，

則存在矩陣 Um×m和 Vn×n，使得

其中

于是，σi(i=1，2，…，r)為A的奇異值。定義奇異值向量Sγ為對角矩陣S對角線元素的排列，即

那么

由上述定義知，矩陣經過奇異值分解后得到的非零奇異值的個數與矩陣的秩相等。因為經歷了重采樣后的圖像塊的秩小于等于原圖像塊，也就是說，圖像塊像素間的相關性增大。所以，對圖像進行奇異值分解，圖像塊的能量將集中于對角線的左上角，序數低的奇異值將增大，而序數高的奇異值會變小。即重采樣圖像塊的奇異值向量中，零奇異值和小奇異值的個數會增加。

1.2 重采樣算法

重采樣就是在矩陣元素之間引入某種相關性，一般通過對矩陣進行采樣和插值實現。重采樣算法的變換有線性和非線性之分，但其變換總會以線性相關性表現。重采樣包括縮放變換［13］和旋轉變換，通常分為下采樣、插值和上采樣3個步驟。不同的重采樣方法，所采用的插值［14］方法也不同。

使用雙三次插值［15］算法來實現重采樣。雙三次插值，是一種比雙線性插值更加復雜的插值方式，其創(chuàng)造出的圖像邊緣也更加平滑。在二維空間中最常用的插值方法就是雙三次插值。這種方法中，可以通過矩形網格中最近的十六個采樣點的加權平均得到函數f在點(x，y)的值，雙三次插值即使用兩個多項式插值三次函數，每個方向使用一個。通過雙三次插值得到的插值函數是連續(xù)的，其一階偏導數連續(xù)，交叉導數也處處連續(xù)。

雙三次插值計算公式為

插值數據的特性決定計算系數aij，如果插值函數的導數已知，使用四個頂點的高度以及每個頂點的三個導數。x與y方向的表面斜率用一階導數h'x與h'y表示，同時在x與y方向的斜率由二階相互導數h″xy表示。可以通過分別連續(xù)對x與y向量取微分得到這些值。將局部坐標(0，0)，(1，0)，(0，1) 和(1，1)帶入這些方程，再解這16個方程，可得到網格單元的每個頂點。圖1給出了雙三次插值的原理，它展示了插值像素F用4×4鄰域像素計算的過程。

圖1 雙三次插值原理

為了減少計算的復雜度，雙三次插值過程通常分解為橫向和縱向兩個方向的插值。首先利用原像素和虛擬像素進行縱向插值，并且得到(Fh1，Fh2，Fh3，Fh4)4個像素;然后再由這4個像素通過橫向插值得到像素F。

1.3 算法改進

經典縮放算法在圖像縮放時只關注圖像本身，未注意到在圖像中存在較多無用的信息，這些無用的信息隨著圖像的縮放而縮放。為了解決在圖像縮放同時兼顧圖像本身所帶信息的有效性和圖像文件的大小問題，提出一種基于奇異值分解和雙三次插值的圖像縮放算法。

算法思想基本如下:每一個彩色圖像可以看做為由RGB三通道組成的三個實數矩陣，若為灰度圖像則可以看做由0到255組成的單個矩陣。由式(1)可知無論是彩色圖像還是灰度圖像均可分解為三個矩陣相乘的形式。三個矩陣中的中間矩陣式(2)為奇異值矩陣，且該矩陣的能量集中在左上角。在圖像進行壓縮時，可以利用該矩陣中能量集中在左上角的性質依次減少最少的能量，達到在壓縮過程中圖像損失最小的目的。圖2為32×32的猴子圖像及以奇異值10%為跨度取值的奇異值分解結果圖像。

圖2 奇異值分解

由式(1)可知，針對奇異值分解中的三個矩陣左右矩陣U和VH的重采樣可以達到對圖像尺寸大小的變化。其中重采樣方法采用雙三次插值法。以M×N的圖像為例，分別對三個圖像通道做如下變換。奇異值分解結果為USVH，其中S為奇異值矩陣，S對應的酉矩陣為U和V，即U為M×M矩陣，V為N×N矩陣，若想將原始M×N的矩陣縮放到M1×N1的矩陣，需要通過式(3)分別對矩陣U和矩陣V進行重采樣，得到矩陣UM1×M和矩陣VHN×N1，分別記為U'和V'，最后利用公式U'SV'進行反變換。

通過上述方式，對原始圖像進行縮放處理之后，得到的結果圖像不僅可以達到圖像縮放的目的，而且極大的減少了圖像內無關的信息，使可以得到最優(yōu)的結果。

2 實驗與分析

針對刑偵圖像數據庫進行了實驗測試分析。以圖3所示原始圖像(600×358像素)為例，使用最近鄰插值法、線性插值法、區(qū)域插值法、雙三次插值法、Lanczos插值法和所給改進算法進行5倍放大的結果圖像如圖4所示，其相應的局部圖像如圖5所示。從中可見，所給改進算法在視覺效果上要優(yōu)于其他算法，特別是在保存圖像紋理細節(jié)信息上，所給改進算法表現良好。

圖3 刑偵圖像

圖4 放大結果

圖5 (a)和圖5(c)中的局部圖像出現了明顯的 馬賽克現象，如書包帶。而在文中使用算法進行放大的圖像圖5(f)中沒有出現明顯的馬賽克現象。對比圖5(b)和圖5(g)可以發(fā)現改進算法在清晰度較線性插值法更好一些。因此改進算法的放大結果不僅保留了圖像的細節(jié)信息，同時從直觀來講較最近鄰插值、線性插值和區(qū)域插值有一定的優(yōu)化。通過對圖4(d)、圖4(e)和圖4(f)雙三次插值法、Lanczos插值法和改進算法的對比可以看出這三種算法在視覺上無太大差異，而在客觀指標中改進算法在各個指標中都略優(yōu)于雙三次插值法、Lanczos插值法。

圖3 圖像局部

評價圖像縮放質量好壞的另一種方法是使用客觀評價指標進行評價。使用應用較為廣泛的四種評價方法對包括改進算法在內的6種算法縮放結果圖像進行評價。評價方法分別為反應圖像平均亮度的均值、反應圖像灰度級分散程度的圖像標準差、反應圖像清晰程度的圖像平均梯度和反應圖像平均信息量的圖像熵。

圖像像素的均值，反映了圖像的平均亮度，平均亮度越小，圖像質量越差，設待評價圖像為F，大小為M×N，其均值計算公式為

圖像像素灰度值相對于均值的離散程度用標準差(Standard Deviation)表示。如果標準差越小，表明圖像中灰度級分別越集中，圖像質量也就越差。設待評價圖像為F，大小為M ×N，均值為u，其標準差計算公式為

圖像中細節(jié)反差和紋理變換用平均梯度來反映，圖像的清晰程度其在一定程度上也能反映。設待評價圖像為F，大小為M×N，其平均梯度計算公式為

式中，ΔxF(i，j) 和 ΔyF(i，j) 分別表示像素點(i，j)在x或者y方向上的一階差。

圖像的平均信息量用熵來表示，他從信息論的角度衡量圖像中信息的多少，圖像中的信息熵越小，說明圖像包含的信息越少。其計算公式為

其中，灰度值l在圖像中出現的概率為P(l)，圖像的灰度級為L，對256灰度等級的圖像，L=255。

各種算法在5倍、2倍、0.5倍和0.2倍縮放比例下，結果圖像均值指標對比情況如表1所示。在6種算法中放大5倍和放大2倍時改進算法均值指標均高于其他算法，在縮放0.5倍時改進算法排第四，但與第二只有0.09%的差距，與第一有0.21%的差距，可以認為是基本一致的。在縮放0.2倍時，改進算法均值指標排第二，較第一有1%的差距?？傮w上在均值方面改進算法表現良好。

表1 均值指標對比

各種算法在不同放大比例下，結果圖像標準差指標對比見表2。從表中可知，改進算法在標準差指標上較為穩(wěn)定，只有0.4%的浮動。在圖像放大時，除線性插值法外的其他算法基本一致且要優(yōu)于線性插值法。在圖像縮小時，改進算法要優(yōu)于或等同于除最近鄰插值法外其他算法，且與最近鄰插值法只有 1.26%的差距。在縮放 5 倍、2 倍、0.5 倍、0.2倍下，分別在第一、第三、第五和第四名，即使在最差的縮放0.5倍時也與第一只有0.47%的差距，且在最好時可以超過區(qū)域插值法約4.5%?？梢哉J為在標準差指標上這6種算法效果基本一致，即6種算法的灰度分布較為統(tǒng)一。

平均梯度是反應細節(jié)反差和紋理變換的一種指標，在一定程度上反應出圖像的清晰度。各種算法在不同縮放倍數下平均梯度指標對比見表3。在放大5倍時最鄰近插值法和區(qū)域插值法在指標上均好過改進算法，但是這兩種算法從主觀評價上產生了較多的馬賽克現象，放大倍數越大，其馬賽克現象越嚴重。在本算法中，避免了該問題的產生。在縮放0.2倍時改進算法較區(qū)域插值法提高了32.6%。

表4為各種縮放算法在不同縮放倍數下熵對比，熵代表了圖像的信息量，在圖像放大的過程中圖像的信息量基本不會損失，由該表可以看出在各種縮放倍數下包括改進算法的這6種算法計算的結果圖像對原圖像信息保留結果較為一致，且相差不到1%。在圖像縮小時圖像的信息會有一定的損失，在縮放0.5倍和0.2倍時，改進算法保留了較多的圖像信息。

表5為各算法在各個縮放倍數下結果圖像的文件大小概況。由圖可知，改進算法無論在對圖像進行放大操作還是縮小操作時，均可減少文件大小，且遠小于其他五種算法的結果圖像文件大小。在5倍縮放倍數下改進算法較其他算法減少了73%～58.5%的文件體積，在2倍縮放時減少了60%～50.7%的文件體積，在縮放0.5倍和0.2倍時分別減少了 55.8%～40.1%和 49.1%～42%的文件體積。改進算法在文件體積上有較大的優(yōu)化。

表2 標準差對比

表3 平均梯度對比

表4 熵對比

表5 文件大小對比/kb

3 結語

提出基于奇異值分解和雙三次插值縮放算法的改進。利用奇異值分解方法將圖像矩陣分解為三個小矩陣相乘的形式，采用雙三次插值算法將乘式中左右矩陣進行重新采樣，經過重構得到縮放結果圖像。實驗表明，改進算法可以完成對圖像的縮放，能在有效縮放的同時減小圖像文件大小。經過實驗，并與傳統(tǒng)縮放算法進行比較和對縮放結果圖像的客觀指標的計算，發(fā)現通過該算法結果圖像的客觀圖像評價指標略優(yōu)于其他算法指標，結果圖像文件大小遠小于其他算法結果圖像。