基于旋轉及尺度空間拓展的圖像修復算法

何 凱，鄭 歡，張麗瑩

(天津大學電子信息工程學院，天津 300072)

數字圖像修復技術是計算機視覺領域的重要研究課題，其主要研究內容在于如何利用圖像中的已知信息對破損區(qū)域進行填充，最終保證修復圖像的效果自然合理．該技術在字幕、污點、劃痕去除、老照片修復、影視特技、文物保護等領域都具有重要的意義和研究價值．

數字圖像修復的經典算法是 Criminisi等[1]于2003年提出的基于樣本塊的修復算法，該算法利用置信度函數和結構性函數來確定修復的優(yōu)先權函數，可實現大區(qū)域破損紋理圖像的自動修復．

傳統(tǒng)基于樣本塊的修復算法在修復圖像結構時容易出現塊效應和誤匹配．針對這一問題，國內外學者提出了一些改進方法．Wexler等[2]提出利用迭代算法來優(yōu)化能量函數，通過下采樣形成多級金字塔圖像，分別對每層金字塔圖像進行塊搜索和填充，改善了整體修復效果．Bugeau等[3]提出將紋理合成、幾何偏微分方程以及鄰域像素一致性綜合為一個能量函數，通過最小化該能量函數完成修復過程，取得了較好的修復效果．謝伙生等[4]提出了一種基于樣本塊的優(yōu)化方法，在考慮置信度和數據項的同時，增加了是否接近原始邊界因素的影響，改善了修復效果. Kwok等[5]將圖像轉換到頻域進行處理，通過選擇少數頻域系數來評估匹配情況，并將梯度引入到填充破損區(qū)域的過程當中，為圖像匹配提供了新的思路．何凱等[6]在傳統(tǒng)圖像修復算法優(yōu)先權系數的基礎上，增加了方向性優(yōu)先權系數，為紋理合成時各點的傳播方向和進度提供索引，能夠有效克服傳統(tǒng)紋理合成方法沒有考慮方向性的缺點．

在結構優(yōu)化方面，Zhang等[7]提出將塊稀疏度優(yōu)先權和動態(tài)結構標簽裁剪綜合成一個全局優(yōu)化模型，保證了紋理和結構修復效果的正確性．李志丹等[8]根據塊結構稀疏度值來選擇不同大小的樣本塊及鄰域一致性約束，以自適應獲得稀疏表示的指導信息．還有一些學者提出利用結構曲線來改善結構修復效果．Sun等[9]提出利用人機交互方案來解決圖像結構的修復問題，通過人為干預，手動添加匹配塊的搜索范圍，提高了結構圖像修復質量和速度．Pan等[10]采用自然圖像局部自相似的假設，將顯著結構曲線由已知區(qū)域拓展到破損區(qū)域，能夠較好地修復破損區(qū)域內部的結構曲線．

除此之外，利用離散馬爾科夫隨機場(MRF)模型來改進修復效果也是當前的一個研究方向，Komodakis等[11]和 Pritch等[12]分別利用置信度傳播BP和圖像分割的方法來優(yōu)化 MRF模型，將塊和像素位置進行重新分配，以改善圖像修復效果．2012年，Sun等[13]使用圖像中樣本塊及其最優(yōu)匹配塊的位移，利用分布最密集的k個位移為修復圖像提供信息來源，并利用 MRF優(yōu)化完成修復過程，提高了結構圖像的修復效果．

傳統(tǒng)基于樣本塊的圖像修復及其改進方法存在一個缺陷，即只能在平移空間中進行搜索，當圖像中出現旋轉及尺度變換時，無法實現匹配塊的最優(yōu)選?。槍ι鲜鰡栴}，本文通過改進能量函數來實現搜索空間的旋轉和尺度空間拓展，并利用 LM(Levenberg-Marquadt)優(yōu)化算法[14]求解最優(yōu)變換系數，以實現旋轉和尺度變換時最優(yōu)匹配塊的自動搜索．

1 Patchmatch快速搜索算法

Barnes等[15]提出了一種快速塊匹配搜索算法Patchmatch，其最大特點是可以利用相鄰塊之間的相互關系來傳播鄰域信息．

1.1 隨機初始化

針對圖像 A的所有樣本塊，定義其在圖像 B中的匹配矢量函數為

