基于塊匹配算法的運(yùn)動(dòng)估計(jì)講解

1、基于塊匹配算法的運(yùn)動(dòng)估計(jì)摘要：本文首先介紹了運(yùn)動(dòng)估計(jì)和塊匹配的概念和思想， 然后詳細(xì)介紹了塊匹配的搜索算法。 最后根據(jù)塊匹配算法的運(yùn)動(dòng)估計(jì)給出了一個(gè)設(shè)計(jì)。關(guān)鍵字：運(yùn)動(dòng)估計(jì)，塊匹配，算法1 1研究背景隨著現(xiàn)代信息社會(huì)對(duì)通信業(yè)務(wù)要求的不斷增長(zhǎng)， 圖像通信與通信網(wǎng)容量的矛 盾日益突出， 尤其是具有龐大數(shù)據(jù)量的視頻圖像通信， 更是很難傳輸和存儲(chǔ)， 極 大的制約了圖像通信的發(fā)展。例如，按 CCIR601 建議，普通質(zhì)量的電視信號(hào)數(shù) 字視頻的碼率約為 216Mbit/s，而高清晰度電視 HDTV 則在 1.2Gb/s 以上，如果 沒(méi)有高效率的壓縮技術(shù)， 則難以傳輸和存儲(chǔ)。 而運(yùn)動(dòng)檢測(cè)與估計(jì)不僅是軍事領(lǐng)域

2、中目標(biāo)探測(cè)與跟蹤的有效技術(shù)之一， 同時(shí)也是視頻圖象編碼與壓縮的常用方法與 核心技術(shù)。因此，該項(xiàng)研究對(duì)于復(fù)雜背景下的目標(biāo)探測(cè)以及視頻處理均具有重要 的應(yīng)用價(jià)值。運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償是緊密聯(lián)系的， 它是視頻圖像壓縮編碼中使用的一項(xiàng)核 心技術(shù)，很好的解決了視頻圖像中時(shí)間冗余的問(wèn)題， 經(jīng)驗(yàn)表明， 實(shí)用化的壓縮方 法可以將運(yùn)動(dòng)圖像數(shù)據(jù)壓縮 30 倍而不失真。運(yùn)動(dòng)估計(jì)技術(shù)主要分為兩大類 :象素 遞歸法和塊匹配法。 考慮到計(jì)算復(fù)雜度和實(shí)時(shí)性要求， 塊匹配法已成為目前最常 用的方法。顯然，要想獲得好的運(yùn)動(dòng)補(bǔ)償，關(guān)鍵是要有準(zhǔn)確的運(yùn)動(dòng)估計(jì)，因此運(yùn) 動(dòng)估計(jì)算法的研究成為視頻壓縮算法的研究重點(diǎn)。 運(yùn)動(dòng)估計(jì)研究的主要內(nèi)容

3、就是 如何快速、 有效的獲得有足夠精度的運(yùn)動(dòng)矢量。 即把前一幀的運(yùn)動(dòng)部分根據(jù)運(yùn)動(dòng) 矢量補(bǔ)過(guò)來(lái)，同時(shí)用其它方法得到其剩余的不同部分的過(guò)程稱為運(yùn)動(dòng)補(bǔ)償 (Motion Compensation,MC)。就這樣，采用運(yùn)動(dòng)估計(jì)和補(bǔ)償可以有效地去除視頻 信號(hào)在時(shí)間方向的重復(fù)信息， 達(dá)到壓縮的目的。 其中， 在這方面的一種有效方法 就是塊匹配運(yùn)動(dòng)估計(jì) BMME(Block-Matching Motion Estimation), 它目前已被許多 視頻編碼標(biāo)準(zhǔn)所采納。 為了提高搜索速度和效率， 目前研究最多的是基于塊匹配 (Block Matching,BM) 的快速搜索算法，例如三步法，四步法，二維對(duì)數(shù)法

