1.4 基于運動估計的視頻倍頻插幀

對于一段視頻圖像，通常情況下，人眼所能感知的沒有明顯閃爍的最小幀率是每秒24幀。但是，在具體應(yīng)用中，受到圖像的采集裝置、存儲介質(zhì)和傳輸硬件等條件的影響，所獲得的片源有可能出現(xiàn)幀率不高的情況。比如，早期的醫(yī)學(xué)X射線影像透視設(shè)備，受到裝置熱容量的限制，或者為了減少對病人的射線輻射劑量，往往選擇15幀拍攝，但是明顯的閃爍感很容易造成視覺疲勞，給醫(yī)生診斷帶來很大的負(fù)擔(dān)；又如，某些電視為了達(dá)到更為精細(xì)的顯示效果或滿足3D顯示需要，原始的片源幀率不能滿足需求。

為了解決上述問題，提供更好的視覺感受，需要在原始的視頻圖像之間插入一幀或者多幀過渡圖像，其中的關(guān)鍵問題就是應(yīng)該插入怎樣的圖像。如果插入一幀與前一幀或者后一幀完全一樣的圖像，與沒有插入圖像幾乎沒有區(qū)別。所以，所插入的圖像應(yīng)該是一幅新的圖像，該圖像基于已有的圖像計算而得到，但圖像之間復(fù)雜的變化情況給這個問題帶來不小的難度。對于這些問題，有沒有比較成熟的解決思路和方法呢？目前，用來獲得圖像插幀最為常見的思路是運動估計和運動補償。

1.4.1 運動估計簡介

運動估計（Motion Estimation, ME）常常和運動補償（Motion Compensation, MC）一起使用，MEMC是目前幀間編碼最為常用的方法之一。運動估計的基本思路是：首先將一幅圖像劃分為若干細(xì)小的單元，然后將每個細(xì)小的單元與前一幅或后一幅圖像對應(yīng)位置的某個區(qū)域進(jìn)行對比，找到匹配度最高的位置，將該位置和原來位置之間的坐標(biāo)差記錄下來，這個差就是一個向量，稱為運動向量（Motion Vector, MV）。利用這些運動向量，可以幫助實現(xiàn)視頻壓縮、圖像插幀倍頻等應(yīng)用。而運動估計研究的主要內(nèi)容就是如何快速、有效地獲得有足夠精度的運動向量。反過來，通過MV計算出或者預(yù)測出完整圖像的過程，就是運動補償。

1.4.2 運動估計的應(yīng)用領(lǐng)域

利用運動估計實現(xiàn)的應(yīng)用大致分為兩大方向：視頻壓縮和視頻插幀。它們分別是怎么實現(xiàn)的呢？

先來看看視頻壓縮，上面介紹過，求運動估計（ME）可以得到運動向量（MV）。這樣，在保存視頻的時候，在保存一張完整的圖像之后，第二幅圖像甚至后面若干幅圖像都不用保存原始圖，而只需要保存MV即可，顯示的時候通過這個完整的圖像和所得到的MV就可以計算還原出來。顯然，一般情況下，相比起每個圖像小塊所要存儲的像素，這個由只包含兩個整數(shù)的一組MV所占用的空間遠(yuǎn)遠(yuǎn)小于一幅完整的圖像，因此，在保存為MV的同時，視頻也就被壓縮了。事實上，常見的視頻編碼標(biāo)準(zhǔn)H.261、H.263、H.264以及MPEG-1/2/4等主流標(biāo)編碼標(biāo)準(zhǔn)中都采用了基于運動估計的壓縮方法。

上述過程中，一段視頻經(jīng)過了求運動估計（ME）得到運動向量（MV），再經(jīng)過運動補償（MC）還原得到一幅完整的圖像。那么，如果現(xiàn)在進(jìn)行這樣一個實驗：對第一幅圖和第三幅圖計算ME，并將所得到的MV1,3與剛才第一幅圖和第二幅圖的MV1,2對比。通過統(tǒng)計，可以發(fā)現(xiàn)得到的MV1,3里面每個向量方向幾乎都與MV1,2一樣，但是長度卻變?yōu)閮杀丁＿@一規(guī)律常被用來作圖像插幀的MC：求出兩幅圖像之間的MV，并將該MV長度減小為一半MV′，再用原圖和MV′計算得到新的圖像，該圖像即為插入幀。

以上就是運動估計應(yīng)用的簡單介紹，具體的方法需要根據(jù)不同的應(yīng)用背景來設(shè)計。

圖1.4.1為運動估計和運動補償?shù)牧鞒淌疽鈭D，運動估計（ME）的過程需要參考幀和當(dāng)前幀參與，計算得到運動向量（MV），這些MV構(gòu)成壓縮編碼所需的必要信息；而解碼圖像的過程，也即是運動補償（MC）的過程，需要參考幀和運動向量（MV）。

1.4.3 運動估計方法分類

20世紀(jì)70年代，運動估計方法剛剛被提出的時候，分為兩個大的方向：基于像素的方法和基于塊的方法。基于像素的方法主要是像素遞歸法，而基于塊的方法主要是塊匹配方法。

像素遞歸法根據(jù)像素間亮度的變化和梯度，通過遞歸修正的方法來估計每個像素的運動向量，每個像素都有一個運動向量與之對應(yīng)。該方法的優(yōu)點是估計精度高，缺點是解碼端復(fù)雜，不利于一發(fā)多收。

相比之下，塊匹配方法通用性好，改進(jìn)空間大，很快便成為研究的熱點和主流。而隨著時間的推移，常見應(yīng)用中，基于像素的方法幾乎已難覓蹤影。現(xiàn)在用到的各類常見的運動估計方法都是基于塊匹配的思想，各種方法的不同之處，主要包括搜索的起始方向、匹配方法和搜索算法。

