基于FFT 和PCA 的图像压缩方法研究①

苗水清, 闫文耀, 张 静, 吴梦蝶

(延安大学西安创新学院,陕西 西安 710100)

0 引 言

互联网时代,人们对于大量图像的保存,共享以及携带都发生了很大的变化,以数字图像进行存储则更受用户的青睐,但是针对海量的图像所需的存储空间是无法估量的,正因为如此图像压缩技术在图像处理中一直备受研究员和用户关注的科学问题。图像压缩为用户通过网络传输共享多媒体信息不仅提供了较小的存储空间,而且通过较少的数据量即可表达出用户所需的信息,成为数据携带和共享的有效手段。除此之外,图像压缩在其他领域也应用较多,视频会议、遥感、文本和医学图像处理,传真传输等[1]。图像压缩,又称为图像编码,是指以较少的数据比特有损或无损地表示原始图像的技术[2]。目前许多学者致力于多媒体信息压缩的研究,经过几十年的发展研究,小波理论,人工神经网络,视觉仿真纷纷诞生并应用到图像压缩技术中。其中也有一些压缩技术是在空间域中进行一些数学变换,有的研究快速方向离散余弦变换[3],DCT 变换[4]等等。主要研究了在空域中直接对图像进行PCA 变换进行图像压缩的方法和基于频域对图像进行傅里叶变换(FFT)后,然后再用PCA变换进行图像压缩并重构的方法,将这两种方法做了比较,研究证明:采用后者能够快速提取较少的主成分对频域图像进行压缩,对压缩后图像重构后有较好的还原度。

1 FFT 变换基本原理[5,6]

DFT(离散傅利叶变换)将任何的信号如一维数字信号或二维图像信号等表示成一系列正弦信号的叠加,从而在频域中能够将时域或空间域信号分解成无数个离散的正弦波。而FFT(快速傅里叶变换)是DFT 的一种快速的计算方法。它是库利(Cooley)和图基(Tukey)于1965 年提出的。FFT 使DFT 的次数由N^2减少到Nlog2(N)次,使DFT 应用于实际变为现实,使DFT 进一步得到完善。

在数字图像处理中,傅里叶变换将图像由空间域转换到频域,在频域研究图像的频率分布或者进行一些滤波去噪处理等,也可以通过FFT 逆变换实线图像从频域到空间域的转换。

一维DFT 计算公式如式(1),(2):

式(1),(2)中x(n)表示输入的离散数字信号序列,WN为旋转因子,X(k)为输入序列x(n)对应的N 个离散频率点的相对幅度。 一般情况下,假设x(n)来自于低通采样,采样频率为fs,那么X(k)表示了从-fs/2率开始,频率间隔为fs/N,到fs/2,-fs/N 截至的N 个频率点的相对幅度。因为DFT 计算得到的一组离散频率幅度值实际上是在频率轴上成周期变化的,即X(k + N)=X(k)。因此任意取连续的N 个点均可以表示DFT 的计算效果,负频率成分比较抽象,难于理解,根据X(k)的周期特性,于是又可以认为X(k)表示了从零频率开始,频率间隔为fs/N,到fs,-fs/N 截至的N 个频率点的相对幅度。

1)DFT 及IDFT(离散傅立叶逆变换)变换

DFT 计算公式如(3):

式(3),(4)中,f(x,y)是M *N 的二维数据,u,v 为频域变量,x,y 为空间域变量;u,x=0,1,2…,M -1,v,y=0,1,2,…,N -1。

2)空间和频率间隔的关系

在连续函数f(t,z)取样生成了数字图像f(x,y),它分别由在t和z 方向所取的M*N 个样点组成。

式(5),(6)中,ΔT ,ΔZ 表示M *N 个样本点间的间隔,从公式中反应出频域样本间的间隔与空间样本间的间距和样本数成反比。

2 PCA 基本原理[7][8]

PCA 是一种将高维数据通过变换矩阵投影到低维度空间以实现数据降维的一种方法,通常具有很好的压缩比,且降维的数据能够很好的表现原始数据的特征,对于数量较大指标有明显的优势,并对提高系统运行效率有着重要的意义。具体计算步骤如下:

1)构造样本矩阵S,如有p 个样本并将其中心化,如式(7):

2)计算样本协方差矩阵,如式(8),(9):