4、，菱形隨著計(jì)算機(jī)網(wǎng)絡(luò)的普及和發(fā)展， 很多信息可以通過(guò)網(wǎng)絡(luò)實(shí)現(xiàn)共享。 形色兼具的視頻信息在網(wǎng)絡(luò)傳輸?shù)男畔⒅兴紦?jù)的比例也越來(lái)越高。 但由于視頻信息本身 十分龐大， 限制了其在網(wǎng)絡(luò)中的傳播速度。 于是視頻信息的壓縮成為視頻傳輸?shù)?一個(gè)重要環(huán)節(jié)。 數(shù)字視頻信息是由數(shù)字圖像的時(shí)間序列構(gòu)成的， 每一幅數(shù)字圖像 稱為一幀。視頻編碼的一個(gè)主 (frame)要目的就是在保證一定重構(gòu)質(zhì)量的前提下， 以盡量少的比特?cái)?shù)來(lái)表征視頻信息。 視頻編碼是視頻壓縮的關(guān)鍵技術(shù)。 視頻編碼 與的原理是： 由于表示圖像和視頻信息所需的大量的數(shù)據(jù)往往是高度相關(guān)的， 這 些相關(guān)性會(huì)引起信息的冗余， 因此可以通過(guò)去除這些冗余信息來(lái)實(shí)現(xiàn)對(duì)

5、視頻數(shù)據(jù) 的壓縮。靜止圖像的壓縮是在保持重建圖像質(zhì)量可以接收的同時(shí)， 盡量去除圖像 本身存在的空間冗余， 而視頻信號(hào)的壓縮， 除了去除空間冗余之外， 還可以通過(guò) 去除時(shí)間冗余達(dá)到較高的壓縮比。運(yùn)動(dòng)估計(jì)技術(shù)是視頻圖像壓縮編碼中使用的一項(xiàng)核心技術(shù)， 很好的解決了視 頻圖像中時(shí)間冗余的問(wèn)題，運(yùn)動(dòng)估計(jì)技術(shù)主要分為兩大類 :象素遞歸法和塊匹配 算法?？紤]到計(jì)算復(fù)雜度和實(shí)時(shí)性要求，塊匹配法已成為目前最常用的方法。2 2實(shí)驗(yàn)原理如圖1 所示 , 運(yùn)動(dòng)估計(jì)的基本思想是將圖像序列的每一幀圖像分成許多互 不重疊的宏塊 , 并假設(shè)塊內(nèi)各像素只作相等的平移 , 然后對(duì)于當(dāng)前幀中的每一 塊到前一幀或后一幀某一給定搜索范

6、圍內(nèi)根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最 相似的塊 , 即匹配塊 , 由匹配塊與當(dāng)前塊的相對(duì)位置計(jì)算出運(yùn)動(dòng)位移 , 所得運(yùn) 動(dòng)位移即為當(dāng)前塊的運(yùn)動(dòng)矢量。 宏塊大小為 MN, 一般取 1616。搜索范圍一般由最大偏移矢量來(lái)決定 , 設(shè)可能的最大偏移矢量為 ( dxmax, dymax) , 則搜索范 圍為 (M+2dxmax) (N+2dymax)。圖 1 運(yùn)動(dòng)估計(jì)基本原理2.1塊匹配介紹按照一般的想法，運(yùn)動(dòng)估計(jì)應(yīng)當(dāng)首先將圖像中靜止背景和運(yùn)動(dòng)物體區(qū)分開(kāi) 來(lái)，然后對(duì)運(yùn)動(dòng)物體的實(shí)際位移進(jìn)行估計(jì)。 但塊匹配方法卻不是這樣， 它的思想 是將圖像劃分為許多互不重疊的子塊 ( 例如 1616) ，并認(rèn)為子塊內(nèi)所

