基于H.264視頻壓縮快速運(yùn)動(dòng)的估計(jì)算法

0 引言

H.264采用了減少視頻圖像各幀間冗余度的運(yùn)動(dòng)估計(jì)算法。運(yùn)動(dòng)估計(jì)算法傳統(tǒng)的有全搜索(FS)、三步搜索(TSS)、新三步搜索(NTSS)、四步搜索(FSS)等;常用的是鉆石搜索(DS)和非對(duì)稱十字交叉多層次六邊形格點(diǎn)運(yùn)動(dòng)搜索算法(UMHexagonS)。運(yùn)動(dòng)估計(jì)是整個(gè)視頻編碼中運(yùn)算量最大的模塊，可占整個(gè)軟件編碼器運(yùn)算量的70%以上。因此視頻系統(tǒng)中編碼器的復(fù)雜部分取決于運(yùn)動(dòng)估計(jì)算法體系結(jié)構(gòu)的復(fù)雜性。

1 運(yùn)動(dòng)估計(jì)算法分析

1.1 鉆石搜索(DS)算法

DS算法即鉆石搜索算法，被MPEG-4國(guó)際標(biāo)準(zhǔn)采用并收入驗(yàn)證模型VM(Verification Model)中，是MPEG-4建議采用的快速運(yùn)動(dòng)估計(jì)算法。 DS算法采用了兩種搜索模板，分別是有9個(gè)檢測(cè)點(diǎn)的大模板和有5個(gè)檢測(cè)點(diǎn)的小模板。搜索時(shí)先用大模板LDSP在搜索區(qū)域中心及周?chē)?個(gè)點(diǎn)處進(jìn)行匹配計(jì)算，當(dāng)最小塊誤差出現(xiàn)在中心點(diǎn)處時(shí)，將大模板LDSP換為SDSP，再進(jìn)行匹配計(jì)算，這時(shí)5個(gè)點(diǎn)中的MBD(Minimum Block Distortion)即為最優(yōu)匹配點(diǎn);否則，改變中心位置，仍用LDSP重復(fù)計(jì)算。

1.2 菱形十字搜索(DCS)算法

菱形十字搜索算法(DCS)算法是在DS算法基礎(chǔ)上改進(jìn)而來(lái)，DCS的匹配模板是建立在兩種不同的搜索模板之上的，即大菱形十字型(LDCSP)和小菱形十字型(SDCSP)，如圖1所示。其中，十字型可以對(duì)應(yīng)于實(shí)際的運(yùn)動(dòng)的矢量分布，而交叉型則是為了加速搜索效果。

DCS算法在進(jìn)行運(yùn)動(dòng)估計(jì)匹配運(yùn)算時(shí)，有三種可能的情況：

(1)若MBD點(diǎn)位于LDCSP中心位置，說(shuō)明圖像是靜止的，DCS算法一步結(jié)束;

(2)若MBD點(diǎn)位于LDCSP小十字位置，說(shuō)明圖像的運(yùn)動(dòng)較小，則在此基礎(chǔ)上按照SDCSP模板反復(fù)進(jìn)行交叉搜索。

(3)若MBD點(diǎn)位于LDCSP大十字位置，說(shuō)明圖像的運(yùn)動(dòng)較大，則在此基礎(chǔ)上按照LDCSP模板反復(fù)進(jìn)行交叉搜索。

由此可以看出，DCS算法的優(yōu)點(diǎn)是，可以根據(jù)圖像的運(yùn)動(dòng)類型(如上述三種情況)，白適應(yīng)選擇下一步相應(yīng)的搜索模板，使搜索與圖像內(nèi)容有關(guān)(基于內(nèi)容的搜索)，從而得到較好的搜索效果；DCS算法的搜索并不一定要經(jīng)歷模板由大到小的必然過(guò)程，有時(shí)一步即可完成搜索；用DCS搜索時(shí)，十字形模板對(duì)應(yīng)于實(shí)際的運(yùn)動(dòng)矢量分布，交叉形模板則有準(zhǔn)確性“聚焦”特性，這從本質(zhì)上體現(xiàn)了DCS是粗定位和準(zhǔn)確定位的有效結(jié)合。

