一種改進的基于塊的圖像修復算法

趙子巖 ， 齊 敏 ， 齊 榕 ， 李 珂

（1.西北工業大學 電子信息學院，陜西 西安 710129；2.西北工業大學 自動化學院，陜西 西安 710129）

圖像修復是根據圖像已知區域的像素信息來推斷缺失的未知區域信息，并且要求最終圖像的已知區域與修補區域過渡自然，從而達到人眼看不出修補的痕跡。圖像修復應用相當廣泛，包括珍貴的歷史文物、舊照片、目標移除、圖像壓縮與編碼等。

目前圖像修復的算法主要分為兩大類：基于像素點的圖像修復算法與基于塊的圖像修復算法。前者主要是針對小范圍破損區域的圖像進行修復，這類方法包括基于偏微分方程的圖像修復的三種模型，即 BSCB模型[1]、整體變分（TV）模型[2]和基于曲率驅動擴散的修復模型 （CDD）模型[3]以及基于插值及鄰域模板的方法。基于偏微分方程修復的方法主要是利用物理學上的熱擴散原理，通過建立圖像的偏微分方程，然后解偏微分方程，從而實現對圖像的修復，而基于插值與鄰域模板的方法是套用某種類型，而不用循環迭代，得到待修復點的值。比如鄰域點的值套用范本或者直接帶入插值公式，然后通過計算得到待修復區域的像素值。后者主要是針對大范圍破損區域的圖像進行修復，這類方法包括基于樣本塊的紋理合成圖像修復方法、變換域（傅里葉變換或小波變換）圖像修復方法以及基于分形理論以及基于稀疏性的圖像修復方法等。在這類方法中，以圖像塊為基本操作單位[4]，根據未知區域邊界處的信息，通過從圖像的已知區域中搜索相似匹配塊，并通過相關計算找到最佳匹配塊，最后將最佳匹配塊復制到未知區域塊中，從而逐步填充缺損區域，完成圖像修復。Criminisi等人在2003年提出了基于樣本塊的圖像修復算法，該算法利用局部邊界等照度線方向和單位法線方向定義塊的填充次序，得到優先填充的樣本塊后，在圖像已知區域尋找最佳匹配塊，并通過待修復匹配塊填充待修復樣本塊。此方法的優點是同時兼顧了圖像的紋理信息以及結構信息，是至今研究大范圍破損區域圖像修復的主流，然而Criminisi算法也存在一些缺陷:

1）算法中優先項的計算采用了置信項與數據項乘積的形式。這樣，當數據項為零時，即使置信項很高，由于優先項為零也不能得到優先修復。但是在紋理豐富的區域，數據項是不為零的，這就造成了紋理豐富的區域修復先于紋理信息較少的區域，出現紋理豐富區域修復過渡的現象。

2）算法中采用固定的樣本塊窗口大小，這樣有可能會導致在圖像的平坦區域產生塊狀效應，在圖像紋理豐富的區域產生錯誤衍生的現象。另外算法中只是利用先前計算出來的源圖像塊的置信度來更新填充未知像素的置信度，未考慮到樣本塊與匹配塊之間存在誤差，從而造成修復過程中的誤差累積，導致Criminisi算法的貪婪性。

本文針對以上Criminisi算法的缺陷進行改進，實驗結果表明，本文改進算法取得了較好的效果。

1 算法的描述

1.1 Criminisi算法的原理

如圖1所示，整幅圖像為I，待修復區域為Ω，源區域為Φ，?Ω為待修復區域的邊界。該算法的圖像修復過程分為如下3個步驟：

圖1 算法標記圖Fig.1 Signature of criminisi algorithm

1）計算優先級

定義待修復邊界處任意像素點p優先級函數P（p）為：

式中C（p）為置信度項，用來度量以像素點p為中心的目標塊 ψp內已知信息的數目；D（p）為數據項。 C（p）和 D（p）表達式如下：

式中|ψp|表示ψp的面積，α是歸一化的系數（對于8位的灰度圖像，一般取值為 255），Δ的大小與梯度相等，方向垂直于梯度，即等照度線方向，為待修復區域邊界?Ω的單位法向量。初始化時圖像中的各像素點的置信度值為：

其中d（ψp^，ψq）定義為兩個塊中已知像素的差的平方和，搜索整幅圖像的已知信息后，找到最小的d（ψp^，ψq）即為最佳的匹配塊ψq^。其計算公式為

3）置信度 C（p）的更新

重復（1）、（2）、（3）直至修復邊緣為零。

1.2 優先權函數的改進

本文運用的優先權計算公式為：

式中：α+ β=1，當 D（p）=0 且 C（p）<0 時，α=0，β=0；當D（p）≠0 且 C（p）≠0 時，α=0.4，β=0.6；當 D（p）=0 且 C（p）>0.8 時，α=1，β=0。通過這就能保證當 D（p）為零時，只要 C（p）高，也能夠優先修復；當 D（p）為零和 C（p）很低時，令 P（p）為零，表示該像素塊后修復；當 D（p）和 C（p）都不為零時，令β>α，使數據項占主導因素。實驗表明，這種方法能夠避免紋理豐富區域修復過渡擴展的現象以及解決Criminisi算法中修復方向嚴格按照線性結構方向進行出現斷層的問題。

1.3 根據梯度自適應選擇樣本模板以及置信度更新

