基于多尺度塊搜索的單幅圖像超分辨率重建

申世聞，曹 國，孫權森

(南京理工大學計算機科學與技術學院，南京 210014)

1 概述

圖像超分辨率技術可以分為2個方向:基于重建的超分辨率技術［1-2］和基于學習的超分辨率技術［3-4］?；谥亟ǖ某直媛始夹g利用多幅具有互補信息的低分辨率圖像來復原其對應的高 /低分辨率圖像［5］，這些互補信息可以是亞像素差，也可以是不同的模糊核;此方法存在很多問題，如當放大倍數(shù)過大時(2倍以上)，會因重建過程中能夠使用的互補信息太少，導致重建效果不太理想［6］?；趯W習的超分辨率技術基本思想為通過對高/低分辨率圖像庫的學習，在某種最優(yōu)化方法下求出給定低分辨率圖像對應高分辨率圖像。如Freeman的方法［3］:運用馬爾科夫網(wǎng)絡找出對應的高分辨率塊的最大后驗概率值，在此基礎上也有一系列改進方法［1，7］。以上這些方法都需要大量的訓練集圖像，且重建出的圖像有明顯的偽邊緣，看起來十分不自然。重建速度過慢也是這類方法一個共同的缺陷。針對上述問題，如何在無任何先驗信息的前提下，能夠快速地對一張圖像進行超分辨率重建，且重建效果良好，成了本文研究的問題。

本文在文獻［8］的研究基礎上做了3點改進:(1)把查找到的2個相似低分辨率塊之間的差值進行插值放大，并加到對應的高分辨率塊上。避免了低分辨率相似塊之間差異較小，但是兩者對應的高分辨率塊卻差異較大的情況。(2)不僅考慮到要重建的低分辨率和學習到的相似低分辨率之間的差異，而且考慮到重建出的高分辨率塊是否和其周圍的高分辨率塊兼容。由于文獻［8］并沒有考慮這幾點，使得其重建后的高分辨率圖像有一定的鋸齒現(xiàn)象，并且圖像看起來極其不自然。(3)引入最新的隨機塊搜索［9］算法，使得算法用于KNN查找的速度大幅提高，降低了重建時間。

2 基于學習的超分辨率技術

在自然圖像中，一副圖像中像素塊相似甚至相同的現(xiàn)象也較為普遍。文獻［8］在伯克利分割數(shù)據(jù)庫上做了大量的實驗，并對結果進行了統(tǒng)計。實驗證明源圖像上多于90%的5×5小塊，在此圖像的其他位置都可以找到9個或者更多的相似塊，大約80%的圖像塊在源圖像的0.41=1.25–4下采樣級別上有9或者更多的相似塊，大約70%的圖像塊在源圖像的0.26=1.25–6下采樣級別上有9或者更多的相似塊。這一結論奠定了利用一幅圖像及其下采樣圖像的塊冗余信息進行高分辨率重建的基礎。文獻［8］把基于重建和基于學習的超分辨率方法結合起來，利用不同級的相似塊，構成對應的高/低分辨率塊集，通過學習找出低分辨率塊對應的多個中間級的高分辨率塊。把這多個中間級高分辨率看成具有互補信息的冗余塊，最終用這些互補信息來復原目標級高分辨率塊。

2.1 高低分辨率圖像間的線性約束

現(xiàn)給定一幅低分辨率圖像L，假定它是由原高分辨率圖像H經過模糊和下采樣過程得到:L=(H*B)↓s。這里，↓代表下采樣操作;s是H和L之間下采樣的縮小比例因子;B是相應的模糊核(點擴散方程);*為卷積。因此，L中的每個像素p的值可由高分辨率圖像相應位置上像素q∈H及其周圍的像素進行線性變換求得，有:

這里用高斯核對B進行估計，i的大小由模糊核B來決定。如果有足夠多的低分辨率圖像，就形成了上述方程的方程組，并且如果獨立方程的個數(shù)大于未知數(shù)的個數(shù)，則方程(1)有解。正如文獻［8］所述，一幅圖像本身及其下采樣圖像中有大量的冗余塊。設P為低分辨率圖像L中以p為中心的一個5×5圖像塊，L中存在多個相似圖像塊 P1，P2，…，Pk(在L下采樣中也可找到多個相似塊)。假設這k個低分辨率塊來自于k個不同低分辨率圖像，且這些低分辨率圖像描述的是同一個高分辨率場景?？衫脗鹘y(tǒng)的多幀超分辨率重建方法進行亞像素配準［2］，并根據(jù)P和Pi之間的相似度對相應方程的可信度進行衡量，最終解出目標高分辨率H。

