Featured Post

新春快乐!

Read More

新春快乐 瑞雪积丰门,闲阳照景深, 又到换岁时,围炉思旧事。 笑斟一杯酒,遥举香可闻。 恭祝您身体健康,永葆快乐心。 鼠年大吉,万事如意!

基于小波变换的数据压缩算法的研究与实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-09-2009

标签:, , ,

0

目录
摘要 III
ABSTRACT IV
第一章 绪论 1
1.1 课题研究的背景 1
1.2 课题研究的任务和目标 1
1.3 内容安排 2
第二章 小波变换图像压缩技术基础 3
2.1 小波变换简介 3
2.2 小波变换基本理论 4
2.2.1 连续小波变换 4
2.2.2 离散小波变换 7
2.3 多分辨率分析 12
2.4 几种常见的小波 13
2.5 小波变换与图像压缩 15
2.6 从能量角度看小波变换 16
第三章 基于小波变换的图像压缩算法的研究 18
3.1 几种小波图像压缩算法的介绍 18
3.1.1 几种小波图像压缩算法的介绍 18
3.1.2 关于JPEG2000 20
3.2 各种小波图像压缩算法的共性 20
3.3 对各种小波压缩算法的比较及本课题所选方案 21
3.3.1 对各种小波压缩算法的比较 21
3.3.2 本课题所选方案 21
3.4 所选方案的实现 21
3.4.1 EZW算法概述 21
3.4.2 零树的构造 22
3.4.3 扫描方法 23
3.4.4 EZW算法的实现 23
3.5 EZW算法举例 24
3.5.1 树结构 24
3.5.2 编码 25
3.5.3 解码过程 27
3.6 关于编码 28
第四章 基于小波变换的图像压缩算法的软件实现 29
4.1 软件总体功能设计 29
4.2 软件各个模块的实现 30
4.3 软件应用举例 35
4.4 软件评价 37
4.5 本软件系统的优点和不足 38
4.6 值得改进的地方 38
第五章 总结 39
5.1 所做工作的总结 39
5.2展望 39
参考文献 41
致谢 43
附录 44

摘要
信息时代的到来使人们极易获得大量的信息,数字图像就是一种重要的信息载体。如何存储和传输这些图像一直是人们关注的焦点,对此,人们也提出了许多方法和制定了许多标准。小波变换作为一门较新的数学分支,被引入图像处理以后,很快引起了人们的极大兴趣。随着研究的开展,相继出现了许多基于小波变换的图像压缩方式,如嵌入式零树算法(EZW,the Embedded Zerotree Wavelet algorithm )、分层树集合分割算法(SPIHT,Set Partitioning In Hierarchical Trees)、最佳截断嵌入码块算法 ( EBCOT ,Embedded Block Coding with Optimized Truncation)等等,在此基础上,人们还制定了基于小波变换的国际化图像压缩标准JPEG2000。
本文首先介绍了小波变换理论的发展情况和一些基本的小波理论,然后又介绍了几种基于小波变换的图像压缩技术并对它们做了简单的比较,紧接着重点论述了EZW算法的原理和实现,这也是本文的重点。最后,实现了基于EZW算法的一个软件系统。

关键词: 图像压缩,小波,离散小波变换,EZW算法

ABSTRACT
People can easily obtain a large amount of information with the arrival of the information age, digital image is an important information carrier. How to store and transmit these digital images has been the focus of people’s attention, thus, many methods were proposed and a number of standards were shaped. As a relatively new branch of mathematics, wavelet transform has been introduced into image processing, and quickly caught the great interest. Following this study, many image compression methods which based on wavelet transform have been launched, for example, the Embedded Zerotree Wavelet algorithm (EZW), Set Partitioning In Hierarchical Trees (SPIHT), Embedded Block Coding with Optimized Truncation (EBCOT), and so on. On these basses, it has developed international image compression standard JPEG2000 based on wavelet transform.
Firstly, this paper introduces the basic wavelet transform theory and the development of the wavelet theory, then introduces several image compression technology based on wavelet transform , compares them Simply, and treatises the EZW algorithm and its implementation, which is the focus of this paper. Finally, it’s realized a software system based on the EZW algorithm.
KEY WORDS: Image compressing, Wavelets, Discrete Wavelet Transform, EZW algorithm

第一章 绪论
1.1 课题研究的背景
人类社会已经进入信息时代了。在这个时代,人们每天都可以通过各种手段(如PDA、网络、电视、广播等等)获得大量的信息,而这些信息在我们的日常生活中是不可或缺的。图像信源由于其具有丰富的信息量而成为传递信息地重要媒介。我们日常所获取地信息有百分之七十以上来自于眼睛,可以说数字图像正成为信息高速公路上一种重要的媒体。数据量大是数字图像地一个显著特点,例如,按CCIR601 标准对常规电视信号进行每秒25帧,每帧分辨率为720×576,Y:U:V 为4:2:2 每个分量8bit 的格式进行数字化,则其总数编码率可达166Mb/s[1]。这给数字图像的存储、传输带来了极大的困难,因此必须进行压缩以减少数据量。由于数字图像存在着大量的冗余,故图像数据可以进行压缩处理。数字图像压缩可追溯到上世纪四十年代所提出的线性PCM 编码方法,迄今为止已有六十多年的历史。目前数字图像压缩技术已成为信息高速公路、高清晰电视(HDTV)、可视电话、会议电视、多媒体通信等技术的关键,在航空遥感、生物医学工程等领域也起着重要的作用。
图像数据压缩是指以较少的比特率有损或无损地(指信息)表示原来的象素矩阵的技术,也称图像编码。由于图像数据中通常存在这种信息的冗余,如空间冗余、时间冗余、信息熵冗余、结构冗余、知识冗余和视觉冗余等冗余信息。减少或消除信源的各种冗余度是实际图像数据压缩的基本依据。图像压缩研究的就是寻找高压缩比的方法且压缩后的图像要有合适的信噪比,在压缩传输后恢复原信号且在压缩、传输、恢复过程中,还要求图像的失真度小。
图像压缩过程常称为编码,图像恢复过程常称为解码。根据解码后的数据与原始数据是否完全一致来分类,图像压缩方法一般划分为无失真编码和失真编码两大类。本文的侧重点将放在失真编码部分。
1.2 课题研究的任务和目标
本课题的选题是《基于小波变换的数据压缩的算法研究和应用》,鉴于小波分析理论在图像压缩方面的突出表现和图像数据在人们生活中的重要性,本课题将只研究小波变换在图像数据处理方面的应用。
基于小波变换的图像压缩技术都有其共性,即对图像都要首先进行小波变换,然后再量化编码,各种技术的不同主要体现在量化和编码阶段。本文将对小波变换理论进行系统的论述,然后介绍几种典型的基于小波变换的图像压缩算法,并对它们做简要的分析,接着,本文将选择其中一种算法进行详细的探讨,最后,将用VC++开发工具对此算法进行实现,设计出一个软件系统,这也是本研究的目标。
1.3 内容安排
本文对小波变换图像压缩技术做了比较深入的研究,共分五章,各章的内容安排如下:
第一章简要介绍了本课题的研究背景、研究任务和目标,以及本文的内容安排。
第二章详细介绍了小波变换图像压缩的技术基础。首先详细论述了小波变换理论,然后介绍了几种常用的小波,最后举例将小波变换引入图像压缩,并从能量角度进行了说明。
第三章是本文的重点。本章首先介绍了几种典型的基于小波变换的图像压缩算法,并对它们进行了简单的比较及说明了本课题的所选算法,然后详细的论述了此算法的原理及实现,最后用举例的方式进一步阐述了此算法。
第四章是本课题所选算法的软件实现。首先介绍了软件的总体功能,然后对软件设计中各个模块进行了说明,并对一副图像的进行了压缩,最后对软件做了评价,并讨论了它的优缺点,提出了值得改进的地方。
第五章对本研究做了总结,并对新技术做了展望。

第二章 小波变换图像压缩技术基础
2.1 小波变换简介
小波变换是近十几年才发展起来并迅速应用到图像处理等众多领域的一种数学工具,是继110 多年前的傅立叶(Joseph Fourier)分析之后的一个重大突破,无论是对古老的自然学科还是对新兴的高新技术应用学科都产生了强烈冲击。
傅立叶理论指出,一个信号可表示成一系列正弦和余弦函数之和,叫做傅立叶展开式。用傅立叶表示一个信号时,只有频率分辨率而没有时间分辨率,这就意味我们可以确定信号中包含的所有频率,但不能确定具有这些频率的信号出现在什么时候。为了继承傅立叶分析的优点,同时又克服它的缺点,人们一直在寻找新的方法。20 世纪初,哈尔(Alfred Haar)对在函数空间中寻找一个与傅立叶类似的基非常感兴趣。1909 年,Haar发现了最简单,我们现称之为Haar小波基的标准基,同时打开了通向小波的道路。
1936 年 Littleword 和 Paley 对傅立叶级数建立了二进制频率分量分组理论,即L-P 理论,分组后的傅立叶变换序列相当于带通滤波器作用于原序列,使得L-P 理论具备了频率域内以任意尺度分析函数的能力,这是最早的多尺度分析的思想。1952 年至1962 年 Calderon、Zygmund、Stern 和 Weiss 等人将L-P 理论推广到高维情况,建立了数学研究领域中的奇异积分算子理论。1965 年 Calderon 给出了再生公式[2],对任意函数f(x):
(2.1)
式中 且 满足一定的条件。Calderon 再生公式将函数f(x)表示成伸缩与平移 线性组合,其离散形式非常接近于我们现在说的小波展开;1974 年 Coiffman 对一维 空间和高维 空间给出了原子分解,原子分解的意义即使函数空间中的函数可以由该空间的原子按一定的规则完全表示:1975 年Calderon 利用他自己前面提出的再生公式给出了H空间的原子分解,现已成为许多函数分解的出发点;1976 年 Peetre 引入了 Besov空间的一组基,其展开的系数的大小刻画刻 Besov 空间本身;1981 年 Stromberg 在对 Haar标准正交基改进的基础上,引入了 Sobolev空间的H s 正交基,所有这些工作维小波分析奠定了基础。1984 年法国科学家 Molet 在分析地震波的局部特性时首先使用了小波变换对信号进行分析并提出了小波这一术语。什么是小波?所谓小波就是小的波形,“小”指其具有衰减性,“波”指其波动性,具有振幅正负相间的振荡形式。Molet 与理论物理学家 Grossman 共同提出了连续小波变换的几何体系其基础是平移和伸缩的不变性:1985 年法国马赛大学的数学家 Mayer 将 Molet 的思想与数学研究中已经存在的奇异积分算子理论联系起来,构造了具有一定衰减性的光滑函数,其二进制尺度位移体系构成了L2 (R) 空间的标准正交基,同时 Meyer 与 Grossman 及比利时籍科学家 Daubechies 合作,通过构造了L2 (R) 上的一个准正交完备集的方法选取了小波空间的离散子集,即框架,并证明了一维小波函数的存在性。随后 Lemarie 将这一结果推广到n 维情况,并和 Battle 分别给出了具有指数衰减性的小波函数;1988 年Daubechies 发表了他的论文,证明了具有有限紧支集的正交小波的存在性,这就是人们熟 Daubechies小波基;1989 年数字图像处理的专家 S.Malla t将小波变换用于信号处理,提出了对小波分析理论具有突破性意义的多分辨分析的概念,统一了在此之前提出的这种小波构造方法,将小波正交基纳入统一的框架之中。Mallat 还在这一框架下给出了二进小波变换的快速算法——Mallat 算法(FWT)[3,4]。
90 年代,Sweldens 等人提出了用提升方案来构造小波的方法[5,6],这种以
新的方法构造的小波可以称为第二代小波,以便同以前的小波相区别。第二代小
波构造方法的继承了第一代小波变换的多分辨率特性,同时不依赖于傅立叶变换,因此利于构造非线形的小波,在图像处理等领域有广阔的应用前景。
在这以后,人们又构造了许多小波基。当前小波理论的研究方兴未艾,一是继续研究满足各种不同要求的小波基,一是研究小波分析在信号分析、语音与图像处理、地震勘探、数值算法、CT 成像、天体识别、机器视觉、分形及数字电视、系统故障检测和量子力学等多学科领域的应用。
在信号分析领域,小波分析是一种强有力的数学分析工具。事实上,小波分
析理论将一些各自独立发展的信号处理技术,如计算机视觉中的多尺度信号处理、语音与图像压缩中的子带编码等纳入到一个统一的框架中去。由于小波分析在时域和频域都有很好的局部化性质,所以较好地解决了时间和频率分辨的矛盾。对信号的低频成分用窄时窗使得时域分辨率低而频率分辨率高,对信号的高频成分,用宽时窗使得时域分辨率高而频域分辨率低。这一体现了自适应分辨分析思想的性质就是小波变换的“变焦性”,使得小波分析在信号处理领域的很多方面如地震信号处理、语音的合成与分析、信号的奇异性检测与谱估计、图像处理等都取得了成功的应用。本文主要用小波分解以后将能量集中在低频部分,这样就可以形成零树结构,这样就可以用零树编码对图像进行压缩。
2.2 小波变换基本理论
2.2.1 连续小波变换
1. 一维连续小波变换
定义:设 ,其傅立叶变换为 ,当 满足允许条件(完全重构条件或恒等分辨条件)
< (2.2)
时,我们称 为一个基本小波或母小波[7]。将母函数 经伸缩和平移后得
(2.3)
称其为一个小波序列。其中a为伸缩因子,b为平移因子。对于任意的函数 的连续小波变换[7]为
(2.4)
其重构公式[7](逆变换)为
(2.5)
由于基小波 生成的小波 在小波变换中对被分析的信号起着观测窗的作用,所以 还应该满足一般函数的约束条件
(2.6)
故 是一个连续函数。这意味着,为了满足完全重构条件式, 在原点必须等于0,即
(2.7)
为了使信号重构的实现在数值上是稳定的,处理完全重构条件外,还要求小波 的傅立叶变化满足下面的稳定性条件:
(2.8)
式中 。
从稳定性条件(2.8)可以引出一个重要的概念[7]:
定义(对偶小波) 若小波 满足稳定性条件(2.8)式,则定义一个对偶小波 ,其傅立叶变换 由下式给出:
(2.9)
注意,稳定性条件(2.8)式实际上是对(2.9)式分母的约束条件,它的作用是保证对偶小波的傅立叶变换存在的稳定性。值得指出的是,一个小波的对偶小波一般不是唯一的,然而,在实际应用中,我们又总是希望它们是唯一对应的。因此,寻找具有唯一对偶小波的合适小波也就成为小波分析中最基本的问题。连续小波变换具有以下重要性质:
(1)线性:一个多分量信号的小波变换等于各个分量的小波变换之和。
(2)平移不变性:若f(t)的小波变换为 ,则 的小波变换为 。
(3)伸缩共变性:若f(t)的小波变换为 ,则f(ct)的小波变换为 。
(4)自相似性:对应不同尺度参数a和不同平移参数b的连续小波变换之间是自相似的。
(5)冗余性:连续小波变换中存在信息表述的冗余度。
小波变换的冗余性事实上也是自相似性的直接反映,它主要表现在以下两个方面:
(1)由连续小波变换恢复原信号的重构分式不是唯一的。也就是说,信号f(t)的小波变换与小波重构不存在一一对应关系,而傅立叶变换与傅立叶反变换是一一对应的。
(2)小波变换的核函数即小波函数 存在许多可能的选择(例如,它们可以是非正交小波、正交小波、双正交小波,甚至允许是彼此线性相关的)。
小波变换在不同的(a,b)之间的相关性增加了分析和解释小波变换结果的困难,因此,小波变换的冗余度应尽可能减小,它是小波分析中的主要问题之一[8]。
2. 高维连续小波变换
对 ,公式
(2.10)
存在几种扩展的可能性[7],一种可能性是选择小波 使其为球对称,其傅立叶变换也同样球对称,
(2.11)
并且其相容性条件变为
(2.12)
对所有的 。
(2.13)
这里, =〈 〉, ,其中 且 ,公式(2.10)也可以写为
(2.14)
如果选择的小波 不是球对称的,但可以用旋转进行同样的扩展与平移。例如,在二维时,可定义
(2.15)
这里, , ,相容条件变为
(2.16)
该等式对应的重构公式[7]为
(2.17)
对于高于二维的情况,可以给出类似的结论[4]。
2.2.2 离散小波变换
将连续小波变换的缩放因子a离散化,得到二进小波变换;再将其平移因子b也离散化,就得到离散小波变换[7]。
1. 二进小波变换与滤波器
为了适应数字信号处理,需要将小波变换离散化。可以先进行缩放因子的离散:若小波函数 满足
, (2.18)
则称 为基本二进小波。
在连续小波变换中,若 为基本二进小波,则令a = 2k ,得到二进小波变换:
(2.19)
为了构造基本二进小波,可设φ满足:
(2.20)
可推出 ,则φ大体上相当于一个低通滤波器,因此,φ(2x)的通道比φ(x)的宽,可设φ满足如下的双尺度方程:
(2.21)
其Fourier变换为:
,其中
为低通滤波器。由 ,可得H(0) = 1 即∑hn = 1。
若设
,其中
则G为高通滤波器,有
(2.22)
其Fourier变换为:
(2.23)
因 且 ,得G(0) = 0 即∑gn = 0。
2. 离散小波变换
下面再将二进小波变换中的平移因子也离散化:令b = n2k,则可得离散小波变换[7]:
(2.24)
可以用前面所讲的滤波器系数改写成如下循环形式:
(2.25)
其中, ,D= 为差——高频部分,A = 为剩余——低频部分, 与 为上面讲过的滤波器 之系数。
可以写出正反离散小波变换的具体算法如下:
 正变换(分解)(保存 和所有 )
