七方向差分鏈碼的視頻對(duì)象形狀編碼

王燕妮,樊養(yǎng)余

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

1 引 言

視頻對(duì)象形狀編碼是基于內(nèi)容的視頻編碼特有的,有對(duì)象就有形狀,而基于鏈碼的形狀壓縮是視頻傳輸中的重要環(huán)節(jié),也體現(xiàn)了形狀編碼的重要性。目前的形狀編碼有四方向鏈碼和八方向鏈碼[1],主要由形狀和位置編碼組成,形狀邊界處有斷開(kāi)或錯(cuò)誤劃分情況,這樣將導(dǎo)致圖像編碼質(zhì)量下降。因此,本文在對(duì)視頻圖像進(jìn)行區(qū)域生長(zhǎng)[2-3]分割的基礎(chǔ)上,為了提高對(duì)象形狀邊界的精確性,提出七方向差分鏈碼的輪廓形狀編碼,預(yù)測(cè)達(dá)到滿意的恢復(fù)圖像質(zhì)量和很高的壓縮比。

2 常規(guī)輪廓形狀鏈碼

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

鏈碼是對(duì)圖形邊界按順時(shí)針?lè)较蛎繉?duì)像素的連接線段賦予一個(gè)方向而生成的。對(duì)于任意的圖像形狀輪廓,以圖形下部中點(diǎn)為出發(fā)點(diǎn),可編出四方向鏈碼和八方向鏈碼。從鏈碼生成可知,邊界線必須是連續(xù)的,不能斷開(kāi)和缺口,也不能噪聲太多,使得在一個(gè)點(diǎn)周圍有多個(gè)點(diǎn),難以確定連接線段的方向。為此,在原圖像中選擇比像素間隔大的網(wǎng)格而對(duì)邊界進(jìn)行重新取樣,產(chǎn)生近似處理,近似精度取決于網(wǎng)格的大小,這樣就可以消除原圖像邊界點(diǎn)和噪聲點(diǎn)的影響。

圖1 兩種常規(guī)鏈碼Fig.1 Two conventional chain codes

編碼[4-5]的目標(biāo)是被編碼的結(jié)構(gòu)信息最小化。對(duì)于四方向Freeman鏈碼(4F),有4個(gè)碼值,需要2位二進(jìn)制位對(duì)其進(jìn)行編碼,碼長(zhǎng)為2。八方向Freeman鏈碼(8F),有8個(gè)碼值,需要3位二進(jìn)制位對(duì)其進(jìn)行編碼,碼長(zhǎng)為3?？梢钥吹?每個(gè)小直線段表示每個(gè)碼的移動(dòng),而碼字的編碼是根據(jù)鏈碼中的一個(gè)碼與其前一個(gè)碼前進(jìn)方向之間的角度差。在表示對(duì)象形狀曲線或邊界時(shí),其中每個(gè)碼與其后一個(gè)碼的碼值通常是相同的或是相鄰的,或者說(shuō)在鏈碼中,一個(gè)碼所表示的方向與其前一個(gè)碼的方向相同或相近情況出現(xiàn)的概率大大高于兩者之間方向變化很大的情況。因此,提出新的七方向差分鏈碼(Seven Differential Chain,SDC),每個(gè)碼值被定義來(lái)表示該碼與其前一個(gè)碼之間的方向變化角度值。

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

3.1 七方向差分鏈碼

七方向差分鏈碼編碼方法可以用較短的鏈碼表示區(qū)域的邊界,縮短鏈碼表示法的鏈碼長(zhǎng)度,減少視頻圖像信息的存儲(chǔ)量。用鏈碼表示一個(gè)圖像邊界時(shí),定義7個(gè)碼值表示鏈碼的7個(gè)前進(jìn)方向,對(duì)其方向定義如圖2所示,以逆時(shí)針?lè)较蛐D(zhuǎn),上半部分采用45°角5個(gè)方向,下半部分采用60°角2個(gè)方向的小直線段表示每個(gè)碼的移動(dòng),通過(guò)統(tǒng)計(jì)各種應(yīng)用中的1500多條數(shù)字曲線或區(qū)域邊界中前后碼元素間的方向變化的各種角度差值的出現(xiàn)概率。統(tǒng)計(jì)結(jié)果表明,大部分區(qū)域邊界編碼的碼值是相同或相鄰的,或者說(shuō)在鏈碼中一個(gè)碼所表示的方向與其前一個(gè)碼的方向相同或相近情況的概率大大高于兩者之間方向變化很大的情況。因此,七方向新鏈碼中的7個(gè)小直線段被定義來(lái)表示一個(gè)碼與其前一個(gè)碼前進(jìn)方向之間的角度差。

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