2.2 不同分辨率圖像級聯(lián)中的塊冗余

現(xiàn)在令I0，I1，…，In為從低分辨率L到目標高分辨率H的級聯(lián)，且分辨率依次遞增(即I0=I，In=H)。相應的模糊核為 B0，B1，…，Bn(點擴散函數(shù))，這樣每一個Il滿足L=(Il*Bl)↓sl(sl表示相應的放縮因子)。仍然用高斯核來代替，方差由 sl決定。放縮因子sl用sl=αl表示，這里α為相鄰級之間的放大倍數(shù)。

為了得到各級中間圖像Il，可以分下面3個步驟。

(1)建庫:為每級圖像建立低/高分辨率庫［P，Q］l。設 L=I0，I－1，…，I－m為從 L 開始分辨率逐漸降低的一組級聯(lián)，這些低分辨率圖像可以由L進行模糊下采樣得到 I－l=(L*B－l)↓sl，B－l=Bl。為 I－l中每個點取以其為中心的塊，并在 I0中取相應位置 sl·∈I0上的塊 Q0(sl·)，這樣就構成了低高圖像塊庫在后面的實驗中，取低分辨率塊大小為5×5，若放大2倍sl=2，則高分辨率塊大小為9×9。有些文獻中用其他形式特征來建庫，如拉普拉斯金字塔［7］、梯度特征［4］。

(2)相似塊查找:在庫中搜索和P0(p)相似的低分辨率塊，文獻［8］里面用到了近似最近鄰查找算法(k=9)［10］。

圖1 高分辨率塊學習過程

2.3 隨機最近鄰查找算法的引入

由前文可知，求相似塊是一個極其重要的步驟。但由于源圖像塊與各級下采樣塊數(shù)目過多，想要準確地查找到k個近鄰需要花費大量的時間。例如用最普通的查找算法需耗時O(r2M)，其中，r為塊大小;M為圖像中的像素數(shù)。故基于學習的超分辨率方法一般選用近似最近臨查找法。這些方法基本上是基于樹結構的，如 TSVQ［11］，kd-trees［12］和 VP-trees［13］，這些方法都是利用塊的維數(shù)進行查找。并且經常和降維技術結合起來使用，如PCA［12］。能夠達到耗時O(mMlogM)，但是建樹時需多增加O(M)的內存空間，這里m為樹的維數(shù)。

但是基于樹的查找方法在建樹和查找上面仍然花費大量時間，它并沒有考慮到圖像具有局部相似性。為此，本文引入了Connelly的隨機塊匹配算法［10］，此算法在時間和空間消耗上面都要優(yōu)于帶降維的kd-trees。它幾乎不需要額外的空間消耗，仍需耗時O(mMlogM)。雖然在數(shù)量級上和最右的基于樹結構的查找算法相同，但是實際上的常數(shù)要遠小于基于樹結果的查找算法。由于本文的著重點并不在求隨機最近鄰這一步驟，因此該方法的詳細步驟在此不予列出。此方法也有一定的局限性，只能用于如圖像這類具有局部相似性的搜索，并且實驗結果也受到實驗環(huán)境的影響(并行計算)。

3 目標圖像的重建

本文對上KNN查找到了中間級高分辨率塊做了改進，并且在用這些中間級高分辨率塊復原目標級高分辨圖像時考慮到多方面因素。本文通過自適應加權使得重建結果模糊度和鋸齒現(xiàn)象都有所降低，看起來更自然。

3.1 高分辨率塊的改進

雖然P1，P2，…，P9和P之間較為近似，但是不同Pi對應的高分辨率塊Qi之間卻差別很大［3］，這也是由文獻［8］重建出的圖像看起來不自然的一個原因。并不直接使用學習出的Qi作為P對應的高分辨率估計值。本文把P與Pi之間的差值進行放大(可采用雙立方法)，再加到對應的高分辨率Qi上面，使得到的高分辨率估計值更加準確，如圖2所示。

圖2 修正學習到的高分辨率Qi

其中，σ1為高斯核的標準差;λ1，λ2為系數(shù);w1不僅考慮到了由于相似度不同導致的9個相似塊的可信度不同，而且考慮到了相鄰塊重疊部分的相似度對重建結果的影響，這樣不僅使得重建出的目標分辨率H和真實的高分辨率圖像更吻合，而且大大消除了鋸齒現(xiàn)象，使得重建效果看起來更真實。σ1的取值也對最終的放大效果有著重要影響，關系到最終圖像的清晰度。

