岳 鑫，肖 晨

(1.西安工業(yè)大學(xué)光電工程學(xué)院，陜西西安710021;2.電子信息現(xiàn)場勘驗(yàn)應(yīng)用技術(shù)公安部重點(diǎn)實(shí)驗(yàn)室，陜西西安710121;3.西安工業(yè)大學(xué)學(xué)報(bào)編輯部，陜西西安710021)

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

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

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

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

1.1 奇異值分解算法

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

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

其中

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

那么

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

1.2 重采樣算法

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

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

雙三次插值計(jì)算公式為

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

圖1 雙三次插值原理

為了減少計(jì)算的復(fù)雜度，雙三次插值過程通常分解為橫向和縱向兩個(gè)方向的插值。首先利用原像素和虛擬像素進(jìn)行縱向插值，并且得到(Fh1，F(xiàn)h2，F(xiàn)h3，F(xiàn)h4)4個(gè)像素;然后再由這4個(gè)像素通過橫向插值得到像素F。

1.3 算法改進(jìn)

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

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

圖2 奇異值分解

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

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

2 實(shí)驗(yàn)與分析

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

圖3 刑偵圖像

圖4 放大結(jié)果

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

圖3 圖像局部

評價(jià)圖像縮放質(zhì)量好壞的另一種方法是使用客觀評價(jià)指標(biāo)進(jìn)行評價(jià)。使用應(yīng)用較為廣泛的四種評價(jià)方法對包括改進(jìn)算法在內(nèi)的6種算法縮放結(jié)果圖像進(jìn)行評價(jià)。評價(jià)方法分別為反應(yīng)圖像平均亮度的均值、反應(yīng)圖像灰度級分散程度的圖像標(biāo)準(zhǔn)差、反應(yīng)圖像清晰程度的圖像平均梯度和反應(yīng)圖像平均信息量的圖像熵。

圖像像素的均值，反映了圖像的平均亮度，平均亮度越小，圖像質(zhì)量越差，設(shè)待評價(jià)圖像為F，大小為M×N，其均值計(jì)算公式為

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

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

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

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

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

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

表1 均值指標(biāo)對比

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

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

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

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

表2 標(biāo)準(zhǔn)差對比

表3 平均梯度對比

表4 熵對比

表5 文件大小對比/kb

3 結(jié)語

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