基于超分辨率圖像重建技術(shù)的運動估計研究

顧剛+袁杰

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

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

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

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

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

1 基于塊的運動估計

1.1 塊運動模型

假設(shè)圖像運動可以用塊運動來表征，塊運動通常分為平移、旋轉(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)在如下幾個方面：匹配準(zhǔn)則、搜索策略、塊尺寸選擇方法。

（1） 匹配準(zhǔn)則

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

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

（2） 搜索策略

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

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

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

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

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

算法步驟：

步驟1：設(shè)整像素精度的搜索結(jié)果為以點1為起點的宏塊，設(shè)點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準(zhǔn)則，求得周圍的8個半像素點以及點1為起點的宏塊的匹配準(zhǔn)則函數(shù)值。SAD值最小的就是半像素搜索結(jié)果。同理，可以再以搜索到的半像素點為中心，連同周圍的8個[14]像素點進行搜索，使得運動估計的精度達到[14]像素。

1.2.2 相位相關(guān)法

（1） 僅有平移變換的兩幅圖像的配準(zhǔn)

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

設(shè)[f1（x，y）]為參考圖像，[f2（x，y）]為僅存在位移變化的實測圖像，其位移值為[（x0，y0）]，即[f2（x，y）]=[f1（x-x0，y-y0）]，設(shè)[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)的兩幅圖像的配準(zhǔn)

假設(shè)[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）

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

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

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

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

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

（3） 坐標(biāo)變換

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

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

則：

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

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

2 實驗結(jié)果

2.1 塊匹配算法

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

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

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

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

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

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

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

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

圖7 圖片變化示意圖

將進行半像素搜索中的SAD值標(biāo)出，如圖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壓縮圖像序列的驗證

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

（1） 整像素搜索。模型如圖9所示，兩幅圖都是JPEG 2000格式，相當(dāng)于有噪聲的降質(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 僅存在平移變換的兩幅圖像的配準(zhǔn)

（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)的兩幅圖像的配準(zhǔn)

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

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

將極坐標(biāo)中的點映射到迪卡爾坐標(biāo)系中，通常落在非整像素點上，再通過周圍四個像素點根據(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 坐標(biāo)變換示意圖

圖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)峰。當(dāng)兩幅圖像確實相關(guān)時，由于檢測結(jié)果為一個δ函數(shù)，有非常尖銳的相關(guān)峰，因此能實現(xiàn)圖像的精確配準(zhǔ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)塊匹配算法的應(yīng)用有一定的局限性，如易陷入局部最小值、對于平移超過一定范圍無法進行配準(zhǔn)等；雖然基于平移的塊模型的運動估計是簡單的，但處理旋轉(zhuǎn)、變形運動和不連續(xù)運動場時，效果不是很好。相位相關(guān)方法可以得到非常好的結(jié)果，對于平移變換，用文中的方法只能精確到整像素，對于旋轉(zhuǎn)變換可以達到較高的精度，但是要在運算速度上做出犧牲。

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

參考文獻

[1] 劉丁峰.超分辨率圖像復(fù)原技術(shù)綜述[J].軟件導(dǎo)刊，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