七方向差分鏈碼的視頻對象形狀編碼

王燕妮,樊養余

(1.西安建筑科技大學信息與控制工程學院,西安 710055;2.西北工業大學電子信息學院,西安 710072)

1 引 言

視頻對象形狀編碼是基于內容的視頻編碼特有的,有對象就有形狀,而基于鏈碼的形狀壓縮是視頻傳輸中的重要環節,也體現了形狀編碼的重要性。目前的形狀編碼有四方向鏈碼和八方向鏈碼[1],主要由形狀和位置編碼組成,形狀邊界處有斷開或錯誤劃分情況,這樣將導致圖像編碼質量下降。因此,本文在對視頻圖像進行區域生長[2-3]分割的基礎上,為了提高對象形狀邊界的精確性,提出七方向差分鏈碼的輪廓形狀編碼,預測達到滿意的恢復圖像質量和很高的壓縮比。

2 常規輪廓形狀鏈碼

鏈碼用于表示圖像的邊界線,一般由順次連接的具有有限長度和方向的直線段組成。線段的方向用四方向鏈碼和八方向鏈碼表示,如圖1所示。

鏈碼是對圖形邊界按順時針方向每對像素的連接線段賦予一個方向而生成的。對于任意的圖像形狀輪廓,以圖形下部中點為出發點,可編出四方向鏈碼和八方向鏈碼。從鏈碼生成可知,邊界線必須是連續的,不能斷開和缺口,也不能噪聲太多,使得在一個點周圍有多個點,難以確定連接線段的方向。為此,在原圖像中選擇比像素間隔大的網格而對邊界進行重新取樣,產生近似處理,近似精度取決于網格的大小,這樣就可以消除原圖像邊界點和噪聲點的影響。

圖1 兩種常規鏈碼Fig.1 Two conventional chain codes

編碼[4-5]的目標是被編碼的結構信息最小化。對于四方向Freeman鏈碼(4F),有4個碼值,需要2位二進制位對其進行編碼,碼長為2。八方向Freeman鏈碼(8F),有8個碼值,需要3位二進制位對其進行編碼,碼長為3。可以看到,每個小直線段表示每個碼的移動,而碼字的編碼是根據鏈碼中的一個碼與其前一個碼前進方向之間的角度差。在表示對象形狀曲線或邊界時,其中每個碼與其后一個碼的碼值通常是相同的或是相鄰的,或者說在鏈碼中,一個碼所表示的方向與其前一個碼的方向相同或相近情況出現的概率大大高于兩者之間方向變化很大的情況。因此,提出新的七方向差分鏈碼(Seven Differential Chain,SDC),每個碼值被定義來表示該碼與其前一個碼之間的方向變化角度值。

3 七方向差分鏈碼的視頻對象輪廓形狀編碼

3.1 七方向差分鏈碼

七方向差分鏈碼編碼方法可以用較短的鏈碼表示區域的邊界,縮短鏈碼表示法的鏈碼長度,減少視頻圖像信息的存儲量。用鏈碼表示一個圖像邊界時,定義7個碼值表示鏈碼的7個前進方向,對其方向定義如圖2所示,以逆時針方向旋轉,上半部分采用45°角5個方向,下半部分采用60°角2個方向的小直線段表示每個碼的移動,通過統計各種應用中的1500多條數字曲線或區域邊界中前后碼元素間的方向變化的各種角度差值的出現概率。統計結果表明,大部分區域邊界編碼的碼值是相同或相鄰的,或者說在鏈碼中一個碼所表示的方向與其前一個碼的方向相同或相近情況的概率大大高于兩者之間方向變化很大的情況。因此,七方向新鏈碼中的7個小直線段被定義來表示一個碼與其前一個碼前進方向之間的角度差。

圖2 七方向差分鏈碼Fig.2 Seven differential chain

將七方向差分鏈碼中前后碼元素間的方向變化的各種角度差值,對可能出現的概率進行了統計,如表1所示。

表1 各種角度差值出現的概率Table 1 The probability of value in angle difference

當存儲視頻圖像區域或數字曲線的信息時,則可根據上述概率對邊界的每一個像素進行編碼,形成鏈碼來表示和存儲信息。

3.2 七方向差分鏈碼編碼

