顧剛+袁杰

摘 要： 闡述用于超分辨率重建對兩幀連續(xù)圖像運動估計的若干算法，對其中的塊匹配算法以及相位相關(guān)法進行研究。對塊匹配算法主要研究三步搜索策略以及快速搜索策略，實驗說明塊匹配算法當平移變換量在一定范圍內(nèi)，圖像灰度變化連續(xù)穩(wěn)定，但在處理壓縮圖像序列時易陷入局部最小值。而相位相關(guān)法使用的是傅里葉頻域方法對有相對運動的兩幅圖像進行運動估計，實驗表明相位相關(guān)法不僅可以用于平移變化，且對于旋轉(zhuǎn)變化也可以通過坐標變換后再通過此法進行運動估計。

關(guān)鍵字： 運動估計； 超分辨率重建； 塊匹配； 搜索策略

中圖分類號： TN919?34； TP751.1 文獻標識碼： A 文章編號： 1004?373X（2015）10?0080?07

在數(shù)字圖像的采集與處理過程中，有許多因素會導致圖像分辨率的下降，其主要表現(xiàn)為模糊、噪聲和變形。為了使獲得的圖像具有更高的分辨率、更好的質(zhì)量，通常采用基于信號處理的軟件方法對圖像的空間分辨率進行提高，即超分辨率圖像重建[1]。

超分辨率圖像重建就是從一系列質(zhì)量較差、分辨率較低的圖像來重建圖像質(zhì)量更好、空間分辨率更高的圖像的算法[2]。其核心思想就是用時間帶寬（獲取同一場景的多幀圖像序列）換取空間分辨率，實現(xiàn)時間分辨率向空間分辨率的轉(zhuǎn)換[3]。由于在成象的場景中一般有多個物體做不同的運動，如果直接按照不同類型的運動將圖像分割成復雜的區(qū)域是比較困難的。因此通常采用基于塊的物體運動表示法。

1 基于塊的運動估計

1.1 塊運動模型

假設圖像運動可以用塊運動來表征，塊運動通常分為平移、旋轉(zhuǎn)、仿射、透視等運動形式，一般情況下，塊運動是這些運動的組合，稱為變形運動。

1.2 塊的運動估計算法

目前基于塊的運動估計算法有如下幾種：塊匹配方法、相位相關(guān)法和傅里葉方法[4?5]，下面對其分別進行分析。

1.2.1 塊匹配算法

塊匹配算法的基本思想如圖1所示。在第[k]幀中選擇以[（x，y）]為中心、大小為[m×n]的塊[W，]然后在第[k+1]幀中的一個較大的搜索窗口內(nèi)尋找與塊[W]尺寸相同的最佳匹配塊的中心位移矢量[r=（Δx，Δy）]。搜索窗口一般是以第[k]幀中的塊[W]為中心的一個對稱窗口，其大小常常根據(jù)先驗知識或經(jīng)驗來確定[6?8]。

圖1 塊匹配示意圖

各種塊匹配算法的差異主要體現(xiàn)在如下幾個方面：匹配準則、搜索策略、塊尺寸選擇方法。

（1） 匹配準則

目前典型的匹配準則有：最大互相關(guān)準則、最小均方差準則、最小平均絕對值差、最小絕對誤差和準則等[9?10]。由于最小絕對誤差和準則（SAD）具有不需乘法運算、實現(xiàn)簡單方便的優(yōu)點，在本設計中選用此準則：

[SAD（Δx，Δy）=（x，y）∈WI（x，y，k）-I（x+Δx，y+Δy，k+1）] （1）

（2） 搜索策略

目前的搜索策略有全搜索策略、快速搜索策略、亞像素搜索，下面分別進行介紹：

全搜索策略：計算所有可能位移矢量對應的匹配誤差，然后選擇最小匹配誤差對應的矢量就是最佳位移估計值。這種策略的最大優(yōu)點是可以找到全局最優(yōu)值，但十分浪費時間，因此，提出了各種快速搜索策略。

