一種可實(shí)現(xiàn)零內(nèi)存存取的CAVLC解碼算法

黃明政，韓一石

一種可實(shí)現(xiàn)零內(nèi)存存取的CAVLC解碼算法

黃明政，韓一石

(廣東工業(yè)大學(xué)信息工程學(xué)院，廣州 510006)

在基于上下文的自適應(yīng)可變長(zhǎng)度編碼(CAVLC)解碼算法中，對(duì)非結(jié)構(gòu)化自適應(yīng)可變長(zhǎng)度編碼碼表進(jìn)行解碼時(shí)需要反復(fù)查找碼表進(jìn)行碼字匹配，從而導(dǎo)致解碼速度慢和需要大量?jī)?nèi)存存取的問(wèn)題。為此，提出一種可實(shí)現(xiàn)零內(nèi)存存取的CAVLC解碼算法。將CAVLC碼字前綴0的個(gè)數(shù)作為一級(jí)索引，同時(shí)通過(guò)一級(jí)索引獲得輸入碼流的可能長(zhǎng)度。將碼字后綴作為二級(jí)索引并獲得碼字的值，直接通過(guò)碼字快速獲得解碼結(jié)果。對(duì)于確定的輸入碼字，只需通過(guò)無(wú)碼表查找代碼操作即可得到對(duì)應(yīng)的解碼輸出。測(cè)試結(jié)果表明，該算法不僅可以實(shí)現(xiàn)零內(nèi)存存取的CAVLC解碼，而且其解碼速度比標(biāo)準(zhǔn)算法提高了45%。

基于上下文的自適應(yīng)可變長(zhǎng)度編碼；零內(nèi)存存取；碼字前綴；一級(jí)索引；碼字后綴；二級(jí)索引

1 概述

H.264/AVC是最新的國(guó)際性的視頻編解碼標(biāo)準(zhǔn)，它通過(guò)ITU-T(電信聯(lián)盟)和ISO/IEC(標(biāo)準(zhǔn)聯(lián)盟)進(jìn)行制定[1]。H.264/AVC標(biāo)準(zhǔn)包括基本檔次、高級(jí)檔次和主要檔次3種。其中，H.264/AVC基本檔次只包括基于上下文的自適應(yīng)可變長(zhǎng)度編碼(ContextAdaptive Variable Length Coding, CAVLC)技術(shù)，這個(gè)技術(shù)被用來(lái)對(duì)視頻圖像的塊殘差數(shù)據(jù)進(jìn)行編碼。它適用于移動(dòng)設(shè)備環(huán)境，這些環(huán)境都具有低復(fù)雜度、低功耗要求等特點(diǎn)。在H.264/AVC CAVLC編碼中，在對(duì)視頻圖像的塊殘差數(shù)據(jù)量化并進(jìn)行之字形掃描后，利用Coeff_token、(1)、、和這5個(gè)語(yǔ)法元素對(duì)視頻圖像的塊殘差數(shù)據(jù)進(jìn)行編碼壓縮。其中，語(yǔ)法元素代表非零系數(shù)個(gè)數(shù)()和拖尾系數(shù)個(gè)數(shù)()(1)；1代表拖尾系數(shù)符號(hào)；代表除了拖尾系數(shù)外的非零系數(shù)幅值；代表最后一個(gè)非零系數(shù)之前0的個(gè)數(shù)；代表每個(gè)非零系數(shù)前的0個(gè)數(shù)。在CAVLC解碼算法中，只有和1這2個(gè)語(yǔ)法元素通過(guò)規(guī)則的算術(shù)運(yùn)算進(jìn)行解碼，其中算術(shù)運(yùn)算的解碼過(guò)程不需要查找任何的碼表，所以它不需要進(jìn)行存儲(chǔ)碼表的內(nèi)存存取，則這2個(gè)語(yǔ)法元素的解碼碼表內(nèi)存存取次數(shù)為0。其余的3個(gè)語(yǔ)法元素，如、和，都是通過(guò)可變長(zhǎng)度的編碼碼表(VLCTs)進(jìn)行解碼，在此過(guò)程中，需要不斷地查找碼表進(jìn)行相應(yīng)的解碼碼流的匹配；如果碼字跟解碼的碼流不匹配，需要重新查找；因此，在一次解碼的過(guò)程中，需要多次地查找匹配碼表操作才能完成一個(gè)碼字的解碼；以此類(lèi)推在這3個(gè)語(yǔ)法元素的解碼過(guò)程中，一個(gè)視頻圖像碼流需要反復(fù)查找匹配存儲(chǔ)在內(nèi)存中的不規(guī)則碼表，因此，這需要消耗大量的內(nèi)存存取直到所期望的碼字被匹配。在嵌入式系統(tǒng)特別是在多媒體應(yīng)用場(chǎng)合中，內(nèi)存存取次數(shù)是系統(tǒng)性能和功耗的瓶頸[2]。

