動態(tài)分塊隔行掃描算法設(shè)計與實現(xiàn)

趙司井，林宏剛

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

0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，遠程計算機教學、遠程網(wǎng)絡(luò)監(jiān)控、視頻會議等工程得到廣泛應(yīng)用[1－2]。而在這些工程應(yīng)用中，都需要傳輸計算機屏幕位圖[3]。因此，為保證給用戶提供良好的屏幕圖像傳輸服務(wù)的同時不影響其他應(yīng)用程序提供服務(wù)，實時屏幕圖像傳輸系統(tǒng)應(yīng)當滿足以下條件:低CPU使用率，低帶寬占用率[4－5]，盡量避免延時、抖動和花屏現(xiàn)象發(fā)生等。為滿足這項條件，通常采用2種方法:一是提高網(wǎng)絡(luò)帶寬;二是減少傳輸數(shù)據(jù)量[6]。由于網(wǎng)絡(luò)帶寬很大程度上受限于網(wǎng)絡(luò)硬件，因此，通過優(yōu)化壓縮算法和傳輸算法，減少數(shù)據(jù)傳輸量成為解決問題的關(guān)鍵[7]。

目前實時屏幕圖像傳輸系統(tǒng)中常用的圖像處理算法為固定分塊隔行掃描算法[8]，該算法將屏幕進行分塊，并對每個分塊進行編號，每個分塊的大小和分塊的數(shù)量固定，然后將前后相鄰兩幅位圖的數(shù)據(jù)保存，并分別按照對應(yīng)的編號塊進行對比，若圖像有變化則壓縮發(fā)送當前塊中的圖像。由于固定分塊隔行掃描算法每次只發(fā)送變化塊中的圖像數(shù)據(jù)，所以能夠降低數(shù)據(jù)的傳輸量。但是，由于這種方法對屏幕分塊的大小和數(shù)量固定，當屏幕圖像變化區(qū)域正好位于各個分塊的臨界點時，就會發(fā)送大量的屏幕分塊，造成很高的帶寬占用和CPU使用率。

分析固定分塊隔行掃描算法的不足，設(shè)計并實現(xiàn)一種動態(tài)分塊隔行掃描算法，該算法相比傳統(tǒng)的固定分塊隔行掃描算法更能有效地降低CPU使用率，減少帶寬占用率，提高圖像傳輸?shù)男阅堋?/p>

1 固定分塊隔行掃描算法簡介

固定分塊隔行掃描算法是一種在圖像處理中比較經(jīng)典的算法，該算法首先對屏幕進行分塊處理，并對分塊進行編號?？紤]到分塊尺寸和分塊內(nèi)部變化像素點等因素，目前較為理想的劃分方案為16X8[9];接著要保存前后相鄰的bmp位圖數(shù)據(jù);最后對前后兩副位圖分別按照對應(yīng)的編號塊進行對比找出變化的數(shù)據(jù)塊。對比的方法是隔若干行(根據(jù)具體情況而定)對比前后兩幅圖像的一行中的像素點是否相同，若不同則壓縮發(fā)送當前塊中的圖像。由于是隔若干行對比一行，因此稱其為隔行掃描。為提高掃描的效率，需要設(shè)置一個掃描行數(shù)的閥值，如果從開始掃描就有連續(xù)的掃描行都相等，當這樣的行數(shù)達到該閥值時，就認為該塊沒有發(fā)生變化，并終止該塊的掃描，進行下一塊的掃描工作。

由于固定分塊隔行掃描算法對屏幕分塊的大小和數(shù)量固定，經(jīng)過掃描后得到變化的分塊，每次只壓縮發(fā)送這些分塊。當屏幕變化區(qū)域正好位于各個分塊的臨界點時，就會將其占用的所有分塊全部發(fā)送，這樣就發(fā)送了大量的冗余數(shù)據(jù)，造成不必要的帶寬占用，如圖1所示。

圖1 屏幕圖像變化矩形區(qū)域

從圖1可以看出，屏幕圖像在12個塊中都有變化區(qū)域，其大部分變化區(qū)域都位于6、7塊，2、3、5、8、10、11塊占有少部分變化區(qū)域，而1、4、9、12僅占有一點變化區(qū)域。固定隔行掃描算法在掃描如圖1這種屏幕圖像時，會認為這12個塊都是需要壓縮發(fā)送的數(shù)據(jù)。這樣就造成CPU使用率大，帶寬占用高。