7、有像素的 位移量都相同。這意味著每個(gè)子塊被視為運(yùn)動(dòng)物體。假設(shè)在圖像序列中， t 時(shí)刻 對(duì)應(yīng)于第 k 幀圖像， t- 時(shí)刻對(duì)應(yīng)于第 k-1 幀圖像。 對(duì)于 k 幀中的一個(gè)子塊， 在 k-1 幀中尋找與其最相似的子塊，這個(gè)過(guò)程稱為尋找匹配塊，并認(rèn)為該匹配塊在 k-1 幀中所處的位置就是 k 幀子塊位移前的位置，這種位置的變化用運(yùn)動(dòng)矢量 D 來(lái)表示。將圖像分割成 MN 的小塊，并假設(shè)塊內(nèi)象素作相同的運(yùn)動(dòng)，且只作平移運(yùn) 動(dòng)。雖然實(shí)際上塊內(nèi)各點(diǎn)運(yùn)動(dòng)不一定相同，也不定只有平移運(yùn)動(dòng)，但當(dāng)MN 較小時(shí)，上述假設(shè)可近似成立。 這樣做的目的只是為了簡(jiǎn)化運(yùn)算。 塊匹配法對(duì)當(dāng)前 幀圖像的每一塊， 在上一幀的一定范圍內(nèi)

8、搜索最優(yōu)匹配， 并認(rèn)為本塊就是從上一 幀最優(yōu)匹配塊位置處平移過(guò)來(lái)的。設(shè)可能的最大偏移矢量為 (r,r) ，則搜索范圍 為(p+2r) (q+2r) 。圖 2 示出了待匹配塊與搜索區(qū)的幾何位置關(guān)系。 隨著圖像壓 縮編碼技術(shù)的發(fā)展和對(duì)壓縮效率愈來(lái)愈高的要求， 在很多場(chǎng)合均要求運(yùn)動(dòng)矢量精 確到亞象素元級(jí)。圖2 待匹配塊與搜索區(qū)的幾何位置關(guān)系塊的大小受到兩個(gè)矛盾的約束 : 塊大時(shí)，塊內(nèi)各像素作平移運(yùn)動(dòng)的假設(shè)易被 破壞，影響估計(jì)的精度；塊小時(shí)，則易受噪聲影響，估計(jì)不夠可靠，而且運(yùn)算量 增加，所需傳輸?shù)母郊有畔⒁苍黾恿恕?因此必須恰到好處地選擇塊的大小， 以做N 1 N 1Fc(u,v) c(u)c(v)

9、x 0 y 02.1)N 1N 1f (x,y) c(x)c(y)Fc( , v)cos(u 0 v 0 x(2u 1)x(22Nu 1)cos(y(2v 1)2N2.2)c(k)1/ N(k 0)2/N (1 k N 1)到兩者兼顧。 目前的視頻壓縮標(biāo)準(zhǔn)， 如 H.26x 和 MPEG等，一般均以 1616 大小 的塊作為塊匹配單元，這是一個(gè)已為實(shí)踐證明的較好的折衷結(jié)果。2.2離散余弦變換 (DCT)離散余弦變換(DCT)是利用傅立葉變換的對(duì)稱性 , 將圖象描述為不同幅值和 頻率的正弦值之和的形式；是圖象壓縮 JPEG壓縮算法的基礎(chǔ)和核心。是一個(gè)無(wú) 信號(hào)損失的雙向數(shù)學(xué)過(guò)程。通過(guò) DCT變換能

10、去除視頻信號(hào)的空間冗余。一個(gè) NN 矩陣的二維 DCT定義如下：(1)正變換f (x,y)cos( u(22Nx 1)cos( v(22Ny 1)2N 2N(2)反變換其中2.3塊匹配的準(zhǔn)則運(yùn)動(dòng)估計(jì)算法中常用的匹配準(zhǔn)則有三種，即最小絕對(duì)差 (擬 D) 、最小均方誤 差 (MSE)和歸一化互相關(guān)函數(shù) (NCCF)。分別定義如下：1、互相關(guān)函數(shù) (Cross-Correlation Function,簡(jiǎn)稱 CCF)s(n1,n2,k) s(n1 d1,n2 d2,k 1) n1,n2 Bs(n1,n2,k)2s(n1 d1,n2 d2,k 1)2n1,n2 B n1,n2 B其中， p n1,n2

11、 p 。(2.3)式是計(jì)算當(dāng)前幀中 (X Y)矩陣域與前幀相對(duì)應(yīng) 的(X +2P, Y +2P)矩陣區(qū)域互相關(guān)函數(shù)。2、均方誤差函數(shù) (MSE)MSE(d1,d2)1s(n1,n2,k) s(n1 d1,n2 d2,k 1)2 ( n1,n 2 B)N1N2.4)MAD (d1,d2 )1N1N2 (n1,n2 B)s(n1,n2,k) s(n1 d1,n2 d2,k 1)2.5)T(n1,n2,d1,d2)1(s(n1,n2,k) s(n1 d1,n20(Otherwise )d2,k 1) t )2.6)2.7)其中， p n1,n2 p 。(2.4)式是計(jì)算相鄰幀相對(duì)應(yīng) (X Y)矩形區(qū)