為了能夠減少內(nèi)存存取次數(shù)，許多優(yōu)化的CAVLC解碼算法已經(jīng)被提出。在硬件設(shè)計(jì)方案中，文獻(xiàn)[3]將所有的碼表融合成一個(gè)碼表，同時(shí)將碼表構(gòu)建成多個(gè)子表來(lái)減少40%的功耗。文獻(xiàn)[4]提出流水線(xiàn)架構(gòu)來(lái)大幅度降低系統(tǒng)操作頻率，從而進(jìn)一步減少功耗。在軟件設(shè)計(jì)方案中，傳統(tǒng)的碼表查找算法，如順序查找碼表算法(TLSS)和二叉樹(shù)查找碼表算法(TLBS)被用來(lái)進(jìn)行CAVLC解碼。然而，由于TLSS要進(jìn)行完整地碼表查找匹配而得到所需要的解碼碼字，因此它需要在每一個(gè)解碼碼字上進(jìn)行碼表的內(nèi)存存取。由于TLBS對(duì)于碼表的內(nèi)存存取的隨機(jī)性，因此它在某些系統(tǒng)中表現(xiàn)得并不是很高效。在一些新的方案中，由于整數(shù)算術(shù)運(yùn)算可以直接進(jìn)行碼字的解碼而不需要碼表查找操作的特性，因而，整數(shù)算術(shù)運(yùn)算被引入CAVLC解碼算法中來(lái)減少碼表的內(nèi)存存取次數(shù)。在Moon的方案中，用于和語(yǔ)法元素的新碼表被提出來(lái)，它通過(guò)利用整數(shù)算數(shù)運(yùn)算來(lái)減少約65%~88%的內(nèi)存存取次數(shù)[5]。在Kim方案中，其他一些整數(shù)算數(shù)運(yùn)算被提出來(lái)，它可以減少大約94%的內(nèi)存存取次數(shù)[6]。然而，在Moon方案中，少量?jī)?nèi)存取次數(shù)是必須的，因?yàn)椴糠终Z(yǔ)法元素還使用TLBS來(lái)進(jìn)行解碼。

為消除CAVLC碼表的內(nèi)存訪(fǎng)問(wèn)次數(shù)，進(jìn)一步提高解碼速度，本文提出一種可實(shí)現(xiàn)零內(nèi)存存取的CAVLC解碼算法，設(shè)計(jì)能夠表達(dá)非結(jié)構(gòu)化可變長(zhǎng)度編碼碼表的代碼，同時(shí)利用該算法，不通過(guò)任何碼表查找獲得解碼的碼字。

2 CAVLC的解碼原理

在H.264/AVC基本檔次中，CAVLC和Exp-Golomb碼字被用來(lái)作為熵編碼的方法。指示信息通過(guò)Exp-Golomb碼來(lái)進(jìn)行編碼，其中這些碼字都具有規(guī)則性結(jié)構(gòu)。那些殘差塊數(shù)據(jù)的量化變換系數(shù)通過(guò)CAVLC碼來(lái)進(jìn)行編碼[7]。在CAVLC中，那些量化的系數(shù)被之字形掃描，然后被5個(gè)語(yǔ)法元素進(jìn)行編碼：，(1)，，，。