2 動態(tài)分塊隔行掃描算法

動態(tài)隔行掃描算法不是將屏幕圖像分成固定大小和數(shù)量的分塊，而是首先比較相鄰兩幀圖像，找出所有圖像變化，然后根據(jù)變化像素點的坐標得到面積最小的不重疊矩形區(qū)域的集合，每次只發(fā)送矩形區(qū)域的集合包含的圖像數(shù)據(jù)，以減小每一幀的傳輸數(shù)據(jù)，達到有效降低傳輸帶寬占用率和CPU使用率的目的。

2.1 算法原理

算法的重點在于如何根據(jù)變化像素點的坐標得到變化矩形區(qū)域范圍。

式(1)和式(2)是根據(jù)變化像素點判斷矩形R范圍的算式。其中Rl和Rt代表矩形左上角的橫坐標和縱坐標，Rr和Rb代表矩形右下角的橫坐標和縱坐標，Px和Py代表變化像素點的橫坐標和縱坐標，Py0代表第一次變化像素點的縱坐標。按照2D圖形學的習慣，X軸水平向右遞增，Y軸水平向下遞增。根據(jù)式(1)和式(2)即可求變化矩形區(qū)域的范圍。

動態(tài)隔行掃描算法同樣先將前后相鄰兩幅位圖的數(shù)據(jù)保存，并隔行掃描比較兩幅圖像的像素點是否相同。當掃描到不同的像素點時，會將該像素點的坐標(Px0，Py0)進行記錄，作為變化矩形區(qū)域的左上角坐標(Rl，Rt)，并且將已掃描到不同的像素點狀態(tài)記為true。當再次掃描到不同像素點且掃描狀態(tài)為已掃描到不同像素點時，會將該像素點的橫坐標Px同矩形左上角的橫坐標Rl進行比較并取最小值，同時矩形右下角的坐標(Rr，Rb)和該點的坐標(Px，Py)比較并取最大值，并將行像素點不同狀態(tài)記為true。即:

當掃描完一行時，會先判斷行像素點不同狀態(tài)是否為true，若為true，表明該行已有像素點不同;若為false，則表明整行無不同像素點，此時退出循環(huán)，這樣就得到變化的矩形區(qū)域塊。下次隔行掃描的位置從該矩形塊的下方一行開始進行。動態(tài)隔行掃描算法的示意圖如圖2所示。

圖2 動態(tài)分塊隔行掃描示意圖

2.2 算法設(shè)計

動態(tài)分塊隔行掃描算法工作流程如下所述:以固定分塊的隔行掃描為基礎(chǔ)，掃描屏幕圖像的像素點，根據(jù)變化像素點的坐標動態(tài)確定需要發(fā)送的矩形塊。在隔行掃描有變化的像素點時，記錄該點坐標為矩形左上角坐標，然后繼續(xù)掃描，每次掃描都會將像素點的坐標和矩形右下角的坐標進行比較并取最大值，和矩形左上角橫坐標比較并取最小值。當掃描到無變化行時退出循環(huán)。算法流程如圖3所示。

首先獲得屏幕的寬度width和高度height，2個變量將作為行掃描變量iRow和列掃描變量i的范圍。列掃描變量i會根據(jù)隔行掃描變量iRow的步長掃描像素點，當掃描到不同的像素點時，先判斷是否第一次像素點不同變量IsFirstUnequal的值是否為true，如果為true，則將當前坐標(i，iRow)記錄為矩形區(qū)域的左上角坐標(left，top)，然后將IsFirstUnequal置為false。矩形的右下角坐標(right，bottom)也記為(i，iRow)，并將行坐標點不同變量IsLineChanged設(shè)為true。當再次掃描到不同的像素點時，將該點的坐標(i，iRow)與矩形的右下角坐標(right，bottom)進行比較，將較大的那個值作為矩形右下角的新坐標。同時還會將矩形左上角的橫坐標left同該點的橫坐標進行比較，并取較小的值作為矩形左上角橫坐標的新值。掃描完一行以后，先會判斷IsLineChanged的值，如果為true，即本行有不同的像素點時，將IsLineChanged修改為false，行掃描變量會根據(jù)隔行掃描的步長掃描下一行像素點。當掃描到一行無不同的像素點時，IsLineChanged的值必然為false，此時退出循環(huán)，即得到變化矩形區(qū)域的大小。由于行掃描變量和列掃描變量均為靜態(tài)變量，下一次調(diào)用函數(shù)時繼續(xù)從該行向下掃描。這樣每次掃描都會動態(tài)得到變化的矩形塊，每次僅壓縮傳輸這些變化塊。