快速搜索策略：本設計中采用的是n步搜索或?qū)?shù)搜索快速搜索策略。其具體設計思路是：設窗口大小為15×15，當前像素值位于窗口中心，用“0”來標記，如圖2（a）所示。第一步，選擇標記為“0”和“1”的9個像素計算匹配準則函數(shù)，如果最佳匹配仍在“0”處，則無運動。第二步，以第一步最佳匹配對應的像素點為中心選擇8個點（圖中用標記“2”表示），計算這8個點的匹配準則函數(shù)值。第三步，以第二步最佳匹配對應的像素點為中心選擇8個點（圖中用標記“8”表示），計算這8個點的匹配準則函數(shù)值，最佳匹配值即為最后的最佳運動估計。由圖2（a）可見，每進行一步，搜索距離減小一半，并且越來越接近精確解。

人們將上述搜索過程稱為三步搜索[8?9]。進行超分辨率圖像配準是可以繼續(xù)在子像素級上進行搜索，以得到更精確的估計值，這樣就需要大于三步的搜索，稱之為[n]步搜索，由于搜索步數(shù)與窗口內(nèi)像素個數(shù)是對數(shù)關(guān)系，因此，常將這種搜索稱為對數(shù)搜索。另一種對數(shù)搜索策略是在每一步有4個搜索位置，它們以十字形或交叉形布置，如圖2（b）所示。亞像素搜索：僅搜索到整像素精度的運動矢量遠不能滿足高質(zhì)量的圖像重建需要，經(jīng)過三步搜索或全搜索得到整像素的偏移量后，再以最佳整點匹配宏塊為中心進行半像素搜索。

圖2 對數(shù)搜索示意圖

算法步驟：

步驟1：設整像素精度的搜索結(jié)果為以點1為起點的宏塊，設點1為（m，n），如圖3所示。

圖3 半像素搜索原理示意圖

步驟2：用線性插值方法求得以點（m，n）周圍8個半像素點為起點的宏塊的各點灰度值（以點2，6為例）：

[G2=0.5×（I1（m，n-1）+I1（m，n））] （2）

[G6=0.25×（I1（m-1，n-1）+I1（m-1，n）+I1（m，n-1）+I1（m，n））] （3）

步驟3：仍然使用最小SAD準則，求得周圍的8個半像素點以及點1為起點的宏塊的匹配準則函數(shù)值。SAD值最小的就是半像素搜索結(jié)果。同理，可以再以搜索到的半像素點為中心，連同周圍的8個[14]像素點進行搜索，使得運動估計的精度達到[14]像素。

1.2.2 相位相關(guān)法

（1） 僅有平移變換的兩幅圖像的配準

相位相關(guān)技術(shù)是一種非線性、基于傅氏功率譜的頻域相關(guān)技術(shù)，經(jīng)常被用來檢測兩幅圖像之間的平移，根據(jù)頻域信息，利用相關(guān)技術(shù)能夠快速地找到最佳匹配位置[11?12]。

設[f1（x，y）]為參考圖像，[f2（x，y）]為僅存在位移變化的實測圖像，其位移值為[（x0，y0）]，即[f2（x，y）]=[f1（x-x0，y-y0）]，設[F2（ξ，η）]和[F1（ξ，η）]分別為[f2（x，y）]和[f1（x，y）]的傅氏變換，則有：

[F2（ξ，η）=e-j2π（ξx0+ηy0）*F1（ξ，η）] （4）

則功率譜定義為：

[F1*（ξ，η）×F2（ξ，η）F1*（ξ，η）×F2（ξ，η）=e-j2π（ξx0+ηy0）] （5）

式中[F1*]為[F1]的共軛[13?16]。

對式（4）再做傅氏反變換，則可檢測到一δ函數(shù)，δ函數(shù)的位置即為其位移[（x0，y0）]。

（2） 存在平移和旋轉(zhuǎn)的兩幅圖像的配準

假設[f1（x，y）]為參考圖像，[f2（x，y）]為存在位移和旋轉(zhuǎn)變化的實測圖像，令：