其中，對搜索算法的研究十分活躍，最近十多年，涌現(xiàn)了非常多的新算法和改進(jìn)方法，比一開始的遍歷式的全搜索方法有了長足進(jìn)步。在后續(xù)小節(jié)中，將會對一些經(jīng)典的搜索算法進(jìn)行介紹。

1.4.4 基于塊匹配方法的運動估計

基于塊匹配方法的運動估計，基本思想是：先將圖像劃分為許多小子塊（Block），然后對當(dāng)前幀中的每一小塊根據(jù)一定的匹配準(zhǔn)則在相鄰幀中找出當(dāng)前塊的匹配塊，由此得到兩者的相對位移，即當(dāng)前塊的運動向量（MV），該過程即為運動估計（ME）計算。進(jìn)行運動補償（MC）計算時，將得到的MV和原始圖的對應(yīng)小子塊進(jìn)行計算，還原出新圖像。

由此得到基于塊匹配方法的運動估計的一般流程為：

（1）獲得前后兩幀圖像，前一幀習(xí)慣上稱為參考幀（Referenced Image），后一幀稱為當(dāng)前幀（Current Image）；

（2）為了方便計算，常常將圖像中要做運動估計計算的部分裁剪為長寬各為8或16的倍數(shù)；

（3）將參考幀圖像劃分為很多邊長為MBSize的小子塊，比如16×16像素的小塊，設(shè)定搜索區(qū)域range的大小，比如令range＝8，即上下左右各8個像素；

（4）對于每一塊得到的小子塊，在當(dāng)前幀與其對應(yīng)的特定搜索區(qū)域（如圖1.4.2所示）中進(jìn)行搜索，通過價值函數(shù)找到匹配程度最好的那個子塊位置，該位置相對于參考幀中對應(yīng)子塊的位置之差，即為運動向量；

（5）如果要進(jìn)一步還原出圖像，則利用運動向量（MV）和參考幀對應(yīng)子塊，將子塊按照MV所指的位置移動過去，所得圖像即為還原出來的當(dāng)前幀圖像，該過程也即成為運動補償。

基于塊匹配的運動估計，在實際應(yīng)用中面臨下面的一些難點：

首先，準(zhǔn)確度問題。運動估計（ME）和運動補償（MC）之后所得到的圖像應(yīng)當(dāng)足夠準(zhǔn)確，也就是說計算得到的運動向量（MV）應(yīng)當(dāng)足夠準(zhǔn)確。這里說的“準(zhǔn)確”，包含兩方面的意義：每個小塊的MV是否準(zhǔn)確以及所有小塊的MV的準(zhǔn)確率是否足夠高。由于搜索區(qū)域大小的有限性、小塊之間匹配算法的局限性，對于運動速度較大、亮度變化較大或是圖像中圖形不連續(xù)的部分，在計算MV的時候，有一定出錯的可能性。

其次，計算效率問題。將一幅圖像劃分為很多小塊，每個小塊都需要進(jìn)行各自獨立的搜索，這對搜索過程和匹配算法的效率提出了很高的要求。最初的遍歷式搜索方法能夠保證找到搜索區(qū)域中匹配度最高的點，但是動輒每幀圖像十幾甚至幾十秒的運算速度，也讓實時應(yīng)用難以實現(xiàn)。

為了又快又準(zhǔn)地進(jìn)行運動估計計算，研究人員主要從搜索算法尋求突破，研究的方向主要有搜索起始點的方向、能夠盡可能減少搜索點的搜索路徑、MV在時間和空間上的關(guān)聯(lián)預(yù)測等，來對算法進(jìn)行改進(jìn)。

對于經(jīng)過MEMC計算和還原的圖像，評價其品質(zhì)好壞的方法是計算其峰值信噪比（PSNR）。

PSNR即到達(dá)噪聲比率的峰值信號，它是原圖像與被處理圖像之間的均方誤差相對于（2 ＾n－1）＾2的對數(shù)值（信號最大值的平方，n是每個采樣值的比特數(shù)），它的單位是dB。PSNR是一種評價圖像的客觀標(biāo)準(zhǔn)，PSNR值越大，就代表失真越小。

式（1.4.1）中的MSE是最小均方差（Mean Squared Error），其計算公式如下：

這里N是子塊的邊長，Cij和Rij是各個當(dāng)前子塊和參考子塊中對比的像素值。

在前面介紹了運動估計的難點，歸結(jié)起來就是怎樣才能又準(zhǔn)又快地計算出MV，而目前的研究熱點主要是針對這些難點進(jìn)行改進(jìn)的。這些改進(jìn)主要包括搜索起始點的位置和方向、匹配算法和搜索算法，其中搜索算法是近幾年來研究進(jìn)展最快的，嚴(yán)格地說，起始點位置和方向也屬于搜索算法中的一部分。

1.4.5 相關(guān)概念

起始點位置和方向是每個小子塊在搜索一開始可以做的一個選擇，選擇搜索區(qū)域中從哪個位置開始搜索，朝哪個方向開始搜索。最初的遍歷式的全局方法中并不考慮這個問題，只是單純地將搜索區(qū)域中所有點遍歷一遍，然后找出匹配度最高的位置。

但是隨著研究的深入以及終止條件的引入，人們發(fā)現(xiàn)，對于同一個小子塊的運動總有著一定的規(guī)律：這些運動方向往往與當(dāng)前幀中周圍位置的子塊（如圖1.4.3所示）或者前面幾幀中相同位置的子塊（如圖1.4.4所示）有著類似的運動趨勢。于是，就利用這些條件來預(yù)測搜索起始點的位置和方向，從而提高搜索的效率和速度。