即以圖 A中某樣本塊的中心點像素坐標a作為該樣本塊的塊坐標，該樣本塊在圖像 B中的匹配塊坐標為 b．

初始化過程對A中所有塊在B中隨機分配一個匹配塊，然后進行傳播和隨機搜索，通過迭代優(yōu)化來更新匹配塊．

1.2 傳 播

在奇數次迭代時，利用已知的 m ( x - 1,y)和m ( x,y -1)矢量來更新 m ( x,y)，以向右側和下方傳播有效信息；設 D (v)表示A中位于(x,y)的塊和B中位于(x,y)+v的塊的最小均方誤差，則 m ( x,y)更新為

偶數次迭代時可向左側和上方傳播信息，此時選用 ( 1,)x y+m 和 (, 1)xy+m 作為候選匹配矢量．

1.3 隨機搜索

假定(',')xy是A中塊坐標為(,)xy的樣本塊在B中當前分配的塊坐標，定義搜索半徑為

式中：w為樣本塊的最大搜索半徑；{α|0 ＜ α＜1}為搜索半徑轉換比率；1 ＜ Ri+1＜ w ．當 i＝0，1，2，…時，在以點(x',y ') 為中心、Ri+1為半徑的范圍內隨機選取候選塊對當前匹配塊進行優(yōu)化更新．

2 本文算法

設圖像破損區(qū)域為 T，信息來源區(qū)域為 S，所有和破損區(qū)域相交的樣本塊稱為目標塊，其余稱為信息塊；則圖像修復的目的就是從源區(qū)域S中尋找最優(yōu)區(qū)域塊，并將其填充到破損區(qū)域 T當中．本文采用Patchmatch搜索算法對所有目標塊進行最優(yōu)匹配塊的全局搜索．傳統(tǒng)能量函數[2]的表達式為

其中

式中：tn、sxn分別表示以點n為中心的目標塊和以點xn為中心的信息塊；ip為塊內部像素的相對索引；D 為兩個塊像素值的最小均方誤差．

2.1 能量函數的改進

傳統(tǒng)能量函數只能針對平移空間進行搜索，當圖像包含其他變換信息時無法實現樣本塊的準確搜索．為此，本文將傳統(tǒng)能量函數加以改進，增加了旋轉和尺度變換參數，以實現變換空間的拓展；同時加入了梯度項以減小匹配誤差．拓展后的能量函數可表示為

式中：第 1項為目標塊 tn和變換后的信息塊 f (sxn)在R、G、B三維像素值的最小均方誤差；?為水平和垂直方向的梯度；?tn為目標塊tn的梯度值；f(?sxn)為對信息塊 sxn的梯度值進行變換；λ為加權系數，表示梯度的影響權重；f為變換函數； f(sxn)為以 xn為中心的信息塊 sxn進行旋轉和尺度變換之后彩色通道的像素值．將 f (sxn)定義為

式中 fxn(ip)為對點 xn為中心的信息塊進行變換后在圖像中的絕對索引． fxn(ip)的定義為

式中：Rθn為進行θn角度旋轉后的塊內相對索引；αn為尺度變換系數(將樣本塊的中心點作為旋轉和尺度變換的中心點). 式(7)中 f(? sxn)的計算方法與f(sxn)類似．

針對尺度變換，采用正方形搜索塊，對旋轉變換采用正方形內切圓作為搜索塊，順時針旋轉θn后的塊內相對索引 Rθnip依照式(10)、(11)確定，即

式中0xi、0yi 和xi、yi分別為旋轉前后的二維相對索引．

2.2 利用LM算法獲取最優(yōu)化模型參數

以確定旋轉變換的最優(yōu)參數θ為例，設隨機初始化步奏分配的當前最優(yōu)匹配塊是nxs，?()fθ=t為nxs旋轉θ角度后對目標塊nt的估計．給定初始角度0θ和目標塊nt，誤差函數定義為

本文利用 LM 迭代算法尋找使得平方誤差(ε( θ ) )Tε ( θ )達到最小時的最優(yōu)旋轉角度θ．每次迭代都尋找新的δθ，使其滿足

式中：J是雅克比矩陣 ? f（θ） / ?θ；μ＞0；I為單位矩陣．若由式(13)獲得的δθ滿足關系

