基于偏微分方程的圖像修復(fù)算法

李 亮，郭樹旭，陳國法

（吉林大學(xué) 電子科學(xué)與工程學(xué)院，長春 130012）

基于偏微分方程的圖像修復(fù)算法

李 亮，郭樹旭，陳國法

（吉林大學(xué) 電子科學(xué)與工程學(xué)院，長春 130012）

針對TV模型修復(fù)算法只沿梯度垂直方向擴(kuò)散，容易在平滑區(qū)域引入階梯效應(yīng)，迭代效率低，易產(chǎn)生假邊緣的缺點(diǎn)，分析比較了TV圖像修復(fù)模型的性能，提出了一種改進(jìn)的圖像修復(fù)算法。該算法同時(shí)結(jié)合了各向同性和各向異性擴(kuò)散，利用區(qū)域頻率差異實(shí)現(xiàn)了在不同的區(qū)域使用不同的迭代方程，有效避免了原始算法引入的階梯效應(yīng)，提高了迭代效率。實(shí)驗(yàn)結(jié)果表明，該算法與TV模型算法相比，在具有同樣修復(fù)效果的前提下，避免了階梯效應(yīng)并優(yōu)于TV模型的修復(fù)速度。

圖像修復(fù)；各向同性；各向異性；TV模型；階梯效應(yīng)

0 引 言

圖像修復(fù)技術(shù)［1］是圖像處理［2－4］中的重要組成部分，圖像修復(fù)是根據(jù)圖像中的已知區(qū)域的相關(guān)信息，恢復(fù)信息缺失區(qū)域中的信息。根據(jù)圖像修復(fù)理論和方法的不同特點(diǎn)，圖像修復(fù)技術(shù)大致可以分為兩大類：1）基于結(jié)構(gòu)的圖像修復(fù)技術(shù)［5－10］；2）基于紋理合成的圖像修復(fù)技術(shù)［11－15］?；诮Y(jié)構(gòu)的圖像修復(fù)技術(shù)適用于對劃痕、污漬和文字等小目標(biāo)區(qū)域的修復(fù)，基于結(jié)構(gòu)的修復(fù)算法核心思想是利用物理學(xué)中的熱擴(kuò)散方程將待修補(bǔ)區(qū)域周圍的信息傳播到待修補(bǔ)區(qū)域中。TV模型修復(fù)存在平滑區(qū)域修復(fù)時(shí)易出現(xiàn)階梯效應(yīng)的缺點(diǎn)。筆者在前人算法基礎(chǔ)上提出了一種改進(jìn)算法，采用各向同性和各向異性相結(jié)合的擴(kuò)散模式，在像素梯度較小的區(qū)域采用各向同性擴(kuò)散，提高迭代速度，而在像素梯度值較大的區(qū)域采用基于P-laplace算子［16］的各向異性擴(kuò)散，避免了圖像平坦區(qū)域修復(fù)時(shí)出現(xiàn)的階梯效應(yīng)。實(shí)驗(yàn)結(jié)果表明，該算法具有很好的修復(fù)效果和良好的收斂性。

1 基于TV模型修復(fù)算法

TV模型最早是由Ruin提出的一種圖像去噪模型，他通過擴(kuò)展基于TV的去噪模型，提出了基于TV模型的圖像修復(fù)方法，能在有噪聲的情況下有效地對圖像進(jìn)行修復(fù)。TV模型修復(fù)算法主要利用偏微分方程求能量最小化泛函，再利用Lagrange乘子轉(zhuǎn)換成無約束條件的極值問題，然后求解滿足Euler-Lagrange的方程，方程的解就是圖像的修復(fù)結(jié)果，具體過程如下。

圖1 圖像修復(fù)示意圖Fig.1 The sketch map of image inpainting

記D為待修復(fù)區(qū)域，E為待修復(fù)區(qū)域的鄰域，記修復(fù)后的區(qū)域?yàn)閡，待修復(fù)區(qū)及其鄰域?yàn)棣福ㄒ妶D1）。定義代價(jià)函數(shù)

其中R為一非負(fù)實(shí)函數(shù)，u為圖像。