1.4.6 匹配方法：價值函數(shù)

參考幀中的子塊在當(dāng)前幀中的搜索區(qū)域搜索，要找到最佳匹配位置，每一次搜索會計算出一個匹配值，而最佳區(qū)域就是滿足條件的峰值點。這里，如何計算每次匹配的值，就要用到價值函數(shù)，也就是所謂的匹配方法。在圖像匹配中，可以用作價值函數(shù)的方法包括：絕對平均誤差（MAD）、絕對差和（SAD）、最小均方誤差（MSE）和歸一化互相關(guān)（NCC）。下面對這幾種匹配方法進(jìn)行簡單介紹。

1．絕對平均誤差（MAD）

絕對平均誤差也稱平均絕對失真，是對兩個子塊間對應(yīng)像素誤差的描述。其計算公式見式（1.4.3）：

其中，（i,j）是位移向量，（m,n）為當(dāng)前子塊左上角坐標(biāo)，fk和fk－1分別為當(dāng)前幀和上一幀的灰度值，M×N為子塊大小。若在某一點（i0,j0）, MAD（i0,j0）達(dá)到最小，則該點為要找的最優(yōu)匹配點，對應(yīng)的塊為最優(yōu)匹配塊。

2．絕對差和（SAD）

絕對差和是對兩個子塊間對應(yīng)像素誤差之和的描述，與MAD的區(qū)別在于絕對差和不求平均值，因此，比MAD少一個計算步驟，而所得到的匹配結(jié)果與MAD是一樣的。其計算公式見式（1.4.4）：

與MAD類似，其中，（i,j）是位移向量，（m,n）為當(dāng)前子塊左上角坐標(biāo)，fk和fk－1分別為當(dāng)前幀和上一幀的灰度值，M×N為子塊大小。若在某一點（i0,j0）, SAD（i0,j0）達(dá)到最小，則該點為要找的最優(yōu)匹配點，對應(yīng)的塊為最優(yōu)匹配塊。

3．最小均方差（MSE）

最小均方差也是對兩個子塊間對應(yīng)像素誤差之和的描述，與SAD相比，在計算中多了相乘的步驟，使得計算量大大增加。其計算公式見式（1.4.5）：

其中，（i,j）是位移向量，（m,n）為當(dāng)前子塊左上角坐標(biāo)，fk和fk－1分別為當(dāng)前幀和上一幀的灰度值，M×N為子塊大小。若在某一點（i0,j0）, MAE（i0,j0）達(dá)到最小，則該點為要找的最優(yōu)匹配點，對應(yīng)的塊為最優(yōu)匹配塊。

4．歸一化互相關(guān)（NCC）

歸一化互相關(guān)是模板匹配中常用的方法，用到能量函數(shù)的思想，該方法有很多改進(jìn)算法，包括擴展到頻率域等。常用于尺寸較大的圖像的匹配，匹配準(zhǔn)確率較高。

其中，是當(dāng)前幀子塊的平均值，是參考幀中當(dāng)前幀對應(yīng)位置子塊的平均值。若在某一點（i0,j0）, NCC（i0,j0）達(dá)到最大，則該點為要找的最優(yōu)匹配點，對應(yīng)的塊為最優(yōu)匹配塊。

對比上述幾種常見匹配方法，計算最為復(fù)雜、準(zhǔn)確率最高的是NCC，最簡單的是SAD，其匹配準(zhǔn)確率在圖像很小的時候也比較不錯。考慮到資源占用和性能要求，往往選擇SAD作為匹配算法。實際使用中，經(jīng)典的非對稱十字多層次六邊形搜索算法UMHexagonS中，就以SAD作為匹配算法。

考慮到圖像之間亮度可能發(fā)生變化，因此，具有較強魯棒性且運算速度較快的價值函數(shù)也成為研究的需要。

1.4.7 搜索算法

怎樣盡可能快地找到匹配點？除了匹配方法，更重要的就是尋找最佳匹配點的方法。這一部分將介紹若干經(jīng)典的搜索算法。

1．窮盡搜索法（ES）/全搜索法（FS）

窮盡搜索法（Exhaustive Search, ES），也稱全搜索法（Full Search, FS），顧名思義，就是將待搜索區(qū)域每個可能位置遍歷一遍，如圖1.4.5所示，找到最佳匹配位置。這樣的結(jié)果就是它不會遺漏并且能夠發(fā)現(xiàn)搜索區(qū)域中最好的可能的匹配，并且獲得所有塊匹配算法中最高的PSNR值。

后面提出的各類快速塊匹配算法都是試圖在盡可能少的計算中做到相同的PSNR。ES的優(yōu)點是找到的MV精度高，而其缺點也很明顯，就是搜索窗越大，越耗費資源。

2．三步搜索法（TSS/3SS）

三步搜索法（Three Step Search, TSS/3SS）可以追溯到20世紀(jì)80年代中期，是最早嘗試快速塊匹配的方法之一，大致思想如圖1.4.6所示。假設(shè)對于一個普通的設(shè)為range＝7的搜索區(qū)域參數(shù)，該算法的起點是搜索區(qū)域的中心，并且設(shè)置“搜索步長”為S＝4；然后搜索8個位置，環(huán)繞位置（0,0）±S個像素；從這9個位置搜索，找到最小值的那一點；然后以此點作為新的搜索原點；然后設(shè)置新的搜索步長S＝S/2，重復(fù)類似搜索兩個周期，直到S＝1；在該點發(fā)現(xiàn)價值函數(shù)的最小值，子塊在這點位置被認(rèn)為是最好匹配。

