??? 摘 要： 提出了一種基于預(yù)測的自適應(yīng)六邊形搜索方法，并將此算法與其他常用的快速運(yùn)動(dòng)估計(jì)" title="運(yùn)動(dòng)估計(jì)">運(yùn)動(dòng)估計(jì)算法進(jìn)行實(shí)驗(yàn)比較。實(shí)驗(yàn)結(jié)果表明：該算法有效地降低了搜索點(diǎn)數(shù)，搜索精度比較接近于FS算法，在一定程度上提高了搜索的效率。
??? 關(guān)鍵詞： 視頻壓縮? 運(yùn)動(dòng)估計(jì)? 快速搜索

?

??? 當(dāng)今時(shí)代，信息技術(shù)和計(jì)算機(jī)互聯(lián)網(wǎng)飛速發(fā)展。為適應(yīng)技術(shù)發(fā)展和應(yīng)用的要求，各種多媒體數(shù)據(jù)壓縮編碼技術(shù)也在不斷發(fā)展中，其中視頻壓縮技術(shù)一直是人們研討的熱點(diǎn)。
??? 視頻圖像處理實(shí)時(shí)性要求高，而且視頻圖像數(shù)據(jù)量龐大，因此必須對(duì)它進(jìn)行壓縮。同時(shí)人們注意到，視頻圖像存在很強(qiáng)的幀間/幀內(nèi)冗余，為了消除幀間冗余，人們普遍采用運(yùn)動(dòng)估計(jì)算法" title="估計(jì)算法">估計(jì)算法和運(yùn)動(dòng)補(bǔ)償算法。運(yùn)動(dòng)估計(jì)算法的優(yōu)劣直接影響視頻編碼的效率和質(zhì)量。運(yùn)動(dòng)估計(jì)算法是塊匹配算法，如何快而準(zhǔn)地在參考幀中搜索到最佳的匹配塊是塊匹配算法的核心。本文對(duì)現(xiàn)有的搜索法進(jìn)行分析，并給出基于預(yù)測的自適應(yīng)六邊形搜索法。
1 對(duì)已有搜索算法的分析
??? 常用的快速搜索算法有：二維對(duì)數(shù)搜索算法(TDL)、共扼方向搜索算法(CS)、三步搜索算法(TSS)、菱形搜索算法（DS）等。其中，菱形搜索法又叫鉆石搜索法，以菱形模板形狀而得名，其算法簡單高效，是現(xiàn)有性能最優(yōu)的快速搜索算法之一，被MPEG-4采用。
??? 在搜索最佳匹配點(diǎn)時(shí)，選擇小的搜索模板可能會(huì)陷入局部最優(yōu)，選擇大的搜索模板可能增加計(jì)算量。DS算法采用兩種搜索模板：大鉆石搜索模板（LDSP）和小鉆石搜索模板（SDSP），如圖1所示。圖1(a)為大鉆石搜索模板，該模板包括圍繞中心點(diǎn)" title="中心點(diǎn)">中心點(diǎn)的8個(gè)點(diǎn)，共計(jì)9個(gè)點(diǎn)，形成一個(gè)大鉆石形；圖1(b)為小鉆石搜索模板，該模板包括5個(gè)點(diǎn)，形成一個(gè)較小規(guī)模的鉆石形。

