HEVC幀內(nèi)預(yù)測(cè)快速算法研究

摘 要：HEVC （High Efficiency Video Coding）于2010年由JCT-VC制定，并于2013年正式發(fā)布。相比H.264/AVC，在相同圖像質(zhì)量下HEVC相比AVC能得到更高的壓縮率，但是同時(shí)也帶來(lái)了編碼工具復(fù)雜度的提升。以幀內(nèi)預(yù)測(cè)為例，AVC幀內(nèi)預(yù)測(cè)包括9種4x4和4種16x16共13種幀內(nèi)預(yù)測(cè)。HEVC每一個(gè)預(yù)測(cè)單元存在35個(gè)預(yù)測(cè)方向。因此降低幀內(nèi)預(yù)測(cè)算法的復(fù)雜度成為HEVC編碼研究的熱點(diǎn)。本文主要針對(duì)HEVC粗略模式選擇（RMD，Rough Mode Decision）和率失真優(yōu)化計(jì)算（RDO，Rate Distortion Optimization）過(guò)程中候選模式個(gè)數(shù)較多的問(wèn)題進(jìn)行研究與優(yōu)化，在保證壓縮率的前提下盡量減少計(jì)算量。

關(guān)鍵詞：HEVC;幀內(nèi)預(yù)測(cè);模式選擇

1.引言

方向預(yù)測(cè)（angular intra prediction）因其較低的實(shí)現(xiàn)復(fù)雜度以及相對(duì)高效的編碼增益，成為多項(xiàng)國(guó)際視頻標(biāo)準(zhǔn)（如H.264/AVC，VP9，AVS1，HEVC，VVC等）中的關(guān)鍵編碼技術(shù)。HEVC作為新一代視頻編碼標(biāo)準(zhǔn)，具備更好的視頻壓縮性能、能夠滿足更多的應(yīng)用場(chǎng)景。HEVC相比AVC能提升大約50%的壓縮率[1]。但同時(shí)由于編碼工具復(fù)雜度的提升也帶來(lái)了算法實(shí)時(shí)性與算法計(jì)算量之間的巨大矛盾，特別是算法復(fù)雜度的提升，極大的提高了SOC設(shè)計(jì)的成本。在幀內(nèi)預(yù)測(cè)方面，每個(gè)預(yù)測(cè)單元存在35個(gè)預(yù)測(cè)方向，且CU向下劃分以后，每個(gè)CU又有35個(gè)預(yù)測(cè)方向，因此對(duì)整體計(jì)算量的優(yōu)化有著迫切的需求。

HEVC的幀內(nèi)預(yù)測(cè)從預(yù)測(cè)模式上包括了0～34一共35個(gè)預(yù)測(cè)模式。其中0表示Planar模式，1表示DC模式，2～34表示33個(gè)方向預(yù)測(cè)模式[2]。

HEVC的幀內(nèi)預(yù)測(cè)的CU尺寸和個(gè)數(shù)可以簡(jiǎn)單的描述如下：一個(gè)64x64的CU，如果進(jìn)行深度為四的劃分的話，一共會(huì)形成4^0+4^1+4^2+4^3=85個(gè)CU，深度遍歷四叉樹的每個(gè)節(jié)點(diǎn)，對(duì)四叉樹上每個(gè)節(jié)點(diǎn)的CU進(jìn)行幀內(nèi)預(yù)測(cè)，計(jì)算總量相當(dāng)龐大。

2 普通的幀內(nèi)預(yù)測(cè)方法

HEVC普通幀內(nèi)預(yù)測(cè)方法，是在每個(gè)CU內(nèi)，先對(duì)35個(gè)預(yù)測(cè)模式進(jìn)行粗搜，粗搜索結(jié)果選擇N（N一般選2～3）個(gè)模式，然后進(jìn)行精搜，確定當(dāng)前CU的最佳編碼模式。