j = 0; ;
while ( j < J ) {

j++;
}
 逆变换(重构)(利用正变换所保存下来的 和所有 )
j = J;
while ( j > 0 ) {

j–;
}

说明:
图形的横纵坐标分别表示时间(平移因子)和变换结果S f与W f的值。
小波分解可以无限进行下去,J是自己指定的最大分解次数,一般为8~10。
求和符号中k∈Z,无上下限,但具体计算时,由于只有有限个hk、gk不为0,所以实际上是有限的。
逆变换中h与g上的一杠表示复数的共轭,对于实h与g,则共轭与不共轭相同。
求S f与W f都涉及到对所有的样本求和,不可能只处理一个样本。
3. 小波分解
执行离散小波变换的有效方法是使用滤波器。该方法是Mallat在1988年开发的,叫做Mallat算法[9]。这种方法实际上是一种信号的分解方法,在数字信号处理中称为双通道子带编码。用滤波器执行离散小波变换的概念如图2.1所示。

其中: 为低通滤波器
为高通滤波器

图2.1 双通道滤波过程
图中,S表示原始的输入信号,通过两个互补的滤波器产生A和D两个信号,A表示信号的近似值(approximations),D表示信号的细节值(detail)。在许多应用中,信号的低频部分是最重要的,而高频部分起一个“添加剂”的作用。犹如声音那样,把高频分量去掉之后,听起来声音确实是变了,但还能够听清楚说的是什么内容。相反,如果把低频部分去掉,听起来就莫名其妙。在小波分析中,近似值是大的缩放因子产生的系数,表示信号的低频分量。而细节值是小的缩放因子产生的系数,表示信号的高频分量。
由此可见,离散小波变换可以被表示成由低通滤波器和高通滤波器组成的一棵树。原始信号通过这样的一对滤波器进行的分解叫做一级分解。信号的分解过程可以叠代,也就是说可进行多级分解。如果对信号的高频分量不再分解,而对低频分量连续进行分解,就得到许多分辨率较低的低频分量,形成如图2.2所示的一棵比较大的树。这种树叫做小波分解树(wavelet decomposition tree)。分解级数的多少取决于要被分析的数据和用户的需要。小波分解树表示只对信号的低频分量进行连续分解。

为低通滤波器
为高通滤波器

图2.2 小波分解树
在使用滤波器对真实的数字信号进行变换时,得到的数据将是原始数据的两倍。例如, 如果原始信号的数据样本为1000个,通过滤波之后每一个通道的数据均为1000个,总共为2000个。于是,根据尼奎斯特(Nyquist)采样定理就提出了降采样(downsampling)的方法,即在每个通道中每两个样本数据取一个,得到的离散小波变换的系数(coefficient)分别用cD和cA表示,如图2.3所示。图中的符号 表示降采样。

图中 分别表示低通、高通滤波器。
图2.3降采样过程
4. 小波重构
离散小波变换可以用来分析或者叫做分解信号,这个过程叫做分解或者叫做分析。把分解的系数还原成原始信号的过程叫做小波重构(wavelet reconstruction)或者叫做合成(synthesis),数学上叫做逆离散小波变换(inverse discrete wavelet transform,IDWT)。
在使用滤波器做小波变换时包含滤波和降采样两个过程,在小波重构时要包含升采样(upsampling)和滤波过程。小波重构的方法如图2.4所示,图中的符号 表示升采样。

图中:
为高通滤波器

为低通滤波器

图2.4 小波重构方法
升采样是在两个样本数据之间插入“0”,目的是把信号的分量加长。升采样的过程如图2.5所示。

(a)降采样信号 (b)升采样信号
图2.5 升采样的方法

2.3 多分辨率分析
多分辨率分析MRA(Multi-resolution Analysis)是S. Mallat与Y. Meyer于1986年左右共同引入的。这一程序是构造小波基的一种有效的方法。从函数分析的角度给出了正交小波的数学解释,在空间的概念上形象的说明了小波的多分辨率特性,给出了通用的构造正交小波的方法,并将之前所有的正交小波构造方法统一起来,并类似傅立叶分析中的快速傅立叶算法,给出了小波变换的快速算法—— Mallat算法[9]。这样,在计算上变得可行以后,小波变换在各个领域才发挥它独特的优势,解决了各类问题,为人们提供了更多的关于时域分析的信息。
多分辨分析就是要构造一组函数空间,每组空间的构成都有一个统一的形式,而所有空间的闭包则逼近 。在每个空间中,所有的函数都构成该空间的标准化正交基,而所有函数空间的闭包中的函数则构成 的标准化正交基,那么,如果对信号在这类空间上进行分解,就可以得到相互正交的时频特性。而且由于空间数目是无限可数的,可以很方便地分析我们所关心的信号的某些特性。
下面简要介绍一下多分辨分析的数学理论[8]。
定义:空间 中的多分辨分析是指 满足如下性质的一个空间序列 :
(1)调一致性: ,对任意
(2)渐进完全性: ,
(3)伸缩完全性:
(4)平移不变性:
(5)Riesz基存在性:存在 ,使得 构成 的Risez基。关于Riesz的具体说明如下:
若 是 的Risez基,则存在常数A,B,且,使得:
(2.26)
对所有双无限可平方和序列 ,即
(2.27)
成立。
满足上述条件的函数空间集合成为一个多分辨分析,如果 生成一个多分辨分析,那么称 为一个尺度函数。
可以用数学方法证明,若 是 的Riesz基,那么存在一种方法可以把 转化为 的标准化正交基。这样,我们只要能找到构成多分辨分析的尺度函数,就可以构造出一组正交小波。
多分辨分析构造了一组函数空间,这组空间是相互嵌套的,即

那么相邻的两个函数空间的差就定义了一个由小波函数构成的空间,即

并且在数学上可以证明 且 , ,为了说明这些性质,我们首先来介绍一下双尺度差分方程,由于对 ,所以对 ,都有 ,也就是说可以展开成 上的标准化正交基,由于 ,那么 就可以展开成
(2.28)
这就是著名的双尺度差分方程,双尺度差分方程奠定了正交小波变换的理论基础,从数学上可证明,对于任何尺度的 ,它在j+1尺度正交基 上的展开系数 是一定的,这就为我们提供了一个很好的构造多分辨分析的方法。
在频域中,双尺度差分方程的表现形式为:
(2.29)
如果 在 =0连续的话,则有
(2.30)
说明 的性质完全由 决定。

2.4 几种常见的小波
同傅立叶分析不同,小波分析的基(小波函数)不是唯一存在的,所有满足小波条件的函数都可以作为小波函数,那么小波函数选取就成了十分重要的问题[10],一下对几种常见小波[11]做一个简单介绍。
 Haar小波
A.Haar于1990年提出一种正交函数系,定义如下:
(2.31)
这是一种最简单的正交小波,即

… (2.32)
 Daubechies(dbN)小波系
该小波是Daubechies从两尺度方程系数 出发设计出来的离散正交小波。一般简写为dbN,N是小波的阶数。小波 和尺度函数吁中的支撑区为2N-1。 的消失矩为N。除N=1外(Haar小波),dbN不具对称性〔即非线性相位〕;dbN没有显式表达式(除N=1外)。但 的传递函数的模的平方有显式表达式。假设 ,其中, 为二项式的系数,则有
(2.33)
其中
在本研究的实现中,本文采用的小波就是db9/7小波。
 Mexican Hat(mexh)小波
Mexican Hat函数为
(2.34)
它是Gauss函数的二阶导数,因为它像墨西哥帽的截面,所以有时称这个函数为墨西哥帽函数。墨西哥帽函数在时间域与频率域都有很好的局部化,并且满足
(2.35)
由于它的尺度函数不存在,所以不具有正交性。
 Meyer函数
Meyer小波函数 和尺度函数 都是在频率域中进行定义的,是具有紧支撑的正交小波。
(2.36)
其中, 为构造Meyer小波的辅助函数,且有
(2.37)
2.5 小波变换与图像压缩
对信号与图像来说,如果要传输和存储,这就需要快速传输。在同等的通道容量下,如果信号与图像数据可以压缩后在传输,就可以使传输的数据量变的很小,也就增加了通信能力。对图像压缩来说,首要的认为就是对图像数据进行压缩,这就要寻找高压缩比的方法且压缩后的图像要有合适的信噪比,在传输后的恢复图像中,要保持图像的原始特征不改变。图像最终是依靠于人眼的观察而感知的,所以某些图像的压缩编码就要考虑人类的视觉特性。这类方法思想在于将原始图像在频域内作多层分解,然后对分解后得到的信息表示灵活的有选择的编码。
小波变换主要是对原有的图像进行离散小波变换(discrete wavelet transform ,DWT),将原有的图像在时间-频率域上分解。这里给出一个例子[12]:

图 2.6.a

图2.6.b Lena三级分解图像

图2.6.a是图像名字叫“Lena”。“Lena”不仅是图像压缩界,也是整个图像处理领域最常用到的一幅测试图像。该图是1972年10月“花花公子”杂志的中间插页的一部分,是瑞典人Lena Soderberg的特写,被南加利福尼亚大学一位不知名的学者发现后加以剪裁和扫描,用来作为其图像压缩研究的测试图像。从此“Lena”在图像处理研究领域广为使用,成为最重要、知名和常用的测试图像。而Lena本人一直生活在瑞典,直到1988 年她才知道自己的“名声”,1997年5月她还应邀参加了波士顿第50届图像科学与技术协会年会[13]。但为什么会选用这些图像作为检验图像压缩算法的测试图像呢?因为这些测试图像都是很有特点和代表性的。“Lena”图像多为纯连续色调,特别是墙和露出的皮肤区域;图像中帽子是好的连续色调,而头发和帽子上的羽毛却是差的连续色调;墙上的直线和镜子的曲线部分则是离散色调图像的特征。因此用该图作为图像压缩的测试图是很具有代表性的。
图2.6.b表示Lena图像使用三级滤波器组做小波变换输出的子图像(sub- image),所选用的小波为Daub 9/7。图中的数字1, 2和3表示分解的级数编号,LL3表示第3级的低频子图像,在这个例子中,它是分辨率最低的子图像,HL3表示第3级分解在水平方向上的子图像,LH3表示第3级分解在垂直方向上的子图像,HH3表示第3级分解在对角线方向上的子图像,其他的组合符号依此类推。
2.6 从能量角度看小波变换
图像经过小波变换后,它的能量并不会发生损失,而是会将能量重新分配,这样,各子图像包含的能量差别很大[14]。以某细胞图像为例[15],对其进行小波分解,其能量分布特征如表3.1所示。表3.1中数据为各子图像能量占整幅图像能量的百分比。
表2.1 某细胞4级分解后各子图像的能量百分
子图像名称 能量特征

98.51

0.36

0.38

0.08

0.16

0.20

0.03

0.09

0.09

0.01

0.03

由表2.1可见,图像分解后的能量主要集中在 子图像,占全部能量的98%以上,其它子图像的能量较少,且层次越低,能量越少.
目前,对于小波变换图像压缩的研究主要集中在两个方面:一是小波基的选
择,一是小波系数的编码。因为小波变换本身并不能压缩图像,只是提供了减少
比特率的一种可能,必须结合其它编码技术对小波系数编码才能实现压缩目的。
所以,基于小波变换的图像压缩方法通常分为3个步骤 :小波变换、量化和编码。此类方法首先对图像进行多级小波分解,然后对每层的小波系数进行量化, 如零树编码进行量化,矢量量化等,再对量化后的系数进行编码,如算术编码、哈夫曼编码等无失真编码。对于基于小波变换的图像压缩编码方法,对小波变换后系数的量化和编码是实现数据压缩的关键,也是本文的研究重点。

第三章 基于小波变换的图像压缩算法的研究
3.1 几种小波图像压缩算法的介绍
3.1.1 几种小波图像压缩算法的介绍
自从小波变换用运到图像处理领域以后,发展相当的快,出现了许多新的技术,例如向嵌入零数小波编码(EZW)技术,它是运用较早的基于离散小波变换的图像压缩技术,在 EZW图像压缩技术的基础上,又出现了SPIHT图像压缩算法和EBCOT图像压缩算法,她们的基础都是EZW算法。下面,分别对它们作一介绍:
 EZW算法
在1992年,Lewis,A. S.和Knowles, G.首先介绍了一种树形数据结构来表示小波变换的系数[16]。在1993年,Shapiro, J. M.把这种树形数据结构叫做“零树(zerotree)”,并且开发了一个效率很高的算法用于熵编码,他的这种算法叫做嵌入(式)零树小波(Embedded Zerotree Wavelet,EZW)算法[17]。EZW主要用于与小波变换有关的二维信号的编码,但不局限于二维信号。
 SPIHT算法
受 EZW算法和 Amir Said 本人开发的 IEZW(Improved Embedded Zerotree Wavelet)算法的启发,Amir Said 和 William Pearlman 在1996年发表了他们对EZW的改进算法[18],叫做 SPIHT(set partitioning in hierarchical trees)算法,可考虑译成“层树分集”算法。图像经过小波变换之后,大部分能量都集中在低频子带。SPIHT算法就是从这个事实出发,最先传送幅度大的系数,这样解码器即使在低速率应用环境下也可得到图像的大部分信息。编码树的结构与EZW算法的结构类似,每一个节点要么没有子节点,要么有4个子节点。在编码过程中,使用三个列表变量存储重要系数和不重要系数。
小波图像编码方法的开发与渐进图像(progressive image)如何传输有着密切的关系。传输渐进图像的方法很多,SPIHT算法采用的方法是幅度大的系数先传送,理由是这样的:假设原始图像由一组像素 组成,用 表示 经过小波变换之后产生的系数,其中(i, j) 为像素的坐标,也是小波图像系数的坐标。为简化符号,使用字母p表示二维图像,
用c 表示小波变换之后的系数,因此一幅图像的小波变换可表示成,
(3.1)
W(g) 表示单式(unitary)分层子带变换,经过小波变换之后的二维阵列c 具有与p 相同的维数。每一个元素 可用二进制数的格式表示在渐进图像传送中,解码器开始设置的重构矢量 通常为零,然后按照接收到的编码信息进行修改。在接收到系数的近似值或者精确值之后,解码器可以得到重构的图像 ,
(3.2)
其中, 表示小波变换的逆变换。为使接收端能够尽快看到图像的主要内容,就需要对图像的内容进行选择。选择的原则是解码器重构的图像与原始图像最接近。如果用均方差(MSE)指标来衡量,则失真程度 可表示为,
(3.3)
其中N 为图像的像素数目, 是由系数, 重构的像素值。由于欧几里得范数(Euclidean norm)即向量的长度相对于单式变换 是不变的。该式表明,解码器开始使用的系数近似值 为零时,最大的系数 对减少均方差最重要,因此幅度比较大的系数需要先传送。根据幅度大的系数先传送的原则,就需要对系数进行排序。如何排序就是SPIHT算法想解决的问题。假设传送的系数已经按要求排了序,当系数 用二进制的形式表示时,同样根据幅度大的系数先传送的原则,自然而然地会按照最高有效位最先传送的原则进行传输。在渐进图像传输中,这个方法叫做位平面(bit plane)方法。这个原则也体现在SPIHT算法中。
SPIHT算法的一个特点是不单独传输系数的排序信息。这样做的基本依据是任何排序算法的执行路径都是使用分支点的比较结果进行定义的,如果编码器和解码器使用相同的排序算法,解码器就可重复编码器的执行路径,因此排序信息可从执行路径中重新获得。
 EBCOT算法
最佳截断嵌入码块编码 (Embedded Block Coding with Optimized Truncation,EBCOT)是 David Taubman 在1999年发表的一种压缩算法[19],现正处在进一步开发之中。该方法与早期的EZW,SPIHT以及Taubman和Zakhor开发的LZC(layered zero coding)等算法有着不同程度的联系。
EBCOT算法是一种对小波变换产生的子带系数进行量化和编码的方法。它的基本思想是把每一个子带的小波变换系数分成独立编码的码块(code-block),并且对所有的码块使用完全相同的压缩算法。
对每一个码块进行编码时,编码器不用其他码块的任何信息,只是用码块自身的信息产生单独的嵌入位流(bitstream)。每一码块的嵌入位流可以被截断成长度不等的位流,生成不同的位速率,这就是EBCOT算法中“截断”的含义。
每一码块的嵌入位流应该截断到什么程度才符合特定的目标位速率、失真限度或者其他衡量图像质量的指标,也就是在给定一个目标位速率的情况下,使重构图像的失真程度最小,David Taubman提出了一种认为是“最佳”的方法来截断每一个独立码块的位流,这就是EBCOT算法中“最佳”的含义。
概括地说,EBCOT算法的主要想法是把嵌入码块编码方法与码块位流的最佳截断方法结合在一起,使重构图像的失真最小,它的主要特性包括分辨率可变(resolution, scalability)、信噪比可变(SNR scalability)和随机访问(random access)。
3.1.2 关于JPEG2000
JPEG2000[20]是由ISO/IEC JTC1 SC29标准化小组负责并正在制定的新的静态图像压缩国际标准。JPEG全名为Joint Photographic Experts Group(联合摄影专家组),它是一个在国际标准组织(ISO)下从事静态图像压缩标准制定的委员会。它制定出了第一套国标静态图像压缩标准:ISO10918-1;就是我们所说的JPEG了。由于JPEG优良的品质,使得它在短短的几年内就获得极大的成功,目前网站上百分之八十的图像都是采用JPEG的压缩标准。然而,随著多媒体应用领域的激增,传统JPEG压缩技术已无法满足人们对多媒体图像资料的要求。因此,更高压缩率以及更多新功能的新一代静态图像压缩技术JPEG2000就诞生了。JPEG2000正式名称为:ISO15444,同样是由JPEG组织负责制定。该标准是由联合摄影专家组于1997年开始征集提案,把它作为JPEG标准的一个更新换代标准。它的目标是进一步改进目前压缩算法的性能,以适应低带宽、高噪声的环境,以及医疗图像、电子图书馆、传真、Internet网上服务和保安等方面的应用。国际标准化组织的WG1小组已于2000年8月制定了最终的国际标准化草案(The Final Draft International Standard,简称FDIS)。JPEG2000与传统JPEG;最大的不同,在于它放弃了JPEG。所采用的以离散余弦变换(Discrete Cosine Transform)为主的区块编码方式,而采用以小波转换(Wavelet Transform)为主的多解析编码方式。离散子波变换算法是现代谱分析工具,在包括压缩在内的图像处理与图像分析领域正得到越来越广泛的应用。此外JPEG2000还将彩色静态画面采用的JPEG编码方式与2值图像采用的JBIG编码方式统一起来,成为对应各种图像的通用编码方式。
3.2 各种小波图像压缩算法的共性
在3.1.1小节中提到了三种基于小波变换的图像压缩技术( EZW算法、SPIHT算法、EBCOT算法),它们都是基于小波变换的压缩算法,因此之间都存在着某种共性。以下的图3.1.a和图3.1.b中分别说明了小波压缩和解压缩的五个步骤。