?????????????????????
??? DS算法的搜索思想是先用LDSP搜索，由于步長大、搜索范圍廣，可以實(shí)現(xiàn)粗定位，使搜索不會(huì)陷于局部最小。當(dāng)粗定位結(jié)束時(shí)，可以認(rèn)為最優(yōu)點(diǎn)就在LDSP周圍8個(gè)點(diǎn)所圍的菱形區(qū)域中。然后用SDSP實(shí)現(xiàn)最佳匹配塊的準(zhǔn)確定位，使搜索不至于有較大的起伏，從而提高運(yùn)動(dòng)估計(jì)精度。
??? DS搜索法缺乏自適應(yīng)性，不管運(yùn)動(dòng)矢量是大是小均采用LDSP模板進(jìn)行粗定位。這樣，對(duì)于小運(yùn)動(dòng)矢量來說，勢必會(huì)有很多冗余的搜索。因此有必要對(duì)DS搜索法進(jìn)行改進(jìn)。
2 改進(jìn)的快速搜索方法
??? 本文提出一種基于預(yù)測的自適應(yīng)六邊形搜索法，該算法主要包含以下幾項(xiàng)核心技術(shù)：預(yù)判別零運(yùn)動(dòng)矢量，設(shè)定閥值對(duì)靜止塊直接終止運(yùn)動(dòng)估計(jì)；使用空間相鄰塊和時(shí)間相鄰塊估計(jì)當(dāng)前塊的運(yùn)動(dòng)類型；根據(jù)運(yùn)動(dòng)類型自適應(yīng)選擇搜索起始點(diǎn)；結(jié)合使用六邊形搜索法和小鉆石形搜索法的搜索策略。下面對(duì)具體的技術(shù)加以介紹。
2.1 預(yù)判別零運(yùn)動(dòng)矢量
??? 視頻序列的運(yùn)動(dòng)矢量具有中心偏移特性，即運(yùn)動(dòng)矢量高度集中在搜索窗口的中心附近。其中零運(yùn)動(dòng)矢量占有很大的比重，而且零矢量對(duì)編碼也是很有用的。
??? 設(shè)定閥值Th，在搜索前首先檢測（0，0）矢量。在進(jìn)行塊匹配時(shí)，一般采用SAD準(zhǔn)則。如果滿足SAD(0，0)則認(rèn)為該塊屬于靜止塊，其最優(yōu)運(yùn)動(dòng)矢量就是(0，0)，此時(shí)直接終止搜索，不需要進(jìn)行運(yùn)動(dòng)估計(jì)。

??? 閥值Th的選擇很重要。如果太小，該方法的優(yōu)勢體現(xiàn)不出來；如果太大，則會(huì)將一些非靜止塊誤判為靜止塊。經(jīng)驗(yàn)表明，取Th=900時(shí)，大約50%的塊被判為靜止塊，可以不做運(yùn)動(dòng)估計(jì)，而且圖像質(zhì)量主觀上沒有下降。
2.2 判定運(yùn)動(dòng)類型
??? 在視頻序列圖像中，物體運(yùn)動(dòng)是連續(xù)的，即在時(shí)間域和空間域上相鄰宏塊" title="宏塊">宏塊的運(yùn)動(dòng)矢量是緩慢變化的。在大多數(shù)情況下，當(dāng)前宏塊的運(yùn)動(dòng)矢量與幀內(nèi)和幀間相鄰宏塊的運(yùn)動(dòng)矢量有著相同的大小和方向。因此，描述物體運(yùn)動(dòng)的宏塊的運(yùn)動(dòng)矢量在時(shí)間上和空間上具有很強(qiáng)的相關(guān)性。利用運(yùn)動(dòng)矢量的這種時(shí)間上和空間上的相關(guān)性可以對(duì)當(dāng)前宏塊的運(yùn)動(dòng)矢量進(jìn)行預(yù)測，該初始運(yùn)動(dòng)矢量在一定程度上反映了當(dāng)前塊的運(yùn)動(dòng)情況，利于隨后進(jìn)行自適應(yīng)搜索。實(shí)驗(yàn)統(tǒng)計(jì)表明，當(dāng)前塊與幀內(nèi)上方、左方和右上方的子塊" title="子塊">子塊的相關(guān)性最強(qiáng)，而與其他位置子塊的相關(guān)性則較弱。本文選取與當(dāng)前塊相關(guān)性最強(qiáng)的三個(gè)空間相鄰子塊(上方、左方和右上方的子塊)和參考幀中相同位置的對(duì)應(yīng)點(diǎn)作為侯選點(diǎn)進(jìn)行預(yù)測(即圖2中的塊1，2，3，4)。

????????????????????????????
??? 令運(yùn)動(dòng)矢量集合V={V₀，V₁，V₂，V₃，V₄}，V₀=(0，0)，V₁=(x_i，y_i)，i=1，2，3，4，分別表示塊1，2，3和4的運(yùn)動(dòng)矢量。l_i=|x_i|+|y_i|，L=max{l₁，l₂，l₃，l₄}。設(shè)定閥值L₁和L₂，且L₁≤L₂。當(dāng)L≤L₁時(shí)，當(dāng)前塊被認(rèn)為是小運(yùn)動(dòng)塊；當(dāng)L₁2時(shí)，當(dāng)前塊被認(rèn)為是中等運(yùn)動(dòng)塊；當(dāng)L≥L₂時(shí)，當(dāng)前塊被認(rèn)為是大運(yùn)動(dòng)塊。