在CAVLC解碼器中，一個(gè)4×4塊殘差數(shù)據(jù)的之字掃描值通過(guò)壓縮的比特流來(lái)進(jìn)行重建。圖1為CAVLC解碼過(guò)程的一個(gè)例子，它可以在H.264/AVC標(biāo)準(zhǔn)中找到[8]。該圖顯示了在H.264/AVC基本檔次中的CAVLC解碼原理。其中，Zero_left指示了剩余的0系數(shù)的個(gè)數(shù)。1和語(yǔ)法元素一般都通過(guò)整數(shù)算術(shù)運(yùn)算進(jìn)行解碼，因?yàn)樗鼈兌际峭ㄟ^(guò)規(guī)則的可變長(zhǎng)度編碼碼字(VLC)進(jìn)行編碼的。語(yǔ)法元素、和通過(guò)可變長(zhǎng)度編碼碼表進(jìn)行解碼，因?yàn)樗麄兌际峭ㄟ^(guò)碼表查找來(lái)執(zhí)行的。在解碼的過(guò)程中，需要大量的內(nèi)存存取來(lái)找到所需碼字。

圖1 CAVLC解碼示例

3 本文算法

在H.264/AVC CAVLC解碼中，那些利用可變長(zhǎng)度編碼碼表進(jìn)行解碼的語(yǔ)法元素必須得到處理才能減少內(nèi)存存取次數(shù)以進(jìn)一步降低功耗。在這些語(yǔ)法元素中，語(yǔ)法元素是二維碼表，然而和這2個(gè)語(yǔ)法元素的碼表是一維碼表。通過(guò)分析可變長(zhǎng)度編碼碼表的碼字相關(guān)性，本文提出了一種直接的CAVLC解碼方案[9]，具體步驟如下：

(1)將輸入碼流的最開(kāi)始連續(xù)0的個(gè)數(shù)作為一級(jí)索引，同時(shí)通過(guò)一級(jí)索引獲得輸入碼流的可能長(zhǎng)度。

(2)確定所提出的碼表中的二級(jí)索引并獲得碼字的值。

(3)通過(guò)碼字快速地獲得解碼結(jié)果。

基于這種原則，二維碼表和一維碼表被分別設(shè)計(jì)如表1和表2所示。

表1 Coeff_token(VLCT0, 0≤NC＜2)語(yǔ)法元素的部分二維碼表

表2 Total_zeros(Tc=5)語(yǔ)法元素的部分一維碼表

在表1中，碼字(Code)表示對(duì)應(yīng)語(yǔ)法元素的輸入比特流；8位的解碼碼字(Codeword)表示解碼輸出結(jié)果；其中前3位表示拖尾系數(shù)(1)的個(gè)數(shù)，后5位表示非零系數(shù)的個(gè)數(shù)()；碼字前綴0的個(gè)數(shù)表示碼字的第1個(gè)非零系數(shù)之前部分的連續(xù)0個(gè)數(shù)；碼字后綴(Code Suffix)表示第1個(gè)非零系數(shù)之后的部分。在表2中，解碼碼字直接表示單一的解碼輸出結(jié)果；其他元素表示與表1相同的意思。表3和表4分別表示碼字長(zhǎng)度與表1、表2中所提到的碼字前綴0的個(gè)數(shù)之間的關(guān)系。

表3 表1中碼字前綴0的個(gè)數(shù)和碼字長(zhǎng)度之間的關(guān)系

表4 表2中碼字前綴0個(gè)數(shù)和碼字長(zhǎng)度之間的關(guān)系

本文所提出的解碼算法由以下步驟組成：

