江 平， 張 錦

(合肥工業(yè)大學數(shù)學學院，安徽 合肥 230009)

一種結合CDD模型和Criminisi算法的圖像修復算法

江 平， 張 錦

(合肥工業(yè)大學數(shù)學學院，安徽 合肥 230009)

針對既含有大塊缺失信息又含有劃痕的圖像，結合CDD模型和Criminisi算法的優(yōu)點，提出一種新的修復算法。算法先采用可以強化細節(jié)的自適應直方圖均衡化操作來擴大圖像的動態(tài)范圍，后利用形態(tài)學算子分離出待修復圖像中的劃痕區(qū)域與大塊區(qū)域,接著用CDD模型對劃痕進行修復，再用改進優(yōu)先級的 Criminisi算法進行后續(xù)修復，最后把修復后的圖像對應于缺失區(qū)域的像素填補到待修復圖像的區(qū)域中。實驗結果表明，改進后的算法克服了現(xiàn)有算法可能存在的偏差延續(xù)問題，使圖像修復的結果更加符合人們的視覺效果。

CDD模型；Criminisi算法；圖像修復；自適應直方圖均衡化；形態(tài)學算子

圖像修復技術是近年來計算機圖形學和計算機視覺中的一個倍受關注的研究熱點，所謂圖像修復[1]是指針對圖像中遺失或缺損的部分，利用未丟失或未破損的圖像信息，按一定的方法自動填補的過程，其目的是使觀察者無法察覺到圖像曾經(jīng)缺損或已被修復。圖像修復技術在文物的保護、多余物的剔除、影視特技的制作、圖像壓縮等方面得到廣泛的應用。

2000年，Bertalmio等[2]首先提出了一個基于三階偏微分的 BSCB修復模型，他開創(chuàng)了基于偏微分方程修復的先河，其基本思想是利用待修復區(qū)域的邊緣信息，將待修復區(qū)域邊界的外部信息沿輪廓擴散到中間待修補區(qū)域的像素上；2002年，Chan和Shen[3]在全變分(total variation, TV)去噪模型[4]的啟發(fā)下提出了基于 TV模型的圖像修復方法，同時說明了TV模型不滿足人類視覺中的“連續(xù)性”準則的缺點，進一步提出了曲率驅動擴散(curvature driven diffusion, CDD)[5]修復模型，讓圖像中不自然的大曲率迅速擴散，能以較低的計算復雜度實現(xiàn)有效的修復。此類修復方法對于小面積的圖像缺失(例如劃痕)有顯著的效果，但對破損區(qū)域較大的圖像修復效果不太理想。

基于樣本塊紋理合成方法能夠較好地處理大范圍缺失圖像，其中較為經(jīng)典的修復算法是Criminisi等[6]提出的Criminisi算法：將待修補區(qū)域分塊修復，按照優(yōu)先級公式計算出修補順序，在圖片中尋找與待修復區(qū)域塊最相近的塊將其填補；此后，文獻[7]中描述了該算法，并通過更多的實例說明該算法的有效性。盡管如此，Criminisi算法在處理圖像時，對較強的結構信息持續(xù)優(yōu)先處理很容易造成偏差延續(xù)，導致修復效果不理想。文獻[8]提出了改進優(yōu)先級的方法解決偏差問題，取得了一定的成效，具有較好的視覺效果。

目前的圖像修復算法主要都是針對大塊信息缺失(文獻[8-11])或小區(qū)域破損(文獻[12-14])的圖像，但是對既含有劃痕又含有大塊缺失信息的圖像卻很少涉及，如果分別用CDD算法和Criminisi算法修復此類圖像時，都會產(chǎn)生一些不好的視覺效果：CDD算法修復大塊區(qū)域會產(chǎn)生模糊現(xiàn)象，并且會有一些修復不到的孤立點；Criminisi算法修復會優(yōu)先處理劃痕，再修復大塊區(qū)域時會產(chǎn)生錯誤信息的累積。本文分析了這些算法，找到造成修復效果不佳的原因，在此基礎上，提出一種將強化細節(jié)的自適應直方圖均衡化、CDD模型、改進的Criminisi算法及形態(tài)學濾波結合起來的修復方法。

1 CDD模型描述

CDD模型是建立在TV模型的基礎上，而TV模型[3]是在約束條件下求泛函極值的問題：

如圖1所示，這里Ω為待修復區(qū)域，Φ為待修復區(qū)域周圍完好相鄰的區(qū)域，I=Φ∪Ω為整幅圖像，u為原始圖像，0u為破損圖像，▽表示梯度，λ表示Lagrange乘子。

圖1 圖像受損區(qū)域及其鄰域

根據(jù)變分原理，可求得與之對應的Euler-Lagrange方程為：