Script type=text/javascript> function ImgZoom(Id)//重新設(shè)置圖片大小防止撐破表格 { var w =
$(Id).width; var m = 650; if(w m){return;} else{ var h = $(Id).height; $(Id).height = parseInt(h*m/w); $(Id).width = m; } } window.onload = function() { var Imgs = $(content).getElementsByTagName(img); var i=0; for(;i
　　
視頻圖像的運(yùn)動(dòng)矢量大部分為零矢量或運(yùn)動(dòng)很小的矢量。運(yùn)動(dòng)矢量為零的塊稱為靜止塊；運(yùn)動(dòng)矢量很小的塊(以搜索窗口中心為圓心，兩像素為半徑的圓內(nèi))稱為準(zhǔn)靜止塊：而其他的稱為運(yùn)動(dòng)塊。如果有超過(guò)80％運(yùn)動(dòng)矢量很小的塊可被看作靜止或準(zhǔn)靜止塊。因此，可設(shè)一個(gè)閥值T，當(dāng)運(yùn)動(dòng)矢量的值小于T時(shí)，可用SDCSP搜索法直接進(jìn)行精確定位，找出最優(yōu)點(diǎn)；當(dāng)運(yùn)動(dòng)矢量的值大于T時(shí)，可用LDCSP搜索算法找出最優(yōu)點(diǎn)。

運(yùn)動(dòng)矢量空間域的預(yù)測(cè)方式有運(yùn)動(dòng)矢量中值預(yù)測(cè)、空間域的上層塊模式運(yùn)動(dòng)矢量；在時(shí)間域的預(yù)測(cè)方式有前幀對(duì)應(yīng)塊運(yùn)動(dòng)矢量預(yù)測(cè)和時(shí)間域的鄰近參考幀運(yùn)動(dòng)矢量預(yù)測(cè)。本文采用運(yùn)動(dòng)矢量中值預(yù)測(cè)方式。根據(jù)與當(dāng)前E塊相鄰的左邊A塊，上邊B塊和右上邊C塊的運(yùn)動(dòng)矢量，取中值作為當(dāng)前塊的預(yù)測(cè)運(yùn)動(dòng)矢量。如圖2所示。

設(shè)當(dāng)前要編碼塊E的運(yùn)動(dòng)矢量為MVp。如果運(yùn)動(dòng)矢量的值MVp≥T，則與E塊相鄰的各塊間運(yùn)動(dòng)的相關(guān)性較高，表明該區(qū)域的變化比較平緩；如果運(yùn)動(dòng)矢量的值MVpT，則與E塊相鄰的各塊間運(yùn)動(dòng)的相關(guān)性較低，表明該區(qū)域變化比較劇烈。通過(guò)對(duì)missa、grandmother、carphone、salesman的檢測(cè)可知，取閾值T=2。

3 自適應(yīng)運(yùn)動(dòng)估計(jì)算法

結(jié)合上述DCS算法和閾值的確定，可采取先對(duì)視頻圖像的運(yùn)動(dòng)塊進(jìn)行閾值的判斷，再根據(jù)判斷結(jié)果進(jìn)行最佳匹配塊的搜索。具體搜索步驟描述如下：

　　Step 1：判斷當(dāng)前塊運(yùn)動(dòng)矢量MVp和閾值確大小。若MVp≥T，則進(jìn)入Step 2；若MVpT，則進(jìn)入Step 5。

　　Step 2：用LDCSP在搜索區(qū)域中心及周?chē)?個(gè)點(diǎn)進(jìn)行匹配運(yùn)算，然后判斷，找出MBD點(diǎn)。若MBD點(diǎn)位于中心點(diǎn)，說(shuō)明宏塊是靜止的，DCS算法一步結(jié)束，得到最優(yōu)匹配塊；否則進(jìn)行Step 3。

　　Step 3：若MBD點(diǎn)為L(zhǎng)DCSP模版的小十字處，以該點(diǎn)為中心構(gòu)建SDCSP進(jìn)行匹配計(jì)算，若MBD點(diǎn)位于中心點(diǎn)，所得MBD點(diǎn)為所求。否則，進(jìn)入Step 4。

　　Step 4：若MBD點(diǎn)為L(zhǎng)DCSP模版的大十字處，以該點(diǎn)為中心構(gòu)建LCSP進(jìn)行匹配計(jì)算，進(jìn)入step 2。

　　Step 5：用LDCSP在搜索區(qū)域中心及周?chē)?個(gè)點(diǎn)進(jìn)行匹配運(yùn)算，然后判斷，找出MBD點(diǎn)。若MBD點(diǎn)位于中心點(diǎn)，所得MBD點(diǎn)為所求；否則繼續(xù)Step 5。

