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

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

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