图 3.1.a 图像压缩

图 3.1.b 图像解压

从以上两个图中可以看到各种小波算法压缩图像和解压缩图像的流程是一样的。此外,压缩中的五个步骤除了量化都是可逆的。量化的过程是为了降低小波变换后产生的浮点数的精度。
量化和编码阶段是小波变换图像压缩的重要方面,小波变换的目的是为了产生大量零值或者近视于零值的幅度值。各种小波变换的图像处理方法的不同点主要就体现在量化和编码阶段。
3.3 对各种小波压缩算法的比较及本课题所选方案
3.3.1 对各种小波压缩算法的比较
小波图像处理的方法是非常之多的,在前面只是介绍了比较经典的三种算法,这三种算法之间存在着不同的联系,它们之间的区别主要体现在对图像进行完小波变换后的量化和编码阶段。这三个经典的算法中,EZW算法是最为基本的算法,也是首先被提出的,后面介绍的SPIHT算法和EBCOT算法都是以EZW算法为基础的、经过改进的更为优秀的算法,当然,比起EZW算法的实现,后两种算法也将会更加的复杂。
3.3.2 本课题所选方案
本课题中将选用EZW算法作为小波变换图像压缩的方案,原因有二:第一,虽然这种算法提出的较早,也在它的基础上衍生了别的算法,但是它是较基础的算法,对于它的理解和应用会有助于对别的算法的理解;第二,EZW算法相对于SPIHT、EBCOT等许多算法实现起来更为容易,而且在压缩效果上还是比较理想的。因此,本课题选用了EZW算法来实现基于小波变换的图像压缩。
3.4 所选方案的实现
3.4.1 EZW算法概述
嵌入式零树小波中的“嵌入(Embedded)”是渐进编码技术(Progressive Encoding) 的另一种说法,其含义是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像,图像合成的过程与分解的过程相反,使用子图像生成许多分辨率不同的图像。
“零树(ZeroTree)”是指小波变换系数之间的一种数据结构,因为离散小波变换是一种多分辨率的分解方法,每一级分解都会产生表示图像比较粗糙的低频图像和比较精细的高频图像的小波系数,在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示,如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(Threshold) ,那么这棵树就叫做零树。
“小波(wavelet)”是指该算法以离散小波变换为基础,以大的小波变换系数比小的小波变换系数更重要,以及高频子带中的小系数可以被抛弃的事实为背景。
EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次,生成一种分辨率图像,编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤:设置阈值、每个小波系数与阈值进行比较、量化系数和重新排序。在扫描过程中需要维护两种表,一种是小波系数的符号表,另一种是量化表[12]。
3.4.2 零树的构造
回顾二维小波变换的计算过程,不难想象各级子图像中的系数是相关的。由于低频子图像的系数要比高频子图像的系数大,零树编码技术就是利用这个事实来设计编码/解码过程中每一级使用的量化器。各级子图像中的系数之间的关系可以用树的形式描述。如图3.2(a)所示,最低频率的子图像在左上角,最高频率的子图像在右下角,由同一方向和相同空间位置上的所有小波系数组成一棵树。例如,从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位置上的所有系数构成一棵下降树。按箭头所指的方向,各级系数的名称分别用祖系数、父系数、子系数和孙系数来称呼。举例来说,LL3的系数为{63}, HH2和HH1中的系数分别为{3}和{4, 6, 3, -2}, 由这些系数构成的树如图3.2(b)所示。如果把{63}指定为父系数,{3}就称为子系数,而{4, 6, 3, -2}中的4个系数就称为孙系数。

(a)构造方法 (b)小波系数举例
图3.2 EZW编码树的构造
为便于比较,把图3.2(b)所示的两棵树用图3.3(a)和(b)表示。假设编码时开始的阈值 =32,由于63比32大,这样的树叫做非零树,图3.3(a)所示。假设下一次编码时的阈值 =16,把-13当作父系数,它的幅度16小,而它的所有4个子系数的幅度都比16小,这样的树叫做零树,系数-13叫做零树根,如图3.3(b)所示。根据以上的分析,零树的定义可概括为一句话:子孙系数都为零的树。定义零树的重要意义在于,如果一棵树是零树,那么这棵树就可以用一个预先定义的符号来代表整棵树,从而提高了压缩比。

(a) 非零树例子 (b) 零树例子
图3.3 非零树与零树的概念
3.4.3 扫描方法
EZW算法对小波系数的进行编码的次序叫做扫描[12]。扫描子图像系数的方法有两种,一种叫做光栅扫描(raster scan),如图3.4(a)所示,另一种叫做迂回扫描(morton scan),如图3.4(b)所示。

(a) 光栅扫描 (b) 迂回扫描
图3.4 小波变换系数扫描方法
3.4.4 EZW算法的实现
EZW算法可粗略地归纳为下面几个主要步骤。
⑴阈值T 的选择
开始时的阈值 通常按下式估算,
= (3.4)
其中, 表示最大的系数值, 表示小波变换分解到第i 级时的系数。以后每扫描一次,阈值减少一半。
⑵给系数分配符号
使用EZW算法编码图像时每一次扫描需要执行两种扫描,并产生两种输出的符号。第一种扫描叫做主扫描(dominant pass),它的任务是把小波系数X 与阈值T 进行比较,然后指定POS(positive significant)、NEG(negative significant)、ZTR(zerotree root)、IZ(isolated zero)中4个系数符号之一,其余的用T,0表示,其中T表示该系数没有子孙系数且它本身为0。对整幅图像扫描之后产生系数符号序列。第二种扫描叫做辅扫描(subordinate pass),其任务是对主扫描取出的带有符号POS或者NEG的系数进行量化,产生代表对应量化值的量化符号“0”和“1”。
即:
 主扫描: 扫描每一个系数以产生系数符号
如果系数幅度大于阈值(T )且为正数,输出符号POS,如果系数幅度小于阈值(T )且为负数,输出符号NEG,如果系数是零树根,输出ZTR,如果系数幅度小于阈值但树中有大于阈值的子孙系数,输出孤立零符号IZ。
 辅扫描: 量化带符号POS和NEG的系数
在量化系数之前要构造量化器。量化器的输入间隔为[ , ) ,该间隔被1.5 分成两个部分:[ ,1.5 ]和[ ,2 ],量化间隔为0.5 , 其中i 为第i 次编码。量化器的输出为量化符号“0”和“1”,“0”对应量化值为(1.5-0.25) ,“1”对应量化值为(1.5+0.25) 。
3.5 EZW算法举例
为进一步理解EZW算法,举一个例子。假设有一幅8×8的图像P ,离散小波变换矩阵为W ,经过小波变换之后的图像为X=WP ,小波图像系数X 和扫描方式分别如图3.5(a)和(b)所示。另外还假设,图3.5(a)所示的数据是经过3级分解的小波图像系数。

(a) 小波图像数据 (b) 迂回扫描
图3.5 8×8小波变换图像
3.5.1 树结构
图3.6(a)中的系数用坐标(行号,列号)表示。最低分辨率子图像(即第3级)中的(0,0)系数和其他三个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关,构成的树如图3.6(b)所示。说明如下:
(0,0) 表示子带LL3的系数,它与第3级子图像中相关的子系数有3个:(0,1),(1,0),(1,1)。
(0,1) 表示子带HL3的系数,它与第2级子图像中相关的子系数有3个:(0,2),(0,3),(1,2),(1,3)。
(1,0)表示子带LH3的系数,它与第2级子图像中相关的子系数有3个:(2,0),(2,1),(3,0),(3,1)。
(1,1) 表示子带HH3的系数,它与第2级子图像中相关的子系数有3个:(2,2),(2,3),(3,2),(3,3)。

(a) 8×8子图像小波变换系数 (b) 最低频带小波变换系数树
图3.6 编码树的结构
在其他子图像中,任何一个系数在高一级分辨率子图像中都有4个子系数与它有关,它们之间构成的树如图3.7(b)所示,图中只表示了两个的树。从图中可以看到,
(0,2)表示子带HL2 的系数,它与第1级子图像中相关的子系数有4个:(0,4),(0,5),(1,4),(1,5)。
(0,3) 表示子带HL2 的系数,它与第1级子图像中相关的子系数有4个:(0,6),(0,7),(1,6),(1,7)。
(1,2)表示子带HL2 的系数,它与第1级子图像中相关的子系数有4个:(2,4),(2,5),(3,4)(3,5)。
(1,3)表示子带HL2 的系数,它与第1级子图像中相关的子系数有4个:(2,6),(2,7),(3,6)(3,7)。

(a) 8×8子图像小波变换系数 (b) 2级子图像小波变换两个系数树
图3.7 编码树的结构
3.5.2 编码
根据对图像分辨率的要求,编码时可对小波图像系数进行多次扫描。每一次扫描包括主扫描和辅扫描 。
 第一次扫描:
步骤1: 选择初始阈值。最大的系数为63,因此选择 。
步骤2: 指定系数的符号。设DL为主扫描表,SL为辅扫描表,从(0,0)点开始扫描,扫描的每一个系数与阈值32比较,在此过程中将比较符号放在DL中。当一个系数被指定为符号ZTR时,它的所用子孙系数不在扫描,标记它的子孙系数为x。当一个系数被标识为Z时表示此系数小于阈值且没有子孙系数。如图3.8所示为第一次扫描的结果。
第一次主扫描之后, DL中的系数符号为:
DL={ POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z POS,Z, Z} 。POS,NEG在此次扫描中它为一个重要系数,不在被扫描。

(a) 系数符号和标记 (b)系数量化
图3.8 第一次主扫描
步骤3: 量化系数。对带符号POS/NEG的系数进行量化。在第一次主扫描期间的阈值是32,幅度大于32的有4个系数{63,34,49,47}。用48把间隔[32, 64) 分成两个部分,如图3.8(b)所示。幅度在间隔[32,48) 中的系数指定为符号“0”, 幅度在间隔[48, 64) 中的系数指定为符号“1”,于是这4个系数被编码成如表3.1所示的量化符号。
在第一次辅扫描之后,4个系数{63-POS, 34-NEG, 49-POS, 47-POS}的量化符号所组成的位流为:
S1: 1 0 1
表3.1 第一次辅扫描量化表
系数幅度 量化符号 重构幅度
63 1 56
34 0 40
49 1 56
47 0 40
步骤4:把系数集{63-POS, 34-NEG,49-POS, 47-POS}排列成{63-POS, 49-POS, 34-NEG, 47-POS}。
步骤5: 输出编码信息。编码器输出两类信息,一类给解码器的系数符号系列等信息,另一类用于下一次扫描的阈值和大于阈值的系数值等信息。
① 给解码器的信息包含下面三种:
HEADER (即 ), D1: POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z, POS, Z, Z
S1: 1 0 1 0.
② 给下一次扫描用的信息包含下面三种:
,{63-POS, 49-POS, 34-NEG, 47-POS}和子带图像。
 同第一编码一样,可以继续进行第二次扫描以及更多次。这可以根据对图像的压缩率或者数据的传送率等应用要求可决定是否继续编码。
3.5.3 解码过程
EZW的解码过程是EZW编码的逆过程,编码时扫描多少次,解码时也可以解多少次,这要取决于对图像分辨率或者传输环境的要求。解码过程大致分为三个步骤:在接收到编码器发送的信息之后,解码器首先设置阈值,构造逆量化器,然后开始解读位流中包含的位置和小波系数值。
 第一次解码
解码器开始时的阈值 ,它接收到来自编码器第一次扫描输出的系数符号是,POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z, POS, Z, Z /1 0 1 0。这个信息相当于量化符号所组成的位流与系数符号之间有如下的对应关系,

D1 POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z POS, Z, Z
S1 1 0 1 0

解码器要按照编码时的扫描和量化方法进行解码。输入位流的第1个系数符号是POS,对应的量化符号位是“1”,因此第1个系数是56;第2个系数符号是NEG,对应的量化符号位是“0",因此第2个系数是-40;第3个系数符号是IZ,在相应的图像系数位置上用“0”表示它的系数,第4个系数是ZTR,对应为“0”并且它的所有子孙系数也为“0”。第一次解码的结果如图3.9所示。用“0”表示的系数表示已经扫描过,它们对应符号IZ或者ZTR,用“×”表示的系数表示不需要扫描的系数,因为它们是零树根的子孙。

图3.9 第一次解码
在第一次解码之后,解码器需要判断是否要进一步重构比较精细的图像。如果不需要,则退出解码,如果需要则进入第二次解码甚至更多次。
3.6 关于编码
在以上给出的编码器输出中并没有用到熵编码,在实际的许多软件设计中都会用到熵编码,例如可以用运EZW算法和算术编码来共同完成图像数据的处理。
另外,由于EZW算法先将待编码的比特流按重要性排序,再依据所排顺序从最重要位到最不重要位依次发送。该算法在发送过程中,可根据目标码率或失真度要求随时结束编码;在解码过程中,也能根据要求随时结束解码,并可得到相应码流截断处的目标码率的恢复图像,从而有效地控制计算量,满足网络传输中实时处理的要求。这也是本课题所采用的方法,即用户可以根据自己的需要,自行的设置压缩率和解压率,来随时停止编码和解码过程。

第四章 基于小波变换的图像压缩算法的
软件实现
4.1 软件总体功能设计
本软件主要实现基于小波变换的EZW算法对图像(位图)的压缩和解压缩,也就是将第三章的研究和小波变换技术相结合,用具体的开发工具——VC++[21]进行实现。

图4.1 软件界面
该软件完整的工作过程是:
 图像压缩过程:图像读入后显示在软件的界面,然后可以根据需要设定图像小波变换的级数对图像进行变换,变换完之后还可以进行图像的重构。对经小波变换的图像可以进行EZW编码,编码中没有使用熵编码,而是采用直接设定压缩率的方法来得到压缩图像(后缀名为ezw)。
 对于压缩后的文件(.ezw文件),可以按照原压缩率将其读入界面并显示,然后用户可以设定解压缩率实现图像的解压,将.ezw文件解压为.bmp文件。
注:本章中的压缩率和解压缩率只是一种笼统的说法,并不遵循严格的公式定义。
4.2 软件各个模块的实现
按照软件应该实现的功能,本软件可以分为一下四个模块,分别为图像的读入模块、图像小波变换模块、EZW算法实现模块、解码模块。各个模块之间的联系如图4.2所示。图4.2所示的过程实际上也就是一次完整的图像处理过程。

图4.2 软件模块设计流程图

各个模块的分别实现:
 位图读入显示模块
本软件实现的是BMP文件格式的图像压缩,BMP位图文件可以看成由四个部分组成:位图文件头(bitmap-file header)、位图信息头(bitmap-information header)、彩色表( color table) 和定义位图的字节(BYTE)阵列,可以调用基本类对图像信息进行存取。
实现位图的读入,由于本软件是基于MFC(Microsoft Foundation Class Library)框架的,但MFC中没有处理设备无关位图(DIB)位图的类,可以定义一个处理DIB位图的专用类CDib类,在其中封装必要而有效的DIB数据成员和处理函数[22]。该类具有的功能如下:
Void LoadFIle(CString m_fileName); //装载BMP位图文件
BOOL SaveFile(const char* paszFilename); //存储BMP位图文件
Char* GetFileName(); //返回位图文件名
DWORD GetSize(); //返回位图文件的大小
UINT GetWidth(); //返回位图文件的宽度
UINT GetHeight(); //返回位图文件的高度
UINT GetNumberofCorlors(); //返回位图颜色数目
RGBQUAD* GetRGB();//返回颜色表首地址
BITMAPINFO* GetInfo(); //返回图像信息结构首地址
BYTE *GetData(); //返回图像数据首地址
位图的读取流程图如图4.3所示。

图4.3 位图的读取流程图

图4.4为位图的显示流程图。

图4.4 位图的显示流程图

 图像的小波变换模块
