分布式視頻編碼的關(guān)鍵幀提取算法

宋曉麗，劉冀偉，張曉星

(北京科技大學(xué)信息工程學(xué)院，北京 100083)

分布式視頻編碼的關(guān)鍵幀提取算法

宋曉麗，劉冀偉，張曉星

(北京科技大學(xué)信息工程學(xué)院，北京 100083)

分布式視頻編碼方案中，目前常用固定周期的方法選取關(guān)鍵幀.該方法忽略了視頻序列的幀間相關(guān)性、運(yùn)動變化情況.針對這些缺陷，研究了基于聚類的自適應(yīng)關(guān)鍵幀提取算法，在此基礎(chǔ)上，提出基于互信息量的改進(jìn)算法.最后，針對以上2種算法中的時延問題給出了解決方案.實(shí)驗(yàn)證明，對于不同的測試序列，基于互信息量改進(jìn)算法相比固定選取關(guān)鍵幀算法，邊信息PSNR均值有0.67～1.4dB的提高.此外，解決時延的算法比改進(jìn)算法在效率上有很大提高.

分布式視頻編碼;關(guān)鍵幀;互信息

傳統(tǒng)視頻編碼方案在編碼端隱含一個解碼器，使編碼端的運(yùn)算復(fù)雜度是解碼端的5～10倍以上［1］.這種編碼方案適用于編碼端復(fù)雜的領(lǐng)域.而近年來，一些新的移動視頻設(shè)備如:移動視頻相機(jī)、移動視頻電話、無線PC機(jī)等需要低復(fù)雜度編碼.此時，傳統(tǒng)的視頻編碼方案難以勝任，迫切需要一種編碼端復(fù)雜度低的編碼方案.在此背景下，一種新的視頻編碼框架—分布式視頻編碼(distributed video coding，DVC)應(yīng)運(yùn)而生.該編碼方案是基于20世紀(jì)70年代Slepian和Wolf［2］的分布式無損編碼理論以及 Wyner和 Ziv［3］的使用解碼端邊信息(side information)的有損編碼理論而建立.從2002年起DVC的實(shí)現(xiàn)算法逐漸引起關(guān)注，成為視頻編碼領(lǐng)域關(guān)注較多的前沿課題之一.

Wyner－Ziv 視頻編碼 (Wyner－Ziv video coding，WZVC)是DVC編碼的一種主流框架.在WZVC中，待編碼的幀分為K幀和Wyner－Ziv(WZ)幀，K幀是通過傳統(tǒng)的視頻編碼方案進(jìn)行幀內(nèi)編解碼，而WZ幀則是通過信道編碼，僅傳輸校驗(yàn)位給解碼端.大多數(shù)WZVC方案采用周期性選擇關(guān)鍵幀的方法，該方法有許多弊端［4］:如果視頻序列運(yùn)動緩慢，選擇過多的關(guān)鍵幀會造成冗余，不利于壓縮比的提高;如果視頻序列運(yùn)動劇烈，選擇較少的關(guān)鍵幀則難以生成高質(zhì)量的邊信息.為了解決這些問題，需要一種有效的選擇關(guān)鍵幀的方法，使得關(guān)鍵幀會隨著視頻序列的運(yùn)動情況而靈活變化.

文獻(xiàn)［5］提出一種基于聚類算法的自適應(yīng)關(guān)鍵幀提取算法;文獻(xiàn)［4］利用感興趣點(diǎn)來描述圖像的信息，提出一種基于感興趣點(diǎn)匹配的關(guān)鍵幀選擇算法;文獻(xiàn)［6］利用SURF算法得到的特征點(diǎn)信息作為對幀間相關(guān)性的近似估計，提出一種自適應(yīng)選取關(guān)鍵幀的方法.上述幾種方法從不同角度進(jìn)行了關(guān)鍵幀提取算法的研究，系統(tǒng)性能比周期性選取關(guān)鍵幀提取算法均有所提高.

本文研究了文獻(xiàn)［5］中的算法，并且從另一角度，利用互信息量來描述相鄰2幀的相關(guān)性，提出基于互信息量的自適應(yīng)關(guān)鍵幀提取改進(jìn)算法，從系統(tǒng)性能和計算復(fù)雜度上對文獻(xiàn)［5］中的算法進(jìn)行了改進(jìn)，然后對算法中的時延問題給出了解決方案.

1 Wyner－Ziv 視頻編碼框架