則更新 θ =θ+δθ，同時減小μ；否則增加μ并重新求解式(13)，直到求得的δθ滿足式(14)，更新θ= θ +δθ.

依照上述法則不斷求解式(13)，設初始點為θ0，通過迭代產生一系列 θ1、θ2、…，直到收斂到局部最優(yōu)解．

調整μ的目的在于確保式(14)成立．當算法滿足以下條件之一時停止迭代，并取當前θ為最優(yōu)旋轉參數．

(1)式(13)右邊項 JTε低于某個閾值ε1；

(2)θ的相對變化量δθ低于某個閾值ε2；

(3)誤差項 (ε (θ) )Tε (θ)低于某閾值ε3；

(4)迭代次數達到最大值 kmax．

具體做法如下．

(1)角度方面．將角度范圍均勻分成 8個區(qū)間，設當前分配的最優(yōu)匹配塊的角度參數為θ，則以角度θ為起點，在360°范圍內依次增加(或減小)45°，作為LM迭代的起始角度，在以每個迭代起始角度為中心的±22.5°范圍內，通過迭代計算各自的最優(yōu)參數．

(2) 尺度方面．設搜索塊大小為ω，當前分配的最優(yōu)匹配塊的尺度參數為 {α0|1 ≤ α0≤2}，將尺度范圍[ω ,2ω]均勻分成8等份，以尺度α0ω為起點，依次增加(或減小)ω8，作為迭代尺度參數的起始值，在以每個迭代起始尺度參數為中心的±ω 16的范圍內進行迭代，獲得最優(yōu)尺度參數．

最后，利用具有最小平方誤差 (ε ( θ ) )Tε( θ )的最優(yōu)系數對當前最優(yōu)匹配塊進行變換，以去除旋轉和尺度變換的影響．

2.3 算法流程

首先對破損圖像進行下采樣，構造高斯金字塔圖像，從金字塔頂層開始，逐層對圖像迭代進行塊搜索和信息填充[2]．算法流程如圖1所示，其中，k表示當前金字塔層數，2n表示當前層已迭代次數，1n和N分別表示在第k層、第2n次迭代時，空間拓展及LM優(yōu)化塊搜索過程的已迭代次數和所需的總迭代次數．

圖1 本文算法流程Fig.1 Flow chart of the algorithm proposed in this paper

3 實驗結果及分析

為了驗證本文方法的有效性，選取了4幅具有尺度和旋轉變化的圖像進行實驗仿真，如圖2～圖5所示．其中圖(a)代表原始圖像，圖中的小線框內部代表破損區(qū)域．

本文實驗均采用5級高斯金字塔，由粗到細進行迭代，以在保證準確度的前提下降低計算量．其中第5級進行15次迭代，以后每級迭代次數遞減3次，每次迭代的總迭代次數 N設為 100；除此之外，能量函數的梯度項設置至關重要，如果不設置梯度項或者其權重系數過小，會造成圖像在結構變化處出現模糊和平滑，丟失結構信息；反之，如果權重系數過大，則會導致紋理信息的誤匹配，根據實驗仿真結果，本文能量函數的梯度權重設為λ＝0.2，樣本塊大小選為11，LM參數選取為 ε1=ε2=ε3=1×10-4，kmax＝10，隨機搜索過程取w為圖像的最大維度，α＝0.5．

從圖 2和圖 3中可以看出，破損區(qū)域 T內的圖像信息與源區(qū)域 S中相應圖像具有明顯的尺度變換特征，由于傳統(tǒng)全局優(yōu)化算法不具有尺度變換的功能，無法準確找到最優(yōu)樣本塊，修復效果較差；而本文方法通過尺度拓展，并利用LM優(yōu)化算法確定尺度最優(yōu)化系數，可以顯著提高匹配的準確度，有效地解決了這一問題，取得了理想的修復效果．

圖2 五角星尺度圖像修復效果Fig.2 Result of five-pointed star scale image

圖3 熱氣球尺度圖像修復效果Fig.3 Result of fire balloon scale image