对图像进行小波变换,它是小波变换图像压缩的基础,后面的EZW算法就是以此为前提和基础。这个过程中将弹出一个对话框,要求用户输入一个1~6之间的整数,用来指定小波变化的级数。
此模块对图像进行离散小波变换,这里选用的小波是db9/7小波,用db9/7小波的滤波器系数可以构成小波变换矩阵 。当然,由于这个矩阵是非常规则的[23],所以只需构造出它的一行就行了。对图像进行二维小波变换时采用标准分解方法,即对每一行的像素值先进行变换,产生每一行像素的平均值和细节系数,再对经过变换的图像的所有列进行变换,形成最终小波变换图像。
此过程的流程图4.5所示:

图4.5 图像小波变换模块流程图

 编码模块
对经过小波变换的图像进行量化编码。这个模块就是EZW算法的实现过程,这里又会有一个对话框弹出,让用户输入一个0~1之间的小数,来设定压缩率,实际就是何时终止编码。用户输入的数字越小,则压缩率越大。
该模块就是第三章的具体实现,完成对小波变换后的图像编码。它首先判断一个系数的符号情况,是 POS、NEG、ZTR、IZ 和 Z 中的哪一个,然后再对符号为POS和NEG两种符号进行量化编码。此模块的流程图如下:

图4.6 EZW编码模块

 解码模块
这个模块按压缩时的压缩率来显示图像,用户可以设定解码率,并在此解码率下解码图像。
此模块为EZW算法的解码过程,主要是对获得的码流进行定位和量化。这个过程中设定的解码率实际就是用来说明什么时候停止解码。
 小波重构模块
此模块为一次完整压缩/解压缩的最后一步,是对解码中得到的系数进行小波重构,也就是小波变换的逆过程。
至此,一次完整的图像压缩/解压过程完成。
4.3 软件应用举例
以下,将对该软件的应用做一个小的演示,来看一下它的工作情况。

图4.7 载入24位Lena图

图4.8 Lena图的三级小波变换图

图4.9(a) 压缩前的Lena文件 图4.9(b) 压缩后的ezw文件

图4.10(a) 解压后Lena图 图4.10(b) 解压后bmp文件
说明:图4.7为软件载入24位Lena图,它的大小为720K;
图 4.8 为图4.5的三级小波变换;
图4.9为压缩后生成的ezw文件,编码长度占总码的比重为0.6,大小为403K;
图4.10为解压后的Lena图,解码长度占总码的比重为0.7,大小为719K。
从以上的应用中可以看出,对比压缩前和解压后的图像,本软件的性能还是比较好的。
4.4 软件评价
在图像编码系统中,评估编码系统性能的一种方法是失真度量法,用峰值信号噪声比(peak signal to noise ratio, PSNR)[23]来衡量, 定义为最大像素值(Peak Signal Value, PSV)与均方差(mean square error,MSE)[23]之比,
(5.1)
对8位二进制图像,
(5.2)
其中,

(5.3)
其中,x(m,n)为原始图像的像素值, 为解压缩之后的像素值。
评估编码系统性能还使用其他方法,这些方法包括使用规格化均方差
(normalized mean square error,NMSE)、信号噪声比(signal to noise ratio,SNR) 和平均绝对误差(mean absolute error,MAE)来度量,分别定义为
(5.4)
(5.5)
(5.6)
其中,x(m,n)为原始图像的像素值, 为解压缩之后的像素值。
表5.1 Lena图像七级小波分解EZW压缩算法整体性能
压缩比 CR 峰值信噪比 PSNR(db) 压缩时间 T(s)

16:1 27.54 0.54
8:1 23.23 0.61
4:1 33.17 0.68
2:1 36.28 0.77
1:1 39.55 0.91
4.5 本软件系统的优点和不足
本软件系统实现了EZW算法,能够对图像实现压缩和解压缩功能,用户可以根据自己的需要设定压缩率和解压缩率,压缩效果较好,压缩图像解压缩后主观上没有区别。
虽然本软件实现了图像压缩/解压处理功能,但EZW算法毕竟是一种较为基础的算法,相对于SPIHT算法和EBCOT算法在压缩率等方面就存在着差距,另外,在本课题的实现中并没有采用熵编码,这在某种程度上也会造成系统的性能下降。
4.6 值得改进的地方
本软件实现了EZW算法,但还可以进行一些改进,用于提升性能:
 本系统的编码过程中没有进行熵编码,可以进一步用运EZW算法和熵编码(如算术编码)相结合的算法来提供系统的性能;
 如果要取得好的压缩率,可以在EZW算法基础上采用改进的编码方法(如SPIHT算法和EBCOT算法), JPEG 2000 编码规范就是一个很好的改进;
 本系统只实现了对位图(.bmp)的处理,没有考虑到其他图像格式,因此,可以对其功能进行改进。

第五章 总结
5.1 所做工作的总结
在本研究中,首先详细的介绍了小波变换的产生背景和小波变换的基本理论知识,重点谈到了连续小波变换和离散小波变换,其中的离散小波变换最为重要,它是图像小波变换的理论基础。接着,介绍了几种常见的小波并将小波变换引入了图像处理中,在这里,为了直观,举出了一个对图像进行小波变换的例子,随后还从能量的角度对图像小波变换进行了说明。所有这些都是基于小波变换处理图像的前提和基础,是每种小波变换算法都要用到的。
随后,对基于小波变换的图像压缩算法进行研究。这里,首先介绍了几种比较经典的基于小波变换的图像压缩算法和JPEG2000这个国际化图像处理标准,并对几种算法进行了简单的分析,阐述了它们之间的共性,并对它们做了比较。接着,确定了本课题中所要采用的基于小波变换的图像压缩算法——EZW算法。随后,重点论述了EZW算法,包括它的由来、算法概述及如何实现,还提及到了与算法相关的内容,如零树的构造、扫描等等。最后,举出了一个EZW算法实现的具体例子,详细阐述了EZW算法的思想和实现。这一部分是全文的重点,也是基于小波变换图像压缩的精髓所在,还是各种基于小波变换处理图像的区别点。
最后,论述了小波变换图像压缩的软件实现。在此,具体阐述了基于小波变换的EZW图像压缩算法的VC++实现。首先,讲到了软件的总体设计思路,要实现的功能,接着对软件各个模块进行了介绍,并说明了实现流程,然后对软件进行了应用举例,说明软件的工作情况。最后,对软件及EZW算法的性能进行了评价,并讨论了软件系统的优点和不足以及值得改进的地方。
从整个工作来看,基本上到达了前期的目标,在对基于小波变换的图像压缩的算法进行研究的基础上实现了软件系统,对软件系统的性能也是比较满意的。但也留下了些遗憾,主要有一些几点:
 研究的基于小波变换的图像压缩算法不是最先进的、性能最良好的算法(如EBCOT算法),而是一种较为基础的算法。
 在实现了EZW算法之后,并没有实现熵编码,而是直接进行了编码,导致了压缩性能的下降。
5.2展望
由于小波变换在图像处理方面的突出表现,引起了人们的极大关注和兴趣。随之而来,许多新技术也不断出现,这其中,有的是对原有技术的改进,有的是将小波图像处理技术和别的编码技术相结合,以取得最佳效果,有的是原创型的新算法。第三章中所介绍的JPEG2000也是许多技术的结合产物,它就综合应用了图像分块技术、小波变换技术、EBCOT压缩技术。在功能上,它的压缩比要比原来的JPEG技术提高20%以上,还实现了渐进传输(progressive transmission),这是JPEG2000的一个重要特性,它可先传输低分辨率的图像或者是图像的轮廓,然后逐步传输其他数据,不断提高图像质量,以满足用户的需要。这个特性在多媒体网络应用中有重要的意义。例如,当下载一幅图像时,可比较快地看到这幅图像的概貌,根据对图像质量的要求和可用的网络带宽控制下载图像的数据量。支持兴趣区(region of interest, ROI)的编码是其另一个重要功能。用户利用这个特性可指定感兴趣的图像区域,在压缩时对这些图像区指定特定的压缩质量,或在恢复时指定特定的解压缩要求,这给用户带来了极大的方便。例如,在有些情况下图像中只有一小块区域对用户是有用的,对这些区域采用低压缩比,而其他区域采用高压缩比,在保证不丢失重要信息的同时能有效地压缩数据量。
创新无界,可以相信,随着人们研究的不断深入,小波变换技术在图像处理方面将不断会有新的成果产生。

参考文献
[1] 鲁宏伟.多媒体计算机原理与应用[M]. 北京:清华大学出版社,1998.
90~93.
[2] Han Y. A version of Calderon-Zygmund decomposition and its applications[C]. Sci Sinica, 1985, 28:134~146
[3]李建平 主编. 小波分析与信号处理——理论、应用及软件实现[M]. 重庆:重庆出版社,1997.12.
[4] 张贤达. 现代信号处理[M].北京:清华大学出版社. 2001. 485~573.
[5] Wim Sweldens. The Lifting Scheme:A New Philosophy in Biorthogonal Wavelet Constructions [J]. In Proc. Of SPIE,San Diego,CA,USA. Vol.2569. Sept.1995:68~79.
[6] Wim Sweldens. The Lifting Scheme:A Construction of Second Generation Wavelets [J]. SIAM J.Math. Appl. to appear 1997.
[7] 张贤达. 小波与离散变换理论及工程实践[M].北京:清华大学出版社. 2005.
[8]胡昌华,张军波,夏军,张伟.基于MATLAB的系统分析与设计——小波分析[M].西安:西安电子科技大学出版社,2000.
[9]Mallat, S. G.,A Theory for Multiresolution Signal Decomposition: The Wavelet
Representation [J], IEEE Trans. PAMI, vol. 11, no. 7, July 1989:674~693.
[10]董长虹,高志,余啸海.Matlab小波分析工具箱原理与应用[M].北京:国防工业出版社,2004.
[11] 谭建豪,章兢,蔡立军,张新国. 现代信息处理及其应用[M].北京:清华大学出版社,2006.70~80.
[12]林福宗,多媒体技术基础(第二版)[M].北京:清华大学出版社,2002.
169~194.
[13]David Salomon 著. 吴乐南 等译. 数据压缩原理与应用(第二版)[M].
北京: 电子工业出版社,2003.
[14]李萍,许录平.整数小波图像变换及统计分析[J].计算机工程与应用,2004,40(11) :90~92.
[15]黄雪菊,王秀梅,郝常明.基于小波变换的图像分级压缩算法[J] .重庆邮电学院学报(自然科学版),Vol.18,No.4,Aug.2006:1~3.
[16]Lewis, A. S. and Knowles, G. Image Compression Using the 2-D Wavelet Transform [J], IEEE Trans. IP, vol. 1, no. 2, April 1992:244~250.
[17]Shapiro, J. M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients [J], IEEE Trans. SP, vol. 41, no. 12, Dec. 1993:3445~3462.
[18] A. Said and W. Pearlman, A new, fast and efficient image codec based on set partitioning in hierarchical trees [J], IEEE Trans. Circuits System, Video Technology, vol. 6,June 1996:243–250.
[19]David Taubman, High performance scalable image compression with EBCOT [J], Image Processing, IEEE Transactions on , Volume: 9 Issue: 7 , July 2000: 1158 ~1170.
[20] 张晓娣 等.新一代的静止图像压缩标准JPEG2000 [J]. 电信科学,2001(5).
[21] 靳济芳. Visual C++小波变换技术与工程实践[M]. 北京:人民邮电出版社,2004.
[22] 杨淑莹. VC++图像处理程序设计(第二版)[M].北京:清华大学出版社,北京交通大学出版社,2005.4~16.
[23] 吴乐南.数据压缩(第二版)[M].北京:电子工业出版社,2005.
150,19~22.

附录
主要程序:

基于分形图像编码的数据压缩算法的研究与实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-09-2009

标签:, , ,

0

摘要 I
ABSTRACT II
第一章 绪论 1
1.1研究背景 1
1.2内容安排 1
第二章 图像压缩编码技术 3
2.1图像压缩编码的必要性和可能性 3
2.2图像压缩编码方法简介 3
2.3图像压缩编码的国际标准 5
2.4图像压缩编码的评价方法 7
第三章 分形图像编码的理论基础 9
3.1分形理论的产生和发展 9
3. 2分形的定义和性质 10
3.3迭代函数系统 11
3.4带映射的局部迭代函数系统 14
第四章 分形图像编码算法研究 16
4.1分形图像编码简介 16
4.1.1介绍 16
4.1.2分形图像编码的基本原理 16
4.1.3分形图像编码的特点 17
4.1.4分形图像编码的发展趋势 17
4.2分形图像编码的基本算法 18
4.2.1编码 18
4.2.2解码 23
4.3分形图像编码的改进算法 24
4.3.1四叉树方法 24
4.3.2 HV划分和三角形划分 26
4.3.3 邻域搜索法 29
4.3.4 小波变换和分形结合算法 29
第五章 分形图像编码软件实现 32
5.1功能描述 32
5.2总体设计 32
5.3模块实现 33
5.3.1显示模块实现 33
5.3.2分形编码模块实现 35
5.3.3分形解码模块实现 39
5.4实验及讨论 41
5.3.1分形图像编码实验 41
5.3.2分形图像解码实验 43
第六章 总结与展望 46
6.1全文工作总结 46
6.2对分形图像编码的展望 46
参考文献 48
致谢 49

摘要

分形图像压缩编码是近年来迅速兴起的一种高倍率的图像压缩方法。它依据分形原理,利用迭代函数系统来抽取自然图像中的自相似性,达到压缩图像的目的;解码时利用拼贴定理来快速恢复图像。分形图像压缩编码以理论新颖,解码快捷而倍受关注。
本文首先介绍了图像压缩技术;其次对分形图像压缩理论的数学基础进行概述,并详细介绍了分形图像压缩的理论基础:迭代函数系统(IFS)、不动点定理、拼贴定理;然后重点介绍了分形图像压缩的基本原理、Jacquin的全自动分形图像压缩算法和四种分形编码方法的改进算法:自适应四叉树方法、HV划分和三角形划分法、邻域搜索法、小波变换和分形结合法。本文对这些压缩算法进行比较,给出了每种算法的优缺点。
通过计算机编程,本文采用Jacquin的方法对图像进行压缩编码与解压缩,给出了分形图像压缩的算法与具体实现。通过实验,研究了块尺寸与编码时间、压缩比以及重建图像质量之间的关系。实验结果显示,基于分形的图像压缩算法可以取得比传统编码算法更好的效果。

关键词:分形,图像压缩,迭代函数系统,分形图像编码

ABSTRACT

Fractal image coding has been an area of rapid expansion and increasing significantly in recent years, which is a high compression ratio images coding technique. It is based on a fractal theory of IFS to compress the image by exploiting the image redundancy through self-similar. And the decoding is rapidly by the Collage Theorem. It has received much attention from the research community for its desirable properties such as new theoretical background and fast decoding.
Technologies of image compression are first introduced in this paper. Then the mathematical principles of fractal image coding are presented generally, among which the theoretical foundations of fractal image coding: the theory of Iterated Function System, the Fixed Point Theorem and the Collage Theorem are introduced in detail, Besides, the author pay much attention to the fundamental principle of fractal image coding, Jacquin’s fractal image coding method and four kinds improved algorithms: self-adapted quadtree method, HV-partitioning and Triangular partitioning method, neighbor-region search method, fractal coding based on wavelet method. In this paper, the author also gives merit and demerit of each kind of these algorithms.
Through computer programming, Jacquin’s fractal image coding method is used to compress and decompress an image. The algorithm and realization of fractal image compression are given out. Through the experiments, the author researches on the relationship between the size of block and the coding time, the compression ratio, as well as the quality of reconstructed image. The experiments results show that the algorithm of fractal-based image compression can get better effect than other traditional coding algorithms.

KEY WORDS fractal, image compression, IFS, fractal image coding

第一章 绪论
1.1研究背景
进人21世纪,人类已步人信息社会,新信息技术革命使人类被日益增多的多媒体数字信息所包围,一个“信息爆炸”的时代已经来临。多媒体信息主要有三种表现形式,即文本、声音和图像。其中,图像作为最常见的信息存储方式,其表现形式生动而直观,能提供比其它形式数据更多的信息。在人类所接受到的全部信息中,大部分是通过视觉得到的。然而图像是三种信息形式中数据量最大的,若不经过压缩,数字图像传输所需的高传输速率和数字图像存储所需要的巨大容量将会是十分惊人的,因此对数据进行压缩十分必要。
图像压缩己研究了几十年,提出了诸如DPCM,DCT,VQ等压缩算法,并己出台了基于DCT等技术的国际压缩标准,如JPEG,MPEG,H.261等,图像压缩己得到较为广泛的实际应用。然而,随着人们对这些传统编码方法的深入应用,也逐渐发现了这些方法的许多缺点:比如高压缩比时图像出现严重的方块效应、人眼视觉系统(Human Visual System,简称HVS)的特性不易被引入到压缩算法中,等等。为克服传统压缩方法中的上述缺点,人们又在不断探索新的图像编码方法。经过十多年的发展,M. Kunt等人认为,目前有三种方法属于第二代图像编码方法:基于分割(Segment-based)的压缩方案、基于模型(Model-based)的压缩方案及基于分形(Fractal-based)的压缩方案[1]。
分形编码是二十世纪九十年代新兴的一种编码方法。由于其不同于传统的图像编码技术,具有较高的压缩比,被认为很有发展潜力。但是目前分形编码还存在着编码时间过长、编码效果有待提高等不尽人意的地方。因此,仍有进一步进行研究的必要。
1.2内容安排
本文对分形编码算法进行了深入地探讨和研究,共分为六章,各章的内容安排如下:
第一章简要介绍了课题的研究背景及内容安排。
第二章是图像压缩编码技术的综述。首先阐述了图像压缩的基本思想,然后介绍了常用的图像编码方法及图像编码的国际标准,最后简要说明了图像压缩方法的评价标准。
第三章主要介绍了分形编码方法的数学背景知识,包括分形的基本概念以及分形图像压缩所需要的一些数学理论基础。
第四章对分形编码算法进行了深入的探讨和研究。首先介绍了分形编码的基本原理和特点,分析了分形图像编码的特点。然后分形图像压缩算法进展进行深入研究,详细分析了Jacquin提出的分形编码方法,该方法为分形图像编码的基本方法。接着研究了几种优秀的改进算法,包括:自适应四叉树方法、HV划分和三角形划分法、邻域搜索法、小波变换和分形结合法。本文对这些压缩算法进行比较,给出了每种算法的优缺点。
第五章给出了分形图像压缩的具体实现。文中用分块的方法对图像进行分割,基于局部迭代函数的思想,采用分块的方法对给定图像进行压缩编码与解压缩。研究了块尺寸与编码时间、压缩比以及解压缩图像质量之间的关系。
第六章是总结与展望。对本文工作进行了总结,并探讨可以进一步深入研究的方向。