本文采用變換域分布式視頻編碼系統(tǒng)［7］，編碼框架如圖1所示，首先將視頻序列分為K幀和WZ幀(每個GOP里的首幀為K幀，其余幀為WZ幀).K幀采用傳統(tǒng)幀內(nèi)編解碼方法.WZ幀經(jīng)過基于8×8的塊DCT變換后，進(jìn)行量化，然后提取位平面，從高位到低位依次送入LDPC編碼器編碼，編碼后根據(jù)解碼端的反饋信息，將要求的校驗(yàn)位送到解碼端.

圖1 Wyner－Ziv視頻編碼框架Fig.1 Architecture Wyner-Ziv video coding

在Wyner－Ziv視頻編碼系統(tǒng)框架中，解碼是最復(fù)雜的部分，對于K幀，只需要進(jìn)行傳統(tǒng)的幀內(nèi)解碼就可以得到相應(yīng)的解碼幀;而對于每個WZ幀，解碼器都會利用相鄰的已經(jīng)解碼的K幀，使用時間域上的插值或者外推的方法形成作為估計WZ幀的輔助信息，對輔助信息做DCT變換，和編碼端一樣提取位平面，送入LDPC解碼器;LDPC解碼器，如果不能可靠地解碼出符號流，會通過反饋信息從編碼器的緩沖區(qū)中申請附加的奇偶校驗(yàn)碼;利用解碼后的比特流和DCT變換后的邊信息重建WZ幀.

2 自適應(yīng)選取關(guān)鍵幀

2.1 基于聚類的自適應(yīng)關(guān)鍵幀提取

文中利用以下4個低水平特征指標(biāo)來評估視頻序列的運(yùn)動劇烈程度［5］:1)直方圖差DH;2)差的直方圖HD;3)塊的直方圖差BHD;4)塊的方差的差BVD;

它們的定義如下:

式中:i、j代表幀的索引，h代表L區(qū)間的直方圖，Df和DB分別代表幀和塊的大小，σ代表方差，對于指標(biāo)HD，α代表與原值接近的閾值.前2個指標(biāo)在幀水平上，檢測全部運(yùn)動的變化，HD指標(biāo)是非常有效的.BHD和BVD指標(biāo)對于局部運(yùn)用更為敏感.

基于上述4個指標(biāo)的聚類關(guān)鍵幀提取算法描述如下:

1)計算所有幀中相鄰幀間的4個指標(biāo)，建立四維矢量，并進(jìn)行歸一化;

2)累積相鄰2幀幀間運(yùn)動矢量，找到相鄰2幀幀間運(yùn)動矢量規(guī)范化式最小值對應(yīng)的下標(biāo)值;

3)將該下標(biāo)值對應(yīng)的幀與后一幀或后一類進(jìn)行聚類;

4)重復(fù)步驟2)、3)，直到相鄰2幀間運(yùn)動積累大于設(shè)定的閾值φ時，停止聚類.

φ控制聚類的類數(shù)，同時也控制了關(guān)鍵幀幀數(shù)(每類里的首幀為關(guān)鍵幀).

2.2 基于互信息量的關(guān)鍵幀提取

2.2.1 互信息量

互信息量源于信息論，不僅是2個隨機(jī)變量相似性的量度，同時也決定了每一個獨(dú)立的隨機(jī)變量在交迭處各自表示的信息量的大小.利用互信息量作為圖像的相似性測度是Collignon［9］于1995年提出的，它在應(yīng)用上取得了很大成功.

2幅圖像的互信息量定義如下:式中:PX(x)和PY(y)分別表示前一幀X和當(dāng)前幀Y的概率密度函數(shù)，由圖像的直方圖除以圖像總的像素個數(shù)得到;PXY(xy)表示相鄰2幀的聯(lián)合概率密，由圖像X、Y的聯(lián)合直方圖除以圖像總的像素個數(shù)得到.由定義可知，互信息量并不信賴于灰度值本身，而是信賴于這些灰度值出現(xiàn)的概率.當(dāng)互信息量為0時，說明視頻序列相鄰幀發(fā)生劇烈運(yùn)動，該相鄰幀相互獨(dú)立;當(dāng)互信息量值較大時，意味著相鄰幀間的相似性程度較高，所以互信息量能很好地反映視頻序列中相鄰2幀間的相似性程度.

2.2.2 關(guān)鍵幀提取的改進(jìn)算法

