（微电子学与固体电子学专业论文）jpeg编码器ip的研究与实现.pdf

j p e g 编码器i p 的研究与实现 摘要 ， 在目前多媒体通信采用的技术中，j p e g 标准以其显著的压缩效率和较低的 图像质量损失获得了广泛应用，成为国际通用的标准。同时，随着v l s i 技术 的迅速发展，越来越多图像处理和视频应用采用集成电路实现。当今图像和视 频处理算法越来越复杂，因此基于可重用技术的i p 核设计，对于增加芯片的可 靠性和缩短v l s i 设计的开发周期，显得越来越重要。 j p e g 采取多种编码方式，包含有行程编码( r u nl e n g t hc o d i n g ) 和胡夫曼 ( h u f f m a n ) 编码，有很高的压缩比。在编码前，先对数据进行分块，离散余弦变 换( d c t ) 及量化，保留大量的低频信号，丢弃高频信号以达到压缩的目的。 本文首先对j p e g 编解码的原理进行了阐述。 其次，用硬件设计语言v e r i l o gh d l 对j p e g 编码器进行了r t l 级建模， 用t o p d o w n 设计方法，给出了各个模块的设计流程和方块图。 第三，对d c t 算法进行了某些方面的改进，利用优化算法进行某些改良，从 整体上提高编码性能，达到了满意的效果。并利用f p g a 进行了验证。总结了消 耗的资源，并和以往的设计进行了对比。 关键词：j p e gd c th u f f m a nr t l r e s e a r c ha n di m p l e m e n t a t i o no fj p e g e n c o d i n gi p a b s t r a c t a m o n g al o to fm u l t i m e d i at r a n s m i tt e c h n o l o g i e s ，j p e gh a sb e e nw i d e l yu s e d b e c a u s eo fi t sh i g hc o m p r e s s i o nr a t i oa n dl o wl o s et h eq u a l i t yo ft h ep i c t u r e s oi t b e c o m et h es t a n d a r do ft h es t a t i cp i c t u r ec o m p r e s s i o ns y s t e m a tt h es a m et i m e m o r ea n dm o r ei m a g ep r o c e s s i n ga n dv i d e oa p p l i c a t i o n sa r ei m p l e m e n t e do n c h i p s d u et oi m p r o v e m e n to fv l s it e c h n o l o g y n o wt h ea l g o r i t h m so f i m a g ep r o c e s s i n g a r eb e c o m i n gi n c r e a s i n g l yc o m p l e x ，s ot h ed e s i g n sb a s e do nr e u s a b l ei pc o r ea r e a t t a c h e dm o r ei m p o r t a n c ef o rt h er e l i a b i l i t yo fc h i pa n ds h o r t e n i n gd e s i g n p e r i o d j p e ge n v o l v e ss o m ek i n d so fw a y so fe n c o d i n gi n c l u d i n gr u n l e n g t hc o d i n g a n dh u f f m a nc o d i n g ，s oi th a s h i g hc o m p r e s s i o nr a t i o 。b e f o r ec o d i n g ，w ed i v i d e d a t ai n t ob l o c k s ，d c ta n dq u a n t i f ye a c hb l o c k 。t h e l o w f r e q u e n c ys i g n a l st h a t h a v em o r ee n e r g ya r em a i n t a i n e da n do t h e r sa r er e je c t e d 。 a tf i r s tt h i sa r t i c l ee x p l a i n st h ej p e gc o d i n ga n dd e c o d i n g p r i n c i p l e 。 s e c o n d l yt h er t l ( r e g i s t e rt r a n s f e rl e v e l ) m o d e lw a sd e s i g n e dw i t hv e r i l o g h d ll a n g u a g ef o rj p e gc o d i n g u s i n gt o p d o w nm e t h o d ，w eg e tt h es t e po fa l lt h e m o d u l e t h i r d l yw em o d i f yt h ea l g o r i t h mo fd c tc h a n g e ，s oi tc a ne n h a n c et h es p e e d o fj p e gc o d i n gc h i p t h er e s u l tm e e to u r p u r p o s e w eu s e df p g at ot e s tm yd e s i g n w ec a l c u l a t e dt h er e s o u r c ew eu s e d t h e nm a d eac o n t r a s tw i t ho t h e re x p e r i m e n t k e y w o r d ：j p e gh u f f m a nr t l d c t 插图清单 图1 1 集成规模和设计效率对比l 图2 一l 亮度量化表8 图2 2 色度量化表。9 图2 3h u f f m a n 树形图l3 图2 - 4m c u l 1 7 图2 - 5m c u 2 1 7 图2 6m c u 3 1 8 图3 1j p e g 流程图2 1 图3 2j p e g 编码器2 1 图3 3 编码程序流程图2 2 图3 - 4 量化模块2 2 图3 5h u f f m a n 编码器2 3 图3 - 6a c 系数的编码2 4 图3 7 帧编码控制过程2 5 图3 8 帧扫描控制过程2 5 图3 - 9 重启段编码2 6 图3 1 0 编码m c u 。2 6 图4 1e p 2 s18 0 系列器件特性3 3 图4 2 资源消耗图3 3 图4 3 测试平台3 4 图4 4 时序图3 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 佥g 垦王些态堂或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：飞稳l 还 签字日期q 伊湃j 月乡日 学位论文版权使用授权书 本学位论文作者完全了解金g 曼王些盔堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金魍王业太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 了醴 签字日期：o ，6 萨3 月多日 学位论文作者毕业后去向： 工作单位： 通讯地址； 导师签名： 签字日期：腑3 月r 日 电话： 邮编； 致谢 本论文在导师叶兵教授的耐心指导和帮助下完成。叶老师在工作中兢兢业业，一 丝不苟，导师的敬业精神和严谨的治学态度让我知道了应该以什么态度对待学习和工 作。在此谨向叶老师几年以来对我的辛勤培养、教导和生活上的关心表示最诚挚的感 谢和敬意! 在论文的研究的期间得到了何亚军同学的大力支持和帮助，在此表示衷心感谢。 还要感谢谢可可、蔡发志等同学的热心帮助。 最后祝老师们和同学们生活愉快，工作顺利! 作者：陈超 2 0 0 7 年1 2月2 4日 1 1 集成电路设计方法的发展 第一章绪论 在当前图像的压缩比例不断增加、压缩算法越来越复杂，需要处理的数据 量成指数趋势增加的情况下，对速度的要求也越来越高，以前有些用软件可以 实现的部分，现在己经不能胜任，需要用专用硬件v l s i 集成电路来代替。 集设 成计 规效 模率 图l - 1 集成规模与设计效率对比 时同 而同时集成电路设计技术发展迅速，规模越来越大，尽管只有4 0 年的发 展历程，已经从1 0j 1 0 0 门大小的s s l ( 4 、规模集成电路) 发展到目前千万门以上 的u l s i ( 超超大规模集成电路) 。在集成度方面的发展遵循摩尔定律。i n t e l 即 将推出的p r e s c o t t 处理器，主频将达到3 4 g h z ，内部集成1 亿2 5 0 0 万个晶 体管。如果按照传统的设计方法，针对满足芯片功能和时序要求进行。假设参与 的i c 工程师的设计产能大约为1 0 0 门，天，需要3 0 0 0 人年的工作量来完成 这样一颗1 2 5 亿门规模的芯片设计。显然，这是不现实的，这样基于l p 复用 的数字i c 设计方法和基于集成平台进行系统芯片设计的方法应运而生。 i p 是指集成电路设计中所采用的、具有独立知识产权的、可重用的功能模 块，其英文名称为i n t e l l e c t u a lp r o p e r t y 。现在集成电路的功能越来越复杂，规 模越来越大，甚至达到上千万门的规模，因此在集成电路设计中，完全依靠自 己的力量开发，会使产品的开发周期很长。而利用i p 资源可以缩短相应的设计 周期，同时也可以提高一次流片成功的概率。尤其是在要求实现片上系统 ( s y s t e mo nc h i p ) 的今天，充分利用i p 核可以使系统级的功能更加强大，i p 设 计的层次按照a s l c 设计方法学，分为行为、结构和物理3 级不同程度的设计， 分别称为软核、硬核和固核。功能经过验证的、可综合的、实现后电路结构总 门数在5 0 0 0 门以上的h d l 模型称之为“软核 ( s o f tc o r e ) 。在某一种现场可 编程门阵列( f p g a ) ；器件上实现的，经验证是正确的总门数在5 0 0 0 门以上电 路结构编码文件，称之为“固核”( f r mc o r e ) 。在某一种专用集成电路( a s i c ) 器件上实现的经验证是正确的，总门数在5 0 0 0 门以上的电路结构版图掩膜， 称之为“硬核”( h a r dc o r e ) i p 软核投入最少，只需要完成r t l 级的行为设 计，以h d l 文本提交给用户，它已经过行为级设计优化和功能验证，但其中不 含有任何具体的物理信息。据此，用户可以综合出正确的门电路级网表，并可 以进行后续结构设计，具有最大的灵活性。可以很容易地借助于e d a 综合工具 与其它外部逻辑电路结合成一体，根据各种不同的半导体工艺，设计成具有不 同性能的芯片。并且由于其工艺的无关性，在设计中可以减少重复劳动，提高 工作效率，大大缩短产品的开发周期，因此在现代的i c 设计中得普遍认同而得 以广泛的应用。 与l p 技术相辅相成发展的还有s o c 技术，s o c 就是将系统的全部功能模 块集成到单一半导体芯片上，包括c p u 。i 0 接口、存储器，以及一些重要的模 拟集成电路。功能模块化的系统芯片具有易于增加新功能和缩短上市时间的显 著特点，是i c 设计业当前、乃至可预见未来的主流设计方式。s o c 针对特定 的产品应用，以l p 复用( 一般包括一个或多个微处理器或d s p ) 、片上总线为基 础，以软硬件协同开发为特征，根据产品的系统目标选择功能模块，进行模块 互连和系统功能验因此，s o c 的发展，极大的促进了i p 核的发展。经过1 0 多年的发展，静态图像压缩技术获得很大应用，市场上也出现了很多i p 软核产 品，如k a w a s a k i l s i 公司的k l 5 a 7 10 0 7 ，z o r a n 公司的z r 3 6 0 6 0 ，s y n o p s y s 的 j p e g c o d e c 等。 1 2 集成电路与图像技术 国内外很早以前就开始对图像理论进行了深入的研究，也取得很大的成果。 受条件制约，很多理论停留在软件实现阶段，随着集成电路的进步，以及多媒 体技术在各种手持电子产品的广泛应用，图像解压缩的硬件实现技术受到越来 越广泛的关注，如何提高图像解码的实时性并减少资源消耗也已经成为一个研 究的热点问题。由于图像处理具有数据量大，算法通常比较复杂的特点，研究 者需要同时掌握算法理论和硬件电路设计知识，才能够根据算法设计出满足各 种性能要求的硬件电路，从而得到较好的实现方案，其实质是需要把图像算法 的实现深入到集成电路领域，并实现两者的完美结合。本论文就是集成电路设 计方法与j p e g 标准中基本系统算法结合的产物。 2 1 3 图象压缩的必要和3 p e g 产生的背景 随着微电子，计算机和传感器等技术的高速发展。世界已进入信息时代， 信息时代的重要特征是信息的数字化。这些信息包括：数值、文字、语言、声音、 图形、动画、电视、视频图像等多种多媒体信号。这些多媒体信号由模拟量转 换成数字量信息后送到计算机存储，存储后的数据或者仍由计算机对其自身进 行处理，或者将其通过传输通道进行传输。图像、声音、等媒体信息的记录、 存储正朝着数字化的方向发展。而这些被数字化了的图像、音频等信号的数据 量之大是非常惊人的。通常，媒体信号经过数字化处理之后形成的数据量非常 庞大。一副3 0 0 0 2 0 0 0 个象素组成的灰度图片，如果每个象素用8 b i t 数据量 来表示，那么这幅数字图像需要用：3 0 0 0 2 0 0 0 8bi t ，约为4 8 兆，如此庞大 的数据量存储开销很大，这些大量的数据无疑对存储器存量、计算机的速度都 增加了极大的压力，解决这一问题，单纯用扩大存储器容量的方法，不是很有 效的方法，图像不仅在存储和处理的时候因其数据巨大而造成大量问题，同时 在图像数据的传输过程中也因为网络带宽和图像数据量之间瓶颈，极大的制约 着网络多媒体技术的发展。网络通信技术飞快发展，网络上传输的数据量将越 来越多，数据的复杂度也将越来越大。增加通信干线的传输率的办法是不现实 的。这些数据如果通过数据压缩手段把信息数据压缩下来，以压缩的形式存储 和传输，既节约了存储空间，又提高了通信干线的传输效率，同时也使计算机 能实时处理高质量的音频、视频信息。通过压缩图像数据，最直接的后果就是 减少了传输图像所需的带宽，同时不需额外的物理设备和存储容量，减少了因 此而带来的一系列费用和问题。使用图形、声音、动画、活动图像等多媒体信 息时，特别是具有较高的质量要求时。不仅需要占用相当大的存储空间，而且 需要相当高的数据传输率。因此可以看出，对静态图像进行压缩是绝对必要的。 从以上的论述可以看出图像数据必然要通过压缩，但是这种压缩是否可行? 压 缩后的数据是否会影响到图像的品质? 信息论的核心理论将证明图像压缩技术 具有可行性并有待进一步优化。信息论的观点认为信源中心总是或多或少地含 有自然冗余度，这些冗余度既来自信源本身的相关性，又来自信源概率分布的 不均匀性。这些冗余包括空间冗余、时间冗余、信息熵冗余、结构冗余、知识 冗余、视觉冗余、图像区域的相同性冗余等多种图像冗余。这些冗余大部分来 自图像数据自身，一部分来自外界环境和主观因素。对于这些冗余，根据它对 图像生成的影响程度来分，信息熵冗余和图像区域的相同性冗余是造成图像信 息量大于其要表达的信息的主要原因。图像压缩编码是在对数字图像进行统计 分析，掌握和了解图像信息的统计特性的基础上，充分利用图像本身的相关性 强的特点，寻求消除或减少相关性或改变图像信源概率分布不均匀性的方法， 实现数据的压缩。一般来说，图像压缩编码的目的为： 1 减少数据存储量。 3 2 降低数据率以减少传输宽带。 3 压缩信息量，便于特征抽取，为识别做准备。 信息论对图像压缩编码是否存在科学依据做了详细、有利的证明，大量压 缩算法从产生逐渐成熟。 压缩编码的方法主要分成以下4 大类：1 像素编码：2 预测编码：3 变换编 码：4 其它方法 在数据压缩编码技术的发展过程中，获得最大成功的，并被广泛应用在各 个领域的就是压缩技术第二代中的j p e g 压缩算法。j p e g ( j o i n tp h o t o g r a p h i c e x p e r t sg r o u p ) 是19 5 2 年l s o 国际质量认证组织) 和国际通信联盟联合组成 的。j p e g 组织提出和制定的一种压缩标准，主要适用于静态图像信号的压缩 和编码。j p e g 标准结合采用了预测、不定长等多种压缩编码方法，压缩比可 以达到1 0 ：1 1 0 0 ：1 ，而且压缩比可以在一定范围内由用户进行选择。当压缩 比小于4 0 ：1 时，可以被认为压缩结果是无失真的。但是采用j p e g 标准制定 的压缩算法的计算量比较大，如对一幅较高精度的真彩色图像使用j p e g 压缩 时，大约要进行上亿次运算操作，这对实现j p e g 压缩、编码的软件、硬件设 备产品提出了较高的要求。早期的j p e g 压缩多数做成专用的压缩卡，以专用 的高速c p u 芯片实现压缩处理，现在在通用的计算机c p u 速度不断提高的情 况下，j p e g 压缩也可以用软件来实现。为了解决j p e g 中存在计算复杂，块 效应的问题，近些年来出现了很多新的压缩编码方法，如使用人工神经元网络 ( a r t i f i c i a ln e u r a ln e t w o r k 。a n n ) 的压缩编码算法：分形( f r a c t a l ) ；小波 ( w a v e l e t ) ；基于对象( o b j e c t b a s e d ) 的压缩编码算法：基于模型( m o d e l b a s e d ) 的压缩编码算法( 应用在m p e g 4 及未来的视频压缩编码：际准中) 。 1 4 题来源、背景及意义 专用图像处理芯片的设计是近年来世界范围内研究的热点，这类芯片由于 高速和廉价的特性而备受人们青睐，已经得到了广泛应用。j p e g 压缩芯片更 是在军用高速清晰摄影，卫星遥感图像等尖端科技领域拥有广泛的用途。同时。 我们不应该忽视这样一个事实，这些芯片绝大多数都是由国外厂家设计并制造 的，这些厂商有各自的优化算法和设计方案，但这都是不公开的。国内学者和 厂商在这方面的研究还处于十分落后的地位，我们生产的电子产品大多数都需 要购买国外的知识产权和芯片，这无疑给我国电子信息产业的进步构成了很大 的障碍。选择j p e g 压缩标准作为图像处理硬件模块的压缩算法，并以此来设 计的图像压缩芯片可以在诸多领域得到应用，如数码相机，数码摄像机，卫星 通信等，具有良好的应用前景。因此。可以说，从事高速j p e g 图像压缩芯片的 研究工作，可以有效地填补国内空白，减小与发达国家在信号处理，芯片设计 等领域的差距，是一项很有意义的研究工作。 4 1 5 工作及论文结构 本论文的工作主要有以下2 个方面， 1 ：建立了j p e g 编码模块的r t l 级模型( 由流程框图的形式给出) ，并用f p g a 进行了功能验证。 2 ：提出了一种基于r o m 的d c t 算法，提升了系统的性能 论文的结构安排如下： 第一章介绍了集成电路设计方法学的发展、j p e g 标准的产生及课题的来 源、研究背景和意义。 第二章j p e g 标准的编解码技术介绍。本章对j p e g 标准基本模式的编码、 解码原理以及j p e g 的文件格式进行阐述。 第三章利用v e r i l o gh d l 对j p e g 编码模块进行r t l 级建模，给出了主要流 程图和主要模块。 第四章提出了改进的d c t 算法，并对其原理进行了阐述，并通过f p g a 进行 了验证，通过m o d e l s i m 进行了仿真。 第五章总结与展望。 5 2 13 p e g 算法介绍 第二章j p e g 标准算法介绍 j p e g 是联合图象专家组( j o i n tp i c t u r ee x p e r tg r o u p ) 的英文缩写，是国际标 准化组织( i s o ) 和c c i t t 联合制定的静态图象的压缩编码标准。和相同图象质 量的其它常用文件格式( 如g i f ，t i f f ，p c x ) 相比，j p e g 是目前静态图象中压 缩比最高的。我们给出具体的数据来对比一下。例图采用w i n d o w s 2 0 0 0 目录下 的c l o u d s b m p ，原图大小为6 4 0 * 4 8 0 ，2 5 6 色。用工具s e a ( v e r s i o n l 3 ) 将其分 别转成2 4 位色b m p 、2 4 位色j p e g 、g i f ( 只能转成2 5 6 色) 压缩格式、2 4 位色 t i f f 压缩格式、2 4 位色t g a 压缩格式。得到的文件大小( 以字节为单位) 分别 为：9 2 1 6 5 4 ，1 7 7 0 7 ，1 7 7 1 5 2 ，9 2 3 0 4 4 ，7 6 8 1 3 6 。可见j p e g 比其它几种压缩比 要高得多，而图象质量都差不多( j p e g 处理的颜色只有真彩和灰度图) 。 2 2 1 色彩模型 大家知道，人眼所能感受到的五颜六色都可以归结为三种颜色，即红色， 绿色和蓝色。其它任何颜色可以由这三种颜色按照不同的比例组合来实现。这 就是所谓的三基色原理。要传输彩色图像实际只要传输这三种颜色的图像就可 以了。 j p e g 的图片使用的是y c r c b 颜色模型，而不是计算机上最常用的r g b 颜 色模型。丛视觉学的角度来看，y c r c b 模型更适合图形压缩。因为人眼对图片 上的亮度y 的变化远比色度c 的变化敏感。我们完全可以每个点保存一个 8 b i t 的亮度值，每2 * 2 个点保存一个c rc b 值，而图像在肉眼中的感觉不会 起太大的变化。所以，原来用r g b 模型，4 个点需要4 x 3 = 1 2 字节。而现在仅需 要4 + 2 = 6 字节：平均每个点占1 2 b i t 。 rgb 一 yc bc r 转换( r ，g ，b 都是8 b i tu n s ig n e d ) y = 0 2 9 9 r + 0 5 8 7 g + 0 11 4 * b c b =一o 1 6 8 7 r 一0 3 3 1 3 * g + 0 5 ，l = b + 1 2 8 c r = 0 5 木r 一0 4 1 8 7 g 一0 0 8 1 3 * b + 1 2 8 逆转换的公式为： y ，c b ，c r 一 r 。g ，b 转换 r = y + 1 4 0 2宰( c r - 1 2 8 ) g = y 一0 3 4 4 1 4 * ( c b - i 2 8 ) 一0 7 1 4 1 4 ( c r 一1 2 8 ) b = y + 1 7 7 2水( c b 一1 2 8 ) 一般，c 值( 包括c bc r ) 应该是一个有符号的数字，但这里被处过了， 方法是加上了1 2 8 。j p e g 里的数据都是无符号8 b i t 的。 6 2 1 2 d c t ( 离散余弦变换) 目前两种方法使用最广泛：离散余弦变换( d c t ) 和离散小波变( d w t ) 。本文 主要阐述d c t 。d c t 之所以能广泛地被使用主要有以下因素：首先它通过能量聚 集和去除相关性使得图像数据转变为易于压缩的形式；其次d c t 的均方误差编码 性能在理论上近似于在马尔可夫模型假定下的最佳统计匹配正交变换( k l t ) ； 第三d c t 可以用快速算法实现。 d c t 的去相关性和能量集中性能随着块尺寸的增加而增加，然而计算的复杂 性却随着块尺寸成指数地增加。所以在图像的d c t 变换中常一次处理8 * 8 大小的 块，这个尺寸的压缩效率高，同时计算也不是很复杂。处理8 * 8 矩阵大小的图像 数据的d c t 变换公式为： f ，v ) = 丢c ) c ( v ) 萎7 荟7 厂 ，力c 。s 望兰尝 t 工= 0y = o 1 u 其中，”，v = o ，i 6 ，7 当“， ，均为。时，c ) ，c ( y ) 2 西i ，其他情况下c ) ，c ( ，) 2 1 1 6 通过公式。图像采样点的每个块的数据表示为二维余弦函数的一个加权和。 2 1 3 重排列d c t 结果 d c t 将一个8 x 8 的数组变换成另一个8 x 8 的数组。但是内存里所有数据都 是线形存放的，如果我们一行行的存放这6 4 个数字，每行的结尾的点和下行开 始的点就没有什么关系，就无法很好的表示其相关性，所以j p e g 规定按如下次 序整理6 4 个数字。 0 ，l ，5 ，6 ，1 4 ，1 5 ，2 7 ，2 8 ， 2 ，4 ，7 ，1 3 ，16 ，2 6 ，2 9 ，4 2 ， 3 ，8 ，1 2 ， 1 7 ，2 5 ，3 0 ，4 1 ，4 3 ， 9 ，1l ，1 8 ，2 4 ，3 l ，4 0 ，4 4 ，5 3 ， 1 0 ，1 9 ，2 3 ，3 2 ，3 9 ，4 5 ，5 2 ，5 4 ， 2 0 ，2 2 ，3 3 ，3 8 ，4 6 ，5 1 ，5 5 ，6 0 ， 2 1 ，3 4 ，3 7 ，4 7 ，5 0 ，5 6 ，5 9 ，6 i ， 3 5 ，3 6 ，4 8 ，4 9 ，5 7 ，5 8 ，6 2 ，6 3 这样数列里的相邻点在图片上也是相邻的了。 7 2 1 4 量化 对于前面得到的6 4 个空间频率振幅值，我们将对它们作幅度分层量化， 操作方法就是分别除以量化表里对应值并四舍五入。 下面两张 p e g 标准量化表。( 按上面同样的弯曲次序排列) 1 6l ll o1 62 44 06 l6 0 1 21 21 41 92 65 86 05 5 1 41 31 62 44 05 76 95 0 1 41 72 22 95 18 78 06 2 1 82 23 75 66 81 0 91 0 39 2 2 43 55 56 48 11 0 411 39 2 4 96 47 88 71 0 31 2 11 2 01 0 1 7 29 29 59 8l1 2 1 0 01 0 39 9 图2 1 亮度量化表 8 1 71 82 4 4 79 99 99 99 9 1 82 l2 66 6 9 99 99 99 9 2 42 65 69 9 9 99 99 99 9 4 76 69 99 99 99 9 9 99 9 9 99 99 99 99 99 99 9 9 9 9 99 99 99 9 9 99 99 99 9 9 99 99 9 9 99 99 99 99 9 9 99 99 99 99 99 99 99 9 图2 - 2 色度量化表 这两张表依据心理视觉阀制作，对8 b i t 的亮度和色度的图象的处理效果不 错。当然我们可以使用任意的量化表。量化表是定义在j p e g 的d o t 标记后。一 般为y 值定义一个，为c 值定义一个。 量化表是控制j p e g 压缩比的关键。这个步骤除掉了一些高频量，损失了高 频细节。但事实上人眼对高频远没有低频敏感。所以处理后的视觉损失很小。 另一个重要原因是所有的图片的点与点之间会有一个色彩过渡的过程。大量的 图象信息被包含在低空间频率中。经过量化处理后，在高空间频率段，将出现 大量连续的零。 这里我们将跳过第一个矢量，因为它的编码比较特别。 2 1 50r l e 编码 现在我们矢量中有许多连续的0 。我们可以使用r l e 来压缩掉这些o 。 流量) 。假设有一组矢量( 6 4 个的后6 3 个，已按z 字形扫描得到) 是 5 7 ，4 5 ，0 ，0 ，0 ，0 ，2 3 ，0 ，一3 0 ，一1 6 ，0 ，0 ，1 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 经过r l c 压缩后就是 ( 0 ，5 7 ) ；( 0 ，4 5 ) ：( 4 ，2 3 ) ：( 1 ，一3 0 ) ：( 0 ，一1 6 ) ：( 2 ，1 ) ：e o b 。 e o b 是一个结束标记，表示后面都是0 了。实际上我们用( 0 ，0 ) 表示e o b ， 9 但是，如果这组数字不以0 结束，那么就不需要e o b 。 2 1 6h u f f m a n 编码 为了提高储存效率，j p e g 里并不直接保存数值，而是将数值按位数分成 1 6 组： 数值 0 1 ，l 一3 ，一2 ，2 ，3 7 ，一6 ，一5 ，一4 ，4 ，5 ，6 ，7 1 5 ，一8 ，8 ，1 5 3 1 ，一1 6 ，1 6 ，3 1 6 3 ，一3 2 ，3 2 ，6 3 1 2 7 ，一6 4 ，6 4 ，1 2 7 2 5 5 ，一1 2 8 ，1 2 8 ，2 5 5 5 l l ，一2 5 6 ，2 5 6 ，5 l l 一1 0 2 3 ，一5 1 2 ，5 1 2 ，1 0 2 3 2 0 4 7 ，一1 0 2 4 ，1 0 2 4 ，2 0 4 7 4 0 9 5 ，一2 0 4 8 ，2 0 4 8 ，4 0 9 5 8 1 9 1 ，一4 0 9 6 ，4 0 9 6 ，8 1 9 1 1 6 3 8 3 ，一8 1 9 2 ，8 1 9 2 ，1 6 3 8 3 - 3 2 7 6 7 一1 6 3 8 4 ，1 6 3 8 4 ，3 2 7 6 7 1 5 1 0 11 1 2 1 3 1 4 实际保存值 0 ，1 0 0 ，0 1 ，1 0 ，11 0 0 0 ，0 0 1 ，0 1 0 ，0 1 1 ，1 0 0 ，1 0 l ，1 1 0 ，1 1 1 0 0 0 0 ，0 111 ，1 0 0 0 ，1111 0 0 0 0 0 ，0 1111 ，1 0 0 0 0 ， a c 的编码 例如t ( o ，5 7 ) ：( 0 ，4 5 ) ：( 4 ，2 3 ) ：( 1 ，- 3 0 ) ：( 0 ，一8 ) ；( 2 ，1 ) ：( 0 ，0 ) 只处理每对数右边的那个： 5 7 是第6 组的，实际保存值为11 1 0 0 1 ，所以被编码为( 6 ，l l1 0 0 1 ) 4 5 ，同样的操作，编码为( 6 ，1 0 1 1 0 1 ) l o 缍 0 l 2 3 4 5 6 7 8 9 2 3一 ( 5 ，1 0 1 11 ) 一3 0 一 ( 5 ，0 0 0 0 1 ) 一8 一 ( 4 ，0 1 11 ) 1一 ( 1 ，1 ) 前面的那串数字就变成了： ( 0 ，6 ) ， l l1 0 0 1 ：( 0 ，6 ) ，1 0 11 0 1 ：( 4 ，5 ) ， 1 0 11 1 ：( 1 ，5 ) ，0 0 0 0 1 ：( 0 ， 4 ) ， 0 111 ：( 2 ，1 ) ，l ：( 0 ，0 ) 括号里的数值正好合成一个字节。后面被编码的数字表示范围是 一3 2 7 6 7 3 2 7 6 7 。合成的字节里，高4 位是前续o 的个数，低4 位描述了 后面数字的位数。 继续刚才的例子，如果0 6 的h u f f m a n 编码为1 1 1 0 0 0 6 9 = ( 4 ，5 )1 1 1 l l l l l l 0 0 1 1 0 0 1 2 1 = ( 1 ，5 )1 1 1 1 1 1 1 0 1 1 0 4 = ( 0 ，4 )1 0 l l 3 3 = ( 2 ，1 )11 0 11 0 = e o b = ( 0 ，0 ) 1 0 1 0 等号左边的是表示相应中间符号在h u f f m a n 表中的位置。 那么最后对于前面的例子表示的6 3 个系数按位流写入j p e g 文件中就 是这样的： 1 1 1 0 0 01 1 1 0 0 l1 1 1 0 0 01 0 1 1 0 11 1 1 1 1 1 1 1 1 0 0 1 1 0 0 11 0 1 1 l1 1 1 1 1 1 1 0 1 1 00 0 0 0 1 1 0 l l0 1 1 l1 l o l l l1 0 1 0 d c 的编码 记得刚才我们跳过了每组6 4 个数据的第一个吧，d c 就是指的这个数字 ( 后面6 3 个简称a c ) ，即一块图象样本的平均值。就是说， 它包含了原始 8 x 8 图象块里的很多能量。( 通常会得到一个很大的数值) j p e g 的作者指出连续块的d c 之间有很紧密的联系，因此他们决定对8 x 8 块的d c 值的差别进行编码( y ， c b ，c r 分别有自己的d c ) 。 d i f f = d c ( i )一d c ( i - 1 ) 所以这一块的d c ( i ) 就是：d c ( i )= d c ( i - 1 ) + d i f f j p e g 从o 开始对d c 编码， 所以d c ( 0 ) = 0 。然后再将当前d i f f 值加 在上一个值上得到当前值。下面再来看看上面那个例子：( 记住我们保存的 d c 是和上一块d c 的差值d i f f ) 。例如在这样一个例子中， d i f f 如果是 一5 1 1 ，就编码成( 9 ，0 0 0 0 0 0 0 0 0 ) 。如果9 的h u f f m a n 编码是1 1 1 1 1 1 0 ( 在 j p e g 文件中，一般有两个h u f f m a n 表，一个是d c 用，一个是a c 用) 那 么在j p e g 文件中， d c 的2 进制表示为1 1 l l l l 00 0 0 0 0 0 0 0 0 它将放在6 3 个a c 的前面，上面上个例子的最终b i t 流如下： l l l l l l l l 00 0 0 0 0 0 0 0 01 1 1 0 0 01 1 1 0 0 11 1 1 0 0 01 0 1 1 0 1 1 1 1 1 1 1 l l l 0 0 1 1 0 0 1 1 0 1 1 l1 1 1 1 1 1 1 0 1 1 00 0 0 0 11 0 1 10 1 1 11 1 0 1 1 11 0 1 0 2 2h u f f m a n 原理 哈夫曼( h u f f m a n ) 编码是一种常用的压缩编码方法，是h u f f m a n 于1 9 5 2 年 为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替， 较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是 二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8 种符号 s o ，s l ，s 2 ，s 3 ，s 4 ，s 5 ，s 6 ，s 7 ，那么每种符号要编码，至少需要3 比特。 假设编码成0 0 0 ，0 0 1 ，0 1 0 ，0 1 l ，1 0 0 ，1 0 1 ，1 1 0 ，1 l l ( 称做码字) 。那么符号 序列 s o s i s 7 s o s l s 6 s 2 s 2 s 3 s 4 s 5 s o s o s l 编码后变成 0 0 0 0 0 11 11 0 0 0 0 0 111 0 0 1 0 0 1 0 0 11 1 0 0 1 0 1 0 0 0 0 0 0 0 0 l ，共用了4 2 比特。我们发现 s o ，s l ，s 2 这三个符号出现的频率比较大，其它符号出现的频率比较小，如果 我们采用一种编码方案使得s o ，s 1 ，s 2 的码字短，其它符号的码字长，这样就 能够减少占用的比特数。例如，我们采用这样的编码方案：s 0 到s 7 的码字分 别0 1 ，1 1 ，1 0 1 ，0 0 0 0 ，0 0 0 1 ，0 0 1 0 ，0 0 11 ，1 0 0 ，那么上述符号序列变成 0 “11 0 0 0 11 1 0 0 11 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 111 ，共用了3 9 比特，尽管有些码字 如s 3 ，s 4 ，s 5 ，s 6 变长了( 由3 位变成4 位) ，但使用频繁的几个码字如s o ， s 1 变短了，所以实现了压缩。 上述的编码是如何得到的呢? 编码必须保证不能出现一个码字和另一个的 前几位相同的情况，比如说，如果s o 的码字为0 1 ，s 2 的码字为0 1 l ，那么当 序列中出现0 1 1 时，你不知道是s 0 的码字后面跟了个1 ，还是完整的一个s 2 的码字。我们给出的编码能够保证这一点。 下面给出具体的h u f f m a n 编码算法。 ( 1 )首先统计出每个符号出现的频率，上例s o 到s 7 的出现频率分别为4 1 4 ， 3 1 4 ，2 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ，1 1 4 。 ( 2 )从左到右把上述频率按从小到大的顺序排列。 ( 3 )每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们 的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。 ( 4 )重复( 3 ) ，直到最后得到和为1 的根节点。 ( 5 )将形成的二叉树的左节点标0 ，右节点标1 。把从最上面的根节点到最下 面的叶子节点途中遇到的0 ，1 序列串起来，就得到了各个符号的编码。 上面的例子用h u f f m a n 编码的过程如图2 3 所示，其中圆圈中的数字是新 节点产生的顺序。可见，我们上面给出的编码就是这么得到的。 1 2 s 3s 4s 5 s 6s 7s 2s 1 0 0 0 0 0 0 0 10 0 1 00 0 1 11 0 01 0 11 1 s o 0 1 图2 3h u f f m a n 树形图 产生h u f f m a n 编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出 原始数据中，每个值出现的频率，第二遍是建立h u f f m a n 树并进行编码。由于 需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但 简单有效，因而得到广泛的应用 2 25 p e g 文件格式 下面介绍一些常用的标记码的结构及其含义。 j p e g 文件格式 j p e g 编码的最后一个步骤是把各种标记码( t a g ) 和熵编码后的图像数据组 成一帧一帧的数据，以便于对编码数据进行传输、存储和解码，这样组织的数 据通常称为j p e g 位数据流( j p e gb i t ss t r e a m ) 。 j p e g 文件使用的位数据流方式有多种。最常用的格式称为j p e g 文件交换格 式( j p e gf i l ei n t e r c h a n g ef o r m a t ，j f i f ) 。而j f i f 文件大体上可以分成两 个部分：头文件和压缩数据。头文件由标记码和标记码所包含的信息构成。标 记码由两个字节构成，其前一个字节是固定值o x f f ，后一个字节则根据不同意 义有不同数值。在每个标记码之前还可以添加数目不限的无意义的o x f f 填充， 也就说连续的多个o x f f 可以被理解为一个o x f f ，并表示一个标记码的开始。而 在一个完整的两字节的标记码后，就是该标记码包含的图像信息，记录了关于 文件的诸种信息。因为在j f i f 文件中o x f f 具有标志性的意思，所以在压缩数据 流( 真正的图像信息) 中出现o x f f ，就需要作特别处理。具体方法是，在数据o x f f 后添加一个没有意义的o x 0 0 。换句话