霍夫曼編碼是一種可變字長編碼方式,是由David.A.Huffman發展起來的。它是根據每一個源字符出現的估算概率而建立起來的,出現概率高的字符使用較短的編碼,反之出現概率低的則使用較長的編碼,這便使編碼之后的字符串的平均期望長度降低,從而達到無損壓縮數據的目的。例如,在英文中,“e”的出現概率很高,而“z”的出現概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時,“e”則用一個位(bit)來表示,而“z”則可能花去25個位。用普通的表示方法時,每個英文字母均占用一個字節(byte),即8個位。兩者相比,“e”使用了一般編碼的1/8的長度,“z”則使用了3倍多。倘若我們能實現對于英文中各個字母出現概率的較準確估算,就可以大幅度提高無損壓縮的比例。

霍夫曼編碼算法步驟如下:

(1)首先統計信源中各符號出現的概率,按符號出現的概率從大到小排序;

(2)把最小的兩個概率相加合并成新的概率,與剩余的概率組成新的概率集合;

(3)對新的概率集合重新排序,再次把其中最小的兩個概率相加,組成新的概率集合。如此重復進行,直到最后兩個概率的和為l;

(4)分配碼字:碼字分配從最后一步開始反向進行,對于每次相加的兩個概率,給大的賦“1”,小的賦“0”(也可以全部相反,如果兩個概率相等,則從中任選一個賦“0”,另一個賦“1”即可),讀出時由該符號開始一直走到最后的概率和“1”,將路線上所遇到的“0”和“1”按最低位到最高位的順序排好,就是該符號的霍夫曼編碼。

以七方向差分鏈碼的7個碼值符號和其概率作為輸入,用霍夫曼編碼方法對其編碼,可得到具體的編碼過程如圖3所示。

圖3 新鏈碼編碼過程Fig.3 The process of new chain coding

碼值如下:

根據信息論理論,該編碼的平均碼長(bit)為

式中,li表示第i個碼值的編碼長度,pi表示其出現的概率大小。則該編碼的信源熵(bit)為

該編碼的效率為

3.3 區域填充

區域填充算法是將指定不規則區域內部像素填充為填充色的過程,在計算機輔助設計和圖像處理等領域有廣泛應用,包括種子填充(Seed Filling)算法、掃描線填充(Scan-Line Filling)算法等。種子填充算法又稱為邊界填充算法,其基本思想是:從多邊形區域的一個內點開始,由內向外用給定的顏色畫點直到邊界為止。如果邊界是以一種顏色指定的,則種子填充算法可逐個像素地處理直到遇到邊界顏色為止。該算法優點是非常簡單,缺點是需要大量棧空間來存儲相鄰的點。

為了減少遞歸次數、提高效率,在此采用掃描線算法,即通過沿掃描線填充水平像素段,來處理四連通或八連通相鄰點,這樣就僅僅只需要將每個水平像素段的起始位置壓入棧,而不需要將當前位置周圍尚未處理的相鄰像素都壓入棧,從而可以節省大量的棧空間。

掃描線填色算法,其基本思想是:用水平掃描線從上到下掃描由點線段構成的多邊形。每根掃描線與多邊形各邊產生一系列交點。將這些交點按照橫坐標進行分類,將分類后的交點成對取出,作為兩個端點,以所填的色彩畫水平直線。多邊形被掃描完畢后,填色也就完成。

SDC算法流程如圖4所示。

圖4 SDC算法流程圖Fig.4 The flow chart of SDC algorithm

3.4 各種鏈碼間的比較

對于平均碼長,4F鏈碼和8F鏈碼采用固定長度編碼,其4個碼值和8個碼值分別使用2位和3位二進制數進行編碼,碼長為2和3;而七方向差分鏈碼編碼的平均碼長為每碼2.203位。對于鏈碼總位數,是平均碼長乘以鏈碼的長度,則以上3種鏈碼的總位數如表2所示。

表2 鏈碼所需位數比較Table 2 The comparison of required chain code number

4 仿真實驗

采用區域生長法對視頻圖像進行對象分割,在此基礎上,用SDC編碼跟蹤視頻對象邊緣進行壓縮編碼并進行區域填充。

4.1 實驗1:重建幀的比較

采用missamerica(360×288)序列,以第一幀作為參考幀,進行視頻分割后,再對其對象輪廓進行七方向差分鏈碼編碼,分別用4F、8F和SDC得到第二幀的重建幀,結果如圖5所示。可看出,八方向Freeman鏈碼和七方向差分鏈碼編碼重建的視頻圖像非常接近視頻圖像的原始幀。