考慮到圖像可能被噪聲污染，在修復(fù)的同時(shí)還應(yīng)去噪，所以需滿足噪聲約束條件

假定初始信號是被白噪聲污染的，σ是白噪聲的標(biāo)準(zhǔn)方差。

要滿足修復(fù)邊緣的條件，必須選擇適當(dāng)?shù)膔函數(shù)，即r函數(shù)有限時(shí)邊緣才能修復(fù)，這里取r＝（｜▽u｜）＝｜▽u｜［17］。運(yùn)用拉格朗日乘子法將式（1），式（2）轉(zhuǎn)化為無約束條件極值問題，其新的代價(jià)函數(shù)為

式（3）中第1項(xiàng)為正則化項(xiàng)，第2項(xiàng)為保真項(xiàng)，λ為Lagrange乘子。

式（3）對應(yīng)的能量最小泛函方程為

對于一切z＝（x，y）∈E，z為像素點(diǎn)，lagrange乘子λ滿足

用梯度下降法求解式（4）有

解得u值即為所求的最終修復(fù)圖像。

1.1 TV模型的缺點(diǎn)

TV模型修復(fù)算法運(yùn)用了二階偏微分方程，有較完整的數(shù)學(xué)理論基礎(chǔ)，數(shù)值實(shí)現(xiàn)上較簡單，在保持邊緣的同時(shí)達(dá)到去噪的目的。但從TV修復(fù)方程的迭代過程看，它是一種各向異性擴(kuò)散的過程。事實(shí)上，在圖像特征明顯的區(qū)域應(yīng)該使用較慢的迭代速度，而在圖像特征不明顯的區(qū)域（如圖像的平滑區(qū)域），其修復(fù)的迭代速度應(yīng)該加快，而TV模型的這種單獨(dú)使用各向異性擴(kuò)散的過程，使其擴(kuò)散效率較低。再者，TV模型修復(fù)過程中，TV是沿著與梯度正交的方向和邊緣方向擴(kuò)散，反映出沿著不同的方向擴(kuò)散系數(shù)不同的思想。而實(shí)際在圖像的平滑區(qū)域是不存在邊緣方向的，仍沿著邊緣方向擴(kuò)散，這將導(dǎo)致在平坦區(qū)域的噪聲抑制不充分，甚至出現(xiàn)假邊緣，文獻(xiàn)［18］已證明出現(xiàn)假邊緣原因是擴(kuò)散系數(shù)不能隨圖像結(jié)構(gòu)特征的變化而取值，產(chǎn)生階梯效應(yīng)。圖2給出了一組由TV模型修復(fù)實(shí)驗(yàn)得到的圖像。

圖2 TV模型修復(fù)實(shí)驗(yàn)Fig.2 The experiment of inpainting based on TV

在圖2中（n＝900steps，t＝4.85s），對有劃痕的圖像具有較好的修復(fù)，但是在平滑區(qū)域產(chǎn)生假邊緣，存在階梯效應(yīng)。

2 新算法的改進(jìn)與實(shí)現(xiàn)

圖3 整體坐標(biāo)與局部坐標(biāo)示意圖Fig.3 The sketch map of Integral coordinate system and local coordinate system

針對TV模型修復(fù)算法中存在的不足，提出一種各向同性和各向異性擴(kuò)散相結(jié)合的圖像修復(fù)模型。其基本思想是，首先對圖像進(jìn)行歸一化處理，利用sobel算子計(jì)算待修復(fù)點(diǎn)的梯度。設(shè)定一像素點(diǎn)梯度閾值，當(dāng)待修復(fù)點(diǎn)梯度小于給定閾值時(shí)，采用各向同性擴(kuò)散；當(dāng)待修復(fù)點(diǎn)梯度值大于給定閾值時(shí)，采用基于p-laplace算子的非線性的各向異性擴(kuò)散。修復(fù)方程如下

