一種改進的自適應(yīng)十字模式搜索算法在圖像配準中的應(yīng)用

一種改進的自適應(yīng)十字模式搜索算法在圖像配準中的應(yīng)用

序列圖像的重建通常包括兩個步驟：第一，將低分辨率圖像的噪聲和檢測知識與之前的知識結(jié)合起來，以獲得高分辨率的序列圖像。重建超分辨率通常包括兩個步驟。首先，將低分辨率圖像作為圖像的輪廓，即運動評估流程。然后，使用頻率域或域間重建算法將已配制的低分辨率圖像整合到高分辨率圖像。在視頻超分辨率重建中，重建效果對較高的噪聲源的精度有很大的影響。由于不完整的輸出結(jié)果往往導(dǎo)致重建失敗。運動評估方法一般可分為三種類型：空空空頻域和空頻域方法。在超分辨率重建中，最常用的方法是基于光流法和基于塊的方法。在塊匹配算法中,全搜索算法精度最高,它對搜索范圍內(nèi)所有的像素點逐一進行匹配運算以得到全局最優(yōu)運動矢量,但其巨大的計算量和時間開銷阻礙了它的有效應(yīng)用,為此,后續(xù)出現(xiàn)了許多快速搜索算法,如新三步搜索法(Newthreestepsearch,NTSS),簡單有效搜索法(Simpleandefficientsearch,SES),六邊形算法(Hexagon-basedsearch,HEXBS),定向菱形法(Directionaldiamondsearch,DDS),多模板六邊形法(Multiplepatternhexagonsearch,MPHS)等.文獻[6提出一種自適應(yīng)十字搜索(Adaptiveroodpatternsearch,ARPS)算法,該算法利用相鄰塊的運動矢量作為當前塊的預(yù)測矢量,大大地減少了運算量,但因為初始搜索點的問題,往往需要多執(zhí)行一些不必要的搜索.本文基于ARPS塊匹配算法,提出了一種小波變換的分層塊匹配算法,其主要思想是對預(yù)測幀的首行/列宏塊采用小菱形搜索模式(Smalldiamondsearchpattern,SDSP)進行搜索,得到精度較高的預(yù)測運動向量(Motionvector,MV),為在其他宏塊上應(yīng)用ARPS算法提供更準確的預(yù)測MV,而對其他宏塊則直接運用自適應(yīng)十字模式(Adaptiveroodpattern,ARP)進行搜索.同時,引入小波理論,利用小波域中各子圖像在統(tǒng)計和空間上的相關(guān)性,在小波變換域?qū)崿F(xiàn)匹配宏塊的搜索,把點的匹配搜索與塊的匹配搜索統(tǒng)一起來,取得了比一般塊匹配方法更高的精度.最后采用基于集合理論的凸集投影算法對配準后的圖像進行重建,取得了較好的重建效果.1小波變換圖像搜索及分析小波變換可得到不同頻帶下的子圖像,能夠成比例地降低圖像尺寸,通過對低頻子帶圖像的分析,可以獲得上一級圖像的平均統(tǒng)計特性.對子圖像“點”的分析,實際上是對上一級圖像“區(qū)域”的分析,有效地擴大了圖像的搜索范圍.基于小波變換的搜索方法與原有的塊匹配方法一致,小波變換實現(xiàn)了對點搜索與對塊搜索的統(tǒng)一.采用幅頻特性不變的二維離散可分離小波,其子圖像定義如下:其中,h(n)和g(n)分別是對應(yīng)同一小波基的低通濾波器和高通濾波器.圖像經(jīng)過一次小波分解得到尺寸和頻率減半的四個子圖像,Cj,kl為原圖像的低頻子圖像,它保留了原始圖像重要的視覺和統(tǒng)計特性,各級的低頻子圖像保留了原始圖像的主要信息,運動矢量估計主要分析各級的低頻子圖像.d(1)j,kl,d(2)j,kl,d(3)j,kl分別為水平方向、垂直方向和對角線方向的細節(jié)圖像.2基于小波變換的層次結(jié)構(gòu)算法2.1小三角形搜索模式的優(yōu)化大多數(shù)情況下,同一個運動對象的相鄰宏塊具有相似的運動,所以當前塊的運動行為可以使用其空間或者時間域上相鄰塊的MV來預(yù)測.參考幀中相同位置的塊是最好的選擇,但是利用時間相關(guān)需要記錄整個前一幀的MV域,占用的存儲空間較大所以可以考慮用當前塊的左、上、左上和右上方向上的塊作為相鄰的參考塊.圖1為當前塊的鄰塊區(qū)域示意圖.表1為測試3個圖像序列當前塊與相鄰塊的運動矢量相等的結(jié)果.從表1可以看出,通過對圖像序列的統(tǒng)計結(jié)果分析表明,當前塊與其左、上鄰塊的運動矢量相等的比重相對最大,與左上、右上鄰塊的相關(guān)性次之,但因為使用的鄰塊越多,計算復(fù)雜度越高,為了減少計算代價,只選擇將左鄰塊作為預(yù)測塊進行計算.為避免復(fù)雜的平方運算,本文采用常見的平均絕對誤差函數(shù)(Meanabsolutedifference,MAD)作為匹配誤差準則,其定義如下:式中,fn為當前幀的圖像塊,fn-1為前一幀中的預(yù)測塊,大小均為M×N.基于最小平均絕對誤差函數(shù)的運動估計就是求MAD的最小值,令MAD達到最小的(x,y)就是當前塊的運動矢量,即求在運動估計的開始,計算當前塊與參考塊同一位置之間的匹配誤差,若其MAD值小于設(shè)定的誤差容限則當前塊判為不變塊,運動向量為零并停止搜索,這樣可以減少很大一部分計算量;如果當前塊是首行(列)宏塊,則直接采用固定的小菱形搜索模式(SDSP)進行搜索;如果不是首行或首列宏塊,則按照粗–精定位的方法進行搜索.搜索方法如圖2所示.粗定位階段,首先根據(jù)預(yù)測MV的x和y坐標確定搜索臂長Γ,臂長確定公式為首先把大十字模型的中心對準搜索窗的中心點,根據(jù)搜索臂長檢測4個搜索點以及預(yù)測MV代表的點找到使MAD值最小的點.通過初步搜索,粗定位出每個宏塊中對象運動的主要趨向,并把該最小值點作為小十字模型的中心點.完成初步搜索后,采用SDSP模型檢測它的搜索點,當最小的MAD值位于小菱形中心時,中心點即為運動矢量,搜索結(jié)束;如果不是中心點,重復(fù)此步驟,直到最小匹配錯誤點為中心點,完成MV的精定位.大十字五點模型用于在一個大的搜索范圍內(nèi)鎖定粗略的運動矢量,而SDSP模型具有搜索點數(shù)少、易收斂和結(jié)構(gòu)簡單等優(yōu)點,在檢測小范圍內(nèi)的運動矢量時具有良好的性能,因此SDSP用于進行細微的調(diào)整.IARPS算法在圖像進行宏塊劃分之后,對首行/列塊直接運用SDSP模型進行搜索,而對其他的宏塊直接運用ARPS算法.這樣做的原因是利用SDSP模型搜索點數(shù)少、精度高的特點,較快速地得到精度較高的MV,為在其他宏塊上應(yīng)用ARPS算法提供更準確的預(yù)測MV.同時,對于相鄰兩幀圖像中的不變宏塊采用零運動預(yù)先判斷以減少算法的計算量,并利用運動矢量的空間一致性提高預(yù)測運動矢量的質(zhì)量.2.2基于小波變換的圖像配準基于小波變換的塊匹配方法與原有塊匹配方法是一致的,但由于加入小波變換后,搜索只需在其低頻分量的圖像上進行,減少了匹配點的搜索個數(shù).圖像經(jīng)過小波分解后,原始圖像分解成沿水平、垂直、對角三個方向的高頻圖像和一個低頻圖像.設(shè)原始圖像為I,小波分解為式中,IL為低分辨率圖像,IH為水平高頻細節(jié),IV為垂直高頻細節(jié),ID為對角線方向上的高頻細節(jié),dwt2為二維離散小波變換.將連續(xù)兩幀圖像I、P(其中I為待匹配圖像,P為參考幀)分別進行一次二維離散小波分解,得到兩幀圖像的低頻分量圖像IL和PL,將IL和PL按照上文所述的方法進行塊匹配得到低頻分量的配準圖像IL*,將配準圖像IL*與高頻分量的三個細節(jié)圖像IH,IV和ID進行小波逆變換即得到配準后的圖像I*.基于小波變換的塊匹配方法與傳統(tǒng)塊匹配方法相比,濾除了原圖像的高頻噪聲,防止了在含噪原圖像上進行塊匹配不準確的缺點;另外,在低頻分量圖像的N×N范圍進行塊匹配,相當于原圖像在2nN×2nN的范圍內(nèi)進行匹配搜索(n為小波分解的層數(shù)).小波變換中各級塊的尺寸由運動程度和小波變換級數(shù)共同決定,宏塊的大小根據(jù)經(jīng)驗和圖像序列的具體運動情況而定.3凸集超分辨率重建圖像超分辨率重建算法可以分為兩大類:頻域法和空域法.空域算法使用通用的觀察模型,具有良好的適應(yīng)性和重建效果,是目前主要的研究方向.凸集投影(Projectionsontoconvexsets,POCS)算法利用投影至凸集的原理進行圖像重構(gòu),直觀而且有效,是最有前途的空域算法之一.POCS算法將成像系統(tǒng)的先驗知識作為圖像重構(gòu)的約束條件,每個約束條件對應(yīng)于整個成像空間中的一個含有理想高分辨率圖像的凸集.這些凸集的交集中的任何一點都被認為是可以接受的圖像重構(gòu)的結(jié)果.POCS算法從圖像的初始估計出發(fā)進行迭代處理,并按照模擬誤差逐步修正圖像,最終將超分辨率重建圖像投影到所有限制集的交集中,形成最后的解空間.POCS的迭代過程即是從成像空間中任意一點開始投影定位到凸集的交集上的過程.在圖像配準的基礎(chǔ)上,凸集投影圖像超分辨率重建實現(xiàn)的基本流程是先對超分辨率圖像進行預(yù)估,也就是建立參考幀,然后根據(jù)觀察圖像序列對參考幀進行修正,直至得到可以接受的重構(gòu)結(jié)果.圖3所示為基于小波變換的改進的自適應(yīng)十字模式搜索算法(Improvedadaptiveroodpatternsearchalgorithmbasedonwavelettransform,W-IARPS)塊匹配和POCS的超分辨率重建框圖.首先將相鄰兩低分辨率圖像序列進行小波變換得到各自低頻圖像,然后將低頻圖像配準后進行小波逆變換,得到配準后的低分辨率圖像序列,再將該序列按照凸集投影方法進行超分辨率重建.圖3中A,B兩個區(qū)域表示兩個凸集.x0表示初始估計值,經(jīng)過一定次數(shù)的迭代,最后收斂到兩凸集之交的一個邊界定點xn,至此完成超分辨率重建.4序列測試結(jié)果為驗證本文提出的配準算法的有效性,首先采用Tennis,Mobile及Mother&Daughter測試序列在相同的條件下比較ES,W-ES,SES,W-SES,ARPS和W-IARPS幾種算法的性能.實驗采用宏塊大小為16像素×16像素,搜索窗為±8像素,匹配準則使用MAD準則.加入一次小波變換后,宏塊和搜索窗大小均減半.圖4和圖5分別為Tennis序列預(yù)測幀的峰值信噪比(Peaksignaltonoiseratio,PSNR)和每個宏塊的平均搜索點數(shù).從圖4可以看出,加入小波變換后,圖像的PSNR值增加,即配準圖像的質(zhì)量提高,W-IARPS算法得到的PSNR曲線除略低于全搜索外,和W-SES算法接近,搜索準確度相近.圖5為用不同算法(由于全搜索算法的計算量太大,圖中未畫出)求出每一幀的平均搜索點數(shù)的比較結(jié)果.可以看出,采用本文算法的平均搜索點數(shù)要明顯低于其他算法,搜索點數(shù)最少.表2和表3為不同測試序列在不同算法中的實驗結(jié)果.從表2中可以看出,ES算法進行窮盡搜索,運算量過大.W-ES由于加入了一次小波變換,搜索點數(shù)大大減少.本文提出的W-IARPS方法搜索點數(shù)最少,在Tennis序列中只需要4.70個點即可找到最優(yōu)矢量,其搜索點數(shù)減少55.17倍.對于Mobile和Mother&Daughter序列的測試也得到了類似的結(jié)果.表3為以Mother&Daughter序列為例,處理不同幀數(shù)時的計算時間.ARPS算法對單幀圖像的處理時間少于本文算法0.35s,但隨著圖像幀數(shù)的增加,W-IARPS的計算時間逐漸少于ARPS法.處理60幀圖像時,已經(jīng)少于ARPS算法1.30s.雖然本文算法對單幀圖像的計算時間大于ARPS算法,但對圖像序列的總體計算時間有所減少,說明雖然小波變換和逆變換會增加部分計算時間,但當圖像序列的幀數(shù)較多時(本實驗Mother&Daughter序列中為10幀),圖像序列整體搜索點數(shù)減少所節(jié)省的時間大于小波正反變換所需的時間,故處理圖像序列時本文算法的計算時間最少.序列幀數(shù)越多,時間節(jié)省越大.表4中ES算法得到的配準圖像的PSNR值高于ARPS,搜索精度最高,加入小波變換后,兩種方法的搜索精度均有較大程度提高.本文提出的W-IARPS方法的重建圖像質(zhì)量逼近全搜索法,在Mobile序列中僅低于W-ES算法0.06dB.綜合表2～4可知,本文算法在配準精度上最接近于全搜索,且其處理圖像序列所需的時間小于ARPS算法,故綜合性能最優(yōu).將已通過上述塊匹配方法配準的序列圖像采用凸集投影(POCS)算法進行重建,圖6所示為采用Teddy序列進行超分辨率重建第5,17,26,38幀的實驗結(jié)果.圖6(a)所示為Teddy序列的原始低分辨率圖像幀,圖6(b)為重建后的高分辨率幀.從圖中放大的文本部分可以明顯看出,經(jīng)過超分辨率重建后的圖片具有更高的分辨能力和更好的視覺效果.圖7所示為Mobile序列第33幀的重建結(jié)果.圖7(a)是參考幀的雙線性插值結(jié)果,圖像整體比較模糊,且顏色較暗;圖7(b)為采用ARPS算法配準后重建的高分辨率圖像;圖7(c)為采用本文算法配準的重建結(jié)果.通過比較發(fā)現(xiàn),通過本文方法實現(xiàn)的超分辨率重建效果無論是在圖像的亮度還是在清晰度方面都有所改善,圖片中日歷的數(shù)字部分較為明顯.5配準精度對比本文提出的基于小波變換的分層塊匹配算法應(yīng)用小波理論將點的匹配搜索與塊的匹配搜索統(tǒng)一起來,能夠明顯降低宏塊的平均搜索點數(shù),且從配準圖像的PSNR值可以看出該運動估計算法比其他快速塊匹配算法具有更高的配準精度,適應(yīng)了視頻超分辨率重建對圖像配準精度的要求.使