【正文】 下面是一個(gè) 4 4的宏塊，在搜索范圍為（ 2,1）的搜索區(qū)域。 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)為參考幀中相對(duì)當(dāng)前塊位移為（ m,n）的點(diǎn)的亮度值 ,MxN 為宏塊大小。然后在參考幀 （ f,+f）的范圍 中，找到與當(dāng)前幀中的當(dāng)前塊相似程度最大的塊，即最佳匹配塊。 在全搜索法 (FS)中， PE 結(jié)構(gòu)簡(jiǎn)單，而且 每個(gè) PE 都完成的是一個(gè)固定的操作，適合脈動(dòng)陣列處理的特點(diǎn)，因此可以采用脈動(dòng)陣列來實(shí)現(xiàn)整個(gè)算法。脈動(dòng)陣列特點(diǎn)如下： （ 1）每一個(gè)節(jié)點(diǎn)，也就是 PE，也稱為胞元，都是相同的； （ 2）每個(gè) PE 只與相鄰的 PE進(jìn)行通信，也就是說 PE間的通信具有局部性，而且通信是規(guī)則的； （ 3）每個(gè) PE都有局部的存儲(chǔ)器，也就是 PE 的某些邊帶有延時(shí)，這些延時(shí)在硬件上對(duì)于寄存器； 由于脈動(dòng)陣列的以上特點(diǎn)，造成 PE 之間的高度流水化、規(guī)則化，因此系統(tǒng)吞吐率非常大且易于 VLSI 實(shí)現(xiàn)。 脈動(dòng)陣列概述 H. T. Kung 首先提出了脈動(dòng)陣列 [21]（ systolic array）的概念。為了提高 大型的 、對(duì) 速度要求 比較高的系統(tǒng) 的工作頻率，便可以采用流水線的設(shè)計(jì)方法 。流水線的處理速度只與輸入速度有關(guān)，因此，只要設(shè)計(jì)出好的流水線，就能使運(yùn)行效率達(dá)到很高。與并行結(jié)構(gòu)相比，流水線結(jié)構(gòu)可以充分利用數(shù)據(jù)的相互依賴關(guān)系，但只允許順著流水線的單方向依賴關(guān)系。具體到本文的流水線技術(shù)指的是將當(dāng)前塊數(shù)據(jù)和搜索區(qū)域的數(shù)據(jù)存在不同的片外存儲(chǔ)單元中，而且數(shù)據(jù)流在各部分之間單向傳遞，并在相鄰部分之間增加數(shù)據(jù)緩沖層 ，形成一系列流水級(jí)。數(shù)據(jù)流串行輸入，最小 SAD值和運(yùn)動(dòng)矢量并行輸出，使得 PE 的利用率也一直保持在 100%，促進(jìn)了實(shí)時(shí)實(shí)現(xiàn)的可能。THOMAS KOMAREK 等提出的 AB2型 2D 脈動(dòng)結(jié)構(gòu)雖然實(shí)現(xiàn)了數(shù)據(jù)的重用，但卻大大增加了 I/O 帶寬。 全搜索算法的主要硬件結(jié)構(gòu)有 1D 脈動(dòng)結(jié)構(gòu)、 2D 脈動(dòng)結(jié)構(gòu)和樹形結(jié)構(gòu) 【 19】 ，這三種結(jié)構(gòu)都是從減小 I/O帶寬、提高計(jì)算吞吐率的方向進(jìn)行設(shè)計(jì)實(shí)現(xiàn)的。窮盡式的搜索算法帶來了龐大的計(jì)算量，為了保證其在 VLSI 結(jié)構(gòu)中的高效運(yùn)行，就只有增加芯片的面積，使用多個(gè) PE 并 行計(jì)算。因?yàn)楸疚难芯康氖侨阉魉惴?，所以就不再介紹快速搜索算法的方方面面。 算法映射了結(jié)構(gòu)，視具體算法的數(shù)據(jù)流來確定要采用的硬件結(jié)構(gòu)。一個(gè)好的運(yùn)動(dòng)估計(jì)硬件結(jié)構(gòu)意味著該結(jié)構(gòu)占用了較少的硬 件資源、運(yùn)行速度快、使用的硬件 I/O 端口數(shù)目少。 西安理工大學(xué)碩士學(xué)位論文 18 運(yùn)動(dòng)估計(jì)的經(jīng)典硬件結(jié)構(gòu) 19 3 運(yùn)動(dòng)估計(jì)的經(jīng)典硬件結(jié)構(gòu) 既然選擇了全搜索算法作為本文的研究對(duì)象，那么接下來就要著手研究用怎樣的硬件結(jié)構(gòu)來實(shí)現(xiàn)全搜索算法。 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 非 對(duì)稱十字型多層次六邊形格點(diǎn)運(yùn)動(dòng)搜索算法 Fig29 Asymmetric crossshaped multilayered hexagonal movement grid search algorithm 通過對(duì)以上幾種搜索算法的實(shí)現(xiàn)過程對(duì)比，發(fā)現(xiàn)全搜索算法雖然計(jì)算量最龐大，但是匹配效果卻是最好的，而 UMHexagonS 算法雖然能達(dá)到和全搜索算法差不多的效果，但是搜索模板多樣化，不利與硬件實(shí)現(xiàn)，通過權(quán)衡，最終選擇了全搜索法進(jìn)行研究。 第四步：擴(kuò)展的六邊形搜索，第三步的多層次六邊形搜索可以得到不同精度的運(yùn)動(dòng)矢量，當(dāng)最佳匹配塊在外部六邊形時(shí)，得到的運(yùn)動(dòng)矢量精度就偏低，故需要進(jìn)一步細(xì)化搜索，通常用六邊形繼續(xù)下一步的搜索，如圖 29 Step4 所示。首先以上一步的最佳匹配點(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)動(dòng)的規(guī)律。這一步得到最佳匹配點(diǎn)便是下一步搜索的中心。 第二步：非對(duì)稱的十字搜索，在一般的運(yùn)動(dòng)中，水平方向的運(yùn)動(dòng)幅度大于垂直方向的運(yùn)動(dòng)幅度，故可以通過非對(duì)稱的十字形搜索先做一個(gè)初步的搜索。 混合非對(duì)稱十字多六邊形 格點(diǎn) 搜索 （ UMHexagonS） 混合非對(duì)稱十字多六邊形 格點(diǎn) 搜索 算法 【 18】 (UMHexagonS)是已有的快速搜索算法中估計(jì)效果最好的，已被 官方采用。 (4)搜索窗口換為 3x3，這時(shí)得到的最小 BDM 點(diǎn)便是最優(yōu)匹配點(diǎn)，其相對(duì)位移便是運(yùn)動(dòng)矢量。 (2)搜索窗口仍用 5x5，但搜索模式要依賴上一步最小 BDM 的位置，若在窗口的四個(gè)角，就增加五個(gè)測(cè)試點(diǎn)，若在窗口四條邊的中心，就增加三個(gè)測(cè)試點(diǎn)，若出現(xiàn)在窗口的中心，轉(zhuǎn)至第 四步繼續(xù)，否則繼續(xù) 。 四步搜索法 (Four Step Search) 四步搜索法也利用了運(yùn)動(dòng)矢量靠近中心分布的理論，將 TSS 的 9x9 搜索窗改為 5x5，每一步都以上一步最小的 BDM 的位置為中心，繼續(xù)下一步的搜索，步長(zhǎng)取決于最小 BDM的位置。如果得到的新 MBD 點(diǎn)位于中心，轉(zhuǎn)至第三步，否則，重復(fù)此步操作，直至匹配點(diǎn)到達(dá)搜索窗的邊緣，停止搜索。否則，轉(zhuǎn)至第二步繼續(xù)搜索。 運(yùn)動(dòng)估計(jì)及經(jīng)典算法 15 （ a）大菱形 （ b）小菱形 圖 27 “鉆石”搜索模板 Fig27 Diamond search template DS算法流程如下 : 第一步 :以搜索窗口的原點(diǎn) (O， 0)為中心，采用 LDSP 模板，檢測(cè)這九個(gè)點(diǎn)。 第 一 步 第 二 步 第 三 步 圖 26 新三步搜索法 Fig26 New three step search 菱形搜索法 (Diamond Search) 菱形搜索法因其搜索模板像鉆石又被稱為 “鉆石”搜索算法 [17]，它采用 LDSP（ Large Diamond Search Pattern，大鉆石搜索模板）和 SDSP（ Small Diamond Search Pattern，小鉆石搜索模板）兩種搜索模板，如圖 27所示。如果最小的 BDM 出現(xiàn)在 w/2 上，接下來就按三步搜索法的第二步和第三步執(zhí)行，找到最佳的運(yùn)動(dòng)矢量。如果第一步最小的 BDM 在搜索窗口的中心，就停止搜索 。具體步驟如下 : (l)在三步法的第一步的基礎(chǔ)上，增加對(duì)中心點(diǎn)的 8 個(gè)鄰域的測(cè)試。 新三步搜索法 (New Three Step Search) NTSS 算法 [16]彌補(bǔ)了 TSS 算法在估計(jì)運(yùn)動(dòng)不劇烈的的運(yùn)動(dòng)上的不足。 三步搜索法，最多需要計(jì)算 25 個(gè)點(diǎn)的 SAD 值，而全搜索算法采用相同的搜索范圍，卻需要計(jì)算 225 個(gè)點(diǎn)的 SAD 值，相比可見，三步法大大降低了運(yùn)算量。 ①②③① ①① ① ①① ① ①②②②②②②②③ ③③ ③ ③③③ 圖 25 三步搜索法 Fig25 Threestep search method 圖 25 示意了最大搜索距離為 7 時(shí)的搜索過程。三步法思想簡(jiǎn)單，性能良好，被許多 軟件采用。 三步搜索法（ TSS），顧名思義，得到最終的運(yùn)動(dòng)矢量需要三個(gè)步驟。為了保證速度，快速搜索算法并沒有像全搜索算法那樣進(jìn)行窮盡的搜索，只搜索了特定的 宏塊，雖然保證了速度，卻容易陷入局部最優(yōu)，而全搜索算法能夠保證找到全局最優(yōu)的匹配塊，保證最匹配的宏塊運(yùn)動(dòng)矢量信息?？焖偎阉鞣ㄖ皇菍?dāng)前塊與對(duì)應(yīng)搜索區(qū)域中的部分宏塊進(jìn)行匹配計(jì)算，從這幾個(gè)宏塊中找到最佳的匹配塊，這樣做就減小了全搜索算法需要的匹配次數(shù)。 全搜索法的算法簡(jiǎn)單，性能也最好，易于 VLSI 實(shí)現(xiàn)，考慮到現(xiàn)有的硬件條件，要實(shí)現(xiàn)它 已成為一種可能，某些要求高的應(yīng)用場(chǎng)合非的采用全搜索算法不可，因此對(duì)它的研究還是很有意義的。 全搜索算法 (FS)的規(guī)則最簡(jiǎn)單的，但運(yùn)算量卻占到了視頻壓縮編碼過程的 70%左右，當(dāng)搜索范圍為 (f,+f)時(shí)，需要進(jìn)行 (2f+1)2次的運(yùn)算，因此加大了實(shí)時(shí)性實(shí)現(xiàn)的難度，要想實(shí)時(shí)實(shí)現(xiàn)，就需要很高的硬件水平。 （ a）光柵式搜索 西安理工大學(xué)碩士學(xué)位論文 12 （ b）螺旋式搜索 圖 24 全搜索的兩種搜索方式 Fig24 Two search methods of full search 全搜索法（ FS）擁有最高的運(yùn)動(dòng)估計(jì)準(zhǔn)確度，也不容易陷入局部最優(yōu)，也是其它快速搜索 算法的判斷準(zhǔn)則，將匹配結(jié)果和全搜索法進(jìn)行對(duì)比，來評(píng)判該算法的好壞。全搜索法有光柵式和螺旋式兩種搜索方式，如圖 24 所示。下面介紹幾種常用的運(yùn)動(dòng)估計(jì)算法。準(zhǔn)確度越高，殘差值越小，編碼后需要傳輸?shù)谋忍財(cái)?shù)就越少，降低了傳輸帶寬。 經(jīng)典塊匹配運(yùn)動(dòng)估計(jì)算法介紹和性能分析 運(yùn)動(dòng)估計(jì)的算法決定了視頻壓縮的性能和速 度，是視頻壓縮編碼系統(tǒng)中至關(guān)重要的一環(huán)。亞像素運(yùn)動(dòng)估計(jì)通常在整像素搜索得到的最佳匹配點(diǎn)的附近插值形成一個(gè)虛擬的亞像素塊，將步長(zhǎng)變?yōu)榉謹(jǐn)?shù)進(jìn)行下一步運(yùn)動(dòng)估計(jì)及經(jīng)典算法 11 的搜索。 3 63 43 23 02 82 0 K4 0 K 6 0 K 8 0 K 1 0 0 K 1 2 0 K 1 4 0 K 1 6 0 KPSNR（ D B ）比 特 率 （ b p s ）1 / 2 像 素1 / 4 像 素1 / 8 像 素 圖 23 不同亞像素的編碼效率 Fig24 Coding efficiency of the different subpixel 為了進(jìn)一步提高運(yùn)動(dòng)估計(jì)的準(zhǔn)確度，后來的標(biāo)準(zhǔn)采用了亞像素的運(yùn)動(dòng)估計(jì)，雖然在一定程度上提升了性能，但卻大大增加了運(yùn)算量。 物體運(yùn)動(dòng) 具有 連續(xù)性，相鄰兩幀之間不 可能都是 是以整像素為基本單位的 運(yùn)動(dòng)的 ，可能是以 1/2 像素 或者 1/4 像素等亞像素 作為 運(yùn)動(dòng) 單位的?？陀^的標(biāo)準(zhǔn)不受任何因素的影響，因此采取客觀的標(biāo)準(zhǔn)來衡量匹配效果的好差，其中最常用的是峰值信噪比 PSNR(Peak Signal to Noise Ratio)： 2( 2 1)1 0 lg ndBPS N R MS E?? () PSNR 值越大，圖像的質(zhì)量就越高， PSNR 值越小，圖像的質(zhì)量相對(duì)較低。但人眼看到的圖像是諸多西安理工大學(xué)碩士學(xué)位論文 10 因素相互作用的過程。 算法評(píng)定指標(biāo) 運(yùn)動(dòng)估計(jì)就是為了在前一幀搜索區(qū)域中找到與當(dāng)前塊最為相似的塊，運(yùn)動(dòng)估計(jì)越準(zhǔn)確 ，得到的相似塊的相似度就越高，壓縮性能就越好，需要傳輸?shù)臍埐顗K像素就越少。當(dāng)搜索區(qū)域增大時(shí)，雖然能在一定程度上提高運(yùn)動(dòng)估計(jì)的準(zhǔn)確度，但是增大了計(jì)算量，這就意味著將要占用更多的硬件資源。 搜索范圍的確定 搜索范圍的大小嚴(yán)重影響著運(yùn)動(dòng)估計(jì)的精度，它的確定需要綜合、慎重的考慮。但不能讓搜索過程無限制 的進(jìn)行下去，有時(shí)候沒有必要，比方對(duì)靜止的圖像，那么多搜索步驟都是在做無用功，因此需要一個(gè)提前終止準(zhǔn)則，保證搜索過程能夠及時(shí)終止，減少時(shí)間的浪費(fèi)。 搜索策略 搜索策略選擇恰當(dāng)與否，嚴(yán)重影響著運(yùn)動(dòng)估計(jì)的準(zhǔn)確性和速度。確定了需 要采用的運(yùn)動(dòng)估計(jì)算法和搜索范圍的大小，匹配準(zhǔn)則對(duì)運(yùn)動(dòng)估計(jì)精度的影響可以忽略不計(jì)，但采用SAD 能夠明顯的降低計(jì)算復(fù)雜度，它和 MAD 相比只是少了一個(gè)除法因子，其它一樣，雖然如此，但它卻和 MAD 準(zhǔn)則有著相同的匹配效果。 由于 MSE 準(zhǔn)則和 NCCF 準(zhǔn)則中有乘方運(yùn)算，實(shí)現(xiàn)時(shí)相比之下就要占用更多的資源，計(jì)算復(fù)雜度也較其它的高。 （ 4）絕對(duì)差值和（ SAD）。 （ 3）歸一化互相關(guān)函數(shù) (NCCF)。 （ 2）最小均方誤差函數(shù) (MSE)。常見的匹配準(zhǔn)則有： (1)MAD 是最小絕對(duì)差。 匹配準(zhǔn)則 任何事物的執(zhí)行都需要一定的標(biāo)準(zhǔn)。采用 4x4的分塊，雖然在一定程度上能夠提高運(yùn)動(dòng)估計(jì)的精度，但這樣每一幀圖像就需要更過的運(yùn)動(dòng)矢量和殘差塊來表示 ，編碼效率降低，傳輸時(shí)也將占用更多的帶寬。因此有必要選擇合適的塊大小，滿足既定的前提。運(yùn)動(dòng)的劇烈程度不同，需要采用的分塊大小最好也不要相同。 塊匹配運(yùn)動(dòng)估計(jì)的參數(shù)和準(zhǔn)則 塊匹配算法中，涉及到分塊大小、搜索范圍、匹配準(zhǔn)則等幾個(gè)參數(shù)的選取，這些參數(shù)的選取需要綜合考慮，它們的好壞嚴(yán)重影響著運(yùn)動(dòng)估計(jì)的準(zhǔn)確度及實(shí)現(xiàn)難易程度。如圖 22所示。運(yùn)動(dòng)補(bǔ)償?shù)男ЧQ于運(yùn)動(dòng)矢量的精確程度， 運(yùn)動(dòng)矢量的精確程度又取決于運(yùn)動(dòng)估計(jì)的準(zhǔn)確度，因此，選擇一個(gè)好的運(yùn)動(dòng)估計(jì)算法很重