5782人阅读
C/C++编程知识（134）
游程长度编码
图1:原始栅格数据
游程编码又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码。对于二值图有效。 行程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度。 例如：1 行程编码为：（5，6）（7，5）（3，3）（2，4）（l，7）。可见，行程编码的位数远远少于原始字符串的位数。 在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。 行程编码分为定长行程编码和不定长行程编码两种类型。 行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
　　游程长度编码（run-length code）
　　游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。
　　例如对图1所示的栅格数据，可沿行方向进行如下游程长度编码：
　　(9,4),(0,4),(9,3),(0,5),(0,1)(9,2),(0,1),(7,2),(0,2),(0,4),(7,2),(0,2),(0,4),(7,4),(0,4),(7,4) ,(0,4),(7,4) ,(0,4),(7,4)
　　游程长度编码对图3-6(a)只用了40个整数就可以表示，而如果用前述的直接编码却需要64个整数表示，可见游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。
　　游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。
　　[font id="zoom" class="zoom"]游程长度RL (Run—Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度．如果给出了形成申的字符，申的长度及申的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。游程长度编码的主要思想是将一个相同值的连续申用其值和申长(重复的个数)的数对二元组来替代．例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程．游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据．例如，若沿水平方向有一申M 个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M )就可以代替这M个像素的M个灰度值N。简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据．在多媒体信息量激增、网络特性和速度都飞速提高的今天，游程长度编码是一种十分简单的压缩方法，编码／解码的速度也非常快，可广泛应用于多媒体信息的存储，传输。江苏科技大学电子信息学院毕业论文游程长度编码算法研究蒋 伟（设计者）系 电子信息 专业 电子信息工程班级
学号 指导教师 田雨波 职称 副教授2006 年 6 月摘要游程长度编码非常简单，编码、解码速度快，应用广泛。本文主要介绍了游程长度编码的原理和实现技术，对游程长度编码技术做了较为全面地研究。包括游程压缩模型、数据压缩、解压缩过程，并给出了流程图和相应的程序。关键词：编码；解码；游程长度编码；压缩；解压缩。
　　AbstractRLCis very simple，and its speed of coding and decoding is quick So it hasa wide application．This paper gives a brief introduction to theprinciples and realization technology of RLC Researching the RLCtechnology is in a relatively comprehensive way，including the RLCcompression models，the processes of data compression and uncompression，and giving the flow diagrams and relevantprograms．Keywords：code；decode；RLC；compression；uncompression目录ABSTRACT 2第一章 游程长度编码算法概述 51.1 信源编码原理 61.2 游程长度 71.3游程长度编码的基本原理 71.3.1 文本游程压缩的原理 71.3.2 图象游程压缩的原理 8第二章开发环境 92.1 MICROSOFT VISUAL C++ 6.0 中文版 92.1.1 简介 92.1.2 主要特点 10第三章 实现算法 113.1 数据压缩算法流程 113.2数据解压算法流程 123.3 文本游程压缩的算法 133.3.1 文本压缩部分 133.3.2文本解压部分 143.4 图象游程压缩的算法 143.4.1 图象压缩部分 143.4.2图象解压部分 15第四章 系统原理 164.1 程序运行主界面 164.2文本游程压缩的界面与程序 164.3 图象压缩的界面和程序 23第五章 游程长度编码压缩算法的讨论 29结 束 语 31致 谢 32参考文献 33附录3 34附录2 88绪论信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1min，图像尺寸为640×480pixete，每秒播放30帧的非压缩彩色24位真彩色视频的信息量为：640×480×3×30×60：Bytes，约为1.6GB(未含音频信息的容量)，如果用650MB的CD-R来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的。数据压缩技术主要采用两种方法：一种是“保真率”较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。
　　无损压缩虽然压缩比不是很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Hufman)编码、算术编码(AC)和游程长度编码(RLC)。其中，游程长度编码是一种十分简单的压缩方法，编码／解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如.BMP，.TIF及.AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以达到减少数据文件所占的存储空间的目的。飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究。通过对游程编码(RunLengthEncoding,RLE)进行研究,最后提出一种实现相对简单、压缩效果比较好的算法，采用该算法可以收到比较理想的效果，基本克服由于RLE自身特点而引起的数据扩张的现象。第一章游程长度编码算法概述飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求。
　　现有的无损压缩方法，如Huffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究。1.1信源编码原理[1][2][5][7]定义一象元的M层，其灰度值 的平均信息量或熵为：(1.1)其中 为每一个灰度等级出现的概率，熵值可以在0~ 之间变化，即编码后的码长平均起来不得少于熵值。对于游程编码，设定一个象元出现边缘的概率为P，而象元间是相对独立的，则边缘间游程长度Z的概率分布可用下式表示：(1.2)式中 。当游程长度时，表示两个相邻边缘的情况。在这种简单的统计假设条件下，边缘长度的均值为：(1.3)而边缘间游程长度Z的熵为：(1.4)假如游程的最大长度为M个象元，则对应的边缘间的熵，可近似得出：(1.5)把对应边缘间游程的熵除以游程长度的均值，就可以得到每个象元的熵为：(1.6)以上各式的推导参见[1]。由以上公式可以得出对于黑白灰度的二值图象，使用二维游程编码，可以使压缩比达到10：1。1.2游程长度游程长度RL(Run-Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。
　　1.3游程长度编码的基本原理[5][9]在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(l)。“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，…，直到无限。将任何(二元)序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以达到压缩码率的目的。游程长度编码的主要思想是将一个相同值的连续申用其值和申长(重复的个数)的数对二元组来替代．例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程．游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据．例如，若沿水平方向有一串M 个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M)就可以代替这M个像素的M个灰度值NJ简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据。1.3.1文本游程压缩的原理对重复字段采用3符号标识法：(1) 重复提示符,比如@,#等；(2)游程长度参数或重复次数,若用一个字节表示,最大长度可为255个重复字；(3) 重复字符。
　　以上三部分合称为重复因子。可见要获得压缩效益，重复字符应在3个以上。对于非重复字段则直接拷贝字段，不做任何处理。1.3.2图象游程压缩的原理对于二值图像，原始数据为零一矩阵，压缩时逐行处理该矩阵：(1) 连续n个1，表示为+n；(2)连续n个0，表示为-n。在游程长度编码(RLC)中用3个字节表示一个字符申：第一个字节是压缩指示字符，第二个字节记录连续出现的字符，第三个字节记录重复字符出现的次数。可见，只有当RL3时进行数据压缩才有意义，因此，编码时首先要判断RL值，然后再决定是否进行游程长度编码(RLC)；解码时则需根据每一字符后是否为，再决定其下一字符的含义，如下图所示：例如：设一幅二维黑白图像F(i,j)的各像素的灰度值如下所示，规定沿水平方向从左到右扫描，则扫描后得到的游程为右边的13个二元数组。图表 1.1图表2.2由上例可见：(1)该图像是由8行、8列共64个像素组成；(2)像素的灰度值变化范围是：0～8；由于是黑白图，颜色过渡只是黑一灰一白，按人眼分辨率，用8 bit即得 。(3)第一行8个像素灰度值相同，只传(8，8)；第二行只传(8，4)(7，4)；第三行只传(7，8)；第四行只传(6，4)(5，4)；第五行时只传(5，5)(3，3)；第六行只传(3，8)；第七行只传(3，3) (2，5)；第八行只传(1，4)(0，4)。
　　这样，64个像素只需传13个数据对即可， 比一个个像素传送要节省很多时间．一般情况下，编码时间为2~4倍的解码时间。第二章 开发环境2.1 MicrosoftVisual C++ 6.0 中文版[3]2.1.1 简介Microsoft VisualC++是一种从C语言的基础上逐步发展和完善起来的，而C是吸收了其他语言的一些优点逐步成为实用性很强的一种语言。C++并不是对C语言的简单的改进和扩充，而是一种本质性革新。C++是C语言的一个超集，大多书的C程序代码略做修改和不做修改就可以在C++的集成环境下调试。C++是面向对象的程序设计语言，它似的程序的各个模块的独立性更强，程序可读性和可理解性更好。C++的扩充性强，具有封装性，继承派生性，重载性和多态性。MicrosoftVisual C++ 6.0中文版为用户开放C++程序提供了一个集成的环境，而这个集成环境包括：源程序的输入，编辑和修改，源程序的编译和连接，程序运行间的调试和跟踪，项目的自动管理，为程序的开放提供工具，窗口管理，联机帮助。正是由于这个继承的环境功能齐全，故选择了Microsoft Visual C++ 6.0中文版作为界面，图象文本压缩的开放工具。
　　2.1.2 主要特点在Windows98或XP下启动VC++的集成环境，则产生下图所示的组合窗口。窗口的最上面部分为标题。第二部分为菜单条，其中包括“文件(File)编辑(edit)”等菜单。第三部分是功能按钮，类同于Word，有“打开”文件等等按扭。当要建立一个新的源程序文件时，选择“file”菜单中的“new”命令，这时弹出一个子窗口，在子窗口中选择“file”按扭，在弹出的信息窗口中再选择“c++ sourcefile”，这时光标进入源程序编辑子窗口，就可以输入源程序了。当正确输入源程序文件后，可以选择“file”菜单中的“open”命令，然后按照提示的信息，选择相应的源程序文件名。由系统将指定的源程序文件调入源程序编辑子窗口，就可以对源程序文件进行编辑。当正确地输入源程序文件后，先存盘，然后可选择“build”菜单中的“build”命令来编译源程序和连接目标程序，最后选择“build”菜单中的“execute”来执行程序。
　　图表 2.1 Microsoft Visual C++ 6.0界面第三章 实现算法3.1数据压缩算法流程[1]用游程长度编码压缩数据时，首先要计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来。这种压缩数据的方法，连续相同的字符及出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。(1)打开源数据文件和压缩后的数据文件；(2)从源数据文件中读取字符，并把它放人一个寄存器中，然后再循环读取后面的字符，并与寄存器中的字符相比较。如果相等，则计数器加1，否则，把寄存器中的字符和计数器中数写入压缩数据文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把计数器置1。图表 3.1 RLC数据压缩算法流程图3.2数据解压算法流程(1)打开压缩数据文件和恢复文件；(2)从压缩文件中循环读出字符和该字符连续的个数，在恢复文件中连续写入从压缩文件中读出的字符，写的次数等于该字符连续的个数。图表 3.2 RLC数据解压缩算法流程图3.3 文本游程压缩的算法3.3.1文本压缩部分初始化计数变量（已读字符数C，重复字符数R）；如果待压缩文本m_cOriginalText没有结束{读取当前字符CH；如果当前字符是第一个字符，将比较字符SH设为当前字符，continue；如果当前字符等于比较字符，重复次数加一，continue；如果重复次数小于3，将比较字符写入压缩流m_cCompressText：R+1次，重复次数置零，将比较字符设为当前字符，continue；将重复字符，以三字节格式写入压缩流m_cCompressT重复次数置零，将比较字符设为当前字符，continue；}注：continue表示结束本次循环，并转下次循环的入口点。3.3.2 文本解压部分如果压缩文本m_cCompressText中还有字符{读取当前字符cCur；如果当前字符等于'@',读取重复字符cR以及重复次数iNum，将重复字符写入解压流m_cUncompressText：iNum次，continue；将当前字符写入解压流m_cUncompressText；}3.4 图象游程压缩的算法3.4.1图象压缩部分对于二值矩阵Original的每一行{重复计数iNum赋值为1；对于该行的第一列～倒数第二列中的每一列{如果当前列的值＝下一列的值{重复计数iNum加一；如果当前列是倒数第二列{如果当前列的值＝1，将iNum写入压缩数据链pCompress，否则将-iNum写入压缩数据链pCompress；}}否则{//如果当前列的值不等于下一列的值如果当前列的值＝1，将iNum写入压缩数据链pCompress，否则将-iNum写入压缩数据链pCompress；置重复计数iNum为1；如果当前列是倒数第二列{如果下一列的值＝1，将+1写入压缩数据链pCompress，否则将-1写入压缩数据链pCompress；}}}}3.4.2图象解压部分如果解压的结果数组Uncompress没有填满{如果压缩数据链pCompress上的数据已处理完，结束解压；从压缩数据链上取一个数据；如果数据值val0,则向解压结果数组Uncompress中写入val个1，否则写入-val个0(也可写-1)；准备取下一个数据；} 第四章系统原理4.1程序运行主界面[4]本实验的程序采用VC6.0编制，程序类型为MFC，实验的主界面如图1。点击菜单“RLEText”，将弹出“文本的游程压缩”对话框，如图。
　　点击菜单“RLEBmp”，将弹出“图像的游程压缩”对话框，如图4.1。图表 4.1 程序主界面4.2文本游程压缩的界面与程序点击“压缩”按钮，压缩结果将出现在相应的文本框中，如图4.2。压缩代码如下。//【获取原文本】CString sOriginalText,s;this-GetDlgItemText(IDC_EDIT_Original,sOriginalText);strcpy(m_cOriginalText,(LPSTR)(LPCTSTR)sOriginalText )；//【压缩文本】//初始化计数变量int R=0; //重复字符数int C=0; //已读字符数int CC=0;char CH;//当前字符char SH; //比较字符//如果文本没有结束{do{//读取当前字符CH=m_cOriginalText[C];C++;//如果当前字符是第一个字符，将比较字符设为当前字符，continueif(C==1){SH=CH;}//如果当前字符等于比较字符，重复次数加一，continueif(CH==SH){R++;}//如果重复次数小于3，将比较字符写入压缩流：R+1次;重复次数置零，将比较字符设为当前字符，continueif (R&3){for(int i=0; i&=R;i++){m_cCompressText[CC]=SH;CC++;}R=0;SH=CH;}//将重复字符，以三字节格式写入压缩流;重复次数置零，将比较字符设为当前字符，continuem_cCompressText[CC++]='@';char cNum=(char)(R+1);m_cCompressText[CC++]=cNm_cCompressText[CC++]=SH;R=0;SH=CH;//}} while( CH!='' );C--;m_cCompressText[CC]='';s.Format("原字符数=%d/n 压缩字符数=%d/n压缩比＝%f",C,CC,(C+0.0)/CC);::AfxMessageBox(s);//【设置压缩文本，激活解压按钮】this-SetDlgItemText(IDC_EDIT_Compress,CString(this-m_cCompressText));CButton *pBpBtn=(CButton*)GetDlgItem(IDC_BUTTON_Uncompress);pBtn-EnableWindow(TRUE);pBtn=(CButton*)GetDlgItem(IDC_BUTTON_Compress2);pBtn-EnableWindow(TRUE);图表 4.2 文本压缩界面图表4.3文本的游程压缩结果（将字节计数转换为字符串）我们发现压缩结果中，重复因子的第二个字符，即用于计数的字符无法显示。要显示计数，需获取重复因子的第二个字符的ASCII码对应的字符串，处理结果如图4.3。代码如下。//将压缩文本中的@后的一字节计数用数字串替换int iAt,iStart=0;char cNCStringcsCompressText,csNcsCompressText.Format("%s",m_cCompressText);while((iAt=csCompressText.Find('@',iStart))=0){cNum=csCompressText.GetAt(iAt+1);csNum.Format("[%d]",int(cNum));csCompressText.Delete(iAt+1);csCompressText.Insert(iAt+1,csNum);iStart=iAt+1;}this-SetDlgItemText(IDC_EDIT_Compress,csCompressText);我们对压缩的文本进行解压，得到的还原文本与原文本一样，处理结果如图4.4。代码如下。
　　int iC=0/*压缩文本字符计数*/,iU=0/*解压结果文本字符计数*/;int iNum/*重复次数*/;char cCur/*当前字符*/,cR/*重复字符*/;//如果压缩文本中还有字符{while(m_cCompressText[iC]!='' ){//读取当前字符；cCur=m_cCompressText[iC];iC++;//如果当前字符等于'@',读取重复字符cR以及计数iNum，将重复字符写入解压流：iNum次，continue；if (cCur=='@'){cR=m_cCompressText[iC+1];iNum=(int)m_cCompressText[iC];for(inti=0; i&iNi++){m_cUncompressText[iU++]=cR;}iC+=2;}//将当前字符写入解压流；m_cUncompressText[iU++]=cC//}}m_cUncompressText[iU]='';this-SetDlgItemText(IDC_EDIT_Uncompress,CString(this-m_cUncompressText));图表4.4文本的游程压缩－解压4.3图象压缩的界面和程序图像游程压缩的原始数据为二值数组，我们用方格阵列来模拟该二值数组，方格填充对应的数值为1，否则为-1。通过绘制方格阵列，我们可获得原始数据，如图4.5图表4.5图像的游程压缩－绘制图像点击“压缩”按钮，得到的压缩结果如图7，代码如下。//对于二值矩阵Original的每一行{for(inti=0; i&PANES_Ri++){//重复计数iNum赋值为1；iNum=1;//对于该行的第一列～倒数第二列中的每一列{for(int j=0; j&(PANES_Col-1); j++){//如果当前列的值＝下一列的值{if(Original[PANES_Col*i+j]==Original[PANES_Col*i+j+1]){//重复计数iNum加一；iNum++;//如果当前列是倒数第二列{if( j==(PANES_Col-2) ){pNext=newCompressN//如果当前列的值＝1，将iNum写入压缩数据链pCompress，否则将-iNum写入压缩数据链pCompress；pNext-val=(Original[PANES_Col*i+j]==1)?iNum:(-iNum);pNext-next=NULL;pPre-next=pNpPre=pN iNum=1;}}//否则{ //如果当前列的值不等于下一列的值else{pNext=newCompressN//如果当前列的值＝1，将iNum写入压缩数据链pCompress，否则将-iNum写入压缩数据链pCompress；pNext-val=(Original[PANES_Col*i+j]==1)?iNum:(-iNum);pNext-next=NULL;pPre-next=pNpPre=pN //置重复计数iNum为1；iNum=1;//如果当前列是倒数第二列{if( j==(PANES_Col-2) ){pNext=newCompressN//如果下一列的值＝1，将+1写入压缩数据链pCompress，否则将-1写入压缩数据链pCompress；pNext-val=(Original[PANES_Col*i+j+1]==1)?1:(-1);pNext-next=NULL;pPre-next=pNpPre=pN iNum=1; //}}//}}//}}//}}//显示压缩结果，激活解压按钮pPre=pCompress-CStringcsCompress="",intiSum=0;while(pPre!=NULL){cs.Format("%6d",pPre-val);csCompress+=if(pPre-val0)iSum+=pPre-elseiSum-=pPre-if(iSum%PANES_Col==0)csCompress+="/r/n";pPre=pPre-}this-SetDlgItemText(IDC_EDIT_Compress,csCompress);CButton *pBpBtn=(CButton*)GetDlgItem(IDC_BUTTON_Uncompress);pBtn-EnableWindow(TRUE);图表4.6图像的游程压缩－压缩点击“解压”，将在还原图像区显示解压结果，如图8，代码如下。//如果解压的结果数组Uncompress没有填满{while( k&(PANES_Row*PANES_Col)){//如果压缩数据链pCompress上的数据已处理完，结束解压；if(p==NULL)//从压缩数据链上取一个数据；如果数据值val0,则向解压结果数组Uncompress中写入val个1，if(p-val0){for(int i=0; i&p-i++)Uncompress[k++]=1;}//否则写入val个-1；else{for(int i=0; i&(-p-val);i++)Uncompress[k++]=-1;}//准备取下一个数据；p=p-}//显示图像pTable2-Fill(Uncompress);第五章游程长度编码压缩算法的讨论游程长度编码压缩方法的压缩比与文本中字符重复出现的概率及长度有关。表5.1给出了对长度均为1000Bytes的不同文件，使用游程长度编码进行压缩后，压缩比、字符出现次数及重复字符串平均长度之间的统计和对比情况。根据表5.1的统计来看，在文本中字符重复出现次数相同的情况下，重复字符串的平均长度越长，压缩比就越高；在重复字符串的平均长度相同的情况下，字符重复出现的次数越多，压缩比也越高。出现重复字符次数 重复字符串的平均长度 压缩比（%） .016.891.966..4.9634.98结 束语转眼之间，两个半月的毕业设计即将结束，我们也将离开学校，踏上工作岗位。经过这段时间的学习与实践，我对游程长度编码与信号编码的发展及现状有了更深刻的认识，意识到数据压缩与解压对社会生活的巨大影响及其潜在经济效益，并对Microsoft Visual C++6.0软件有了一定程度的了解，学习了信源编码的相关知识及如何利用Microsoft Visual C++ 6.0编译程序。
　　经过这段短暂时间的学习，我想我对于知识的猎取是有限的，关键是我学会了如何用认真、严谨的学习态度去面对工作，如何用自学的方法来处理问题，如何以积极的团队协作精神去相处同组同学。我们这次主要涉及的是C++，图象压缩编码相关领域的课题，由于以前没有系统地学习过这方面的知识，所以肯定有一定的缺陷，恳请老师们耐心批评与指正。游程长度编码RLC一般不直接应用于多灰度图像，但是比较适台于二值图像的编码，例如传真图像的编码等．为了达到较好的压缩效果。有时游程长度编码和其它一些编码方法混台使用．例如，在JPEG中，游程长度编码和离散余弦变换DCT(Discrete CosineTransform)及霍夫曼(Huffman)编码一起使用，对分块做完DCT及量化后的频域图像数据做z形扫描，然后做游程长度编码，对游程长度编码的结果再做霍夫曼编码.游程压缩作为数据压缩技术的一个分支，理论浅显，压缩比之高已经让人刮目相看，这不由令人对数据压缩技术肃然起敬。走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；新兴的神经网络理论将数据压缩推向了一个新的高度；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准使小波理论傲视群雄。可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废。致 谢本篇论文的选题、收集资料和撰写工作都是在田雨波老师的指导下完成的。在毕业设计期间，田雨波老师在工作繁忙的情况下，不辞辛苦，多次为我们查找、提供资料。
　　田雨波治学严谨、待人亲切的态度，深深的影响了我们。为此，我向田老师表示深深的谢意，感谢田老师在毕业设计期间对我们的关怀和指导。在此期间，信号与系统实验室的老师们也为我们提供了许多帮助，在此对他们也表示深深的感谢。在此期间，给老师们带来的种种不便，请老师们谅解。对那些曾经帮助过我的同学们也表示衷心的谢意。 参考文献[1] 刘冰, 游程长度编码算法的研究, 天津理工学院学报, 10(6): 77～81.[2] 王辉, 王晓群,多媒体应用基础, 清华大学出版社, 1999年.[3] 洪小达，《多媒体计算机与数据压缩技术》 中国国际广播出版社 1999年6月[4]黄国胜 刘珠 饶一梅，《多媒体速成与应用》 天津科学技术出版社 1997年3月[5] 翟屺，《数字图象处理技术与应用》 电子工业出版社 1997年5月[6] Steve Rimmer,木杉，《Windows图象处理实用技术和范例》 学苑出版社 1994年11月[7] 《精通Visual C++ 图象编程》电子工业出版社 2003年1月[8]朱志刚，《数字图象处理》清华大学出版社1998年1月[9] J. Oliver, M. P. Malumbres, A simplepicture coding algorithm with fast run-lengthmode.附录2快速游程长度在简易图像编码算法中的应用J. Oliver, M. P. MalumbresE-mail: {joliver,mperez}@disca.upv.es摘要：复杂图像编码算法曾提议使用高率失真函数的编码方式，也详细设计过信噪比和解析分辨率和误差纠错。这些算法在设计和计算时的复杂性导致了执行速度的减缓。这篇论文中，我们提供一种全新的小波图象编码方式，它在定义和执行时非常简易，并且表现比以前的算法快很多。
　　尽管非常简易，它的实际执行表明它的压缩比率和失真度都在艺术要求范围内。因此，我们的运算编码法则目前与SPIHT和JASPER（官方联合图象专家组2000）达到同样的信号-噪音功率比。更重要的是，由于SPIHT缺乏交互式，执行时间较长，我们的方案比SPIHT更有发展潜力。1．介绍小波图象编码器已证明在最优化率失真时是最好的压缩数据方案。尽管如此，主要的缺点是小波图象编码器[1][2][3]是相当复杂的。那主要是由于压缩位流处理，通过不断的重复，达到了来用于不同的位流的极限。通过这样的方法，很容易达到使用先进的编码的位流，自从更多的比特位图获得更大的信噪比用到图片中。尽管嵌入式的位流是图象编码器的优点，但它不总是必须的，并且有其他的可选择的特点例如，解析度可测量性可能对最终效果来讲更加有价值。
　　这论文中，我们提供一个非常简易快速的运算法则，它很容易把小波系数编码下来，而且都不需要先把每个位流先循环扫描一遍。相反，从头到尾仅需要一次扫描。在第2段中，小波编码器将做详细介绍。第3段将会调谐好并评价。第4段将介绍游程长度模式以及在第5段中执行中达到数字化结果。最后，结论将会在第6段。2．简单小波图象编码器在先前的运算法则中，量子化进程是由2种策略执行的，一个是简易粗糙的，一个是完美的。较好的一边包括把标量的统一量子化应用到系数中，并且紧随DWT应用后执行。
　　另外一个粗糙的方法是基于去除比特位图中最少的系数的重要部分，它与运算法则应用同时执行。现在我们把RPLANES设为被清除的不太重要的比特信息数量。在编码器初始化时，最大数量的比特数量（我们设为MAXPLANE）已经被记数。这个MAXPLANE和RPLANES将作为参数送往编码器。然后，我们将初始化一个自适应的算术编码器，它是用来将系数所需要的比特数量编码。然后我们把所有系数编码。因为那些需要的系数比编码RPLANES比特()需要得更多，我们使用一个算术特征来表明到底编码那个特征多少比特是必须的。仅仅MAXPLANE－ RPLANES个记号是必须的来描述信息。
　　尽管如此，一个多余的符号（成为LOWER符号），还是必须用来编码这样的系数，系数是略微小于建立时的极限()的。请注意当它在抛弃最少的重要RPLANES比特时，还不是0的话，我们称 是一个重要的系数。换言之，即时.在下一阶段，小波系数将按如下步骤编码好。对于每个分块，所有的系数都将被仔细扫描。为了保护信息的位置，扫描信息不是逐行进行的，而是取中等大小的码块，一个适合扫描的大小的块，其大小与分块（在二维分解中最小且最少频率的分块）。对于每个分块的系数，如果它是重要的，一个用来描述系数的比特数量的标志将会被算术编码。在同样大小的分块中将有大小相似量级的系数，并且由于规则，我们也将确立扫描系数。我们的自适应的运算编码能够非常有效率地再次描述出信息内容。
　　尽管如此，我们并没有足够的信息来重新正确地构建系数，所以我们仍需要将重要的比特信号编码。另一方面，如果一个系数不是重要信息，我们应该将其编为LOWER信号，所以解码器可以肯定它已经被完全量子化，并且因此系数和信号都与信息没有联系。你会注意到当我们把重要信息编码时，最开头的RPLANES和最重要的比特并没有被编码，通过暗示比特编码时需要多少数量的算法记号，解码器能将最重要的比特解码。另外，为了提高执行速度，重要的比特和信号将原封不动地编码起来，导致了在率失真函数上表现出非常少的信息丢失。如下编码算术法则，算术法则1：（E1）INITIALIZATIONOutputrplanesOutput maxplane= { (E2) 输出系数。在每个分块中扫描If Arithmetic_output Output Output sign( )Else Arithmetic_outputLOWER3．调整提议的运算法则尽管被提议的运算法则很简易，它的率失真函数表现可以跟艺术编码要求可以媲美。它提供了匹配的调谐参数。在这段，我们将提供运算法则的细节部分，它使得运算法则执行得更有效。
　　为了表现出理想的执行结果，我们选择了一个标准的LENA的照片做为基本的模板。一个自适应的运算编码器是用来有效地将译码进程输出编码。一个自适应编码器使用一个动态的柱状图来估计目前符号出现的几率。为了提高命中几率，将一个与每时每刻出现符号联系着的频率计数编码。因此，我们引入一个全新的参数，参数是反映柱状图随每个符号的增长趋势，我们把这个参数称为增长因素。在最初始的自适应的运算法则编码器,每个的价值就被用来做参数。如果它比其他的有更高的价值，它的自适应运算编码器将很快地会聚本地图片的特征，导致了更高的压缩比率。尽管如此，增长过高将会把模型扭变得不相称的，导致了执行的错误。
　　另外，参数将用maximum frequency count求得。当它的数值超过了所有的编码器柱状图的总和（这个数值称为cumulativefrequencycount），所有的数量将被减半，并且超出的部分将被阻止（更多细节在第4段）。最原始的提议参数是16384（当使用16进制时），但是实验结果使得我们稍微降低数值，12500，所以模型里减半了很多。在实验一中，我们测试了不同的增长因素（例如低，中，高压缩比率2bpp，0.5bpp，0.25bpp，0.125bpp）对信号-噪音功率比的影响。实验结果表明，对于maximum frequencycount为最大值12500时，增长因素在200时均达到了最佳效果，并且与原始数据相比得到了0.1~0.3dB的增益。在前面曾提到，对于同样大小的码块，系数有同样大小的量级。为了达到较好的增益，编码的系数的量级将控制好不同的柱状图，当然它也受其他因素控制。特别地，由于左边和上方系数的重要性（如果扫描命令已经执行，系数就已经编码了），我们提议使用两种不同的前后关系。
　　所以，如果两个系数都不重要，由它导致的编码也将会是不重要的，因此得使用一个特殊的模型。使用这样的特殊模型的好处在图1中表现出来了，当信号-噪音功率是由两种因素引起，将会达到0.2dB的增益。另外，在图中我们可以看到我们的编码器在按照率失真函数里达到了艺术要求，与其他几个编码方式，达到了相似的信号-噪音功率比。编码器速率 提议的算法 CTXT编码 JPEG2000 SPIHT210.50.250.125 45.33..34..34..34.1131.10不同压缩比率和编码方式处理LENA照片时的信号-噪音功率比尽管我们算法执行比SPIHT和Jasper快很多，它呈现出一个主要的劣势在低比特图片。如果我们分析先前的部分，我们会发现所有记号都明白地编码了，高长记号是算术上的编码。众所周之，自适应编码器是图片编码系统的最慢的部分。在我们算术法则上，实验上的结果表明对于低比特速率，超过75%的部分花费了大部分在算术编码系统上。另外大部分的被编码的记号已经完全地量子化，并总是用同样的记号编码LOWER。
　　为了克服这样的问题，并减少这些事情的复杂性，一个新的分组方法来应对LOWER将被在下一段介绍。4．快速游程长度模式在这一段，游程模式曾在第2段中先前介绍过。由于容易在高压缩比率信号易出现的大量连续的LOWER符号，这个游程模式在处理到时能降低处理的复杂性。人们对压缩执行时期望较小的提高，是由于我们替代了很多连续的符号，或是比较少出现的暗示了多少LOWER信号的符号。因此，尽管很少数量的符号被编码，离散的几率相反地影响自适应编码器，因为编码器随着压缩比率提高而工作更好。我们知道在这新的尝试里，仅当LOWER符号数量超过极限数量（称为ENTER_RUN_MODE参数）时，游程长度才将LOWER编码。另外，由于大量数量的游程长度符号代替了同样的短的流信号——LOWER符号，这算法的压缩性能将将会稍微减少。当游程被更重要的信息打断，并且这个更重要信息的数值足够高（比ENTER_RUN_MODE还要高），这个游程的数值必须输出到解码器，同时游程重新安排。
　　在这种要求下，一个全新的符号将引进介绍给大家：RUN，它用来反映一个游程即将被编码。在将RUN编码后，RUN的存储方法跟重要数值的存储方法一样。首先，需要将RUN数值编码的比特数量，在算术上输出（使用先后层次关系），然后数据将原封不动的输出。如下是全新的游程长度编码的算法2：(E1)INITIALIZATIONOutput rplanesOutput maxplane= { Run_length=0(E2)输出系数。在每个分块中扫描 If Increase run_lengthElseIf run_length 0Ifrun_length&enter_run_modeRepeat run_length timesArithmetic_outputLOWERElse Arithmetic_output RUNRbits= Arithmetic_outputrbitsOutputRun_length=0Arithmetic_output Output Output sign()5．数字结果我们已经执行过这样的运算法则来测试它的压缩和复杂性。读者可以在http://www.disca.upv.es/joliver/wavelet/RLW.zip轻易地在32位机器上测试这样的结果。为了比较我们的算法，使用了标准的lena和barbara的个人照片。所有的结果在如下的表格里表现出来了。
　　编码器速率 游程长度编码 JPEG2000 SPIHT10.50.250.125 36.25.12 37.25.25 36.24.86不同解码器在处理barbara图片时的信号噪音功率比编码器速率 SPIHT JPEG2000 CTXT编码 游程长度编码210.50.250.125 210..736.8 278.23..264.352.747.044.0 95.461.237.025.519.7不同编码器编码的执行时间（百万级别每秒）编码器速率 SPIHT JPEG2000 CTXT编码 游程长度编码210.50.250.125 217..659.7 108.872.351.438.131.3 91.370.260.355.453.0 93.763.036.324.117.8不同编码器解码的执行时间（百万级别每秒）6．结论在这论文中，我们已经描述了一个全新简易的小波游程编码算法。这样的解码器更简单方便。不过尽管复杂性比其他的（如JPEG2000和SPIHT）少很多，游程长度是介绍来减少对低比特数据的处理。这样我们可以看到执行速度于10倍的Jasper，3.5倍的SPIHT。由于较少的复杂性，需要较少的存储空间，无系统依赖性和高速的编解码能力，我们相信这样的编码方式会成为最真实的交互式多媒体通信最佳选择
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1552208次
积分：20155
积分：20155
排名：第338名
原创：525篇
转载：191篇
评论：272条
(1)(1)(1)(2)(2)(2)(1)(1)(1)(1)(2)(5)(1)(2)(4)(8)(10)(5)(3)(12)(7)(1)(6)(9)(10)(31)(43)(25)(12)(13)(15)(12)(10)(4)(13)(8)(6)(6)(22)(1)(7)(29)(11)(24)(20)(23)(23)(5)(8)(3)(1)(4)(10)(17)(9)(19)(33)(23)(6)(1)(1)(11)(1)(5)(2)(1)(2)(12)(5)(18)(22)(2)(2)(2)(3)(30)(2)(2)}