UMHexagonS算法優(yōu)化(AP1234)[白世軍]

1、基于H.264/AVC視頻編碼運(yùn)動(dòng)估計(jì)算法的優(yōu)化學(xué)科：控制科學(xué)與工程答辯人：白世軍導(dǎo) 師：王煜 教授博導(dǎo) 副導(dǎo)師：吳曉軍副教授副導(dǎo)師：吳曉軍副教授哈爾濱工業(yè)大學(xué)深圳研究生院哈爾濱工業(yè)大學(xué)深圳研究生院2008年年12月月13日日論文題目：論文題目：答辯提綱 課題背景及研究任務(wù) H.264/AVC編碼器原理 UMHS算法描述及可優(yōu)化點(diǎn)分析 基于UMHS算法的優(yōu)化 實(shí)驗(yàn)結(jié)果與性能分析 總結(jié)及展望課題背景及研究任務(wù)(編碼發(fā)展簡(jiǎn)史) 1984年CCITT發(fā)布了H.120(數(shù)字基群電視會(huì)議編碼標(biāo)準(zhǔn))建議 1988年CCITT通過了“px64Kbps(p = 1,2,3,30)”視頻編碼標(biāo)準(zhǔn)H.261建議，

2、被成為視頻壓縮編碼的一個(gè)里程碑 1986年，ISO和CCITT成立了聯(lián)合圖象專家組（JPEG, Joint Photographic Experts Group),1992年通過了JPEG標(biāo)準(zhǔn) 1998年ISO/IEC成立了活動(dòng)圖象專家組(MPEG,Moving Picture Experts Group). 1991年公布了MPEG-1標(biāo)準(zhǔn)，碼率為1.5Mbps,主要應(yīng)用于家用VCD的視頻壓縮 1994年公布了MPEG-2標(biāo)準(zhǔn),用于DVB、DVD、HDTV碼率從4Mbps 、15Mbps.直到100Mbps分別用于不同檔次和不同級(jí)別的視頻壓縮中課題背景及研究任務(wù) 1995年，ITU-T推出H

3、.263標(biāo)準(zhǔn)，用于低于64Kbps的低碼率視頻傳輸 1998年和2000年又分別公布了H.263+和H.263+等標(biāo)準(zhǔn) 1999年，ISO/IEC通過了MPEG4,它除了定義視頻壓縮標(biāo)準(zhǔn)為，還強(qiáng)調(diào)了多媒體通信的交互性和靈活性 2003年3月， ITU-T和ISO/IEC公布了H.264視頻壓縮標(biāo)準(zhǔn)，不僅顯著提高了壓縮比，而且具有良好的網(wǎng)絡(luò)親和性，加強(qiáng)了對(duì)IP網(wǎng)、移動(dòng)網(wǎng)的誤碼和丟包的處理有人將H.264成為新一代的視頻編碼標(biāo)準(zhǔn)課題背景及研究任務(wù)(H.264標(biāo)準(zhǔn)的性能優(yōu)勢(shì)和計(jì)算復(fù)雜度)H.264的視頻編碼層采用了多種新技術(shù)，在相同的圖像質(zhì)量下，H.264所需碼率約為MPEG-2的36%、H.263

4、的51%、MPEG-4的61%，極大的提高了壓縮率，保證了圖象質(zhì)量。研究表明：H.264編碼器由于采用了高精度運(yùn)動(dòng)矢量(Motion vector)，計(jì)算量迅速增長(zhǎng)，運(yùn)動(dòng)估計(jì)消耗整個(gè)編碼80左右時(shí)間，嚴(yán)重降低了編碼的實(shí)時(shí)性。 因此，研究基于H.264的運(yùn)動(dòng)估計(jì)(Motion Estimation )快速算法，是H.264標(biāo)準(zhǔn)走向?qū)崟r(shí)應(yīng)用的關(guān)鍵，也是本文研究的重點(diǎn)。H.264/AVC編碼器原理(圖像的冗余) 視頻序列圖像在時(shí)間上存在很強(qiáng)的相關(guān)性，采用運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償技術(shù)可以消除時(shí)間冗余以提高編碼效率，這種技術(shù)廣泛用于視頻壓縮的一些國(guó)際標(biāo)準(zhǔn)中，如H.261/263/264、MPEG-1/2/4。