圖3 動態(tài)隔行掃描算法流程圖

3 對比測試

為驗證動態(tài)分塊隔行掃描算法是對于固定分塊隔行掃描算法實際性能的提高以及數(shù)據(jù)傳輸?shù)墓?jié)省，設(shè)計了一個對比測試。

測試包括2個方面:一是測試兩種算法對系統(tǒng)CPU資源消耗的情況;二是測試2種算法對帶寬資源占用的情況。測試對2種算法中所做的文檔操作、網(wǎng)頁瀏覽操作、視頻操作分別每隔20秒采集一次CPU占用率和帶寬占用情況，持續(xù)5分鐘，并重復100次，最后取平均值作為其對比結(jié)果。測試環(huán)境選用2臺配置為Inter I7 3630qm四核CPU、6G內(nèi)存、分辨率為1920*1080的計算機。具體相關(guān)參數(shù)如表1所示。

表1 測試環(huán)境參數(shù)表

測試所有對比操作都在相同的環(huán)境下進行，相同的系統(tǒng)環(huán)境、相同的文檔操作、相同的網(wǎng)頁瀏覽內(nèi)容、相同的視頻瀏覽內(nèi)容的流程和步驟。

(1)CPU使用率對比

測試對比包括3種常見操作:文本操作、網(wǎng)頁瀏覽和播放視頻。

文本操作比較。圖4為固定分塊與動態(tài)分塊隔行掃描算法的文本操作比較情況，從圖中可以看到2種方法的文本操作的CPU占用率在6%～12%波動，并得出動態(tài)分塊隔行掃描操作消耗CPU資源情況較于固定分塊隔行掃描操作整體上低約25%。

網(wǎng)頁瀏覽操作比較。圖5為固定分塊與動態(tài)分塊隔行掃描算法的網(wǎng)頁瀏覽操作比較情況，從圖中可以看出，在第3分鐘時固定分塊隔行掃描算法的CPU占用率要低一點，因為此時屏幕圖像的變化區(qū)域正好位于某個或者幾個分塊中，但是整體上動態(tài)分塊隔行掃描算法CPU占用率比固定分塊隔行掃描算法低約12%。

圖4 文本操作比較

圖5 網(wǎng)頁瀏覽操作比較

視頻播放比較。圖6為固定分塊與動態(tài)分塊隔行掃描算法的文本操作比較情況，從圖中可以看出，由于視頻畫面的頻繁變換因此兩者對系統(tǒng)CPU資源的消耗比較接近，但是整體上，動態(tài)分塊隔行掃描算法在視頻操作CPU資源消耗上比固定分塊隔行掃描算法高約5%。這是由于當圖像變化區(qū)域數(shù)量超過一定數(shù)值的時候(200左右)，如果圖像變化區(qū)域都位于固定分塊隔行掃描算法的一個或幾個分塊中，固定隔行掃描算法僅需掃描比較這幾個分塊。而動態(tài)隔行掃描算法對每個變化區(qū)域都要進行掃描和比較，這樣大量占用CPU資源。所以在視頻播放時(特別是運動畫面)，動態(tài)分塊隔行掃描算法并不能很好地降低CPU資源消耗。

(2)帶寬占用

圖6 視頻操作比較

文本操作比較。圖7為文本操作的情況下各自占用的帶寬情況，從圖中可以看出，文本操作屏幕圖像的變化較少，需要壓縮和發(fā)送的數(shù)據(jù)量也較少，2種算法占用帶寬都不高。在1～2分鐘前，有個最低值，因為該時間點屏幕幾乎無變化塊，所以發(fā)送數(shù)據(jù)量處于最小值。從總體上看，動態(tài)分塊隔行掃描算法占帶寬比固定分塊隔行掃描算法低約4%。