當(dāng)1＜p＜2時(shí)，方程是沿uζζ和uηη兩個方向同時(shí)進(jìn)行擴(kuò)散的，｜▽u｜（p－2）和（p－1）｜▽u｜（p－2）分別控制兩個方向的擴(kuò)散速度，根據(jù)待修復(fù)區(qū)域鄰域特征選擇適當(dāng)?shù)膒值，即可保持圖像的邊緣信息又可平滑噪聲，所以該算法具有較快的修復(fù)速度。

2.1 數(shù)值計(jì)算

對擴(kuò)散算子｜▽u｜p－2▽u離散化，令v＝（ν1，ν2）＝｜▽u｜p－2▽u，其中Δt為時(shí)間步長；u（n）表示待修復(fù)點(diǎn)在nΔt時(shí)刻的值。對于散度算子采用半點(diǎn)中心差分法實(shí)現(xiàn)。示意圖如圖4所示，∧＝［E，N，W，S］為待修復(fù)點(diǎn)O的4鄰域像素點(diǎn)，［e，n，w，s］分別為對應(yīng)的4鄰域半點(diǎn)像素。

圖4 目標(biāo)像素O及鄰域點(diǎn)Fig.4 Target pixel Oand its neighbors

記v＝（ν1，ν2）＝｜▽u｜p－2▽u，則▽·v離散化為

其中h為網(wǎng)格大小，一般取h＝1。對半點(diǎn)像素梯度值做進(jìn)一步計(jì)算，下面以半點(diǎn)像素e（i＋，j）為例，e點(diǎn)梯度計(jì)算如下

將式（14）代入式（7）第二方程有

使用Gauss-Jacobi迭代算法，則圖像值

經(jīng)一步步迭代即可得到修復(fù)后的圖像。

3 實(shí)驗(yàn)結(jié)果及分析

筆者算法是在實(shí)驗(yàn)環(huán)境AMD Athon（th）64Processor3000，CPU 2.00GHz，內(nèi)存512MByte硬件條件下，利用Matlab7.4.0編程進(jìn)行的仿真實(shí)驗(yàn)。分別采用了lena圖像，cameraman圖像和老舊照片做對比實(shí)驗(yàn)（見圖5～圖7）。

圖5 對比實(shí)驗(yàn)1Fig.5 Contrast test 1

圖6 對比實(shí)驗(yàn)2Fig.6 Contrast test 2

圖7 對比實(shí)驗(yàn)3Fig.7 Contrast test 3

由實(shí)驗(yàn)1和實(shí)驗(yàn)2可以看到，TV模型算法在平坦區(qū)域存在假邊緣。實(shí)驗(yàn)1中TV模型算法在帽子處存在明顯的假邊緣，而改進(jìn)算法避免了假邊緣現(xiàn)象。

表1，表2數(shù)據(jù)是在T＝0.1，p＝1.8時(shí)的實(shí)驗(yàn)結(jié)果，可看以出，改進(jìn)算法從迭代時(shí)間和峰值信噪比上都優(yōu)于TV模型算法。由對比實(shí)驗(yàn)3看出，當(dāng)圖像劃痕較小，破損面積較小的時(shí)候，改進(jìn)算法和TV模型算法在修復(fù)效果上，不能從視覺上很好地進(jìn)行判斷，因此當(dāng)修復(fù)結(jié)果從視覺上未能清晰區(qū)分修復(fù)效果時(shí)，應(yīng)從數(shù)值上量化分析修復(fù)效果。理論上，多數(shù)采用峰值信噪比PSNR對修復(fù)結(jié)果進(jìn)行評價(jià)

其中U為原圖，U0為修復(fù)后的圖像，M和N 為圖像的行列值?？梢钥闯?，修復(fù)后的圖像，其PSNR的計(jì)算結(jié)果越大，說明修復(fù)的效果越好，即修復(fù)后的圖像與原始圖像的差值越小。表1是3組實(shí)驗(yàn)的PSNR值的結(jié)果比較，從表1中可以看出，改進(jìn)算法其PSNR計(jì)算結(jié)果值都大于TV模型算法的PSNR值，即改進(jìn)后的算法的修復(fù)結(jié)果圖更接近原始圖像，修復(fù)結(jié)果優(yōu)于TV模型算法。表2為TV模型算法和改進(jìn)算法的修復(fù)時(shí)間效率對比，從表2中可以看出，改進(jìn)的算法由于兩個方向同時(shí)擴(kuò)散，大大提高了修復(fù)的效率，修復(fù)所用時(shí)間比TV模型算法少。所以，無論從主客觀上比較，改進(jìn)算法都要優(yōu)于TV模型算法。