5、H.264/AVC編碼器原理H.264編碼器前向編碼通道反向解碼通道(重構(gòu)幀)本文研究對(duì)象本文研究對(duì)象H.264/AVC編碼器原理（運(yùn)動(dòng)估計(jì)的定義） 基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認(rèn)為宏塊內(nèi)所有象素的位移量都相同，然后對(duì)每個(gè)宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最相似的塊，即匹配塊，匹配塊與當(dāng)前塊的相對(duì)位移即為運(yùn)動(dòng)矢量。視頻壓縮的時(shí)候，只需保存運(yùn)動(dòng)矢量和殘差數(shù)據(jù)就可以完全恢復(fù)出當(dāng)前塊。H.264/AVC編碼器原理(運(yùn)動(dòng)估計(jì)的基本思想 )運(yùn)動(dòng)估計(jì)（Motion Estimation, ME):其表達(dá)方式是運(yùn)動(dòng)矢（Motion Vector, MV

6、），研究的主要內(nèi)容就是如何快速、有效的獲得有足夠精度的運(yùn)動(dòng)矢量(MV)H.264/AVC編碼器原理H.264中定義的塊匹配誤差函數(shù)：(,)( , ()()J MVSAD s c MVMOTIONMOTIONR MVPMV其中SAD(絕對(duì)差值和)定義如下：,1,1( , () , ,16,84xyBBxyxyxySAD s c MVs x yc xMVyMVB Bors: 當(dāng)前要進(jìn)行編碼的原始數(shù)據(jù)c: 是已編碼重建的用于進(jìn)行運(yùn)動(dòng)補(bǔ)償?shù)膮⒖紟瑪?shù)據(jù)MV: 為侯選的運(yùn)動(dòng)矢量PMV:為中值預(yù)測(cè)矢量R(MV-PMV):代表運(yùn)動(dòng)矢量差分編碼可能耗費(fèi)的比特?cái)?shù)H.264/AVC編碼器原理(UMHSUMHS算法算

7、法)UMHSUMHS算法算法(本文研究的快速運(yùn)動(dòng)估計(jì)算法) UMHS算法全名叫“非對(duì)稱十字型多層次六邊形格點(diǎn)搜索算法”(Unsymmetrieal-CrossMuti-HexagonSeareh，UMHS)算法特點(diǎn)：可以在很大程度上提高預(yù)測(cè)的有效性和魯棒性 ，相對(duì)于H.264中原有的快速全搜索算法可節(jié)約90% 搜索時(shí)間 UMHS算法描述及可優(yōu)化點(diǎn)分析具體搜索方法的步驟：Step1:起始搜索點(diǎn)搜索（中值預(yù)測(cè)）Step2:不對(duì)稱的十字交叉搜索Step3:非均勻多層次六邊形格點(diǎn)搜索Step3-1:小矩形窗口全搜索Step3-2:擴(kuò)展的多層次六邊形16格點(diǎn)Step4:擴(kuò)展的六邊形搜索Step4-1:六

8、邊形模式搜索Step4-2:基于小六邊形(菱形)模式搜索UMHS算法描述及可優(yōu)化點(diǎn)分析 (1)算法起始搜索點(diǎn)位置如何確立？(2)參考搜索窗口多大？(3)能否鎖定搜索象限？(4)小六邊形(菱形)搜索點(diǎn)數(shù)目是否可以減少？UMHS算法深入分析：UMHS算法描述及可優(yōu)化點(diǎn)分析(AP1)(1)算法起始搜索點(diǎn)位置如何確立？中值預(yù)測(cè)中值預(yù)測(cè)的不足：由于不同的視頻序列運(yùn)動(dòng)特征不一樣，對(duì)不同的序列都把中值預(yù)測(cè)作為起始搜索窗口的起始點(diǎn)，而不是根據(jù)不同的序列所特有的運(yùn)動(dòng)特性動(dòng)態(tài)的確定搜索窗口位置，不利于快速匹配和提高匹配精度時(shí)間和空間預(yù)測(cè) (t-1)tUMHS算法描述及可優(yōu)化點(diǎn)分析(AP1)參考幀中對(duì)應(yīng)位置的塊當(dāng)前