Step1 選擇語(yǔ)法元素的可變長(zhǎng)編碼碼表的入口。語(yǔ)法元素有3個(gè)可變長(zhǎng)度編碼碼表和1個(gè)固定長(zhǎng)度編碼的碼表，分別為(VLCT0, 0≤＜2)、(VLCT1, 2≤＜4)、(VLCT2, 4≤＜8)、(FCLT,=–1)[10]。

Step2 讀取碼字前綴0的個(gè)數(shù)值，并將其值作為一級(jí)索引。

Step3 通過(guò)一級(jí)索引獲取碼字的長(zhǎng)度。其中，語(yǔ)法元素的碼字長(zhǎng)度和一級(jí)索引之間的關(guān)系如表3所示。設(shè)定一個(gè)參數(shù)RL作為二級(jí)索引，其中，=碼字長(zhǎng)度–碼字前綴的長(zhǎng)度。

Step4 讀取在輸入碼流中的可能碼字后綴，并將它假設(shè)為，其中，的長(zhǎng)度是根據(jù)來(lái)確定的。將的值跟CAVLC算法中的標(biāo)準(zhǔn)碼字后綴進(jìn)行比較，可以獲得如表1中的解碼碼字。

其他2種語(yǔ)法元素和也通過(guò)同樣的步驟進(jìn)行解碼，只不過(guò)利用碼表表2和表4來(lái)代替表1和表3。語(yǔ)法元素和1可以通過(guò)規(guī)則的整數(shù)算術(shù)運(yùn)算進(jìn)行直接解碼。

圖2展示了一個(gè)選擇VLCT0入口開(kāi)始而實(shí)現(xiàn)CAVLC的5個(gè)語(yǔ)法元素解碼例子。對(duì)于語(yǔ)法元素，一級(jí)索引和二級(jí)索引可以逐步獲得，則和1的結(jié)果可根據(jù)一級(jí)索引直接得到。

圖2 本文算法的解碼原理

圖2中語(yǔ)法元素的輸入碼流(0000100)，其一級(jí)索引為4。如表3所示，可以直接獲取碼字長(zhǎng)度為6或7，這樣就可以得到二級(jí)索引為1或2。如表1所示，在VLCT0中的碼字后綴可能為(1)，(00)或(01)。對(duì)于輸入碼流(0000100)，值與它的碼字后綴相等。筆者轉(zhuǎn)換值，并與標(biāo)準(zhǔn)的碼字相比較，可以得到解碼碼字為(0X65)。這個(gè)解碼的碼字可被解碼為1=2，=5。根據(jù)、、1、和元素即可得到解碼輸出。在表1~表4中，加下劃線(xiàn)的數(shù)字表示這個(gè)例子中所用到的相應(yīng)參數(shù)。

4 仿真結(jié)果

本文計(jì)算4種算法的CAVLC解碼碼表內(nèi)存存取次數(shù)節(jié)省數(shù)據(jù)，包括二叉樹(shù)查找碼表算法(TLBS)、Moon算法，Kim算法和本文算法。針對(duì)不同QP值的測(cè)試序列，與標(biāo)準(zhǔn)按順序查找碼表算法(TLSS)相比，上述4種算法內(nèi)存存取次數(shù)的減少比例如圖3所示。其中，TLSS算法數(shù)值利用JM16.2[11]得到，仿真環(huán)境為Windows XP操作系統(tǒng)，CPU為Intel 2.00 GHz，內(nèi)存大小為1 GB。

圖3 不同序列的碼表內(nèi)存存取次數(shù)節(jié)省比例

由圖3可以看出，本文提出的算法完全消除解碼過(guò)程中的碼表內(nèi)存存取次數(shù)，并且本文算法節(jié)省比例比其他各種算法都高。由于本文算法可以在代碼中完全表達(dá)解碼過(guò)程中非結(jié)構(gòu)化的可變長(zhǎng)度編碼碼表，從而完全省略對(duì)碼表的查找，繼而完全省略碼表的內(nèi)存存取。此外還可以看出，Kim算法比TLBS算法和Moon算法的內(nèi)存存取次數(shù)節(jié)省比例更高一點(diǎn)。可以看出，TLBS算法在圖像高QP值處的內(nèi)存存取次數(shù)會(huì)少一點(diǎn)，而Moon算法在圖像低QP值處的內(nèi)存存取次數(shù)會(huì)少一點(diǎn)。相似結(jié)論也可在文獻(xiàn)[6]中找到。