12、域的最小 均方誤差。這是一種非線性測(cè)量，能較好地跟蹤圖像的協(xié)方差模型。3、絕對(duì)平均誤差函數(shù) (MAD)(2.5) 式是最簡(jiǎn)單的匹配函數(shù)，用它計(jì)算相鄰幀的絕對(duì)平均誤差。在 (2.3) ， (2.4) 和(2.5) 式中都在尋找 (x ,y) ，得到一個(gè)最小失真矢量。 (2.3) 式是計(jì)算一 個(gè)最大的自相關(guān)函數(shù) CCF (x ,y) ，而 (2.4) 和(2.5) 式是計(jì)算最小的均方誤差和 絕對(duì)平均誤差函數(shù) MSE (x, y) 和 MAD (x, y) 。由于塊匹配算法計(jì)算簡(jiǎn)單，能夠 實(shí)時(shí)處理，近幾年獲得廣泛的應(yīng)用4、最大像素匹配統(tǒng)計(jì) (Maximum Pixels Counting ，MPC)

13、 還有一種匹配準(zhǔn)則叫做最大匹配像素?cái)?shù) (MPC：Matching-Pixel Count) 準(zhǔn)則。 首先根據(jù)下式將當(dāng)前塊中的像素分成匹配像素和不匹配像素：MPC(d1,d2) T(n1,n2,d1,d2) (n1,n2 B)T(n1,n2,d1,d2) 1，則位置 (n1,n2,d1,d2) 的像素為匹配像素，否則為不匹配 像素。2.4塊匹配的搜索算法前兩節(jié)的分析可以發(fā)現(xiàn)，在塊匹配方法中最重要的兩個(gè)問(wèn)題是如何確定(1) 判別兩個(gè)子塊匹配的準(zhǔn)則 :(2) 計(jì)算量最小的搜索方法。 對(duì)這兩個(gè)問(wèn)題的不同解決方案構(gòu)成了不同的搜索算法。下面將對(duì)一些典 型的塊匹配快速搜索算法進(jìn)行逐次介紹。2.4.12.4.

14、1 完全搜索法(1)算法思想全搜索法(Full Search Method,FS)也稱為窮盡搜索法，是對(duì)(p+2r) (q+2r) 搜索范圍內(nèi)所有可能的候選位置計(jì)算 MAD(i , j) 值，從中找出最小 MAD，其對(duì)應(yīng) 偏移量即為所求運(yùn)動(dòng)矢量。此算法雖計(jì)算量大，但最簡(jiǎn)單、可靠，找到的必為全 局最優(yōu)點(diǎn)。(2)FS算法描述FS算法描述如下 :Step 1: 從原點(diǎn)出發(fā)，按順時(shí)針?lè)较蛴山斑h(yuǎn)，在逐個(gè)像素處計(jì)算MAD值，直到遍歷搜索范圍內(nèi)所有的點(diǎn) .Step 2: 在所有點(diǎn) MAD中找到最小值，該點(diǎn)所在位置即對(duì)應(yīng)最佳運(yùn)動(dòng)矢量。(3)FS算法的分析FS 算法是最簡(jiǎn)單、最原始的塊匹配算法，由于可靠，且能