粗搜結(jié)果一般采用SAD或者SATD作為評(píng)價(jià)標(biāo)準(zhǔn)。在每個(gè)CU遍歷35個(gè)預(yù)測(cè)模式，每個(gè)模式根據(jù)幀內(nèi)預(yù)測(cè)的公式計(jì)算預(yù)測(cè)值，然后計(jì)算預(yù)測(cè)值與原始像素的差值的平方和（SAD），或者計(jì)算預(yù)測(cè)值與原始像素的差值先進(jìn)行hadamard變換后再絕對(duì)值求和得到SATD。當(dāng)SAD或者SATD越大，表示預(yù)測(cè)與原始像素之間的差異越大，所以最終選用SAD或者SATD最小的N個(gè)模式作為粗選的結(jié)果。SAD和SATD的區(qū)別是，SAD作為評(píng)價(jià)標(biāo)準(zhǔn)的優(yōu)點(diǎn)是計(jì)算量較小，但僅僅反映殘差空域差異，影響PSNR值，不能有效反映碼流的大小。SATD計(jì)算量相對(duì)SAD較大，但是作為一種簡(jiǎn)單的二維變換，SATD不但體現(xiàn)了空域差異，而且反映了頻率的差異。所以其值在一定程度上可以比SAD更能反映生成碼流的大小。

精搜一般采用率失真計(jì)算，除了考慮PSNR，還需要考慮預(yù)測(cè)方向存儲(chǔ)和CU的四叉樹劃分時(shí)候需要消耗的bit，也就是考慮了整體的壓縮率。

普通的幀內(nèi)預(yù)測(cè)的缺點(diǎn)：粗搜需要遍歷35種模式，如果是單通道計(jì)算一個(gè)模式，計(jì)算總時(shí)長(zhǎng)太長(zhǎng)，實(shí)時(shí)性較難得到滿足。如果并行35個(gè)模式進(jìn)行計(jì)算，所需要的硬件成本較大?？偠灾?jì)算量太大，不利于工程實(shí)現(xiàn)。

3 改進(jìn)的幀內(nèi)預(yù)測(cè)方法

鑒于普通的幀內(nèi)預(yù)測(cè)方法天然的存在計(jì)算量太大的不足，難以在工程中實(shí)現(xiàn)，有必要針對(duì)性的改進(jìn)上述方法。本文在上述方法的基礎(chǔ)上，提出了兩點(diǎn)改進(jìn)方案，第一，在粗搜之前增加一級(jí)預(yù)搜索，粗略估計(jì)預(yù)測(cè)模式，可以把粗搜所需要計(jì)算的模式從35個(gè)減少到12個(gè)。第二，在進(jìn)行粗搜的時(shí)候，如果CU尺寸為64x64，32x32或者16x16的時(shí)候，可以采用下采樣后再粗搜的方式，進(jìn)行粗搜。8x8和4x4的由于原始CU尺寸太小，不適合進(jìn)行下采樣。兩種方式結(jié)合，粗搜計(jì)算量可以減少到原先的10%。經(jīng)過(guò)仿真該改進(jìn)方案對(duì)壓縮率影響有限。

預(yù)搜索的原理如下描述：采用的預(yù)搜索算法是基于圖像內(nèi)容的搜索，采用梯度算子對(duì)圖像數(shù)據(jù)進(jìn)行處理，得到幀內(nèi)預(yù)測(cè)的大致方向，然后增加DC和Plannar模式，組成粗搜列表進(jìn)行粗搜。梯度算子可以采用Sobel算子。Sobel算子是一種一階的微分算子，可以用于圖像的線的檢測(cè)，通常用于圖像邊緣檢測(cè)中。

對(duì)一幅圖像分別用3x3的Sobel算子進(jìn)行卷積，所用的Sobel算子如圖1所示：

以一個(gè)8x8的CU的計(jì)算為例。假設(shè)8x8的CU原始圖像如圖2所示，圖中深藍(lán)色的數(shù)據(jù)a00～a77表示當(dāng)前需要計(jì)算的CU，旁邊一圈表示該CU的鄰邊的CU的原始圖像數(shù)據(jù)。如果CU處于圖像邊界，鄰邊數(shù)據(jù)可以用當(dāng)前CU的原始邊界數(shù)據(jù)填充。b表示上邊界，c表示左邊界的數(shù)據(jù)，d表示右邊界的數(shù)據(jù)，e表示下邊界，f，g，h，k分別表示左上，右上，左下，右下的CU的邊界數(shù)據(jù)。

當(dāng)前CU經(jīng)過(guò)矩陣計(jì)算的規(guī)則描述如下，以a11像素計(jì)算為例，a11與矩陣C計(jì)算結(jié)果的像素表示為aC11，aC11 = a01+2*a02-a10+a12-2* a20-a21。