網(wǎng)頁瀏覽操作比較。圖8為網(wǎng)頁操作的情況下各自占用的帶寬情況，從圖中可以看出網(wǎng)頁操作屏幕圖像的變化也較少，僅需要壓縮和發(fā)送變化的區(qū)域。整體上，動態(tài)隔行掃描算法占用的帶寬比固定隔行掃描算法低約10%。

圖7 文本操作比較

視頻操作比較。圖9為視頻操作的情況下各自占用的帶寬情況，從圖中可以看出，固定分塊隔行掃描算法的帶寬占用情況波動較大，而動態(tài)分塊隔行掃描算法波動較小。1～3分鐘，固定分塊隔行掃描算法的帶寬占用明顯低于動態(tài)分塊隔行掃描算法。而從整體上來看，在視頻操作時，動態(tài)隔行掃描算法的帶寬占用率甚至高于固定分塊隔行掃描算法約7%。這是由于動態(tài)隔行掃描算法的數(shù)據(jù)傳輸量隨著圖像變化區(qū)域數(shù)量的增加不斷增大，由于其發(fā)送到矩形變化區(qū)域還包含額外的未發(fā)生變化圖像數(shù)據(jù)，所以當圖像變化區(qū)域數(shù)量超過一定數(shù)值的時候(200左右)，每幀傳輸?shù)臄?shù)據(jù)總量超過固定分塊隔行掃描算法的傳輸?shù)臄?shù)據(jù)總量。所以在視頻操作時(特別是運動畫面)，動態(tài)分塊隔行掃描算法并不能很好降低數(shù)據(jù)傳輸量。

圖8 網(wǎng)頁瀏覽操作比較

圖9 視頻操作比較

4 結(jié)束語

動態(tài)分塊隔行掃描算法利用矩形結(jié)構(gòu)存儲圖像的變化區(qū)域，用點坐標結(jié)構(gòu)存儲矩形中的變化分塊，使動態(tài)分塊隔行掃描算法無論在系統(tǒng)性能，還是在帶寬占用方面都有優(yōu)勢。實驗結(jié)果表明，動態(tài)分塊隔行掃描算法在圖像變化較小，且變化多集中在某一處或者某幾處的應(yīng)用場景下，相比傳統(tǒng)的固定分塊隔行掃描算法更能有效地降低CPU使用率，減少帶寬占用率，提高傳輸?shù)男阅?。該算法也有一定的局限性，當圖像出現(xiàn)大量變化對象的時候(如播放視頻)，該算法并不能很好提升性能和降低數(shù)據(jù)傳輸量，甚至有可能適得其反。因此，如果能根據(jù)實際情況選擇使用該算法，將有效提高圖像傳輸性能和降低帶寬占用率。

[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].計算機工程應(yīng)用，2005，(1):114－116.

[4] 李芳.屏幕共享中截屏技術(shù)的研究與實現(xiàn)[J].湖南冶金職業(yè)技術(shù)學院學報，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].計算機應(yīng)用，2007，27(3):704－705.

[7] 劉德勝.基于矩形分割的局部渲染技術(shù)在無線圖像通信中的應(yīng)用[J].成都信息工程學院學報，2012，27(4):355－358.

[8] 左強翔，吳潔.一種基于分塊采集和壓縮技術(shù)的屏幕共享方案[J].計算機技術(shù)與發(fā)展，2008，18(4):207－209.

[9] 羅紅，蔡德俊.桌面圖形圖像序列壓縮與傳輸研究[J].計算機應(yīng)用，2005，25(6):1330－1304.

[10] 張紅祥，車鵬飛.屏幕圖像實時傳輸方法研究及一種改進實現(xiàn)[J].科技信息，2009，(33):821－824.

[11] 徐向陽，曹幫琴.差異截圖法實現(xiàn)屏幕圖像快速傳輸[J].南陽師范學院學報，2007，6(9):63－65.

[12] 朱東輝.基于WinSock通信的遠程屏幕抓取方法與實現(xiàn)[J].計算機應(yīng)用研究，2005，(8):204－206.

[13] 吳棟淦.兩種屏幕圖像捕獲方案的比較[J].計算機技術(shù)應(yīng)用，2007，(3):9－11.

[14] 肖道舉，劉洪峰，陳曉蘇.面向遠端屏幕監(jiān)控的一種圖像壓縮傳輸方法[J].計算機工程與設(shè)計，2005，26(12):3356－3364.

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