將七方向差分鏈碼中前后碼元素間的方向變化的各種角度差值,對(duì)可能出現(xiàn)的概率進(jìn)行了統(tǒng)計(jì),如表1所示。

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

當(dāng)存儲(chǔ)視頻圖像區(qū)域或數(shù)字曲線的信息時(shí),則可根據(jù)上述概率對(duì)邊界的每一個(gè)像素進(jìn)行編碼,形成鏈碼來(lái)表示和存儲(chǔ)信息。

3.2 七方向差分鏈碼編碼

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

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

(1)首先統(tǒng)計(jì)信源中各符號(hào)出現(xiàn)的概率,按符號(hào)出現(xiàn)的概率從大到小排序;

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

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

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

以七方向差分鏈碼的7個(gè)碼值符號(hào)和其概率作為輸入,用霍夫曼編碼方法對(duì)其編碼,可得到具體的編碼過(guò)程如圖3所示。

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

碼值如下:

根據(jù)信息論理論,該編碼的平均碼長(zhǎng)(bit)為

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

該編碼的效率為

3.3 區(qū)域填充

區(qū)域填充算法是將指定不規(guī)則區(qū)域內(nèi)部像素填充為填充色的過(guò)程,在計(jì)算機(jī)輔助設(shè)計(jì)和圖像處理等領(lǐng)域有廣泛應(yīng)用,包括種子填充(Seed Filling)算法、掃描線填充(Scan-Line Filling)算法等。種子填充算法又稱為邊界填充算法,其基本思想是:從多邊形區(qū)域的一個(gè)內(nèi)點(diǎn)開(kāi)始,由內(nèi)向外用給定的顏色畫點(diǎn)直到邊界為止。如果邊界是以一種顏色指定的,則種子填充算法可逐個(gè)像素地處理直到遇到邊界顏色為止。該算法優(yōu)點(diǎn)是非常簡(jiǎn)單,缺點(diǎn)是需要大量?？臻g來(lái)存儲(chǔ)相鄰的點(diǎn)。

為了減少遞歸次數(shù)、提高效率,在此采用掃描線算法,即通過(guò)沿掃描線填充水平像素段,來(lái)處理四連通或八連通相鄰點(diǎn),這樣就僅僅只需要將每個(gè)水平像素段的起始位置壓入棧,而不需要將當(dāng)前位置周圍尚未處理的相鄰像素都?jí)喝霔?從而可以節(jié)省大量的棧空間。

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

SDC算法流程如圖4所示。

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

3.4 各種鏈碼間的比較

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

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

4 仿真實(shí)驗(yàn)

采用區(qū)域生長(zhǎng)法對(duì)視頻圖像進(jìn)行對(duì)象分割,在此基礎(chǔ)上,用SDC編碼跟蹤視頻對(duì)象邊緣進(jìn)行壓縮編碼并進(jìn)行區(qū)域填充。

4.1 實(shí)驗(yàn)1:重建幀的比較

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

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

4.2 實(shí)驗(yàn)2:誤差幀的比較

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

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

4.3 實(shí)驗(yàn)3:性能的比較

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

4.4 實(shí)驗(yàn)4:搜索時(shí)間的比較

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

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

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

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

5 結(jié) 論

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

[1] 賀貴明,吳元保,蔡朝暉,等.基于內(nèi)容的視頻編碼與傳輸控制技術(shù)[M].武漢:武漢大學(xué)出版社,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] 丁學(xué)君,田勇.一種利用SA-DWT的任意形狀ROI編碼方法[J].電訊技術(shù),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] 申杰,鄭小玉,朱維樂(lè).降低頭肩視頻序列編碼碼率的一種新方法[J].電訊技術(shù),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)