圖4 中破損區(qū)域T與源區(qū)域S之間存在明顯的旋轉變換關系．從圖 4的修復結果對比中可以明顯看出，傳統(tǒng)方法在解決這一類問題時效果明顯不夠理想；而本文方法不僅可以有效地修復圓盤的弧形邊界，而且在相對復雜的花紋圖盤方面，修復效果也更為準確．同理，對于圖 5齒輪中的破損部分，由于本文方法有效地利用了旋轉信息，將最優(yōu)旋轉角度作用于匹配塊，從而有效地降低了匹配誤差，取得了理想的修復效果；而傳統(tǒng) Criminisi樣本塊修復算法和space-time修復算法由于缺乏相應的旋轉變換能力，修復后圖像具有明顯的人工修復痕跡．

圖4 圓盤旋轉圖像修復效果Fig.4 Result of disk rotation image

圖5 齒輪旋轉圖像修復效果Fig.5 Result of gear rotation image

4 結 語

本文提出了一種基于旋轉及尺度變換的圖像修復算法，通過改寫能量函數并利用LM優(yōu)化方法求得最優(yōu)變換參數，當圖像存在旋轉及尺度空間變換時，能夠明顯提高塊匹配的準確度，取得了比較理想的修復效果．

［1］ Criminisi A，Perez P，Toyama K. Object removal by exemplar-based inpainting [C]// Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Wisconsin，USA，2003：721-728.

［2］ Wexler Y，Shechtman E，Irani M. Space-time completion of video[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(3)：463-476.

［3］ Bugeau A，Bertalmío M，Caselles V，et al. A comprehensive framework for image inpainting [J]. IEEE Transactions on Image Processing，2010，19(10)：2634-2645.

［4］ 謝伙生，潘姣君. 基于紋理合成的圖像修復優(yōu)化方法[J]. 福州大學學報：自然科學版，2013，41(3)：305-310.Xie Huosheng，Pan Jiaojun. Optimal method of image inpainting based on texture synthesis [J]. Journal of Fuzhou University：Natural Science Edition，2013，41(3)：305-310(in Chinese).

［5］ Kwok T H，Sheung H，Wang C C L. Fast query for exemplar-based image completion[J]. IEEE Transactions on Image Processing，2010，19(12)：3106-3115.

［6］ 何 凱，焦青蘭，孟春芝，等. 非均勻紋理圖像大區(qū)域修復算法[J]. 天津大學學報，2012，45(4)：314-318.He Kai，Jiao Qinglan，Meng Chunzhi，et al. Nonregular texture image completion algorithm in large region[J]. Journal of Tianjin University，2012，45(4)：314-318(in Chinese).

［7］ Zhang X，Liu B. Image completion with patch sparsitybased global optimization[C]// IEEE 2011 3rd International Conference on Computer Research and Development(ICCRD). Shanghai，China，2011：62-66.

［8］ 李志丹，和紅杰，尹忠科，等. 基于塊結構稀疏度的自適應圖像修復算法[J]. 電子學報，2013，41(3)：549-554.Li Zhidan，He Hongjie，Yin Zhongke，et al. Adaptive image inpainting algorithm based on patch structure sparsity[J]. Acta Electronica Sinica，2013，41(3)：549-554(in Chinese).

［9］ Sun J，Yuan L，Jia J，et al. Image completion with structure propagation [J]. ACM Transactions on Graphics，2005，24(3)：861-868.

［10］ Pan P，Zheng X，Xu Q，et al. Image completion with automatic structure propagation [C] // IEEE 2012 8th International Conference on Computational Intelligence and Security (CIS). Guangzhou，China，2012：305-309.

［11］ Komodakis N，Tziritas G. Image completion using efficient belief propagation via priority scheduling and dynamic pruning [J]. IEEE Transactions on Image Processing，2007，16(11)：2649-2661.

［12］ Pritch Y，Kav-Venaki E，Peleg S. Shift-map image editing [C]// IEEE 2009 12th International Conference on Computer Vision. Kyoto，Japan，2009：151-158.

［13］ He K，Sun J. Statistics of patch offsets for image completion [C]// Computer Vision-ECCV 2012. Springer Berlin Heidelberg，2012：16-29.

［14］ Madsen K，Nielsen H B，Tingleff O. Methods for Non-Linear Least Squares Problems [M]. Copenhagen，Denmark：Technical University of Denmark，2004.

［15］ Barnes C，Shechtman E，Finkelstein A，et al. Patch-Match：A randomized correspondence algorithm for structural image editing [J]. ACM Transactions on Graphics，2009，28(3)：24-33.