【毕业学位论文】（Word原稿）基于GHA学习算法的图像压缩研究-计算机科学与技术软件技术

I 电 子 科 技 大 学 毕业设计（论文）任务书 拟题单位 电子科技大学计算机学院 审题人 蒲晓蓉 题目全称 基于 习算法的图像压缩研究 主要任务： 本文研究了 习算法的 理论基础，并给出 基于 习算法的图像压缩程序 发实例，最后对其性能进行测试。 起止时间： 2005年 3 月 1 日至 2005年 6 月 10 日 学生姓名 张湛 专业 计算机科学与技术软件技术 班次 21082010 指导单位 电子科技大学计算机学院 指导教师 蒲晓蓉 设计地点 学校 成果形式 论文 2005 年 6 月 12 日 录 摘要 . . . 一章 引 言 . 1 人工神经网络 . 1 络拓扑结构 . 2 练方法 . 2 统 图像压缩 . 4 像压缩算法 . 5 像压缩应用领域 . 7 像压缩质量客观评价标准 . 7 第二章 主元分析神经网络 . 8 元分析算法（ . 8 元分析神经网络模型 . 9 物学模型 . 9 学模型 . 11 元分析神经网络学习算法 . 11 机学习算法 . 12 局收敛的主元分析学习算法 . 13 行提取多个主元的学习算法 . 13 第三章 基于 法的图像压缩系统的分析与实现 . 17 序流程 . 17 统实现 . 20 第四章 系统性能测试 . 31 主观评价 . 31 客观标准评价 . 36 第五章 结论 . 39 参 考 文 献 . 40 致 谢 . 45 附录 . 46 附录一 代码 . 46 . 46 . 46 . 48 . 49 . 50 . 51 于 习算法的图像压缩研究 作者： 张湛 班级： 21082010 班 指导老师： 蒲晓蓉 指导单位： 计算机科学与工程学院 摘要： 在传统的 有损图像压缩 领域中， 主要 采用的是 基于 的压缩 算法，而本文 提出 了一种基于 神经网络的 学习算法 的 有损 图像压缩 方法， 这种方法借助了 法在线压缩的特性 ，具有自学习能力 。本文 研究了 习 算法的理论基础， 并 给出 发实例， 最后 对其 性能 进行测试 。 关键词： 人工 神经网络、主元分析 、 法 、 有损 图像压缩 is in In we a of of We HA it we 1 第一章 引 言 在生物神经网络理论的影响下，人们已经在开发智能系统的 方面取得了很多进展，于是人工神经网络应运而生，目前主要被用来研究关于模式识别、预测、优化、联合存储和控制这些领域的问题。虽然在这些领域， 已经有一些成功地的系统 被开发出来，但是 这些系统都非常大的局限于最初设计的环境 ，无法解决 或者需要花费很大功夫在最初的系统设计上才能解决相似 的问题。而人工神经网络， 提供了一种以 智能的 方式 来解决各种问题 的可能，很多问题领域都可以应用其来解决 。 人工神经网络 人工神经网络 （ ，是对于生物神经网络 （ 的电子仿真。 早在 20 世纪四十年代，人工神经网络领域的先锋 立了著名的 型，开启了第一轮人工神经网络的研究。然而，在六十年代， 于单神经元的局限性的论文 以及异或（ 无法表示 使得学术研究人员 进入 了集体反思 的 过程。直到八十年代初期 后 ，人工神经网络才重新为人们所关注，其中主要的研究成果包括 ， ，以及提出的 法。 生物神经 元 ( 是由胞体（ 两种外延树状分支：轴突（ 枝蔓（ 成的 ，胞体包含一个胞核存储遗传信息。神经元通过枝蔓接受别的神经元传递过来的脉冲信号，通过轴突传递胞体产生的脉冲信号。这些轴突一般都有分支，在这些分支末端便是是突触（ 两个神经元的交互的基本单位。 见图 2 当脉冲信号 到达突触末端的时候，会产生一种称为神经传递素（ 物质，神经传递素穿过突触间隙，根据突触的类型来减 弱或者加强神经元本身的 是否准许脉冲信号通过的倾向。而对于突触来说，不断地对于过往行为的学习会不断地改变该突触的行为，从而也就形成了存储功能。 人工神经网络正是对于此“学习（训练） 改变（适应）”过程的模拟。 我们将从网络 拓扑结构 、训练方法 、实际应用 等方面来 讨论 人工神经网络 。 络 拓扑结构 人工神经网络可以抽象为加权有向图，其中人工神经元表示为节点而 人工神经元对于输入输出的改变表示为加权边。通常人工神经网络 拓扑结构 有以下两种： 1 前向网络（ 抽象为无环图，又可以 分为： 1) 单层 感知器 （ 2) 多层 感知器 （ 3) 络（ 2 反馈网络（ 抽象为有环图，又可以分为： 1) 竞争网络 （ 2) 络（ s 3) 络（ 4) 同的网络拓扑结构决定了网络不同的特性。一般来说 ，前向网络是静态的，对于一组输入只会产生一组输出，因此这也决定了前向网络是无记忆性的，也就是对于输入的反应与之前的网络状态无关 ；而反馈网络则是动态的，也就是有状态的网络，对于每次输入，除了计算出相应的输出外，由于网络拓扑的特性，同时也会更新网络的状态，也就是改变相应的权值。 练方法 学习能力，也就是训练能力，是人工神经网络的基础。学习（训练）过程也就是更新和改变网络结构和权值的过程，这个过程的目的就是为了能够更加有效地完成特定的任务。人工神经网络通过对学习样本的训练，不断地改进自身结构从而使得输出与期 望值之间的差距不断趋小。这种学习（训练）能力也正是人工 3 神经网络最为超越传统解决方法的方面，也是智能的最好模拟。 在这个学习过程中，有两个考量： 1. 学习范例（ 可以分为三种类别： 1) 有 监督 学习（ 提供样本的期望输出值，网络根据比较真实输出值与期望输出值来修改结构和权值 2) 无监督 学习（ 不要求提供样本的期望输出值，网络探索潜在的数据之间的关系 3) 混合（ 有 监督 学习 和无 监督 学习的混合 2. 学习规则（ 1) 误差修正规则（ 误差修正学习规则属于前面所提到的有 监督 学习 ，即提供样本的期望输出值以比较误差，从而修改网络 。 考虑训练样本 . . . . 1对每一个义误差信号 然后使用不同的算法来 使用 例如感知器学习算法： I. 使用小的随机数初始化权值和阙值 （ 使用训练样本 T 对网络进行训练 根据 1更新权值 。 其中 是 增益（ ；式 （ 1 2) 则（ 是一个有二进制值构成的循环网 络，其中 1 表示“开”而 示“关”。其中，也就是它的“对称”特性。 为它也是减少误差，只不过 是计算输出的相关矩阵的差 ： 3) 则（ 习假设是最为古老的学习规则，它基于生物科学中所观察到的事实 如果在突触两边的神经元都同步且重复地激活，那么该突触 强度会加强。数学上的表示如下式： 1 习规则的一个重要特点就是它是一个局部学习算法，也就是说对于一个突触来说，其权值的改变仅由该突触两边所连接的神经元 4 所决定。这个特点很大程度上降低了算法复杂度，从而比较容易 用 4) 竞争学习规则（ 与 习规则不同，采用竞争学习规则时，一次只产生一个有效输出 元 ，也就是 被称为 “ 的 现象。在一组输出元中，每个输出元 相互 竞争取得有效权 。生物神经元上确实存在这 种竞争现象。 考虑一个简单的竞争学习网络，它是一个单层网络，每个输出元且每个输出元还与其它输出元相连接。 如下图所示： 在竞争过程中，只有最大（或者最小）的输出元就是 ,。一个简单的 竞争学习规则可以是： 0, 注意到只有一个胜利者的权值会被应用上式来更新 。 统 图像压缩 目前被人们采用的图像文件格式有很多种，原因主要有： 1. 针对不同的图像类型 2 维 /3 维，黑白 /灰度 /彩色，实数 /整数 ； 2. 历史和公司 协会所有， 3. 压缩算法 4. 带宽限制 网络视频会议 ； 5. 存贮能力 高清晰 大医学图像数据库； 6. 有限数据取得 海量 指纹比对； 下面我们将就 传统 图像压缩算法和 图像压缩应用领域 作详细研究。 5 像 压缩算法 一般来说，图像压缩算法有两个大类：无损压缩和有损压缩。其中无压缩指压缩过程中不丢失原始信息的、可以完全恢复的压缩算法；而有损压缩指压缩过程中为了减少信息所占用的空间而选择性的丢失部分原始信息、不能够完全恢复的压缩算法。 下面先讨论常用的无损 图像 压缩算法： 1. 码与 码 码根据熵与信源的理论，采用从上到下的方法，按照符号出现的概率进行排序，然后按照递归方法分为两个部分进行编码。 码采用从下到上的方式编码，也是按照符号出 现的概率进行排序。 码虽然也是变长编码，却不需要另外的同步代码，这一点优于 码。 2. 算术编码 在算术编码中，消息用 0 到 1 之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0 到 1 之间。编码过程中的间隔决定了符号压缩后的输出。 算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。 而 在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地 进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。 3. 行程编码 （ 现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的 颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用 (示，具有相同颜色并且是连续的象素数目称为行程长度。 4. 词典编码 般在 开始时不知道要编码数据的统计特性，也不一定允许事先知 6 道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码 (术就是属于这一类。 词典编码 (根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多，归纳起来大致有两类： 第一类是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。如 法。 第二类是企图从输入的数据中创建一个“短语词典 (of 。编码数据过程中当遇到已经在词典中出现 的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。如著名的法。 常用的有损 图像 压缩算法： 有损图像压缩一般是在减少数据量的同时尽可能的使信息损失最小化，一般有损图像压缩算法是试图丢失那些不容易为人眼识别出来的信息的数据。比如，有损 像格式采用 丢失掉图像中的那些 高频信息的数据量，从而达到压缩的目的。 有两种基本的有损压缩方案：变换编码和预测编码。采用变换编码时，图像被分成小的区段，然后变换到新的域里，再进行离散量化，最后熵编码（比如 码）；而预测编码一般用 来对数据流（比如图像流或者声音流）进行编码，这里不做讨论。 有损压缩在压缩比上要优于无损压缩。并且，虽然有损压缩在比特值上使得原始数据和压缩数据有不少差别，但是在人类感知程度上却能够保持一个很好的近似。 1. 散余弦变换。离散余弦变换是一个类似于 散傅立叶变换的傅立叶相关变换，与离散傅立叶变换不同的是， 它只使用实数。 在实际应用中，由于 时间复杂度为 2一般采用时间复杂度为 速傅立叶变换来代替。 2. 小波变换 。 和傅立叶变换只与频率有关不同的是，小波变换是时域与空间域相关的，也就是能够反映出空间上和时间 7 上发生的变化。 小波变换的时间复杂度仅为 )(甚至快于快速傅立叶变换的 )小波变换除了在图像压缩方面的应用外，还主要应用于信号 处理领域。小波变换有以下种类： 续小波变换， 散小波变换， 速小波变换。 像压缩应用领域 很多时候，需要从远程的图像数据库中查找比对图像，比如人脸数据库、远程指纹比对 、轮胎图片数据库 等。在这些情况下， 由于数据 海量 和网络带宽的原因，需要 不可能将所有数据库内的图像都通过网络传输至客户端进行查找比对操作，因此 往往由服务器端负责完成图 像查找比对 的工作 ；或者需要图像能够有一个压缩比非常大的算法，而这些算法又要满足快速查找的需求。 这样，就需要对图像的格式按照查找比对所需要的特征进行专门设计 ，并且对算法的压缩比有特别设计要求。 像压缩质量客观评价标准 对于图像压缩质量的客观评价标准，一般用的有两个指标：均方差（ 峰值信噪比（ 均方差（ 就是 衡量误差均方的指标。数学定义如下： 21 1),(),(1 E 峰值信噪比（ 就是 衡量峰值误差的指标。数学定义如下： )/2 5 5(lo 0 M S N R 其中 ),( 原始图像数据，而 ),( 是解压后的近似图像数据。 M, N 是图像的维数。 一般来说，较低的 表示误差较小，而 越大表示误差越大； 越高代表信息噪声比越高，也就是越好， 越低表示噪声比例高，也就是误差越大。 8 第二章 主元分析 神经网络 元分析算法（ 主元分析是 一种非常有用的统计技术，通常被用于 模式 识别和图像压缩领域。主元分析主要体现了数据的类似和不同处。 假 设有 n 维空间向量集合 )( ,2,1 ，对其中每一个向量 x 用单位正交向量系 ,2,1, ju j 展开 1j jj 由于我们想用 m 维空间表示向量集，即 mj jj 其均方误差 )()( ，因为 ,2,1, ju j 相互正交，即 1所以 12mj 由 x 展开式可知 ，因此 Tj 1 令 , 则 j 1 由拉格郎日乘子法，可以求出在满足正交条件下， 取极值的坐标 系统，即用目标函数 )1()(11 mj 9 对 ,1 导数，有 0)( jj ， ,1 因此当 j ,2,1, 作为矩阵 征向量展开 x 时，其截断均方误差具有极值性质。 而 对 于 离 散 的 随 机 过 程 x(k) ， ,2,1 ，有11 ( ) ( ) ( ) ( ) x k x k x k x （也有用 N T )()(11 ，详见文献？） ，称 x(k)的 相关 矩阵。 用 矩阵 C 的特征向量作为坐标系将矩阵 C 对角化，将消除原有向量的相关性，因此去掉那些带有较少信息的特征向量将降低特征空间的维数。特别地，数据集在这些特征向量方向上投影的方差为其对应的 相关 矩阵 ( ) ( )TE x k x k 的特征值。 主元分析方法 是 直接计算 相关 矩阵 C 的特征值与特征向量，但当向量 x 的维数非常高或 者 向量 x 为动态的随机过程时，矩阵 C 的特征值与特征向量将很难或者不能直接计算。 元分析 神经网络模型 物学模型 人类用近一半的大脑来进行模式识别，所以人类的生物神经网络能很好地完成特征提取等功能。如图 是一个单 经元神经元模型，该神经元的输入信号为一零均值随机过程 , 21 ， , 21 为 n 个 连接输入输出神经元的 突触的权 。那么， 神经元的输出 y 定义为： ni 出是输入的 线性组合，称该神经元 模型 是线性的。 x1(k) x2(k) xn(k) w1(k) w2(k) wn(k) y(k) 10 图 经元模型 根据 出的假设，权向量随着时间而变化，当输入信号 输出 y 相一致时，权向量增强，无监督 习规则如下 ,2,1),()()()1( （ 2 将 式 （ 2为向量形式有 )()()()1( (2其中 t 表示离散时间， 是学习速率。 如果 W(t)收敛到主元方向 W，则称 为主元。式 (2义的 则有一定的缺点，即如果我们连续提交输入并更新 w 时 ， 权值 w 将趋于无限大，这与导出 则的生物 神经元 系统 相 矛盾 ，因为 突触不 可 能无限增大。 前面所示的 单神经元模型只能提取一个主元方向，能一次提取 m 个主元方向的 向神经网络模型如图 示。其无监督 习规则如下 ： )()()()1( (2其中 t 为离散时间， 是学习速率， 1,1 。由于在 接触突上的输入以类似 (2习算法称为局部学习算法。记, 21 , )( , 将 (2写为矩阵与向量形式有 )()()()1( （ 2 图 经网络模型 数学上，容易说明 习规则 (2是不稳定的 ， 如果是稳定的 ， 稳定解一定等于零。因 )(随机变量，所以 )(是随机变量，对（ 2求条y1(k) xn(k) k) x1(k) ym(k) x2(k) k) k) k) k) k) 11 件期望 ),(),(| ，并以 )(W 代表其条件期望有 )()()()()1( 令 C= )()( 是向量 )(关联矩阵 , 由于输入向量为零均值，所以 C 也 )(协方差矩阵。如果 )(敛到稳定解 W ，有 0 (2由于输入的相关 矩阵是非奇异的，所以方程（ 2只能是 0W 。因此需要对 习规则进行一定的修正，使得其权向量收敛于主元方向。 学模型 上节讨论了 经网络的生物模型，基于 习规则， 出了收敛的 习算法。本节将讲述如何通过优化目标函数，导出收敛的 习算法。 可以看到，两者导出的学习算法一致。 由图 5n 维向量 X 经过 经元压缩后输出 Y ，通过 Y 以及权向量 W ，重新构造出 n 维向量 定义 误差 为 。定义目标函数 ： )()(21|21|21)( 22 )2(21 2 关于 W 对 )(导得 )( （ 2 经网络的目标是找到权向量 W 使得 )(小，即求相关矩阵 C 的最大特征向量，在本书中，最大特征向量指 相关 矩阵 C 最大特征值对应的特征向量。由梯度下降方法， 经网络学习算法为 )()()()()()1( 2 （ 2 对 (2求期望，如果 )(均值收敛到 W ，有 )( 则收敛的解为 相关 矩阵 C 的特征向量和零点。 元分析神经网络学习算法 本节 按照算法的优化顺序 介绍主元分析神经网络中常用的学习算法 ，包括：机学习算法，全局收敛的学习算法，并行提取多个主元的学习算法。 12 机学习算法 我们 知道 习规则是发散的，为避免权向量趋于无穷大 ， 一个简单的方法是在算法 (2一步迭代过程中单位化权向量 W ，即 |)()()(| )()()()1( (2由于直接计算（ 2复杂度 非常 高 ，所以 (2需要一定的简化。关于 进行泰勒展开，又因为 1|)(| 所以有 |)()()(| )()()( )()(1)()()( )()()()()( 由上式，我们得到 机学习算法如下： )()()()()()1( 2 (2很明显，（ 2与通过优化目标函数 J(w)而导出的学习算法 (2一致。 (2写为分量形式如下： )()()()()()1( 2 （ 2 其中 ,2,1 。 对 (2取条件期望得到平均权向量 w(k)的迭代方程如下，该方程是确定的和关于时间离散的。 )()()()()()1( (2设j,= )()( 按特征值大小排列的第 j 个特征值与特征向量。 特别地，记最大特征值为 。假设最大特征值的重数为 m, 特征子空间 , 21 p a 如果 1m , 很明显 1。关于 习算法，我们 有如下的局部收敛定理，关于该定理的详细证明请参见文献 3。 定理 果 且选取权向量初始值 1|)0(| W ，则算法 (2的平均权向量将指数收敛于特征子空间，即 ,)( 当 t 且 1|)(| 特别地，如果最大特征值重数为 1，则 ,)( 1 当 t 算法的指数收敛率为 。 定理 证了如果初始权向量 1|)0(| W ，那么 机学习算法中权向量的平均值将收敛到最大的特征向量。反之，如果权向量初始值选取过大， 13 习算法有可能发散，如定理 述。定理 详细证明请参见文献 4。 定理 习算法不全局收敛。 在实际计算中，最大特征值 是未知的，一般我们用关联矩阵 C 的迹来代替 以确定学习速率的取值范围。对于零均值的随机向量 )( ,2,1 ，关联矩阵 C 的 迹由下式计算 )= (1 于是将 的取值范围放宽为 )(1 局收敛的主元分析学习算法 由于 法不是全局收敛的，所以在选择初始权向量时要使得其模小于 1，实际应用中会有一 定的不便。 目前已有的全局收敛算法如下 |)1(|/)1()1()()()()()()1( 2 (2定理 果算法 (2学习速率 1，权向量可以取任意初始值，如果最大特征值重数为 m，则算法 (2的平均权向量将收敛于特征子空间，即 ,)( 当 t 特别地，如果最大特征值重数为 1，则 ,)( 1 当 t 关于定理 详细证明请参见文献 4。实践中，算法 (2收到比较良好的计算效果，但由于在计算中需要规格化权向量，所以计算的效率有所降低。 行提取多个主元的学习算法 在前两小节中，我们讨论了从输入向量中提取第一主元的学习算法。本节将扩展单神经元网络到有 m 个神经元的情形。该神经网络的生物学模型请参见 前面的 图 于这个模型有两个基本假设： 每个神经元都是线性的。 14 该神经网络有 n 维的输入，输出为 m，并且 。 图 示的前向神经网络需要学习训练的是其权向量 i 个输入与第 j 个神经元之间的突触的权。 在时刻 t 第 j 个神经元的输出 )( ni ,2,1),()( 习规则推出权2 jl )()()()()()1( （ 2 其中 ,2,1 ， ,2,1 。与前两小节一致， 是学习速率。当 j=1 时，习算法 (2算法 (2为 习算法， 法（ 为深刻理解 习算法，将 (2写为如下方程 )()()()()()1( （ 2 其中 ,2,1 ， ,2,1 。 )( x(t)第 i 个分量的修改量，它是 j 的函数，定义为 11)()()( jl （ 2 如果固定 j, 算法 (2 习算法 (2致，除了算法 (2输入的信号为 )( 以算法（ 2利用了所需要计算权向量的局部信息，是一个局部的学习算法。 将算法 (2为向量形式有 )()()()()()1( （ 2 其中 ,2,1 , ,)( 21 且 11)()()()( jl (2由 (2 (2，我 们有如下观察： 对应如图 示前向神经网络的第一个神经元，有 1j ： )()( 在这种情况下， 法实际上就是 习算法。 此时关联矩阵x(t)的最大特征值为 1 ，由定理 ， ，且初始权向量值1|)0(| 1 w ， 法能从输入向量 X(n)中提取第一个主元。 对应如图 示前向神经网 络的第二个神经元，有 15 2j ： )()()()( 11 如果第一个神