基于分形思想的差值圖像壓縮技術

摘要:針對屏幕監(jiān)控系統(tǒng)中數據傳輸的特殊性，提出基于分形思想的差值圖像壓縮技術#65377;圖像分形后，對相鄰幀間對應的數據求差并進行壓縮編碼，減少時間與空間冗余度#65377;試驗表明，該方法能有效降低傳輸時的數據量，節(jié)約傳輸時間，同時是一種無損的壓縮算法#65377;

關鍵詞:圖像壓縮; 冗余度; 游程編碼; 分形

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001-3695(2007)04-0190-02

0引言

信息論之父C.E.Shannon在其1948年發(fā)表的論文《A Mathematical Theory of Communication》中指出，任何信息都存在冗余#65377;冗余大小與信息中每個符號(數字#65380;字母或單詞)的出現頻率有關#65377;一個符號出現的頻率越小，其信息量也就越小#65377;對于離散無記憶信源的第i個事件的信息量，可以將其定義為 I=-log Pi(Pi為第i個事件的概率)#65377;如果將信息中所有可能的信息量進行平均，就得到信息的熵#65377;對于離散的無記憶信源，熵為H=-∑Pi log Pi#65377;信源經常由于事件相關或概率分布不均勻等原因，使得實際的熵小于其最大熵，這樣就產生信息的冗余#65377;冗余度定義為R=1-H(x)/Hmax(x)#65377;信息熵及相關的定理用數學手段精確地描述了信息冗余的程度#65377;從本質上講，數據壓縮的目的就是消除信息中的冗余#65377;

數據壓縮分為熵壓縮與冗余度壓縮#65377;熵壓縮是信源平均信息量的壓縮，這將導致信息的減少，是一種有損壓縮，如JPEG#65380;MPEG壓縮等#65377;冗余度壓縮就是除去數據中的冗余，對信息無任何破壞，是無損的壓縮#65377;典型算法有游程編碼#65380;LZ系列編碼#65380;Huffman編碼#65377;這些算法基本解決了通用數據壓縮中兼顧壓縮速度與壓縮效果的難題#65377;但是，C.E.Shannon在信息論中還提出，對信息的先驗知識了解得越多，就可以把信息壓縮得越小#65377;換句話說，如果壓縮算法的設計目標不是任意的數據源，而是基本屬性已知的特種數據，壓縮的效果可能會進一步提高#65377;因此在發(fā)展通用壓縮算法之余，還必須研究針對各種特殊數據的專用壓縮算法#65377;

1分形的差值壓縮算法

本文研究的內容來源于特殊環(huán)境下電腦屏幕監(jiān)控軟件的實現#65377;在點陣圖像中，點組成線#65380;線組成面#65377;因此可將一幅圖像看成是由許多個點組成的#65377;組成圖像的一個點就是一個像素，它是構成圖像的最小單位，其形態(tài)是一個小方點#65377;彩色圖像的像素是由紅#65380;綠#65380;藍(RGB)三種顏色組成，每種顏色由一個字節(jié)來表示其深度#65377;因此，假設屏幕的分辨率是1 024×768，一幅彩色屏幕圖像正常的大小是1 024×768×3=2 359 296=2.25 MB#65377;如果監(jiān)控系統(tǒng)要求每兩秒刷新一次，也就是指定的傳輸量需要大于或等于1.125 Mbps#65377;這對網絡將是巨大的考驗#65377;如果當前網絡連接情況不好，傳輸量一旦小于1.125 Mbps，將達不到實時監(jiān)控的目的#65377;因此，采用壓縮算法是必要的#65377;另外，此系統(tǒng)有兩個特點:①電腦屏幕圖像經常出現連續(xù)像素點相同的區(qū)域;②在較短時間內，屏幕畫面往往只有部分區(qū)域像素點發(fā)生變化#65377;根據這些先驗知識，本文提出了基于分形思想的差值壓縮技術(Difference Image Compression Technology Based on Fractal，DICTF)#65377;這是一種專用的壓縮算法，特別適用于連續(xù)的圖像傳輸系統(tǒng)#65377;

1.1差值編碼