2.3 預(yù)測搜索起始點(diǎn)
??? 如果當(dāng)前塊為小運(yùn)動(dòng)塊或者中等運(yùn)動(dòng)塊，則最優(yōu)運(yùn)動(dòng)矢量常位于（0，0）附近較小的區(qū)域內(nèi)，不必預(yù)測搜索起始點(diǎn)；如果當(dāng)前塊為大運(yùn)動(dòng)類型，則最優(yōu)運(yùn)動(dòng)矢量偏離（0，0）點(diǎn)較大，而預(yù)測的搜索起始點(diǎn)更接近最優(yōu)運(yùn)動(dòng)矢量，所以需要預(yù)測搜索起始點(diǎn)。
??? 預(yù)測搜索起始點(diǎn)的方法有中值法、加權(quán)法和SAD比較法。本文采用SAD比較法，選取與當(dāng)前塊相關(guān)性最強(qiáng)的三個(gè)空間相鄰子塊(上方、左方和右上方的子塊)和參考幀中相同位置的對(duì)應(yīng)點(diǎn)作為侯選點(diǎn)進(jìn)行預(yù)測（即如圖2中的塊1，2，3，4），比較當(dāng)前塊與上述塊的絕對(duì)誤差和SAD，然后選取SAD最小的塊作為預(yù)測起點(diǎn)。
??? 令運(yùn)動(dòng)矢量集合V={V₁，V₂，V₃，V₄}，對(duì)應(yīng)的塊失真度分別為{SAD₁，SAD₂，SAD₃，SAD₄}，當(dāng)SAD_n=min{SAD₁，SAD₂，SAD₃，SAD₄}時(shí)，運(yùn)動(dòng)矢量所對(duì)應(yīng)的點(diǎn)即為搜索起始點(diǎn)。
??? 利用SAD比較法對(duì)各預(yù)測矢量進(jìn)行比較，取SAD最小者作為搜索起始點(diǎn)。從預(yù)測精度的角度考慮，使用SAD比較法最好，結(jié)合適當(dāng)?shù)乃阉鞑呗裕軌蜃羁斓卣业阶顑?yōu)運(yùn)動(dòng)矢量，同時(shí)使用SAD比較法得到的搜索起始點(diǎn)必然是某個(gè)相鄰塊的運(yùn)動(dòng)矢量，使得運(yùn)動(dòng)矢量場具有連續(xù)性，利于差分編碼。
2.4 搜索策略
??? 圓上的任意一點(diǎn)到圓心的距離都是相同的，如果能利用圓形作為匹配模板，則該模板在各個(gè)搜索方向都具有相同的搜索速度。但考慮到計(jì)算的復(fù)雜度和圖像序列的實(shí)際情況，本文采用六邊形搜索法，包含如圖3(a)所示的大六邊形模板（HSP）和如圖3(b)所示的小鉆石模板（SDSP）。
??????????????????????????????????????

??? 搜索時(shí)，先用HSP模板進(jìn)行粗定位，當(dāng)最小塊誤差點(diǎn)出現(xiàn)在中心點(diǎn)處時(shí)，可以認(rèn)為最優(yōu)點(diǎn)位于六邊形所圍的區(qū)域內(nèi)。這時(shí)再用SDSP模板準(zhǔn)確定位，SDSP模板5個(gè)點(diǎn)中誤差最小的點(diǎn)就是最優(yōu)匹配點(diǎn)。六邊形搜索法的搜索過程如圖3(c)所示，具體搜索過程如下：
??? (1)用HSP搜索法進(jìn)行匹配運(yùn)算，如果最小塊誤差（MBD）點(diǎn)出現(xiàn)在中心點(diǎn)，則轉(zhuǎn)(3)，否則轉(zhuǎn)(2)；
??? (2)以上一次找到的MBD點(diǎn)為中心點(diǎn)，轉(zhuǎn)(1)；
??? (3)以上一次找到的MBD點(diǎn)為中心點(diǎn)，用SDSP模板代替HSP模板進(jìn)行匹配運(yùn)算，在SDSP下的5個(gè)點(diǎn)中，MBD點(diǎn)的位置即提供最佳匹配塊的運(yùn)動(dòng)矢量。
??? 比較大六邊形搜索法和小鉆石搜索法，不難而知，HSP模板包含7個(gè)搜索點(diǎn)，而LDSP模板包含9個(gè)搜索點(diǎn)，因而在粗定位時(shí)HSP搜索法比 LDSP搜索法計(jì)算復(fù)雜度低。而且，HSP比LDSP更接近于圓，其水平方向的頂點(diǎn)到中心點(diǎn)的距離為2像素，對(duì)角方向的頂點(diǎn)到中心點(diǎn)的距離為像素。使用HSP在匹配窗移動(dòng)時(shí)，沿水平方向模板的梯度下降速度為2像素/步，沿對(duì)角方向模板的梯度下降速度為像素/步，高于LDSP像素/步的搜索速度，且新增搜索點(diǎn)數(shù)與方向無關(guān)，不管最小點(diǎn)在六邊形的邊點(diǎn)還是角點(diǎn)，在進(jìn)行下一次搜索時(shí)，都只需要計(jì)算3個(gè)點(diǎn)。由六邊形大模式切換到SDSP模式和DS方法相同。
3 實(shí)驗(yàn)結(jié)果
??? 為了驗(yàn)證算法的有效性，選取幾種有代表性的快速運(yùn)動(dòng)估計(jì)算法：FS、TSS、DS等算法，和本文提出的基于預(yù)測的自適應(yīng)六邊形算法在相同的條件下進(jìn)行對(duì)比實(shí)驗(yàn)。使用的子塊大小為16×16像素，搜索窗大小為15像素，匹配準(zhǔn)則選用SAD準(zhǔn)則。測試序列選用兩個(gè)QCIF格式視頻序列“Mother & Daughter”和“Foreman”，其中，“Mother & Daughter”序列是小運(yùn)動(dòng)序列，“Foreman”是大運(yùn)動(dòng)序列。對(duì)這些序列進(jìn)行運(yùn)動(dòng)估計(jì)，計(jì)算其PSNR和平均搜索點(diǎn)數(shù)，實(shí)驗(yàn)結(jié)果如表1和表2所示。