解碼時(shí)間通過(guò)Window系統(tǒng)的API接口函數(shù)Query PerformanceCounter()進(jìn)行計(jì)算，算法的時(shí)間節(jié)省比例根據(jù)下式計(jì)算：(1–本文算法/標(biāo)準(zhǔn)算法)×100%。圖4顯示了用不同QP值的各種序列進(jìn)行測(cè)試時(shí)，各種算法的解碼時(shí)間節(jié)省比例。

圖4 120幀圖像序列的時(shí)間節(jié)省比例結(jié)果

表5是圖4的解碼時(shí)間數(shù)據(jù)。其中，F(xiàn)orman、Crew和Paris序列是CIF格式的，而Harbour、Soccer和Mobile序列是QCIF格式的。可以看出，本文算法比其他各種算法具有優(yōu)越性。與TLSS標(biāo)準(zhǔn)算法相比，本文算法表現(xiàn)出45%的時(shí)間節(jié)省比例，這是因?yàn)樵撍惴ú恍枰M(jìn)行碼表查找從而可以快速定位解碼碼字。由于Moon算法和Kim算法利用了部分整數(shù)算術(shù)運(yùn)算操作，這2種算法相對(duì)于TLSS算法也表現(xiàn)出了一定的高效性。而由于TLBS算法的二叉樹(shù)隨機(jī)內(nèi)存存取性質(zhì)，因此，該算法表現(xiàn)得并不高效。

表5 系統(tǒng)的CAVLC解碼次數(shù)

5 結(jié)束語(yǔ)

H.264標(biāo)準(zhǔn)的CAVLC查表解碼算法在匹配解碼碼字時(shí)，需要反復(fù)查找碼表，會(huì)導(dǎo)致解碼速度慢和需要消耗大量?jī)?nèi)存存取的問(wèn)題，為此，本文提出一種可實(shí)現(xiàn)零內(nèi)存存取的直接CAVLC解碼算法。該算法根據(jù)CAVLC算法的語(yǔ)法元素、、中前綴0的個(gè)數(shù)與碼字長(zhǎng)度之間的對(duì)應(yīng)關(guān)系，利用二級(jí)索引思想來(lái)提出能夠表達(dá)CAVLC中的非結(jié)構(gòu)化碼表，同時(shí)利用二級(jí)索引技術(shù)設(shè)計(jì)能夠表達(dá)非結(jié)構(gòu)化碼表解碼的代碼，實(shí)現(xiàn)CAVLC的無(wú)碼表查找的直接解碼。仿真結(jié)果表明，相比于標(biāo)準(zhǔn)的TLSS算法，本文算法可以實(shí)現(xiàn)零內(nèi)存存取的CAVLC解碼。同時(shí)，本文算法比標(biāo)準(zhǔn)TLSS算法快45%，優(yōu)于目前常見(jiàn)CAVLC解碼算法。這些內(nèi)存存取次數(shù)的節(jié)省不僅適用于高比特率的場(chǎng)合，也適用于低比特率的場(chǎng)合。本文算法尤其適用于對(duì)功耗要求嚴(yán)格的嵌入式平臺(tái)編解碼環(huán)境[12]。下一步工作是設(shè)計(jì)無(wú)碼表查找同數(shù)字算術(shù)運(yùn)算相結(jié)合的解碼算法，或純數(shù)字算術(shù)運(yùn)算的解碼算法，以實(shí)現(xiàn)CAVLC解碼速度、內(nèi)存存取次數(shù)的消除和內(nèi)存存儲(chǔ)空間的最佳平衡。

[1] ITU. Advanced Video Coding for Generic Audio Visual Services[EB/OL]. (2011-11-01). http://citeseerx.ist.psu.edu/ showciting?cid=323674.