其中：

為解決 TV模型中的不連續(xù)問題，Chan和Shen[5]在TV模型的基礎上提出CDD模型，即將TV模型的擴散系數(shù)修改為此處，g的定義為：

由于這種選擇可以在大曲率處擴散變強，小曲率處擴散逐漸消失，因此，CDD修復模型為：

2 Criminisi算法描述

Criminisi等[6]提出的基于樣本紋理合成的圖像修補方法可以概括為以下3個步驟。

2.1 計算待修補塊的優(yōu)先權

圖2中，I表示整幅圖像，Ω表示待修復區(qū)域，?Ω代表其輪廓，Φ表示已知區(qū)域，且有 IΦ= ?Ω。

圖2 Criminisi算法示意圖

對于以?Ω上的點p為中心的目標塊pΨ，定義其優(yōu)先權為：

上式中，

其中 C(p)稱為置信度項，規(guī)定優(yōu)先填充那些含有較多已知像素部分的模塊，是Ψp的面積，一般C(p)的初始化取值為：

D(p)為數(shù)據(jù)項，它反映邊緣前沿的等照度強度，具有較強結構特征的部分優(yōu)先修復。 ▽Ip⊥表示p點的等照度線的方向和強度，np表示待修補區(qū)域輪廓的單位外法線方向，α為歸一化因子，這里取255。

本文采用的 Criminisi算法為改進優(yōu)先權的Criminisi算法[8]，取優(yōu)先權為：

這里 C(p)， D(p)滿足式(5)，設{Ωi}(0 ≤i≤ N)是每執(zhí)行一次修復之后新的待修復序列，則令：

2.2 搜索最佳匹配塊

在?Ω上找到 ()Pp值最大的目標塊?pΨ后，然后在已知區(qū)域內(nèi)搜索此目標塊的最佳匹配塊?qΨ，目標塊與最佳匹配塊有如下匹配準則：

其中，d (Ψp?,Ψq)表示目標塊Ψp?和樣本塊Ψq中對應已知像素的顏色差的平方和，I,I′分別對應塊Ψp?和Ψq中的已知像素點，則 d(Ψp?,Ψq)可由下式表示：

2.3 置信度的更新

在找到最佳匹配塊?qΨ后，將塊?qΨ中的像素對應復制到目標塊?pΨ中的未知像素點，該目標塊內(nèi)未知像素點轉變?yōu)橐阎袼攸c，因此這些點的置信度需要更新為：

重復上述的3個步驟，直至待修復區(qū)域被填完為止。

3 本文算法介紹

直方圖均衡化是由圖像灰度演繹得出的一種增強圖像整體對比度的增強技術，但是這種變換擴大圖像的動態(tài)范圍卻是以犧牲圖像的細節(jié)為代價的，因此本文將采用可以強化細節(jié)的自適應直方圖均衡化[16]，不僅擴大了圖像的動態(tài)范圍，還可以抑制圖像噪聲，即先保存圖像細節(jié)，再對圖像進行直方圖均衡化處理，最后再把細節(jié)加在處理后的圖像上。

根據(jù)文獻[15-16]，強化細節(jié)的自適應直方圖均衡化的原理可以用以下公式來說明：

上式中， xi,j為原始圖像的灰度值， xi′,j為處理后圖像的灰度值， mi,j為以點 xi,j為中心的的圖像窗領域內(nèi)所有像素點的灰度均值， H(xi,j)表示對點 xi,j進行直方圖均衡化操作，而 k(xi,j? mi,j)是用于增強所選圖像的局部對比度即強化圖像的細節(jié)，為了使增強后的圖像不超過[0,255]圖像的灰度值范圍，上式增加了判別條件。

在式(6)中，k為自適應參量，通過自適應改變的取值，可以在增強圖像細節(jié)的同時抑制掉圖像背景中的噪聲。為了實現(xiàn)這個目的，將參量的表達式定義為：

上式中，σi2,j為一個選定的大小為n×n方形窗W內(nèi)的灰度方差， σn2為整幅圖像的噪聲方差，k′為根據(jù)所選圖像的實際噪聲狀況決定的比例系數(shù)，其數(shù)值不宜過大也不宜過小。

在圖像修復前用強化細節(jié)的直方圖均衡化處理，可以擴大圖像的動態(tài)范圍，范圍越大，層次感越強，有利于CDD模型的擴散和最佳匹配塊的選擇，但是不可避免的會降低圖像的峰值信噪比，因此本文最后把修復后的圖像，對應于待修復區(qū)域位置上的像素填充到原待修復圖像上，以降低對原圖像的影響。

