基于SVD变换图像压缩的VC实现

基于SVD变换图像压缩的VC实现

作者：宋 锋

来源：《电脑知识与技术》2010年第10期

摘要:通过对奇异值分解的基本原理和特点的分析,总结出运用奇异值分解进行数字图像压缩的基本方法和步骤,并以VC程序调用MatrixC++库[1]的形式加以实现,表明了该方法的有效性。

关键词:图像处理;图像压缩;压缩率;奇异值分解

中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2010)10-2483-04 VC Implementation based on SVD Transform Image Compression SONG Feng

(Department of Armaments, 93033 People's Liberation Army Troops, Shenyang 110411, China) Abstract: Based on the basic principles and characteristics of the analysis of singular value decomposition, summarized the basic methods and steps of digital image compression by use of singular value decomposition,and then call the VC program Matrix C + + library [1] to be achieved that demonstrated the effectiveness of this method.

Key words: image processing; image compression; compression rate; singular value decomposition

奇异值分解变换(singular value decomposition)即SVD变换,是一种对非对称矩阵的正交变换,它通过特征分析得出基函数,是一种以特征向量为基础的变换。这种变换被广泛应用于数字图像处理(尤其是在图像变换)领域,就发展为基于图像统计特性的变换。 1 基本原理

从矩阵论的角度来看,奇异值分解可定义如下:若A是m×n的实矩阵,且A的秩为r(r∈[0,min(m,n)]),则存在m阶正交矩阵U和n阶正交矩阵V使得:

其中∑是非负对角矩阵,且,是A的全部非零奇异值。矩阵ATA和AAT具有相同的特征值λ,且λ的平方根就是A的奇异值,即:。SVD变换的结果就是得到有一子块为对角矩阵而其余阵元均为零的矩阵。

若A为数字图像,则一个M×N实值图像A可以看作是MN维空间中的一个向量,也可将此图像表示在r维子空间,为r矩阵[A]的秩。由奇异值分解的定义[2]可得:

龙源期刊网 http://www.qikan.com.cn

(1) S=VAUT(2)

式(1)和(2)所表示的正反变换对,叫做奇异值分解(SVD)变换。其中,σi是A的非零奇异值,U和V分别是M×r和N×r矩阵,它们的列向量分别是ATA和AAT的正交特征向量,uiviT可以看作是一个基图像,则数字图像A表示为r个秩为1的基图像的加权和,权系数是奇异值σi。 U和V的核矩阵取决于图像A,进行图像的SVD变换一般需要计算图像A的ATA和AAT特征向量。图像按奇异值分解后,有如下性质:

1)图像的奇异值代表图像的能量信息,因而具有稳定性; 2)图像的奇异值具有比例不变性; 3)图像的奇异值具有旋转不变性。

因此,图像的奇异值变换在图像特征提取、压缩、检索、匹配、数字水印等领域应用广泛。以图像压缩为例,当前对图像压缩的算法有很多,且各有不同的特点[3]。数字图像 A经奇异值分解后,其纹理和几何信息都集中在U、V 之中[4],而∑中的奇异值则代表它刻画了图像的能量信息,若N≤M,则对角阵 至多有N个非零元素,至少可以获得M倍的无损压缩。同时,奇异值中总有一些小到可以被忽略的值,忽略这些值依然可得到满意的视觉效果,则选择合适的奇异值个数来实现图像的有损压缩,可以得到更高的压缩比。奇异值个数选取的越少,图像的压缩比率就越大。调节压缩率可以达到不同的压缩效果,是一种实现过程简单、有效的压缩方法,具有一定的应用前景。下面举例说明:

对于一个的8×8图像矩阵A进行奇异值分解,得到三个矩阵分别为:U(8×8)、S(8×8)、V(8×8): 矩阵A分解后,由其非负对角矩阵S可以得到A的奇异值个数为8个。为了实现矩阵的压缩,取4个奇异值,得到压缩率为50%,则相应的矩阵U、V也取为U1(8×4)、V1(8×4)。重新计算得到压缩后的矩阵A1(8×8):

矩阵A和矩阵A1差距不大,说明应用此原理可以实现图像的压缩,并且能够得到较大的压缩比和较好的效果。 2 压缩步骤

实现用SVD变换完成数字图像在屏幕上的压缩,达到既大幅减小图像的容量,又基本满足视觉效果的目的。可以分为以下6个步骤,如图1所示: 1)将源图像保存到缓冲区,并记录下缓冲区的地址。

龙源期刊网 http://www.qikan.com.cn

2)获取源图像的高度和宽度,创建图像(M×N)的数据矩阵A。 3)根据式(1)对图像矩阵A进行SVD变换,得到矩阵U、V和S。

4)使用对话框设置图像的压缩比率,根据压缩比率选择合适的奇异值个数K,舍弃多余的奇异值,得到K×K的矩阵SK,M×K的矩阵U K和N×K矩阵V K。 5)由公式: Ak=UkSkVkT,得到压缩后的矩阵AK(M×N)。 6)将变换后的矩阵数据赋值给图像,更新显示变换后的图像。 3 程序实现

由于数字图像的SVD变换中使用了大量的矩阵运算,编程和调试工作比较复杂且极易出错,所以我们在VC中使用MatrixC++库,来完成图像变换的操作。

MatrixC++数学库是MathTools公司利用MatCom技术开发的一个面向专业从事工程技术和科学计算人员的矩阵运算动态链接库。该C++库提供了绝大多数的关于矩阵类、矩阵操作、数值计算等函数的定义。

1)在VC工程中集成MatrixC++数学库