[f2（x，y）=f1（xcosθ0+ysinθ0-x0，-xsinθ0+ycosθ0-y0）] （6）

根據(jù)傅里葉變換的平移和旋轉(zhuǎn)理論，有：

[F2（ξ，η）=e-j2π（ξx0+ηy0）*F1（ξcosθ0+ηsinθ0，-ξsinθ0+ηcosθ0）] （7）

假設M1，M2為[F1]，[F2]的幅值，根據(jù)式（7），有：

[M2（ξ，η）=M1（ξcosθ0+ηsinθ0，-ξsinθ0+ηcosθ0）] （8）

從式（8）看出，[F1]，[F2]的幅值是相同的，只不過是相對旋轉(zhuǎn)了[θ0]，式（8）用極坐標寫成：

[M2（ρ，θ）=M1（ρ，θ-θ0）] （9）

由式（9）可見，當兩幅圖像同時又平移和旋轉(zhuǎn)時，如果是用極坐標表示頻譜的幅值，則可表示成只有旋轉(zhuǎn)角度的平移，其幅度是不發(fā)生變化的，這樣就可以用只發(fā)生平移變化的方法來檢測旋轉(zhuǎn)角度[17]。

（3） 坐標變換

由以上分析可知，要配準發(fā)生平移和旋轉(zhuǎn)的兩幅圖像時，可先將兩幅圖像的頻譜由迪卡爾坐標系轉(zhuǎn)化為極坐標系，然后用相位相關(guān)法檢測出兩幅圖像相差的角度，角度配準以后再配準平衡移量，可見從迪卡爾坐標系變到極坐標系也是用此方法進行圖像配準比較關(guān)鍵的一步。因此，引入如下極坐標：

[ρ=ξ2+η2 ， θ=tan-1ηξ] （10）

則：

[ξ=ρcosθ，η=ρsinθ] （11）

在極坐標系中，橫軸坐標為[θ]，對[θ]的采樣間隔可取0.01，為了提高精度，[θ]的采樣間隔可以更小些，但這樣會降低計算速度。設采樣間隔為[Δθ]，則變換后[ρ]?[θ]平面中圖像的大小為[360Δθ][×][ρ]，設極坐標系中點[（ρ，θ）]的值為[G（ρ，θ）]，求出的[ξ]、[η]通常落在原頻譜圖像[F（ξ，η）]的4個像素之間，因此，要求[G（ρ，θ）]的值必須用插值的辦法來計算。常用的插值方法有最鄰近插值、雙線性插值和高階插值。由于雙線性插值速度較快，而且插值效果也比較好，因此選用雙線性插值來求[G（ρ，θ）]。在極坐標系中，[θ]的取值范圍為0°～360°，橫軸坐標[ρ]，縱軸坐標為[θ]，[θ]的采樣間隔取0.01。

2 實驗結(jié)果

2.1 塊匹配算法

2.1.1 簡單確定的降質(zhì)模型

三步搜索法原理如圖4所示。設圖5中有以（i，j）為左上點的大小為L×L的塊，要在圖5（b）中搜索到與之匹配的塊，則將圖5（a）中的點（i，j）標記為點1，加上周圍8個點，計算它們的SAD，SAD最小值對應的點，就是第一步搜索的結(jié)果。再以這一點為中心，加上周圍8個點，此時步長減半，與第一步同樣的方法進行第二步搜索，同理進行第三步搜索。到此為止，實現(xiàn)了精確到整像素的快速搜索。

圖4 三步搜索法原理示意圖

圖5 “cir.bmp”原圖和左移3像素后的圖

以“cir.bmp”圖為例，圖5（a）為原圖，圖5（b）為原圖向左平移3像素，根據(jù)上述原理，可以預想搜索結(jié)果為圖中第7行第9列加粗的3號點。

