王玉松,趙 明
(清華大學(xué) 電子工程系,北京 100084)
H.264/AVC[1]引入了幀內(nèi)預(yù)測(cè)算法以提高幀內(nèi)編碼效率,但算法復(fù)雜度較高,使得幀內(nèi)編碼速度變慢,影響了H.264/AVC的實(shí)際應(yīng)用。因此,研究更簡(jiǎn)單快速的算法以便廣泛應(yīng)用,即在編碼質(zhì)量影響不大,保持原有編碼結(jié)構(gòu)和碼率的情況下,降低算法復(fù)雜度,提高編碼速度,就成了編碼研究的熱點(diǎn)[2]。
在眾多快速幀內(nèi)編碼的研究中,如在文獻(xiàn)[3]中,F(xiàn).Pan等利用了邊緣map來獲得邊緣的強(qiáng)度和方向,大大減少了預(yù)測(cè)模式個(gè)數(shù),此算法已經(jīng)在JM6中實(shí)現(xiàn)。在文獻(xiàn)[4-5]中將4×4塊化為2×2塊,進(jìn)行各個(gè)方向的濾波,選擇其中最大的作為邊緣方向的預(yù)測(cè),減小了模式預(yù)測(cè)個(gè)數(shù),提高了預(yù)測(cè)速度。
通過對(duì)圖像邊緣特性的統(tǒng)計(jì)分析發(fā)現(xiàn),在邊緣方向上的像素具有相近的灰度,它們之間具有很強(qiáng)的連續(xù)的相關(guān)度,而不在邊緣方向的像素很少具有這一特性。所以筆者充分利用了這一特性,計(jì)算相應(yīng)模式方向的相關(guān)度,然后選擇其中較小的幾個(gè)模式作為候選的預(yù)測(cè)模式,從而減小了預(yù)測(cè)模式的數(shù)量。由于本算法與其他快速算法獨(dú)立,在與其他算法結(jié)合使用時(shí),將會(huì)進(jìn)一步提高編碼速度。
根據(jù)H.264/AVC相關(guān)標(biāo)準(zhǔn)可知,在H.264/AVC幀內(nèi)編碼模式選擇時(shí),全搜索算法總共需要進(jìn)行的RDO計(jì)算復(fù)雜度為:N=4×(9×16+4)=592,N 為搜索次數(shù)。 在 4×4 幀內(nèi)編碼預(yù)測(cè)模式中,共有9種方向的預(yù)測(cè)。目前采用的快速算法很多,筆者僅選取其中具有代表性的2種作分析。
在文獻(xiàn)[3]中,通過梯度Sobel算子計(jì)算來獲得宏塊邊緣信息的map,這個(gè)map包含了邊緣方向和邊緣強(qiáng)度,通過這個(gè)map來計(jì)算它的每個(gè)方向的邊緣強(qiáng)度。兩個(gè)方向的計(jì)算,具體見文獻(xiàn)[3]。
選取其中值最大的3種方向模式,再加DC直流模式共4個(gè)模式作為候選模式。
文獻(xiàn)[3]算法的模式復(fù)雜度為:Nmax=3×(4×16+2)=198;Nmin=2×(4×16+2)=132。復(fù)雜度降低了 66.6%~77.7%。文獻(xiàn)[3]算法在計(jì)算中采用了3×3的矩陣,只能用3×3的塊,但是為與下面的算法比較,即都以16個(gè)3×3即12×12大小的塊作比較,所以該算法的計(jì)算復(fù)雜度如表1所示。
很明顯該算法在速度上確實(shí)有大幅提升,但是碼率比FS有了一定的增長(zhǎng),PSNR也有些提高。所以碼率和PSNR損失較高是本算法的一個(gè)弱點(diǎn)。而在算法的開銷上,由于它包含的乘法、除法、函數(shù)運(yùn)算,使它在FPGA等實(shí)現(xiàn)時(shí)開銷很大,這確實(shí)是應(yīng)用中的弱點(diǎn)。
表1 文獻(xiàn)[3]算法的運(yùn)算量統(tǒng)計(jì)
在文獻(xiàn)[4]中,首先將宏塊化為一個(gè)2×2的新塊,然后對(duì)其中4個(gè)新像素塊進(jìn)行預(yù)測(cè)方向的濾波,每個(gè)方向的濾波選用不同的濾波算子,具體計(jì)算見文獻(xiàn)[4]。
選擇其中值較大的作為邊緣預(yù)測(cè)的候選模式,這里每種模式代表相應(yīng)的4種預(yù)測(cè)模式。Snd為除其他4種模式外的一種模式,如果是此模式,則選擇所有9種模式計(jì)算,文獻(xiàn)[4]算法的復(fù)雜度為:Nmax∶2×(9×16+2)=292;Nmin∶2×(4×16+2)=132。 復(fù)雜度降低了 49.3%~77.7%。
文獻(xiàn)[4]算法運(yùn)用了濾波。為了與其他算法比較,使用了9個(gè)4×4的塊即12×12大小的塊,所以文獻(xiàn)[4]算法的計(jì)算復(fù)雜度如表2所示。
表2 文獻(xiàn)[4]算法的運(yùn)算量統(tǒng)計(jì)
在PSNR上文獻(xiàn)[4]算法比文獻(xiàn)[3]算法提高了近10倍,碼率也下降了1%左右,所以文獻(xiàn)[4]算法的優(yōu)勢(shì)是PSNR提高比較明顯,不過碼率還是偏高。同樣在算法開銷上,它也包含了大量的乘法和除法,這使得FPGA等實(shí)現(xiàn)的復(fù)雜度不小,這也是該算法的弱點(diǎn)。
為了達(dá)到全面準(zhǔn)確地了解宏塊的邊緣特性,減少誤判等造成的PSNR損失和碼率上升,充分利用了邊緣處相鄰像素相關(guān)的特性。筆者對(duì)每種模式方向的相關(guān)度,采用相鄰像素間相關(guān)度的MAD之和來評(píng)判這種模式的總體相關(guān)度,由于相關(guān)性越大,那么它們的差值MAD就小,反之MAD值就大。所以最后選擇其中值較小的幾個(gè)模式作為候選的預(yù)測(cè)模式,從而減小了模式預(yù)測(cè)的數(shù)量。
對(duì)于一個(gè)4×4塊的預(yù)測(cè),首先將它按照各個(gè)模式方向,計(jì)算相應(yīng)方向的相關(guān)度,如圖1所示。
圖1 4×4塊模式預(yù)測(cè)相關(guān)度計(jì)算示意圖
各個(gè)方向的MAD的計(jì)算如下:
1)水平(M1)
2)垂直(M0)
3)對(duì)角下(M3)
4)對(duì)角上(M4)
根據(jù)預(yù)測(cè)方向的對(duì)稱性,充分利用已計(jì)算的方向值,其他幾個(gè)方向可以通過其相鄰方向組合計(jì)算出來,而不需要按先前的方法計(jì)算。例如,水平上(M8):MAD22.5=(MAD0+MAD45)/2。 其他模式方向 67.5°,112.5°,157.5°計(jì)算類似。上面公式中的差值為相鄰像素間的MAD值,由于邊緣處像素相近,它們的相關(guān)性大,這樣其差值就小。同樣如果像素不在邊緣處,它們的相關(guān)性就小,結(jié)果是它們的差值就大。選擇其中MAD值最小的3種模式,再加1個(gè)總是被選擇的DC直流模式,共4個(gè)模式作為候選的預(yù)測(cè)模式。
對(duì)16×16的亮度塊,將一個(gè)16×16塊化為16個(gè)4×4的a塊,再將每個(gè)塊下面4×4像素子塊b的16個(gè)像素的總和作為a塊的像素值
a塊其他像素值計(jì)算類似。
對(duì)8×8的色度塊,也是先化為4個(gè)4×4的a塊,再將每個(gè)塊用其中2×2子塊的4個(gè)像素值的總和作為a塊的像素值。
16×16的亮度塊和8×8的色度塊的a塊的相關(guān)度計(jì)算類似4×4的亮度塊,然后都選用其中值最小的方向模式和常選DC直流模式共2種模式,作為候選的預(yù)測(cè)模式。
在預(yù)測(cè)模式選擇上, 本算法復(fù)雜度為:2×(4×16+2)=132,復(fù)雜度降低了77.7%。算法在模式的預(yù)測(cè)上,總是使用最少的模式,模式的復(fù)雜度減少到最大為77.7%,而其他算法都有不同程度降低。
為了與其他算法比較,用了9個(gè)4×4的塊即12×12大小的塊,所以本算法的計(jì)算復(fù)雜度如表3所示。
表3 改進(jìn)算法的運(yùn)算量統(tǒng)計(jì)
與其他算法相比,可以發(fā)現(xiàn)本算法沒有使用復(fù)雜度高的乘法和函數(shù),所以計(jì)算的復(fù)雜度比其他算法低。本算法由于復(fù)雜度較低,規(guī)律性強(qiáng),所以能夠在FPGA等上很好地實(shí)現(xiàn)并行計(jì)算。
在JM10的代碼基礎(chǔ)上進(jìn)行實(shí)驗(yàn),使用了JM10的相關(guān)測(cè)試模型。其編碼特性分別在QP為28,32,36,40下獲得,其中的 ΔPSNR,Δt,ΔRbit為相應(yīng)算法與 JM10.0 中基于RDO的FS算法比較所得的差值。具體見表4~5和及圖2~3。
圖2 News序列的RD曲線
圖3 Mobile序列的RD曲線
從測(cè)試中可以發(fā)現(xiàn),改進(jìn)后的算法比文獻(xiàn)[3]與文獻(xiàn)[4]的快速算法在速度上都有6%~10%的提高,比文獻(xiàn)[3]算法碼率下降了1.5%,PSNR提高了5倍,比文獻(xiàn)[4]算法的碼率也有一定降低。與FS相比,PSNR基本保持不變,CIF序列的速度平均提高了65.98%,碼率平均只提高了2%;對(duì)于QCIF序列,速度平均提高67.07%,其碼率平均也只提高了2%??梢钥闯觯舅惴ㄅc其他快速算法相比,速度、碼率、PSNR都有了不同程度的改善,效果是明顯的。
筆者提出了一種H.264/AVC幀內(nèi)編碼的快速算法,它利用宏塊邊緣處像素具有很強(qiáng)的相關(guān)度特性,通過計(jì)算在各個(gè)預(yù)測(cè)方向的相關(guān)度值,選擇其中最小的幾個(gè)值作為候選的預(yù)測(cè)模式,降低了模式預(yù)測(cè)的復(fù)雜度。實(shí)驗(yàn)結(jié)果證明,本算法比H.264/AVC算法有了66%左右的提高,而PSNR基本保持不變,與其他算法[2-3]相比都有不同程度的性能提高。由于本算法計(jì)算復(fù)雜度比較低,能夠很好地適用于VLSI的實(shí)現(xiàn)。
表4 采用QCIF序列3種算法的性能比較
表5 采用CIF序列3種算法的性能比較
[1]Joint Video Team of ISO/IEC MPEG&ITUT VCEG.ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec.H.264 ISO/IEC 14496-10 AVC)[S].2003.
[2]王海勇,孫雁飛,吳啟宗.H.264編碼中幀內(nèi)預(yù)測(cè)算法研究[J].電視技術(shù),2009,33(8):11-12.
[3]PAN F,LIN X,RAHARDJA S,et al.Fast mode decision algorithm for intra prediction in H.264/AVC video coding[J].IEEE Trans.Circuits and Syst.Video Technol.,2005,15(7):813-822.
[4]WANG J F,WANG J C,CHEN J T,et al.A novel fast algorithm for intra mode decision in H.264/AVC Encoders[C]//Proc.2006 IEEE Int.Symp.Circuit Syst.Island of Kos,Greece:IEEE Press,2006:3498-3501.
[5]TSAI A,WANG J,LIN W,et al.A simple and robust direction detection algorithm for fast H.264 intra prediction[C]//Proc.2007 IEEE International Conference on Multimedia and Expo.[S.l.]:IEEE Press,2007:1587-1590.