15、夠得到全局最優(yōu) 的結(jié)果，通常是其它算法性能比較的標(biāo)準(zhǔn)， 但它的計(jì)算量的確很大， 這就限制了 在需要實(shí)時(shí)壓縮場(chǎng)合的應(yīng)用，所以有必要進(jìn)一步研究其它快速算法。2.4.22.4.2 二維對(duì)數(shù)法二維 對(duì) 數(shù)(Two-Dimensional Logarithmic TDL)搜 索法 由 J.R.Jain 和 A.K.Jain 提出，它開(kāi)創(chuàng)了快速算法的先例，分多個(gè)階段搜索，逐次減小搜索范 圍直到不能再小而結(jié)束。(1)TDL算法描述 TDL算法的基本思想是從原點(diǎn)開(kāi)始，以“十”字形分布的五個(gè)點(diǎn)構(gòu)成每次搜 索的點(diǎn)群，通過(guò)快速搜索跟蹤最小塊誤差MBD(Mininum Block Distortion) 點(diǎn)(MAD值

16、最小的點(diǎn) ) ，算法具體描述如下 :Step 1: 從原點(diǎn)開(kāi)始，選取一定的步長(zhǎng)，在以十字形分布的五個(gè)點(diǎn)處進(jìn)行塊 匹配計(jì)算并比較。Step 2: 若 MBD點(diǎn)在邊緣四個(gè)點(diǎn)處，則以該點(diǎn)作為中心點(diǎn)，保持步長(zhǎng)不變， 重新搜索十字形分布的五個(gè)點(diǎn)；若 MBD點(diǎn)位于中心點(diǎn)，則保持中心點(diǎn)位置不變，將步長(zhǎng)減半，構(gòu)成十字形點(diǎn)群，在五個(gè)點(diǎn)處計(jì)算Step 3: 在中心及周圍 8 個(gè)點(diǎn)處找出 MBD點(diǎn)，若步長(zhǎng)為 1，該點(diǎn)所在位置即 對(duì)應(yīng)最佳運(yùn)動(dòng)矢量，算法結(jié)束；否則重復(fù) Step 2 。具體的一個(gè)搜索例子請(qǐng)參考圖 3。圖中每個(gè)點(diǎn)上的數(shù)字表明了每個(gè)階段搜索 時(shí)計(jì)算的候選塊的位置。圖 3 TDL 搜索過(guò)程（2）TDL算法的分

17、析TDL算法搜索時(shí)，最大搜索點(diǎn)數(shù)為 2+71og2 r ，若發(fā)現(xiàn)新的十字形點(diǎn)群的中 心點(diǎn)位于搜索區(qū)的邊緣， 則步長(zhǎng)也減半， 后來(lái)有人提出應(yīng)該在搜索的每個(gè)階段都 將步長(zhǎng)減半 , 所有這些改動(dòng)都是為了使算法搜索范圍很快變小，提高收斂速度。 TDL算法的前提是假設(shè)搜索區(qū)內(nèi)只有一個(gè)谷點(diǎn)，如果搜索區(qū)內(nèi)存在多個(gè)谷點(diǎn)時(shí)， 該方法找到的可能是局部最小點(diǎn)。2.4.32.4.3 三步搜索法三步搜索（Three Step Search,TSS）法與二維對(duì)數(shù)法類似，是 T.KOGA等人提 出的，由于簡(jiǎn)單、健壯、性能良好的特點(diǎn)，為人們所重視。 若最大搜索長(zhǎng)度為 7， 搜索精度取 1個(gè)像素，則步長(zhǎng)為 4,2,1 ，共需三