① 将v4501v.lib和matlib.h两个文件拷贝到所需用到的工程文件路径中。注意:这两个文件可以在互联网上找到,也可以通过安装MATcom软件(其最新版本为4.5)后,在其安装路径下的lib文件夹中得到,这里我们推荐使用安装MATcom软件的方法。

② 将v4501v.lib添加到工程中,其具体做法是:选中相应的工程,单击【项目】/【属性】项,显示【工程属性页】对话框,在【工程属性页】对话框中的【配置属性】/【链接器】/【命令行】右侧的“附加选项(D)”中,添加v4501v.lib文件。

③ 在需要使用MatrixC++数学库的头文件(.h)和实现文件(.cpp)中添加头文件,即包含如下代码:

#include \"matlib.h\"

④ 初如化MatrixC++数学库,在MainFrm.cpp文件中加入如下代码: CMainFrame::CMainFrame() {

// TODO: add member initialization code here

龙源期刊网 http://www.qikan.com.cn

initM(MATCOM_VERSION); //初始化类库调用 }

CMainFrame::~CMainFrame() {

exitM(); //结束类库调用 }

⑤ 安装MatrixC++数学库对应的动态链接库,当采用MatrixC++数学库完成矩阵的运算时,要求系统中有相关的ago4501.dll、v4501v.dll、opengl132.dll和glu32.dll四个动态链接库文件,这四个文件应拷贝到Window\\system32目录下。如果系统已经安装了Matcom4.5,则这四个文件会自动安装在相应的目录下。

2)通过在数字图像处理程序的框架窗口上增加菜单【正交变换】/【SVD变换】。对应视图类中的OnSvd ()函数进行图像的变换: {…… Mm mSize ;

MmUsvd; //使用 Mm定义矩阵 Mm Wsvd; Mm Ssvd; Mm ff; Mm uu; Mm ww;

mSize = size(m_matBits); //获得矩阵的行数和列数 Usvd = svd_U(m_matBits); //矩阵SVD变换 Wsvd = svd_W(m_matBits);

龙源期刊网 http://www.qikan.com.cn

Ssvd = svd_S(m_matBits); int fsvdAngle;

fsvdAngle = columns(m_matBits); //得到矩阵列长度 CDlgsvdsvdPara; // 创建对话框

if (svdPara.DoModal() != IDOK)// 显示对话框,提示用户设定量 return;

int temsvd = svdPara.m_svd; intk; //奇异值的个数 k = fsvdAngle * temsvd /100; Mm ffn;

ff = Ssvd(colon(1.0,1.0, k),c_p); ff = transpose(ff);

ffn = ff(colon(1.0,1.0, k),c_p); ffn = transpose(ffn); Usvd = transpose(Usvd); uu = Usvd(colon(1.0,1.0, k),c_p); uu = transpose(uu); Wsvd = transpose(Wsvd); ww = Wsvd(colon(1.0,1.0, k),c_p);

m_matBits = uu * ffn * ww; //变换后的压缩矩阵 //将矩阵赋值给图像

m_matBits = muint8(m_matBits);

龙源期刊网 http://www.qikan.com.cn

int nTmp = (int)rem(nWidth,4); int nPadding; if (nTmp > 0) {

nPadding = 4 - nTmp;

m_matBits = cat(2,m_matBits,repmat(muint8(0),(BR(size(m_matBits)),nPadding))); }

m_matBits = rot90(m_matBits,-1);

memcpy(lpSrcStartBits,m_matBits.addr(),(nWidthBytes*nHeight)*sizeof(unsigned char)); …… }

4 结果演示

源图像如图2(a)所示,对其进行SVD变换,分别取压缩比率为50%、30%和20%,其结果分别如图2(b)、2(c)和2(d)所示。

(a)原始图像 (b)压缩比率为50%的图像(c)压缩比率为30%的图像(d)压缩比率为20%的图像 图2 SVD变换效果演示 5 结论

本文探索了一种基于SVD变换的图像压缩方法,并且进行了VC程序实现。数字图像 A经奇异值分解后,其奇异值则代表它刻画了图像的能量信息。选择合适的奇异值个数,去除奇异值矩阵中的零元素及忽略奇异值中一些较小值时,可得到较高的图像压缩率及满意的视觉效果。实验结果表明,当压缩比率大于30%时,均可得到比较满意的视觉效果。也就是说,图像的奇异值个数可以减少约三分之一,图像的容量大幅减小,这种方法有效的实现了图像的压缩。

目前绝大多数基于SVD变换的图像压缩方法都是通过Matlab实现的,本文通过VC程序调用MatrixC++库的形式进行编程,实现了无Matlab环境下的SVD变换,提高了程序的可扩展性。基于SVD变换的图像压缩也有许多改进的算法,例如:奇异值分解的之前先将数据图像分成了M?M个小图像,先求出每个小图像的奇异值的平均,再进行图像的压缩,由于相邻像素点相关性

龙源期刊网 http://www.qikan.com.cn

比较强,因此通过较少的特征向量即可在比较大的压缩比情况下获得更好的图像质量。这些是开展未来研究工作的方向,可以应用于更复杂的领域。 参考文献:

[1] 何东健.数字图像处理[M].2版.西安电子科技大学出版社,2008. [2] ANIL K.JAIN.数字图像处理基础[M].韩博等,译.清华大学出版社,2006.

[3] CHEN,KWONG SAM,FENG JJFU.A new compression scheine for color-quantized image[J].IEEE Transactions on Circuits and SystemsforVideoTechnology,2002,12(10):36-39. [4] MARTIN M B.New image compression techniques using multiwavelets and multiwavelet packets[J].IEEE Transactions on Image Processing,2001,10(4):500-511.