圖像序列中兩幅相鄰的圖像有較大的相關性，反映為時間冗余#65377;其表現是屏幕畫面中相繼各幀對應像素點的值往往相近或相同，即前后幀間相應位置像素之差很小甚至為零#65377;或者說差值小的概率大;而差值大的概率小，具有時間相關性#65377;從這個方面講，差值反映了相鄰幀間的所有差異信息#65377;因此，如果發(fā)送端將同一位置的當前像素值與前一像素值相減所得差值經量化后進行傳輸，接收端將收到的差值與前一個像素值相加，也能得到當前像素值，這就是差值編碼的基本想法#65377;其原理圖如圖1所示#65377;

其中，參考圖像(Reference Image)指前面已經傳輸的圖像，用數組ref_img[k][l]表示;目標圖像(Target Image)指當前要傳輸的圖像，用數組tar_img[k][l]表示#65377;其中k#65380;l的取值范圍取決于圖像的分辨率#65377;Data′[k][l]表示一幅由tar_img與ref_img產生的差值圖像#65377;設圖像分辨率為K×L，則

只用到幀內像素的處理稱為幀編碼，用到前后幀像素的處理稱為幀間編碼#65377;要得到較大的壓縮率，就必須使用幀間編碼#65377;一般來說，電腦屏幕圖像是由面積較大的像素塊組成的#65377;每個像素塊的像素值不一定相同，但是一個像素塊內部各點的像素值是一樣的#65377;像素值躍變的部分對應像素塊的輪廓，只占圖像很小的一部分#65377;因此，幀間對應位置像素值相同的概率很大，靜止圖像相鄰幀間對應位置的像素值更是相等#65377;這種情況下，經過幀間差值編碼，所得結果Data′[k][l]必然小于tar_img[k][l]，甚至有大部分為0#65377;與原始數據相比，降低了數據的復雜度，同時也為后面進行進一步的壓縮打好了基礎#65377;

1.2壓縮差值碼

求差運算降低了數據的復雜度，但是并沒有降低數據量的多少#65377;本文傳輸的數據量仍然是1 024×768×3=2.25 MB，但是與原始的數據量相比，結果中含有大量的0以及大面積的差值相等區(qū)域#65377;這時可以通過常用的壓縮算法對差值碼進行進一步的壓縮#65377;

游程編碼是一種利用空間冗余度壓縮圖像的方法#65377;設圖像中的某一行或者某一像素塊經采用或經某種方法變換后的系數為(x1，x2，…，xn)#65377;某一行或某一塊內像素值可分為k段，長度為Ii的連續(xù)串，每個串具有相同的值#65377;那么，該圖的某一行或某一列可由下面偶對(gi，Ii)(I≤i≤k)來表示:

其中，gi為每個串內像素值，Ii為串的長度，串長Ii就是游程(RunLength)，即由字符或采樣值或灰度值構成的數據流中的各個字符等重復出現而形成的字符串長度#65377;如果給出了形成串的字符串的長度及串的位置，就能很容易地恢復出原來的數據流#65377;假定有一幅灰度圖像，第n行的像素值如下:

用一對符號格式表示一個長度顏色值:(顏色值 |長度)#65377;這里暫不考慮如何區(qū)分每一對符號，即顏色值和長度值#65377;用游程編碼方法得到的代碼是:0|4，1|5，7|30，4|20，3|3，0|5#65377;如果直接傳輸每個像素的顏色值，傳輸的數據量是4+5+30+20+3+5=67 Bytes#65377;采用游程編碼，傳輸的是數據對，現在的傳輸量是6×2=12 Bytes，顯然得到了壓縮#65377;此外，可以按不同顏色出現的概率，分配以不同碼長的碼字:大概率以短碼;小概率以長碼#65377;譯碼時，按照與編碼時采用的相同規(guī)則進行，還原后得到的數據與壓縮前的數據完全相同#65377;

此外，游程算法實現簡單，對原始數據進行一次掃描就可以了，壓縮與還原速度快，是效率最高的編碼方式，適合圖像監(jiān)控領域對時間的要求#65377;對于存在大面積顏色相同區(qū)域，采用游程編碼的壓縮率也是很高的#65377;上述求差運算的結果有大量的0，此時再用游程編碼對差值進行壓縮，將得到更高的壓縮率#65377;因此，從時間和效率兩個因素考慮，本文采用游程編碼來壓縮相鄰幀間的差值#65377; 