第二章 图像压缩编码技术
本章阐述了图像压缩的必要性和可能性,介绍了常用的图像编码方法及图像编码的国际标准,最后简要说明了图像压缩方法的评价标准。
2.1图像压缩编码的必要性和可能性
人类日常生活中所接收到的全部信息中,大部分是通过视觉得到的。和语音、文字等信息相比,图像包含的信息量更大、更直观、更确切。因而具有更高的使用效率和更广泛的适应性。众所周知,图像信息的数据量是相当庞大的。大数据量的图像信息会给存储器的存储容量、通信干线信道的带宽以及计算机的处理速度带来极大的压力。单纯靠增加存储器容量,提高信道带宽以及计算机的处理速度等方法来解决这个问题是跟不上需求的,因此就需要对图像进行压缩处理。
图像数据压缩的可能性是因为图像中像素之间,行或帧之间都存在着较强的相关性。图像编码与压缩,从本质上来说,就是对要处理的图像源数据用一定的规则进行变换和组合,从而达到以尽可能少的代码(符号)来表示尽可能多的数据信息的目的。从信息论的角度来看,压缩就是去掉信息中的冗余。即保留不确定的信息,去掉确定的信息(可推知的),也就是用一种接近信息本质的描述来代替原有冗余的描述。
2.2图像压缩编码方法简介
图像压缩编码的主要任务是去掉各种冗余和不相干的信息,保留有用的信息,将一个大的数据文件转换成较小的文件,以尽量少的比特数来表征图像,同时保持复原图像的质量,使它符合预定应用场合的需求。压缩数据量和提高有效性是图像压缩编码的首要目的。通常把图像压缩编码简称为图像编码,它是一种信源编码,其信源是各种类型的图像信息。图像恢复的过程叫做解码。根据解码后的数据与原始数据是否一致,图像压缩方法可以分为无损压缩编码[2]和有损压缩编码[2]。
一、无损压缩编码
无失真压缩编码,又称可逆压缩,压缩是可完全恢复的。这种压缩方法的基本思想是将输入的图像中表达像素点灰阶的值的每个符号,用规定的码字符号按一定的方式编排而成。由于规定的码字符比原始图像中的符号短,从而可用比较少的比特数来表达原始图像的符号,进而完成图像压缩的目的。在恢复图像时,我们只要把码字符与像素点的灰阶符号对应起来,就可以达到无失真地恢复图像。通常这类方法的可信度较高,但压缩比不高,一般介于1.7-2.1之间。常用的无失真压缩技术有[2]:
1.哈夫曼编码(Huffman Coding)
哈夫曼编码是由哈夫曼在1952年提出的一种编码方法。这种方法是根据信源中各种符号出现的概率进行编码,出现概率越高的符号,为其设计的码字越短,出现概率越小的符号,则其对应的码字越长,从而达到较少的平均码长。理论研究表明,哈夫曼编码是接近于信源熵的编码方法。
2.游程编码(RLE Coding)
在实际的信源符号流中,由于相邻符号间潜在的相关性,有些符号可能连续重复数次,表现出较高的冗余度,游程编码就是要设法利用这种冗余度。所谓游程就是指由信源符号构成的数据流中某个符号重复出现而形成的串的长度。其实,这样重复表示是没有必要的,我们只要简洁地给出了形成串的符号、串的长度,就能恢复出原来的数据流。游程编码就用二进制码给出上述信息的一类方法。
3.算术编码(Arithmetic Coding)
为了解决计算机必须采用整数位进行编码而使哈夫曼编码性能不佳,人们提出了算术编码的概念。该编码方法的基本思想就是将被编码的信息表示成实数0和1之间的一个间隔。也就是说,信源编码试图将任意的信息流与0, 1之间的间隔建立一一对应的关系。要表示的信息流越长,则表示它的间隔就越小,那么用于表示这一间隔所需的二进制位就越多。
二、有损压缩编码
限失真编码,又称不可逆压缩,指压缩后解码的数据与原始数据存在着一定的误差,恢复数据只是某种失真度下的近似,但不影响数据的主要信息。尽管这类方法的可信度不如无失真编码,但是可以获得较高的压缩比。为了充分利用图像中像素之间的相关性,以及考虑到人们视觉对图像灰度灵敏度的差异,限失真编码便成了压缩图像的重要手段。目前大多数压缩编码方法都属于这一类。一般说来,这种方法可达到2:1—1000:1的压缩比。常用的方法有[2]:
1.变换编码
图像的变换编码是图像编码的一个重要分支,是目前最有效、研究最热、应用最广泛的一类方法,即把原始图像通过一些变换后,得到在变换区域中系数具有比较低的熵值,然后再用无失真的编码把信息压缩进去。常用变换有多种:KLT(卡洛变换)、DCT(离散余弦变换)、SLT(斜变换)、DFT(离散傅氏变换)、WHT(沃尔什-哈达玛变换)、HRT(霍尔变换)等等。
2.矢量量化编码
量化是图像编码的重要环节,量化能够有效改变系数的分布特性,为后续的熵编码作好了铺垫。量化又分为标准量化和矢量量化两种。标准量化就是对单个参数进行映射和取整,在模—数转换和一般的编码系统中得到了广泛的应用。
矢量量化编码(VQ)是图像编码的一种高效的方法,它是一种基于图像块的编码方法,其编码原理为首先把图像分块,每一个块的像素组成一个矢量,然后再对矢量进行新的编码。我们注意到在图像中的很多块可能都比较相近,因而只要用一个矢量就可以代表这些块。通过聚类算法,就可以用比较少的码把原始图像恢复出来了。
3.预测编码
预测编码是图像压缩技术的重要分支,它的理论基础主要是现代统计学和控制论。在信息数据流中由于相邻象素点之间存在相关性,因此前面的数据和当前的数据之间存在某种相近性,预测编码就是试图利用预测值与原象素的灰阶值之差进行编码,以降低信源的不确定性,减少数码率。
预测编码的不足之处就是当传输过程中出现误码时,会导致解码图像中的大片区域失真。因此,预测编码要求可靠性很高的信道,一般要增加新的纠错编码。为了防止误码的扩散,可以每隔一定时间将预测系数设为零。
4.模型图像编码
模型图像编码的基本思想是把图像分成几个基本的模型,并通过分析获得模型参数,而解码时拟合重建图像。直接提取图像的描述是件很困难的事情,但是如果首先将输入图像模型化,那么对于该图像的描述就变成了参数的估计。也就是说,编码时,首先通过分析图像获得模型参数,而解码时,通过己知模型和量化的参数将图像重建。
5.分形图像编码
基于分形理论的图像压缩方法是介于矢量量化编码和模型图像编码之间的一种编码方法,但是它又有自己的特性,主要是充分利用了分形几何中的自相似原理,即把任意一幅图像看作一个分形,只要找到迭代函数的参数,那么就可以用迭代的方法把原始图像恢复出来。我们既然把原始图像近似的看作是分形,因而它属于限失真编码方法。
在我们实际的图像压缩编码系统中,往往是将无失真编码和限失真编码结合起来使用的,各种编码方法也可以交叉使用。
2.3图像压缩编码的国际标准
图像压缩编码技术的发展和广泛应用促进了许多相关国际标准的制定。国际标准化协会(ISO),国际电子学委员会(IEC)和国际电信联盟(ITU)制定了以下几个有关图像压缩编码的国际标准[3]:JPEG,MPEG,H.261/H.263。
一、 JPEG标准
在图像压缩领域,著名的JPEG标准是有损压缩算法中的经典。JPEG标准由静态图像联合专家组(Joint Photographic Experts Group,JPEG)于1986年开始制定,1994年后成为国际标准。JPEG以离散余弦变换(DCT为核心算法,外加Huffman编码、游程编码与Z排序,通过调整质量系数控制图像的精度和大小。对于照片等连续变化的灰度或彩色图像,JPEG在保证图像质量的前提下,一般可以将图像压缩到原大小的十分之一到二十分之一。如果不考虑图像质量,JPEG甚至可以将图像压缩到“无限小”。
JPEG标准的最新进展是1996年开始制定,2001年正式成为国际标准的JPEG 2000。与JPEG相比,JPEG 2000作了较大改进,其中最重要的是用离散小波变换(DWT)替代了JPEG标准中的离散余弦变换。在文件大小相同的情况下,JPEG 2000压缩的图像比JPEG质量更高,精度损失更小。
二、 MPEG标准
MPEG(Moving Picture Expert Group)是在1988年ISO和IEC联合成立的专家组,负责开发电视图像数据和声音数据的编码、解码和它们的同步等标准。这个专家组开发的标准称为MPEG标准,到目前为止,已开发的MPEG标准有:
MPEG-1 :数字电视标准
MPEG-2 :数字电视标准
MPEG-3 :已于1992年7月合并到高清晰度电视工作组
MPEG-4 :多媒体应用标准
1.MPEG-1标准
MPEG-1标准于1993年发布。它的设计思想是在1Mbit/s到1.5Mbit/s的低带宽条件下,提供尽可能高的图像质量(包括音频,以下所指图像均包括音频)。对家庭录影与商务资料存档来说,MPEG-1所提供的质量已经足够好。VCD使用MPEG-1标准,图像尺寸为352×288,标准带宽为1.2Mbit/s。
MPEG-1是针对运动图像的数据压缩技术,采用了帧内数据与帧间数据压缩技术。帧内压缩算法与JPEG大致相同,采用基于DCT的变换编码技术减少空间冗余。帧间采用预测和插补技术以减少时间冗余,为了提高压缩比甚至对于预测误差也进行DCT变换编码处理。
2.MPEG-2标准
MPEG-2标准是一个直接与数字电视广播有关的高质量图像和声音编码标准。MPEG-2可以说是MPEG-1的扩充,因为它们的基本编码算法都相同。但MPEG-2增加了许多MPEG-1所没有的功能,例如运动向量的精确度提高到半个像素;由于关键帧里存在特殊向量,扩展了错误冗余;离散余弦变换中可选择精度;超前预测模式;质量伸缩性(在同一视频流中可容忍不同质量的图像);支持VBR;提供了位速率的可变性能(scalability)功能;增加了隔行扫描电视的编码。MPEG-2要达到的最基本目标是:位速率为4-9Mbit/s,最高达15Mbit/s。
3.MPEG-4标准
MPEG-4标准是目前最新的图像格式标准之一。完整的MPEG-4是一个多媒体通信的框架和规范协议,其中的视频编码算法的设计思想是在极低带宽和可变输出码率(lOKbit/s到1Mbit/s)的条件下提供尽可能好的图像质量。此外,对MPEG-4来说,由于网络传输的不确定性,数据传输的完整性、正确性也显得非常重要。因此MPEG-4在移动多媒体通信中也占据了关键地位。
MPEG-4标准最不同从前编码算法的是基于对像的编码算法。它按对像组织图像内容。也就是说,它把图像内容分解成一个个的对像单元,对这些对像单元可以进行单独的存放和处理,并改动他们的相对位置。
它是为视听(audio-visual)数据的编码和交互播放开发算法和工具,是一个数据速率很低的多媒体通信标准。MPEG-4的目标是要在异构网络环境下能够高度可靠地工作,并且具有很强的交互功能。
三、H.261与H.263
H.261是为ISDN的电视/电话会议制定的标准。它可以根据传输线路的带宽来调整图像质量,以达到刚好吻合的程度。H.261的传输速率为64Kbit/s、128Kbit/s直到384Kbit/s (P×64Kbit/s)。
H.263和H.263+是H.261的后续标准。比之H.261,它提高了运动补偿的精度,常用于超低速率的图像传输,例如可视电话等。
2.4图像压缩编码的评价方法
在图像压缩中,为了提高压缩比有时会舍弃图像里一些不太重要的细节,所以原始图像与重建图像之间会存在着某些差异。差异的大小,意味着恢复图像质量的不同。因此,我们常常需要有对信息损失的测度,用以描述重建图像相对于原始图像的偏离程度,即评价压缩后图像质量的标准,但是由于人的视觉冗余度,对有些差异灵敏度比较差,也就相应地产生了两种判别标准。一种是客观判别标准[2],它是建立在原始图像和重建图像之间的误差基础之上;另外一种是主观判别标准[2],也就是用人的肉眼来识别图像的还原效果。
一、主观方法
主观方法就是由观察者依靠自己的视觉对经过压缩处理之后的恢复图像进行质量评价。在具体做法上,有时可由一组观察者分别对所评价的同一恢复图像进行打分,然后按照一定规则得出一个总的评价结果。
主观标准的具体规定为:
1) 极好 — 图像具有极高的质量,和你所想象的一样好;
2) 良好 — 图像质量高,能供满意的观察,干扰并不令人讨厌;
3) 通过 — 图像具有可以接受的质量,干扰并不令人讨厌;
4) 勉强 — 图像质量低劣,但你还希望改善它,干扰有些令人不愉快;
5) 低劣 — 图像质量很低劣,但还能观看,干扰确实令人讨厌;
6) 不能用 — 图像差的无法观看。
尽管这种方法使用起来不够方便,对观察者的知识水平有一定的要求,有时不同的观察者会得出不同的评价结论,但主观方法仍是最可靠的,这是因为图像的最终接受者是人的视觉。
二、客观方法
客观方法就是定义一个数学公式,然后对待评估的图像进行运算,得到一个唯一的数学量作为测度结果。一般用下面的指标参数来客观评价一种图像压缩方法的优劣。
1.均方误差(MSE)

其中 是大小为M×N的原始图像, 是大小为M×N的恢复图像。
2.峰值信噪比(Peak Singal to Noise Ratio)

其中 为图像的最大灰度值,例如,对于具有256个灰度级的黑白图像, 通常为255。在压缩比一定的情况下,PSNR越大表示压缩效果越好,反之越差。当PSNR超过30dB时,人的主观感觉很难找出压缩前后的差异。
3.压缩比 (Compress Ratio)

其中n为原始图像的总数据量, 为压缩编码后的总数据量。
另外还有处理时间,实现的难易程度等。一个好的压缩方法可能不是以上指标都优于其他压缩方法,但它应该是各个指标的一个较优的折中。