圖1.4.6中，●為第一步，▲為第二步，■為第三步的檢索點。

TSS背后的思想是：在每一個子塊的運動中產(chǎn)生的錯誤構(gòu)成的曲面是單峰值的。一個單峰值的曲面是一個碗形曲面，這樣由價值函數(shù)產(chǎn)生的值在全局極小值中是單調(diào)遞增的。

對于range＝7的情況，ES將要搜索225個子塊，而TSS只需要計算25個子塊，可見，該方法可以顯著減少計算量。

3．新三步搜索法（NTSS）

三步搜索法（TSS/3SS）對于運動估計使用了固定的檢索模式，容易錯過小的運動。相比之下，新三步搜索法（New Three Step Search, NTSS）的步驟如圖1.4.7所示。在第一步中，除了搜索原點之外的16個點（8個●和8個■），找到價值函數(shù)的最小值點。這些多出來的搜索位置，8個點是距離原點S＝4的點（與TSS類似），另外8個點是距離原點S＝1的點。如果最小值在原點，那么搜索就停在這里，并且運動向量就為（0,0）；如果最小值為S＝1是8個點中的任意一個點，則改變搜索原點到該點，并檢查它鄰近的值。按照不同的點，或許能夠檢查5個◆點（見圖1.4.8（b））或3個▲點就結(jié)束（見圖1.4.8（c））。給出最小值的位置就是最接近的匹配，運動向量就被設(shè)置為那個位置。從另一方面來說，如果最小值在第一步之后，是S＝4中的8個點其中之一，那么就按照TSS的標(biāo)準(zhǔn)方法。因此，盡管這個方法在理想情況下需要對每個子塊最少檢測17個點，但是也有可能在最差情況下檢索33個點。

如圖1.4.7所示，●是三步搜索法（TSS/3SS）中第一步的檢索點，■是NTSS中加入的屬于第一步的多余的8個點。▲和◆是NTSS的第二步，當(dāng)?shù)谝徊街凶钚≈翟?個相鄰點中一個的中心時，后面要檢索的點數(shù)分兩種情況：5個◆點或者是3個▲點。

新三步搜索法改進(jìn)了三步搜索法的結(jié)果，通過增加一個有偏向性的中心搜索方案和一個中途停止條件來減少計算量。這是最早被廣泛接受的快速算法之一，被頻繁用于實施早期的編碼標(biāo)準(zhǔn)，比如MPEG 1和H.261。

4．四步搜索法（FSS/4SS）

與NTSS類似，四步搜索法（Four Step Search, FSS/4SS）同樣采用中心偏置搜索，并且有中途停止條件。如圖1.4.8所示，F(xiàn)SS在第一步中設(shè)置了一個固定搜索步長S＝2，而不考慮搜索區(qū)域參數(shù)r的值是多少。因此，它在5×5的窗口中搜索9個位置。如果最小值在搜索窗中心被發(fā)現(xiàn)，搜索直接跳到第四步；如果最小值為8個位置中的一個，則將該點作為搜索原點并進(jìn)入到第二步。搜索窗仍然維持在5×5。也許可以在檢索到3個點或5個點時結(jié)束，這取決于最小值的位置。

四步搜索法的搜索模式如圖1.4.9所示。此外，如果最小值的位置在5×5搜索窗的中心，可跳到第四步或者繼續(xù)第三步。第三步和第二步一模一樣，在第四步，窗口尺寸縮小到3×3，比如S＝1。最小值的位置就是最佳匹配宏塊，運動向量就設(shè)置成指向該位置。

圖1.4.8中顯示了一個處理例子，●是第一步檢索的點，■是第二步檢索的點，▲是第三步檢索的點，◆是第四步檢索的點。這個搜索算法最好情況下檢索17個點，最差情況下檢索27個點。

5．菱形搜索法（DS）

菱形搜索法（Diamond Search, DS）和FSS幾乎一樣，但是搜索點模式從方形換成了菱形，并且對于算法的搜索步驟數(shù)沒有限制。DS使用了兩種不同的混合的模式，一種是大菱形搜索（LDSP），另一種是小菱形搜索（SDSP）。

這兩種模式DS的執(zhí)行過程如圖1.4.10所示，黑色點為大菱形搜索模式，灰色點為小菱形搜索模式。該例中得到運動向量（－4, －2）總共5步：4步使用了LDSP,1步使用了SDSP。

因為搜索模式既不太小也不太大，事實上對于搜索的步數(shù)并沒有限制，該算法可以比較精確地找到全局最小值。

6．非對稱十字多層次六邊形搜索法（UMHexagonS）

非對稱十字多層次六邊形搜索法（Unsymmetrical-Cross Multi-Hexagon Search，UMHexagonS）是目前比較主流的搜索算法，因其快速和高精度的特點，被H.264編碼標(biāo)準(zhǔn)所采用。需要說明的是，UMHexagonS方法并非最快速的方法，相比其他簡單算法，計算復(fù)雜度反而有所上升。

圖1.4.11顯示了UMHexagonS算法搜索過程，總體上分為四步，其中第一步為初始判斷，之后根據(jù)所得結(jié)果與閾值進(jìn)行判斷，按照SAD值的滿意程度選擇進(jìn)入Step2～4中的任意一步。

Step1（圖1.4.11中的●）：搜索起點預(yù)測。具體預(yù)測模式包括中值預(yù)測（MP）、上層預(yù)測（UP）、時間域鄰近參考幀預(yù)測（NRP）、上一參考幀對應(yīng)塊（CP）、原點預(yù)測（OP）這五種方法來預(yù)測當(dāng)前塊的運動向量（MV），將該點作為搜索起點；此外，還可以利用SAD的相關(guān)性來進(jìn)行預(yù)測。

