孫 燕, 李曉光, 卓 力, 潘春花, 朱 存

(1. 青海民族大學(xué) 計算機學(xué)院, 青海 西寧 810007；2. 北京工業(yè)大學(xué) 信號與信息處理實驗室， 北京 100124)

?

一種基于小波壓縮感知的藏族壁畫圖像處理

孫 燕1, 李曉光2, 卓 力2, 潘春花1, 朱 存1

(1. 青海民族大學(xué) 計算機學(xué)院, 青海 西寧 810007；2. 北京工業(yè)大學(xué) 信號與信息處理實驗室， 北京 100124)

針對藏族壁畫特點在采集圖像時采用一種基于小波壓縮的感知算法，利用改進的小波變換，分解圖像高頻分量和低頻分量，并進行稀疏變換，達到采樣壓縮。圖像重構(gòu)利用壓縮感知OMP算法重構(gòu)圖像，實驗表明，原始圖像分塊數(shù)和隨機矩陣不變時，采樣率越大，PSNR越小，重構(gòu)的圖像也越清晰，針對藏族壁畫算法有效。

藏族壁畫； 小波壓縮感知； OMP; 算法

0 引 言

壓縮感知(Compressed sensing)也被稱為壓縮采樣(Compressive sampling)、稀疏采樣(Sparse sampling)[1-6]和壓縮傳感[2-4]。作為一個新的采樣理論，它通過開發(fā)信號的稀疏特性，在遠小于Nyquist 采樣率的條件下，用隨機采樣獲取信號的離散樣本，然后通過非線性重建算法完美的重建信號[5]壓縮感知是一種在采樣的同時實現(xiàn)壓縮目的的理論。藏族壁畫構(gòu)圖豐滿、線條分明、顏色以青、綠、紅、赭等礦石顏料為主，具有鮮明的民族特色，它是傳承藏族傳統(tǒng)文化的載體，圖像在采集時數(shù)據(jù)量大。本文模擬采樣就壓縮，采用小波變換將圖像分解為高頻和低頻分量進行稀疏變換，數(shù)據(jù)量大大減小，緩解了藏族壁畫巨大信息量的硬件壓力，為藏族壁畫數(shù)字化提供了理論基礎(chǔ)。

1 藏族壁畫的特點

藏族壁畫屬喇嘛教宗教畫系，具有濃郁的印藏風(fēng)味。壁畫顏料采用石質(zhì)礦物，色澤鮮艷經(jīng)久不變。壁畫內(nèi)容廣泛，整幅畫面構(gòu)思巧妙，布置恰當(dāng)，色調(diào)和諧，精巧細膩，層次分明千姿百態(tài)，栩栩如生。藏族壁畫精湛古樸，線條細膩明快。形象生動而略有夸張。繪畫技藝潤熟，整體流暢舒展。針對藏族壁畫的特點，藏族壁畫圖像處理需要采集的信息量是巨大的。在采集時就考慮壓縮處理十分必要。

2 壓縮感知理論

壓縮感知Candes等提出[2]，信號在某一正交空間具有稀疏性，在低于奈奎斯特采樣頻率的條件下對信號進行采樣，并重構(gòu)該信號。一般情況下，RN中的長度為N的信號X可表示為

(1)

式中：ψ為N×N的標(biāo)準(zhǔn)正交基；θ是信號X在該正交基上展開的系數(shù)向量；ψi為正交基ψ中的列向量；θi為N×1維系數(shù)向量θ中的元素。如果系數(shù)向量θ中僅有K個元素不為零，且K?N,則稱信號X在正交基ψ下是K-稀疏(K-Sparse)的[7]。