用坐標圖來表示每一步搜索中各點的SAD值，SAD值最小點便是這一步的搜索結(jié)果。由圖6可以看到，第一步搜索中，3號點的SAD值最小，第二步搜索中，7號點的SAD值最小，第三步搜索中，3號點的SAD值最小，因此參考原理圖4，可見的確搜索到了紅色3號點。在塊匹配運動估計的快速算法中，三步法等在希疏格點上的搜索算法，運算量低，但容易陷入局部極小點。因此對于圖片有一定的要求，當兩圖之間變化不劇烈，差異較小，可以用快速匹配法來進行處理。而當兩幅圖像變化較為劇烈，或是像素的灰度值變化劇烈，容易因快速算法導致陷入局部最小值而得不到正確的結(jié)果。

圖6 整像素搜索分步示意圖

超分辨率的圖像恢復是要求由一系列低分辨率圖像中構(gòu)造出一幅或多幅高分辨率的圖像，接下來進行的是使精度達到半像素的搜索方法。有關(guān)半像素搜索的原理圖見圖3以及相關(guān)闡述。以大小為M×N的“cir.bmp”為原圖，將其行和列分別縮小1倍，即每4個像素平均得到一個像素值，得到大小為[M2×N2]的圖，如圖7所示。

圖7 圖片變化示意圖

將進行半像素搜索中的SAD值標出，如圖8所示，可以看到，SAD最小值所在點為4號點。從代碼運行中可以看出，整像素搜索部分的結(jié)果為x=0，y=-2。意思是（i，j）左移兩個點為整像素搜索的結(jié)果，見圖4，即為紅色3號點。

半像素搜索的結(jié)果為4號點，4號點是1號點右邊0.5個像素點，而1號點是左移2個像素點，綜合可知，搜索結(jié)果為左移1.5像素，這正是制造出的圖7中7.3和7.4的關(guān)系。

2.1.2 JPEG 2000壓縮圖像序列的驗證

在實際應用中，常常遇到的是經(jīng)過壓縮的圖像，而不是簡單確定的模型，因此一個運動估計算法的好壞不能單憑簡單模型的驗證，而要通過更接近實際情況的壓縮圖像的驗證來評判優(yōu)劣。分別采用整像素搜索以及半像素搜索進行處理。

（1） 整像素搜索。模型如圖9所示，兩幅圖都是JPEG 2000格式，相當于有噪聲的降質(zhì)圖，圖9（a）為原圖，圖9（b）為原圖向右移3個像素，向上移1個像素所得。

圖8 半像素搜索部分的SAD值

圖9 整體像素搜索模型

三步搜索的 SAD值如圖10所示：可以看到，三步的SAD最小值所在點分別是7號點，1號點，2號點，由圖4可知，搜索結(jié)果為藍色7號點左上的點，正是原（i，j）點向右3像素，向上1像素?？梢?，若是精確到整像素，快速搜索的塊匹配方法可以對JPEG 2000壓縮圖像進行運動估計。

圖10 JPEG 2000壓縮模型的三步搜索SAD值

（2） 半像素搜索。 模型如圖11所示：這兩幅圖是由圖9（a）和圖9（b）壓縮而得到的，可以認為圖11（b）是圖11（a）向上移0.5像素，向右移1.5像素。

整像素搜索SAD值如圖12所示。

可見，三步搜索的SAD最小值所在點分別為7號點，1號點，1號點，參考圖4，[Δx1]=0，[Δy1]=4。在進行半像素搜索，SAD值如圖13所示，可見SAD最小值所在點為6，即[Δx2=-0.5，Δy2=-0.5]。綜上所述，有[Δx=Δx1+][Δx2=-0.5，Δy=Δy1+Δy2=3.5]。制造模型的[Δx=-0.5，Δy=1.5]，結(jié)果不符。注意到，整像素搜索的結(jié)果有較大偏差，而在圖13中不難看出，點1雖然是最小值，SAD1=1 249，但點3的值與點1相近，如圖4所示，SAD3=1 265。

圖11 半像素搜索模型

圖12 JPEG 2000再壓縮圖像三步搜索SAD值

[圖13 [Δx1]=0，[Δy1]=4之后 圖14 點3的SAD值

的半像素搜索結(jié)果 ]

