关于屏幕捕捉程序中使用的压缩算法描述.doc

《关于屏幕捕捉程序中使用的压缩算法描述.doc》由会员分享，可在线阅读，更多相关《关于屏幕捕捉程序中使用的压缩算法描述.doc（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、应用技术研究作者简介：戚 利 男 济南铁路局党校讲师1基于窗口图像的压缩算法基于窗口图像的压缩算法戚 利文章摘要文章摘要 本文从分析 DIB 位图数据入手，结合对屏幕显示特征的分析，提出了一种针对程序界面的实用的图象数据压缩算法。该算法参照了 RLE 行程压缩以及基于熵的 Huffman 压缩理论，提出“以保留主色调，模拟生成过渡颜色”为基本思路的压缩算法。关关 键键 词词 压缩 算法 屏幕捕捉 图象处理 RLE为了能在捕捉对方屏幕的时候得到最小的数据传输量，需要一种压缩率极高、压缩速度相对较快并且失真很小的算法。通过对常用程序界面的截图像素进行分析，本文提出了一种针对性很强的关于 DIB 位

2、图的高质量的压缩算法。一、窗口图象特征分析一、窗口图象特征分析1、窗口界面的一致性由于 WINDOWS 操作系统软件界面的一致性，导致了大量相同的颜色出现在将被压缩的数据中。比如，捕捉的示例图象中存在大面积的工具栏背景颜色（EC-E9-D8） 。对于这种出现频率极高的颜色我们可以通过使用更少的位数来表示，原来用3 个字节来表示（EC-E9-D8） ，我们可以只用一个字节甚至一个位来表示（EC-E9-D8） ，这样就大大减少了数据的冗余，达到压缩的目的。2、颜色的连续性一般而言，在程序界面中存在颜色跳跃的几率很小，大部分采用连续色或过渡色。这样，就给我们提供了一个通过计数来还原颜色区域的方法。我

3、们可以通过记录连续色的数量来减少连续色占据的空间。假设有一行全是一种颜色，那么这一行颜色一共占据了 400*3=1200 个字节的空间，我们可以使用 RLE 算法，通过记录颜色个数来达到压缩数据的目的。用一个字节记录像素数，用另外一个字节记录颜色在颜色表中的索引。于是，这一行数据就从存储 1200 个字节减少到只存储 10个字节。这也许就是屏幕图象压缩部分最大的看点了。3、主色调的一致性各应用系统为了保持与操作系统软件之间界面的统一，在程序设计上基本使用了相同的主色调作为窗口的颜色分配方案。这样，我们就能从一个窗口的图象中分析出主色调，并对主色调进行单独记录，以保证整体色调不失真。同时，使用主

4、题色调来模拟其他非连续区域的颜色，达到更有效地还原真实图象目的。二、窗口图象数据分析二、窗口图象数据分析首先，在 24 位真彩下捕捉屏幕的一角（大小200*100） ，使用 WINDOWS 操作系统自带的画图程序保存该图片。便于研究。 由于 24 位位图中使用三个字节（RGB）来表示一个像素的颜色，因此，BMP 文件图象内容的大小应该为：200*100*3/1024=58.5K 左右。这个大小在一般的网络中传输是没有问题的。但为了能获得动态更新（通常定义为 4 帧/秒） ，也就是一秒钟内传输到网络的数据量为 58.5*4=234K，这个数据量就相当大了，如果捕捉发生在因特网上，我们就无法保证远

