基于塊匹配算法的運動估計

基于塊匹配算法的運動估計摘要：本文首先介紹了運動估計和塊匹配的概念和思想，然后詳細(xì)介紹了塊匹配的搜索算法。最后根據(jù)塊匹配算法的運動估計給出了一個設(shè)計。關(guān)鍵字：運動估計，塊匹配，算法1研究背景隨著現(xiàn)代信息社會對通信業(yè)務(wù)要求的不斷增長，圖像通信與通信網(wǎng)容量的矛盾日益突出，尤其是具有龐大數(shù)據(jù)量的視頻圖像通信，更是很難傳輸和存儲，極大的制約了圖像通信的開展。例如，按CCIR601建議，普通質(zhì)量的電視信號數(shù)字視頻的碼率約為216Mbit/s，而高清晰度電視HDTV那么在1.2Gb/s以上，如果沒有高效率的壓縮技術(shù)，那么難以傳輸和存儲。而運動檢測與估計不僅是軍事領(lǐng)域中目標(biāo)探測與跟蹤的有效技術(shù)之一，同時也是視頻圖象編碼與壓縮的常用方法與核心技術(shù)。因此，該項研究對于復(fù)雜背景下的目標(biāo)探測以及視頻處理均具有重要的應(yīng)用價值。運動估計和運動補償是緊密聯(lián)系的，它是視頻圖像壓縮編碼中使用的一項核心技術(shù)，很好的解決了視頻圖像中時間冗余的問題，經(jīng)驗說明，實用化的壓縮方法可以將運動圖像數(shù)據(jù)壓縮30倍而不失真。運動估計技術(shù)主要分為兩大類:象素遞歸法和塊匹配法?？紤]到計算復(fù)雜度和實時性要求，塊匹配法已成為目前最常用的方法。顯然，要想獲得好的運動補償，關(guān)鍵是要有準(zhǔn)確的運動估計，因此運動估計算法的研究成為視頻壓縮算法的研究重點。運動估計研究的主要內(nèi)容就是如何快速、有效的獲得有足夠精度的運動矢量。即把前一幀的運動局部根據(jù)運動矢量補過來，同時用其它方法得到其剩余的不同局部的過程稱為運動補償(MotionCompensation,MC)。就這樣，采用運動估計和補償可以有效地去除視頻信號在時間方向的重復(fù)信息，到達(dá)壓縮的目的。其中，在這方面的一種有效方法就是塊匹配運動估計BMME(Block-MatchingMotionEstimation),它目前已被許多視頻編碼標(biāo)準(zhǔn)所采納。為了提高搜索速度和效率，目前研究最多的是基于塊匹配(BlockMatching,BM)的快速搜索算法，例如三步法，四步法，二維對數(shù)法，菱形法等。隨著計算機網(wǎng)絡(luò)的普及和開展，很多信息可以通過網(wǎng)絡(luò)實現(xiàn)共享。形色兼具的視頻信息在網(wǎng)絡(luò)傳輸?shù)男畔⒅兴紦?jù)的比例也越來越高。但由于視頻信息本身十分龐大，限制了其在網(wǎng)絡(luò)中的傳播速度。于是視頻信息的壓縮成為視頻傳輸?shù)囊粋€重要環(huán)節(jié)。數(shù)字視頻信息是由數(shù)字圖像的時間序列構(gòu)成的，每一幅數(shù)字圖像稱為一幀。視頻編碼的一個主(frame)要目的就是在保證一定重構(gòu)質(zhì)量的前提下，以盡量少的比特數(shù)來表征視頻信息。視頻編碼是視頻壓縮的關(guān)鍵技術(shù)。視頻編碼與的原理是：由于表示圖像和視頻信息所需的大量的數(shù)據(jù)往往是高度相關(guān)的，這些相關(guān)性會引起信息的冗余，因此可以通過去除這些冗余信息來實現(xiàn)對視頻數(shù)據(jù)的壓縮。靜止圖像的壓縮是在保持重建圖像質(zhì)量可以接收的同時，盡量去除圖像本身存在的空間冗余，而視頻信號的壓縮，除了去除空間冗余之外，還可以通過去除時間冗余到達(dá)較高的壓縮比。運動估計技術(shù)是視頻圖像壓縮編碼中使用的一項核心技術(shù)，很好的解決了視頻圖像中時間冗余的問題，運動估計技術(shù)主要分為兩大類:象素遞歸法和塊匹配算法?？紤]到計算復(fù)雜度和實時性要求，塊匹配法已成為目前最常用的方法。2實驗原理如圖1所示,運動估計的根本思想是將圖像序列的每一幀圖像分成許多互不重疊的宏塊,并假設(shè)塊內(nèi)各像素只作相等的平移,然后對于當(dāng)前幀中的每一塊到前一幀或后一幀某一給定搜索范圍內(nèi)根據(jù)一定的匹配準(zhǔn)那么找出與當(dāng)前塊最相似的塊,即匹配塊,由匹配塊與當(dāng)前塊的相對位置計算出運動位移,所得運動位移即為當(dāng)前塊的運動矢量。宏塊大小為M×N,一般取16×16。搜索范圍一般由最大偏移矢量來決定,設(shè)可能的最大偏移矢量為(dxmax,dymax),那么搜索范圍為(M+2dxmax)×(N+2dymax)。圖1運動估計根本原理2.1塊匹配介紹按照一般的想法，運動估計應(yīng)當(dāng)首先將圖像中靜止背景和運動物體區(qū)分開來，然后對運動物體的實際位移進行估計。但塊匹配方法卻不是這樣，它的思想是將圖像劃分為許多互不重疊的子塊(例如16×16)，并認(rèn)為子塊內(nèi)所有像素的位移量都相同。這意味著每個子塊被視為運動物體。假設(shè)在圖像序列中，t時刻對應(yīng)于第k幀圖像，t-τ時刻對應(yīng)于第k-1幀圖像。對于k幀中的一個子塊，在k-1幀中尋找與其最相似的子塊，這個過程稱為尋找匹配塊，并認(rèn)為該匹配塊在k-1幀中所處的位置就是k幀子塊位移前的位置，這種位置的變化用運動矢量D來表示。將圖像分割成M×N的小塊，并假設(shè)塊內(nèi)象素作相同的運動，且只作平移運動。雖然實際上塊內(nèi)各點運動不一定相同，也不定只有平移運動，但當(dāng)M×N較小時，上述假設(shè)可近似成立。這樣做的目的只是為了簡化運算。塊匹配法對當(dāng)前幀圖像的每一塊，在上一幀的一定范圍內(nèi)搜索最優(yōu)匹配，并認(rèn)為本塊就是從上一幀最優(yōu)匹配塊位置處平移過來的。設(shè)可能的最大偏移矢量為(r,r)，那么搜索范圍為(p+2r)×(q+2r)。圖2示出了待匹配塊與搜索區(qū)的幾何位置關(guān)系。隨著圖像壓縮編碼技術(shù)的開展和對壓縮效率愈來愈高的要求，在很多場合均要求運動矢量精確到亞象素元級。圖2待匹配塊與搜索區(qū)的幾何位置關(guān)系塊的大小受到兩個矛盾的約束:塊大時，塊內(nèi)各像素作平移運動的假設(shè)易被破壞，影響估計的精度；塊小時，那么易受噪聲影響，估計不夠可靠，而且運算量增加，所需傳輸?shù)母郊有畔⒁苍黾恿?。因此必須恰到好處地選擇塊的大小，以做到兩者兼顧。目前的視頻壓縮標(biāo)準(zhǔn)，如H.26x和MPEG等，一般均以16×16大小的塊作為塊匹配單元，這是一個已為實踐證明的較好的折衷結(jié)果。2.2離散余弦變換(DCT)離散余弦變換〔DCT〕是利用傅立葉變換的對稱性,將圖象描述為不同幅值和頻率的正弦值之和的形式；是圖象壓縮JPEG壓縮算法的根底和核心。是一個無信號損失的雙向數(shù)學(xué)過程。通過DCT變換能去除視頻信號的空間冗余。一個N×N矩陣的二維DCT定義如下：(1)正變換〔2.1〕(2)反變換〔2.2〕其中2.3塊匹配的準(zhǔn)那么運動估計算法中常用的匹配準(zhǔn)那么有三種，即最小絕對差(擬D)、最小均方誤差(MSE)和歸一化互相關(guān)函數(shù)(NCCF)。分別定義如下：1、互相關(guān)函數(shù)(Cross-CorrelationFunction,簡稱CCF)〔2.3〕其中，。(2.3)式是計算當(dāng)前幀中(X×Y)矩陣域與前幀相對應(yīng)的(X+2P,Y+2P)矩陣區(qū)域互相關(guān)函數(shù)。2、均方誤差函數(shù)(MSE)〔2.4〕其中，。(2.4)式是計算相鄰幀相對應(yīng)(X×Y)矩形區(qū)域的最小均方誤差。這是一種非線性測量，能較好地跟蹤圖像的協(xié)方差模型。3、絕對平均誤差函數(shù)(MAD)〔2.5〕(2.5)式是最簡單的匹配函數(shù)，用它計算相鄰幀的絕對平均誤差。在(2.3)，(2.4)和(2.5)式中都在尋找(x,y)，得到一個最小失真矢量。(2.3)式是計算一個最大的自相關(guān)函數(shù)CCF(x,y)，而(2.4)和(2.5)式是計算最小的均方誤差和絕對平均誤差函數(shù)MSE(x,y)和MAD(x,y)。由于塊匹配算法計算簡單，能夠?qū)崟r處理，近幾年獲得廣泛的應(yīng)用。4、最大像素匹配統(tǒng)計(MaximumPixelsCounting，MPC)還有一種匹配準(zhǔn)那么叫做最大匹配像素數(shù)(MPC：Matching-PixelCount)準(zhǔn)那么。首先根據(jù)下式將當(dāng)前塊中的像素分成匹配像素和不匹配像素：〔2.6〕〔2.7〕，那么位置的像素為匹配像素，否那么為不匹配像素。2.4塊匹配的搜索算法前兩節(jié)的分析可以發(fā)現(xiàn)，在塊匹配方法中最重要的兩個問題是如何確定:(1)判別兩個子塊匹配的準(zhǔn)那么:(2)計算量最小的搜索方法。對這兩個問題的不同解決方案構(gòu)成了不同的搜索算法。下面將對一些典型的塊匹配快速搜索算法進行逐次介紹。2.4.1完全搜索法〔1〕算法思想全搜索法(FullSearchMethod,FS)也稱為窮盡搜索法，是對(p+2r)×(q+2r)搜索范圍內(nèi)所有可能的候選位置計算MAD(i,j)值，從中找出最小MAD，其對應(yīng)偏移量即為所求運動矢量。此算法雖計算量大，但最簡單、可靠，找到的必為全局最優(yōu)點?！?〕FS算法描述FS算法描述如下:Step1:從原點出發(fā)，按順時針方向由近及遠(yuǎn)，在逐個像素處計算MAD值，直到遍歷搜索范圍內(nèi)所有的點.Step2:在所有點MAD中找到最小值，該點所在位置即對應(yīng)最正確運動矢量。〔3〕FS算法的分析FS算法是最簡單、最原始的塊匹配算法，由于可靠，且能夠得到全局最優(yōu)的結(jié)果，通常是其它算法性能比擬的標(biāo)準(zhǔn)，但它的計算量確實很大，這就限制了在需要實時壓縮場合的應(yīng)用，所以有必要進一步研究其它快速算法。2.4.2二維對數(shù)法二維對數(shù)(Two-DimensionalLogarithmicTDL)搜索法由J.R.Jain和A.K.Jain提出，它開創(chuàng)了快速算法的先例，分多個階段搜索，逐次減小搜索范圍直到不能再小而結(jié)束。〔1〕TDL算法描述TDL算法的根本思想是從原點開始，以“十〞字形分布的五個點構(gòu)成每次搜索的點群，通過快速搜索跟蹤最小塊誤差MBD(MininumBlockDistortion)點(MAD值最小的點)，算法具體描述如下:Step1:從原點開始，選取一定的步長，在以十字形分布的五個點處進行塊匹配計算并比擬。Step2:假設(shè)MBD點在邊緣四個點處，那么以該點作為中心點，保持步長不變，重新搜索十字形分布的五個點；假設(shè)MBD點位于中心點，那么保持中心點位置不變，將步長減半，構(gòu)成十字形點群，在五個點處計算。Step3:在中心及周圍8個點處找出MBD點，假設(shè)步長為1，該點所在位置即對應(yīng)最正確運動矢量，算法結(jié)束；否那么重復(fù)Step2。具體的一個搜索例子請參考圖3。圖中每個點上的數(shù)字說明了每個階段搜索時計算的候選塊的位置。圖3TDL搜索過程〔2〕TDL算法的分析TDL算法搜索時，最大搜索點數(shù)為2+71og2r，假設(shè)發(fā)現(xiàn)新的十字形點群的中心點位于搜索區(qū)的邊緣，那么步長也減半，后來有人提出應(yīng)該在搜索的每個階段都將步長減半,所有這些改動都是為了使算法搜索范圍很快變小，提高收斂速度。TDL算法的前提是假設(shè)搜索區(qū)內(nèi)只有一個谷點，如果搜索區(qū)內(nèi)存在多個谷點時，該方法找到的可能是局部最小點。2.4.3三步搜索法三步搜索(ThreeStepSearch,TSS)法與二維對數(shù)法類似，是T.KOGA等人提出的，由于簡單、健壯、性能良好的特點，為人們所重視。假設(shè)最大搜索長度為7，搜索精度取1個像素，那么步長為4,2,1，共需三步即可滿足要求，因此而得名三步法。TSS算法描述TSS算法的根本思想是采用一種由粗到細(xì)的搜索模式，從原點開始，按一定步長取周圍8個點構(gòu)成每次搜索的點群，然后進行匹配計算，跟蹤最小塊誤差MBD點算法具體描述如下:Step1:從原點開始，選取最大搜索長度的一半為步長，在周圍距離步長的8個點處進行塊匹配計算并比擬。Step2:將步長減半，中心點移到上一步的MBD點，重新在周圍距離步長的8個點處進行塊匹配計算并比擬。Step3:在中心及周圍8個點處找出MBD點，假設(shè)步長為1，該點所在位置即對應(yīng)最正確運動矢量，算法結(jié)束；否那么重復(fù)Step2。一個可能的搜索過程如圖4所示，圖中每個點上的數(shù)字說明了每個階段搜索時計算的候選塊的位置。圖4三步搜索步驟〔2〕TSS算法的分析TSS算法搜索時，整個過程采用了統(tǒng)一的搜索模板(SearchPattern)，使得第一步的步長過大，容易引起誤導(dǎo)，從而對小運動效率較低。最大搜索點數(shù)為1＋1og2r，當(dāng)搜索范圍大于7時，僅用3步是不夠的，搜索步數(shù)的一般表達(dá)式為log2(p+1)。總體說來，三步法是一種較典型的快速搜索算法，所以被研究的較多，后來又相繼有許多改良的新三步法出現(xiàn)，改良了它對小運動的估計性能。直角搜索法直角搜索法(OrthogonalSearchAlgorithm，OSA)是二維對數(shù)法和三步法的一種混合，由Purl提出[is]，為了找到最正確匹配點搜索過程由垂直和水平兩個階段交替進行，逐步減小步長?！?〕OSA算法描述TSS算法實際上仍是TDL和TSS的模式，但更加簡化，使每次只沿水平或垂直方向在三個點處進行塊匹配計算，算法具體描述如下:Step1:初始化選取最大搜索長度的一半為步長，先在水平方向距離原點步長的位置處進行塊匹配計算并比擬，然后將中心點移到MBD點。Step2:在垂直方向距離當(dāng)前中心點步長處選取兩點進行塊匹配，并找到MBD點。Step3:假設(shè)步長為1，該點即為最優(yōu)點，算法結(jié)束;否那么，將步長減半，改變中心點位置，重復(fù)Step1。圖4是一個具體的搜索例子，圖中每個點上的數(shù)字說明了每個階段搜索時計算的候選塊的位置。圖5OSA搜索過程〔2〕OSA算法分析OSA算法每一步可以看成是由水平和垂直兩個階段組成，直到步長變?yōu)?時視為算法結(jié)束。由于每次計算的匹配點數(shù)太少，不能顧及各個方向，雖然速度較快，但得到局部最優(yōu)的可能性進一步擴大。交叉法1990年，Ghanbari提出了交叉搜索算法(CrossSearchAlgorithm,CSA),它也是在TDL和TSS根底上為進一步減少計算量而開展起來的快速搜索法?！?〕CSA描述CSA的根本思想是從原點開始，以“X〞字形分布的五個點構(gòu)成每次搜索的點群，以TDL的搜索方法檢測MBD點，僅在最后一步采用“十〞字形點群。算法具體描述如下:Step1:從原點開始，選取最大搜索長度的一半為步長，在以“X〞字形分布的五個點處進行塊匹配計算并比擬，然后移動中心點。Step2:以上一步的MBD點為中心，步長減半，繼續(xù)做“X〞字形的S點搜索。假設(shè)步長大于1，那么重復(fù)Step2;假設(shè)步長為1，那么進行Step3。Step3:最后一步根據(jù)MBD點的位置，分別做“+〞字形和“X〞字形搜索:假設(shè)上一步MBD點處于中心點、左下角或右上角，做“十〞字形搜索；假設(shè)上一步MBD點處于左上角或右下角，做“X〞字形搜索。由當(dāng)前MBD點得到最正確運動矢量，算法結(jié)束。圖6是CSA搜索的一個具體實例，圖中每個點上的數(shù)字說明了每個階段搜索時計算的候選塊的位置，第三步箭頭說明了兩種不同的搜索模式。圖6CSA搜索過程〔2〕CSA分析CSA的最大搜索點數(shù)為5+41og2r，搜索速度很快，但是運動補償?shù)男Ч凰闾?。如圖6右圖所示，有些點根本就不可能成為候選點，或者說，在搜索區(qū)域的邊界上有四分之一的點CSA沒有考慮，因此它不適用于較復(fù)雜的運動。除此以外，還有菱形搜索法和四步搜索法，就不一一介紹了。3設(shè)計實現(xiàn)f2=imread('G:\壁紙\car1.BMP')f1=imread('G:\壁紙\car2.BMP')fp=0figure,imshow(f2),title('target')figure,imshow(f1),title('anchor')N=16;R=16height=256width=256fori=1:N:height-N+1forj=1:N:width-N+1MAD_min=256*N*Ndy=0;dx=0;fork=-R:1:Rforl=-R:1:Rifi+k<1MAD=256*N*Nelseifi+k>height-NMAD=256*N*Nelseifj+l<1MAD=256*N*Nelseifj+l>width-NMAD=256*N*NelseMAD=sum(sum(abs(double(f1(i:i+N-1,j:j+N-1))-double(f2(i+k:i+k+N-1,j+l:j+l+N-1)))))endifMAD<MAD_minMAD_min=MADdy=k;dx=l;end;end;end;fp(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,Y,mvx,mvy),title('motionvector');diff=abs(double(f1)-fp);figure,imshow(uint8(d