动态分块隔行扫描算法设计与实现

赵司井，林宏刚

(成都信息工程学院信息安全工程学院，四川成都610225)

0 引言

随着网络技术的发展，远程计算机教学、远程网络监控、视频会议等工程得到广泛应用[1－2]。而在这些工程应用中，都需要传输计算机屏幕位图[3]。因此，为保证给用户提供良好的屏幕图像传输服务的同时不影响其他应用程序提供服务，实时屏幕图像传输系统应当满足以下条件:低CPU使用率，低带宽占用率[4－5]，尽量避免延时、抖动和花屏现象发生等。为满足这项条件，通常采用2种方法:一是提高网络带宽;二是减少传输数据量[6]。由于网络带宽很大程度上受限于网络硬件，因此，通过优化压缩算法和传输算法，减少数据传输量成为解决问题的关键[7]。

目前实时屏幕图像传输系统中常用的图像处理算法为固定分块隔行扫描算法[8]，该算法将屏幕进行分块，并对每个分块进行编号，每个分块的大小和分块的数量固定，然后将前后相邻两幅位图的数据保存，并分别按照对应的编号块进行对比，若图像有变化则压缩发送当前块中的图像。由于固定分块隔行扫描算法每次只发送变化块中的图像数据，所以能够降低数据的传输量。但是，由于这种方法对屏幕分块的大小和数量固定，当屏幕图像变化区域正好位于各个分块的临界点时，就会发送大量的屏幕分块，造成很高的带宽占用和CPU使用率。

分析固定分块隔行扫描算法的不足，设计并实现一种动态分块隔行扫描算法，该算法相比传统的固定分块隔行扫描算法更能有效地降低CPU使用率，减少带宽占用率，提高图像传输的性能。

1 固定分块隔行扫描算法简介

固定分块隔行扫描算法是一种在图像处理中比较经典的算法，该算法首先对屏幕进行分块处理，并对分块进行编号。考虑到分块尺寸和分块内部变化像素点等因素，目前较为理想的划分方案为16X8[9];接着要保存前后相邻的bmp位图数据;最后对前后两副位图分别按照对应的编号块进行对比找出变化的数据块。对比的方法是隔若干行(根据具体情况而定)对比前后两幅图像的一行中的像素点是否相同，若不同则压缩发送当前块中的图像。由于是隔若干行对比一行，因此称其为隔行扫描。为提高扫描的效率，需要设置一个扫描行数的阀值，如果从开始扫描就有连续的扫描行都相等，当这样的行数达到该阀值时，就认为该块没有发生变化，并终止该块的扫描，进行下一块的扫描工作。

由于固定分块隔行扫描算法对屏幕分块的大小和数量固定，经过扫描后得到变化的分块，每次只压缩发送这些分块。当屏幕变化区域正好位于各个分块的临界点时，就会将其占用的所有分块全部发送，这样就发送了大量的冗余数据，造成不必要的带宽占用，如图1所示。

图1 屏幕图像变化矩形区域

从图1可以看出，屏幕图像在12个块中都有变化区域，其大部分变化区域都位于6、7块，2、3、5、8、10、11块占有少部分变化区域，而1、4、9、12仅占有一点变化区域。固定隔行扫描算法在扫描如图1这种屏幕图像时，会认为这12个块都是需要压缩发送的数据。这样就造成CPU使用率大，带宽占用高。

2 动态分块隔行扫描算法

动态隔行扫描算法不是将屏幕图像分成固定大小和数量的分块，而是首先比较相邻两帧图像，找出所有图像变化，然后根据变化像素点的坐标得到面积最小的不重叠矩形区域的集合，每次只发送矩形区域的集合包含的图像数据，以减小每一帧的传输数据，达到有效降低传输带宽占用率和CPU使用率的目的。

2.1 算法原理

算法的重点在于如何根据变化像素点的坐标得到变化矩形区域范围。

式(1)和式(2)是根据变化像素点判断矩形R范围的算式。其中Rl和Rt代表矩形左上角的横坐标和纵坐标，Rr和Rb代表矩形右下角的横坐标和纵坐标，Px和Py代表变化像素点的横坐标和纵坐标，Py0代表第一次变化像素点的纵坐标。按照2D图形学的习惯，X轴水平向右递增，Y轴水平向下递增。根据式(1)和式(2)即可求变化矩形区域的范围。

动态隔行扫描算法同样先将前后相邻两幅位图的数据保存，并隔行扫描比较两幅图像的像素点是否相同。当扫描到不同的像素点时，会将该像素点的坐标(Px0，Py0)进行记录，作为变化矩形区域的左上角坐标(Rl，Rt)，并且将已扫描到不同的像素点状态记为true。当再次扫描到不同像素点且扫描状态为已扫描到不同像素点时，会将该像素点的横坐标Px同矩形左上角的横坐标Rl进行比较并取最小值，同时矩形右下角的坐标(Rr，Rb)和该点的坐标(Px，Py)比较并取最大值，并将行像素点不同状态记为true。即:

当扫描完一行时，会先判断行像素点不同状态是否为true，若为true，表明该行已有像素点不同;若为false，则表明整行无不同像素点，此时退出循环，这样就得到变化的矩形区域块。下次隔行扫描的位置从该矩形块的下方一行开始进行。动态隔行扫描算法的示意图如图2所示。

图2 动态分块隔行扫描示意图

2.2 算法设计

动态分块隔行扫描算法工作流程如下所述:以固定分块的隔行扫描为基础，扫描屏幕图像的像素点，根据变化像素点的坐标动态确定需要发送的矩形块。在隔行扫描有变化的像素点时，记录该点坐标为矩形左上角坐标，然后继续扫描，每次扫描都会将像素点的坐标和矩形右下角的坐标进行比较并取最大值，和矩形左上角横坐标比较并取最小值。当扫描到无变化行时退出循环。算法流程如图3所示。

首先获得屏幕的宽度width和高度height，2个变量将作为行扫描变量iRow和列扫描变量i的范围。列扫描变量i会根据隔行扫描变量iRow的步长扫描像素点，当扫描到不同的像素点时，先判断是否第一次像素点不同变量IsFirstUnequal的值是否为true，如果为true，则将当前坐标(i，iRow)记录为矩形区域的左上角坐标(left，top)，然后将IsFirstUnequal置为false。矩形的右下角坐标(right，bottom)也记为(i，iRow)，并将行坐标点不同变量IsLineChanged设为true。当再次扫描到不同的像素点时，将该点的坐标(i，iRow)与矩形的右下角坐标(right，bottom)进行比较，将较大的那个值作为矩形右下角的新坐标。同时还会将矩形左上角的横坐标left同该点的横坐标进行比较，并取较小的值作为矩形左上角横坐标的新值。扫描完一行以后，先会判断IsLineChanged的值，如果为true，即本行有不同的像素点时，将IsLineChanged修改为false，行扫描变量会根据隔行扫描的步长扫描下一行像素点。当扫描到一行无不同的像素点时，IsLineChanged的值必然为false，此时退出循环，即得到变化矩形区域的大小。由于行扫描变量和列扫描变量均为静态变量，下一次调用函数时继续从该行向下扫描。这样每次扫描都会动态得到变化的矩形块，每次仅压缩传输这些变化块。

图3 动态隔行扫描算法流程图

3 对比测试

为验证动态分块隔行扫描算法是对于固定分块隔行扫描算法实际性能的提高以及数据传输的节省，设计了一个对比测试。

测试包括2个方面:一是测试两种算法对系统CPU资源消耗的情况;二是测试2种算法对带宽资源占用的情况。测试对2种算法中所做的文档操作、网页浏览操作、视频操作分别每隔20秒采集一次CPU占用率和带宽占用情况，持续5分钟，并重复100次，最后取平均值作为其对比结果。测试环境选用2台配置为Inter I7 3630qm四核CPU、6G内存、分辨率为1920*1080的计算机。具体相关参数如表1所示。

表1 测试环境参数表

测试所有对比操作都在相同的环境下进行，相同的系统环境、相同的文档操作、相同的网页浏览内容、相同的视频浏览内容的流程和步骤。

(1)CPU使用率对比

测试对比包括3种常见操作:文本操作、网页浏览和播放视频。

文本操作比较。图4为固定分块与动态分块隔行扫描算法的文本操作比较情况，从图中可以看到2种方法的文本操作的CPU占用率在6%～12%波动，并得出动态分块隔行扫描操作消耗CPU资源情况较于固定分块隔行扫描操作整体上低约25%。

网页浏览操作比较。图5为固定分块与动态分块隔行扫描算法的网页浏览操作比较情况，从图中可以看出，在第3分钟时固定分块隔行扫描算法的CPU占用率要低一点，因为此时屏幕图像的变化区域正好位于某个或者几个分块中，但是整体上动态分块隔行扫描算法CPU占用率比固定分块隔行扫描算法低约12%。

图4 文本操作比较

图5 网页浏览操作比较

视频播放比较。图6为固定分块与动态分块隔行扫描算法的文本操作比较情况，从图中可以看出，由于视频画面的频繁变换因此两者对系统CPU资源的消耗比较接近，但是整体上，动态分块隔行扫描算法在视频操作CPU资源消耗上比固定分块隔行扫描算法高约5%。这是由于当图像变化区域数量超过一定数值的时候(200左右)，如果图像变化区域都位于固定分块隔行扫描算法的一个或几个分块中，固定隔行扫描算法仅需扫描比较这几个分块。而动态隔行扫描算法对每个变化区域都要进行扫描和比较，这样大量占用CPU资源。所以在视频播放时(特别是运动画面)，动态分块隔行扫描算法并不能很好地降低CPU资源消耗。