5、程屏幕内容会流畅地显示出来。这就要求我们必须对该内容进行实时高效地压缩。以下是使用 DEBUG 工具获得的 BMP 图象数据最后四行共 200*3*4=2400 个字节，部分数据有所删节。-d 1708:0100 42 4D 96 EA 00 00 00 00-00 00 36 00 00 00 28 00 BM.6.(.应用技术研究21708:0110 00 00 C8 00 00 00 64 00-00 00 01 00 18 00 00 00 .d. 1708:0120 00 00 60 EA 00 00 00 00-00 00 00 00 00 00 00 00 . 1708:0130

6、 00 00 00 00 00 00 99 A8-AC 99 A8 AC 99 A8 AC 99 . 1708:0140 A8 AC 99 A8 AC 99 A8 AC-99 A8 AC 99 A8 AC 99 A8 . 1708:0150 AC 99 A8 AC 99 A8 AC 99-A8 AC 99 A8 AC 99 A8 AC . 1708:0160 99 A8 AC 99 A8 AC 99 A8-AC 99 A8 AC 99 A8 AC 99 . 1708:0170 A8 AC 99 A8 AC 99 A8 AC-99 A8 AC 99 A8 AC 99 A8 . -d 1708:0

7、300 AC 99 A8 AC 99 A8 AC 99-A8 AC 99 A8 AC 99 A8 AC . 1708:0310 99 A8 AC 99 A8 AC 99 A8-AC 99 A8 AC 99 A8 AC 99 . 1708:0320 A8 AC 99 A8 AC 99 A8 AC-99 A8 AC 99 A8 AC 99 A8 . 1708:0330 AC 99 A8 AC 99 A8 AC 99-A8 AC 99 A8 AC 99 A8 AC . 1708:0340 99 A8 AC 99 A8 AC 99 A8-AC 99 A8 AC 99 A8 AC 99 . 1708:0

8、350 A8 AC 99 A8 AC 99 A8 AC-99 A8 AC 99 A8 AC 99 A8 . 1708:0360 AC 99 A8 AC 99 A8 AC 99-A8 AC 99 A8 AC 99 A8 AC . 1708:0370 99 A8 AC 99 A8 AC 99 A8-AC 99 A8 AC 99 A8 AC 99 . -d 1708:0380 A8 AC 99 A8 AC 99 A8 AC-99 A8 AC 99 A8 AC FF FF . 1708:0390 FF D8 E9 EC D8 E9 EC D8-E9 EC D8 E9 EC D8 E9 EC . 170

9、8:03A0 D8 E9 EC D8 E9 EC D8 E9-EC D8 E9 EC D8 E9 EC D8 . 1708:03B0 E9 EC D8 E9 EC D8 E9 EC-D8 E9 EC D8 E9 EC D8 E9 . 1708:03C0 EC D8 E9 EC D8 E9 EC D8-E9 EC D8 E9 EC D8 E9 EC . 1708:03D0 D8 E9 EC D8 E9 EC D8 E9-EC D8 E9 EC D8 E9 EC D8 . 1708:03E0 E9 EC D8 E9 EC D8 E9 EC-D8 E9 EC D8 E9 EC D8 E9 . 170

10、8:03F0 EC D8 E9 EC D8 E9 EC D8-E9 EC D8 E9 EC D8 E9 EC .被标注的兰色部分是 BMP 的文件头，记录了整个文件的一些属性，比如大小，调色板个数，数据起始位置等，这些不是我们所关心的。我们主要来看一下紧跟在后面的像素颜色数据。可以看到，开始的连续三个字节代表了一个像素，也就是图象最左下角的第一个像素，是灰色。由于 BMP中存放像素三原色分量采用 G-B-R 的顺序，因此，我们取到的第一个颜色为：99-A8-AC，分别对应红色分量，绿色分量，兰色分量。我们可以从图象处理软件中获取到具备给定分量颜色值的颜色（172-168-153） 。通过对位图

11、文件的简单分析，我们可以对 BMP 文件中像素颜色数据的排列结构有一个初步的认识。三、压缩算法描述三、压缩算法描述1、有损压缩算法描述首先，建立一个颜色表，作为压缩数据的一部分。这个颜色表将保存 256 个三原色数据（大小应该为 256*3） 。为了模仿颜色，我使用了其中215 个作为自然色，而使用 40 个作为特征色，也就是前面提到的主色调。其实，这个颜色表就是我们经常听说的调色板。由于存在特征色，因此不同的捕捉图象调色板是不一样的。其次，我们使用（数量+索引）的方式来定义像素颜色数据。也就是说，我们将对捕捉区域内出现的所有颜色进行处理，并将所有颜色都统一到调色板中的 256 种颜色上。这样

12、，每一个颜色在表中都对应了一个索引。而这个索引只需要一个字节（8 位，其索引可以映射到 256 种颜色）存储就可以了。引入数量表示该颜色连续出现的个数。充分利用自然界面中的连续色这一特征来实应用技术研究3现压缩比的最大化。因此，最终的结果可能类似于下面的排列：D8-E9-EC-FF-FF-FF-99-A8-AC-00-00-00-00-00-33-FF-FF-CC-FF-FF-FFC8-02-01-01-C7-01-01-01-C7-01-01-01-02-00-03-02-C2-00其中第一行表示调色板数据，一共有256*3=768 个字节，后面紧跟着的就是压缩后的数据(第二行)，我们可以这

13、样来读：200（C8）个深灰色（99-A8-AC） ；1 个白色（FF-FF-FF） ，199 个工具栏背景色（D8-E9-EC） ；1 个白色（FF-FF-FF） ，199 个工具栏背景色（D8-E9-EC） ；1 个白色（FF-FF-FF） ，2 个工具栏背景色（D8-E9-EC） ，3 个深灰色（99-A8-AC） ，194 个工具栏背景色（D8-E9-EC） ；一共是四行，每行 200 个字节。这四行数据没有压缩时的大小为：200*3*4=2400 个字节，经过压缩以后大小为：768+18=786 个字节(这里包含了固定大小的调色板长度)压缩比：(2400-768)/2400*100%

14、=68%按照这个思路下去，最终图象大小应该变为200*100*3*32%/1024=19k，很明显，图象变小了，尽管压缩比看起来不算理想，但在这个例子中调色板本身的数据在当前四行图象数据中占据了相当大的比重。图象尺寸超过 20*20，调色板的数据相对来说就小得多了。2、算法执行效率和压缩效率假设图象大小为 x*y 像素，则最低复杂度：6*6*6+3xy+40+3xy最高复杂度：6*6*6+3x2y2+40*7xy+3xy最高压缩比：(3xy-(2xy+256*3)/256)/3xy*100%最低压缩比：(3xy-(2xy+256*3)/ 3xy*100%四、程序实现四、程序实现1、压缩算法（1

15、）首先构造 256 色调色板B G R 0 0 0 52 52 51 104 104 102 156 156 153 202 202 204 255 255 255按照排列组合算法将值（共215 种颜色）写入调色板，偏移在40*3=120 处（要保留40 个给特征色）（2）根据图象数据构造调色板的前 40 个颜色（从 0 到 39）统计图象中出现的颜色，将排在前 40 位的颜色写入调色板首部作为特征色，这里用到的数据结构 为：GBR频率（双字）00FF1A8A47h0E4312780Fh0987FF7768h表 1：特征色频度表示方法（3）查找颜色所对应的索引假设现有一个颜色，BGR 分量依次

16、为 66-5A-D1，接下来我们需要从调色板中查找与之最相近的颜色，如果我们通过对每一个颜色进行比对，则运算效率将大打折扣。我们可以从调色板自然色的合理构造这个角度来解决这个问题。调色板最终的数据排列将会是：00-00-00-00-00-33-00-00-66-00-00-99-这是构造自然色时使用的六个分量值：0,33H,66H,99H,CCH,FFH。首先，依次将三个分量与对应的值比较，获得每个分量的编号：编号 0 1 2 3 4 5颜色值 Ai 0 51 102 153 204 255B=102 Min|102-Ai|对应的编号为 2G=90 Min|90-Ai|对应的编号为 2应用技术

17、研究4R=209 Min|209-Ai|对应的编号为 4(注意，前 40 个颜色（0 到 39）为整个图形中出现频率最靠前的 40 个，这 40 个颜色不能取近似值，以保证整个画面效果，也就是说要保证主色调不变)，以下是计算索引的方法： m=i(如果 value=Ai,iAi,i40) 首先检索看该颜色是否与前 40 个颜色值匹配，如果不是则根据后一个公式计算出该颜色的索引值 m=36*2+6*2+4+40=128：（4）更换当前颜色为调色板颜色，根据索引号将当前颜色更换为调色板上已有的颜色。（5）重新遍历整个图象数据，使用 RLE 行程压缩数据。2、解压算法解压就相对简单多了，根据图象颜色连

18、续出现的个数以及在调色板中的索引重现 24 位模式下的图象数据，这里就不做介绍了。3、效果对比作为一种算法设计是否好坏，最有利的说服是通过实际比对。为了测试该算法的实际效果，我将原始图以多种不同的方法进行了转换。以下是比对效果：转换 方式原始图256 色 位图画图里 保存为 JPG格 式本算法本算法大小59k(600 54)21k(210 78)9k(868 3)6k(635 8)6k(6358)颜色 数24 位256 色256 色256 色 （不含 特征色）256 色 （含特征 色）效果颜色逼 真颜色丢 失了不 少,尤其 是特征 颜色杂点明 显增多无杂点， 主色调 失真， 压缩速 度快效果几乎 与原图一 样五、算法改进五、算法改进其实，这个算法还有许多需要改进的地方，比如，在使用 RLE 时可以增加控制符，减少一个像素出现几率较多的情况，还可以在压缩以前分析图象数据，针对纵向连续色使用该方法压缩比较小的缺点进行改进。也可以使用算法模拟中间色以达到减少颜色表的目的。通过减少颜色表的大小达到减少每个像素的颜色占用字节数。