基于KL变换编码的数据压缩算法的研究与实现
Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-09-2009
标签:KL变换, 变换编码, 图像压缩, 数据压缩, 算法
0
摘要 I
ABSTRACT II
第一章 绪论 1
1.1研究背景 1
1.2 研究意义 1
1.3 研究内容 2
第二章 图像压缩技术现状 3
2.1 图像压缩的理论基础 3
2.1.1 图像压缩的意义 3
2.1.2 图像压缩的方法评价 3
2.1.3 图像压缩的可能性 4
2.2 图像压缩技术分类 4
2.2.1无损压缩 4
2.2.2 有损压缩 5
2.3 图像编码标准 6
2.3.1 二值图像压缩标准G3和G4 6
2.3.2 JPEG(Joint Picture Expert Group)标准和JPEG2000标准 6
2.3.3 视频图像编码标准H.261和H.263 7
2.3.4 运动图像压缩标准MPEG系列 7
2.4 本章小结 8
第三章 变换编码与KL变换 9
3.1 变换编码与图像压缩 9
3.1.1正交变换与消除相关性 9
3.1.2 图像数据压缩和变换编码 10
3.1.3 变换编码的数理概念 11
3.2 KL变换基础 11
3.2.1 KL变换的概念 11
3.2.2 KL变换的性质 12
3.2.3 KL变换的应用 13
3.3 各种变换编码的性能比较 14
3.4 本章小结 15
第四章 基于KL变换的图像压缩算法研究 16
4.1 基于KL变换的图像压缩基本思想 16
4.1.1图像的KL变换 16
4.1.2 KL变换用于图像数据压缩 17
4.2 基于KL变换的图像压缩基本算法 18
4.3 基于KL变换的图像压缩的改进算法 19
4.4 本章小结 19
第五章 基于KL变换的图像压缩的软件实现 20
5.1 开发程序与环境 20
5.2 功能描述 20
5.3 模块设计 20
5.4 程序流程图 24
5.5 实验结果 26
5.5.1 实际实验 26
5.5.2 实验结果分析 28
第六章 总结与展望 30
6.1 工作总结 30
6.2 未来研究方向 30
参考文献 31
致谢 32
摘要
KL变换是一种建立在图像统计特性基础上的重要的正交变换,在许多方面尤其是图像识别上得到了广泛的应用。由于其可以去掉图像相关性的特性而在图像压缩上也得到应用。
在计算机科学里,数据压缩是通过使用特定的编码方案编码信息,比解码后的表示法使用更少的比特数(或其他的信息单位)的处理过程。需要压缩的数据主要是多媒体,比如音频,视频,图像等。对数据压缩人们目前已经提出了多种多样的理论与技术。变换编码压缩是其中经常应用的一类,KL变换是其中的失真最小的一种最佳变换。对于不同的数据类型,有不同的压缩方法。而课题研究的KL变换用于数据压缩时,主要是用于图像压缩,因此论文讨论的是KL变换用于图像压缩。
本文主要介绍了KL变换的概念及应用,图像压缩的基本原理与技术,相关的国际标准,KL变换用于图像压缩的原理,研究了其算法,并做了具体的实现等。证实了其在图像压缩方面的应用的可行性。
关键词:图像压缩,变换编码,KL变换,算法
ABSTRACT
The Karhunen-Loeve transform(KLT) is a kind of important orthogonal transformation,it has been widely applied in many respects particularly image recognition. Because of its characteristic of removing the image correlation,it also been used in image compression.
In computer science,data compression is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.The data need to be compressed mainly is multimedia,such as audio,video and image.Now people has made a wide variety of theories and techniques to Data compression. Transform Coding compression is an often used method,and the KL transform is a best transformation has smallest Distortion. Regarding the different data type, has the different compression method.The study of the subject–KL transform,is mainly used in image compression when it’s been used in data compression,so what the paper discussed is KL transform used in image compression.
This paper mainly introduced the concept and application of the KL transform, basic principle and technology of image compression, international standard relevanted,the principle of the KL transform used in image compression. Has studied its algorithm and the concrete realization,approved its feasibility in the image compression aspect.
KEY WORDS: image compression,transform coding,KL transform, algorithm
第一章 绪论
1.1研究背景
1950年以来,新技术革命――信息技术的应用使人类社会生产力的发展一日千里。随之而来的巨大数据量需要处理。可以说,人类正处在信息爆炸的时代,每时每刻产生的数据需要传输、存储。然而,不经压缩的信息其所需要的数据空间是极其巨大的。尤其是在多媒体信息渗透了人类生活方方面面的今天,声音,图像,视频需要巨大的传输带宽与存储空间。例如,一幅512*512像素,每分量8bit的彩色图像占768KB,而一幅2230*2230*8bit的气象卫星云图就占4.74MB了。再如,数字电话取样率最低,按每一取样用8位压扩量化,其数码率已达到64kb/s;而一路高清晰度电视(HDTV)数码率高达1280*720*60*3*8=1327Mb/s!可以看出,若不对这些数据进行压缩,其传输或存储很难实用化。因此,人们提出了各种各样的数据压缩理论与方法。
数据压缩就是以最少的数码表示信源所发出的信息,减少容纳给定消息集合或数据采样集合的信号空间。其中一种理论是,数据的冗余度有时与不同的表示方法有关。可以将原始数据变换到另一个更为紧凑的表示空间,从而实现数据压缩。也就是所谓变换编码压缩。其基本原理是,用映射变换把原始信号中的各个样值从一个域变换到另一个域,然后针对变换后的数据再进行量化(二次量化)与编码操作。接收端首先对收到到信号进行解码和反量化,然后再进行反变换以恢复原来信号(在一定保真度下)。映射变换的关键在于能产生一系列更加有效的系数,对这些系数进行编码的总比特数,要比对原始数据直接编码所需的总比特数少的多,使数据率得以降低[1]。其中一种重要方法就是KL变换。KL变换是在均方误差准则下,失真最小的一种变换。KLT便于失真和码率的控制。在早期的编码实践中,用KL变换压缩在13.5kb/s下得到到的语音质量,可与56kb/s的PCM相比拟;在2bit/pel编码下的图像质量,可与7bit/pel的PCM相当。由此可见,研究KL变换编码压缩是有一定的意义的。不过KL变换需要先知道信源的协方差矩阵并求出特征值。但求特征值与特征向量并非易事,维数较高时甚至求不出来。即使能借助于计算机求解,也很难满足实时处理的要求,因此KLT在工程实践中还不能广泛使用[1]。
1.2 研究意义
作为毕业设计研究内容,基于KL变换编码的数据压缩研究可以加深对变换编码压缩的理解,增强工程实践能力。并对数据压缩尤其是图像压缩有切身体会。另外,KL变换主要用于图像处理领域,这也是值得研究的一个方向。
KL变换虽然实际工程中应用较少,但KL变换常用来评价其他变换的性能,因此其具体实现也有研究的必要。KL变换目前无快速算法,能找到一个相对高效的算法也是本课题的研究意义之一。
1.3 研究内容
KL变换(Karhunen-Loeve transform),也称Hotelling变换,特征向量变换或主分量变换。一个随机向量中各元素间往往存在某些相关性,1933年霍特林(Hotelling)提出了一个可以去掉其相关性的线性变换,并把它称为“主分量分析法”,所以此变换又称Hotelling变换。此后Karhunen和Loeve提出了一种针对连续信号的类似的变换,并派生出它的离散变换方法。故这个方法就称为Karhunen-Loeve transform――KL变换。
本课题将研究KL变换的概念,KL变换的应用,比较各种变换编码的性能,研究KL变换用于图像压缩的理论基础及基本算法,利用KL变换实现一个基本的图像压缩程序。讨论其改进算法。
第一章主要介绍了课题研究的背景。第二章则讨论了图像压缩的基本理论,技术分类等。第三章介绍了变换编码技术,KL变换的理论基础与应用。第四章研究了KL变换用于图像压缩的理论与算法。第五章则讨论了基于KL变换的图像压缩的具体实现。第六章给出全文的结论与总结。
第二章 图像压缩技术现状
2.1 图像压缩的理论基础
2.1.1 图像压缩的意义
图像是信息传递的重要媒介,图像的应用在不断扩大:遥感图像、数字图书馆、Internet上的大量图像、视频,如电视会议、数字电视、IPTV等等。然而,图像的数据量通常很大,对存储、处理和传输带来许多问题。比如,图象采样后,如果对之进行简单的8bit量化和PCM编码,其数据量是巨大的。以CIF(Common Intermediate Format)格式的彩色视频信号为例,若采样速率为25帧/秒,采样样点的Y、U、V分量均为8bit量化,则一秒钟的数据量为:
352×288×3×8×25=60.83Mbit
要传输或存储这样大的数据量是非常困难的,必需对其进行压缩编码,在满足实际需要的前提下,尽量减少要传输或存储的数据量。
在这种情况下,必须对图像进行合适的压缩以满足实际使用的要求。
2.1.2 图像压缩的方法评价
1.编码效率:包括图象压缩比(CR)、每像素所用的比特数(bpp)、每秒所需的传输比特数(bps)等。
2.重建图象质量,包括客观度量和主观度量。
客观度量:即图象的逼真度,可考虑为原图像与重建图像的差值。令波形解码器的输入波形为X,解码器的输出波形为Y,则较为常用的两个参数为:
均方误差: (2.1)
峰值信噪比: (2.2)
主观度量:即通过人们的主观测试来评价系统的质量,包括二元判决(即“接受”和“不可接受”)、主观PSNR、平均判分、等偏爱度曲线、多维积分(MDS)等。
3.算法的运算量和硬件实现的复杂程度;
4.算法的适用范围;
5.算法的抗信道噪声干扰能力等。
2.1.3 图像压缩的可能性
图像存在三种基本的数据冗余:编码冗余、像素间冗余、心理视觉冗余。如果能减少或消除上述三种冗余的1种或多种冗余,就能取得数据压缩的效果。
编码冗余:如果一个图像的灰度级编码,使用了多于实际需要的编码符号,就称该图像包含了编码冗余。
像素间冗余:1. 反映图像中像素之间的相互关系。2. 因为任何给定像素的值可以根据与这个像素相邻的像素进行预测,所以单个像素携带的信息相对较少。3. 对于一幅图像,很多单个像素对视觉的贡献是冗余的。它的值可以通过与它相邻的像素值为基础进行预测。
心理视觉冗余:1. 人眼感觉到的图像区域亮度不仅取决于该区域的反射光,例如根据马赫带效应,在灰度值为常数的区域也能感觉到灰度值的变化。2. 这是由于眼睛对所有视觉信息感受的灵敏度不同。在正常视觉处理过程中各种信息的相对重要程度不同。3. 有些信息在通常的视觉过程中与另外一些信息相比并不那么重要,这些信息被认为是心理视觉冗余的,去除这些信息并不会明显降低图像质量。4. 由于消除心理视觉冗余数据会导致一定量信息的丢失,所以这一过程通常称为量化。5. 心理视冗余压缩是不可恢复的,量化的结果导致了数据有损压缩。
2.2 图像压缩技术分类
这里主要讨论的是静态图像压缩。可以分为两类:无损压缩(Lossless Compression)与有损压缩(Lossy Compression)。
2.2.1无损压缩
无损压缩主要基于减少像素间冗余,减少编码冗余的思想。主要分类与技术如下:
一 变长编码
这是一种减少编码冗余的方法。
1. Huffman编码
将需要考虑的符号概率排序,并将最低概率的符号联结为一个单一符号。对每个化简后的信源进行编码,从最小的信源开始,一直编码到原始的信源。解码通过查询表的方式完成。问题:当对大量符号进行编码,构造霍夫曼编码比较复杂;对J个信源符号,需要进行J-2次信源化简和J-2次编码分配。它是一种单义码。
2. 游程编码(RLC)
若沿某一特定方向上的一串m个象素具有相同的灰度值p,则只要传输(p,m)即可。
3. 算术编码(Arithmetic Coding ,AC)
从整个符号序列出发,采用递推形式连续编码;在算术编码中,源符号和码字间的一一对应关系并不存在。1个算术码字要赋给整个信源符号序列,而码字本身确定0和1之间的1个实数区间;随着符号序列中的符号数量增加,用来代表它的区间减小而表达区间的信息单位数量变大。在信源概率分布比较均匀的情况下,它的编码效率高于Huffman编码,而且没有变换编码对数据输入分块的要求。
二 LZW编码
消除像素间冗余。是由Lemple和Ziv最早提出,然后由Welch充实的有专利保护的算法;将原始数据中的重复字符串建立一个字串表,然后用该重复字串在字串表中的索引替代原始数据达到压缩的目的;使用LZW的文件格式包括TIFF,GIF和PDF等。
三 位平面编码
消除像素间冗余。将一幅图像分解为一系列二值图像并通过二值图像压缩方法对每幅二值图像进行压缩;位平面分解的两种方法:二值图像位平面与灰度编码位平面。
四 无损预测编码
基本思想:通过仅提取每个像素中的新信息并对它们编码来消除像素间的冗余;1个像素的新信息定义为该像素的当前值与预测值的差;正是由于像素间有相关性,所以才使预测成为可能。
2.2.2 有损压缩
这里的思想是:牺牲图像复原的准确度以换取压缩能力的增加;如果产生的失真可以容忍,则压缩能力的增加是有效的。
一 有损预测编码
直接对像素在图像空间进行操作。有损预测编码系统;最优预测器;最优量化。
二 变换编码
这是种基于图像变换的编码方法:用可逆的线性变换(如傅里叶变换)将图像映射成1组变换系数,然后将这些系数量化和编码;大多数图像变换得到的系数值都很小,这些系数可以较粗地量化,或忽略不计;虽然失真很小,信息仍然不能完全复原,所以还是有损压缩。
三 分形(fractal)编码
基于自相似性:无论几何尺度怎样变化,物体任何组成部分的形状都以某种方式与整体相似。关键在于引入了局部与全部相关去冗余的思想。压缩效率与物体本身性质有关。
四 矢量量化(vector quantization,VQ)编码
核心思想:利用码书(Code Book)进行信息的传递和存储。编码思路:码书就是一种人为制定的映射,按照一定的准则把n维空间划分为若干子空间,然后把图像各象素的输入值分配到各组中,每组用一个n维矢量来表示。这组矢量和相应的序号构成码书;工作时码书在发送端和接收端各有一本,每输入一个像素数据就根据距离最小原则确定重建矢量,查出相应的序号送出,达到压缩的目的。特点:压缩效率较高;码书的训练非常重要。
五 其他
主要有小波变换编码、基于模型的编码方法(MBA)、人工神经网络方法(ANN)等等。
2.3 图像编码标准
相关的国际组织:ISO(International Standardization Organization,国际标准化组织),ITU(International Telecommunication Union,国际电信联盟),前身是CCITT(国际电话电报咨询委员会)。相关工作:覆盖了从二值到灰度(彩色)值的静止和运动图像;采用的大部分基本技术前面已经介绍,主要包括预测和变换编码技术。
2.3.1 二值图像压缩标准G3和G4
这2个标准是由CCITT的两个小组(Group 3和Group 4)负责制定的,最初是为传真应用而设计的,现也用于其它方面。G3采用了非自适应、1维行程编码技术。对每组N行(N=4或N=2)扫描线中的后N-1行也可以用2维方式编码。G4是G3的1种简化版本,其中只使用2维编码。
在制定标准期间曾选择了1组共8幅具有一定代表性的“试验”图用来评判各种压缩方法。它们既包括打印的文字,也包括用几种语言手写的文字,另外还有少量的线绘图,G3对它们的压缩率约为15:1,G4的压缩率一般比G3高1倍。
2.3.2 JPEG(Joint Picture Expert Group)标准和JPEG2000标准
ISO和CCITT于1986年底成立了“联合图片专家组”,(Joint Photographic Experts Group,简称JPEG),致力于研究静止图像压缩算法的国际标准。定义了3种编码系统:1. 基于DCT的有损编码基本系统,可用于绝大多数压缩应用场合;2. 用于高压缩比、高精确度或渐进重建应用的扩展编码系统;3. 用于无失真应用场合的无损系统。
JPEG并没有规定文件格式、图像分辨率或所用彩色空间模型,这样它就有可能使用于不同应用场合,JPEG对录像机质量的静止图像的压缩率一般可达到25:1。
2000年完成的JPEG2000标准是JPEG的更新换代,它基于小波变换。特点如下:
1. 卓越的低码率压缩效率。传统的JPEG使用DCT,需将图像分块,限制了图像的压缩倍数;而小波是基于整幅图像处理,可实现高压缩比,避免了“分块”效应;
2. 嵌入式编码:在解码端无论获得多少码流,都能在当前码率下最优地将图像重建;
3. 引入“视觉权重”概念。根据视觉特性模型,对小波系数进行调整;
4. 实现“区域”编码策略,即对图像中感兴趣的部分进行单独的编、解码,而无需将整幅图像完全重建出来;
5. 开放性结构,可随时加入新的有效的算法模块。
2.3.3 视频图像编码标准H.261和H.263
一 H.261
1984年12月,CCITT第15研究组成立了“可视电话编码专家组”,并在1988年提出了视频编码器的H.261建议。主要应用对象是视频会议的图像传输。
H.261建议的原理结构的要点是:采用运动补偿进行帧间预测,以利用图像在时域的相关性;对帧间预测误差以8*8或16*16为宏块,进行DCT变换,以利用图像在空域上的相关性;接着对DCT变换系数设置自适应量化器,以利用人们的视觉特性;再采用Huffman熵编码,获得压缩码流。
二 H.263
H.263是一种低码率的视频编码标准,码率可达H.261的一半,是对H.261标准的很好的改进。它仍然以MC/DCT为核心算法,与H.261不同的是,它采用半像素精度进行运动补偿,传送的符号采用变长编码。除了这些基本编码算法外,H.263还包括下面四个可选的编码方法。所有这些算法可以通过某种组合使用,也可以单独使用。
1.无约束运动矢量模式;2. 基于句法的算术编码模式;3. 先进预测模式;4.PB帧模式。
2.3.4 运动图像压缩标准MPEG系列
为适应有声音的运动图像压缩的需要,1988年5月,CCITT和ISO成立了“运动图像专家组”(Motion Picture Experts Group),致力于有关运动图像的编码标准。MPEG对运动图像的帧内编码技术中采用了JPEG推荐的DCT技术,此外MPEG又引入了帧间MC技术,因此可认为MPEG的工作是JPEG的延续,同时尽量与H.261标准兼容,但比H.261要复杂的多。MPEG标准包括MPEG视频、MPEG音频和MPEG系统三个部分。它采用了MC、DCT、可变长编码(VLC)等多种技术。
MPEG-1标准于1993年8月正式通过,用于对连续传送码率为1.5Mbits/s存储和传输媒体进行操作,CD、硬盘和光盘驱动器;
MPEG-2标准于1994年编译出版,其码率在3~10Mbits/s之间,应用范围更加广泛,如数字电视、数字通信、其他数字媒体等。
MPEG-4与前面提到的JPEG、MPEG-1、MPEG-2有很大的不同,它为多媒体数据压缩编码提供了更为广阔的平台,它定义的是一种格式、一种框架,而不是具体的算法。MPEG的目标为:支持多种多媒体的应用,特别是多媒体信息基于内容的检索和访问,可根据不同的应用需求,现场配置解码器。编码系统也是开放的,可随时加入新的高效的算法模块。
MPEG-7将确定各种类型的多媒体信息的标准描述方法。可应用于数字图书馆、各种多媒体目录服务、广播媒体的选择,以及多媒体编辑等领域。
2.4 本章小结
本章介绍了图像压缩的必要性,压缩的评判指标,图像压缩的可能性,基本原理与技术分类,以及相关的国际标准。
可以看出,图像的压缩有多种方法,并已经形成了一些国际标准,但发展新的技术还是必要的,因为数据增长的速度极快,现有的方法也远非完美。对于将要研究的变换编码压缩,KL变换,将在下一章详细介绍。
第三章 变换编码与KL变换
3.1 变换编码与图像压缩
3.1.1正交变换与消除相关性
用统计学方法描述图像,各分量之间的相关性将会大大增加图像生成和图像处理过程中的误差,有效消除这些相关性是一个基本的任务。也就是说,我们应该设法将协方差矩阵的非对称元素化为零元素,就是设法将协方差矩阵对角化[2]。
线性代数证明,对于一个实对称矩阵Σ(Σ=ΣT),必存在一个正交矩阵Q,使得
(3.1)
其中对角矩阵Λ中的λ1,λ2,…λN是实对角矩阵Σ的N个特征根。这给我们一个重要启示:
通过正交变换能够将协方差矩阵(实对称矩阵)Σ对角化,从而消除图像的相关性。
通过正交矩阵T对向量X 作正交变换Y =TX
证: Y的协方差矩阵定义为:
,
那么Y的协方差矩阵ΣY为:
(3.2)
其中T为正交矩阵;ΣX为实对称矩阵。表明:
向量X通过正交变换后的向量Y的协方差矩阵为λ的对角矩阵,说明向量X的分量间的相关性已被消除,即正交变换能消除存在相关性的冗余度,这是采用正交变换消除图像相关性的一个数学依据[3]。
3.1.2 图像数据压缩和变换编码
这里的变换编码主要指正交变换。基本思想:将空间域里表述的图像经过某种正交函数变换,转换为能量比较集中的变换域中,然后对变换系数进行编码,从而达到缩减比特率的目的。
变换编码之所以能够压缩信息的比特数,是因为经过正交变换得到的系数矩阵中,数值较大的方差总是集中在少数系数中。多数图像的统计特性表明,大幅度的系数往往集中在低频率区内,这样,可以给那些较小的系数分配很少的比特数,甚至可以不予传送,从而压缩了传送数据的比特数。因此,正交变换本身只是把分布在变换域中的信息变得集中起来,为合理少分配给某些数据比特数提供了可能[4]。
变换编码工作流程:
图3.1 变换编码工作流程
变换编码过程主要有两个阶段:变换和量化。经过变换处理,将原始数据从一个空间变换到另一个空间,使图像中相邻像素、相邻扫描行间的数据的相关性变小,同时使图像数据在变换域中相对较为集中,以有利于进行下一步的量化 在进行量化之后,便进一步达到了数据压缩的目的。
3.1.3 变换编码的数理概念
假如变换矩阵是归一化正交变换矩阵,经过变换之后,空间域中的总能量在变换域中得到保持,即满足:
(3.3)
式中f2(m,n)为空间域矩阵中元素,F2(i,j)为变换域矩阵中元素。上式是离散正交变换中的Parseval能量保持定理。其意义在于:空间域中能量全部转移到变换域中,而在反变换中,变换中的能量又能全部转换到空间域中。但是,在变换过程中,保持不变的能量会重新分布。在空间域中,能量的分布有一定的随机性,对于相关图像来说,在大多数情况下,变换域中能量集中于零空间频率或低空间频率对应的变换系数上。
这样,经过变换之后,使图像的相关性减少,在新的变换域中,经过选择适当的量化方法,便可以达到压缩数据的目的。
3.2 KL变换基础
KL变换是一种基于特征向量(Eigenvectors)的离散正交变换[2]。
3.2.1 KL变换的概念
一 特征值(Eigenvalues)
对N*N的矩阵A,有N个标量 , =1,2,…,N,能使
, (3.4)
则称 为矩阵A的特征值;
:单位矩阵
特征值:当矩阵的每个对角元素都减去它时,将变成奇异阵(不存在逆的矩阵)。如果给定矩阵是奇异的,那么N个特征值中至少有一个是0。
二 特征向量(Eigenvectors)
设每个 是N*1维的,通过满足
(3.5)
对应一个特征值 ,则称其为A的特征向量。N个这样的特征向量构成一个正交基集。
如果A是实对称矩阵,那么 也是实数。
三 一维KL变换
定义一个线性变换A,它可由任何X向量产生一个新向量Y:
, (3.6)
这里 为由L个样本向量估计的均值向量。这就是KL变换的变换式。理解:变换后的图像是由中心化向量 与变换矩阵A相乘。
A的构成法:由 的特征向量 , =1,2,…N构成A的行向量,按相应特征值 幅值大小的顺序排列各行:即取A的第一行为对应最大特征值的特征向量,A的最后一行为对应最小特征值的特向量。
3.2.2 KL变换的性质
1.Y的均值 。即变换后的图像向量是期望值为零的随机向量。
2.Y向量的协方差矩阵为 。
3. 协方差矩阵 是对角型矩阵。
, (3.7)
为对角矩阵,特征值即沿着特征向量 方向上Y的第i个元素的方差。
上式主对角线上以外的元素为0,即y向量的各元素是不相关的,也就是说,随机向量Y是由互不相关的随机变量组成的。因此,线性变换A起到了消除变量间相关性的作用。即每个 都是变换后第i个变量 的方差。
4. 能量集中特性
这里所指的能量集中特性是对n 维矢量信号进行K-L 变换后,最大的方差将集中在前m个分量之中的这样一种特性(m < n)。
3.2.3 KL变换的应用
自KL变换提出以来,学者们对其应用做了一些有益的探索。清华大学的研究人员提出了Karhunen—Loeve变换在语音识别中的应用。特征提取与选择是语音识别中一个非常重要的环节。好的特征,既可以具有很高的模式区分能力,又可以节省大量的存储空间,起到很好的数据压缩作用。目前在语音识别中主要采用基于线性预测分析 (LPC)技术得到的倒谱系数或基于 Mel-Scale的 MFcc系数 (Mel频率刻度倒谱系数),然后辅之以能量和过零率等其它特征参数。而他们提出在特征提取阶段利用帧间相关性的一种方法.对每一帧考虑其前后各n帧,加上自身帧共 2n+l帧的特征矢量串起来组合成—个大的特征矢量串。对这个大的特征矢量串用Karhunen-Loeve变换进行降维处理.将变换后的数据作为本帧的特征矢量用于后续的训练和识别。在基于 CDCPM的语音识别系统中采用这种方法进行了音节的训练和识别。实验结果表明Karhunen-Loeve变换在考虑帧间相关性的特征提取阶段上表现了良好的效果,有着很广阔的应用前景[5]。中国科学院长春光学精密机械研究所的学者则提出了一种基于KL变换的三维谱象数据压缩方法。该方法将原始谱象分成若干子块,对每一子块使用去相关性效果最佳的KL变换,去除谱象数据空间相关性。实验结果表明, 经KL变换后,若不编码, 可获得3~5倍的准无损压缩。经JPEG编码后, 压缩比可达100倍以上。且峰值信噪比大于34.0dB[6]。美国的Gabriel Fernandez,Craig M.Wittenbrink也把基于幅度的KL变换用于多光谱图像压缩,他们在更好的压缩率下得到了比典型KL变换更小的失真[7]。
中南林学院的陈爱斌提出了一种基于KL变换的汽车车型的识别方法。先对车辆图像进行预处理,然后通过KL变换构造特征车,将样本投影到特征车子空间,得到的投影系数即为待识别车型的代数特征。最后利用 K近邻法进行车型识别。实验结果表明了文中提出的车辆识别方法是简便、快捷、有效的[8]。
KL(Karhunen—Loeve)变换是一种二维酉变换。理论上,二维酉变换在图像处理中有3种主要功能:第一,从图像中提取特征;第二,图像变换编码;第三,减少计算维数。这些功能在数字图像处理和遥感多图像变换组合分析中得到了成功的应用。KL变换是遥感图像增强和信息提取中用得最多的线性变换,是对原波段图像进行波谱信息的线性投影变换,在尽可能不减少信息量的前提下,将原图像的高维多光谱空间的像元亮度值投影到新的低维空间,减少特征空间维数,达到数据压缩、提高信噪比、提取相关信息、降维处理和提取原图像特征信息的目的,并能有效地提取影像信息。它可使原来多波段图像经变换后提供出一组不相关的图像变量,最前面的主分量具有较大的方差,包含了原始影像 的主要信息,所以要集中表达信息,突出图像的某些细部特征,可采用主分量变换来完成。KL变换的最大优点是去相关性好,可用于数据压缩和图像旋转[9]。KL变换最复杂,时间,空间开销大,变换域中能力最集中,集中到少数几个变换系数上,编码效率最高,误差最小。 K-L 不具有二维分离特性,离散余弦变换性能与其相似。KL变换的缺点是计算过程复杂,变换速度慢。无快速算法而难以实现。但其具有最佳性能。因此,KL变换常常作为其他变换性能的评价标准。
目前,KL变换主要还是用于图像特征处理,比如指纹的识别,遥感图像的提取等。尽管本课题研究的是其用于数据压缩,但实际工程中通常不采用该方法。
3.3 各种变换编码的性能比较
对各种变换编码技术已有了初步的比较[4]:
1. 离散傅立叶变换(DFT)
离散傅立叶变换不对图像本身编码,只对变换系数进行编码和传输,具有蝶型快速算法,但其运算量大,实际使用有问题。
2. 沃尔什-哈达玛变换(WHT)
可取代DFT,使运算量明显降低,这是因为WHT具有DFT的快速算法结构,且只有加减法运算而无乘法。但实践证明经WHT变换后,能量集中程度不如DFT。
3.哈尔变换(HRT)
具有比WHT更快的运算速度,但其能量集中程度WHT更差。
4. 离散余弦变换(DCT)
运算速度较快(有快速算法),而且经DCT后能量集中性仅次于KLT,对于大多数相关性很强的图像数据,DCT是KLT目前最好的替代。
5. KL变换
能量集中性最好。
6. 斜变换(SLT)
奇异值分解最佳坐标展开变换(SVD)。
按变换后数据的可压缩性,在变换域中信源能量集中程度排序(从优至劣):
KLT-DCT-SLT-DFT-WHT-HRT
按算法的简单复杂程度排序(由简至繁):
HRT-WHT-SLT-DCT-DFT-KLT
按变换运算量大小排序(由小至大):
HRT-WHT-SLT-DCT-DFT-KLT
3.4 本章小结
本章介绍了变换编码用于图像压缩的基本原理,工作流程,KL变换的概念,性质与应用。最后还对各种变换编码技术做了简单的比较。这样,为下面引入基于KL变换的图像压缩做了技术上的铺垫。
可以看出,变换编码技术是相当有效的图像压缩方法,其中KL变换实现图像压缩较为困难,往往用于图像识别等其他领域,但为了利用其对其他变换作出评判,研究其用于图像压缩也有一定意义。
第四章 基于KL变换的图像压缩算法研究
4.1 基于KL变换的图像压缩基本思想
4.1.1图像的KL变换
假定一幅图像N*N的数字图像通过某一信号通道传输了 M 次,由于受随机噪声干扰和环境条件影响,接受到的图像实际上是一个受噪声干扰的数字图像集合
,
对第i次获得的图像 ,可用一个含N2个元素的向量Xi表示,即
, (4.1)
该向量的第一组分量(N个元素)由图像 的第一行像素(N个)组成,接下来是第二行像素组成向量的第二组分量,余类推。亦可按列的方式形成这种向量。
同样,对于M幅数字图像,平均值 和协方差矩阵 可由下面方法求得:
, (4.2)
是 个元素的向量
, (4.3)
的方阵。
假定 是按递减顺序排列的特征值,即 ,对应特征向量为
, (4.4)
定义KL变换矩阵A为
, (4.5)
可得KL变换的变换表达式
, (4.6)
理解为:由中心化图像向量 与变换矩阵A相乘,可得变换后的图像Y。由于协方差矩阵ΣX是实对称矩阵,由线性代数理论知, ,故由KL变换式 可得KL反变换式
(4.7)
4.1.2 KL变换用于图像数据压缩
如前所述,KL变换矩阵A是由特征向量组成的变换矩阵,而且这些特征向量的排列是按特征值递减顺序排列的。由于能量集中在特征值λ大的系数中,因此我们丢掉特征值小的Y系数,不应影响图像质量。
设我们取λ最大的前K个特征向量组成的变换核矩阵,记做Ak,有
(4.8)
这相当于原Y的K维投影,记做Y’。在反变换重建图像向量X时,可采用补零方法。仍补成N*N维向量
, (4.9)
这显然会带来误差。所重建的图像只能叫原X的估计值 :
(4.10)
总之,由于我们只丢掉较小的Y系数,故引入较小的误差。可以证明[10],引入的误差为:
(4.11)
其中λi为协方差ΣX的特征值。因为λi是按大小顺序排列的,因而k+1至N2的λi是非常小的。而且,λi之间数值差异非常之大。这样丢掉特征值小的基向量做变换,引起误差的百分数小。另外,因为对于实际图像集合而言,做KL变换必须求得这个集合的N2*N2的协方差矩阵的特征值与特征向量,计算量非常之大。但由于KL 变换矩阵是不可分离的,所以至今还没有找到一种成熟的快速算法,这就限制了使用。
4.2 基于KL变换的图像压缩基本算法
由上面的基本思想,我们可以得出基于KL变换的图像压缩基本算法如下:
一 图像分块
这里一般是把图像分成一系列不重叠的特定尺寸的如8*8的子图像块,然后对每个块,一排排地级联成64×1向量。
二 构建协方差矩阵,求出特征值与特征向量
收集所有这些级联向量构建所需要的协方差矩阵,求出其特征值和相应的特征向量。
三 进行KL变换
对每个子图像块,已经求出了特征值与特征向量。按特征值递减的顺序排列特征向量构建变换矩阵。能量已经集中在特征值大的向量中,此时丢弃特征值小的特征向量,取特征值最大的前K个向量组成的变换核矩阵,进行KL变换。
四 量化编码
这里若需要传输,则需要量化编码。对KL变换后得到的数据量化编码。在KL变换时,丢弃了特征值小的特征向量,因此实现了数据压缩。
五 解码
接收方需要对接收到的数据进行解码。
六 进行KL反变换重构图像
反变换重建图像时,对丢弃的数据补零,仍构成64×1向量。这样可以恢复出近似原图像的图像,实现了压缩。
补充:对于四、五两个步骤,若不需要传输图像可以省略。实际上,四、五两步还可以实现进一步的压缩。比如采取特殊的编码如游程编码,Huffman编码等。
4.3 基于KL变换的图像压缩的改进算法
传统的算法里,Karhunen-Loeve变换(KLT)很难被使用在图像压缩中,原因是由于它们求解从给定的训练数据中构建的协方差矩阵变换很慢[11]。协方差矩阵的规模或维数越大,计算特征向量的速度就越慢,因此变换越慢。然后表现为压缩编码或变换就越慢。为了缓和这个问题,通常采取两种方法。第一种是用离散余弦变换(DCT)代替KL变换就像JPEG标准中那样[12]。尽管能得到比KLT更快的压缩速度,DCT导致了与KLT比起来在相同压缩比率下相对更大的压缩质量降低。第二种方法是使用相似的技术[13][14]比如神经网络包括关联记忆[15]和自适应主要成分提取(APEX)。尽管是一种强大的相似方法,神经网络也必须在压缩速度和质量之间权衡。
而这里的改进算法由南京航空航天大学的Daoqiang Zhang, Songcan Chen两人提出,对传统的KL变换提出以一种新型的矩阵KL变换扩展,对18幅广泛采用的基准图像的实验结果表明,矩阵KL变换在相似的压缩质量下,可以比传统KL变换压缩速度提高数十至上百倍[11]。
主要思想在于减少原始KLT的协方差矩阵规模。直接用一个矩阵型而不是向量型表示法来构建协方差矩阵,称之为推广协方差矩阵(GCM)。因此它的规模要小于那些由级联向量构建的协方差矩阵。拿一个级联成n维向量的图像块为例,KLT的协方差矩阵规模是n*n,而推广协方差矩阵的规模只有m*m,此时它由m*p维矩阵构建,是n维向量的重新排列,这里m*p=n。显然每个规模的降低率达到了p2,当p很大时会是一个令人印象深刻的结果。
矩阵KL变换由两个主要步骤。第一步是“重新装配或重新排列”,该步把一个子图像块向量组件重新排列成一个新的m*p维的矩阵,它直接用子图像块矩阵作为一种特殊情况从而变得更灵活。第二步是把第一步中得到的矩阵表示为矩阵KLT。
最后重建图像。Daoqiang Zhang和Songcan Chen证明了矩阵KL变换同样可以去掉图像的相关性来达到压缩的目的。而且实现的速度较传统KL变换大为提高。
4.4 本章小结
在这一章里讨论了基于KL变换的图像压缩的基本算法。显然,由于KL变换没有快速算法,求特征值、特征向量困难,用其实现图像压缩较为困难,实际中压缩图像也基本不采用KL变换算法。但实现它的现实意义在于其是失真最小的变换,经常需要用它对其他变换做为评判标准。上面提到的改进算法实际上是对KL变换做了改进,但其还不不成熟,尚未得到广泛认可。
第五章 基于KL变换的图像压缩的软件实现
本设计要实现的目标是完成一个基本的基于KL变换的图像压缩程序,这里采用KL变换的基本算法实现。
5.1 开发程序与环境
在本课题中,实现的程序运行于windows系统下(windows 2000/XP等),使用Visual C++开发。Visual C++是Microsft公司推出的一种高度综合性能的开发Win32环境程序,面向对象的可视化集成编程系统。用它开发的程序有着运行速度快、可移植能力强等特点。由于Visual C++本身就是一个图形的开发界面,它提供了丰富的关于位图操作的函数,对开发图像处理系统提供了极大的方便。因此,它现在已经成为开发win32程序,包括图像处理程序的主要开发工具。
5.2 功能描述
在前面已经提到KL变换无快速算法。因此这里设计的功能将比较基础。比如,简单的压缩设置:仅有固定压缩比,固定的图像类型等。
具体功能如下:
一 可以对256*256的灰度bmp图像进行基于KL变换的压缩;
二 可以选择固定的几个压缩比(1:2,1:4,1:8,1:16,1:32,1:64,1:128,1:256);
三 可以在界面中对比显示压缩前与压缩后的图像;
四 自动在被压缩图像所在的文件夹中生成compic压缩文件和重建的bmp图像文件;
五 若打开的图像不是256*256的bmp图像,则会弹出对话框提示。
5.3 模块设计
本程序主要由主界面模块(由Visual C++自动生成),读取图像模块,KL变换模块,量化编码模块,KL反变换模块,图像重建模块,显示模块构成。
图像依次经过各个模块处理,完成压缩过程。
图5.1 程序模块
主界面模块:
由Visual C++系统自动生成。建立程序时,选择MFC AppWizard [exe],名称为KLT,在菜单中添加“选择压缩比”栏,系统即可自动生成主界面如下图:
图5.2 程序界面
建立的这个界面只是一个框架,其本身无任何处理功能。
读取图像模块:
此模块作用仅为实现256*256位图的读取。这里要注意的是,由于简化设计的考虑,设置的是仅对256*256的灰度位图读取。若不符合要求,自动提示。
KL变换模块:
这是比较核心的模块。这里对读入的图像进行主要的运算-KL变换。
具体步骤:对读入图像分块,求协方差矩阵,求特征值、特征向量,用特征向量矩阵与原始图像数据相乘,得到的结果即为变换后数据。
各个函数如下:
Vec = (double*)malloc(PICSIZE*sizeof(double));
buffer = (double**)malloc(PICSIZE*sizeof(double*));
temp = (double**)malloc(PICSIZE*sizeof(double*));
sort(a, v); //将特征值与特征向量按照由大到小的顺序排序
//特征值与特征向量排序
void CKLTDoc::sort(double* a, double* v)
transpose(v); //特征向量矩阵转置
//矩阵转置
void CKLTDoc::transpose(double* array)
Multiply(v, array); //特征向量矩阵与原始图像数据相乘,得到的结果即为变换後数据,保存在array中
函数及部分参数说明:
//求实对称矩阵的特征值及特征向量的雅格比法
//利用雅格比(Jacobi)方法求实对称矩阵的全部特征值及特征向量
//返回值小于0表示超过迭代jt次仍未达到精度要求
//返回值大于0表示正常返回
//a-长度为n*n的数组,存放实对称矩阵,返回时对角线存放n个特征值
//n-矩阵的阶数
//u-长度为n*n的数组,返回特征向量(按列存储)
//eps-控制精度要求
//jt-整型变量,控制最大迭代次数
量化编码模块:
这是实现压缩的部分。在这里按压缩比把KL变换后数据中由特征值小的部分生成的数据丢弃,并把剩余数据写成compic文件,即生成的压缩文件。
代码如下:
//数据压缩
void CKLTDoc::compress(double** array)
{
int tmp = PICSIZE/comRate;
int i, j;
for(i = tmp + 1; i < PICSIZE; i++)
{
for(j = 0; j < PICSIZE; j++)
{
array[i][j]=0;
}
}
//将压缩後的数据写文件
FILE* fp;
fp = fopen(“compic”, “wb”);
for(i = 0; i < tmp + 1; i++)
{
for(j = 0; j < PICSIZE; j++)
{
unsigned char tempdata = (Byte)array[i][j];
fwrite(&tempdata,sizeof(tempdata),1,fp);
}
}
fclose(fp);
}
KL反变换模块:
把丢弃的数据补零,然后把与前面KL变换后生成的数据一起做KL反变换。反变换是重建的基础。
代码如下:
void CKLTDoc::IKLT(double* a, double* v, double** buffer)
{
transpose(v);
Multiply(v, buffer);
}
图像重建模块:
重建bmp图像。因为这里补的是零,所以肯定带来了误差。所以重建图像是不可能与原图一致的。这也就是有损压缩。
实现代码:
//将KLT反变换后的数据写成一个bmp文件
FILE* fp = fopen(“stuff.bmp”, “wb”);
fwrite(&MyBmp,sizeof(MyBmp),sizeof(unsigned char),fp);
fclose(fp);
for(i=0;i
for(j=0;j
MyBmp.Pix[i][j]=ppbImage[i][j];
}
}
显示模块:
把原图像和重建图像显示在界面中,效果如下(这里压缩率为1:16):
图5.3 显示效果
5.4 程序流程图
一 主程序流程图
图5.5 主程序流程图
二 KL变换模块实现过程图
这里是该模块的实现过程图,并没有对其中每个函数写出具体的流程。比如,图像分块、求协方差矩阵、求特征值与特征向量都是比较复杂的运算过程。这里仅指出该步骤。
图5.6 KL模块实现过程
5.5 实验结果
5.5.1 实际实验
实验环境为Windows XP 系统,Athlon 3000+的处理器,512M的内存。
这里将展示基于KL变换的图像数据压缩程序的实际效果。所用测试图片为“lena”,它是18幅广泛使用的基准测试图像之一。
首先,打开程序后选择压缩比(这里压缩比例的含义代表压缩后图像大小与原图像大小之比),若不设置,则默认为1:8。选择“操作”,在“压缩比例”中选择压缩比,如下图所示:
图5.7 设置压缩比
确定后打开图像,这里的图像必须是256*256的灰度bmp图像,否则,弹出警告对话框如下:
图 5.8 提示对话框
下面是实际效果。
一 压缩比为1:2。此时原图与压缩后的图片效果如下:
图5.9 1:2压缩对比
原图大小为65.0KB,形成的压缩文件compic为32.2KB。
可以看出质量很好,重建图像仅有少量失真。但必须提到的是,执行速度较慢。
二 压缩比为1:4
此时压缩比提高了一倍,下面是结果。
图5.10 1:4压缩对比
此时形成的压缩文件compic为16.2KB。
可以看出,重建图像失真明显比压缩比为1:2时大。
三 设置压缩比为1:16
再次提高了两倍压缩比,结果如下:
图5.11 1:16压缩对比
此时形成的压缩文件compic为4.25KB。
此时的重建图像已经基本不能接受。
其他压缩比不需再一一列举,总之,compic文件的大小体现了压缩程度,而且压缩比越大恢复图像效果越差也是在意料之中。
实际压缩时,由于KL变换无快速算法,程序运行时间较长。这也是KL变换在实际压缩中得不到采用的原因。
5.5.2 实验结果分析
程序基本实现了预计的功能:可以对符合要求的图像进行指定压缩比的压缩,形成压缩文件,可以重建图像。
不足:由于KL变换实现较为复杂,故这里为了简化设计起见设计为只能对256*256的灰度bmp图像进行压缩。压缩进度不能实时显示。不能设置任意压缩比,只有固定的压缩比。若要改进程序,可以在以上几个方面着手。
方法评价:图像在1:2压缩比时,重建质量比较令人满意,在主观度量上,可以达到“良好”,1:4时则只能说“可用”,更高压缩比时只能达到“刚可看”及以下了。编码效率方面,在1:4的压缩比时,重建图像还可以达到“可用”,可以看出效率比较高。算法运算量方面,KL变换无快速算法,运算量很大,程序运行时,要等待的时间较长。
因此,基于KL变换的压缩往往不能用于实际工程实践中,但其效果在变换编码中属于最佳,可以用于对其他变换方法的评价。
第六章 总结与展望
随着信息社会的发展,图像压缩技术越来越重要。包括变换编码压缩在内的各种技术也在不断发展。下面给出本研究课题的结论。
6.1 工作总结
在本文中,探讨了图像压缩的基本技术,评价方法,相关的国际标准,研究了变换编码技术,对其中的基于KL变换的图像压缩做了深入的算法研究与实际实现。通过具体的编程,检验了压缩的效果。可以看出,KL变换在比较高的压缩比下还有相对较好的重建效果。但是,正因为其算法复杂,实现的速度还是很慢的。当选择较大的压缩比时,要等待很长时间。这是其最大的不足,造成了它的不能实用。
尽管在文中提到了其改进算法,但事实上这个算法尚未得到广泛认可,因此还需要进一步的检验。
总之,基于KL变换的图像压缩目前还只能作为其他压缩算法的评判,若想实际应用,必须提出新的高效率改进算法。
6.2 未来研究方向
对于KL变换技术来说,由于其复杂性与实现的困难性,只能找到其他的变换来代替它,这个变换目前是DCT,但未来可以找到更好的变换,这是一个研究方向。但从KL变换本身着手,改进其算法也是一条可行之路,只不过目前看来也相当困难。文中也提到采用相似的技术比如神经网络包括关联记忆和自适应主要成分提取(APEX),从这方面也可以继续研究。
图像压缩技术是不断发展的,相信基于KL变换的压缩技术或有与其效果相似乃至更好的技术一定会出现。
参考文献
[1] 吴乐南.数据压缩[M].北京:电子工业出版社,2000.94,99.
[2] 黄贤武等. 数字图像处理与压缩编码技术[M].成都: 电子科技大学出版社,2000.30-66.
[3] 章毓晋. 图像工程(上) [M].北京:清华大学出版社,1999.43-70.
[4] 刘榴娣,刘明奇,党长民. 实用数字图像处理[M].北京:北京理工大学出版社,2001.62-86.
[5] 郭庆,吴文虎,方棣棠.Karhunen-Loeve变换在语音识别中的应用[J].模式识别与人工智能,1998,11(4),396-402.
[6] 孙辉. 采用KL变换的三维谱象数据压缩方法[N]. 长春邮电学院学报,1999,17(1),5-8,12.
[7] Gabriel Fernandez,Craig M.Wittenbrink. REGION BASED KLT FOR MULTISPECTRAL IMAGE COMPRESSION[Z].
[8] 陈爱斌. 基于KL变换的汽车车型的识别方法[N]. 中南林学院学报,2004,24(2),111-113.
[9] 高守传,姚领田等 Visual C++实践与提高-数字图像处理与工程应用篇[M].北京:中国铁道出版社,2006.202-205.
[10] 容观澳. 计算机图像处理[M]. 北京:清华大学出版社,2000.101-102.
[11] Daoqiang Zhang, Songcan Chen. Fast image compression using matrix KL transform [Z].
[12] R.C.Gonzalez,R.E.Woods,Digital Image Processing,2nd Edition,Prentice Hall,Jan.2002
[13] S.Bhama,H.Singh,N.D.Phadte,”Parallelism for the faster implemention of the K-L transform for image compression”,Pattern Recognition Letters,vol.14,pp.651-659,Aug,1993.
[14] S.Costa,S.Fiori,”Image compression using principal component neural networks”,Image and Vision Computing,Vol.19,pp.649-668,Aug.2001.
[15] C.C.Wang,C.R.Tsai,”Data compression by the recursive algorithm of exponential bidirectional associative memory”,IEEE Trans.Syst.Man.Cybern.
,vol.28,no.4,pp.125-134,Apr.1998.