圖5 重建幀的比較Fig.5 The comparison of reconstruction frame

4.2 實驗2:誤差幀的比較

采用代表運動劇烈的susie(352×240)序列的第十幀作為參考幀,進行視頻分割,再對其對象輪廓進行七方向差分鏈碼編碼。分別用4F、8F和SDC得到第十一幀的誤差幀,結果如圖6所示。

圖6 誤差幀的比較Fig.6 The comparison ofmsE

4.3 實驗3:性能的比較

采用football(352×240)序列,以第五幀作為參考幀,分別用4F、8F和SDC算法恢復下一幀,依次傳輸10幀視頻圖像,得到誤差MSE和相應的峰值信噪比(PSNR),結果如圖7所示。

4.4 實驗4:搜索時間的比較

選取視頻序列forman(352×288)的第五幀作為測試幀,對于4F、8F和SDC算法,分別得到第六幀的恢復幀。壓縮編碼的時間如表3所示。

表3 各種算法的壓縮編碼時間Table 3 The time of compression coding

圖7 各種算法的性能比較Fig.7 The performance comparison of different algorithms

在實驗1中,對于missamerica序列,以第一幀作為參考幀,進行對象分割后,分別用4F、8F和SDC算法得到第二幀的重建幀。可以看出,SDC算法總體上優于其它兩種算法,只是在一些個別的區域劣于8F算法。在實驗2中,采用susie序列對恢復圖像的誤差幀進行比較。可以看出,4F算法的誤差最大,8F和SDC算法的誤差相差不大,但8F算法的誤差略低于SDC算法。在實驗3中,采用football序列對恢復圖像的性能進行比較。可以看出,在傳輸幀數較多的情況下,SDC算法的性能均優于其它兩種算法,其中PSNR比8F算法提高了1.2dB。在實驗4中,用4F、8F和SDC算法進行形狀壓縮編碼,比較可得4F算法的編碼時間最短,但SDC算法比8F算法的運行時間減少了2.1ms。綜合以上實驗結果,考慮到算法運行時間和恢復圖像質量之間的矛盾關系,選取SDC算法,在獲得較清晰圖像的前提下,可實時地傳輸視頻。

5 結 論

通過研究常規輪廓鏈碼編碼,根據對象形狀曲線或邊界上每個碼與其相鄰碼的碼值通常是相同的或是相鄰的這一特征,提出基于對象分割的七方向差分鏈碼的形狀壓縮編碼,使用前后碼元素間的方向變化的角度差值作為鏈碼值,這樣碼值則集中在其中幾個碼元上,編碼時需要的碼長較短。從實驗結果可知,七方向差分鏈碼編碼算法的峰值信噪比及運行時間都優于幾種經典的鏈碼編碼,在實時視頻通信中編碼效果優良。

[1] 賀貴明,吳元保,蔡朝暉,等.基于內容的視頻編碼與傳輸控制技術[M].武漢:武漢大學出版社,2005.HE Gui-ming,WU Yuan-bao,CAI Zhao-hui,et al.Content based video coding and transmission control technology[M].Wuhan:Wuhan University Press,2005.(in Chinese)

[2] FAN J P,YAU D K Y.Automatic image segmentation by integrating color-edge extraction and seeded regiong rowing[J].IEEE Transactions on Image Processing,2001,10(10):1454-1466.

[3] FRANK Y SHIH,CHENG Shouxian.Automatic seeded region growing for color image segmentation[J].Image and Vision Computing,2005(23):877-886.

[4] 丁學君,田勇.一種利用SA-DWT的任意形狀ROI編碼方法[J].電訊技術,2006,46(6):150-153.DING Xue-jun,TIAN Yong.An Arbitrary Shape ROI Coding Method with SA-DWT[J].Telecommunication Engineering,2006,46(6):150-153.(in Chinese)

[5] 申杰,鄭小玉,朱維樂.降低頭肩視頻序列編碼碼率的一種新方法[J].電訊技術,2005,45(5):18-22.SHEN Jie,ZHENG Xiao-yu,ZHU Wei-le.A New Method for Reducing Bit-Rate in Head and Shoulder Video Sequences[J].Telecommunication Engineering,2005,45(5):18-22.(in Chinese)