如果將點3作為整像素搜索第二步的結(jié)果，參考圖3可知： [Δx1=0，Δy1=2]再進行半像素搜索，結(jié)果如圖15所示。則：[Δx=Δx1+Δx2=Δy1+Δy2=][1.5-0.5，Δy=1.5]，與制造出的模型完全符合。

2.2 相位相關(guān)方法

2.2.1 僅存在平移變換的兩幅圖像的配準

（1） 簡單確定的降質(zhì)模型

圖16（a）為lean原圖，（b）為原因右移20個像素。對圖16進行相位相關(guān)處理。具體算法見1.2.2節(jié)。

圖17中，X=21，則[Δx]=20，和實際吻合。

[圖15 [Δx1]=0，[Δy1]=2之后的 圖16 lena原圖和右移

半像素搜索結(jié)果 20個像素 ]

圖17 僅存在平移變換的相位相關(guān)結(jié)果

（2） JPEG 2000壓縮模型

對圖9進行相位相關(guān)處理，處理后結(jié)果如圖18所示，可以看到，x=4，y=104，則：

[Δx=4-1=3， Δy=104-1-104=-1]

即向右3像素，向上1像素，和模型的平移變換一致。

圖18 JPEG 2000壓縮圖像平移變換相位相關(guān)

2.2.2 僅存在旋轉(zhuǎn)的兩幅圖像的配準

在處理旋轉(zhuǎn)變換時，最關(guān)鍵的就是進行坐標系的變換。把圖像從迪卡爾坐標變換到極坐標系：

[ξ=ρcosθ， η=ρsinθ] （12）

將極坐標中的點映射到迪卡爾坐標系中，通常落在非整像素點上，再通過周圍四個像素點根據(jù)權(quán)重進行插值，例如：[ξ]=14.3，[η]=15.2，見圖19，則第14行占比重0.7，第15行占比重0.3，第15列占比重0.8，第16列占比重0.2，則點（14，15）的權(quán)重為0.7×0.8，點（14，16）的權(quán)重為0.7×0.2，點（15，15）的權(quán)重為0.3×0.8，點（15，16）的權(quán)重為0.3×0.2。其算法如圖20所示。

對圖21中存在旋轉(zhuǎn)的兩幅普通圖像進行相位相關(guān)處理，結(jié)果如圖22所示。

圖19 坐標變換示意圖

圖20 存在平移和旋轉(zhuǎn)變換時的相位相關(guān)算法

圖21 lena原圖和逆時針旋轉(zhuǎn)30°圖

圖22 只有旋轉(zhuǎn)變換的相位相關(guān)結(jié)果

從圖22可以看到y(tǒng)=31，即[Δθ]=30°，結(jié)果完全正確。對圖23中的JPEG 2000壓縮原圖（a）和其順時針旋轉(zhuǎn)[π20]的圖（b）進行相位相關(guān)處理。處理結(jié)果如圖24所示：可見，y=352，根據(jù)代碼，[Δθ]的精度為1°，所以[Δθ]=352-1-360=-9°，即順時針旋轉(zhuǎn)9°，與模型中的順時針旋轉(zhuǎn)[π20]相一致。

實驗驗證結(jié)果說明了相位相關(guān)方法的特點：

（1） 尖銳的相關(guān)峰。當兩幅圖像確實相關(guān)時，由于檢測結(jié)果為一個δ函數(shù)，有非常尖銳的相關(guān)峰，因此能實現(xiàn)圖像的精確配準。

（2） 相位相關(guān)算法對噪聲有較高的容忍度，檢測結(jié)果與照度無關(guān)，同時可以大大減少幾何失真對匹配性能的影響。因此對于簡單確定的降質(zhì)模型和高倍率壓縮的模型都能達到精確的相關(guān)估計。

圖23 壓縮原圖和順時針旋轉(zhuǎn)[π20]圖

圖24 JPEG 2000旋轉(zhuǎn)變換的相位相關(guān)

3 結(jié) 語

