【導(dǎo)讀】隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們的生活中充滿了各種多媒體技術(shù)。頒布了視頻編碼標(biāo)準(zhǔn)。個(gè)標(biāo)準(zhǔn)下，可獲得比以往標(biāo)準(zhǔn)都高的編碼效率，滿足低帶寬、高質(zhì)量網(wǎng)絡(luò)視頻應(yīng)用的需要。為了達(dá)到實(shí)時(shí)性，對視頻編碼技術(shù)提出了更高的挑戰(zhàn)。作為視頻壓縮編碼中運(yùn)算量最大也。一個(gè)重要研究方向。像素運(yùn)動估計(jì)結(jié)構(gòu)，并完成了其VLSI設(shè)計(jì)。先簡要描述了標(biāo)準(zhǔn)及其性能，對塊。匹配運(yùn)動估計(jì)原理和相關(guān)參數(shù)對運(yùn)動估計(jì)效果的影響進(jìn)行了詳細(xì)的介紹。算法和幾種快速搜索算法作了一一介紹。然后重點(diǎn)介紹了兩種脈動結(jié)構(gòu)：1-D和2-D，闡述了各自的優(yōu)點(diǎn)和不足。由于搜索區(qū)域中的相鄰參考塊之間有一定的數(shù)據(jù)重疊，為了重。串入并出的流水線，提高了計(jì)算速度的同時(shí)也大大減小了I/O帶寬。塊的Verilog代碼，并分塊進(jìn)行了功能仿真，子模塊仿真通過后，把所有模塊綜合起來，通過分析仿真數(shù)據(jù)，證明了本文設(shè)計(jì)的全搜索運(yùn)動估計(jì)模塊能夠正常工作，并且能夠?qū)崿F(xiàn)全搜索算法的功能，輸出正確的運(yùn)動矢量。

　　