當(dāng)上述幾種預(yù)測完成之后，找到最佳預(yù)測搜索起點，根據(jù)所得SAD值的滿意程度，選擇跳轉(zhuǎn)進(jìn)入Step2～4中的一個。

Step2：不滿意搜索模式。

Step2.1（圖1.4.11中的△）：以預(yù)測得到的搜索起點為中心，用非對稱十字形搜索模板進(jìn)行搜索；獲得當(dāng)前最佳點，判斷此處SAD值是否屬于滿意或很滿意，跳到相應(yīng)的步驟3或步驟4或繼續(xù)搜索。

Step2.2（圖1.4.11中的〇）：以當(dāng)前最佳點為中心，在邊長為5的方形區(qū)域中進(jìn)行ES搜索；獲得當(dāng)前最佳點，判斷此處SAD值是否屬于滿意或很滿意，跳到相應(yīng)的Step3或Step4或繼續(xù)搜索。

Step2.3（圖1.4.11中的□）：用每次擴大最小六邊形直徑一倍的大六邊形模板進(jìn)行搜索，直至搜索到的SAD能符合相應(yīng)閾值而進(jìn)入Step3或Step4的點為止；否則結(jié)束Step2的搜索進(jìn)入Step3。

Step3（圖1.4.11中的▽）：滿意搜索模式。以當(dāng)前最佳點為中心進(jìn)行小六邊形搜索，如果當(dāng)前最佳點在六邊形邊上，則將搜索中心移動到該點，如此反復(fù)，直至最佳點為六邊形的中心。

Step4（圖1.4.11中的■）：很滿意搜索模式。以當(dāng)前最佳點為中心進(jìn)行菱形搜索，直至最佳點為菱形的中心。

1.4.8 實際應(yīng)用舉例

本小節(jié)將對醫(yī)學(xué)X射線透視視頻使用運動估計的方法進(jìn)行插幀，看看是否能讓視頻效果有所提升。

實驗1所用圖像為一段由某型號X射線機采集的每秒30幀的視頻，為了讓結(jié)果更為準(zhǔn)確直觀，以一張分辨率檢測卡為對象進(jìn)行實驗（如圖1.4.12所示），獲得的原始視頻包含56幅灰度值為0～255的灰度圖像。

為了更好地理解運動估計方法的局限性，提供了實驗2，該實驗所用圖像為X射線機采集的每秒15幀的視頻，如圖1.4.13所示，采集對象為人體胸正位透視圖像，原始視頻包含107幅灰度值為0～255的灰度圖像。

實驗3所用視頻與實驗2相同，但是在運動估計計算之前，對亮度進(jìn)行了補償，用來與實驗2效果進(jìn)行對比。

實驗1和實驗2流程框圖如圖1.4.14所示，所用方法為全搜索法（ES）（參看MATLAB程序main＿M(jìn)EMC＿ES.m），具體包括以下環(huán)節(jié)：

（1）設(shè)置初始參數(shù)：子塊大小MBSize，搜索范圍range。

（2）讀入名為XRayVideo.avi的原始圖像視頻。

（3）從視頻中取出兩相鄰幀圖像，前一幀為參考幀ImageRef，后一幀為當(dāng)前幀ImageCur。

（4）將兩幀圖像分割出邊長為MBSize的子塊，進(jìn)行運動估計計算。對于當(dāng)前幀中的每個子塊，通過全搜索法，計算其在參考幀中對應(yīng)位置的子塊的價值函數(shù)（MAD）的值，存放在一個和搜索區(qū)域?qū)?yīng)大小的矩陣Costs中，再找到Costs矩陣中的最小值點以及該點所在的位置dy和dx，這個dy和dx就為該子塊的運動向量（MV）。

（5）重復(fù)步驟（4），直到計算完當(dāng)前圖像中的所有MV，將所得結(jié)果存放在MotionVect中。

（6）計算插入幀圖像：將所得MV的值變?yōu)樵瓉淼囊话隡V′，再利用新的MV′進(jìn)行運動補償MC計算，所得的圖像即為插入幀圖像。

（7）所得結(jié)果保存在result文件夾中。