相對于本文算法，盡管Criminisi算法可以修復大塊破損的圖像也可以修復劃痕區(qū)域，但由于劃痕區(qū)域在利用塊搜索時將浪費大量時間，同時由于破損處較多，可能導致無完整塊進行填充，必將導致修復結果偏差，造成錯誤信息的累積。因此本文先人工提取圖像掩膜信息，利用形態(tài)學運算，先腐蝕再膨脹的方法分離出劃痕區(qū)域與大塊信息缺失區(qū)域的掩膜信息；然后利用CDD模型對劃痕區(qū)域修復；再利用改進的Criminisi算法進行大塊信息缺失區(qū)域的填充，最后把修復后的圖像對應像素填補到待修復圖像中。實驗結果證明改進算法具有良好的視覺效果。

算法流程可以分為三部分，第一部分：對圖像進行強化細節(jié)的自適應直方圖均衡化(步驟1～2)；第二部分：分離出劃痕區(qū)域與大塊信息缺失區(qū)域的掩膜，并用CDD算法對劃痕區(qū)域處理(步驟3～4)；第三部分：用改進的Criminisi算法進行后續(xù)處理(步驟5～9)。

本文算法具體如下：

步驟 1.讀入受損圖像，確定自適應均衡化操作所需要的方形窗W的大小(本文選取W為5×5)和比例系數(shù)k′的值(本文選取 k′= 7)；

步驟2.計算窗內(nèi)的噪聲方差 σi2,j，整幅圖像的噪聲方差 σn2及窗內(nèi)像素點的平均灰度值 mi,j，帶入式(7)，即計算出 xi′,j；

步驟 3.確定圖像的掩膜信息，根據(jù)形態(tài)學運算[17]分離出劃痕區(qū)域與大塊信息缺失區(qū)域，并分別繪制其掩膜圖；

步驟4.根據(jù)步驟3找出劃痕區(qū)域的掩膜，利用CDD算法修復(本文CDD算法中迭代次數(shù)均取n= 1000次)；

步驟 5.找出分離后待修復大塊區(qū)域的邊界?Ωi( ?Ω0=?Ω)，設置(初始時 i= 0)，如果 Ωi= φ，退出循環(huán)；

步驟6.計算優(yōu)先權 P(p)， ?p ∈?Ωi；

步驟 7.找出具有最大優(yōu)先權值的待修復區(qū)域塊?pΨ ，即

步驟8.計算最佳匹配塊Ψq?∈Φ，并把Ψq?中對應的圖像信息復制到中；

Ψ?p∩Ω

步驟9.i=i+1，重復步驟5～8；

步驟10.把修復后的圖像對應于掩膜的部分取出填補到待修復圖像中。

4 實驗結果分析

本文實驗用 Matlab 2012b作為工具，在 Intel酷睿 2處理器(2.0 GHz)，2 G內(nèi)存的 PC機上實現(xiàn)的。

實驗將本文的算法與本文去掉步驟1和步驟2的算法(以下簡稱算法1)、CDD算法、Criminisi算法及文獻[8]的算法分別進行了比較，如圖 3~4所示。

圖3是圖像修復常用的蹦極圖，圖3(b)出現(xiàn)偏差延續(xù)，存在明顯的不連續(xù)性；圖3(c)~(e)(本文取λ1= λ2= 1, λ3= 3)屋頂及屋頂上下都存在一定的偏差，不能自然地體現(xiàn)屋頂?shù)奶卣?；圖3(d)在大塊信息缺失區(qū)域產(chǎn)生模糊現(xiàn)象，白色圈出來的位置為沒有修復到的孤立點；圖3(f)很好地解決了以上出現(xiàn)的問題，取得了較好的視覺效果。

圖3 蹦極修復效果比較圖

如圖4可見，圖4(b)和4(c)出現(xiàn)偏差延續(xù)現(xiàn)象，狒狒的鼻子上均有明顯的黑色部分；圖4(d)在大塊信息缺失處出現(xiàn)模糊現(xiàn)象；圖4(e)保證了圖像在大范圍上的視覺效果，但鼻子的左右兩側均稍有瑕疵，紋理不自然；圖4(f)顯示本文算法克服了上述算法的種種瑕疵，視覺效果最好。

圖4 狒狒修復效果比較圖

本文選取了兩幅具有代表性的圖片進行修復，通過實驗對比與其他算法的修復時間，從表1中可以看出，本文算法相對于其他3種算法有效地縮短了時間，雖然CDD算法時間最短，但是在大塊區(qū)域時有明顯的模糊現(xiàn)象。表2展現(xiàn)了本文算法與其他算法的峰值信噪比(peak signal-to-noise ratio, PSNR)比較。

表1 不同算法修復時間比較(s)

表2 不同修復算法的峰值信噪比比較(dB)