由于Criminisi算法中采用固定的樣本塊，可能會導致在圖像的平坦區域產生塊狀效應，在圖像紋理豐富的區域產生錯誤衍生的現象。因此，圖像修復過程應該根據圖像的局部特征自適應的選擇樣本塊模板大小。根據圖像梯度的變化能夠反映圖像頻率的變化，本文采用根據梯度值自適應選擇樣本塊大小，在紋理豐富的區域采用較小的樣本塊；在平坦或者平滑區域采用較大的樣本塊。另外當待修復塊被匹配塊填充之后，需要對生成塊的置信度進行更新，在Criminisi算法中直接利用源圖像塊的置信度來更新填充未知點的置信度，但是未考慮到待修復塊與匹配塊之間存在一定的誤差，這樣進行會使誤差不斷地累積。對這些問題，本文采用的自適應樣本塊大小以及置信度更新方法分別如下：

自適應樣本塊大小的方法是利用Criminisi算法中選擇的9x9的樣本塊中已知點的平均梯度值的大小來選擇不同尺寸的模板窗口。公式表達如下：

式中，|ΔIP|為樣本塊9x9中已知點的平均梯度模值，size（p）為最終的待修復樣本塊模板半徑的大小。

本文采取置信度的方法為：Ipi令為待修復塊ψq中已知點的梯度值，Iqi為最佳匹配塊ψq^對應的已知點的梯度值，M為待修復樣本塊中已知點的個數，令復塊與對應的最佳匹配塊之間的平均梯度差值，th值越小，說明兩塊之間的紋理相差越小，復制過來點的置信度就越大。改進的置信度更新方式如下：

1.4 改進算法的步驟

結合改進的優先權方法、自適應選擇模板的方法以及改進的置信度更新方式，得到改進后的算法步驟如下：

1）選擇一幅圖像，由用戶利用一種特定的顏色標注出目標區域，然后找出目標區域邊緣?Ω，當?Ω=φ時，算法結束，輸出修復圖像。

2）根據式（2）計算出數據項與置信度項的值，然后按照式（7）求出優先權項，對優先項從高到低進行排序，確定最高優先權的邊界點作為修復的目標，然后以該點為中心計算其9x9領域中已知點的平均梯度值，根據不同的梯度值按照式（8）選擇樣本塊的大小；

3）確定樣本塊大小之后根據式（4）在圖像的已知區域選擇最佳匹配塊ψq^；

4）將最佳匹配塊ψq^的圖像信息復制到待修復樣本塊ψp^中；

5）根據式（9）更新置信度項；

6）重復（2）到（6），直到全部的目標區域被修復。

2 實驗結果與分析

實驗環境是在奔騰core 1.86 GHz，1GB內存的PC機上，利用Matlab7.1軟件平臺實現了Criminisi算法與本文算法對兩幅彩色圖像分別從R、G、B三種通道進行修復。

圖 2（a）是原圖，大小是 262x350 的彩色圖像，圖 2（b）是待修復圖，車以及人物部分是標注的待修補區域，圖2（c）是Criminisi算法修復圖，所用時間為165.57 s，圖2（d）是本文算法修復圖，所用時間為208.42s。圖3（a）是原圖，大小是308x206的彩色圖像，圖3（b）是待修復圖，人物部分是標注的待修補區域，圖 3（c）是 Criminisi算法修復圖，所用時間為 103.20 s，圖 3（d）是本文算法修復圖，所用時間為123.65 s。通過兩組實驗對比，本文算法從視覺效果就可以看出明顯優于Criminisi算法，尤其是在明顯結構變化處的圖像修復。另外本文也從客觀角度采用峰值信噪比（PSNR）的方法將本文算法與Criminisi算法進行了對比，如表1，PSNR的計算公式如公式（10）。

式中 f（i，j）為原灰度圖像，修復后的圖像為 f^（i，j），M、N分別為圖像的寬和高，

PSNR值越大說明修復圖像與參考圖像越相似，修復效率越高，算法性能越好。

圖2 實驗一結果對比圖Fig.2 Comparison chart of the first experiment

圖3 實驗二結果對比圖Fig.3 Comparison chart of the second experiment

表1 兩種算法的PSNR對比表Tab.1 PSNR comparison table of two algorithms

3 結束語

實驗結果表明，本文算法的修復效果明顯優于Criminisi算法，對具有明顯結構特征的圖像修復更有優勢，避免了Criminisi算法會造成圖像結構性丟失以及錯誤衍生等現象的發生。但是由于本文算法中需要計算目標塊中已知點的平均梯度模值以及目標塊與對應匹配塊中已知點的平均梯度差值導致修復時間略高于Criminisi算法，以后會在修復時間上進一步的研究。

[1]Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting[C]//Proceedings of SIGGRA PH， ACM Press，2000:417-424.

[2]Chan T，Shen J.Mathematical models for local non-texture inpaintings[J].SIAM Journal on Applied Mathematics，2001，62（3）:1019-1043.

[3]Chan T，Shen J.Non-texture inpainting by curvature-driven diffusions （CDD）[J].Journal of Visual Communication and Image Representation，2001，12（4）:436-449.

[4]胡熹.基于樣本圖像的圖像修補技術研究[D].上海：上海交通大學電子信息工程學院，2013.

[5]范冠鵬，和紅杰，陳帆，等.基于局部特性的圖像修復算法[J].光電子激光，2012，23（12）:2411-2416.FAN Guan-peng，HE Hong-jie，CHEN Fan，et al.An image inpainting algorithm based on local properties[J].Journal of Optoelectronics and Laser，2012，23（12）:2411-2416.

[6]孟春芝，何凱，焦青蘭.自適應樣本塊大小的圖像修復方法[J].中國圖像圖形學報，2012，17（3）:338-341.MENG Chun-zhi，HE Kai，JIAO Qing-lan.Image completion method with adaptive patch size[J].Journal of Image and Grapphics，2012，17（3）:338-341.