【例1.4.1】圖像插幀程序。

    *******************************************************************************
    % 圖像插幀程序
    % 說明：
    %     本程序讀入根目錄下的一段名為XRayVideo的醫(yī)學(xué)圖像視頻，使用MEMC中的ES
    %     方法進(jìn)行圖像插幀，得到的新視頻XRayVideoNew幀數(shù)和幀率為原來兩倍，結(jié)果存放
    %     在．/result文件夾下
    % 注意：
    %       本程序運算速度很慢，需耐心等待
    close all;
    clear all;
    % 預(yù)設(shè)參數(shù)
    MBSize ＝ 16;                                                 %子塊大小
    Range  ＝ 8; %搜索范圍
    % 要讀寫的文件名
    % ReadFileName  ＝ ＇./XRayVideoCard＇;                       %分辨率卡透視
    ReadFileName  ＝ ＇./XRayVideoMan＇;                          %人體胸正位透視
    WriteFileName ＝[ReadFileName, ＇New＇];
    SaveDirectory＝ ＇./result/＇;
    % 讀出視頻信息
    ReadVideoObject ＝ VideoReader([ReadFileName, ＇.avi＇]);
    FrameRateOrigin＝ ReadVideoObject.FrameRate;                  %幀率
    FrameNums ＝ ReadVideoObject.NumberOfFrames;                  %幀數(shù)
    % 創(chuàng)建要寫入的視頻對象
    WriteVideoObject ＝ VideoWriter([SaveDirectory, WriteFileName, ＇.avi＇]);
    WriteVideoObject.FrameRate ＝ FrameRateOrigin * 2;
    open(WriteVideoObject);
    % 循環(huán)計算插入幀，保存為新視頻文件
    for i ＝ 1 :FrameNums － 1
        imgNumO＝ 2 * i － 1; %存放原始圖序號
        imgNumI ＝ 2 * i;                                          %存放插入圖序號
        % 從視頻中讀出要處理的圖像
        ImageRef0 ＝ read(ReadVideoObject, i);
        ImageCur0 ＝ read(ReadVideoObject, i + 1);
        ImageRef  ＝ double(rgb2gray(ImageRef0));
        ImageCur  ＝ double(rgb2gray(ImageCur0));
        % 生成并保存插入幀
        [MotionVect]＝ME＿ES(ImageCur, ImageRef, MBSize, Range);   %計算運動向量
        ImageComp    ＝MC(ImageRef, MotionVect, MBSize);           %計算插入幀
        % 保存JPG圖像
        imwrite(uint8(ImageRef), [SaveDirectory, ReadFileName, int2str(imgNumO), ＇.jpg＇]);
        imwrite(uint8(ImageComp), [SaveDirectory, ReadFileName, int2str(imgNumI), ＇.jpg＇]);
        % 將圖像寫入AVI視頻
        writeVideo(WriteVideoObject, ImageRef/255);
        writeVideo(WriteVideoObject, ImageComp/255);
   end
   close(WriteVideoObject);
   *******************************************************************************

經(jīng)過以上步驟，實驗1得到一段110幀圖像的分辨率檢測卡的視頻，實驗2得到一段212幀圖像的人體胸正位視頻，兩個視頻中奇數(shù)幀為原始圖像，偶數(shù)幀為插入圖像。

實驗3（參見例1.4.2）的流程框圖如圖1.4.15所示，其步驟與實驗1、2相比，首先將搜索范圍range擴大到10像素，然后在步驟（3）后面新增加了兩幀圖像之間的亮度倍數(shù)計算，粗略地將兩幅圖像亮度相除，得到一個比例系數(shù)，再將該比例系數(shù)乘以參考幀圖像的亮度，所得新圖像再同當(dāng)前幀圖像進(jìn)行運動估計計算得到MV。而最后插入幀圖像步驟與上述步驟（6）、（7）相同。

【例1.4.2】 修改后的圖像插幀程序。

    *******************************************************************************
    % 圖像插幀程序
    % 說明：
    %       本程序讀入根目錄下的一段名為XRayVideo的醫(yī)學(xué)圖像視頻，使用MEMC中的ES
    %       方法進(jìn)行圖像插幀，得到的新視頻XRayVideoNew幀數(shù)和幀率為原來兩倍，結(jié)果存
    %       放在．/result文件夾下
    % 注意：
    %       本程序運算速度很慢，需耐心等待
    close all;
    clear all;
    %%%%%%%%  預(yù)設(shè)參數(shù)  %%%%%%%%
    MBSize ＝ 16;                                               %子塊大小
    Range＝ 10; %搜索范圍
    %%%%%%%%  要讀寫的文件名  %%%%%%%%
    % ReadFileName  ＝ ＇./XRayVideoCard＇;                     %分辨率卡透視
    ReadFileName  ＝ ＇./XRayVideoMan＇;                        %人體胸正位透視
    WriteFileName ＝[ReadFileName, ＇New＇];
    SaveDirectory＝ ＇./result/＇;
    %%%%%%%%  讀出視頻信息  %%%%%%%%
    ReadVideoObject ＝ VideoReader([ReadFileName, ＇.avi＇]);
    FrameRateOrigin＝ ReadVideoObject.FrameRate;                %幀率
    FrameNums ＝ ReadVideoObject.NumberOfFrames;                %幀數(shù)
    %%%%%%%%  創(chuàng)建要寫入的視頻對象  %%%%%%%%
    WriteVideoObject ＝ VideoWriter([SaveDirectory, WriteFileName, ＇.avi＇]);
    WriteVideoObject.FrameRate ＝ FrameRateOrigin * 2;
    open(WriteVideoObject);
    %%%%%%%%  循環(huán)計算插入幀，保存為新視頻文件  %%%%%%%%
    for i ＝ 1 :FrameNums － 1
        imgNumO＝ 2 * i － 1; %存放原始圖序號
        imgNumI ＝ 2 * i;                                      %存放插入圖序號
        %%%%%%%%  從視頻中讀出要處理的圖像  %%%%%%%%
        ImageRef0 ＝ read(ReadVideoObject, i);
        ImageCur0 ＝ read(ReadVideoObject, i + 1);
        ImageRef  ＝ double(rgb2gray(ImageRef0));
        ImageCur  ＝ double(rgb2gray(ImageCur0));
        %%%%%%%%  亮度補償  %%%%%%%%
        [Row, Col]＝ size(ImageRef);
        ImageRefCut ＝ ImageRef(Row/4 + 1 :3 * Row/4, Col/4 + 1 :3 * Col/4);
        ImageCurCut ＝ ImageCur(Row/4 + 1 :3 * Row/4, Col/4 + 1 :3 * Col/4);
        SumPixelRef ＝ sum(ImageRefCut(:));
        SumPixelCur ＝ sum(ImageCurCut(:));
        PixelTimes  ＝ SumPixelCur/SumPixelRef;
        ImageRef1 ＝ ImageRef * PixelTimes;
        %%%%%%%%  生成并保存插入幀  %%%%%%%%
        [MotionVect]＝ME＿ES(ImageCur, ImageRef1, MBSize, Range); %計算運動向量
        ImageComp    ＝MC(ImageRef, MotionVect, MBSize);        %計算插入幀
        %%%%%%%%  保存JPG圖像  %%%%%%%%
        imwrite(uint8(ImageRef), [SaveDirectory, ReadFileName, int2str(imgNumO), ＇.jpg＇]);
        imwrite(uint8(ImageComp), [SaveDirectory, ReadFileName, int2str(imgNumI), ＇.jpg＇]);
        %%%%%%%%  將圖像寫入AVI視頻  %%%%%%%%
        writeVideo(WriteVideoObject, ImageRef/256);
        writeVideo(WriteVideoObject, ImageComp/256);
    end
    close(WriteVideoObject);
    *******************************************************************************

