基于邊緣檢測(cè)的幀內(nèi)預(yù)測(cè)快速算法

王玉松，趙 明

（清華大學(xué) 電子工程系，北京 100084）

1 引言

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來(lái)獲得邊緣的強(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è)速度。

通過(guò)對(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)一步提高編碼速度。

2 快速算法的分析

根據(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種作分析。

2.1 F.Pan等的快速算法[3]

在文獻(xiàn)[3]中，通過(guò)梯度Sobel算子計(jì)算來(lái)獲得宏塊邊緣信息的map，這個(gè)map包含了邊緣方向和邊緣強(qiáng)度，通過(guò)這個(gè)map來(lái)計(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ì)

2.2 Jhing-Fa Wang等的快速算法[4]

在文獻(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提高比較明顯，不過(guò)碼率還是偏高。同樣在算法開銷上，它也包含了大量的乘法和除法，這使得FPGA等實(shí)現(xiàn)的復(fù)雜度不小，這也是該算法的弱點(diǎn)。

3 基于宏塊邊緣方向的快速算法

為了達(dá)到全面準(zhǔn)確地了解宏塊的邊緣特性，減少誤判等造成的PSNR損失和碼率上升，充分利用了邊緣處相鄰像素相關(guān)的特性。筆者對(duì)每種模式方向的相關(guān)度，采用相鄰像素間相關(guān)度的MAD之和來(lái)評(píng)判這種模式的總體相關(guān)度，由于相關(guān)性越大，那么它們的差值MAD就小，反之MAD值就大。所以最后選擇其中值較小的幾個(gè)模式作為候選的預(yù)測(cè)模式，從而減小了模式預(yù)測(cè)的數(shù)量。

3.1 4×4塊的快速預(yù)測(cè)

對(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è)方向可以通過(guò)其相鄰方向組合計(jì)算出來(lái)，而不需要按先前的方法計(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è)模式。

3.2 16×16亮度塊和8×8色度塊的預(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è)模式。

3.3 算法的復(fù)雜度分析

在預(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)本算法沒(méi)有使用復(fù)雜度高的乘法和函數(shù)，所以計(jì)算的復(fù)雜度比其他算法低。本算法由于復(fù)雜度較低，規(guī)律性強(qiáng)，所以能夠在FPGA等上很好地實(shí)現(xiàn)并行計(jì)算。

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

在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%。可以看出，本算法與其他快速算法相比，速度、碼率、PSNR都有了不同程度的改善，效果是明顯的。

5 小結(jié)

筆者提出了一種H.264/AVC幀內(nèi)編碼的快速算法，它利用宏塊邊緣處像素具有很強(qiáng)的相關(guān)度特性，通過(guò)計(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.