表1 PSNR實(shí)驗(yàn)比較Tab.1 Peak value signal-to-noise ratio experimental comparison

表2 算法效率對比Tab.2 Compared the efficiency of the algorithm

4 結(jié) 語

筆者針對TV模型圖像修復(fù)算法中存在的不足，提出一種改進(jìn)算法。該算法中采用了各向同性和各向異性擴(kuò)散相結(jié)合的擴(kuò)散模式，主要通過計(jì)算待修復(fù)點(diǎn)的梯度值判斷圖像區(qū)域的平滑度。設(shè)定一梯度閾值，從而根據(jù)待修復(fù)點(diǎn)梯度閾值的大小選擇修復(fù)方程，即在不同的區(qū)域考慮使用不同擴(kuò)散的修復(fù)方程，有效地避免了原始算法在平滑區(qū)域引入的階梯效應(yīng)，擴(kuò)散在兩個方向同時(shí)進(jìn)行，提高了修復(fù)效率。實(shí)驗(yàn)仿真結(jié)果說明，新算法具有較強(qiáng)的修復(fù)力和較快的收斂速度。

［1］張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述［J］.中國圖象圖形學(xué)報(bào)，2007，12（1）：1-10.

ZHANG Hong－ying，PENG Qi-cong.A Survey on Digital Image Inpainting［J］.Journal of Image and Graphics，2007，12（1）：1-10.

［2］劉樹昌，劉鵬，王延海，等.大容量高速視頻圖像傳輸技術(shù)研究［J］.吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2011，29（1）：21-24.

LIU Shu-chang，LIU Peng，WANG Yan-hai，et al.Research on Large-Capacity High-Speed Video Image Transmission Technology［J］.Journal of Jilin University：Information Science Edition，2011，29（1）：21-24.

［3］趙春彥，趙巖，陳賀新.基于邊緣檢測的深度圖與單視圖配準(zhǔn)算法［J］.吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2011，29（3）：175-180.

ZHAO Chun-yan，ZHAO Yan，CHEN He-xin.Registration of Depth and Video Data Based on Edge Detection［J］.Journal of Jilin University：Information Science Edition，2011，29（3）：175-180.

［4］邵向鑫，郭樹旭，王朗.基于邊緣擴(kuò)展相位相關(guān)的圖像拼接算法［J］.吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2010，28（1）：95-99.

SHAO Xiang-xin，GUO Shu-xu，WANG Lang.Image Mosaic Algorithm Based on Extended Phase Correlation of Edge［J］.Journal of Jilin University：Information Science Edition，2010，28（1）：95-99.

［5］BERTALMIO M，SAPIRO G，CASELLES V，et al.Image Inpainting［C］∥Proc SIGGRA PH 2000.New Orleans，LA：［s，n.］，2000：417-424.

［6］CHAN T F，SHEN J.Mathematical Models for Local Deterministic Inpaintings［J］.Journal on Applied Mathematics，2002，62（3）：1019-1043.

［7］WANG Wei-wei，F(xiàn)ENG Xiang-chu.Anisotropic Diffusion with Nonlinear Structure Tensor［J］.SIAM Joumal on Multiscale Modeling and Simulation，2008，7（2）：963-977.

［8］MARCELO BERTALMIO，LUMINITA VESE，GUILLERMO SAPIRO，et al.Simultaneous Structure and Texture Image Inpainting［J］.IEEE Trans on Image Processin，2003，12（8）：882-889.

［9］ESEDOGLU S，SHEN J H.Digital Inpainting Based on the Mumford Shah-Euler Image Model［J］.European Journal on Applied Mathematics，2002，13（4）：353-370.

［10］CHAN T F，SHEN J.Non-Texture Inpainting by Curvature-Driven Diffusions（CDD）［J］.Journal on Visual Communication and Image Representation，2001，12（4）：436-449.