9、塊確定搜索中心點(diǎn)位置原則：根據(jù)col_mv和med_mv大小和是其夾角大小來確定Collocated blockCurrent block優(yōu)化方法(AP1)：用動(dòng)態(tài)搜索中心代替固定搜索中心(中值預(yù)測(cè))UMHS算法描述及可優(yōu)化點(diǎn)分析(AP1) (0,0)(2,2)(1)_0&_0 xycolmvcolmv(2)垂直運(yùn)動(dòng)（Vertical movement）(3)水平運(yùn)動(dòng)(4)相同的方向和速度運(yùn)動(dòng)(5)相同的方向不同的速度運(yùn)動(dòng)(6)其他情況(中值預(yù)測(cè))XYUMHS算法描述及可優(yōu)化點(diǎn)分析(AP2)(2)參考搜索窗口多大？UMHS 算法中采用了固定大小的參考搜索窗口，其大小為（2*search

10、_range + 1）*（2*search_range + 1） 通過配置文件由search_range來設(shè)置，search_range = 16/32/48/64。 UMHS算法描述及可優(yōu)化點(diǎn)分析(AP2)固定大小參考搜索窗口的不足：7種不同大小的塊都在固定大小的參考窗口中搜索最佳匹配塊是不科學(xué)的，根據(jù)“中心偏移特性”和“非中心偏移特性”理論，7種塊大小不同而且運(yùn)動(dòng)矢量大小也不一樣，比如對(duì)4*4小塊勢(shì)必會(huì)增加一些無用點(diǎn)的搜索；而對(duì)16*16的大塊可能由于運(yùn)動(dòng)比較劇烈而在固定大小的窗口中無法找到最佳匹配的塊.中心偏移特性news序列80以上的運(yùn)動(dòng)矢量分布在中心位置，且偏移比較小，大部分矢量分布

11、在4，4的范圍內(nèi) .非中心偏移特性News_qcifUMHS算法描述及可優(yōu)化點(diǎn)分析(AP2):_Bprpsd DSRfixed part dinamic part優(yōu)化方法(AP2)：用動(dòng)態(tài)搜索窗口代替固定大小窗口AP2動(dòng)態(tài)搜索窗口(DSR)的計(jì)算 ()xxmvxdabs MVPuplayerMVPmedian()yymvydabs MVPuplayerMVPmedian:_max(,)Ddinamicpartmvxd mvyd:_(_)/8Cfixed partinput search range原算法固定大小搜索窗口動(dòng)態(tài)搜索窗口大小定值搜索窗口大小BCD（2*search_range + 1