互信息量從全局運(yùn)動來反映視頻相鄰2幀間的變化，2.1節(jié)中的DH和HD這2個指標(biāo)也是從全局角度出發(fā)來衡量2幀間的相似性.但互信息量表示的是2幅圖像相互包含對方的信息量，即幀X包含幀Y的信息量或幀Y包含幀X的信息量，相比于DH和HD，互信息量更加直接，全面描述了2幀的相似程度.因此在改進(jìn)算法中用互信息量替換DH和HD作為衡量視頻序列全局變化的指標(biāo)，同時保留原有的局部指標(biāo):BHD和BVD.

改進(jìn)的關(guān)鍵幀提取算法步驟如下:

1)計算所有視頻序列的相鄰2幀間的I、BHD和BVD，建立三維矢量，并進(jìn)行歸一化;

2)、3)、4)同2.1節(jié)中基于聚類的關(guān)鍵幀提取算法中步驟 2)、3)、4).

由式(1)、(2)和(3)得知，改進(jìn)算法的計算復(fù)雜度明顯減小.首先，互信息量的計算量小于DH和HD的計算量和;其次，相比于原算法中的基于四維矢量聚類，改進(jìn)算法中基于三維矢量進(jìn)行聚類較為簡單.

3 解決時延的關(guān)鍵幀提取算法

基于聚類的自適應(yīng)關(guān)鍵幀提取算法和基于互信息量的關(guān)鍵幀提取算法，在編碼端的聚類過程引進(jìn)了時延，這不滿足實(shí)際應(yīng)用的實(shí)時性.因而有必要對上述2種方法的時延問題進(jìn)行研究，本文給出了合理的解決方案.

假設(shè)視頻序列比較平穩(wěn)，根據(jù)系統(tǒng)已經(jīng)選擇好的GOP可以預(yù)測后續(xù)視頻序列的GOP，減少編碼端等待時間，同時選擇幾個不同GOP中率失真性能最優(yōu)(用每個GOP中WZ幀的率失真性能代替整個GOP的率失真性能)的GOP作為編碼組，進(jìn)而保證了選擇的關(guān)鍵幀的有效性.其中速率的估計可以直接獲得［9］，WZ 幀 PSNR 值估計［10］如式(6):

解決時延的關(guān)鍵幀提取算法的具體過程如下:

1)以當(dāng)前幀為起始幀，在編碼端分別計算GOP為2、3、4時的率失真性能;

2)選擇最優(yōu)性能的GOP作為特定窗口內(nèi)的第一個GOP，窗口的初始大小為1，當(dāng)且僅當(dāng)當(dāng)前獲得的GOP與先前的GOP一樣時，窗口尺寸才會增加(W=2×Wold，W＜20)，否則W=1;

3)Wold=W;

4)W為1時，使用選擇好的GOP進(jìn)行編碼，從下一幀算起，回到1);

5)當(dāng)W不為1時，連續(xù)進(jìn)行W個GOP(從當(dāng)前GOP的前一個GOP作為初始值算起)編碼，未完成時重復(fù)進(jìn)行4)，否則重新開始測試GOP，回到1).

根據(jù)上述分析及算法步驟可知，該算法選擇性能最優(yōu)GOP作為編碼GOP，能保證系統(tǒng)的性能，且在滿足一定條件時，允許連續(xù)編碼，可以用當(dāng)前的GOP作為后續(xù)窗口內(nèi)的GOP，明顯減少測試GOP所用的時間，因此該算法在保證系統(tǒng)性能的前提下，能有效減少時延.

4 實(shí)驗(yàn)結(jié)果

本部分首先給出傳統(tǒng)周期性關(guān)鍵幀提取算法(periodical key frame selection，PKFS)、基于聚類的自適應(yīng)關(guān)鍵幀提取算法(clustering adaptive key frame selection，CAKFS)和基于互信息量關(guān)鍵幀提取改進(jìn)算法(mutual information key frame selection improving algorithm，MIKFS)3種方案的性能對比，結(jié)果如表1所示.實(shí)驗(yàn)中，以Foreman、Coastguard序列作為測試序列，以邊信息和原始WZ幀的平均PSNR作為評判標(biāo)準(zhǔn)，通過調(diào)整閾值使3種方案中的關(guān)鍵幀數(shù)(key frame number，KFN)相同.

表1 PKFS、CAKFS與MIKFS的性能比較Table 1 Comparison results of the performance of PKFS，CAKFS and MIKFS dB

