一种基于小波压缩感知的藏族壁画图像处理

孙 燕, 李晓光, 卓 力, 潘春花, 朱 存

(1. 青海民族大学 计算机学院, 青海 西宁 810007；2. 北京工业大学 信号与信息处理实验室， 北京 100124)



一种基于小波压缩感知的藏族壁画图像处理

孙 燕1, 李晓光2, 卓 力2, 潘春花1, 朱 存1

(1. 青海民族大学 计算机学院, 青海 西宁 810007；2. 北京工业大学 信号与信息处理实验室， 北京 100124)

针对藏族壁画特点在采集图像时采用一种基于小波压缩的感知算法，利用改进的小波变换，分解图像高频分量和低频分量，并进行稀疏变换，达到采样压缩。图像重构利用压缩感知OMP算法重构图像，实验表明，原始图像分块数和随机矩阵不变时，采样率越大，PSNR越小，重构的图像也越清晰，针对藏族壁画算法有效。

藏族壁画； 小波压缩感知； OMP; 算法

0 引 言

压缩感知(Compressed sensing)也被称为压缩采样(Compressive sampling)、稀疏采样(Sparse sampling)[1-6]和压缩传感[2-4]。作为一个新的采样理论，它通过开发信号的稀疏特性，在远小于Nyquist 采样率的条件下，用随机采样获取信号的离散样本，然后通过非线性重建算法完美的重建信号[5]压缩感知是一种在采样的同时实现压缩目的的理论。藏族壁画构图丰满、线条分明、颜色以青、绿、红、赭等矿石颜料为主，具有鲜明的民族特色，它是传承藏族传统文化的载体，图像在采集时数据量大。本文模拟采样就压缩，采用小波变换将图像分解为高频和低频分量进行稀疏变换，数据量大大减小，缓解了藏族壁画巨大信息量的硬件压力，为藏族壁画数字化提供了理论基础。

1 藏族壁画的特点

藏族壁画属喇嘛教宗教画系，具有浓郁的印藏风味。壁画颜料采用石质矿物，色泽鲜艳经久不变。壁画内容广泛，整幅画面构思巧妙，布置恰当，色调和谐，精巧细腻，层次分明千姿百态，栩栩如生。藏族壁画精湛古朴，线条细腻明快。形象生动而略有夸张。绘画技艺润熟，整体流畅舒展。针对藏族壁画的特点，藏族壁画图像处理需要采集的信息量是巨大的。在采集时就考虑压缩处理十分必要。

2 压缩感知理论

压缩感知Candes等提出[2]，信号在某一正交空间具有稀疏性，在低于奈奎斯特采样频率的条件下对信号进行采样，并重构该信号。一般情况下，RN中的长度为N的信号X可表示为

(1)

式中：ψ为N×N的标准正交基；θ是信号X在该正交基上展开的系数向量；ψi为正交基ψ中的列向量；θi为N×1维系数向量θ中的元素。如果系数向量θ中仅有K个元素不为零，且K≪N,则称信号X在正交基ψ下是K-稀疏(K-Sparse)的[7]。