例1.4.1和例1.4.2所用到的幾個子函數(shù)如下：

    *******************************************************************************
    function Cost ＝ CostFuncMAD(CurBlk, RefBlk, MBSize)
    % 計算兩個子塊的平均絕對誤差(MAD)
    % hehao20131216
    % 輸入
    % CurBlk：當(dāng)前幀子塊
    % RefBlk：參考幀子塊
    % MBSize ：子塊邊長
    % 輸出
    % Cost ：兩個子塊之間的MAD值
    Err ＝ 0;
    for i ＝ 1 :MBSize
        for j ＝ 1 :MBSize
            Err ＝ Err + abs((CurBlk(i, j)－ RefBlk(i, j)));
        end
    end
    Cost ＝ Err/(MBSize *MBSize);
    *******************************************************************************
    *******************************************************************************
    function ImageComp ＝MC(Image, MotionVect, MBSize)
    % 生成運動補償圖像
    % 輸入
    %   Image：參考圖
    %  MotionVect ：運動向量
    %  MBSize ：子塊邊長
    %
    % 輸出
    %   ImageComp：運動補償圖像
    [Row, Col]＝ size(Image);

    ImageC ＝ Image;
    MBCount ＝ 1;
    for i ＝ 1 :MBSize :Row －MBSize + 1
        for j ＝ 1 :MBSize :Col －MBSize + 1
            dy＝MotionVect(1, MBCount);
            dx ＝MotionVect(2, MBCount);
            RefBlockY ＝ i + round(dy/2);
            RefBlockX ＝ j + round(dx/2);
            ImageC(i :i +MBSize － 1, j :j +MBSize － 1)＝ Image(RefBlockY:RefBlockY+
    MBSize － 1, RefBlockX :RefBlockX +MBSize － 1);
            MBCount ＝MBCount + 1;
        end
    end
    ImageComp ＝ ImageC;
    *******************************************************************************
    *******************************************************************************
    function[MotionVect]＝ME＿ES(ImageCur, ImageRef, MBSize, Range)
    % 全搜索法搜索運動向量
    % 輸入
    %   ImageCur：當(dāng)前幀
    %   ImageRef ：參考幀
    %  MBSize ：子塊邊長
    %   Range：搜索范圍
    % 輸出
    %  MotionVect ：運動向量MV
    [Row, Col]＝ size(ImageRef);
    Vectors ＝ zeros(2, Row* Col/MBSize ＾2);
    Costs   ＝ ones(2 * Range + 1,2 * Range + 1)* 256;
    MBCount ＝ 1; %MV計數(shù)
    for i ＝ 1 :MBSize :Row－MBSize + 1                        %分割出子塊
        for j ＝ 1 :MBSize :Col －MBSize + 1
            for m＝ －Range:Range                             %處理每個子塊搜索區(qū)
                for n ＝ －Range :Range
                    RefBlockY ＝ i + m;
                    RefBlockX ＝ j + n;
                    if(RefBlockY   1 ‖ RefBlockY + MBSize － 1   Row ‖ RefBlockX   1 ‖
    RefBlockX +MBSize － 1  Col)
                        continue;
                    end

                    Costs(m + Range + 1, n + Range + 1)＝ CostFuncMAD(ImageCur(i :i +
    MBSize － 1, j :j +MBSize－ 1), ImageRef(RefBlockY:RefBlockY+MBSize－ 1, RefBlockX:
    RefBlockX+MBSize－ 1), MBSize); %計算MAD矩陣
                end
            end
            [dy, dx]＝MinCost(Costs); %找到MAD最小值點作為運動向量的值
            Vectors(1, MBCount)＝ dy－ Range－ 1; %對于每個子塊的運動向量
            Vectors(2, MBCount)＝ dx － Range － 1;
            MBCount ＝MBCount + 1;
            Costs ＝ ones(2 * Range + 1,2 * Range + 1)* 256;
         end
     end
     MotionVect ＝ Vectors;
     *******************************************************************************
     *******************************************************************************
     function[dy, dx]＝MinCost(Costs)
     % 尋找最小值位置
     % hehao20131216
     % 輸入
     %   Costs ：包含一個子塊在搜索區(qū)中各個位置價值函數(shù)值的矩陣
     % 輸出
     %   dy：運動向量豎直方向的值
     %   dx：運動向量水平方向的值
     [Row, Col]＝ size(Costs);
     Min ＝ 256;
     for i ＝ 1 :Row
         for j ＝ 1 :Col
             if(Costs(i, j)  Min)
                 Min ＝ Costs(i, j);
                 dy＝ i;
                 dx ＝ j;
             end
         end
     end
     *******************************************************************************