12、）UMHS算法描述及可優(yōu)化點(diǎn)分析(AP3)(3)能否縮定搜索象限？分析:非均勻多層次六邊形格搜索點(diǎn)數(shù)(a)：N1 = 16*4 = 64 擴(kuò)展的六邊形搜索，搜索點(diǎn)數(shù)(b)：N2 = 7 + 3*n + 4 (a)(b)UMHS算法描述及可優(yōu)化點(diǎn)分析(AP3)優(yōu)化(AP3)：利用運(yùn)動(dòng)矢量(med_mv)和運(yùn)動(dòng)矢量(col_mv)的夾角a大小了優(yōu)化. a = 0 to 90a = 90 to 180a = 180 to 270 a = 270 to 360N1 = 16*4 = 64N2 = 7+3*n+4搜索點(diǎn)數(shù)變化N1 = 4*5 = 20 N2=7+2*n+4UMHS算法描述及可優(yōu)化點(diǎn)分析(

13、AP4)(4)小六邊形(菱形)搜索點(diǎn)數(shù)目是否可以減少？(a)(b)原算法不足：匹配精度有待提高，可以進(jìn)一步優(yōu)化UMHS算法描述及可優(yōu)化點(diǎn)分析(AP4)(a)優(yōu)化(AP4)：利用全局最小周圍的單調(diào)失真特性，使得內(nèi)部點(diǎn)搜索(inner search)只需要搜索一個(gè)特定方向的內(nèi)部點(diǎn)(inner points)。MinSadGroup1, Group2,Group3, Group4, Group5, Group6, 其中Group2和Group5需要搜索三個(gè)點(diǎn)，如圖a所示，Group1，Group3, Group5, Group6需要搜索兩個(gè)點(diǎn)，如圖b所示.UMHS算法描述及可優(yōu)化點(diǎn)分析(AP4)優(yōu)化

14、效果：Group分組分別減少1或者2個(gè)搜尋點(diǎn)，所以大約減少了2*(4/6) + 1*(2/6) = 1.67個(gè)點(diǎn)，因?yàn)槭敲總€(gè)搜索塊都減少了大約1.67個(gè)點(diǎn)，所以一個(gè)frame就減少了相當(dāng)多的搜尋點(diǎn)，自然其速度比六邊形搜索算法快很多。而整個(gè)搜索算法的搜索總點(diǎn)數(shù)為 7 + 3*n + (2, 3) (b)UMHS算法描述及可優(yōu)化點(diǎn)分析(軟件實(shí)現(xiàn)流程)總結(jié)：對(duì)HUMS算法進(jìn)行了AP1,AP2,AP3,AP4四個(gè)方面的優(yōu)化，優(yōu)化后的算法與原算法(HUMS)在總體流程上沒有發(fā)生變化，只是在不同的搜索步驟中進(jìn)行了優(yōu)化，使得整個(gè)算法更加高效，自適應(yīng)性更好，匹配速度和精度極大的提高，實(shí)時(shí)性更好 實(shí)驗(yàn)結(jié)果與性能

15、分析(視頻質(zhì)量的主觀評(píng)定視頻質(zhì)量的主觀評(píng)定)A:A:為原始圖象為原始圖象B:B:為編碼解碼為編碼解碼后的圖象后的圖象CCIR CCIR 五級(jí)評(píng)分等級(jí)五級(jí)評(píng)分等級(jí)評(píng)分等級(jí)評(píng)分等級(jí)高清晰度采用七級(jí)評(píng)分等級(jí)高清晰度采用七級(jí)評(píng)分等級(jí)評(píng)價(jià)評(píng)價(jià)7 7不能覺察任何圖像損傷不能覺察任何圖像損傷特別好特別好6 6剛能覺察有圖像損傷剛能覺察有圖像損傷相當(dāng)好相當(dāng)好優(yōu)優(yōu)5 5不同程度的覺察，輕度損傷不同程度的覺察，輕度損傷很好很好好好4 4有損傷，但不令人討厭有損傷，但不令人討厭好好稍差稍差3 3有令人討厭損傷有令人討厭損傷稍差稍差很差很差2 2損傷令人討厭，但尚可忍受損傷令人討厭，但尚可忍受很差很差劣劣1 1非常令

16、人討厭損傷，無法觀看非常令人討厭損傷，無法觀看劣劣主觀評(píng)價(jià)分?jǐn)?shù)標(biāo)準(zhǔn)主觀評(píng)價(jià)分?jǐn)?shù)標(biāo)準(zhǔn) DSCQSDSCQS測(cè)試系統(tǒng)測(cè)試系統(tǒng) 源視頻源視頻序列序列視頻視頻編碼器編碼器視頻視頻解碼器解碼器顯示顯示BA實(shí)驗(yàn)結(jié)果與性能分析(視頻質(zhì)量的客觀評(píng)定視頻質(zhì)量的客觀評(píng)定)最常用的測(cè)試標(biāo)準(zhǔn)是峰值信號(hào)與噪聲之比（PSNR）均方誤差（MSE）:(i, j)為運(yùn)動(dòng)矢量(MV);(22 - 1)2為圖像種最大可能的信號(hào)值平方;n為表示每個(gè)像素的比特?cái)?shù)21010log (21) /nPSNRMSE一般講，PSNR 愈高視頻質(zhì)量愈高；反之亦然21111( , )( , )(,)MNttxyMSE i jf x yfxi yjM