運動估計是進行超分辨率圖像重建時不可缺少的前提步驟，運動估計的精度對于重建的質(zhì)量有著直接的影響，因此在進行運動估計時，力求算法穩(wěn)定，精度高，對于噪聲的容忍能力強。經(jīng)過試驗發(fā)現(xiàn)塊匹配算法的應用有一定的局限性，如易陷入局部最小值、對于平移超過一定范圍無法進行配準等；雖然基于平移的塊模型的運動估計是簡單的，但處理旋轉(zhuǎn)、變形運動和不連續(xù)運動場時，效果不是很好。相位相關(guān)方法可以得到非常好的結(jié)果，對于平移變換，用文中的方法只能精確到整像素，對于旋轉(zhuǎn)變換可以達到較高的精度，但是要在運算速度上做出犧牲。

注：本文通訊作者為袁杰。

參考文獻

[1] 劉丁峰.超分辨率圖像復原技術(shù)綜述[J].軟件導刊，2009（12）：183?185.

[2] WOOD S L， LAN Hsueh?Ban. Edge detection performance in super?resolution image reconstruction from camera arrays [J]. IEEE Transactions on Image Processing， 2006 （1）： 38?43.

[3] BAI Yun?fei， HU Jing， LUO Yu?pin. Self?adaptive blind super?resolution image reconstruction [J]. IEEE Transactions on Image Processing， 2010 （9）： 1208?1213.

[4] FENG Xiang?bin， CHEN Yong?hong. Digital image watermarking based on Super?Resolution Image Reconstruction [J]. IEEE Transactions on Image Processing， 2012 （10）： 1778?1782.

[5] 湯華蓮，莊奕琪.運動估計的分層搜索算法及FPGA實現(xiàn)[J].現(xiàn)代電子技術(shù)，2004，27（4）： 84?86.

[6] YIN Bin， DUAN Hui?chuan. Image stabilization by combining gray?scale projection and block matching algorithm [J]. IEEE Transactions on Image Processing， 2009 （9）： 1262?1266

[7] LIU Yu?hong， TU Dan. A digital image stability Algorithm [J]. Computer Simulation， 2008， 48： 200?204.

[8] VELLA F， CASTORINA A， MANCUSO M， et al. Digital image stabilization by adaptive block motion vectors filtering [J]. IEEE Transactions on Consumer Electronics， 2002， 50： 796?801.

[9] ZAYNAB Ahmed， ABIR Jaafar Hussain， DHIYA Al?Jumeily. Edge detection for fast block?matching motion estimation to enhance mean predictive block matching algorithm [J]. IEEE Transactions on Consumer Electronics，2012， 52： 1?5.

[10] LIN Yih?Chum， TAI Shen?Chum. Fast full?search hock? atching algorithm for motion?compensated video compression [J]. IEEE Press，1996 （4）： 914?919.

[11] JIA Ruiming， ZHANG Hong， WANG Lei， et al. Digital image stabilization based on phase correlation [J]. IEEE Press， 2009 （3）： 485?489.

[12] YUAN Fei， ZHANG Hong， JIA Ruiming， digital image stabilization based on log?polar transform [C]// Proceedings of Fourth International Conference on Image and Graphics. [S.l.]： [s.n.]， 2007： 111?115.

[13] LANG Li?ying ZHANG Xiao?fang. Study on phase correlation algorithm in intelligent transportation systems [J]. IEEE Press， 2008 （2）： 275?279.

[14] LIU Ji?Lin， SONG Jia?Tao. Vehicle license plate recognition system with high performance [J]. Acta Automatica Sinica， 2003， 29（3）： 457?465.

[15] WEN C?Y， YU C?C， HUN Z?D. A 3D transformation to improve the legibility of license plate numbers [J]. Journalof Forensic Sciences， 2002， 47（3）： 578?585.

[16] ZITOVA B， F LUSSER J. Image registration methods： a survey [J]. Image and Vision Computing， 2003， 21（11）： 977?1000.

[17] ZHANG Jing， WANG Chang?shun， LIAO Wu?ling. An image mosaics algorithm based on improved phase correlation [J]. IEEE Press， 2009 （2）： 383?386.endprint