???????????????????????????
??? 觀察表1可以發(fā)現(xiàn)，對(duì)于小運(yùn)動(dòng)序列“Mother & Daughter”，F(xiàn)S算法需要搜索225個(gè)點(diǎn)，DS算法需要13.85個(gè)點(diǎn)，而本文提出的算法只需要計(jì)算2.86個(gè)點(diǎn)就可以找到最優(yōu)運(yùn)動(dòng)矢量。對(duì)于大運(yùn)動(dòng)序列“Foreman”，也有效地降低了搜索點(diǎn)數(shù)。
觀察表2可以發(fā)現(xiàn)，F(xiàn)S算法的平均PSNR值最高，說明FS算法的搜索精度最高。本文提出的算法的搜索精度高于DS算法的搜索精度，比較接近于FS算法的搜索精度。
??? 總結(jié)本文提出的運(yùn)動(dòng)估計(jì)算法可以看出，它從幾個(gè)方面對(duì)傳統(tǒng)的運(yùn)動(dòng)估計(jì)算法做了改進(jìn)。首先，在宏塊的運(yùn)動(dòng)估計(jì)中，以DS搜索法為基礎(chǔ)，提出了基于預(yù)測的六邊形搜索法，減少了計(jì)算量，提高了搜索速度；其次，搜索具有自適應(yīng)性，可以根據(jù)運(yùn)動(dòng)塊的類型確定搜索策略。
??? 實(shí)驗(yàn)結(jié)果表明，新的算法有效地降低了搜索點(diǎn)數(shù)，搜索精度也比較高，特別是進(jìn)行小運(yùn)動(dòng)估計(jì)，搜索點(diǎn)數(shù)少，搜索速度更快。
參考文獻(xiàn)
[1] 鐘玉琢，王琪，賀玉文．基于對(duì)象的多媒體數(shù)據(jù)壓縮標(biāo)準(zhǔn)——MPEG-4及其效驗(yàn)?zāi)Ｐ蚚M]．北京：科學(xué)出版社，2000．
[2] 鄭翔，葉志遠(yuǎn)，周秉鋒．JVT草案中的核心技術(shù)綜述[J]．軟件學(xué)報(bào)，2004，(1)：58-68．
[3] Coding of Moving Picture and Associated Audio for Digital?Storage Media at up to about 1.5Mbit/s[S].ISO/MPEG-1?ISO11172-2，1991．
[4] Information Technolog-Coding of Moving Picture and? Associated Audio for Digital Storage Media at up to about?1.5Mbit/s-Video[S].ISO/IEC11172-2，1993.
[5] 胡國榮．?dāng)?shù)字視頻壓縮及其標(biāo)準(zhǔn)[M].北京:北京廣播學(xué)院，1999．
[6] 沈蘭蓀．視頻編碼與低速率傳輸[M]．北京：電子工業(yè)出版社，2001．
[7] H.26L Test Model Long Term Number 8.VCEG of ITU-T，Apr.2001．
[8] Test Model 5.Draft.ISO/IEC/JTC1/SC29/WGWG11，Apr，1993．