通过变换得到信号的稀疏系数向量θ=ψTx后，再通过一个观测矩阵Φ(M×N)得到M(M

(2)

式中：Y为观测向量；Acs称为压缩感知矩阵。若Y和Φ已知，要求解出θ,因为M

(3)

对于式(3)可以利用梯度投影法、基追踪法、匹配追踪法、正交匹配追踪法[10]等求解，进而重建恢复信号[9]。从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(方程的数量少于待解的未知数)的最简单解的问题，可以通过最小范数模型[11]解决。

2.1 最小L0范数模型

L0范数刻画的就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏。通常我们采用下式描述最小L0范数最优化问题：

(4)

实际中，允许一定程度的误差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中δ是一个极小的常量：

(5)

但是，这类问题的求解数值计算极不稳定，很难直接求解。

当前研究论证的常见算法包括三类：① 贪婪追踪法，如OMP算法和MP算法; ② 凸松弛法，如内点法，迭代阈值; ③ 组合算法，如傅里叶采样，HHS追踪[12～15]等。

匹配追踪类稀疏重建算法解决的是最小L0范数问题，最早提出的有匹配追踪(MP)算法和正交匹配追踪(OMP)算法[16-17]。

2.2 匹配追踪算法

OMP是利用K稀疏信号x的压缩投影测量信号Φ，OMP在K次迭代过程中选取与残差相关性最大的元素进入支撑集的估计中，然后采用最小二乘正交投影过程来更新估计信号。匹配追踪算法的基本思想是在每一次的迭代过程中，从过完备原子库里(即感知矩阵)选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是,由于信号在已选定原子(感知矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。

匹配追踪类算法通过求余量r与感知矩阵Φ中各个原子之间内积的绝对值，来计算相关系数：

(6)

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

(7)

2.3 改进的OMP算法

在做稀疏变换之前，采用改进小波变换进行高频分量和低频分量分解和滤波，选取不同分量进行稀疏变换，在重构图像时将由小波变换的稀疏矩阵且选取不同的随机矩阵进行OMP矩阵方程最小范数的求解，改进OMP算法步骤如下：

(1) 选取适合藏族壁画特征的小波函数构造高频分量和低频分量。

(2) 转为稀疏矩阵并构造正交矩阵。

(3) 计算藏族壁画特征。颜色和轮廓的相关系数{〈Rkf,xn〉;xn∈DDk}发现xn+1∈DDk,如|〈Rkf,xn+1〉|≥asup|Rkf,xj|0<α≤1。

(4) 当|〈Rkf,xn+1〉|<δ,(δ>0)停止。记录D，从1,2,…,k+1。

(5) 计算

设，

更新以下量

(6) 否停止迭代，则重复(3)～(7)步。最后输出x的逼近值。以上步骤流程图如图1所示。

图1 改进压缩感知小波OMP算法流程图

3 仿真实验与结论

PSNR(Peak Signal to Noise Ratio)是一种评价图像的客观标准。它是原图像与被处理图像之间的均方误差相对于(2n-1)2的对数值(信号最大值的平方，n是每个采样值的比特数)，单位是dB。公式如下：

(8)

仿真实验在Matlab2014b，原图在采集青海同仁县隆务寺院院墙上所得壁画，它是256×256×3的像素点的彩色图像。仿真实验分别使用不同的采样率下的得到PSNR。实验得到的数据和处理的图像如表1和图2所示。

表1 不同采样率下得PSNR

表1是在分块数相同的情况下，原采样率分别为原采样率的0.125,0.25,0.5,0.78倍数下的进行稀疏变换和重构所用的时间、误差、PSNR值。从表中和实际重构图像数据观察可知，随原图采样率加大，稀疏矩阵为16×16，所用时间越长，误差越小，PSNR越小，最后重构的图像也越清晰。表明实验改进的小波压缩感知算法对藏族壁画是有效的，存储数据量小。图2的藏族壁画原图和采样率为原图0.125倍和0.5倍的实验仿真图也能清晰的看到这个结果。

(a) 原图

(b) 采样率为原图的0.125倍

(c) 采样率为原图的0.5倍

图2 分块数不变采样率加大的重构比较

仿真实验还进行了是在分块加大的情况下，在随机矩阵增大如32×32时进行稀疏变换和重构所用的时间，误差和PSNR值，从表2数据和图3实际重构图像来看，采样率不变，所用时间随块数增大而增大，误差不变，PSNR不变，重构图像在分块4×4，8×8，16×16清晰度几乎一样。

表2 随机矩阵为32×32算法指标

块数恢复图像4×4

8×8

16×16

图3 分块数变化重构图像比较

进而得出结论:改进的小波OMP重构算法与随机矩阵与图像分块有关，随机矩阵的块数大，原始分块增大而重构时间加大，图像清晰度不变；在随机矩阵的块数小，原始图像的分块数增大重构时间减小，图像清晰度减小。所以要根据实际应用情况选择随机矩阵和原始图像的分块大小。

实验结果表明：针对藏族壁画彩色图像256×256×3真彩色信号，运用改进选择适合藏族壁画的小波压缩感知算法可以得到较低的16×16的灰度信号，使存储空间大大降低；与OMP的重构图像相比本文改进的小波滤波OMP算法能够兼顾重构时间和重构质量，数据量较传统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].科学通报, 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

青海民族大学与北京工业大学基础研究合作项目

孙 燕(1973-)，女，山东青岛人，副教授，主要从事数字信号处理，图像处理，语音信号处理，自然语言处理。

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

TP391.41

A

1006-7167(2016)05-0138-03