5 結 束 語

本文簡單介紹了CDD模型及Criminisi算法，分別分析了這兩類算法的特點，因此在對待既含有劃痕又含有大塊破損的區(qū)域的圖像，區(qū)分對待不同的待修復區(qū)域。實驗結果表明，本文提出的算法不僅在處理劃痕區(qū)域與大區(qū)域破損處能夠較好的結合，而且Criminisi算法還能較好的處理CDD算法修復不到的孤立點，縮短修復時間，修復后的視覺效果更好。由于目前對圖像修復的質量，均是依靠人眼主觀評價，未來希望對修復質量的定量客觀評價進行研究。

[1] 張紅英, 彭啟琮. 數(shù)字圖像修復技術綜述[J]. 中國圖象圖形學報, 2007, 12(1): 1-10.

[2] Bertalmio M, Sapiro G, Caselles V, Ballester C. Image inpainting [C]//SIGGRAPH 2000, Proceedings of the 27thAnnual Conference on Computer Graphics, New Orleans, USA: ACM, 2000: 417-424.

[3] Chan T, Shen J. Mathematical models for local non-texture inpainting [J]. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019-1043.

[4] Rudin L I, Osher S, Faterni E. Nonlinear total variation based noise removal algorithms [J]. Physica D, 1992, 60: 259-268.

[5] Chan T, Shen J. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436-496.

[6] Criminisi A, Perez P, Toyama K. Object removal by exemplar-based inpainting [C]//Proc Conf Comp Vision Pattern Rec, Madison WI, 2003: 721-728.

[7] 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.

[8] 黃淑兵, 朱曉臨, 徐云云, 朱 坤. 一種改進的基于紋理合成的圖像修復算法[J]. 合肥工業(yè)大學學報(自然科學版), 2011, 34(2): 313-320.

[9] 任 澍, 唐向宏, 康佳倫. 利用紋理和邊緣特征的Criminisi改進算法[J]. 中國圖象圖形學報, 2012, 17(9): 1085-1091.

[10] Li B R, Qi Y, Shen X K. An image inpainting method [C]//Computer Aided Design and Computer Graphics, 2005. Ninth International Conference on. IEEE, 2005: 6.

[11] Wang Min qin. A novel image inpainting method based on image decomposition [J]. Procedia Engineering, 2011, 15: 3733-3738.

[12] Bugeau A, Bertalmio M, Caselles V, Sapiro G. A comprehensive framework for image inpainting [J]. IEEE Transactions on Image Processing, 2010, 19(10): 2634-2645.

[13] 劉庚龍, 檀結慶. 一種改進的整體變分圖像修復方法[J]. 計算機工程與應用, 2012, 48(7): 194-196.

[14] 趙顏偉, 李象霖. 基于 CDD模型的快速圖像修復算法[J]. 計算機仿真, 2008, 25(10): 223-227.

[15] 任 慧, 李新華, 朱逸婷. 自適應直方圖均衡化改進的全變分圖像修復[J]. 計算機系統(tǒng)應用, 2013, 22(6): 98-101.

[16] 宋 剛, 劉瑤華. 一種能強化細節(jié)的自適應直方圖均衡法[J]. 山東工業(yè)大學學報, 1999, 29(1): 81-93.

[17] Rafael C G, Richard E W. 數(shù)字圖像處理[M]. 3版. 阮秋琦, 阮宇智, 譯. 北京: 電子工業(yè)出版社, 2011: 402-493.

An Image Inpainting Algorithm Combined of CDD Model and Criminisi Algorithm

Jiang Ping, Zhang Jin
(School of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China)

Aiming at images with a lot of missing information and scratches, this paper puts forward a new restoration algorithm by combining the advantages of CDD model and Criminisi algorithm. Specifically, this algorithm first adopts the equalized operation of detail-oriented and self-adaptive histogram to expand the dynamic range of the images, and then utilizes morphology operators to separate the scratch regions and large areas in the images that need to be restored. Subsequently, CDD model is applied to restore the scratches and then the improved priority Criminisi algorithm is used to implement subsequent restoration. Finally, the restored images corresponding to the pixel of missing areas are filled into the regions of images need restoration. As the experimental results indicate, the improved algorithm has overcome the possible deviation continuation problems in current algorithm and can make the restored images more consistent with people’s visual effect.

CDD model; Criminisi algorithm; image inpainting; equalization of self-adaptive histogram; morphology operators

TP391

A

2095-302X(2014)05-0741-06

2014-03-03；定稿日期：2014-06-11

國家自然科學基金資助項目(11471093)

江 平(1972–)，女，安徽安慶人，副教授，博士。主要研究方向為CAGD、圖像修復。E-mail：jiang_hfut@126.com