分析表1的數(shù)據(jù)可知，在測試序列為 Foreman、Coastguard時，相比于PKFS方案，CAKFS方案中邊信息質(zhì)量分別平均提高了0.13 dB、0.97 dB.本文給出的MIKFS改進(jìn)方案中邊信息質(zhì)量相比于CAKFS方案提高了0.53 dB、0.47 dB;相比于PKFS方案提高了0.67 dB、1.4 dB.可見說明了本文MIKFS方案的優(yōu)越性.

關(guān)于解決時延的關(guān)鍵幀提取算法的實(shí)驗(yàn)，用Foreman序列的前100幀來測試，測試架構(gòu)是本文第2部分給出的DVC框架，1)量化部分采用JPEG標(biāo)準(zhǔn)里量化矩陣，量化因子為 QF=(0.5，2，4)，取不同的量化因子，可以獲得不同的輸出碼率和不同質(zhì)量的重建幀.量化因子為0.5時，DEKFS算法獲得的GOP情況如圖2;2)調(diào)節(jié)CAKFS和MIKFS中的閾值，使3類算法的關(guān)鍵幀數(shù)相等;3)邊信息使用傳統(tǒng)的運(yùn)動補(bǔ)償內(nèi)插方案來插出.首先給出以PSNR值作為評判準(zhǔn)則，DEKFS算法與PKFS算法相比較的結(jié)果如表2所示.

圖2 DEKFS算法的GOP情況Fig.2 GOP results of DEKFS algorithm

表2 PKFS與DEKFS的性能比較Table 2 Comparison results of the performance of PKFS and DEKFS dB

分析表2的數(shù)據(jù)可知，在測試序列為 100幀F(xiàn)oreman時，相比于PKFS方案，DEKFS方案中邊信息質(zhì)量平均提高了0.1 dB.

另外給出了CAKFS算法、MIKFS算法與解決時延的關(guān)鍵幀選取算法(delay efficient key frame selection，DEKFS)整體性能比較結(jié)果.分別統(tǒng)計CAKFS算法、MIKFS算法和解決時延的關(guān)鍵幀選取算法中總WZ幀的率失真性能，測試結(jié)果如圖3.

圖3 Wyner－Ziv系統(tǒng)性能對比Fig.3 Performance comparison of Wyner-Ziv system

3類算法的時間統(tǒng)計結(jié)果如圖4.

圖4 3種算法的時間對比Fig.4 Time comparison of three algorithms

由圖3可知，解決時延的關(guān)鍵幀算法與基于聚類的自適應(yīng)關(guān)鍵幀算法和改進(jìn)算法相比，率失真性能有略微降低.主要是因?yàn)楸疚牡乃惴ㄊ窃诩僭O(shè)視頻序列比較平穩(wěn)的前提下進(jìn)行的，這樣可以預(yù)測后續(xù)視頻序列的GOP，另外，DEKFS算法限制了每個GOP里能取的幀數(shù)的范圍.

雖然DEKFS算法相比于CAKFS和MIKFS，率失真性能略微降低，但從圖4可得，DEKFS算法相比于 PKFS在時間對比度上有明顯的優(yōu)越性.CAKFS和MIKFS算法必須把所有的幀先聚類，才能編碼，這樣編碼端聚類沒有完成時，編碼器閑置起來，造成時間的浪費(fèi).而CAKFS算法在獲得一組GOP后，編碼器即可開始編碼，編碼和后續(xù)GOP的獲得可以同時進(jìn)行，允許系統(tǒng)持續(xù)編碼，對于平穩(wěn)的視頻序列，可以通過前面的GOP獲得即將編碼的GOP尺寸，減少計算量，且更有效地減少了時間.因此，從實(shí)際角度出發(fā)，能夠解決時延的算法更有效.

5 結(jié)束語

DVC中固定選取關(guān)鍵幀的方法對系統(tǒng)性能的提高有一定的局限性.基于此，本文在研究基于聚類的關(guān)鍵幀提取算法的基礎(chǔ)上，提出了基于互信息量的改進(jìn)算法，改進(jìn)算法中用互信息量作為反映視頻序列的幀間相關(guān)性的全局指標(biāo)，優(yōu)化了率失真性能，同時提高了計算效率.但以上2種算法都有一定的延遲效應(yīng)，解決時延的算法在率失真性能上略微降低，卻有效地減少了編碼器的等待時間，更具有實(shí)際應(yīng)用價值.后續(xù)的工作將考慮如何更精確地度量幀間相關(guān)性，優(yōu)化DVC的率失真性能，以及在DVC的率失真性能和關(guān)鍵幀選取算法的復(fù)雜度之間找到平衡點(diǎn).

