基于分形的圖像修復算法

摘要：基于紋理合成的圖像修復方法通過在圖像中搜索合適的背景塊填充修復區域，但在搜索過程中可能由于缺乏合適的匹配塊造成誤匹配，影響修復效果。提出一種基于分形思想的搜索方法，在搜索匹配塊時，不僅僅將候選塊與邊界塊比較，而且將候選塊進行仿射變換后的結果與邊界塊進行比較。為提高搜索速度，在搜索前對圖像進行分割，以減小解空間。實驗表明該算法在視覺效果和速度方面達到了良好的平衡。

關鍵詞：分形； 圖像修復； 搜索

中圖分類號：TP391 文獻標識碼：A文章編號：2095-2163（2013）02-0068-03

0引言

圖像修復是圖像處理中的一項實用技術，可將圖像中某些缺失區域依據一定算法進行填補，以收取良好的視覺效果。圖像修復技術主要用于歷史圖片破損修復，圖像中的物體或文字移除等。

圖像修復的主流算法有兩大類。第一類基于偏微分方程（PDE）[1]，主要思想是將圖像建模為分片光滑函數，通過邊界區域向缺失區域內部擴散，用邊界區域的梯度控制擴散參數，完成圖像修復。這類方法對于修復小范圍光滑圖像區域效果良好，但在修復紋理區域時，則難以保證紋理的一致性，同時也容易產生過度平滑，影響視覺效果。第二類算法基于紋理合成[2]（Texture Synthesis），主要思想是在圖像中尋找與邊界內容相似的圖像塊，填充到缺失區域中。此類算法應用更為廣泛，但該算法在搜索時對相似性的界定還不夠全面，一方面對圖像內容比較能力仍顯不足，難以找到最佳匹配的圖像塊，另一方面容易發生誤匹配，造成修復錯誤。

本文算法基于紋理合成的實現原理，引入了分形思想對其進行改進。該算法首先對圖像進行分割，確定不同位置的搜索區域。在搜索時，將候選塊的多個仿射變換結果與邊界塊進行比較，尋找最優匹配的結果用于填充。這一算法減少了誤匹配的概率，提高了修復的視覺效果，同時由于控制了搜索區域，增大了填充尺度，也保持了較低的運算量。

1紋理合成算法簡介

圖像修復中，紋理合成算法的基本實現主要分為四步，分別是：修復區域標記、優先度計算、塊搜索和填充。

首先，需要手動標注原始圖像待修補區域，標注后的圖形區域如圖1所示。

由圖1可知，Y表示原始圖像區域，X表示待修補區域，δΩ為兩個區域的邊界線。

標注修復區域后，對該區域所有邊界點計算優先度，優先度最高的那一點將作為參考塊的中心。文獻[2]中，優先度P（p）計算公式為：

確定優先修復的位置后，在整個圖像中搜索與參考塊最為接近的圖像塊，搜索過程中匹配度的評價使用最小均方誤差準則（Sum of Squared Differences，SSD）。搜索到最高匹配度的圖像塊后將其復制到待修復位置。

將上述步驟運行一次后，即更新修復區域邊緣點的優先度，而后重復這一過程，直到圖像修復結束。第2期甘羽，等：基于分形的圖像修復算法智能計算機與應用第3卷

2算法描述

21分形理論簡介

分形的概念可表達為一種由多個與整體有某種相似性的局部堆疊累加而構成的形體。分形可以使用迭代函數系統（Iterated Function System，IFS）生成，而由拼貼定理[3]可知，任何圖像都可以表示為一個IFS。

分形的思想已經應用于圖像壓縮中[4]，分形圖像壓縮編碼的過程是依據拼貼定理，通過給定的圖像尋找一組壓縮映射，使其組成的迭代函數系統的吸引子逼近給定圖像，并記錄得到相應參數。解碼過程則由對應參數確定迭代函數系統，再根據迭代函數系統定理反復迭代生成圖像。

分形圖像壓縮的基本步驟為：

（1）將待壓縮圖像進行K×K分塊，記為Ri。

（2）將圖像進行重疊的L×L分塊，記為Di.通常L=2K。

（3）根據最小均方誤差準則，在Di中搜索最佳的分割塊和合適的壓縮映射變換ωi，滿足Ri=ωi（Di），即對每個像素點：

上述過程表示Di經過一組仿射變換和亮度調整后，收斂于Ri。

由以上論述可以推知，圖像內部存在的自相似性和仿射變換是分形圖像處理的核心。本文也即借鑒分形思想，利用仿射變換，提高圖像修復算法的性能。

22算法步驟

算法的實現過程主要分為以下幾個步驟：

（1）手動標注原始圖像待修補區域。

（2）對圖像進行分割，并標注缺失區域對應的背景區域。

（a） 原始圖像

（a） Test image

（b） Criminisi算法修復結果

（b） Inpainting result by Criminisi's method

（c） 本文算法修復結果

（c） Inpainting result by proposed method

（3）對原始圖像進行仿射變換，生成仿射變換集。仿射變換參數為縮放50%、80%、120%、150%，旋轉30°～180°，間隔30°。

（4）采用第1節介紹的紋理合成算法計算，如圖1中，δΩ邊界上所有點的修補優先度。

（5）在仿射變換集中搜索候選解。首先，對放射變換集中的圖像進行不重疊分塊，計算所有子塊的平均灰度。然后，在與待修復區域對應的圖像局部空間中找出接近于待修復塊平均灰度的塊作為候選塊。接下來，在兩倍于侯選塊的范圍內展開像素級搜索，并基于最小均方誤差準則得到用于修復的圖像塊。

（6）重新計算下次修補的優先度。重復第（5）步，直到圖像修復結束。

3實驗結果與討論

算法采用VC 2010實現，在Thinkpad T420上運行。本文選取了USC-SIPI Miscellaneous 圖像庫[5]中的20幅圖像，并從網絡上節選了20幅圖像作為測試樣本，圖像類別涉及人物、風景、遙感圖像等廣泛門類在內。在將圖像中物體刪除后，利用本文算法與Criminisi原始算法分別進行修復。原始算法典型結果如圖2（b）所示，本文算法結果如圖2（c）所示。由圖中比較得出，本文算法具有更好視覺效果。

4結束語

本文提出了一種基于分析的圖像修復算法，與傳統基于紋理合成的圖像修復算法相比，取得了更好的視覺效果，同時也實現了較高的效率。但算法為減小搜索空間，還需要一定的手工標注，下一步需對算法進行優化，增加自動分割與區域標注功能以提高算法的靈活性。

參考文獻：

[1] CHAN T， SHEN J. Mathematical models for local non-texture inpainting [J]. SIAM J. Appl. Math， 2001， 62（3）： 1019-1043.

[2]CRIMINISI A， PEREZ P， TOYAMA K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE Transactions on Image Processing， 2004， 13（9）： 1200-1212.

[3] JACQUIN A E. Image coding based on a fractal theory of iterated contractive image transformations[J]. IEEE Transactions on Image Processing， 1992， 1（1）：18-30

[4] DAN C P ， DIMCA A， YAN H. A nonlinear model for fractal image coding[J]. IEEE Transactions on Image Processing， 1997， 6（3）：373-38.

[5] USC Signal and Image Processing Institute. USC–SIPI Image Database. http：//sipi.usc.edu/database.