式(8),(9)中:i,j=1,2,3,...,p;通过公式(4)可以得出协方差矩阵的特征值λi和特征向量,选出最大的特征值对应的特征向量,组成新的特征向量矩阵。每个特征值λi对应的单位特征向量为ai,那么第i个主成分Fi为:

3)计算累积贡献率,其中贡献率αi为:

通常当累计贡献率达到一定程度时候,就可以用来评价原始数据;

4)计算样品的主成分:

通过上述步骤得到的即是降维后的图像数据。

PCA 图像变换的过程中通过降维能够实现图像压缩,同时PCA 对于噪声信号也具有一定的过滤作用,PCA 将图像数据投影到低维空间后会屏蔽掉一些噪声信息。

3 基于FFT 和PCA 的图像压缩

将灰度图像应用FFT 变换到频域,然后对频域图像采用PCA 进行降维以实现压缩,图像压缩后需要通过PCA 反变换和FFT 逆变换返回到空间域。

M 表示分块后的每一小块图像为M *M 维,N 表示将原始图像分块的个数,R 和C 表示原始图像为R*C 维,Size表示图像的大小,FD 是降维后的数据,UL为变换矩阵,Mean是均值矩阵,End是结束标志符号,PCA 到PCA 逆变换之间的数据格式由Size+FD+UL+Mean+End组成。具体实现步骤如下:

Step1:把原始图像灰度化后通过FFT 变换到频域;

Step2:对频域图像进行分块处理分成N 个M *M 的矩阵,组成一个M *M 行N 列数据阵列;

Step3:对步骤2中的图像进行PCA 变换,选择累积贡献率达到0.999的主成分组成变换矩阵,并将原始数据变换到主成分投影空间中。一般情况下分块后的矩阵维数如果比较大的话,那么含有的主成分信息量相对较大,舍弃一块会丢失较多信息,还原后的图像失真比较大,因此累积贡献率选取值要大一些;

Step4:对压缩后的图像数据进行PCA 逆变换,并将分块矩阵合并成频域方阵,其中主成分区域采用主成分数据,其他区域则用0代替表示这些区域的数据,使其信息量为0;

Setp5:将步骤4中的频域信号去中心化处理,并利用FFT 逆变换将图像还原。

4 实验结果及分析

对256*256图像分别进行64*64,32*32维度的分割实验,其中图1表示含有高斯噪声的原始图像,图2表示FFT 变换后的频域图像。

图1 原始图像

图2 原始图像转换到频域后

1)将图像按照64*64像素进行分割

图4 复原后图像

图3中采用7个频域中的分割块还原了图像,图像压缩比为:7*64*64/(256*256)=0.4375。

图3 PCA 逆变换后的频域图像

2)将图像按照32*32像素进行分割

图6 复原后图像

图5 中采用29 个频域中的分割块还原了图像,图像压缩比为:29*32*32/(256*256)=0.453125。

图5 PCA 逆变换后的频域图像

3)结果分析:

图3、图5 中可以看出对频域图像进行PCA变换后,再逆变换回来,通常需要一半左右的数据量就能满足效果,这也是傅里叶的对称性作用的结果;随着分块矩阵维度减小,对于相同的复原清晰度,图像的压缩比在逐渐增大,而噪声信号更容易去除,因为将频域图像分块后,分块图像中的噪声信号比有用信号少,去掉噪声信号的同时会去除较多的有用信息,因此,图像分块数据维度越大计算过程越快,图像压缩比越大,但是对噪声的处理效果会越差;

通过对频域图像应用PCA 变换,并且根据FFT 的对称性原理,利用一半的数据量就能还原到和原始图像相差不大的程度,压缩比0.5以下,并且能起到一定的降噪作用。

5 结 语

该方法将图像转换到频域后使得图像的能量信息更集中,采用PCA 变换后能够很好的提取主成分,如果在空间域直接对图像进行PCA 变换降维后将去掉的是图像实际数据,还原效果不好,而通过该方法在频域中去掉的是一些微弱的图像信号和一些噪声信号,能够取得较好的还原效果,同时对图像压缩效果较为明显;此外该方法在处理噪声方面对于分块维度较大情况下虽然计算速度快,但是在去除噪声会噪声方面会失去较多有用的频域信息,相反采用较小的分割维度进行处理,对于去噪方面效果会更好,但是又会牺牲较多的计算时间,因此针对频域图像PCA 变换后的降噪处理和计算时间效率上的矛盾是后期研究的重点。