［11］周珊珊，趙知勁，葉學(xué)義.采用 TV及紋理合成技術(shù)的分層圖像修復(fù)［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（23）：201-203.

ZHOU Shan-shan，ZHAO Zhi-jin，YE Xue-yi.Total Variation and Texture Synthesis Applied to Multi-Level Image Inpainting［J］.Computer Engineering and Applications，2011，47（23）：201-203.

［12］楊關(guān)，馮國燦，陳偉福，等.基于概率模型的圖像紋理模型［J］.中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，50（2）：6-15.

YANG Guan，F(xiàn)ENG Guo-can，CHEN Wei-fu，et al.Texture Models Based on Probabilistic Graphical Models［J］.Acta Scientiarum Naturalium Universitatis Sunyatseni，2011，50（2）：6-15.

［13］張晴，林家駿，高深.基于色差分析的圖像修復(fù)改進(jìn)算法［J］.華中理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，37（3）：367-371.

ZHANG Qing，LIN Jia-jun，GAO Shen.An Improved Colors-Analysis-Based Algorithm of Image Inpainting［J］.Journal of East China University of Science and Technology：Natural Science Edition，2011，37（3）：367-371.

［14］魏欣，蔣華偉.基于紋理和結(jié)構(gòu)的圖像修復(fù)算法研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20（9）：90-93.

WEI Xin，JIANG Hua-wei.Study on Inpainting Algorithm Based on Image Structure and Texture［J］.Computer Technology and Development，2010，20（9）：90-93.

［15］丁西明，段漢根，吳長勤.一種簡單的塊匹配圖像修復(fù)算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20（11）：80-83.

DING Xi-ming，DUAN Han-gen，WU Chang－qin.Image Inpainting Based on Simple Block Matching［J］.Computer Technology and Development，2010，20（11）：80-83.

［16］張紅英.數(shù)字圖像修復(fù)技術(shù)的研究與應(yīng)用［D］.成都：電子科技大學(xué)計(jì)算機(jī)學(xué)院，2006.

ZHANG Hong－ying.Research and Application on Digital Image Inpainting［D］.Chengdu：College of Computer，University of Electronic Science and Technology of China，2006.

［17］CHAN T F，SHEN J H.Mathematieal Models for Local Non-Texture Inpainting［J］.SIAM J APPl Math，2001，62（3）：1019-1043.

［18］WEICKERT J.A Review of Nonlinear Diffusion Filtering［C］∥Scale-Space Theory in Computer Vision.London：Springer-Verlag，1997，1252：3-28.

Based on Partial Differential Equations of Image Inpainting

LI Liang，GUO Shu-xu，CHEN Guo-fa
（College of Electronic Science and Engineering，Jilin University，Changchun 130012，China）

TV image inpainting only repairs algorithm along the vertical direction，making diffusion gradient in smooth area into stair step effect，reducing iterative efficiency，producing false edge faults.We analyse and compare the TV image restoration model and repair the performance of the model is put forward in this paper.Puts forward an improved image restoration algorithm，the algorithm in combination with the isotropic and anisotropic diffusion，the use of regional frequency difference in different area realized the use of different iterative equations，effectively avoid the original algorithm introduces ladder effect，to improve the iterative efficiency.The experimental results show that the algorithm and the TV algorithm，have the same effect on the premise of repair，the algorithm avoids the stair step effect at the same time with the model is better than TV repair speed.

image inpainting；isotropic diffusion；anisotropy diffusion；TV model；step effect

TP391.41

A

1671-5896（2012）01-0072-06

2011-11-19

李亮（1980—）男，吉林松原人，吉林大學(xué)碩士研究生，主要從事圖像處理、數(shù)字信號處理研究，（Tel）86-18943628007（E-mail）lliang09＠m(xù)ails.jlu.edu.cn；郭樹旭（1959—），男，長春人，吉林大學(xué)教授，博士，博士生導(dǎo)師，主要從事信號檢測與信息處理等研究，（Tel）86-13089111921（E-mail）guosx＠jlu.edu.cn。

（責(zé)任編輯：劉東亮）