17、N實(shí)驗(yàn)結(jié)果與性能分析(測(cè)試平臺(tái)及其配置)Intel(R) Pentium(R) D CPU 3.00GHz，512M內(nèi)存。WindowsXP 2002+SP2。測(cè)試序列集為5個(gè) QCIF(176*144)格式序列所有序列yuv4:2:0實(shí)驗(yàn)結(jié)果與性能分析（客觀分析 ）(a)不同紋理復(fù)雜程度(b)不同運(yùn)動(dòng)劇烈程度選用原則實(shí)驗(yàn)結(jié)果與性能分析（客觀分析 ）Mobile_qcif序列總結(jié)及展望（主觀評(píng)價(jià) ）(a)原始幀 右圖(a)給出了news_qcif序列原始幀 ，(b)和(c)分別是UMHS算法和本文優(yōu)化算法得到的解碼幀。 總結(jié)及展望（主觀評(píng)價(jià) ）(b) UMHS解碼幀 (c) 本文優(yōu)化后解碼幀

18、總結(jié)及展望（結(jié)論）實(shí)驗(yàn)結(jié)果表明：與原UMHS搜索算法相比，優(yōu)化后算法的優(yōu)勢(shì)還是很明顯的 ，從客觀視頻質(zhì)量評(píng)估標(biāo)準(zhǔn)來看，節(jié)省了運(yùn)動(dòng)估計(jì)(ME)時(shí)間(平均18.102%)，在保證視頻性能相對(duì)高的前提下，大大降低了運(yùn)算復(fù)雜度，提高了編碼速度。從主觀評(píng)價(jià)標(biāo)準(zhǔn)來看，算法在提高了編碼速度的同時(shí)，可以較好地保持原有的率失真特性。綜合評(píng)價(jià)指標(biāo):(1)圖象質(zhì)量高(PSNR大)(2)編碼(運(yùn)動(dòng)估計(jì))時(shí)間短(實(shí)時(shí)性好)(3)碼率低(壓縮比大，方便存儲(chǔ)和傳輸)總結(jié)及展望（下一步計(jì)劃）(1)研究幀內(nèi)模式選擇、碼率控制、熵編碼等方面的優(yōu)化方法 (2)以H.264擴(kuò)展檔次和主要檔次為研究重點(diǎn)，分析編碼器中涉及到的主要技術(shù)，

19、如加權(quán)預(yù)測(cè)、SP幀與SI幀的編解碼過程等等。(3)基于DSP的編解碼軟件實(shí)現(xiàn). 在熟悉一款DSP(Ti C6000系列)芯片硬件架構(gòu)和開發(fā)環(huán)境(CCS3.3)的基礎(chǔ)上，完成H.264編解碼器代碼的移植和優(yōu)化，即研究如何在DSP上實(shí)現(xiàn)H.264的實(shí)時(shí)編解碼技術(shù) 總結(jié)及展望（下一步計(jì)劃）攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文 白世軍，吳曉軍. H.264/AVC頻編碼運(yùn)動(dòng)估計(jì)算法的優(yōu)化. 電子學(xué)報(bào).2008(09) (外審).感謝各位專家！感謝各位專家！補(bǔ)充材料(實(shí)例)(1)確定搜索起始點(diǎn)(MVEx,MVEy)(2search_range+1)(2search_range+1)，其中s=16/32/64最佳匹配塊當(dāng)前塊當(dāng)前塊補(bǔ)充材料(UMHS算法搜索步驟