通過變換得到信號的稀疏系數(shù)向量θ=ψTx后，再通過一個觀測矩陣Φ(M×N)得到M(M

(2)

式中：Y為觀測向量；Acs稱為壓縮感知矩陣。若Y和Φ已知，要求解出θ,因為M

(3)

對于式(3)可以利用梯度投影法、基追蹤法、匹配追蹤法、正交匹配追蹤法[10]等求解，進而重建恢復(fù)信號[9]。從數(shù)學(xué)意義上講，基于壓縮感知理論的信號重建問題就是尋找欠定方程組(方程的數(shù)量少于待解的未知數(shù))的最簡單解的問題，可以通過最小范數(shù)模型[11]解決。

2.1 最小L0范數(shù)模型

L0范數(shù)刻畫的就是信號中非零元素的個數(shù)，因而能夠使得結(jié)果盡可能地稀疏。通常我們采用下式描述最小L0范數(shù)最優(yōu)化問題：

(4)

實際中，允許一定程度的誤差存在，因此將原始的最優(yōu)化問題轉(zhuǎn)化成一個較簡單的近似形式求解，其中δ是一個極小的常量：

(5)

但是，這類問題的求解數(shù)值計算極不穩(wěn)定，很難直接求解。

當(dāng)前研究論證的常見算法包括三類：① 貪婪追蹤法，如OMP算法和MP算法; ② 凸松弛法，如內(nèi)點法，迭代閾值; ③ 組合算法，如傅里葉采樣，HHS追蹤[12～15]等。

匹配追蹤類稀疏重建算法解決的是最小L0范數(shù)問題，最早提出的有匹配追蹤(MP)算法和正交匹配追蹤(OMP)算法[16-17]。

2.2 匹配追蹤算法

OMP是利用K稀疏信號x的壓縮投影測量信號Φ，OMP在K次迭代過程中選取與殘差相關(guān)性最大的元素進入支撐集的估計中，然后采用最小二乘正交投影過程來更新估計信號。匹配追蹤算法的基本思想是在每一次的迭代過程中，從過完備原子庫里(即感知矩陣)選擇與信號最匹配的原子來進行稀疏逼近并求出余量，然后繼續(xù)選出與信號余量最為匹配的原子。經(jīng)過數(shù)次迭代，該信號便可以由一些原子線性表示。但是,由于信號在已選定原子(感知矩陣的列向量)集合上的投影的非正交性使得每次迭代的結(jié)果可能是次最優(yōu)的，因此為獲得較好的收斂效果往往需要經(jīng)過較多的迭代次數(shù)。

匹配追蹤類算法通過求余量r與感知矩陣Φ中各個原子之間內(nèi)積的絕對值，來計算相關(guān)系數(shù)：

(6)

并采用最小二乘法進行信號逼近以及余量更新:

(7)

2.3 改進的OMP算法

在做稀疏變換之前，采用改進小波變換進行高頻分量和低頻分量分解和濾波，選取不同分量進行稀疏變換，在重構(gòu)圖像時將由小波變換的稀疏矩陣且選取不同的隨機矩陣進行OMP矩陣方程最小范數(shù)的求解，改進OMP算法步驟如下：

(1) 選取適合藏族壁畫特征的小波函數(shù)構(gòu)造高頻分量和低頻分量。

(2) 轉(zhuǎn)為稀疏矩陣并構(gòu)造正交矩陣。

(3) 計算藏族壁畫特征。顏色和輪廓的相關(guān)系數(shù){〈Rkf,xn〉;xn∈DDk}發(fā)現(xiàn)xn+1∈DDk,如|〈Rkf,xn+1〉|≥asup|Rkf,xj|0<α≤1。

(4) 當(dāng)|〈Rkf,xn+1〉|<δ,(δ>0)停止。記錄D，從1,2,…,k+1。

(5) 計算

設(shè)，

更新以下量

(6) 否停止迭代，則重復(fù)(3)～(7)步。最后輸出x的逼近值。以上步驟流程圖如圖1所示。

圖1 改進壓縮感知小波OMP算法流程圖

3 仿真實驗與結(jié)論

PSNR(Peak Signal to Noise Ratio)是一種評價圖像的客觀標(biāo)準(zhǔn)。它是原圖像與被處理圖像之間的均方誤差相對于(2n-1)2的對數(shù)值(信號最大值的平方，n是每個采樣值的比特數(shù))，單位是dB。公式如下：

(8)

仿真實驗在Matlab2014b，原圖在采集青海同仁縣隆務(wù)寺院院墻上所得壁畫，它是256×256×3的像素點的彩色圖像。仿真實驗分別使用不同的采樣率下的得到PSNR。實驗得到的數(shù)據(jù)和處理的圖像如表1和圖2所示。

表1 不同采樣率下得PSNR

表1是在分塊數(shù)相同的情況下，原采樣率分別為原采樣率的0.125,0.25,0.5,0.78倍數(shù)下的進行稀疏變換和重構(gòu)所用的時間、誤差、PSNR值。從表中和實際重構(gòu)圖像數(shù)據(jù)觀察可知，隨原圖采樣率加大，稀疏矩陣為16×16，所用時間越長，誤差越小，PSNR越小，最后重構(gòu)的圖像也越清晰。表明實驗改進的小波壓縮感知算法對藏族壁畫是有效的，存儲數(shù)據(jù)量小。圖2的藏族壁畫原圖和采樣率為原圖0.125倍和0.5倍的實驗仿真圖也能清晰的看到這個結(jié)果。

(a) 原圖

(b) 采樣率為原圖的0.125倍

(c) 采樣率為原圖的0.5倍

圖2 分塊數(shù)不變采樣率加大的重構(gòu)比較

仿真實驗還進行了是在分塊加大的情況下，在隨機矩陣增大如32×32時進行稀疏變換和重構(gòu)所用的時間，誤差和PSNR值，從表2數(shù)據(jù)和圖3實際重構(gòu)圖像來看，采樣率不變，所用時間隨塊數(shù)增大而增大，誤差不變，PSNR不變，重構(gòu)圖像在分塊4×4，8×8，16×16清晰度幾乎一樣。

表2 隨機矩陣為32×32算法指標(biāo)

塊數(shù)恢復(fù)圖像4×4

8×8

16×16

圖3 分塊數(shù)變化重構(gòu)圖像比較

進而得出結(jié)論:改進的小波OMP重構(gòu)算法與隨機矩陣與圖像分塊有關(guān)，隨機矩陣的塊數(shù)大，原始分塊增大而重構(gòu)時間加大，圖像清晰度不變；在隨機矩陣的塊數(shù)小，原始圖像的分塊數(shù)增大重構(gòu)時間減小，圖像清晰度減小。所以要根據(jù)實際應(yīng)用情況選擇隨機矩陣和原始圖像的分塊大小。

實驗結(jié)果表明：針對藏族壁畫彩色圖像256×256×3真彩色信號，運用改進選擇適合藏族壁畫的小波壓縮感知算法可以得到較低的16×16的灰度信號，使存儲空間大大降低；與OMP的重構(gòu)圖像相比本文改進的小波濾波OMP算法能夠兼顧重構(gòu)時間和重構(gòu)質(zhì)量，數(shù)據(jù)量較傳統(tǒng)OMP小，比OMP重建時間長，但不失為一種比較實用針對藏族壁畫特點的圖像處理算法。

[1] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[2] Candes E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[3] Candes E J, Wakin M B.An introduction to compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2):21-30.