3.2 不同權值下數(shù)值的求解

并不是由式(1)直接求出 H，而是依次把 I1，I2，…，Il當成目標高分辨率，每級都要求出直到H。當把 Il+1當作目標分辨率進行重建時(此時I1，I2，…，Il已求出)，同時利用2.1節(jié)在L上找到了多個低分辨率塊P1，P2，…，Pk和2.2節(jié)中以 L為中間級學習到的多級(1，2，…，l+1)高分辨率塊(也可以Ii，i≤l為中間級，學習出 i+1，i+2，…，l級的高分辨率塊)。通過塊加權分別把每級高分辨塊拼接融合成一幅高分辨率圖像。

當求出圖像Il+1時，再通過相同的模糊和下采樣求出和L一樣大小的低分辨率圖像，并和L比較。差距的大小預示著求出的高分辨率圖像Il+1和真實圖像之間的差距?？梢杂谩胺赐队啊狈ǎ?］來修正求出的高分辨率圖像，此過程和圖2類似。這一步驟確保每個新得到的高分辨率圖像Il+1和輸入的低分辨率圖像L一致。

4 實驗結果及分析

本文從有參圖像質量評價和無參圖像質量評價2個方面進行比較。有參質量評價所用的20張灰度圖片來自Granada大學計算機視覺組數(shù)據(jù)庫。包括自然圖像，如人像、風景、建筑、靜物、顯微鏡圖像、合成圖像以及遙感圖像。每張圖像的大小都是512×512像素。實驗操作平臺硬件為Intel Core i5-2450 MB、2.5 GHz、4 核心、3 GB 內存，軟件配置為Windows 7 旗艦版32位操作系統(tǒng)，Matlab R2009a。

4.1 隨機查找算法效率比較

本文采用的隨機查找算法［9］，在相同的配置下和文獻［8］中所用到的 kd-tree［10］和 priority-kdtree［10］算法進行比較。以2個相似塊差值的加權平方和作為塊與塊之間的距離，權值大小和式(3)相同。查找時間以秒為單位，比較結果如表1所示。表中第1行為在源圖像中查找相似塊。

表1 各種搜索方法的對比

本文通過調節(jié)參數(shù)使塊與塊的平均距離盡可能相同，可以看出隨機查找算法在塊與塊的平均距離略小的情況下，速度提高了近2倍。表1中第2行為在源圖像的下采樣圖像中查找的實驗結果，實驗時先對源圖像進行模糊加高斯白噪聲，下采樣率為0.5。而且還發(fā)現(xiàn)當近鄰k的數(shù)量增加時，此算法要更優(yōu)于樹結構的算法。

4.2 重建圖像質量比較

將本文改進的塊查找算法運用在圖像超分辨率放大上面，對高分辨率圖像進行模糊、加高斯白噪聲，并進行下采樣得到128×128像素的低分辨率圖像，圖像的質量相對較差。用本文方法放大4倍并和最近鄰插值、雙線性插值、雙立方法比較，實驗結果如表2所示。

表2 各方法放大結果比較

大量實驗結果表明，隨著σ1的增大圖像會更加模糊。若源圖像質量較差時σ1應取值較大值(如180)，但是和雙立方法的實驗結果比較時還是要明顯清晰很多;當源圖像較好時，σ1應取值較小值(如20)。實驗中取 λ1=0.5，λ2=0.05。由于低分辨率圖像質量較差且放大倍數(shù)較高，其他方法都顯示出了其本身固有的缺點，而本文方法要明顯好于其他方法。前文的3個方法都是利用Matlab的imresize函數(shù)來完成的。本文選擇2個指標:峰值信噪比(Peak Signal to Noise Ratio，PSNR)和結構相似性(Structural Similarity，SSIM)來衡量算法的好壞。

表2的結果是有參的質量評價，可以看出無論文獻［8］方法還是本文方法，和傳統(tǒng)的插值方法比較都有著很明顯的優(yōu)勢。另外本文方法從多幅圖像重建結果看，都要好于文獻［8］方法的結果。

為了進一步進行對比，本文和文獻［8］中一樣也采用Berkeley大學視覺組的彩色圖像進行實驗。這些圖片相對于前文選擇的20張灰度圖像，圖像質量好且清晰度高。下面將從無參的客觀評價和主觀評價2個方面對實驗結果進行對比。