第三章 分形图像编码的理论基础
分形几何学是由曼德勃罗特(Mandelbrot)在20世纪70年代创立的,是现代非线性科学中十分活跃的一个数学分支。其研究对象是自然界和非线性系统中出现的不光滑和不规则的几何形体。它既有深刻的理论意义,又有巨大的实用价值,在自然科学的各个领域都有着广泛的应用。近年来,分形理论在信号处理、模式识别、图像编码、自然图像的模拟等领域取得了很大的发展。本章主要介绍分形的基本概念以及分形图像压缩所需要的一些理论基础。
3.1分形理论的产生和发展
1975年, Mandelbrot出版了《Fractal: Form,Chance and Dimension》[4],可以翻译为《分形,机遇和维数》。标志着“分形”作为一门科学正式成立。分形及其理论涉及的领域非常广泛,其应用已经深入到许多应用领域。“分形”己成为当代科学中最有影响力和感召力的基本概念之一,分形理论也成为非线性科学的生长点之一。分形理论的基础和主要内容是分形几何。分形几何的研究对象是理论和现实中不规则的几何图形。例如,曲折的海岸线、多变的云彩图案、参差不齐的金属表面以及涨落无常的股价曲线等等,这些令经典几何束手无策的现象和状态,均可用分形几何加以描述、解释和研究。分形几何的核心概念之一就是分数维和局部与整体的对称性(自相似性)。分形几何还为研究混沌动力系统的“奇怪吸引子”现象提供了直观的几何语言。近几十年来,分形几何学已成为探讨复杂和无序现象的强有力的数学工具,被各个学科分支中的学者们广泛的应用着。它同孤立子理论、混沌理论一起被誉为二十世纪后期的非线性科学的三大理论突破[5]。
分形理论的发展大致可分为三个阶段[5]。第一阶段为1925年以前:该阶段发现了一些典型的分形集合,同时,为了刻画这些集合的性质,产生了Hausdorf测度和Hausdorf维数,这些概念说明了度量一个无特征长度(所谓特征长度是指所考虑的集合对象所含有的各种长度的代表者)的几何对象时,必须依赖度量方式和度量的尺度单位。第二阶段是从1926-1975年:在这半个世纪中,人们对分形的性质做了较为深入的研究,特别是维数理论的研究已获得了丰硕的成果。在此期间,产生了覆盖维数和熵维数等概念。第三阶段是从1975年至今:在此期间,分形理论和应用都取得了全面发展,分形几何作为一门学科正式诞生。在分形理论方面,维数的估计与计算的算法、分形集的生成与结构、分形的随机理论、动力系统的吸引子理论、分形的局部结构已获得较深入的研究结果。在应用方面,分形在物理的相变理论、材料的结构与控制、力学中的断裂和破坏、高分子链的聚合、模式识别、自然景物的模拟、霉的生长模拟等领域取得了令人瞩目的成果。当计算机科学特别是计算机图形学应用到分形领域后,它为分形的研究提供了方便的、有效的工具,并且促使分形理论和应用有更多的新发现。
3. 2分形的定义和性质
何谓分形呢?事实上,到目前为止分形还没有严格的数学定义,只能给出描述性的定义。粗略地说,分形是对没有特征长度(所谓特征长度,是指所考虑的集合对象所包含的各种长度的代表者,例如一个球,可用它的半径作为它的特征长度),但具有一定意义下的自相似性的结构的总称。自相似性,即某种结构或过程的特征从不同的空间尺度或时间尺度来看都是相似的,或者某系统或结构的局部性质或局部结构与整体相似。按照统计的观点,分形在通常的几何变换下具有不变性,即它的每一部分经平移、旋转、缩放变换后与其它的任意部分相似。
分形(fractal)的概念,最初是由美国IBM公司的数学家Mandelbrot引入的[6],意为破碎的,不规则的。曾经有人尝试给出分形的严格的数学定义,但是所提出的定义都不够全面和精确。因此,下面给出分形的描述性定义。
定义3.1 分形F是具有以下性质的集合:
(1) F具有精细的结构,即有任意小比例的细节。
(2) F是不规则的,以至于不能用传统的几何语言来描述。
(3) F通常有某种自相似性,可能是近似的或统计的。
(4) F在某种方式下定义的分形维数,通常大于它的拓扑维数。
(5) 在大多数情况下,F 可以非常简单的方式定义,可以由迭代产生。
为了对分形的自相似性及构造过程有个直观的了解,下面给出一给经典分形Koch 曲线的构造过程(如图3.1所示),并简单说明其构造原理[5]。

图3.1 Koch曲线的构造过程
Koch 曲线,是Helge Von Koch于1904年构造的。其构造步骤为:首先,将一单位线段三等分,并截去中间的1/3部分,代之以边长为1/3的60度角;然后,再对每一条1/3长的线段重复上述过程,直至无穷,所得曲线即为Koch 曲线。
Koch 曲线是包含于有界区域内的无限长曲线,它是数学领域中处处连续、处处不可微曲线的典型代表。
3.3迭代函数系统
一些特殊的分形可以由计算机图形学和数学构造两方面提出,其中最简单的一类,称为自相似集。1977年曼德勃罗特用初始和标准折线的迭代过程来构造这类集。到1981年,Hutchinson推广此迭代过程,并首先引入了迭代函数系统(Iterated Function Systems,简称IFS)[7]。巴恩斯利又把IFS的思想应用于图象压缩中。IFS在分形图象压缩的发展中起着引导的作用。分形图象压缩的大多数工作都是基于IFS或它的推广。
一个分形集一般都由无限多个点组成,它们的分布又是如此的复杂,以至于不可能通过直接给定每个点的位置来描述它。因此,通过“各部分之间的相互关系”来定义它,而迭代系统可达到这样的目标。
为了定义迭代函数系统,先要介绍“分形空间”[8]和“压缩映射”[8]基本概念。
一、分形空间
为了简单起见,只讨论R2中的分形,并把研究分形理论的基本空间记为(X,d),
其中X是R2中的非空闭子集;d是X中的度量,可以取为欧氏距离,即对任意 ,其距离d(x,y)是:

在定义了距离d以后,空间(X,d)就成为度量空间。一般情况下,还要求基本空
间是完备的,即该空间中的任意一个Cauchy序列的极限仍然属于该空间.
设(X,d)就是一个完备的度量空间,并记X中所有的非空紧子集(即有界闭集)的全体记作H(X),我们可以把H(X)中的任意一个元素想象成X中一幅黑—白图形的集合,因此,任意一幅图形都可以由H(X)的一个子集来表示,该子集所有的点都是黑色的,其它地方是白色的,所以空间H(X)包含有数量十分巨大的元素。现在定义H(X)上的度量,即任意两幅图形(子集)之间的“距离”(称为豪斯多夫距离,记作h)它依赖于基本空间X的度量d
定义3.2 两个子集间的豪斯多夫度量h定义为

其中,从点x到子集B之间的距离定义为

在有了上述的定义后,可以得出下面的结论:如果(X, d) 是完备的度量空间,则(H(X),h) 也是完备的度量空间。
二、压缩映射
自相似性是分形图像的一个十分重要的性质,许多分形图像都是由一些与整体以某种方式相似的部分组成的,例如Koch曲线是由四个与之相似的部分组成的。这些自相似性不仅是这类分形的性质,实际上可以作为它们的定义,这是一种十分有用的性质。
定义3.3(压缩映射定理) :设w: X→X是基本空间(X,d)上的一个映射。如果存在一个正的常数c<1,使

则称w为(X,d)上的压缩映射,c称为压缩因子。
我们根据该定义对一幅笑脸图像F经压缩映射w后变为较小的笑脸w(F)。我们可以发现,变换后的w(F)上的两只眼睛比原始图像F上的更加靠近了许多。实际上,压缩映射总是把原始图像上的一对点变换到距离更近的一对点(如图3.2所示).

图3.2 压缩映射w
根据定义 3.3及压缩映射的性质可以得出下面的结论。
结论1 设w: X→X是基本空间(X,d) 上的一个压缩映射,压缩因子是c。对任
意B∈H(X),则由下式

定义的映射 :H(X)-> H(X)是分形空间(H(X),h) 上的压缩映射,且压缩因子也是c,
即对任意A和B∈H(X)有下式成立

结论2 设 是(H(X),h)空间上的n个压缩映射,其压缩因子分别为 现在定义一个新的映射W: H(X)→H(X),即对于任意的B∈H(X)有:

则W是压缩映射,且压缩因子 。即对任意A,B∈H(X)有:

三、迭代函数系统
定义3.4(迭代函数系统)[8]完备的度量空间(X,d)以及n个压缩映射 :X→X(其压缩因子分别为 )一起,就组成了一个迭代函数系统,简称IFS,记做 . 称为IFS的压缩因子。
下面介绍两个重要定理,是分形图像压缩的主要原理。
定理3.1(不动点定理)[8]:设 是(X,d)上的IFS,则
1.由下式定义的变换W:H(X) →H(X),即

是完备度量空间(H(X),h)上的压缩映射其压缩因子也是c,即

2.压缩变换W存在唯一的不动点 ,满足

且不动点可以通过迭代而得到,即

其中 ,而
在迭代函数系统中,表达不动点集A∈H (X)称为IFS的吸引子,所以压缩映射的不动点定理又称吸引子定理。该定理充分地说明了对于一个迭代函数系统,一定存在一个唯一的不动点,并且生成该迭代函数系统的不动点时与初始图像无关,因此给定一个R2上的迭代函数系统,就能唯一的确定一幅图像。
但在计算机图形学中,特别是计算机图像压缩技术中,更有意义的问题是:对任意一幅图像,能否找到一个R2上的迭代函数系统,使得该迭代函数系统的吸引子就是该图像或者近似于该图像。
定理3.2(拼贴定理)[8]:设(X,d)是完备的度量空间,给定集合 和数ε>0,如果选到一个IFS (0≤c<1),使

其中h为Hausdorff距离,而 是该IFS的不动点(又称为吸引子)。
根据迭代函数的定义可知,一个IFS就是一组压缩映射的集合。而由不动点定理可以得知,它确定一个唯一的不动点。不动点 是从复制它自身的变换W( )构造出来的,所以我们取给定的集合L,对它作压缩变换,然后把它们粘贴到一起以便重新构造集合L。不动点的唯一性是非常重要的,因为假定给出L而能找到W (或者假定给出W,我们能够找到集合L),使得L=W(L),则一定有L= ,即L就是W的吸引子。而拼贴定理告诉我们,即使我们粘贴得不能使之精确地符合,在原始集合L和粘贴后的“拼贴”W(L)之间较好地符合,不动点也将十分接近于L.
四、仿射变换
仿射变换[8]是一类重要的变换,n维欧氏空间 中的仿射变换 具有这样的形式: ,其中A为 上的线性变换,b是 中的一个矢量。因此,仿射变换是平移、旋转、伸缩以及反射的组合。
定义3.5一个变换 如果具有如下形式,

其中a,b,c,d,e,f是实数,则称 是二维仿射变换。若它的线性部分是压缩的,则该仿射变换就是压缩的。
平面线性变换有四种特例: — 按比例缩放, — 伸长, — 剪切, —旋转。

任一平面仿射变换都可分解为这四种变换之乘积。
3.4带映射的局部迭代函数系统
有了迭代函数系统,便可以构造分形。当己知一个二维的IFS ,
就可用计算机构造出相应的分形,这在图像压缩技术中称为解码,即由一组仿射变换的系数迭代出图像。具体算法如下:
1、任选初始图形 作为输入;
2、复制 ,令 ,输出 ;
3、将 作为输入,重复第二步,输出 ;
4、依次迭代,得最终图形 ;
实际中的许多的图像都不是具有分形性质的图像,例如人脸,它并不包含很多的自相似性,但图像的局部小区域中,自相似性是广泛存在的,即图像的某一部分和另一部分是相似的。图3.3是图像压缩中标准的Lena图,可以发现Lena肩上一部分与和其重叠区域中更小的一部分是几乎相同的,而帽子中的一部分与镜中帽子的一小部分在经过旋转和改变灰度后是相似的。人身上,如耳朵、脸颊等多处地方都存在着至少是近似的相似性。近似的相似性是指,局部图像块经过仿射变换和拼贴后,和另一图像块之间并非是完全一致的,而是存在一定的误差。利用这些仿射变换,通过IFS产生的分形图像可以近似地模拟原始的图像。根据拼贴定理,只要拼贴得越接近原始图像,则产生的分形图像就越接近原始图像。

图3.3 Lena头像的局部自相似性
因此需要将IFS方法进行推广,引入局部迭代函数系统[8]。要解决灰度问题,还需增加一个映射 ,函数f(x,y)代表位置(x,y)上的灰级。
定义3.6 设(X,d)是完备度量空间, .局部迭代函数系统(LIFS)即为下列压缩映射集: .LIFS再加上灰级的映射就构成带映射的局部迭代函数系统(LIFSM).
我们把 划分为许多块。设 和 是 的子集又设 : 是一组映射。
定义 3.7设 为IFSM.
定义 3.8 设映射 ,记 , ,如果存在一个正实数s 定理3.3如果 是 压缩的,则 ,是空间 的压缩映射。

第四章 分形图像编码算法研究
4.1分形图像编码简介
4.1.1介绍
分形图像编码这一概念是由美国乔治亚工学院的数学家M.F.Barnsley于1987年提出的[9]。之后,在1988年M.F.Barnsley和A.D.S loan发表了一篇题为“A Better Way to Compress Images”[10]的文章,在此文中,他们首次将M.F.Barnsley提出的IFS理论应用到图像压缩编码中,并获得了较好的压缩效果,压缩比高达10000: 1。但是这个方法存在的最大不足就是在压缩过程中需要专业技术人员的人机交互操作。尽管如此,它的极有希望的压缩效果和压缩比使人们看到了用分形理论解决图像压缩问题的前景和希望。
1990年,M.F.Barnsley的博士生A.E.Jacquin首次提出了一种全自动的分形图像压缩方法[11],完成了分形图像压缩从需人工参与编码到自动编码的飞跃,从此分形图像编码作为一种很有希望的编码方法列入计算机图像自动编码的行列,得到了人们的普遍关注。各国学者纷纷效仿A.E.Jacquin的压缩方案提出各种各样的改进方案,从而掀起了分形图像编码的高潮。
4.1.2分形图像编码的基本原理
分形图像压缩,利用了分形理论中的迭代函数系统理论。编码的过程是依据拼贴定理,通过给定的图像,寻找一组压缩仿射变换,使其构成的迭代函数系统逼近给定的吸引子,然后记录下相应参数,并且用这些参数作为图像的编码进行存储和传输。解码过程首先是由存储或传输的参数确定一组压缩仿射变换,进而构造一个迭代函数系统,并求出这个迭代函数系统的吸引子,根据吸引子定理,该迭代函数系统的吸引子就是原始图像的近似——解码图。这就是分形图像压缩的基本原理和方法。其编解码原理框图如图1所示。

图4.1 分形编解码原理框图
4.1.3分形图像编码的特点
自从1990年A.E.Jacquin应用局部迭代函数系统实现了分形图像的自动压缩以来,人们对分形编码进行了不懈地研究,提出了许多改进方法,这些方法主要针对Jacquin方法中的两大缺点,一是编码计算量大和编码时间较长;二是压缩比不够理想进行改进。改进后的方法同JPEG相比,无论是压缩比,还是解码图像质量方面都具有一定的优势,而且随着分形图像编码研究的不断发展,这种优势还会愈加明显。
现将分形图像压缩的优点归纳如下[12]:
压缩原理新颖:在分形图像编码中,利用原始图像局部和局部的自相似性构造一个迭代函数系统,并使该系统的吸引子尽可能逼近原图像;在解码过程中,只需要该迭代函数系统对任意初始图像不断迭代就可以重建图像。分形图像编码是一种特殊的矢量量化,不需要码表 。
压缩比高:由于自然界的景物图像中都存在着确定的或统计的自相似性,而分形图像编码算法恰恰利用了原始图像的自相似性,因此分形图像编码通常都能获得较高的压缩比和信噪比。
解码效果好:在解码时能去除锯齿效应,而且图像可以被放大到任意尺寸,能保持图像的细微结构即与分辨率无关。
发展速度快:分形图像编码技术从提出到现在才仅仅十几年的时间,但其发展速度之快令人惊讶——国际上发表的文献逐年增加,商业化的软件、硬件己在市场上出售。
“金无足赤”,分形图像编码也存在着编码时间长,压缩比在无人工干预的情况下不够高等不足。但是,随着计算机各方面技术特别是人工智能技术的不断发展并取得突破后,分形图像编码克服时间长的不足,达到极高倍的压缩比并不是不可能的事。
4.1.4分形图像编码的发展趋势
分形图像编码是目前公认的最有前途的编码方法之一。分形图像编码对信源的先验知识要求极少,不必对图像进行先验统计得出最佳方案,作为一种新的图像编码方法,它考虑了图像中更多的信息,非常适合那些存在大量的自相似性或自仿射性的图像。为了解决分形图像编码的不足,需寻找新的突破点,未来的分形图像编码研究将在以下几个方面进行[12]:
1.综合分析当前自动编码的各种算法,在此基础上,继续寻找较快编码速度,提高压缩比、改善压缩效果的突破性的改进方案。
2.研究按分形维数分割图像、将分形维数相同的区域块用分形方法进行编码的理论、方法和实现的算法。
3.继续寻找分形编码与其它编码方法相结合的新的编码方法,特别是与小波分 析相结合的编码方法。
4.2分形图像编码的基本算法
1990年,A.E.Jacquin发表了一种基于方块划分的分形图像压缩方案。这是一种基于IFS的压缩编码方案,准确地说是基于Local IFS的压缩方案。该方案突破了M.F.Barnsley设计的方案,将图像分割成两种大小固定的方块,然后去找这两种方块之间的相似性,由于不再与整幅图像比较,而放宽为原始图像的一部分,从而使该方案能够自动对任意图像进行编码。首次实现了自动分形图像编码方法。以后其他学者提出的方案都是基于此方案的改进,因此A.E.Jacquin的方案被公认为最基本的分形图像编码方案[2]。
4.2.1编码
在A.E.Jacquin提出的编码方案中,分形图像编码分为三个步骤:
(1)对待编码图像I进行分块。
把 大小的待编码图像I分割成若干个不重叠的、大小为 的子块,称之为值域块,记为 。这些值域块的并集能够完全的覆盖整个图像,即当 , ,且 。然后再把待编码图像分割成若干个可以重叠的、大小为 的子块,称之为定义域块,记为 。要求 ,一般来说 。对原始图像的划分如图4.2所示:

(a)值域块 (b)定义域块
图4.2 分形编码分块表示图
(2)找到合适的迭代函数系统。
根据LIFS理论,寻找一个IFS,使得 ,使得 即 和I在Hausdorff测度下尽可能的接近,因为 ,所以实现时,只需要 与 在Hausdorff测度下尽可能的接近。因此,分形图像编码的关键是如何找到最佳的仿射变换和定义域块 。在实际应用中,仿射变换 难以找到、存储,而是把仿射变换 等价分解为紧缩变换 、同构变换 和灰度变换 ,即

紧缩变换 :我们用 来表示起始位置为 ,大小为 的定义域块 。用 来表示经过抽样后,起始位置为 ),大小为 的定义域块 。通过下式:

要求:

紧缩变换把大小为 定义域块几变换大小为 的定义域块 ,即 。这里的 。
同构变换 :同构变换就是4种对折、4种旋转变换。我们以子块X的中心位置为坐标原点,水平方向为x轴,向右为正方向;垂直方向为Y轴,向上为正方向,来说明这几种同构变换。其中,用i,j来表示规定坐标轴中的坐标值。
1、 恒等变换: 如图4.3所示

