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

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

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

1.4.1 運動估計簡介

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

1.4.2 運動估計的應用領域

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

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

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

以上就是運動估計應用的簡單介紹，具體的方法需要根據不同的應用背景來設計。

圖1.4.1為運動估計和運動補償的流程示意圖，運動估計（ME）的過程需要參考幀和當前幀參與，計算得到運動向量（MV），這些MV構成壓縮編碼所需的必要信息；而解碼圖像的過程，也即是運動補償（MC）的過程，需要參考幀和運動向量（MV）。

1.4.3 運動估計方法分類

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

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

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

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

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

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

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

（1）獲得前后兩幀圖像，前一幀習慣上稱為參考幀（Referenced Image），后一幀稱為當前幀（Current Image）；

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4.5 相關概念

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

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

1.4.6 匹配方法：價值函數

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

1．絕對平均誤差（MAD）

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

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

2．絕對差和（SAD）

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

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

3．最小均方差（MSE）

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

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

4．歸一化互相關（NCC）

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

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

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

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

1.4.7 搜索算法

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

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

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

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

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

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

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

TSS背后的思想是：在每一個子塊的運動中產生的錯誤構成的曲面是單峰值的。一個單峰值的曲面是一個碗形曲面，這樣由價值函數產生的值在全局極小值中是單調遞增的。

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

3．新三步搜索法（NTSS）

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

如圖1.4.7所示，●是三步搜索法（TSS/3SS）中第一步的檢索點，■是NTSS中加入的屬于第一步的多余的8個點。▲和◆是NTSS的第二步，當第一步中最小值在8個相鄰點中一個的中心時，后面要檢索的點數分兩種情況：5個◆點或者是3個▲點。

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

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

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

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

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

5．菱形搜索法（DS）

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

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

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

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

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

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

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

當上述幾種預測完成之后，找到最佳預測搜索起點，根據所得SAD值的滿意程度，選擇跳轉進入Step2～4中的一個。

Step2：不滿意搜索模式。

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

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

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

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

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

1.4.8 實際應用舉例

本小節將對醫學X射線透視視頻使用運動估計的方法進行插幀，看看是否能讓視頻效果有所提升。

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

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

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

實驗1和實驗2流程框圖如圖1.4.14所示，所用方法為全搜索法（ES）（參看MATLAB程序main＿MEMC＿ES.m），具體包括以下環節：

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

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

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

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

（5）重復步驟（4），直到計算完當前圖像中的所有MV，將所得結果存放在MotionVect中。

（6）計算插入幀圖像：將所得MV的值變為原來的一半MV′，再利用新的MV′進行運動補償MC計算，所得的圖像即為插入幀圖像。

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

【例1.4.1】圖像插幀程序。

    *******************************************************************************
    % 圖像插幀程序
    % 說明：
    %     本程序讀入根目錄下的一段名為XRayVideo的醫學圖像視頻，使用MEMC中的ES
    %     方法進行圖像插幀，得到的新視頻XRayVideoNew幀數和幀率為原來兩倍，結果存放
    %     在．/result文件夾下
    % 注意：
    %       本程序運算速度很慢，需耐心等待
    close all;
    clear all;
    % 預設參數
    MBSize ＝ 16;                                                 %子塊大小
    Range  ＝ 8; %搜索范圍
    % 要讀寫的文件名
    % ReadFileName  ＝ ＇./XRayVideoCard＇;                       %分辨率卡透視
    ReadFileName  ＝ ＇./XRayVideoMan＇;                          %人體胸正位透視
    WriteFileName ＝[ReadFileName, ＇New＇];
    SaveDirectory＝ ＇./result/＇;
    % 讀出視頻信息
    ReadVideoObject ＝ VideoReader([ReadFileName, ＇.avi＇]);
    FrameRateOrigin＝ ReadVideoObject.FrameRate;                  %幀率
    FrameNums ＝ ReadVideoObject.NumberOfFrames;                  %幀數
    % 創建要寫入的視頻對象
    WriteVideoObject ＝ VideoWriter([SaveDirectory, WriteFileName, ＇.avi＇]);
    WriteVideoObject.FrameRate ＝ FrameRateOrigin * 2;
    open(WriteVideoObject);
    % 循環計算插入幀，保存為新視頻文件
    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);
   *******************************************************************************

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

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

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

    *******************************************************************************
    % 圖像插幀程序
    % 說明：
    %       本程序讀入根目錄下的一段名為XRayVideo的醫學圖像視頻，使用MEMC中的ES
    %       方法進行圖像插幀，得到的新視頻XRayVideoNew幀數和幀率為原來兩倍，結果存
    %       放在．/result文件夾下
    % 注意：
    %       本程序運算速度很慢，需耐心等待
    close all;
    clear all;
    %%%%%%%%  預設參數  %%%%%%%%
    MBSize ＝ 16;                                               %子塊大小
    Range＝ 10; %搜索范圍
    %%%%%%%%  要讀寫的文件名  %%%%%%%%
    % ReadFileName  ＝ ＇./XRayVideoCard＇;                     %分辨率卡透視
    ReadFileName  ＝ ＇./XRayVideoMan＇;                        %人體胸正位透視
    WriteFileName ＝[ReadFileName, ＇New＇];
    SaveDirectory＝ ＇./result/＇;
    %%%%%%%%  讀出視頻信息  %%%%%%%%
    ReadVideoObject ＝ VideoReader([ReadFileName, ＇.avi＇]);
    FrameRateOrigin＝ ReadVideoObject.FrameRate;                %幀率
    FrameNums ＝ ReadVideoObject.NumberOfFrames;                %幀數
    %%%%%%%%  創建要寫入的視頻對象  %%%%%%%%
    WriteVideoObject ＝ VideoWriter([SaveDirectory, WriteFileName, ＇.avi＇]);
    WriteVideoObject.FrameRate ＝ FrameRateOrigin * 2;
    open(WriteVideoObject);
    %%%%%%%%  循環計算插入幀，保存為新視頻文件  %%%%%%%%
    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所用到的幾個子函數如下：

    *******************************************************************************
    function Cost ＝ CostFuncMAD(CurBlk, RefBlk, MBSize)
    % 計算兩個子塊的平均絕對誤差(MAD)
    % hehao20131216
    % 輸入
    % CurBlk：當前幀子塊
    % 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：當前幀
    %   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計數
    for i ＝ 1 :MBSize :Row－MBSize + 1                        %分割出子塊
        for j ＝ 1 :MBSize :Col －MBSize + 1
            for m＝ －Range:Range                             %處理每個子塊搜索區
                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 ：包含一個子塊在搜索區中各個位置價值函數值的矩陣
     % 輸出
     %   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內存，第1、2兩組實驗中每幀圖像的計算時間都是每幅圖約13.6s，第3組實驗中每幀圖像計算時間約為22s。

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

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

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

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

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

經過亮度補償之后，亮度變化時抖動有所改善。

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

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

如圖1.4.16所示，每當亮度發生變化時，運動估計往往出現大范圍失敗。

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

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

（4）馬賽克現象，也就是說子塊之間出現非連續性，嚴重影響視覺質量。

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

對于運動估計的研究一直處于不斷進步之中，研究的熱點主要集中在如何又準確又快速地獲得運動向量，各類更快速、搜索范圍更大的搜索算法層出不窮。這些算法的提出和計算機硬件的升級，正逐漸讓運動估計的實時應用變為可能。

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

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

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

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

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

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

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

對于其他領域，運動估計和運動補償也發揮著重要作用。需要注意的是，讀者在應用過程中應當結合自己的項目背景和成像原理進行計算策略的調整，以達到更好的成像效果。