【文章內(nèi)容簡(jiǎn)介】 對(duì)程序各模塊一一實(shí)現(xiàn)； 第 5 章：算法的驗(yàn)證和評(píng)價(jià)。對(duì)算法進(jìn)行測(cè)試，對(duì)結(jié)果進(jìn)行分析； 第 6 章：結(jié)論。本章對(duì)全文工作以及畢業(yè)收獲進(jìn)行總結(jié)，指出了還需改進(jìn)的地方。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 6 2 塊匹配算法介紹及分析 本章主要介紹塊匹配算法的各個(gè)模塊，及各模塊所用到的算法。 運(yùn)動(dòng)估計(jì) 運(yùn)動(dòng)估計(jì)已發(fā)展得較為成熟，最常用于人群監(jiān)控與視頻壓縮編碼。 基于塊的運(yùn)動(dòng)估計(jì)和補(bǔ)償是視頻編碼中最通用的算法。它把圖像域分割成互相不重疊的稱(chēng)為塊的小區(qū)域，并且假定每一個(gè)塊內(nèi)的運(yùn)動(dòng)都可以用一個(gè)簡(jiǎn)單的參數(shù)模型特征化，如果快足夠小，那么這種模型是相當(dāng)合理 的。目前這種方法被廣泛用于視頻標(biāo)準(zhǔn)變換運(yùn)動(dòng)補(bǔ)償濾波和采用基于塊的運(yùn)動(dòng)補(bǔ)償進(jìn)行的數(shù)字視頻壓縮 [11~12] 。 在一幅幅復(fù)雜的人群圖像中，如果依靠每個(gè)步行者的個(gè)體信息來(lái)估計(jì)人群總體的運(yùn)動(dòng)，必須要分離出每個(gè)個(gè)體的運(yùn)動(dòng)。但要做到這點(diǎn)并不容易，因?yàn)樵陂_(kāi)放的空間中，一個(gè)步行者可能向各個(gè)方向移動(dòng)，且步行者的身體各部分的移動(dòng)方式也各不相同，進(jìn)而，當(dāng)人群密度較大，個(gè)體之間有相互遮擋時(shí)，這就變得更加困難，甚至是不可能的。因此，本文提出基于塊匹配的人群運(yùn)動(dòng)估計(jì)（ BMA）。這種方法由于實(shí)現(xiàn)較簡(jiǎn)單且容易而受到廣泛關(guān)注。 BMA 并不 借助人群中個(gè)體的信息，而是通過(guò)統(tǒng)計(jì)視頻中各宏塊的運(yùn)動(dòng)矢量估計(jì)出人群整體的運(yùn)動(dòng) [13] 。 塊匹配基本思想 基于塊匹配法的運(yùn)動(dòng)估計(jì)的基本思想就是將當(dāng)前幀分成互不重疊的大小為 MN 的宏塊 (一般情況下 M==N)，然后對(duì)當(dāng)前幀中的每一個(gè)塊都在參考幀中的一定區(qū)域，即搜索窗口內(nèi)，按照一定的匹配準(zhǔn)則搜索與之具有最小匹配誤差的塊 (Minimal DistortionBlock，MDB)，該塊即為當(dāng)前塊的匹配塊，由匹配塊與當(dāng)前塊的相應(yīng)位置計(jì)算出運(yùn)動(dòng)位移，所得運(yùn)動(dòng)位移即為當(dāng)前塊的運(yùn)動(dòng)矢量。并且假定每一個(gè)塊內(nèi)的運(yùn)動(dòng)只做 相等的平移同時(shí)可以用一個(gè)簡(jiǎn)單的參數(shù)模型特征化。如果塊足夠小，那么這種模型是相當(dāng)合理的。匹配塊與當(dāng)前塊之間的坐標(biāo)位移就是運(yùn)動(dòng)矢量，匹配塊與當(dāng)前塊的對(duì)應(yīng)象素點(diǎn)逐個(gè)做差就的到差值塊。基于這樣的方法這樣，當(dāng)前幀中的每一個(gè)塊都可以用一個(gè)差值塊和一個(gè)運(yùn)動(dòng)矢量來(lái)表示，對(duì)當(dāng)前幀的編碼就轉(zhuǎn)化為對(duì)每一塊的差值塊和運(yùn)動(dòng)矢量的編碼。 塊匹配的原理如圖 21。運(yùn)動(dòng)估計(jì)算法的整體效率主要體現(xiàn)在初始搜索點(diǎn)的選擇、匹配準(zhǔn)則和運(yùn)動(dòng)搜索策略三個(gè)方面。本程序主要用基于塊的運(yùn)動(dòng)方式開(kāi)發(fā)出的運(yùn)動(dòng)估計(jì)算法——塊匹配算法。塊匹配算法由于它具有較少的硬件 復(fù)雜度，容易在超大規(guī)模集成電路中實(shí)現(xiàn)，因此被認(rèn)為是最通用的算法。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 7 圖 21 塊匹配原理圖 為了提高圖像質(zhì)量，加快估計(jì)速度是運(yùn)動(dòng)估計(jì)算法的研究目標(biāo) 之一 。通常是通過(guò)研究初始搜索點(diǎn)的選擇、匹配準(zhǔn)則和運(yùn)動(dòng)搜索策略等來(lái)提高算法效率的 [13]。 初始搜索點(diǎn)的選擇 (1)直接選擇參考幀對(duì)應(yīng)塊的中心位置。這種方法簡(jiǎn)單，但容易陷入局部最優(yōu)點(diǎn)。如果采用的算法初始步長(zhǎng)太大，而原點(diǎn) (以下均指待搜索塊的中心點(diǎn)在參考幀中的相同位置的對(duì)應(yīng)點(diǎn)，而不是坐標(biāo)位置的 真正原點(diǎn) )又不是最優(yōu)點(diǎn)，有可能使快速搜索跳出原人群的運(yùn)動(dòng)估計(jì)點(diǎn)周?chē)膮^(qū)域 (這些區(qū)域可能包含最優(yōu)點(diǎn) )而去搜索遠(yuǎn)距離的點(diǎn)，導(dǎo)致搜索方向的不確定性，這就有可能陷入局部最優(yōu)。 (2)選擇預(yù)測(cè)的起點(diǎn)。由于相鄰塊之間和相鄰幀之間具有很強(qiáng)的相關(guān)性，因而許多算法都利用這種相關(guān)性先對(duì)初始搜索點(diǎn)進(jìn)行預(yù)測(cè)，以預(yù)測(cè)點(diǎn)作為搜索起點(diǎn)。大量實(shí)驗(yàn)證明預(yù)測(cè)點(diǎn)越靠近最優(yōu)匹配點(diǎn)，越會(huì)使得搜索次數(shù)減少。 下面舉例說(shuō)明幾種常見(jiàn)的預(yù)測(cè)方法。 方法 1:基于 SAD(the Sum of Absolute Differences)值的起點(diǎn)預(yù)測(cè)方法。分別求出 當(dāng)前塊與其相鄰塊間的 SAD 值，然后選取 SAD 最小的塊的運(yùn)動(dòng)矢量作為預(yù)測(cè)值。這種方法預(yù)測(cè)精度高，但計(jì)算 SAD 值的時(shí)間開(kāi)銷(xiāo)大。改進(jìn)的方法是利用運(yùn)動(dòng)矢量的相關(guān)性來(lái)預(yù)測(cè)起點(diǎn)。 方法 2:利用相鄰塊和相鄰幀對(duì)應(yīng)塊的運(yùn)動(dòng)矢量來(lái)預(yù)測(cè)當(dāng)前塊的搜索起點(diǎn)。序列圖像的運(yùn)動(dòng)矢量在空間、時(shí)間上具有很強(qiáng)的相關(guān)性。由于保存前一幀運(yùn)動(dòng)矢量信息在解碼端需要占用大量?jī)?nèi)存，使得系統(tǒng)復(fù)雜化，故大多算法僅考慮同幀塊的空間相關(guān)性來(lái)預(yù)測(cè)運(yùn)動(dòng)。比較典型的是 ―平均預(yù)測(cè) ‖，在 中使用三個(gè)相鄰塊的運(yùn)動(dòng)矢量的中值作為當(dāng)前塊的運(yùn)動(dòng)矢量的預(yù)測(cè)值。 方法 3:基于 相鄰運(yùn)動(dòng)矢量相等的起點(diǎn)預(yù)測(cè)方法。如果當(dāng)前塊的各相鄰塊的運(yùn)動(dòng)矢量相等，則以其作為當(dāng)前塊運(yùn)動(dòng)矢量的預(yù)測(cè)值 。否則，使用方法 1 求出當(dāng)前塊與其相鄰塊間的SAD 值，然后選取 SAD 值最小的塊作為預(yù)測(cè)起點(diǎn)。這種方法在保證精度的基礎(chǔ)上利用運(yùn)動(dòng)矢量相關(guān)性從而大大減少了計(jì)算量。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 8 運(yùn)動(dòng)估計(jì)的復(fù)雜度主要取決于匹配計(jì)算量和所采用的搜索算法這兩個(gè)方面 [14]。在下一節(jié)中將介紹在運(yùn)動(dòng)估計(jì)常用的一些匹配準(zhǔn)則。 塊匹配準(zhǔn)則 運(yùn)動(dòng)估計(jì)算法中常用的匹配準(zhǔn)則有三種，即最小絕對(duì)值差 (MAD)、最小均方誤差 (MSE)和歸一化互相關(guān)函數(shù) (NCCF)，它們分別定義如下 : (1) 最小絕對(duì)值差 : （ 1） 式中， B 代表 MN 宏塊， (dx,dy)為運(yùn)動(dòng)矢量， fk 與 fk1 分別為當(dāng)前幀和前一幀的灰度值，若在某一個(gè)點(diǎn) (x， y)處 MAD(dx,dy)達(dá)到最小，則該點(diǎn)為要找的最優(yōu)匹配點(diǎn)。若在某一個(gè)點(diǎn) (x,y)處 MAD(dx,dy)達(dá)到最小，則該點(diǎn)為要找的最優(yōu)匹配點(diǎn)。 (2)最小均方誤差 : （ 2） 能夠使 MSE 值最小的點(diǎn)為最優(yōu)匹配點(diǎn)。 (3)歸一化互相關(guān)函數(shù)： （ 3） 式中 NCCF 的最大值點(diǎn)為最優(yōu)匹配點(diǎn)。在運(yùn)動(dòng)估計(jì)中，匹配準(zhǔn)則對(duì)匹配的精度影響不是很大，由于 MAD 準(zhǔn)則不需要作乘法運(yùn)算，實(shí)現(xiàn)簡(jiǎn)單、方便，所以使用最 多，通常使用 ASD 代替 MAD。 SAD 即求和絕對(duì)誤差，其定義如下 : （ 4） 搜索策略 搜索策論選擇恰當(dāng)與否對(duì)運(yùn)動(dòng)估計(jì)的準(zhǔn)確性，運(yùn)動(dòng)估計(jì)的速度有很大的影響。有關(guān)搜索策略的研究主要是解決運(yùn)動(dòng)估計(jì)中存在的計(jì)算復(fù)雜度和搜索精度這一矛盾。如四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 9 全搜索法，它對(duì)搜索范圍內(nèi)的每一個(gè)像素點(diǎn)進(jìn)行塊匹配運(yùn)算以得到一個(gè)最優(yōu)的運(yùn)動(dòng)矢量。 不過(guò)，較大的搜索窗通常會(huì)使得搜索點(diǎn)增多，從而加 大計(jì)算量，因此，搜索距離的設(shè)定需綜合考慮具體視頻的運(yùn)動(dòng)特性、運(yùn)動(dòng)估計(jì)的質(zhì)量以及算法的計(jì)算量等因素，以獲得最佳的估計(jì)性能 [15]。 另外三步法、二維對(duì)數(shù)法、交叉法等主要是通過(guò)限制搜索位置的數(shù)目來(lái)減少計(jì)算量。這以后的許多搜多策略都是為了平衡搜索精度與計(jì)算速度而產(chǎn)生的。 典型的塊匹配算法 在 MPEG24 視頻編碼算法中，運(yùn)動(dòng)估計(jì) (ME)的計(jì)算量占整個(gè)編碼計(jì)算量的 2/3 以上 [16]。在視頻編碼系統(tǒng)中，運(yùn)動(dòng)估計(jì)處理消耗近 50%的功耗 [16]。為了減小運(yùn)動(dòng)估計(jì)計(jì)算量 ，出現(xiàn)了各種塊匹配算法，它們只是搜索策略各有不同 ，其中搜索精度最高的是全搜索法，但由于計(jì)算復(fù)雜度高，不宜于實(shí)時(shí)應(yīng)用，為此人們提出了各種改進(jìn)的快速算法。下面介紹幾種常用的經(jīng)典算法。 (l)全搜索法 (FS， Full Seacrh method) ① 算法思想 :全搜索法也稱(chēng)為窮盡搜索法，或螺旋向外搜索法，是對(duì)搜索范圍內(nèi)所有可能的候選位置計(jì)算其 SAD(i， j)值，從中找出最小 SAD，其對(duì)應(yīng)偏移量即為所求運(yùn)動(dòng)矢量。此算法計(jì)算量雖大，但最簡(jiǎn)單，可靠，找到一定是全局的最優(yōu)點(diǎn)。 ② 算法描述 : Setpl:從原點(diǎn)出發(fā)，按順時(shí)針?lè)较蛴山斑h(yuǎn)，在每個(gè)像素處計(jì)算 SAD 值，直到遍 歷搜索范圍內(nèi)的所有點(diǎn)。 StPe2:在所有的 SAD 中找到最小塊誤差 (MBD)點(diǎn) (即 SAD 最小值的點(diǎn) )，該點(diǎn)所在位置即對(duì)應(yīng)的最佳運(yùn)動(dòng)矢量。 ③ 模板及搜索過(guò)程圖示 :如圖 22 所示。 圖 22 全搜索法搜索過(guò)程 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 10 ④ 算法分析 :FS 算法是最簡(jiǎn)單、最原始的塊匹配算法，由于可靠，且能夠得到全局最優(yōu)的結(jié)果，通常是其它算法性能比較的標(biāo)準(zhǔn)，但它的計(jì)算量很大，這就限制了在需要實(shí)時(shí)性較強(qiáng)的場(chǎng)合的應(yīng)用，所以有必要進(jìn)一步研究其它快速算法。 (2)二維對(duì)數(shù)法 (TDL， TwoDimensional Logarithmic) 二維對(duì)數(shù)搜索法由 和 提出，它開(kāi)創(chuàng)了快速算法的先例，分多個(gè)階段搜索，逐次減小搜索范圍直到不能再小時(shí)結(jié)束。 ① 基本思想 :二維對(duì)數(shù)搜索法是由原點(diǎn)開(kāi)始，以 ―十 ‖字形分布的五個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，通過(guò)快速搜索跟蹤加 MBD 點(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::若步長(zhǎng)為 1，在中心及周?chē)?8 個(gè)點(diǎn)處找出 MBD 點(diǎn)，該點(diǎn)所在位置即對(duì)應(yīng)最佳運(yùn)動(dòng)矢量，算法結(jié)束 。否則，重復(fù) Step 2。 ③ 搜索過(guò)程圖示 :如圖 23 所示。 ④ 算法分析 :TDL 算法搜索時(shí)，最大搜索點(diǎn)數(shù)為 2+7lbW，這里 W 表示最大偏移量max(dxmax,dymax)。若發(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)。不能保證找到全局最優(yōu)點(diǎn)也正是大部分快速搜索算法的缺點(diǎn)。 圖 23 二維對(duì)數(shù)法過(guò)程 (3)三步搜索法 (TSS，而 Three Step Search) 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 11 三步搜索法與 TDL 類(lèi)似，由于其簡(jiǎn)單、健壯、性能良好的特點(diǎn)，已被人們所重視。若最大搜索長(zhǎng)度為 7，搜索精 度取 1 個(gè)像素，則步長(zhǎng)為 1，共需要三步即可滿(mǎn)足。 ① 基本思想 :TSS 算法的基本思想是采用一種由粗到細(xì)的搜索模式，從原點(diǎn)開(kāi)始，按一定步長(zhǎng)取周?chē)?8 個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，然后進(jìn)行匹配運(yùn)算，跟蹤最小塊誤差MBD 點(diǎn)。 . ② 算法描述 : Step 1:從原點(diǎn)開(kāi)始，選取最大搜索長(zhǎng)度的一半為步長(zhǎng)，在中心點(diǎn)及周?chē)?8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較。 Step 2:將步長(zhǎng)減半，中心移到上一步的 MBD 點(diǎn)，重新在中心點(diǎn)及周?chē)?8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較。 Step 3:在中心點(diǎn)及周?chē)?8 個(gè)點(diǎn)處找出加 MBD 點(diǎn)，若步長(zhǎng)為 1，該點(diǎn)所在位 置即對(duì)應(yīng)最佳運(yùn)動(dòng)矢量，算法結(jié)束 。否則，重復(fù) Step 2。 ③ 搜索過(guò)程圖示 :一個(gè)可能的搜索過(guò)程如圖 24 所示。圖 24 中點(diǎn) [+4， +4]、 [+6，+4]是第一、第二步的最小塊誤差點(diǎn)。第三步得到最終運(yùn)動(dòng)矢量為 [+7， +5]，每個(gè)點(diǎn)上的數(shù)字表明了每個(gè)階段搜索時(shí)計(jì)算的候選塊的位置。 圖 24 三步搜索法搜索過(guò)程 ④ 算法分析 :TSS 算法搜索時(shí)，整個(gè)過(guò)程采用了統(tǒng)一的搜索模板，使得第一步的步長(zhǎng)過(guò)大，容易引起誤導(dǎo)，因此對(duì)小運(yùn)動(dòng)模式的效率較低 。最大搜索點(diǎn)數(shù)為 1+8blW，當(dāng)搜索范圍大于 7 時(shí)，僅用三步是不夠的，搜索步數(shù)的一般表達(dá)式為 lb(dmax+1). (4)交叉法 (CSA， Cross Search Algorithm) 1990 年， Chanbari 提出了交叉搜索算法，它也是在 TDL 和 TSS 基礎(chǔ)上為進(jìn)一步減小計(jì)算量而發(fā)展起來(lái)的快速搜索法。 本思想 :CSA 是從原點(diǎn)開(kāi)始，以