图4.3(a)恒等变换前的图像 (b) 恒等变换后的图像
2、 顺时针旋转90度: 如图4.4所示

图4.4(a)旋转前的图像 (b) 旋转后的图像
3、 顺时针旋转180度: 如图4.5所示

图4.5(a) 旋转前的图像 (b) 旋转后的图像
4、 逆时针旋转90度: 如图4.6所示

图4.6(a) 旋转前的图像 (b) 旋转后的图像
5、 关于主对角线对折: 如图4.7所示

图4.7(a)对折前的图像 (b) 对折后的图像
6、 关于反对角线对折: 如图4.8所示

图4.8(a) 对折前的图像 (b) 对折后的图像
7、 关于水平中间线对折: 如图4.9所示

图4.9(a) 对折前的图像 (b) 对折后的图像
8、 关于垂直中间线对折: 如图4.10所示

图4.10(a) 对折前的图像 (b) 对折后的图像
经过同构变换后,产生 。即 。
灰度变换 :灰度变化包括比例因子 和补偿因子 ,对 做灰度变换 ,产生 。
对每一个定义域块经过以上三种变换,就得到一个数量很大的定义域池。对值域块 的分形编码就是寻找最佳 , , 以及在定义域池里找到最佳的定义域块 ,我们选择MSE来度量块之间的距离,使得下式最小:

和 分别为值域块R和经过前两种变换后的定义域块 的像素值。
(3)保存分形变换参数。
当最佳仿射变换 , , 及定义域块 找到以后,经过量化,然后存储其参数。对每一个值域块R都找到一组分形代码,就得到整个图像的分形代码。分形图像编码三个步骤如图4.11所示。

图4.11 分形编码过程示意图
由以上步骤可以看出,假设我们处理一个256×256象素的图像D,每个象素的灰度分为256级,因此我们可把这许多象素分成个8×8象素的1024个互不交迭的小方块 。再做16×16的小方块 ,它们是可以互为交迭的,这样的 总共达 个。对于每一个 ,要在D中寻找一个 ,使它们之间的距离极小化,即找到图像的一个小部分使其看起来很像上述的 上的图像。。又有8种方法映射 到 ,这意味着对1024个 中的任意一个要有8×58081个比较。这样必然导致计算量很大且复杂,编码过程需要很长的编码时间。
为了缩短编码时间,提高压缩比,1992年,A.E.Jacquin发表一篇文章,提出改进。这种方案根据图像子块(值域块和定义域块)的复杂性,把它们分成了三类:
平滑子块:即灰度变化平缓的子块,由于这类子块的灰度十分接近,对这类子块的编码就只需要存储平均灰度。
中等复杂子块:即灰度有一定的变化,但是不含有边缘,对这类子块,旋转和对折的意义不大,因此,为了提高压缩比,省略旋转和对折。
边缘子块:即块内灰度变化大,且含有边缘,需要上面介绍的所有步骤。
对于给定的值域块,首先确定它的类别。如果此值域块为平滑子块,就只需要计算出它的平均值,不需要在定义域集里进行搜索;如果此值域块为中等复杂子块,由于8种变换的意义不大,因此减少了要搜索的定义域块数目;如果此值域块为边缘子块,则需要做所有的编码过程。由以上分析可知,这种分类方案可以加快编码速度,而图像的质量基本不变。
4.2.2解码
分形解码方法的解码较为简单。由分形编码方法的数学原理可知,在编码过程中所得到的迭代函数系统IFS是紧缩的,它的吸引子可以通过对任意初始图像的不断迭代变换而得到。从严格的数学角度来说,需要迭代无数多次才能得到吸引子。但是在实际应用过程中,只需要迭代有限次N后即可收敛,在进行N+1迭代,图像的质量只是轻微的变化。一般情况下,N=8。图4.12显示了初始迭代图像为一幅全黑图时,分形图像解码的8次迭代结果:
迭代初始图像 N=1 N=2 N=3 N=4

N=5 N=6 N=7 N=8
图4.12初始迭代图像为一幅全黑图像时,分形图像解码的8次迭代结果

为了验证分形解码对初始图像的任意性,图4.13给出了初始图像为“Lena”像,分形图像解码的8次迭代结果:

迭代初始图像 N=1 N=2 N=3 N=4

N=5 N=6 N=7 N=8
图4.13 初始图像为“Lena”,分形图像解码的8次迭代结果
由以上两幅图可知,解码图像迭代8次以后,图像的质量几乎不改变了。
4.3分形图像编码的改进算法
分形图像编码的关键在于寻找值域块 和定义域块 两者的匹配,既要精度高又要速度快,这样才能在编码速度和图像还原质量间取得良好的平衡。由于分形图像编码属于分块算法,在图像还原的时候,还将出现“方块效应”,会影响了图像的还原质量。所以编码算法还需要设法尽可能地消除“方块效应”产生,以提高图像质量。
下面介绍主要的几种改进算法,以及它们之间的优缺点。
4.3.1四叉树方法
四叉树方法是1991年由Fisher提出的[13],它具有分块灵活性高,压缩比率高的优点。四叉树方法是一种自适应分块的方法。它将图像表示成一棵四叉树,树根就是原图像本身,除叶节点外,树中每个节点均有4个子节点,分别对应于原图像(或图像块)4个象限的子块,如图4.14所示。

图4.14 四叉树分割图
图像自适应分块的目的是将图像合理地划分成不同尺寸的值域块,使任意一块都能找到合适的定义域块与之相应。这样图像中粗糙的部分能以较大的图像块进行变换压缩,提高压缩比;而图像中精细的部分以较小的图像块进行变换压缩,保证较高的图像还原质量。和经典方法相比,四叉树方法能进一步提高压缩比。图4.14显示了标准的Lena图经过四叉树方法分割后的图像。

图4.15 lena图的四叉树分割
实际运用中,往往对值域块和定义域块设置最大值,一般可将值域块分为16×16, 8×8和4×4三级,定义域块一般为值域块大小的四倍。值域块和定义域块比较的过程中,如两者的均方差(MSE大于阀值,则值域块一分为四,在下一级的值域块中再搜寻最佳匹配的定义域块,直至值域块不可再分或找到最佳匹配的定义域块时为止,并进行相应的编码。在比较前,需要对值域块和定义域块进行分类。四叉树方法采用2级的分类体系。首先将待分类块一分为四,如图4.15所示。然后分别计算每个子块中的灰度值总和经过八种仿射变换可以将其归为以下的三种类型:

(1)
(2)
(3)

主类1 主类2 主类3
图4.16按1/4块的均值分类情况
以上是第一级的3个主类。再根据四个子块的灰度值总和进行排序,可得24个子类。每个主类各有24个子类,则所有图像块都可分类到3个主类下的24个子类之一中去,即将整幅图像的所有图像块分成72个子类。以后搜索最佳匹配的过程中,只有同类的值域块和定义域块才进行比较,以加快编码的速度。
两级的分类体系,大大减少了定义域块的搜索范围。确定块类型时,根据图像块的分类情况可确定最佳的变换种类,节省了变换的编码时间。虽然增加了分类预处理,但分类过程中的部分数据在匹配过程中可重用,所以预处理所占时间对整个编码时间的影响是非常小的。因此Fisher的四又树算法在保证了图像恢复质量的同时,提高了分形压缩的编码时间。
四叉树方法存在一些缺点。首先是不能预估图像的压缩比,它的压缩比和原始图像的图像特点相关。其次,它增加了算法复杂度。大的值域块计算MSE和变换参数时需要的计算量大大增加。多级的匹配在遇到精细图像时,需要将值域块不断细分,浪费了上几级值域块的大量匹配工作,而且实际多数的编码值域块都是小尺寸的。最后,四叉树的阀值选取也是一个问题,只有选择合适的阀值才能保证压缩比和图像还原质量的平衡。
四叉树方法有许多改进的方法。一类是改进四叉树方法的分类标准,分出更多的类,同时尽量考虑根据图像特点进行划分。如预处理时间少而分类精确度高,则能使编码速度进一步提高,且图像质量下降少。另一类方法则是设定图像块分解时的自适应阀值。精细图像将分解为小的图像块编码,而粗糙图像则直接匹配。这样可尽量地消除四叉树方法中的计算冗余,发挥四叉树方法的优点
4.3.2 HV划分和三角形划分
Jacquin方法在划分图像块时,为计算机处理方便,将所有图像块都划分成方形。这样的处理虽易于实现,但它没有考虑到图像本身的特点。分形编码是寻找局部图像间的相似性,和图像内容有很大关系,即要求值域块和定义域块应尽量依据图像的特点划分。HV划分[14]和三角形划分[15]就是这样的方法。
HV划分是一种灵活的分块方法,它将图像块分成水平方向或垂直为向上的矩形图像块。无论是水平还是垂直分块,它都将原来的图像块一分为二,新的较小区域和原来的较大区域在形状上有一定的相似性。图4.16显示了HV分割的原理。
图4.17 HV分割
图4.16(a)中所示图像块中有一条对角线,(b)图中垂直分块将图像块分成 和 两部分, 中对角线贯穿整个图像块,而 区域中没有对角线。(c)图中再
在水平和垂直方向上进行三次分割,将其分为四个区域。显然 、 和 ,是相
似的, 、 和 是相似的。重复这种分割步骤,直至到允许的最小尺寸为止。
M×N大小图像块的具体划分由下式决定:

其中 表示图像块(i,j)位置时的灰度值, , 找
出图像块中使 和 最大的j和i如果 ,在j位置水平分割,如果 在i位置垂直分割。整幅图像分割完时,可获一个树形结构,存储所有分割的图像块,除最小尺寸的图像块外,每个图像块都存在着两个子节点。图4.17显示了Lena图经HV分割后的图像。

图4.18 Lena图HV分割后的图像。

搜索时按值域块搜索定义域块,定义域块应至少是值域块的两倍,如匹配误差小于设定值,则停止搜索,记录编码后转到下一值域块,否则分解为下一级值域块,分别搜寻最佳的定义域块,直至最小一级的值域块。
HV分块根据图像特点分割,能提高压缩比,恢复图像时避免方块效应产生,获得更好的图像还原质量。但它的树形结构比四叉树更复杂,且定义域块和值域块形状不同,变换时比较复杂,因此并不能很大程度上提升编码的速度。
和HV划分相似的方法是三角形划分,它将图像块分割成为大小不等的三角形。三角形能精确地按照图像的特点进行分割,同时三角形也便于图形上的处理。图像的所有像素点都设置一个标志位,记录该像素点是否为三角形的顶点。
三角形划分的具体过程如下所示,它由一些分割步骤和一个合并步骤组成:
(1)初始化三角形,通过网格将图像分割成大小相同的三角形;
(2)扫描所有三角形的顶点,重新确定三角形的分布。
(3)计算各个三角形的灰度均值,方差和面积,
(4)如果三角形方差大于预设的方差阀值E,而且三角形的面积大于预设的面积阀值T,则进行分割,即将三角形重心的像素点设置为三角形顶点。
(5)重复步骤(2)(3)(4),直至所有三角形的方差和面积均小于预设值为止。
(6)此时进行合并,如果一个三角形顶点组成的所有三角形的灰度均值都在一定
的灰度范围中,即它们最大的灰度均值差小于预设的阀值,则进行合并,就是将这个三角形顶点去除。图4.18显示了Lena图进行三角形分割的过程。

图4.19 Lena图进行三角形分割的过程
(a)三角形初始化(255) (b)第一次分割(734) (c)第二次分割(971)
(d) 第三次分割(3720) (e)合并(1867)
三角形划分可以将图像中的纹理区全部分割到较小的三角形中,而灰度比较平均,也就是低频图像信号较多的区域划分到尽量大的图像块中。三角形划分仅对值域块进行处理,定义域块还是划分成方形,因此匹配时需要将定义域变换为值域块的形状。三角形划分对图像的分割比HV划分更加细致,因此压缩比更高,还原图像的质量更好,基本消除了方块效应。但是三角形划分的算法更加复杂,值域块数量增加,因此编码速度没有得到大量的提高。
4.3.3 邻域搜索法
大量的统计实验表明,图像块之间的相关性随着图像块距离增加而变小。从图像内容而言,越是接近的图像块,图像内容的相似程度也就越高。邻域搜索就是建立在图像块之间存在近期效应的前提下[16]。
邻域搜索在搜索最佳匹配块时,仅在值域块的8邻域内选择相应定义域块进行匹配。这样就可减少匹配的工作量。对于值域块在图像中的不同位置,8邻域的定义如4.19所示。
图4.20 值域块8邻域定义
(a)中间 (b)左上角 (c)右上角 (d)左下角 (e)右下角
(f)上边 (g)下边 (h)左边 (i)右边

邻域搜索将定义域块搜索的范围大大缩小,可以大大地提高编码速度。但邻域搜索的缺点也是明显的,并不是所有图像都具有近期效应的,所以邻域搜索仅对部分图像是有效的,对于其他图像则会导致图像还原质量的大幅下降。
4.3.4 小波变换和分形结合算法
数字图像经过小波变换后可以得到图像块在水平、垂直和对角线上的细节信息。图像块中最难处理的就是不同方向上的纹理,根据小波变换可以简单地获取纹理图像的方向信息,因此能够简单而精确根据图像块的信息进行编码。小波变换和分形编码的结合算法就建立在这样的基础上[17]。
小波变换和分形结合算法首先使用小波变换对值域块和定义域块分别进行M层分解。分解结果如图4.20所示

图4.21对 大小的图像块进行M层小波分解
可以得到值域块和定义域块的多分辨率系数表为:

其中 和 都仅有一个系数,称为值域块和定义域块的直流分量,它们是值域块和定义域块的灰度均值,其他下标相同的分量是值域块和定义域块在相同频段中的分量。可将空间域中值域块和定义域块的匹配转化到MCF域中。通过 和 可得到比例因子 和补偿因子 ,由小波理论可知,图像块间的匹配误差就是计算正交小波分解后各频段的误差之和,即

由于图像的能量分布在各频段是不均匀的,因此可以采用从低分辨率开始累加误差并逐次与阀值比较的方法。
可以将MCF(R)分解成四个部分:
(1)直流分量:
(2)水平分量:
(3)垂直分量:
(4)对角线分量:
这时 代表值域块在各频段的水平纹理信息, 代表垂直纹理信息, 代表对角线纹理信息。将定义域块也分成相应的 , , 。在实际匹配时不需要将 和 整体进行匹配,而是对不同的分量分别进行匹配。当匹配误差小于阀值,就将相应的值域块分量、定义域块分量和变换系数记录编码。所以在小波域中的匹配实际是将值域块按照方向剖分为三个部分,在每个部分中分别确定一个仿射变换。当搜索到的 和 时,这三个仿射变换就是经典意义下的分形块方法。
如果在小波域中,值域块的分量依然无法找到合适的匹配时,就需要将该分量继续剖分,再搜索相应的定义域块和对应的变换。在小波域中的剖分过程与在空间域的四叉树方法相似。设对 进行剖分,先记录 值,然后将 进行“四叉树”分解,将每个系数矩阵一分为四,将其分别标记为1,2,3,4,然后按照标号将各频段信号重组为四组信号,然后再进行搜索。
解码的过程比较复杂。需要先将定义域块进行小波变换,然后值域块根据压缩文件的数据,找到相应 的水平纹理、垂直纹理和对角线纹理消息,按照相应的变换系数变换后得到值域块的 ,和压缩文件中的 一起组成 。再进行小波的逆变换,得到值域块的图像数据,完成一次迭代。经过多次迭代后,就得到了解码图像。
小波变换和分形结合算法的优点在于,大的值域块往往难以找到匹配的定义域块,而通过小波变换在三个方向上寻找匹配的定义域块,可以大大增加匹配成功的机率,同时也可以降低匹配误差。所以小波变换和分形结合算法可以获得比普通的分形算法更高的压缩比,更好的图像还原质量,同时由于大的值域块能够更多地得到匹配,所以总的搜索工作量会有所下降,能够适当地提高编码速度。
它的缺点在于解码时非常复杂,每次迭代数据的时候都要进行一次小波的正变换和逆变换,所以解码需要用较多的时间,同时编码的算法也比较复杂。

第五章 分形图像编码软件实现
本章主要对软件实现的功能进行分析,从而设计出软件的各主要模块,并介绍各模块要实现的功能。
5.1功能描述
一、基本功能:
1、可以导入并显示jpeg,bmp,jpg等格式的图片
2、对导入的图片进行分形压缩编码,生成码本文件
3、导入码本文件,解码重建图像
二、扩展功能:
1、能选择不同尺寸的值域块和定义域块对图像进行压缩
2、编码时以进度条的形式动态显示压缩进度
3、压缩完显示压缩用时和压缩比等信息
5.2总体设计
本软件主要由显示模块、分形编码模块及解码模块组成,其中编码模块是核心模块。如图5.1所示。

图5.1 软件模块
1)显示模块
该模块使用Java中的Swing工具包来实现,该模块包括两个部分——图像显示和控制按钮。图像显示部分用来展现压缩前和压缩后的图像,控制按钮用来控制程序的运行过程。图像显示部分包括:压缩前图像显示面板和压缩后图像显示面板。控制按钮包括:文件的导入和导出、“压缩”和“解压缩”按钮、值域块大小参数的输入。该模块实现的用户图形界面。
2)分形编码模块
该模块为核心模块,实现了分形图像编码的基本算法,即Jacquin的编码方案。
把 大小的待编码图像I分割成若干个不重叠的、大小为 的子块,称之为值域块,记为 。这些值域块的并集能够完全的覆盖整个图像,即当 , ,且 。然后再把待编码图像分割成若干个可以重叠的、大小为 的子块,称之为定义域块,记为 。要求 ,本软件采用 。
按这样的分割后,值域块的块数 ,定义域块的块数 。对于每个值域块 找到最佳的仿射变换和定义域块 ,使得两者MSE(均方误差)最小。
3)分形解码模块
该模块对输入的码本文件译码形成IFS代码,通过任意初始图像迭代计算恢复出原始图像。
由分形编码方法的数学原理可知,在编码过程中所得到的迭代函数系统IFS是紧缩的,它的吸引子可以通过对任意初始图像的不断迭代变换而得到。从严格的数学角度来说,需要迭代无数多次才能得到吸引子。但是在实际应用过程中,只需要迭代有限次N后即可收敛,在进行N+1迭代,图像的质量只是轻微的变化。本软件的迭代次数采用8次。
5.3模块实现
本节通过详细介绍各模块是如何实现的来说明软件功能的实现。并给出了详细的设计思路和完整的程序流程图。还简要介绍了模块与模块之间的联系。
本次设计开发语言选择Java,Java是一个广泛使用的网络编程语言 ,它是一种新的计算概念。首先 ,作为一种程序设计语言 ,它简单、面向对象、不依赖于机器的结构、具有可移植性、鲁棒性、安全性、并且提供了并发的机制、具有很高的性能。其次,它最大限度地利用了网络 ,Java的小应用程序 (applet)可在网络上传输而不受CPU和环境的限制。另外 ,Java还提供了丰富的类库 ,使程序设计者可以很方便地建立自己的系统。
开发工具选择Eclipse,它是一个开放源代码的、基于Java的可扩展开发平台。
5.3.1显示模块实现
显示模块由FractalGuiPanel类实现,该类调用了ImageDisplayingPanel类和ControlPanel类的实例。ImageDisplayingPanel实现了导入图像的显示面板。ControlPanel包含了各个控制按钮和压缩信息的显示。FractalGuiPanel类调用这两个类的对象,通过使用box布局管理器,实现整体的用户图形界面。
FractalGuiPanel类主要代码如下
public class FractalGuiPanel extends JPanel implements IGui,
IControlPanelListener
{
private ImageDisplayingPanel refImagePanel;
private GuiController controller;
private ControlPanel controlPanel;
private ImageDisplayingPanel retrievedImagePanel;
public FractalGuiPanel()
{
refImagePanel = new ImageDisplayingPanel();
retrievedImagePanel = new ImageDisplayingPanel();
Dimension d = new Dimension(256, 256);
refImagePanel.setPreferredSize(d);
retrievedImagePanel.setPreferredSize(d);
controlPanel = new ControlPanel(this);
this.setLayout(new BorderLayout());
this.add(controlPanel, BorderLayout.SOUTH); //加入controlPanel面板
Box box = Box.createHorizontalBox(); //创建一个从左到右显示其组件的 Box
box.add(refImagePanel); //加入压缩前图像显示面板
box.add(retrievedImagePanel); //加入压缩后图像显示面板
this.add(box, BorderLayout.CENTER);
}
public static void main(String[] args)
{
JFrame frame = new JFrame(); //创建新的框架
FractalGuiPanel panel = new FractalGuiPanel();
frame.getContentPane().add(panel); //在框架中加入FractalGuiPanel
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.show(); //显示界面
}
}
该模块实现的用户图形界面如图5.2所示