算法流程圖如圖3所示

type=text/javascript> function ImgZoom(Id)//重新設(shè)置圖片大小 防止撐破表格 { var w =$(Id).width; var m = 650; if(w m){return;} else{ var h = $(Id).height;$(Id).height = parseInt(h*m/w); $(Id).width = m; } } window.onload = function(){ var Imgs = $(content).getElementsByTagName(img); var i=0; for(;i4 實(shí)驗(yàn)結(jié)果及說(shuō)明用搜索時(shí)間和PSNR值兩個(gè)指標(biāo)來(lái)驗(yàn)證DCS的性能。本節(jié)實(shí)驗(yàn)用到的所有視頻文件均為QCIF(Quartet commonintermediate format)格式。實(shí)驗(yàn)以主頻1.8GHz的PC機(jī)上運(yùn)行的VisualC++6.0為平臺(tái)。測(cè)試對(duì)象為：missa、salesman、news、grandmother、foreman、carphone、claire，搜索范圍為16×16的矩形框，量化范圍為2～12，測(cè)試序列中每幀圖像的大小為176×144。

4.搜索時(shí)間的比較
為了時(shí)間測(cè)試的準(zhǔn)確性，測(cè)試時(shí)采用的是VC++提供的兩個(gè)精確時(shí)間函數(shù)：QueryPerformanceFrequency()和OuerPerformanceCounter()精度對(duì)標(biāo)準(zhǔn)測(cè)試序列missa、salesman、news、grandmother、foreman、carphone進(jìn)行精確測(cè)定，得表1(數(shù)據(jù)均為三次測(cè)量所求得的平均值)。

實(shí)驗(yàn)結(jié)果及說(shuō)明

用搜索時(shí)間和PSNR值兩個(gè)指標(biāo)來(lái)驗(yàn)證DCS的性能。本節(jié)實(shí)驗(yàn)用到的所有視頻文件均為QCIF(Quartet commonintermediate format)格式。實(shí)驗(yàn)以主頻1.8GHz的PC機(jī)上運(yùn)行的VisualC++6.0為平臺(tái)。測(cè)試對(duì)象為：missa、salesman、news、grandmother、foreman、carphone、claire，搜索范圍為16×16的矩形框，量化范圍為2～12，測(cè)試序列中每幀圖像的大小為176×144。

4.1 搜索時(shí)間的比較

為了時(shí)間測(cè)試的準(zhǔn)確性，測(cè)試時(shí)采用的是VC++提供的兩個(gè)精確時(shí)間函數(shù)：QueryPerformanceFrequency()和OuerPerformanceCounter()精度對(duì)標(biāo)準(zhǔn)測(cè)試序列missa、salesman、news、grandmother、foreman、carphone進(jìn)行精確測(cè)定，得表1(數(shù)據(jù)均為三次測(cè)量所求得的平均值)。

從表1可知：a.FS搜索效果最佳，但耗時(shí)太長(zhǎng)；DS算法有較大改進(jìn)，可以實(shí)現(xiàn)實(shí)時(shí)壓縮；DCS比DS，運(yùn)行時(shí)間都有不同程度的減少，故DCS算法 在搜索速度有優(yōu)勢(shì)。b.從單個(gè)序列來(lái)看，DCS算法對(duì)missa和salesman時(shí)間優(yōu)化最為顯著，分別只占FS算法的7.42％、7.50％和DS算 法的98.17％、97.49％；對(duì)carphone序列的搜索速度也有很大優(yōu)化，占FS搜索算法的7.97％和DS算法的97.82％。綜合視頻特性可 知：DCS算法針對(duì)運(yùn)動(dòng)平緩的視頻對(duì)象搜索速度優(yōu)化明顯。

4.2 信噪比的比較

對(duì)標(biāo)準(zhǔn)測(cè)試序列claire和carphone序列進(jìn)行測(cè)定，計(jì)算PSNR得表2。