這里所用為Intel i7-2860QM 2.5GHz處理器，4GB內(nèi)存，第1、2兩組實驗中每幀圖像的計算時間都是每幅圖約13.6s，第3組實驗中每幀圖像計算時間約為22s。

實驗1：成功的分辨率檢測卡插幀實驗XRayVideoCard range＝8。

對比原始圖像和插幀之后的圖像，可以發(fā)現(xiàn)，經(jīng)過插幀的圖像人眼感知到的分辨率線條更為精細(xì)，同時白色十字的跳躍感更小。說明插幀之后的圖像能夠改善人眼視覺感受。

實驗2：失敗的人體胸正位插幀實驗XRayVideoMan range＝8。

該視頻原始圖像為15幀，在人體進(jìn)行平移的時候閃爍感強烈，而經(jīng)過插幀之后的圖像閃爍感減少，但是會有明顯的錯誤。所產(chǎn)生的錯誤都是由運動估計方法本身的一些局限性造成的，這些局限性將在下節(jié)進(jìn)行介紹。

實驗3：效果改善的人體胸正位插幀實驗XRayVideoMan range＝10 LumComp。

經(jīng)過亮度補償之后，亮度變化時抖動有所改善。

實驗2的結(jié)果很不理想。那么，算法中的哪些局限性造成實驗的失敗呢？對比實驗1和實驗2，以及在其他實驗中出現(xiàn)的問題，可以發(fā)現(xiàn)運動估計包括以下一些局限性：

（1）整體亮度變化時容易失敗。實驗1的灰度一直保持整體均勻，而實驗2的整體灰度在不斷變化，每隔特定時間就會從亮到暗跳變幾幀。這是由X射線機的成像原理決定的，射線發(fā)射裝置會依據(jù)圖像整體亮度進(jìn)行調(diào)節(jié)，于是，在人體移動的過程中就會發(fā)生照射劑量的改變，圖像整體灰度也因此改變。對于前后兩張圖像，物體不動時，亮度改變，運動估計時也常常計算失敗。

如圖1.4.16所示，每當(dāng)亮度發(fā)生變化時，運動估計往往出現(xiàn)大范圍失敗。

（2）圖形運動速度大于搜索范圍會失敗。為了節(jié)約計算量，搜索范圍range不能設(shè)置得太大，否則計算速度將非常緩慢。但是，如圖1.4.17所示，如果兩幀圖像間的物體或者物體中的某一部分運動速度非常快，超過了range的范圍時，那可以肯定圖像是無論如何也匹配不上。因此，運動速度或者局部運動速度過快，都會導(dǎo)致匹配失敗。

（3）計算速度慢。由于需要計算的小塊很多，計算速度過于緩慢也是運動估計應(yīng)用的一大問題。

（4）馬賽克現(xiàn)象，也就是說子塊之間出現(xiàn)非連續(xù)性，嚴(yán)重影響視覺質(zhì)量。

（5）對于兩幀圖像之間圖像不連續(xù)會失敗，即某種圖形在前后兩幀圖像中突然出現(xiàn)或者突然消失時，插入圖像也會出現(xiàn)錯誤。

對于運動估計的研究一直處于不斷進(jìn)步之中，研究的熱點主要集中在如何又準(zhǔn)確又快速地獲得運動向量，各類更快速、搜索范圍更大的搜索算法層出不窮。這些算法的提出和計算機硬件的升級，正逐漸讓運動估計的實時應(yīng)用變?yōu)榭赡堋?/p>

但是，在實際應(yīng)用中，一些問題仍然是運動估計方法所急需解決的。這其中比較常見的有：

（1）兩幀圖像亮度變化。目前算法的價值函數(shù)在子塊亮度發(fā)生變化之后，很有可能搜索到錯誤的位置。因此，改進(jìn)的方向可以是改進(jìn)匹配方法的計算規(guī)則，或者是對圖像亮度進(jìn)行補償，又或是對圖像進(jìn)行歸一化計算。

（2）局部運動速度過大。兩幀圖像之間，如果全部或者部分區(qū)域的運動位移超過搜索范圍，那么可以斷定不可能找準(zhǔn)匹配位置。擴大搜索范圍還是改進(jìn)搜索方法，也是未來可以考慮研究的方向。

（3）計算速度過慢。除了從算法上改進(jìn)之外，還可以考慮引入并行計算，Nvidia的顯卡所附帶的CUDA并行計算功能，可以讓傳統(tǒng)算法速度有很大的提升，對于實時應(yīng)用要求較高的讀者不妨嘗試一下。

（4）馬賽克現(xiàn)象。由于人為將圖像劃分成為小子塊，那么子塊邊緣的非連續(xù)性不可避免，或多或少會帶來一定影響，如何解決這個問題也可進(jìn)行研究。

（5）圖像不連續(xù)的情況。對于兩幀圖像不連續(xù)，比如血管造影圖像，當(dāng)造影劑打入血管的一瞬間，前后兩幀圖像很可能大不相同，這就是不連續(xù)的情況。要從圖形憑空生成或者從消失的圖像中產(chǎn)生新的圖像，是一個十分困難但又非常有意義的課題。

從醫(yī)學(xué)影像的角度來說，如果能夠獲得估計精確的插入圖像，不但可以讓醫(yī)生看著更加舒適，更重要的是能夠讓病人和醫(yī)生接受更少的X射線照射。

對于其他領(lǐng)域，運動估計和運動補償也發(fā)揮著重要作用。需要注意的是，讀者在應(yīng)用過程中應(yīng)當(dāng)結(jié)合自己的項目背景和成像原理進(jìn)行計算策略的調(diào)整，以達(dá)到更好的成像效果。