18、步即可滿足要求，因此而得名三 步法。（1） TSS 算法描述 TSS算法的基本思想是采用一種由粗到細(xì)的搜索模式，從原點(diǎn)開(kāi)始，按一定 步長(zhǎng)取周圍 8 個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，然后進(jìn)行匹配計(jì)算，跟蹤最小塊誤差MBD點(diǎn)算法具體描述如下Step 1: 從原點(diǎn)開(kāi)始，選取最大搜索長(zhǎng)度的一半為步長(zhǎng)，在周圍距離步長(zhǎng)的 8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較。Step 2: 將步長(zhǎng)減半，中心點(diǎn)移到上一步的 MBD點(diǎn)，重新在周圍距離步長(zhǎng)的 8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較。Step 3: 在中心及周圍 8 個(gè)點(diǎn)處找出 MBD點(diǎn)，若步長(zhǎng)為 1，該點(diǎn)所在位置即 對(duì)應(yīng)最佳運(yùn)動(dòng)矢量，算法結(jié)束；否則重復(fù) Step 2 。一個(gè)可能的搜

19、索過(guò)程如圖 4 所示，圖中每個(gè)點(diǎn)上的數(shù)字表明了每個(gè)階段搜索 時(shí)計(jì)算的候選塊的位置。圖 4 三步搜索步驟(2)TSS算法的分析TSS算法搜索時(shí)，整個(gè)過(guò)程采用了統(tǒng)一的搜索模板 (Search Pattern) ，使得 第一步的步長(zhǎng)過(guò)大，容易引起誤導(dǎo)，從而對(duì)小運(yùn)動(dòng)效率較低。最大搜索點(diǎn)數(shù)為 1 1og2r，當(dāng)搜索范圍大于 7 時(shí)，僅用 3 步是不夠的，搜索步數(shù)的一般表達(dá)式為 log 2(p+1) ?？傮w說(shuō)來(lái)，三步法是一種較典型的快速搜索算法，所以被研究的較 多，后來(lái)又相繼有許多改進(jìn)的新三步法出現(xiàn)，改進(jìn)了它對(duì)小運(yùn)動(dòng)的估計(jì)性能。2.4.42.4.4 直角搜索法直角搜索法 (Orthogonal Searc

20、h Algorithm ， OSA)是二維對(duì)數(shù)法和三步法的 一種混合，由 Purl 提出 is ，為了找到最佳匹配點(diǎn)搜索過(guò)程由垂直和水平兩個(gè) 階段交替進(jìn)行，逐步減小步長(zhǎng)。(1)OSA算法描述TSS算法實(shí)際上仍是 TDL和 TSS的模式，但更加簡(jiǎn)化，使每次只沿水平或垂 直方向在三個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算，算法具體描述如下 :Step 1: 初始化選取最大搜索長(zhǎng)度的一半為步長(zhǎng)，先在水平方向距離原點(diǎn)步 長(zhǎng)的位置處進(jìn)行塊匹配計(jì)算并比較，然后將中心點(diǎn)移到 MBD點(diǎn)。Step 2: 在垂直方向距離當(dāng)前中心點(diǎn)步長(zhǎng)處選取兩點(diǎn)進(jìn)行塊匹配， 并找到 MBD 點(diǎn)。Step 3: 若步長(zhǎng)為 1，該點(diǎn)即為最優(yōu)點(diǎn)，算法結(jié)束

21、; 否則，將步長(zhǎng)減半，改變 中心點(diǎn)位置，重復(fù) Step1 。圖 4 是一個(gè)具體的搜索例子，圖中每個(gè)點(diǎn)上的數(shù)字表明了每個(gè)階段搜索時(shí) 計(jì)算的候選塊的位置。圖 5 OSA 搜索過(guò)程（2）OSA算法分析OSA算法每一步可以看成是由水平和垂直兩個(gè)階段組成， 直到步長(zhǎng)變?yōu)?1 時(shí) 視為算法結(jié)束。 由于每次計(jì)算的匹配點(diǎn)數(shù)太少， 不能顧及各個(gè)方向， 雖然速度較 快，但得到局部最優(yōu)的可能性進(jìn)一步擴(kuò)大。2.4.52.4.5 交叉法1990 年， Ghanbari 提出了交叉搜索算法 (Cross Search Algorithm,CSA),它也是在 TDL和 TSS基礎(chǔ)上為進(jìn)一步減少計(jì)算量而發(fā)展起來(lái)的快速搜索法。