(2)带宽占用

图6 视频操作比较

文本操作比较。图7为文本操作的情况下各自占用的带宽情况，从图中可以看出，文本操作屏幕图像的变化较少，需要压缩和发送的数据量也较少，2种算法占用带宽都不高。在1～2分钟前，有个最低值，因为该时间点屏幕几乎无变化块，所以发送数据量处于最小值。从总体上看，动态分块隔行扫描算法占带宽比固定分块隔行扫描算法低约4%。

网页浏览操作比较。图8为网页操作的情况下各自占用的带宽情况，从图中可以看出网页操作屏幕图像的变化也较少，仅需要压缩和发送变化的区域。整体上，动态隔行扫描算法占用的带宽比固定隔行扫描算法低约10%。

图7 文本操作比较

视频操作比较。图9为视频操作的情况下各自占用的带宽情况，从图中可以看出，固定分块隔行扫描算法的带宽占用情况波动较大，而动态分块隔行扫描算法波动较小。1～3分钟，固定分块隔行扫描算法的带宽占用明显低于动态分块隔行扫描算法。而从整体上来看，在视频操作时，动态隔行扫描算法的带宽占用率甚至高于固定分块隔行扫描算法约7%。这是由于动态隔行扫描算法的数据传输量随着图像变化区域数量的增加不断增大，由于其发送到矩形变化区域还包含额外的未发生变化图像数据，所以当图像变化区域数量超过一定数值的时候(200左右)，每帧传输的数据总量超过固定分块隔行扫描算法的传输的数据总量。所以在视频操作时(特别是运动画面)，动态分块隔行扫描算法并不能很好降低数据传输量。

图8 网页浏览操作比较

图9 视频操作比较

4 结束语

动态分块隔行扫描算法利用矩形结构存储图像的变化区域，用点坐标结构存储矩形中的变化分块，使动态分块隔行扫描算法无论在系统性能，还是在带宽占用方面都有优势。实验结果表明，动态分块隔行扫描算法在图像变化较小，且变化多集中在某一处或者某几处的应用场景下，相比传统的固定分块隔行扫描算法更能有效地降低CPU使用率，减少带宽占用率，提高传输的性能。该算法也有一定的局限性，当图像出现大量变化对象的时候(如播放视频)，该算法并不能很好提升性能和降低数据传输量，甚至有可能适得其反。因此，如果能根据实际情况选择使用该算法，将有效提高图像传输性能和降低带宽占用率。

[1] T Lin，P Hao.Compound Image Compression for Real-time Computer Screen Image Transmission[J].IEEE Trans-action on Image Processing.2009，14(8):993－1005.

[2] Jesse S Jin，Sue R Wu.Screen Capture-A Vector Quantisation Approach[D].Biomedical and Multimedia Information Technology Group School of Information Techologies[D].University of Sydney，NSW，2011.

[3] 耿增民，余正涛，康海燕.一种提高计算机屏幕图像传输速度的方法[J].计算机工程应用，2005，(1):114－116.

[4] 李芳.屏幕共享中截屏技术的研究与实现[J].湖南冶金职业技术学院学报，2009，9(1):17－18.

[5] WU C，LU D R，YANG K S.K Support system.knowledge support for disseminating and sharing task-relevant knowledge[A].Proceedings of the 2009 IEEE International Conference on Information Reuse and Integration[C].2009:332－337.

[6] 李小鹏，刘连东，李亚敏，等.一种改进的远程屏幕图像实时传输方法[J].计算机应用，2007，27(3):704－705.

[7] 刘德胜.基于矩形分割的局部渲染技术在无线图像通信中的应用[J].成都信息工程学院学报，2012，27(4):355－358.

[8] 左强翔，吴洁.一种基于分块采集和压缩技术的屏幕共享方案[J].计算机技术与发展，2008，18(4):207－209.

[9] 罗红，蔡德俊.桌面图形图像序列压缩与传输研究[J].计算机应用，2005，25(6):1330－1304.

[10] 张红祥，车鹏飞.屏幕图像实时传输方法研究及一种改进实现[J].科技信息，2009，(33):821－824.

[11] 徐向阳，曹帮琴.差异截图法实现屏幕图像快速传输[J].南阳师范学院学报，2007，6(9):63－65.

[12] 朱东辉.基于WinSock通信的远程屏幕抓取方法与实现[J].计算机应用研究，2005，(8):204－206.

[13] 吴栋淦.两种屏幕图像捕获方案的比较[J].计算机技术应用，2007，(3):9－11.

[14] 肖道举，刘洪峰，陈晓苏.面向远端屏幕监控的一种图像压缩传输方法[J].计算机工程与设计，2005，26(12):3356－3364.

[15] Jeffrey Michael Gilbert.Test/Graphics and Image Transmission over Bandlimited Lossy Links[D].University of California，Berkeley，2010.