图5.2 用户图形界面
5.3.2分形编码模块实现
该模块为核心模块,实现了分形图像编码的基本算法,即Jacquin的编码方案。
把 大小的待编码图像I分割成若干个不重叠的、大小为 的子块,称之为值域块,记为 。这些值域块的并集能够完全的覆盖整个图像,即当 , ,且 。然后再把待编码图像分割成若干个可以重叠的、大小为 的子块,称之为定义域块,记为 。要求 ,本软件采用 。
按这样的分割后,值域块的块数 ,定义域块的块数 。对于每个值域块 找到最佳的仿射变换和定义域块 ,使得两者MSE(均方误差)最小。
实现该模块的流程图如图5.3所示

N
N

Y
N

Y

N

Y

图5.3编码模块流程图

DestinationImage类和ReferenceImage类实现了值域块和定义域块的分割,其中定义域块大小是值域块的两倍。块的大小由用户从图形界面上输入。
SFormList类定义了八种同构变换,其中包括了将定义域块大小缩小为值域块大小的紧缩变换。
Metric类用来度量两个像素的差异。
FractalImageModel类用来保存编码参数,编码参数由最佳定义域块的位置、同构变换的系数、灰度变换系数等构成。
压缩结束后返回CompressionResults对象,该对象用来保存压缩比,压缩用时等信息。这些信息在用户图形界面上显示。
FractalCompressor类实现了分形压缩,该类调用了以上各类的对象和对象的方法,压缩的核心代码如下所示:
synchronized void compress()
{ int error, beta, s, x, y, diff;
ImagePanel destRegion, refRegion, bestRegion;
SForm tSForm;
Metric tMetric;
int bestError, bestBeta, bestSForm;
mCompressorRunning = true;
// 获得度量两个像素之间差异的对象
tMetric = new Metric(2, mDestImage.MAX_PIXEL_DEPTH);
bestSForm = bestBeta = 0;
bestRegion = null;
// 初始化
prepareImages();
prepareSForms();
int numDestRegions = mDestImage.numberOfDestPanels();
int numRefRegions = mRefImage.numberOfRefPanels();
mFractalImageModel=newFractalImageModel(mDestImage.getXPanels(), mDestImage.getYPanels(),mDestImage.getDestPanelAt(0).getPanelSize());
int numSForms = mSFormList.getNumberOfSForms();
SForm[] sforms = mSFormList.getSFormArray();
// 值域块循环
for (int numDest = 0; numDest < numDestRegions; numDest++)
{ destRegion = mDestImage.getDestPanelAt(numDest);
bestError = 0x7FFFFFFF;
// 定义域块循环
for (int numRef = 0; numRef < numRefRegions; numRef++)
{ refRegion = mRefImage.getRefRegion(numRef);
// 平均亮度差异
beta = destRegion.getMean() - refRegion.getMean();
// 八种同构变换循环(包括了紧缩变换)
for (s = 0; s < numSForms; s++)
{ error = 0;
tSForm = sforms[s];
//每个像素循环,计算误差
for (x = 0; x < mPanelSize; x++)
{ for (y = 0; y < mPanelSize; y++)
{ diff = destRegion.getPixel(x, y) - tSForm.getTransformedPixel(x, y,refRegion);
error += tMetric.getDistance(Math.abs(diff - beta));
}
}
if (error < bestError) //误差小于设定值,则为当前最佳定义域块
{ bestError = error;
bestSForm = s;
bestBeta = beta;
bestRegion = refRegion;
}
}
if (bestError == 0)
break;
}
//获得当前值域块的编码参数,保存到mFractalImageModel对象中去
mFractalImageModel.addFractalCode(newFractalCode(bestRegion,bestSForm, bestBeta));
mPercentDone = (100.0 * (numDest + 1)) / numDestRegions;
if (listener != null)
listener.updateProgress(mPercentDone);
}
5.3.3分形解码模块实现
分形解码过程首先是由编码参数确定一组压缩仿射变换,进而构造一个迭代函数系统,通过若干次迭代求出吸引子,根据吸引子定理,该迭代函数系统的吸引子就是原始图像的近似——解码图。本软件选择的迭代次数为8次。
该模块的程序流程图如图5.4所示

图5.4 解码模块流程图
该模块实现较为简单,关键代码如下所示:
public class FractalDecompressor
{ public void getNextImage(FractalImageModel pImageModel,
DestinationImage pDestImage, int pPanelSize)
{ // 获得原始迭代图像
ReferenceImage refImage = new ReferenceImage(pDestImage,
FractalCompressor.GAMMA);
refImage.prepareRefRegions(pPanelSize);
pDestImage.prepareDestRegions(pPanelSize);
// 值域块循环
int totalDestRegions = pDestImage.numberOfDestPanels();
ImagePanel destRegion, refRegion;
FractalCode fractalCode;
SForm sForm;
int x, y;
double scaler = (1.0 * pPanelSize) / pImageModel.getPanelSize();
for (int i = 0; i < totalDestRegions; i++)
{
destRegion = pDestImage.getDestPanelAt(i);
fractalCode = pImageModel.getFractalCode(i);
// 获得最佳定义域块的位置.
x = (int) (scaler * fractalCode.getX() + 0.49);
y = (int) (scaler * fractalCode.getY() + 0.49);
if (x >= refImage.getXPanels())
x = refImage.getXPanels() – 1;
if (y >= refImage.getYPanels())
y = refImage.getYPanels() – 1;
refRegion=refImage.getRefRegion(x+y*refImage.getXPanels());
// 获得同构变换参数
sForm = fractalCode.getSForm();
sForm.prepare(pPanelSize);
// 从定义域块变换到值域块
short val;
for (x = 0; x < pPanelSize; x++)
for (y = 0; y < pPanelSize; y++)
{ val = (short) (sForm.getTransformedPixel(x, y, refRegion) + fractalCode.getBeta());
if (val < 0)
destRegion.setPixel(x, y, (short) 0);
else if (val > 255)
destRegion.setPixel(x, y, (short) 0xFF);
else
destRegion.setPixel(x, y, val);
}
}
}
}

5.4实验及讨论
根据以上分析,进行程序设计,程序编码运行时和程序解码结束如图5.5所示
(a) 程序编码运行时截图 (b) 程序解码结束时截图
图5.5 程序截图
5.3.1分形图像编码实验
实验中采取原始图像大小为256×256,灰度为256级的标准 Lena头像,取不同尺寸的值域块和定义域块对图像进行压缩。实验结果如表5.1和图5.6所示。

值域块大小 定义域块大小 压缩比 PSNR
4×4 8×8 3.1:1 30.8
6×6 12×12 7.1:1 29.5
8×8 16×16 12.1:1 26.6
10×10 20×20 19.2:1 23.5
12×12 24×24 26.6:1 19.6
表5.1不同尺寸的值域块与定义域块压缩结果

(a)原始图像(bmp格式) (b) 值域块大小4×4

(c) 值域块大小6×6 (d) 值域块大小8×8

(e) 值域块大小10×10 (f) 值域块大小12×12
图5.6不同值域块与定义域块尺寸时的图像压缩
从以上结果可以看出值域块尺寸越大,图像分割所得的值域块数目越少,压缩所需的时间越短,压缩比越高,相应地每个像素所需的比特数越少,但与此同时,计算所得到的误差越大,图像的失真越明显。在值域块的尺寸不是特别大时,压缩后失真小,所得到的图像质量很好。
5.3.2分形图像解码实验
对编码所得到的IFS进行迭代,可以逐步得到原始图像的近似图像。当然,恢复后的图像与原始图像之间有一定的误差。图像一般通过几次到十次迭代就可以得到不动点,迭代次数越多,所需的解压缩时间也就越长。在这里以值域块尺寸为 4×4,定义域块尺寸为8×8为例对图像进行解压缩,得到结果如图5.7所示。

(a)迭代0次 (b) 迭代1次

(c) 迭代2次 (d)迭代3次
(e)迭代4次 (f) 迭代5次
(g)迭代6次 (h) 迭代7次

(i)迭代8次
图5.7 256×256的Lena头像分形解码结果

各次迭代的结果对应的PSNR如表5.2所示:
迭代次数 1 2 3 4 5 6 7 8
PSNR(dB) 10.46 14.77 19.00 23.90 27.77 29.84 30.61 30.80

表5.2不同迭代次数的解压缩结果
从以上结果可以看出,迭代次数越多,所得到的解压缩图像越接近不动点,一般图像经过5到8次次迭代就可以得到不动点,但相应地所需的解压缩时间也就越长。

第六章 总结与展望
6.1全文工作总结
本文研究了分形的基本理论以及分形图象压缩的方法。通过编程,采用分块的方法对给定图像进行压缩编码与解压缩,给出了分形图像压缩算法的具体实现。通过实验,研究了块尺寸与编码时间、压缩比以及解压缩图像质量之间的关系。实验结果显示,基于分形的图像压缩算法可以取得比传统编码方法更好的效果。从实验结果可以看出,值域块与定义域块的尺寸与图像压缩比以及重建图像质量密切相关。块取得越大,编码时间越短,压缩比越大,但与此同时失真越大,因此重建图像质量也就越差,反之亦然。块尺寸的选取要根据具体图像及应用场合来确定。
但是,分形图像压缩编码方法还存在许多不足,严重地影响了图像的压缩比和重建图像的质量。本文针对加快编码速度以及如何提高重建图像质量等方面介绍了一些改进措施。在编码搜索方法上,可采用邻域搜索法来减少搜索所需时间,而不需要对每一个定义域块进行搜索。在提高重建图像质量方面,可采用自适应四叉树法、HV 划分和三角形划分法。另外,可以充分利用小波变换的优点,采用将分形与小波变换相结合进行图像压缩。
6.2对分形图像编码的展望
近些年来 ,图像压缩编码领域的研究十分活跃,而基于分形理论的图像压缩编码是一门崭新的编码技术,它冲破了传统编码方法的理论框架,以潜在的高压缩比和良好的重建图像质量,引起了编码界研究人员的广泛关注。分形图像编码方法的研究方兴未艾,挖掘分形编码潜在的高压缩比性能,克服其搜索量大的不足,将是推动这一压缩编码方法到实际应用的新的研究课题。由于分形编码起步较晚,目前的理论与技术还需完善,今后的研究可从围绕以下几方面进行:
(1)探索原图像的分割和分类的新方法。一方面完善己有的图像分割方法,另一方面寻找更好的图像分割和图像块分类方法。对于图像分割目前主要有固定块分割、四叉树分割、HV分割以及不规则块分割等。尽管固定方块分割方案实现简单,但编码质量不是很理想,不能自适应于不同的图像,也不能自适应于同一图像的不同细节。四叉树分割方案虽然有一定的图像自适应性,且描述四叉树分割的成本也很小,但它对图像的适应性仍然是有限的。HV分割和不规则分割对图像重建较好,但复杂度较高。因此,研究一种更强的自适应分割方案是一个重要的问题。
(2)减小值域块和定义域块匹配搜索的计算量,加快编码速度。研究值域块与定义域块的特点寻找更有效的搜索方法,完善非搜索的分形编码,进行匹配搜索的并行算法研究。这主要涉及匹配搜索问题,因为在分形编码阶段,匹配搜索占据了主要的编码时间。全搜索固然能够得到最好的编码质量,但全搜索的运算量大是不争的事实。加快分形编码速度的关键是设计好的搜索方案,这是分形图像编码实用化的核心问题。
(3)混合编码研究。将分形编码和其它编码方法(如矢量量化、小波、神经网络等)相结合的混合编码方法己经显示出巨大的发展潜力。分形编码技术已进入与其它编码技术结合的新时代,国外许多学者都在积极寻找新的突破口。目前与分形编码技术结合最为成功的,应该是矢量量化技术与小波技术。
(4)进行分形在视频压缩中的应用研究。视频图像存在时间冗余,分形编码在视频编码方面应该会有良好的效果。
(5)加强分形编码的软、硬件研究,加快其实用化进程。

参考文献
[1]Luis Torres, M.Kunt. Video coding :the second generation approach[M]. Kluwer academic publisher ,1996
[2]吴乐南. 数据压缩[M]. 北京:电子工业出版社,2000.3-5
[3]马小虎,张明敏,严华明.多媒体数据压缩标准及其实现[M].北京:清华大学出版社,1996
[4]Mandelbrot. Fractal: Form, Chance and Dimensions [M]. San Francisco: Freeman,1977
[5]李水根,吴纪桃.《分形与小波》[M].北京:科学出版社,2002
[6]Mandelbrot. The Fractal Geometry of Nature[M]. San Francisco: Freeman,1983.
[7]M.F.Barnsley, S.Demko. Iterated function system and the global construction of fractal[J]. Proc.Roy.London.1985.A (399).243-275
[8]陈守吉,张立明.分形与图象压缩[M].上海:上海科技教育出版社.1998.
[9]M.F.Barnsley. Chaotic Compression. Computer Graphics World, Nov.,1987
[10]M.F.Barnsley, A.D.Sloan A Better Way to Compress Images. BYTE,Jan 1988:215- 223
[11]A .E.Jacquin.a novel fractal block coding technique for digital image. Processing ICASSP,1990:2225-2228.
[12]赵耀,王红星,袁保宗.分形图像编码研究的进展[J].电子学报,2000,28(4)
[13]Y.Fisher. Fractal Image Compression: Theory And Applications[M]. Springer-Verlag 1995
[14]B.Dzerdz,M.O.Ahmad. Adaptive Fractal-based Algorithm For Image Compression. Canadian Conference on Electrical and Computer Engineering, 1995, Sponsored by IEEE.
[15]F.Davoine, J.Svensson, J.Chassery.Mixed Triangular And Quadrilateral Partition For Fractal Image Coding, IEEE International Conference on Image Processing,1995
[16]皮明红.邻域匹配和分类匹配的分形块编码[J].中国图象图形学报, 1997,05: 314-317
[17]张哎,陈刚,基于小波分解和方向剖分的分形图像压缩方法[J],浙江大学学报,Vol32 ,No.1, 1/1998

基于KL变换编码的数据压缩算法的研究与实现

Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-09-2009

标签:, , , ,

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.