H．264解碼器中CAVLC碼表查找算法的分析與優(yōu)化
加入技術(shù)交流群
近年來(lái)，隨著(zhù)信息技術(shù)飛速發(fā)展和互聯(lián)網(wǎng)的日益普及，尤其是以視頻為信息主要來(lái)源的多媒體領(lǐng)域越來(lái)越受到人們的關(guān)注。H．264是ITU-T的視頻編碼專(zhuān)家組(VCEG)和ISO／IEC的活動(dòng)圖像編碼專(zhuān)家組(MPEG)的聯(lián)合視頻組(Joint Video Tearn，JVT)開(kāi)發(fā)的一個(gè)新的數字視頻編碼標準，它既是ITU-T的H．264，又是ISO／IEC的MPEG-4的一部分。H．264和以前的標準一樣，也是DPCM加變換編碼的混合編碼模式。H．264標準可分為三檔：基本檔次(其簡(jiǎn)單版本，應用面廣)；主要檔次(采用了多項提高圖像質(zhì)量和增加壓縮比的技術(shù)措施，可用于SDTV、HDTV和DVD等)；擴展檔次(可用于各種網(wǎng)絡(luò )的視頻流傳輸)。
H．264／AVC的編解碼框架的基本結構與早期的編碼標準(H．263、MPEG4等)相似，都是由運動(dòng)估計、變換、量化、熵編碼、環(huán)路去塊效應濾波器等功能單元組成的。H．264視頻編碼框架的主要變化包括：引入了環(huán)內去塊效應濾波器，去塊效應處理后的宏塊被保存在內存中用于對后續宏塊的預側；采用了多參考幀運動(dòng)估計，需要在內存中保留多個(gè)參考視頻幀；引入了幀內預測機制，可以通過(guò)同一幀內的宏塊進(jìn)行預測；采用了新的整型變換方式，取代了以前的離散余弦變換(DCT)；H．264與以前視頻標準在運動(dòng)估計的模式上也有了較大的變化，H．264支持7種模式的可變塊運動(dòng)估計。此外，在熵編碼中還引入了上下文自適應的變長(cháng)編碼(CAVLC)和二進(jìn)制算術(shù)編碼(CABAC)。
在熵編碼方面，H．264使用了CABAC和CAVLC兩種不同的編碼方式。CABAC熵編碼是一種基于區間劃分的算術(shù)編碼方式。這種編碼方式的效率很高，接近信息熵值，但算法相對復雜，編解碼速度較慢。CAVLC是一種可變長(cháng)編碼，它根據已編碼語(yǔ)法元素的情況動(dòng)態(tài)調整編碼中使用的碼表，在編碼過(guò)程中有些語(yǔ)法元素是組合編碼的，當對這些元素進(jìn)行查找時(shí)就會(huì )耗費很長(cháng)的時(shí)間。因此對CAVLC的優(yōu)化顯得格外重要。
1 原碼表查找算法
原碼表的存儲結構為二維表結構。存儲的內容為碼字，二維坐標分別代表解碼后的兩個(gè)語(yǔ)法元素。對于二維表結構。若通過(guò)坐標查找內容是很容易的；而通過(guò)內容查找坐標，就需要對整個(gè)表進(jìn)行遍歷。JM中的碼表查找算法就是通過(guò)遍歷整個(gè)碼表實(shí)現的，步驟如下：
(1)取碼表的中的一個(gè)碼字；
(2)根據碼字長(cháng)度從碼流中取出相應長(cháng)度的bit；
(3)比較此碼字和bit串，若相同則查找成功，否則若碼表中還有碼字，回步驟(1)，否則查找失敗。
2 算法的優(yōu)化分析
2．1 基于前綴零分組子表搜索算法
基于上下文自適應的變長(cháng)編碼的解碼算法需要不斷的讀取碼流，判斷，直到在碼表中找到該碼字，如此反復，直至解碼整個(gè)塊。由此可見(jiàn)該過(guò)程的時(shí)間空間復雜度都是相當高的。由于變長(cháng)碼為霍夫曼前綴碼，所以可以根據碼表的特性，按照碼字長(cháng)度將原來(lái)的一個(gè)碼表，按照碼字長(cháng)度對原碼表進(jìn)行分割，以Coeff_token碼表為例，原碼表如表1所示，表中NC=-1。
在參考模型中，搜索碼表算法過(guò)程如下：
(1)從最短碼長(cháng)開(kāi)始，讀出該長(cháng)度二進(jìn)制數據流對應的碼字；
(2)遍歷碼表，如找到該碼字進(jìn)行步驟(4)，否則進(jìn)入(3)；
(3)碼字長(cháng)度加1，重定位指針位置，重復步驟(2)；
(4)讀取該碼字對應值，更新指針位置。
從上面過(guò)程中不難發(fā)現，碼字長(cháng)度的不確定性使得在讀取字節流時(shí)只能一次次的試探，導致了效率的下降。如果可以將變長(cháng)碼的讀取采取固定的策略，一次讀取固定的長(cháng)度，之后再做判斷，再讀取一定長(cháng)度，這樣將判斷的次數也固定，從理論上可以降低不斷搜索和重定位指針帶來(lái)的時(shí)間和空間復雜性。利用可以利用碼表中碼字前綴零數目的不同，將表1拆分為兩個(gè)子表，如表2，表3所示NC為-1。
改進(jìn)后的碼表搜索算法如下：
(1)讀取最大碼字長(cháng)度的二進(jìn)制流；
(2)根據不同的前綴零位數、右移位、判零以確定碼字所在子表；
(3)直接根據碼值讀取對應值，更新指針位置。
新的搜索過(guò)程不但避免了不確定性，而且無(wú)需遍歷碼表，這樣可以在一定程度上提高變長(cháng)解碼的效率。
按照改進(jìn)的算法步驟，解碼時(shí)，首先從字節流中讀取8位碼字，由于前綴零個(gè)數分為大于3和小于3的兩種情形，所以右移5位，若為零，則查找表2，否則查找表1，根據碼值直接解碼出±1個(gè)數，非零系數數目。此外在設計代碼時(shí)，還可利用二叉搜索樹(shù)的特性，設計搜索過(guò)程，提高解碼效率。
評論