計(jì)算后得到矩陣aC如圖3所示。將矩陣aC每個(gè)像素絕對(duì)值累加求和得到abs（aC），相同的計(jì)算方法可以得到abs（aA）， abs（aB）和abs（aD）。找出這4個(gè)值中最小的兩個(gè)值，如果夾角是90°，則可以得到預(yù)搜索的結(jié)果，如果夾角是180°，則證明這個(gè)CU不能得到準(zhǔn)確的結(jié)果，采用一組默認(rèn)的模式作為預(yù)搜索的結(jié)果。

預(yù)搜索結(jié)果如表1所示：

當(dāng)矩陣A和矩陣C的結(jié)果最小的時(shí)候，選中模式2的主要原因是，上文所述的計(jì)算雖然考慮了方向，但是由于最終用絕對(duì)值進(jìn)行評(píng)測(cè)，因此對(duì)180°的角度是模糊的，為了避免計(jì)算誤差導(dǎo)致的錯(cuò)誤，增加了模式2。同理，在矩陣B和矩陣C的結(jié)果最小的時(shí)候，也增加了模式34。當(dāng)絕對(duì)值累加最小的兩個(gè)矩陣所代表夾角是180°的時(shí)候，表示計(jì)算結(jié)果不夠理想，輸出的候選模式采用每3個(gè)角度選擇1個(gè)角度。另外每組都增加模式0和模式1。粗選的結(jié)果控制在12個(gè)模式以內(nèi)。

CU16X16，CU32X32和CU64X64的計(jì)算方法相似。

粗搜索的優(yōu)化方法如下描述：以一個(gè)CU32X32為例，CU32在水平和垂直方向都進(jìn)行2抽1的抽?。ň禐V波），結(jié)果得到一個(gè)8X8的矩陣。矩陣中的每個(gè)值由原來(lái)CU32X32中2X2的4個(gè)像素均值下采樣得到。根據(jù)CU32X32的邊數(shù)據(jù)得到8X8矩陣所需要的邊數(shù)據(jù)，對(duì)8X8矩陣進(jìn)行幀內(nèi)預(yù)測(cè)，并計(jì)算相應(yīng)的SAD或者SATD。預(yù)搜索的12個(gè)模式可以通過(guò)粗搜索選擇較好的2～3個(gè)模式進(jìn)行最終的精搜索。優(yōu)化前的粗搜索示意圖如圖4所示。優(yōu)化后的粗搜索示意圖如圖5所示。

圖5中的像素值計(jì)算方法如下：

矩陣N采用預(yù)搜索的模式進(jìn)行預(yù)測(cè)，并計(jì)算SAD或者SATD可以得到用于精搜索的模式。

4 改進(jìn)前后的整體效果仿真

改進(jìn)前后的編碼效果及其壓縮率的仿真測(cè)試方法如下：采用10個(gè)標(biāo)準(zhǔn)測(cè)試片源[3][4]，用QP30 QP35 QP40 QP45進(jìn)行仿真，測(cè)試輸出碼流的PSNR與碼流的大小，擬合PSNR的曲線如圖6所示：

從圖中可以看出，改進(jìn)后由于精簡(jiǎn)了計(jì)算量，整體效果跟改進(jìn)前相比差了一點(diǎn)點(diǎn)。但是跟優(yōu)化的計(jì)算量相比，這部分性能差距是可以接受的。

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

本文通過(guò)對(duì)幀內(nèi)預(yù)測(cè)的一些算法的改進(jìn)，達(dá)到了減少幀內(nèi)預(yù)測(cè)復(fù)雜度，達(dá)到幀內(nèi)預(yù)測(cè)算法的實(shí)時(shí)性的要求。后續(xù)可以考慮其他梯度算子或者下采樣方法評(píng)估計(jì)算性能。甚至可以采用5階的梯度算子，把預(yù)搜索的模式的角度限制在23°以內(nèi)（45°的一半），可以更加有效的減少粗搜索的模式。

參考文獻(xiàn)

[1]吳明.關(guān)于HEVC幀內(nèi)預(yù)測(cè)快速模式選擇算法的研究.南京理工大學(xué).2014.

[2]萬(wàn)帥 楊付正.新一代高效視頻編解碼 H.265/HEVC：原理、標(biāo)準(zhǔn)與實(shí)現(xiàn).電子工業(yè)出版設(shè).2014

[3]https：//media.xiph.org/video/derf/

[4]http：//trace.eas.asu.edu/yuv/index.html

作者簡(jiǎn)介：張毅敏，男，1981年生，碩士，主要研究領(lǐng)域?yàn)橐曨l編解碼。