選用文獻［15］的方法作為無參的客觀評價標準，此方法從模糊度以及鋸齒性等多個方面來衡量圖像的好壞。分值越低，圖像的質量越優(yōu)。結果和人視覺系統(tǒng)判斷效果較為吻合。先把RGB圖像轉換為 YCbCr值，再用本文方法放大4倍并和文獻［8］的放大結果進行比較，實驗結果如表3所示。圖3、圖4為重建效果，從視覺上可以看出本文方法明顯優(yōu)于其他方法，比雙立方法更加清晰，減少了邊緣模糊。通過對細節(jié)的放大可以看出，相比于文獻［8］方法鋸齒現(xiàn)象有所減少，圖像看起來更自然。特別是圖3中帽子和孩子臉部分、圖4中花瓣邊緣和蝴蝶翅膀邊緣，要明顯好于文獻［8］方法。圖像放大4倍后仍有很好的效果。

表3 無參圖像質量評價結果

圖3 重建效果1

圖4 重建效果2

5 結束語

本文利用多尺度圖像之間的塊冗余現(xiàn)象，提出了一種快速超分辨率重建的方法。已有的超分辨率方法多側重利用不同的信息(如高頻、低頻)來建立高低分辨率庫，而鮮有對查找到的相似塊進行修正以及對圖像塊進行更準確的加權的，并且速度較慢。本文依據(jù)這一思路對算法做了改進。實驗證明本文算法無論是重建速度還是重建圖像質量都有所提高。下一步工作是結合基于學習的超分辨率重建算法與傳統(tǒng)的基于重建的超分辨率算法作進一步研究。

［1］Tsai R Y，Huang T S.Multipleframe Image Restoration and Registration［C］//Proc.of Conference on Advances in Computer Vision and Image Processing.Greenwich，USA:JAI Press Inc.，1984:317-339.

［2］Stark H，Oskoui P.High-resolution Image Recovery from Image-plane Arrays，Using Convex Projections［J］.Journal of the Optical Society of America A，1989，6(11):1715-1726.

［3］Freeman W T，Jones T R，Pasztor E C.Example-based Super-resolution［J］.IEEE Computer Graphics and Applications，2002，22(2):56-65.

［4］Chang Hong，Yeung D Y，Xiong Yimin.Super-resolution Through Neighbor Embedding［C］//Proc.of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C.，USA:［s.n.］，2004:275-282.

［5］Irani M，Peleg S.Improving Resolution by Image Registration［J］.CVGIP:Graphical Models and Image Processing，1991，53(3):231-239.

［6］Baker S，Kanade T.Limits on Super-resolution and How to Break Them［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(9):1167-1183.

［7］薛翠紅，于 明，于 洋，等.基于MAP框架的金字塔人臉超分辨率算法［J］.計算機工程，2012，38(10):206-208.

［8］Glasner D，Bagon S，Irani M.Super-resolution from a Single Image［C］//Proc.of the 12th International Conference on Computer Vision.Kyoto，Japan:［s.n.］，2009:349-356.

［9］Barnes C，ShechtmanE，GoldmanD B，etal.The Generalized Patch Match Correspondence Algorithm［C］//Proc.of the 11th European Conference on Computer Vision.Heraklion，Greece:［s.n.］，2010:29-43.

［10］Arya S，Mount D M.Approximate Nearest Neighbor Queries in Fixed Dimensions［C］//Proc.of the 4th Annual ACMSIAM Symposium on Discrete Algorithms.Philadelphia，USA:［s.n.］，1993:271-280.

［11］Wei Liyi，Levoy M.Fast Texture Synthesis Using Tree Structured Vector Quantization［C］//Proc.of the 27th Annual Conference on Computer Graphics and Interactive Techniques.New Orleans，USA:ACM Press，2000:479-488.

［12］Hertzmann A，Jacobs C E，Oliver N，et al.Image Analogies［C］//Proc.of the 28th Annual Conference on Computer Graphics and Interactive Techniques.Los Angeles，California，USA:［s.n.］，2001:327-340.

［13］Kumar N，Zhang Li，Nayar S.What is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?［C］//Proc.of the 10th European Conference on Computer Vision.Berlin，Germany:［s.n.］，2008:364-378.

［14］姚 琦，沈 松，朱 飛.基于加權 POCS的圖像超分辨率重建［J］.計算機工程，2013，39(3):264-266，271.

［15］Mittal A，Soundararajan R，Bovik A.Making a“Completely Blind” Image Quality Analyzer［J］.IEEE Transactions on Signal Processing Letters，2013，20(3):209-212.