1.3分形化思想

實際過程中，屏幕可能只有小部分區(qū)域發(fā)生了變化#65377;假設求差后發(fā)現只有某區(qū)域發(fā)生變化，只需要對相應區(qū)域數據進行游程編碼，而不需要對整個屏幕的數據進行游程編碼#65377;由于信源信息減少，必然降低游程編碼的運算時間#65377;這類似于目前圖像壓縮的新技術——分形化思想#65377;但分形化算法復雜，運行時間長，不利于實時的屏幕監(jiān)控，因此只借鑒了其第一步思路:將圖像劃分成任意形狀#65380;大小相等且互不重疊的塊#65377;

采取分形化的方法，把屏幕劃分成M×N個規(guī)則的網格(Grid)#65377;對于M#65380;N的取值值得討論:太小，每個區(qū)域內有變化的概率就大，算法效果不明顯;太大，需要比較的次數就多了，游程編碼壓縮的次數也多了，同樣影響效率#65377;在經過多次嘗試后發(fā)現，4×8的劃分相對合適#65377;圖2給出了一個4×8劃分網格的方法#65377;其中每個虛線格子就是一個網格，總共32個網格#65377;

圖2中，假設某相鄰兩次屏幕數據只在第18號網格內有所變化，只需對18號網格內的數據進行求差與游程編碼，然后向接收端發(fā)送結果#65377;此時，發(fā)送的不再是整個屏幕的數據，而是每個發(fā)生變化的網格數據#65377;為了讓接收端能正確判斷接收到的數據來自哪個網格，定義了一個新的結構體來表示每個網格#65377;

其中，NO是網格編號，范圍為0~31;INFO[MAX_LENGTH]是相應網格求差并采用游程編碼后的數據#65377;接收端先提取NO值判斷傳來的是幾號網格的數據;然后對具體數據進行解碼并與參考圖像相加得到指定網格數據;最后將此數據映射到目標圖像的指定網格區(qū)域#65377;該方法使得接收端只需重繪發(fā)生變化的網格區(qū)域，既減少了傳輸的數據量，也降低了繪制圖像的時間#65377;

2測試結果

在局域網環(huán)境中對上述算法進行了測試，兩臺主機的網卡是Marvell Yukon Gigabit Ethernet 100/1000BaseT Adapter#65377;屏幕分辨率為1 024×768，在不采用壓縮算法的情況下，每次傳送數據是2.25 MB，傳輸時間是1.468 s#65377;采用分形差值壓縮算法，屏幕劃分為32個網格，屏幕發(fā)生變化時傳輸數據量與時間如表1所示(數據量單位是Byte，時間單位是s)#65377;

(上接第191頁)

這里首先要指出的是，游程編碼的壓縮率與圖像內容密切相關#65377;當存在大面積相同區(qū)域時，效果才是最好#65377;因此，有時變化的網格數多，卻可能出現壓縮后數據量卻比較小的情況#65377;表1中的數據是多次測試的平均值#65377;一般情況下，屏幕一次變化的網格數在3~20之間.從表1可以看出，這個范圍內每次傳輸的數據量約在6~200 KB之間，遠小于不壓縮情況下的2.25 MB#65377;時間上整個壓縮與傳輸過程小于1 s，完全符合屏幕監(jiān)控系統(tǒng)2 s更新一次的要求#65377;

表1傳輸數據量與時間測試

3總結

傳統(tǒng)的壓縮算法是通用的，不考慮特殊環(huán)境#65377;例如游程算法在壓縮圖像時有很高的壓縮率，但是壓縮文件時卻會出現膨脹現象，因為文件中很少有某個文字連續(xù)出現，所以針對特殊環(huán)境采用專用的壓縮算法具有實際的意義#65377;本文針對電腦屏幕監(jiān)控系統(tǒng)的特點提出基于分形思想的差值圖像壓縮算法，根據實際測試結果，傳輸數據量與傳輸時間大幅度降低，提高了系統(tǒng)的性能#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。