[2] Lee J, Park C, Ha S. Memory Access Pattern Analysis and Stream Cache Design for Multimedia Applications[C]//Proc. of DAC’03. Anaheim, USA: [s. n.], 2003: 21-24.

[3] Lin Hengyao, Lu Yinghong, Liu Binda, et al. A Highly Ef?cient

VLSI Architecture for H.264/AVC CAVLC Decoder[J]. IEEE Transactions on Multimedia, 2008, 10(1): 31-42.

[4] Lee B, Ryoo K. A Design of High-performance Pipelined Architecture for H.264/AVC CAVLC Decoder and Low-power Implementation[J]. IEEE Transactions on Consumer Electronics, 2010, 56(4): 2781-2789.

[5] Moon Y H, Kim G Y, Kim J H. An Efficient Decoding of CAVLC in H.264/AVC Video Coding Standard[J]. IEEE Transactions on Consumer Electronics, 2005, 51(3): 933-938.

[6] Kim Y, Yoo Y, Shin J, et al. Memory-efficient H.264/AVC CAVLC for Fast Decoding[J]. IEEE Transactions on Consumer Electronics, 2006, 52(3): 943-952.

[7] 薛 全, 張 穎, 劉濟(jì)林, 等. 基于變步長(zhǎng)分組的H.264系數(shù)碼表優(yōu)化[J]. 電路與系統(tǒng)學(xué)報(bào), 2006, 11(3): 115-117.

[8] Sullivan G, Bjontegaard G. Recommended Simulation Common Conditions for H.26L Coding Efficiency Experiments on Low-resolution Progressive-scan Source Material[EB/OL]. (2001-09-28). http://65.54.113.26/Publica tion/4142353/.

[9] 張秀麗, 萬(wàn) 忠, 鮑程紅. 基于碼頭分組的CAVLC解碼算法優(yōu)化[J]. 電路與系統(tǒng)學(xué)報(bào), 2007, 14(3): 26-30.

[10] 畢厚杰. 新一代視頻壓縮編碼標(biāo)準(zhǔn)——H.264/AVC[M]. 北京: 人民郵電出版社, 2005.

[11] Suhring K. JM16.2 Software[EB/OL]. (2011-11-10). http:// iphome.hhi.de/suehring/tml/.

[12] 龔建鋒, 金文光, 季愛(ài)明. 基于H.264解碼中CAVLC的優(yōu)化[J]. 微電子學(xué)與計(jì)算機(jī), 2007, 24(1): 85-87.

編輯 金胡考

A CAVLC Decoding Algorithm with Zero Memory Access

HUANG Ming-zheng, HAN Yi-shi

(School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China)

This paper proposes a zero memory access algorithm for direct Context-based Adaptive Variable Length Coding(CAVLC) decoding, aiming to solve the problems of slow decoding speed and a large of memory accesses caused by the repeated table look-up for the match codeword during the unstructured variable length coding table decoding. This algorithm takes the numbers of zero in CAVLC code prefix as the primary index, and gets the probably length of the input code stream. It takes the code suffix as the secondary index and gets the codeword value. It can get the decoded result by the codeword quickly. For the specific input code, the decoded output can be directly gotten without any table look-up. Test results show that not only the algorithm can achieve zero memory access for CAVLC decoding, but also the decoding speed of this algorithm can achieve 45% speed-up, compared with the standard algorithm.

ContextAdaptive Variable Length Coding(CAVLC); zero memory access; code prefix; primary index; code suffix; secondary index

1000-3428(2014)03-0278-05

A

TP919.81

廣東省科技計(jì)劃基金資助項(xiàng)目(2011B090400344, 2011B010200029)

黃明政(1989－)，男，碩士研究生，主研方向：視頻通信，視頻編/解碼；韓一石，副教授

2013-03-22

2013-04-23 E-mail：634099571@qq.com

10.3969/j.issn.1000-3428.2014.03.059