[4] Baraniuk R G. Compressive sensing[J]. IEEE Signal Processing Magazine, 2007, 24(4): 118-121.

[5 ] Candes E J, Romberg J. Sparsity and incoherence in compressive sampling Inverse Problems, 2007, 23(3): 969-985.

[6] Tsaig Y, Donoho D L. Extensions of compressed sensing[J]. Signal Processing, 2006, 86(3): 549-571.

[7] Justin Romberg. Imaging via Compressive Sampling[J]. IEEE Signal Processing Magazine 2008,14-20.

[8] 張銳. 基于壓縮感知理論的圖像壓縮初步研究[J].Computer Knowledge and Technology 2010，6(4):958-959.

[9] 喻玲娟.謝曉春. 壓縮感知理論簡介[J].Video Engineering 2008，32(12): 14-17.

[10] 張春梅,尹忠科,肖明霞. 基于冗余字典的信號超完備表示與稀疏分解[J].科學(xué)通報, 2006(6):628-633.

[11] Joel A,Tropp Anna C.Gilbert Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit[J].IEEE TRANSACTIONS ON INFORMATION THEORY,2015, 53( 12):93-100.

[12] DONOHO D.TSAIG Y Extensions of compressed sensing[J]. Signal Processing, 2006(3):533-534.

[13] Candes E, Romberg J. Quantitative robust uncertainty principles and optimally sparse decompositions[J]. Foundations of Comput Math, 2006, 6(2):227-254.

[14] Coifman R, Geshwind F, Meyer Y. Noiselets[J]. Applied and Computational Harmonic Analysis, 2001, 10(1): 27-44.

[15] Bregman L M.The method of successive projection for finding a common point of convex sets[J]. Soviet Math,1965,6(3):688-692.

[16] Egiazarian K, Foi A, Katkovnik V. Compressed sensing image reconstruction via recursive spatially adaptive filtering[C]//In: Proceedings of IEEE International Conference on Image Processing. Washington D. C., USA: IEEE,2007. 549-552.

[17] Dabov K, Foi A, Katkovnik V, Egiazarian K.Image denoising by sparse 3D transform domain collaborative filtering[J]. IEEE Transactions on Image Processing, 2007, 16(8):2080-2095.

A Tibetan Mural Image Processing Based on Wavelet Compressed Sensing

SUNYan1,LIXiao-guang2,ZHUOLi2,PANChun-hua1,ZHUCun1

(1. School of Computer, Qinghai University for Nationalities, Xining 810007， China; 2. Signal & Information Processing Laboratory, Beijing University of Technology, Beijing 100124, China)

According to the feature of Tibetan murals, a compressed sensing algorithm is presented based on wavelet. The improved compressed sampling algorithm separates the high frequency sub-bands from the low frequency sub-band, and realizes sparse transformation. The compressed sensing OMP algorithm is employed in image reconstruction. Experiments show if the number of blocks and random matrix is fixed, then the sampling rate is higher, the PSNR will be smaller, and the reconstructed image will have better quality. Hence the algorithm is effective for Tibetan murals.

Tibetan murals; wavelet compressed sensing; OMP; algorithm

2015-12-04

青海民族大學(xué)與北京工業(yè)大學(xué)基礎(chǔ)研究合作項目

孫 燕(1973-)，女，山東青島人，副教授，主要從事數(shù)字信號處理，圖像處理，語音信號處理，自然語言處理。

Tel.：13709746897； E-mail: sy0623@163.com

TP391.41

A

1006-7167(2016)05-0138-03