【正文】 域中，則以最小 BDM 為中心計(jì)算其 8個(gè)鄰域，重復(fù)該步驟，直至最小 BDM 出現(xiàn)在中心。如果最小的 BDM 出現(xiàn)在 w/2 上，接下來就按三步搜索法的第二步和第三步執(zhí)行，找到最佳的運(yùn)動矢量。 NTSS 算法執(zhí)行完所有的步驟需要測試 33 個(gè)點(diǎn)，但 NTSS 算法有時(shí)會在第一步或第二步的時(shí)候就提前終止，對于靜止的塊只需測試 17個(gè)點(diǎn)，對于亞靜止的塊需要測試 20 或者22 個(gè)點(diǎn)，所以 NTSS 相對于 TSS 有了一定的改善，加速了約 18%。 第 一 步 第 二 步 第 三 步 圖 26 新三步搜索法 Fig26 New three step search 菱形搜索法 (Diamond Search) 菱形搜索法因其搜索模板像鉆石又被稱為 “鉆石”搜索算法 [17]，它采用 LDSP（ Large Diamond Search Pattern，大鉆石搜索模板）和 SDSP（ Small Diamond Search Pattern，小鉆石搜索模板）兩種搜索模板，如圖 27所示。 “鉆石”搜索算法，先 采用步長大、范圍廣 LDSP 模板搜索，進(jìn)行一個(gè)粗略的定位，這也符合視頻圖像運(yùn)動的基本規(guī)律，陷于局部最優(yōu)的可能性降低；當(dāng)完成了粗略定位后，再采用 SDSP 模板搜索 LDSP 中得到的最小 SAD 值點(diǎn)的周圍 4 個(gè)點(diǎn)，這時(shí)得到的 SAD 值最小點(diǎn)便是最優(yōu)匹配點(diǎn)，這樣做避免了陷入局部最優(yōu)，提升了運(yùn)動估計(jì)的準(zhǔn)確度。 運(yùn)動估計(jì)及經(jīng)典算法 15 （ a）大菱形 （ b）小菱形 圖 27 “鉆石”搜索模板 Fig27 Diamond search template DS算法流程如下 : 第一步 :以搜索窗口的原點(diǎn) (O， 0)為中心，采用 LDSP 模板，檢測這九個(gè)點(diǎn)。如果MBD(Minimum Block Distortion)點(diǎn)位于中心，就轉(zhuǎn)至第三步 。否則，轉(zhuǎn)至第二步繼續(xù)搜索。 第二步 :以第一步搜索得到的 MBD 點(diǎn)為中心，構(gòu)造另一個(gè) LDSP。如果得到的新 MBD 點(diǎn)位于中心，轉(zhuǎn)至第三步，否則，重復(fù)此步操作，直至匹配點(diǎn)到達(dá)搜索窗的邊緣，停止搜索。 第三步 :采用 SDSP 模板，這一步搜索得到的 MBD 點(diǎn)便是最優(yōu)匹配點(diǎn)，其相對位移便是運(yùn)動矢量。 四步搜索法 (Four Step Search) 四步搜索法也利用了運(yùn)動矢量靠近中心分布的理論，將 TSS 的 9x9 搜索窗改為 5x5，每一步都以上一步最小的 BDM 的位置為中心，繼續(xù)下一步的搜索，步長取決于最小 BDM的位置。四步搜索法的四步操作如下 : (l)在搜索區(qū)域的中心用一個(gè) 5x5 的窗口，如果最小 BDM 出現(xiàn)在窗口中心，轉(zhuǎn)到第四步，否則繼續(xù) 。 (2)搜索窗口仍用 5x5，但搜索模式要依賴上一步最小 BDM 的位置，若在窗口的四個(gè)角，就增加五個(gè)測試點(diǎn)，若在窗口四條邊的中心，就增加三個(gè)測試點(diǎn)，若出現(xiàn)在窗口的中心，轉(zhuǎn)至第 四步繼續(xù)，否則繼續(xù) 。 (3)搜索模式和第二步一樣，但該步下來不管怎樣都轉(zhuǎn)至第四步 。 (4)搜索窗口換為 3x3，這時(shí)得到的最小 BDM 點(diǎn)便是最優(yōu)匹配點(diǎn)，其相對位移便是運(yùn)動矢量。 西安理工大學(xué)碩士學(xué)位論文 16 1111111 1 3222333334 444444 4 圖 28 四步搜索法 Fig28 Fourstep search method FSS 又一次改進(jìn)了快速搜索算法，搜索速度不一定比 TSS 快，但是 FSS 的計(jì)算復(fù)雜度相比 TSS 有所降低，而且整個(gè)搜索過程比較平緩，減小了出現(xiàn)局部最優(yōu)的可能，并對靜止的塊縮短了搜索時(shí)間，所以獲得了較好 的搜索效果。 混合非對稱十字多六邊形 格點(diǎn) 搜索 （ UMHexagonS） 混合非對稱十字多六邊形 格點(diǎn) 搜索 算法 【 18】 (UMHexagonS)是已有的快速搜索算法中估計(jì)效果最好的，已被 官方采用。 UMHexagonS 算法分四步完成搜索，搜索步驟如下： 第一步：進(jìn)行矢量預(yù)測，確定搜索的起始點(diǎn)。 第二步：非對稱的十字搜索，在一般的運(yùn)動中，水平方向的運(yùn)動幅度大于垂直方向的運(yùn)動幅度，故可以通過非對稱的十字形搜索先做一個(gè)初步的搜索。所謂非對稱十字，如圖 29 中 step2 的△點(diǎn)所示，水平方向 的搜索長度為垂直方向搜索高度的 2倍，搜索點(diǎn)間距 2個(gè)步長。這一步得到最佳匹配點(diǎn)便是下一步搜索的中心。 第三步：多層次六邊形搜索，分兩步完成。首先以上一步的最佳匹配點(diǎn)的位置作為搜索中心，做一個(gè) 5 5 范圍的全搜索，如圖 29 中 step31 的圓圈所示；第二步進(jìn)行多層次六邊形搜索，采用了 16 點(diǎn)的六邊形，即圖 29 中 step32 的小方形所示，如圖 29 所示，六邊形覆蓋的區(qū)域比較大，而且六邊形左右兩側(cè)的點(diǎn)數(shù)比上下兩側(cè)的搜索點(diǎn)數(shù)多，這也符合運(yùn)動的規(guī)律。六邊形由里到外層層搜索，等搜索結(jié)束后，比較每 層中相對較小的SAD 值，其中最小的 SAD值所對應(yīng)的位置便是下一步繼續(xù)搜索位置的中心。 第四步：擴(kuò)展的六邊形搜索，第三步的多層次六邊形搜索可以得到不同精度的運(yùn)動矢量，當(dāng)最佳匹配塊在外部六邊形時(shí)，得到的運(yùn)動矢量精度就偏低，故需要進(jìn)一步細(xì)化搜索，通常用六邊形繼續(xù)下一步的搜索，如圖 29 Step4 所示。先采用半徑為 2 的六邊形反復(fù)搜索，直到最佳點(diǎn)出現(xiàn)在六邊形中心，接下來用半徑為 1 的小菱形繼續(xù)搜索，直至最佳運(yùn)動估計(jì)及經(jīng)典算法 17 匹配塊位于小菱形的中心。 051 01 5 5 1 0 1 5051 0 1 5 5 1 0 1 5s t e p 2s t e p 3 1 s t e p 3 2 s t e p 4 1 s t e p 4 2 圖 29 非 對稱十字型多層次六邊形格點(diǎn)運(yùn)動搜索算法 Fig29 Asymmetric crossshaped multilayered hexagonal movement grid search algorithm 通過對以上幾種搜索算法的實(shí)現(xiàn)過程對比，發(fā)現(xiàn)全搜索算法雖然計(jì)算量最龐大，但是匹配效果卻是最好的，而 UMHexagonS 算法雖然能達(dá)到和全搜索算法差不多的效果，但是搜索模板多樣化，不利與硬件實(shí)現(xiàn)，通過權(quán)衡，最終選擇了全搜索法進(jìn)行研究。 本章小結(jié) 本章介紹了運(yùn)動估計(jì)的概念和塊匹配的原理，分析了分 塊大小、匹配準(zhǔn)則、搜索策略、搜索范圍、估計(jì)精度對視頻壓縮編碼性能的影響，以及它們選取和確定中需要注意的問題，介紹了幾種運(yùn)動估計(jì)算法的原理和具體實(shí)現(xiàn)步驟，經(jīng)過性能對比以及硬件實(shí)現(xiàn)的難易程度，最終決定選擇全搜索算法進(jìn)行研究。 西安理工大學(xué)碩士學(xué)位論文 18 運(yùn)動估計(jì)的經(jīng)典硬件結(jié)構(gòu) 19 3 運(yùn)動估計(jì)的經(jīng)典硬件結(jié)構(gòu) 既然選擇了全搜索算法作為本文的研究對象，那么接下來就要著手研究用怎樣的硬件結(jié)構(gòu)來實(shí)現(xiàn)全搜索算法。良好的硬件結(jié)構(gòu)加上流暢的數(shù)據(jù)流，使的整個(gè)系統(tǒng)能夠高效的運(yùn)行，加大了視頻編碼實(shí)時(shí)性的可能性。一個(gè)好的運(yùn)動估計(jì)硬件結(jié)構(gòu)意味著該結(jié)構(gòu)占用了較少的硬 件資源、運(yùn)行速度快、使用的硬件 I/O 端口數(shù)目少。要想設(shè)計(jì)出一個(gè)好的結(jié)構(gòu)就要從以上三方面綜合考慮。 算法映射了結(jié)構(gòu)，視具體算法的數(shù)據(jù)流來確定要采用的硬件結(jié)構(gòu)。根據(jù)上一章的介紹，主要有全搜索算法和快速搜索算法兩大類算法。因?yàn)楸疚难芯康氖侨阉魉惴?，所以就不再介紹快速搜索算法的方方面面。全搜索算法的性能最好，而且數(shù)據(jù)流工整，易于VLSI 實(shí)現(xiàn)，很早就得到了大量的研究，至今也提出了很多經(jīng)典的硬件結(jié)構(gòu)。窮盡式的搜索算法帶來了龐大的計(jì)算量，為了保證其在 VLSI 結(jié)構(gòu)中的高效運(yùn)行，就只有增加芯片的面積，使用多個(gè) PE 并 行計(jì)算。因此，就要在這幾個(gè)矛盾體之間找到一個(gè)平衡點(diǎn)，使得硬件結(jié)構(gòu)能夠高效的運(yùn)行，進(jìn)而提高編碼的性能，促進(jìn)實(shí)時(shí)實(shí)現(xiàn)的可能。 全搜索算法的主要硬件結(jié)構(gòu)有 1D 脈動結(jié)構(gòu)、 2D 脈動結(jié)構(gòu)和樹形結(jié)構(gòu) 【 19】 ，這三種結(jié)構(gòu)都是從減小 I/O帶寬、提高計(jì)算吞吐率的方向進(jìn)行設(shè)計(jì)實(shí)現(xiàn)的。 Yang 等提出的 1D 脈動結(jié)構(gòu)是最早的運(yùn)動估計(jì)硬件結(jié)構(gòu)，沒能實(shí)現(xiàn)相鄰當(dāng)前塊搜索區(qū)域重疊數(shù)據(jù)的重用。THOMAS KOMAREK 等提出的 AB2型 2D 脈動結(jié)構(gòu)雖然實(shí)現(xiàn)了數(shù)據(jù)的重用，但卻大大增加了 I/O 帶寬。 在分析了這些經(jīng)典硬件結(jié)構(gòu)之 后，通過揚(yáng)長補(bǔ)短，提出了本文的 2D 脈動結(jié)構(gòu)，實(shí)現(xiàn)了相鄰當(dāng)前塊搜索區(qū)域數(shù)據(jù)的重用，也減小了 I/O 帶寬。數(shù)據(jù)流串行輸入，最小 SAD值和運(yùn)動矢量并行輸出，使得 PE 的利用率也一直保持在 100%，促進(jìn)了實(shí)時(shí)實(shí)現(xiàn)的可能。 流水線技術(shù)概述 流水線（ pipeline）技術(shù) 【 20】 是指 將一個(gè)重復(fù)的過程，分解為若干個(gè)子過程，各個(gè)子過程 重疊進(jìn)行操作的一種準(zhǔn)并行處理實(shí)現(xiàn)技術(shù) 。具體到本文的流水線技術(shù)指的是將當(dāng)前塊數(shù)據(jù)和搜索區(qū)域的數(shù)據(jù)存在不同的片外存儲單元中，而且數(shù)據(jù)流在各部分之間單向傳遞，并在相鄰部分之間增加數(shù)據(jù)緩沖層 ，形成一系列流水級。沒有使用流水線時(shí)，要等到上一個(gè)數(shù)據(jù)處理完，才能輸入下一個(gè)數(shù)據(jù)，但使用流水線之后，下一個(gè)數(shù)據(jù)的輸入只需要其上一個(gè)數(shù)據(jù)將一個(gè)流水級處理完畢。與并行結(jié)構(gòu)相比，流水線結(jié)構(gòu)可以充分利用數(shù)據(jù)的相互依賴關(guān)系，但只允許順著流水線的單方向依賴關(guān)系。所謂流水線處理，是指將工作量分成若干個(gè)時(shí)間上均衡的操作段，各操作段 重疊進(jìn)行 并行 操作 。流水線的處理速度只與輸入速度有關(guān)，因此，只要設(shè)計(jì)出好的流水線，就能使運(yùn)行效率達(dá)到很高。 如果一個(gè)設(shè)計(jì)的處理流程可以分為若干個(gè)步驟，并且整個(gè)數(shù)據(jù)處理是單方向流動的，西安理工大學(xué)碩士學(xué)位論文 20 這個(gè)時(shí)候 可以采用流水線設(shè)計(jì)來提高系統(tǒng)的工作效率。為了提高 大型的 、對 速度要求 比較高的系統(tǒng) 的工作頻率，便可以采用流水線的設(shè)計(jì)方法 。 全搜索算法中，當(dāng)前塊的相鄰搜索區(qū)域和相鄰當(dāng)前塊的搜索區(qū)域中數(shù)據(jù)的有很多的重疊，具有較高的數(shù)據(jù)復(fù)用率，因此可采用流水線的技術(shù)對這些數(shù)據(jù)進(jìn)行處理，完成了龐大的運(yùn)算量的同時(shí)也提高了效率。 脈動陣列概述 H. T. Kung 首先提出了脈動陣列 [21]（ systolic array）的概念。脈動陣列中，多個(gè)執(zhí)行固定操作的 PE與相鄰的 PE 按一定的規(guī)則互聯(lián)，需要處理的數(shù)據(jù)在陣列中一級一級的有序 傳播，得到了充分利用，這樣做大大減小了 I/O 帶寬。脈動陣列特點(diǎn)如下： （ 1）每一個(gè)節(jié)點(diǎn)，也就是 PE，也稱為胞元，都是相同的； （ 2）每個(gè) PE 只與相鄰的 PE進(jìn)行通信，也就是說 PE間的通信具有局部性，而且通信是規(guī)則的； （ 3）每個(gè) PE都有局部的存儲器，也就是 PE 的某些邊帶有延時(shí)，這些延時(shí)在硬件上對于寄存器； 由于脈動陣列的以上特點(diǎn)，造成 PE 之間的高度流水化、規(guī)則化，因此系統(tǒng)吞吐率非常大且易于 VLSI 實(shí)現(xiàn)。流水化意味著吞吐率大，規(guī)則化則意味著版圖流片成功率大。 在全搜索法 (FS)中， PE 結(jié)構(gòu)簡單，而且 每個(gè) PE 都完成的是一個(gè)固定的操作，適合脈動陣列處理的特點(diǎn)，因此可以采用脈動陣列來實(shí)現(xiàn)整個(gè)算法。 全搜索運(yùn)動估計(jì)算法的硬件結(jié)構(gòu) 進(jìn)行運(yùn)動估計(jì)的時(shí)候，將當(dāng)前幀分為等大小且互不交疊的宏塊。然后在參考幀 （ f,+f）的范圍 中，找到與當(dāng)前幀中的當(dāng)前塊相似程度最大的塊，即最佳匹配塊。匹配過程中一般采用 SAD 準(zhǔn)則。 1100( , ) | ( , ) ( , ) |NMijS A D m n c i j p m i n j????? ? ? ??? (f≤ m, n ≤ f 1) () c(i,j)為當(dāng)前幀中坐標(biāo)為 (i,j)的點(diǎn)的亮度值， p(m+i,n+j)為參考幀中相對當(dāng)前塊位移為（ m,n）的點(diǎn)的亮度值 ,MxN 為宏塊大小。 在 標(biāo)準(zhǔn)中，最小基本宏塊為 4 4，本文就采用了最小的宏塊進(jìn)行研究。 下面是一個(gè) 4 4的宏塊，在搜索范圍為（ 2,1）的搜索區(qū)域。 運(yùn)動估計(jì)的經(jīng)典硬件結(jié)構(gòu) 21 p ( 0 , 0 ) p ( 1 , 0 ) p ( 2 , 0 ) b ( 3 , 0 ) p ( 4 , 0 ) p ( 5 , 0 ) p ( 6 , 0 )p ( 0 , 1 ) b ( 1 , 1 ) p ( 2 , 1 ) p ( 3 , 1 ) p ( 4 , 1 ) p ( 5 , 1 ) p ( 6 , 1 )p ( 0 , 2 ) p ( 1 , 2 ) p ( 2 , 2 ) p ( 3 , 2 ) p ( 4 , 2 ) p ( 5 , 2 ) p ( 6 , 2 )p ( 0 , 3 ) p ( 1 , 3 ) p ( 2 , 3 ) p ( 3 , 3 ) p ( 4 , 3 ) p ( 5 , 3 ) p ( 6 , 3 )p ( 0 , 4 ) p ( 1 , 4 ) p ( 2 , 4 ) p ( 3 , 4 ) p ( 4 , 4 ) p ( 5 , 4 ) p ( 6 , 4 )p ( 0 , 5 ) p ( 1 , 5 ) p ( 2 , 5 ) p ( 3 , 5 ) p ( 4 , 5 ) p ( 5 , 5 )