一種改進(jìn)的基于塊的圖像修復(fù)算法

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

（1.西北工業(yè)大學(xué) 電子信息學(xué)院，陜西 西安 710129；2.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710129）

圖像修復(fù)是根據(jù)圖像已知區(qū)域的像素信息來(lái)推斷缺失的未知區(qū)域信息，并且要求最終圖像的已知區(qū)域與修補(bǔ)區(qū)域過(guò)渡自然，從而達(dá)到人眼看不出修補(bǔ)的痕跡。圖像修復(fù)應(yīng)用相當(dāng)廣泛，包括珍貴的歷史文物、舊照片、目標(biāo)移除、圖像壓縮與編碼等。

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

1）算法中優(yōu)先項(xiàng)的計(jì)算采用了置信項(xiàng)與數(shù)據(jù)項(xiàng)乘積的形式。這樣，當(dāng)數(shù)據(jù)項(xiàng)為零時(shí)，即使置信項(xiàng)很高，由于優(yōu)先項(xiàng)為零也不能得到優(yōu)先修復(fù)。但是在紋理豐富的區(qū)域，數(shù)據(jù)項(xiàng)是不為零的，這就造成了紋理豐富的區(qū)域修復(fù)先于紋理信息較少的區(qū)域，出現(xiàn)紋理豐富區(qū)域修復(fù)過(guò)渡的現(xiàn)象。

2）算法中采用固定的樣本塊窗口大小，這樣有可能會(huì)導(dǎo)致在圖像的平坦區(qū)域產(chǎn)生塊狀效應(yīng)，在圖像紋理豐富的區(qū)域產(chǎn)生錯(cuò)誤衍生的現(xiàn)象。另外算法中只是利用先前計(jì)算出來(lái)的源圖像塊的置信度來(lái)更新填充未知像素的置信度，未考慮到樣本塊與匹配塊之間存在誤差，從而造成修復(fù)過(guò)程中的誤差累積，導(dǎo)致Criminisi算法的貪婪性。

本文針對(duì)以上Criminisi算法的缺陷進(jìn)行改進(jìn)，實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)算法取得了較好的效果。

1 算法的描述

1.1 Criminisi算法的原理

如圖1所示，整幅圖像為I，待修復(fù)區(qū)域?yàn)棣福磪^(qū)域?yàn)棣担?Ω為待修復(fù)區(qū)域的邊界。該算法的圖像修復(fù)過(guò)程分為如下3個(gè)步驟：

圖1 算法標(biāo)記圖Fig.1 Signature of criminisi algorithm

1）計(jì)算優(yōu)先級(jí)

定義待修復(fù)邊界處任意像素點(diǎn)p優(yōu)先級(jí)函數(shù)P（p）為：

式中C（p）為置信度項(xiàng)，用來(lái)度量以像素點(diǎn)p為中心的目標(biāo)塊 ψp內(nèi)已知信息的數(shù)目；D（p）為數(shù)據(jù)項(xiàng)。 C（p）和 D（p）表達(dá)式如下：

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

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

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

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

1.2 優(yōu)先權(quán)函數(shù)的改進(jìn)

本文運(yùn)用的優(yōu)先權(quán)計(jì)算公式為：

式中：α+ β=1，當(dāng) D（p）=0 且 C（p）<0 時(shí)，α=0，β=0；當(dāng)D（p）≠0 且 C（p）≠0 時(shí)，α=0.4，β=0.6；當(dāng) D（p）=0 且 C（p）>0.8 時(shí)，α=1，β=0。通過(guò)這就能保證當(dāng) D（p）為零時(shí)，只要 C（p）高，也能夠優(yōu)先修復(fù)；當(dāng) D（p）為零和 C（p）很低時(shí)，令 P（p）為零，表示該像素塊后修復(fù)；當(dāng) D（p）和 C（p）都不為零時(shí)，令β>α，使數(shù)據(jù)項(xiàng)占主導(dǎo)因素。實(shí)驗(yàn)表明，這種方法能夠避免紋理豐富區(qū)域修復(fù)過(guò)渡擴(kuò)展的現(xiàn)象以及解決Criminisi算法中修復(fù)方向嚴(yán)格按照線性結(jié)構(gòu)方向進(jìn)行出現(xiàn)斷層的問(wèn)題。

1.3 根據(jù)梯度自適應(yīng)選擇樣本模板以及置信度更新

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

自適應(yīng)樣本塊大小的方法是利用Criminisi算法中選擇的9x9的樣本塊中已知點(diǎn)的平均梯度值的大小來(lái)選擇不同尺寸的模板窗口。公式表達(dá)如下：

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

