動態分塊隔行掃描算法設計與實現

趙司井，林宏剛

(成都信息工程學院信息安全工程學院，四川成都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.