［1］NILSSON M.The advanced video coding standard［C］//IT to HD:Visions of Broadcasting in the 21st Century.London，UK，2004:85－100.

［2］SLEPIAN D，WOLF J.Noiseless coding of correlated information sources［J］.IEEE Transactions on Information Theory，1973，19(4):471－480.

［3］WYNER A，ZIV J.The rate－distortion function for source coding with side information at the decoder［J］.IEEE Transactions on Information Theory，1976，22(1):1－10.

［4］YANG Feng，DING Guiguang，DAI Qionghai.Adaptive key frame selection Wyner－Ziv video coding［C］//IEEE Multimedia Signal Processing.Shanghai，China，2005:1－4.

［5］ASCENSO J，BRITES C，PRERIRA F.Content adaptive Wyner－Ziv video coding driven by motion activity［C］//IEEE International Conference on Image Processing.Atlanta，USA，2006:605－609.

［6］張曉星，劉冀偉，張波.分布視頻編碼中基于幀間相關(guān)性的自適應(yīng)關(guān)鍵幀選取算法［J］.光電子·激光，2010，21(10):1536－1541.

ZHANG Xiaoxing，LIU Jiwei，ZHANG Bo.Adaptive key frame selection algorithm based on interframe correlation in distributed video coding［J］Journal of Optoelectronics·Laser，2010，21(10):1536－1541

［7］AARON A，RANE S，SETTON E，et al.Transforms－domian Wyner－Ziv codec for video［C］//Visual Comm－ unications and Image Processing.San Jose，USA，2004:520－528.

［8］MAES F，COLLIGNON A，VANDERMEULEN D.Multi－modality image registration by maximization of mutual information［C］//Mathematical Methods in Biomedical Image Analysis.San Francisco，USA，1996:14－22.

［9］YAACOUB C，F(xiàn)ARAH J，PESQUET－POPESCU B.Optimal rate allocation in multi－user Wyner－Ziv video coding systems with coded key frames［C］//Personal，Indoor and Mobile Radio Communications.Cannes，F(xiàn)rance，2008:1－5.

［10］AHMAD I，AHMAD Z，ABOU－FAYCAL I.Delay－efficient GOP size control algorithm in Wyner－Ziv video coding［C］//Signal Processing and Information Technology.Ajman，United Arab Emirates，2009:403－408.

宋曉麗，女，1986年生，碩士研究生，主要研究方向?yàn)閳D像處理、視頻壓縮等.

劉冀偉，男，1962年生，副教授，中國人工智能學(xué)會、人工心理與情感計算專業(yè)委員會理事，主要研究方向?yàn)閳D像處理、視頻壓縮、人工智能系統(tǒng)等，近年來在國內(nèi)外著名期刊與會議上發(fā)表學(xué)術(shù)論文40余篇，出版著作多部.

張曉星，男，1984年生，博士研究生，主要研究方向?yàn)閳D像處理、圖像、視頻編碼等.

A key frame selection algorithm for distributed video coding

SONG Xiaoli，LIU Jiwei，ZHANG Xiaoxing
(School of Information Engineering，Beijing University of Science and Technology，Beijing 100083，China)

In most of the existing distributed video coding schemes，the fixed period method is usually applied for selecting a key frame.This strategy ignores the correlation between video frames and the changes of the motion activity along the video sequence.To avoid these flaws，this paper studied the adaptive key frame selection method based on hierarchical clustering;on this basis，an improved algorithm based on mutual information was proposed.Finally，a solution was given to overcome the delay in the above－mentioned methods.Experimental results show that for various video sequences，a 0.67－1.4dB gain in the quality of side information has been achieved.In addition to being delay－efficient，the key selection algorithm requires the lowest performance time.

distributed video coding;key frame;seection algorithm;mutual information

TP18;TN919.81

A

1673－4785(2011)06－0539－05

10.3969/j.issn.1673－4785.2011.06.010

2011－07－11.

國家自然科學(xué)基金資助項(xiàng)目(60903067).

宋曉麗.E－mail:xysxl02@163.com.