本文采取置信度的方法為：Ipi令為待修復(fù)塊ψq中已知點(diǎn)的梯度值，Iqi為最佳匹配塊ψq^對(duì)應(yīng)的已知點(diǎn)的梯度值，M為待修復(fù)樣本塊中已知點(diǎn)的個(gè)數(shù)，令復(fù)塊與對(duì)應(yīng)的最佳匹配塊之間的平均梯度差值，th值越小，說(shuō)明兩塊之間的紋理相差越小，復(fù)制過(guò)來(lái)點(diǎn)的置信度就越大。改進(jìn)的置信度更新方式如下：

1.4 改進(jìn)算法的步驟

結(jié)合改進(jìn)的優(yōu)先權(quán)方法、自適應(yīng)選擇模板的方法以及改進(jìn)的置信度更新方式，得到改進(jìn)后的算法步驟如下：

1）選擇一幅圖像，由用戶(hù)利用一種特定的顏色標(biāo)注出目標(biāo)區(qū)域，然后找出目標(biāo)區(qū)域邊緣?Ω，當(dāng)?Ω=φ時(shí)，算法結(jié)束，輸出修復(fù)圖像。

2）根據(jù)式（2）計(jì)算出數(shù)據(jù)項(xiàng)與置信度項(xiàng)的值，然后按照式（7）求出優(yōu)先權(quán)項(xiàng)，對(duì)優(yōu)先項(xiàng)從高到低進(jìn)行排序，確定最高優(yōu)先權(quán)的邊界點(diǎn)作為修復(fù)的目標(biāo)，然后以該點(diǎn)為中心計(jì)算其9x9領(lǐng)域中已知點(diǎn)的平均梯度值，根據(jù)不同的梯度值按照式（8）選擇樣本塊的大小；

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

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

5）根據(jù)式（9）更新置信度項(xiàng)；

6）重復(fù)（2）到（6），直到全部的目標(biāo)區(qū)域被修復(fù)。

2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境是在奔騰core 1.86 GHz，1GB內(nèi)存的PC機(jī)上，利用Matlab7.1軟件平臺(tái)實(shí)現(xiàn)了Criminisi算法與本文算法對(duì)兩幅彩色圖像分別從R、G、B三種通道進(jìn)行修復(fù)。

圖 2（a）是原圖，大小是 262x350 的彩色圖像，圖 2（b）是待修復(fù)圖，車(chē)以及人物部分是標(biāo)注的待修補(bǔ)區(qū)域，圖2（c）是Criminisi算法修復(fù)圖，所用時(shí)間為165.57 s，圖2（d）是本文算法修復(fù)圖，所用時(shí)間為208.42s。圖3（a）是原圖，大小是308x206的彩色圖像，圖3（b）是待修復(fù)圖，人物部分是標(biāo)注的待修補(bǔ)區(qū)域，圖 3（c）是 Criminisi算法修復(fù)圖，所用時(shí)間為 103.20 s，圖 3（d）是本文算法修復(fù)圖，所用時(shí)間為123.65 s。通過(guò)兩組實(shí)驗(yàn)對(duì)比，本文算法從視覺(jué)效果就可以看出明顯優(yōu)于Criminisi算法，尤其是在明顯結(jié)構(gòu)變化處的圖像修復(fù)。另外本文也從客觀角度采用峰值信噪比（PSNR）的方法將本文算法與Criminisi算法進(jìn)行了對(duì)比，如表1，PSNR的計(jì)算公式如公式（10）。

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

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

圖2 實(shí)驗(yàn)一結(jié)果對(duì)比圖Fig.2 Comparison chart of the first experiment

圖3 實(shí)驗(yàn)二結(jié)果對(duì)比圖Fig.3 Comparison chart of the second experiment

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

3 結(jié)束語(yǔ)

實(shí)驗(yàn)結(jié)果表明，本文算法的修復(fù)效果明顯優(yōu)于Criminisi算法，對(duì)具有明顯結(jié)構(gòu)特征的圖像修復(fù)更有優(yōu)勢(shì)，避免了Criminisi算法會(huì)造成圖像結(jié)構(gòu)性丟失以及錯(cuò)誤衍生等現(xiàn)象的發(fā)生。但是由于本文算法中需要計(jì)算目標(biāo)塊中已知點(diǎn)的平均梯度模值以及目標(biāo)塊與對(duì)應(yīng)匹配塊中已知點(diǎn)的平均梯度差值導(dǎo)致修復(fù)時(shí)間略高于Criminisi算法，以后會(huì)在修復(fù)時(shí)間上進(jìn)一步的研究。

[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]胡熹.基于樣本圖像的圖像修補(bǔ)技術(shù)研究[D].上海：上海交通大學(xué)電子信息工程學(xué)院，2013.

[5]范冠鵬，和紅杰，陳帆，等.基于局部特性的圖像修復(fù)算法[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]孟春芝，何凱，焦青蘭.自適應(yīng)樣本塊大小的圖像修復(fù)方法[J].中國(guó)圖像圖形學(xué)報(bào)，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.