22、（1）CSA描述CSA 的基本思想是從原點(diǎn)開(kāi)始，以“ X”字形分布的五個(gè)點(diǎn)構(gòu)成每次搜索的 點(diǎn)群，以 TDL的搜索方法檢測(cè) MBD點(diǎn)，僅在最后一步采用“十”字形點(diǎn)群。算法 具體描述如下 :Step 1: 從原點(diǎn)開(kāi)始，選取最大搜索長(zhǎng)度的一半為步長(zhǎng)，在以“ X”字形分布 的五個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較，然后移動(dòng)中心點(diǎn)。Step 2: 以上一步的 MBD點(diǎn)為中心， 步長(zhǎng)減半，繼續(xù)做“X”字形的 S點(diǎn)搜索。 若步長(zhǎng)大于 1，則重復(fù) Step 2; 若步長(zhǎng)為 1，則進(jìn)行 Step3。Step 3: 最后一步根據(jù) MBD點(diǎn)的位置，分別做“ +”字形和“ X”字形搜索 : 若上一步 MBD點(diǎn)處于中心點(diǎn)、左下角

23、或右上角，做“十”字形搜索；若上一步 MBD點(diǎn)處于左上角或右下角，做“ X”字形搜索。由當(dāng)前 MBD點(diǎn)得到最佳運(yùn)動(dòng)矢 量，算法結(jié)束。圖 6 是 CSA搜索的一個(gè)具體實(shí)例，圖中每個(gè)點(diǎn)上的數(shù)字表明了每個(gè)階段搜索時(shí)計(jì)算的候選塊的位置，第三步箭頭說(shuō)明了兩種不同的搜索模式圖 6 CSA 搜索過(guò)程（2）CSA分析CSA的最大搜索點(diǎn)數(shù)為 5+41og2r，搜索速度很快， 但是運(yùn)動(dòng)補(bǔ)償?shù)男Ч凰?太好。如圖 6 右圖所示，有些點(diǎn)根本就不可能成為候選點(diǎn)，或者說(shuō)，在搜索區(qū)域 的邊界上有四分之一的點(diǎn) CSA沒(méi)有考慮，因此它不適用于較復(fù)雜的運(yùn)動(dòng)。除此以外，還有菱形搜索法和四步搜索法，就不一一介紹了103 3設(shè)計(jì)實(shí)現(xiàn)壁

24、紙 car1.BMP)壁紙 car2.BMP)fp=0figure,imshow(f2),title(target)figure,imshow(f1),title(anchor)N=16;R=16height=256width=256for i=1:N:height-N+1for j=1:N:width-N+1MAD_min=256*N*Ndy=0;dx=0;for k= -R:1:Rfor l= -R:1:Rif i+kheight-NMAD=256*N*Nelse if j+lwidth-NMAD=256*N*NelseMAD=sum(sum(abs(double(f1(i:i+N-1,j

25、:j+N-1)-double(f2(i+k:i+k+N-1,j+l:j+l+N-1) endif MADMAD_minMAD_min=MADdy=k;dx=l;end;end;end;1112fp(i:i+N-1,j:j+N-1)= f2(i+dy:i+dy+N-1,j+dx:j+dx+N-1) iblk=floor(i-1)/N+1); jblk=floor(j-1)/N+1);mvx(iblk,jblk)=dx;mvy(iblk,jblk)=dy;end;end;figure,imshow(uint8(fp),title(predict); X,Y=meshgrid(N/2:N:256-N/2);Y=256-Y; figure,quiver(X,