表 2中FS的平均PSNR最高，達(dá)到42.38，但搜索時(shí)間最長(zhǎng)；DS的PSNR最低，為42.31，而DCS為42.35，高于DS算法，且僅低于FS算 法0.03dB。從單個(gè)序列來(lái)看，DCS算法對(duì)claire的優(yōu)化程度最大，超過(guò)了FS的PSNR值，說(shuō)明DCS算法身體靜止僅面部表情運(yùn)動(dòng)特點(diǎn)視頻適 用。用DCS算法計(jì)算得到的carphone的PSNR值雖然低于FS算法，但高于DS算法；missa序列的DCS算法的PSNR值和FS、DS法的相 差不大。故DCS算法在搜索速度、圖像質(zhì)量上均有保證。

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

本文從搜索時(shí) 間和圖像質(zhì)量?jī)煞矫鎸?duì)各種塊匹配運(yùn)動(dòng)估計(jì)算法進(jìn)行了性能分析比較。實(shí)驗(yàn)結(jié)果表明，將菱形十字交叉搜索算法和閾值判斷結(jié)合，在搜索速度方面，有很大程度的優(yōu)化，而且能得到與FS、DS搜索算法相當(dāng)?shù)膱D像質(zhì)量。DCS算法針對(duì)運(yùn)動(dòng)平緩的視頻作用明顯，由此推知該算法適用于電視電話、遠(yuǎn)程教育等實(shí)時(shí)視頻壓縮。

...........................................................

與非深度解讀系列:

半導(dǎo)體公司“大學(xué)計(jì)劃”的追問(wèn)和真相

大環(huán)境的不景氣是就業(yè)環(huán)境惡化的元兇，但是也讓我們不禁追問(wèn)半導(dǎo)體公司的大學(xué)計(jì)劃對(duì)于學(xué)子們的真正意義。廠商們的大學(xué)計(jì)劃都在做些什么？那么多的聯(lián)合實(shí)驗(yàn)室有得到充分利用嗎？大學(xué)計(jì)劃的直接體驗(yàn)者--老師和學(xué)生們是否真正從中受益…….【專欄作者：高揚(yáng)】

本土IC公司調(diào)查筆記

全球經(jīng)濟(jì)不景氣的大環(huán)境下一些本土IC公司的創(chuàng)新能力、管理能力、抗風(fēng)險(xiǎn)能力、盈利能力，甚至公司創(chuàng)立的動(dòng)機(jī)都受到一些質(zhì)疑。一方面官方的消息總是告訴我們中國(guó)的半導(dǎo)體產(chǎn)業(yè)得到了長(zhǎng)足的進(jìn)步；而街巷小道中又不絕流傳多少本土IC公司倒閉，多少公司靠欺騙，根本沒(méi)有核心競(jìng)爭(zhēng)力….真相只有一個(gè)，也許會(huì)隨《本土IC公司調(diào)查筆記》慢慢開(kāi)啟…【專欄作者：岳浩】

電子屌絲的技術(shù)人生系列

在這個(gè)系列里，每個(gè)故事都會(huì)向你展示一個(gè)普通工程師的經(jīng)歷，他們的青蔥歲月和技術(shù)年華，和我們每個(gè)人的的生活都有交集。對(duì)自己、對(duì)公司、對(duì)產(chǎn)業(yè)、對(duì)現(xiàn)在、對(duì)未來(lái)、對(duì)技術(shù)、對(duì)市場(chǎng)、對(duì)產(chǎn)品、對(duì)管理的看法，以及他們的經(jīng)歷或正在經(jīng)歷的事情，我們可以看到自己的影子，也看清未來(lái)的樣子……【專欄作者：任亞運(yùn)】

細(xì)說(shuō)電子分銷(xiāo)江湖的那些事

對(duì)于從事電子分銷(xiāo)行業(yè)的同仁們來(lái)說(shuō)這是一個(gè)最壞的年代，也是一個(gè)最好的年代，我們即面臨國(guó)際分銷(xiāo)巨頭在管理、資金、貨源等方面對(duì)我們?cè)斐傻臎_擊，又迎來(lái)本土集成電路的崛起，個(gè)性化服務(wù)盛行的機(jī)遇，通過(guò)這個(gè)系列，我想以“第一現(xiàn)場(chǎng)”的經(jīng)歷帶大家一起了解國(guó)內(nèi)集成電路分銷(xiāo)的那些年、那些事，以及哪些感慨…..【專欄作者：張立恒】

與非網(wǎng)專欄作者申請(qǐng)

聯(lián)系人：高揚(yáng)

郵箱：gaoyang@eefocus.com