非均勻紋理圖像的分層Criminisi修復算法

彭春華，唐利明

?

非均勻紋理圖像的分層Criminisi修復算法

彭春華1,2，唐利明1

（1. 湖北民族學院 理學院，湖北 恩施 445000；2. 恩施職業技術學院，湖北 恩施 445000）

為了提高非均勻紋理圖像大區域修復效果，提出了一個分層Criminisi圖像修復算法。首先采用多尺度變分分解模型將圖像分解成一系列圖層之和，不同圖層包含不同尺度的圖像特征，而同一圖層包含幾乎相同的尺度特征。然后在每個圖層中分別采用Criminisi算法進行修補。由于同一圖層包含尺度大致相同的圖像特征，所以在匹配塊的搜索過程中，分層修復能較容易地搜尋到最優的匹配塊。最后結合分別修復的各個圖層，得到最終的修復結果。實驗結果表明，對于不同的非均勻紋理人工圖像和自然圖像，本文模型都能取得較為滿意的修復結果。

圖像修復；Criminisi算法；變分圖像分解

0 引言

數字圖像修復是圖像處理和計算機視覺等眾多領域中的一個研究熱點。近些年來出現了許多卓有成效的圖像修復模型或方法，這些方法大體上可分為兩大類[1-3]：一類是針對小尺度缺損的基于結構的圖像修復技術；另一類是針對大面積破損的基于樣本塊匹配的紋理合成算法。

對第一類修復算法而言，目前最具代表性的是基于偏微分方程（partial differential equation，PDE）的數字圖像修復算法[4-10]，其核心思想是，利用待修復區域的邊緣信息，確定擴散信息和擴散方向，從區域邊界各向異性地向邊界內擴散。例如Bertalmio等[4]提出的等照度線（isophote）模型；Shen等[5]提出了總體變差（total variation，TV）模型；隨后，他們對TV模型進行改進，又提出了曲率推動擴散模型（curvature driven diffusion，CDD）[5]。基于PDE的圖像修復技術對破損區域相對較小的結構圖像有不錯的效果，但它們對破損區域較大的圖像修復效果不太理想，容易產生模糊現象。

第二類是基于樣本塊匹配的紋理合成技術，主要用于填充大塊信息丟失的圖像，此類算法也稱為圖像補全（Image completion）。其中最具有代表性的是Criminisi等人[11]提出的基于優先權的樣本塊匹配的圖像修復算法。這種算法的主要思想是，首先計算待修補區域的邊界上每個像素點的優先級，并選擇優先級最高的像素點，然后以該點為中心，同時根據圖像的紋理特征，選取大小合適的像素塊，最后在待修補區域的周圍尋找與之最相近的匹配塊，來替代該像素塊。循環整個過程，直至待修補區域被填滿，從而完成修復。Criminisi算法在確保可以修復較大破損區域的同時，還一定程度上保留了圖像的結構和紋理信息，使得修復結果具有較好的視覺效果。后續，很多專家學者對Criminisi算法進行研究，提出了大量的改進算法[12-19]。例如，Zhou等[12]通過極小化一個基于圖像梯度信息的目標函數得到最優的像素塊尺寸；Xu等[13]提出了基于稀疏描述的數據項，用來度量像素塊的結構置信度；Meur等[14]在優先級的計算中提出了基于結構張量的數據項；Huang等[15]采用梯度項代替數據項與置信度構成優先級的計算公式；Liu等[16]將置信度改進為指數形式，并將優先權函數表示為置信度和數據項的加權和以平滑其迅速降為零的缺點；Liu等[17]通過極小化一個包含平滑項和數據項的目標函數尋找最優的匹配塊，并且采用了多尺度圖割方法對優化問題進行了快速求解；張顯全等[18]根據圖像待修復點梯度的大小，在源區域中確定其匹配區域的范圍，減少搜索次數；李尊等[19]利用數學形態學中的腐蝕與膨脹算子對待修復區域邊緣進行處理，以降低錯誤信息的累積。

本文為了提高非均勻紋理圖像大區域修復效果，提出了分層Criminisi圖像修復算法。傳統Criminisi算法中，匹配塊是在整個圖像的已知區域中選擇和待修補塊最相似的像素塊，并將最優像素塊的灰度值拷貝到當前的待修復像素塊中。但是由于圖像通常情況下都包含很復雜的結構信息、灰度信息，所以這可能導致在搜索過程中很難搜尋到和待修補塊非常相似的匹配塊，某些情況下還可能相差很遠。針對上述不足，本文采用分層修復的策略，首先采用多尺度變分分解模型將圖像分解成一系列圖層之和，不同圖層包含不同尺度的圖像特征，而同一圖層包含幾乎相同的尺度特征。然后在每個圖層中分別采用Criminisi修復算法進修修補。由于同一圖層包含尺度大致相同的圖像特征，所以在匹配塊的搜索過程中，分層修復能較容易地搜尋到最優的匹配塊。

順便指出，Bertalmio等人也采用了基于圖像分解的修復方法[20]，他們將圖像分解為結構層和紋理層，結構層使用PDE擴散修復，紋理層采用紋理合成方法修復，最后將兩類方法疊加得到最終結果。基于分解的修復方法對于紋理圖像有較好的效果，并且相對于單純的PDE方法和紋理合成方法更具優勢。但是本文的分層Criminisi修復算法具有以下優勢：①本文算法將圖像分解成不同的圖層并進行分開地修復，這樣分層修復可以很好地修復非均勻紋理圖像，這是本文的研究重點；②每個圖層都采用Criminisi算法進行修復，這樣可以很好地修復大區域破損圖像。

1 Criminisi算法簡介

在基于樣本的紋理合成圖像修補算法中，Criminisi等人[11]利用計算邊界像素點的優先權值來決定修復順序。對于邊界像素點優先權的大小如何確定，他們主要考慮以下兩個因素：①被更多高置信度像素點包圍的點先進行修復；②延續待修復區域的結構（主要指圖像邊緣），強度大，垂直于修補邊界的結構先進行修復。修補過程中，首先通過優先權函數決定修復次序。然后根據SSD（the sum of squared differences）匹配準則（即像素灰度平方差和最小）在已知圖像區域內選擇最佳的像素塊，并將最佳的像素塊的灰度值拷貝到當前的待修復像素塊中。此后更新修補邊界信息，繼續選出優先級最高的像素塊進行修復，如此反復，直到待修補區域被填充滿，完成整個修復過程。

1.1 優先權計算

如圖1所示：表示待修復的圖像區域；表示待修復區域邊界上的一個像素點；是以為中心的像素塊（待修補塊）。設()為目標像素塊的置信度，表示以點為中心的圖像塊中已知數據的可信度，定義為：

式中：||示區域的勢，對于數字圖像，||表示像素塊中像素點的數目。設()為數據項，刻畫目標像素塊的結構信息量。數據項()定義為：

圖1 基于樣本塊的紋理合成示意圖

利用置信度()和數據項()，優先權系數定義為：

()＝()×()

根據優先權系數的定義，()與置信度()和數據項()都成正比例關系。所以Criminisi算法會先修補含有更多像素信息，并且等照度線盡量垂直于修補區域邊界的像素塊。這種修補次序可以使得修復圖像具有更好的視覺連通性，有效地避免修補過程中出現結構斷裂和模糊現象。

2.2 最佳匹配塊的選擇與填充

一旦確定了待修復的目標塊，就可以在未受損的區域尋找與待修復塊相似的樣本塊，其中，滿足：

＝argmin(,) (3)

式中：(,)表示像素塊與的距離，一般情況下，(,)選擇為像素塊與里面對應的已知填充好的像素點的顏色之間的差的平方和，計算公式如下：

找到最佳匹配塊后，待修復塊中待修復點的像素值對應使用目標塊中的像素值來填充，完成修補。

2.3 置信度更新

當待修復目標塊被填充后，那么其填充像素點的置信度更新公式如下：

置信度更新完成后，說明一個待修復塊的修復已經完成。與此同時，圖形的邊緣也發生了變化，然后重復以上幾個步驟，直到整個修補區域被填滿。

3 本文算法

3.1 多尺度變分分解模型

本文采用如下三元變分圖像分解模型對輸入圖像進行分解[21]：

式中：表示BV半范數；表示G范數；表示L2范數的平方。求解極小化問題(5)，輸入圖像I被分解為I＝u＋v＋r，其中u是圖像的結構分量；v是圖像的紋理分量。參數g為尺度參數[21]：在結構分量u中，尺度大于1/g的圖像結構將被保留在結構分量u中，而小于1/g的結構將被模糊掉；在紋理分量中，尺度小于4lg的圖像紋理將被保留在紋理分量u中，而大于4lg的紋理將被模糊掉。圖2顯示了采用變分圖像分解模型(5)對一幅Barbara圖像的分解結果。從實驗結果可以看出該模型可以非常好地區分圖像的結構和紋理。

本文采用變分分解模型(5)進行圖像多尺度分解。首先選取初始尺度參數0，一般情況下選擇一個較小的正數。利用變分分解模型(5)將輸入圖像分解為＝1＋1＋1，其中：

式中：1＝－1＋1為剩余分量。如上分析，1包含了尺度大于1/0的圖像結構；1包含了尺度小于4的圖像紋理。在這種情況下，尺度小于1/0的圖像結構和尺度大于40的圖像紋理都被劃分到剩余分量1。由此，我們可以增加尺度參數的值以捕獲剩余分量中的結構和紋理。設1＞0，將剩余1作為輸入，利用變分分解模型對其進行分解，1＝2＋2＋2，其中：

類似地，2包含結構的尺度為[1/1, 1/0]；2包含紋理尺度為[40, 41]，其它的圖像特征都被劃分到剩余分量2中。由此可以繼續對剩余分量進行分解，每次設定尺度參數滿足＋1＞：

式中：＝0, 1, …；0＝。經過步分解，圖像被分解為：

I

＝

u

1

＋

u

2

＋…＋

uk

＋

v

1

＋

v

2

＋…＋

vk

＋

rk

圖3顯示了采用變分圖像分解模型(5)對Barbara圖像的多尺度分解結果。從實驗結果可以看出圖像很好地分解為不同尺度的結構和紋理分量之和。本文將這些結構分量和紋理分量稱為圖層。

3.2 分解模型的數值求解

多尺度變分分解實際上就是反復求解以下變分模型：

式中：i＝0, 1, …；r0＝I。本文采用交替迭代法求解上述極小化問題。為了簡化符號，在后面的敘述中省略下標“i”。設定初值(u0, v0)＝(0, 0)：

對已極小化問題(6)和(7)，本文采用對偶框架下的投影算法對其進行求解[21]：

式中：1表示閉凸集：

式中：a,j為拉格朗日乘子。通過互補松弛定理，當a,j＞0時，|p,j|＝1；當|p,j|＜1時，a,j＝1，此時?(div()－),j滿足?(div()－),j＝0。因此對于任何一種情況，a,j都滿足：

a,j＝|?(div()－),j|

此時，極小化問題(11)可以采用半隱式固定點迭代算法求解：

3.3 算法步驟

本文的主要貢獻是：采用變分分解模型將圖像分解為不同尺度的圖層，然后在每一個圖層中分別采用修復算法進行修補，這種分層修復的優勢是在匹配塊的挑選過程中，由于是在尺度大致相同的圖層中尋找匹配塊，這樣可以排除其他尺度信息的干擾，而搜尋到最優的匹配塊。算法主要步驟如下：

Step 1 用戶選擇需要修補的區域，找出修補區域邊界?；

Step 3 對每個圖層分別采用Criminisi算法進行修補；

Step 4 結合修補后的所有圖層得到最終的修復結果。

4 數值試驗

本章以不同的人工圖像和自然圖像為實驗對象驗證本文算法的有效性，所有實驗中，圖像分解的層數選擇為＝3。并且和傳統的Criminisi算法，以及2個改進Criminisi算法（文獻[14]和文獻[15]）進行了對比實驗，顯示本文模型對在圖像修復上的優勢。為了對修復效果做量化評價，本文采用峰值信噪比（peak signal to noise ratio，PSNR）和平均結構相似性指標（mean structural similarity，MSSIM）[23]來衡量修復效果，峰值信噪比定義為：

其中結構相似性指標（structural similarity，SSIM）定義為：

本文采用不同的人造圖像和自然圖像，人為地摳去部分區域為待修補區域，采用4種不同的算法對其進行修補。并將修補后結果與原圖進行比較，通過計算PSNR和MSSIM值衡量修補結果，展示本文算法的優勢。

圖4是對一幅人造圖像的修復結果。此圖像包括4種不同的紋理，各類紋理之間有明顯的邊界。待修補區域為圖像中心的一個方塊區域（白色區域），并且4種紋理都有缺損。此破損圖像中，4種紋理區域在圖像中心的交匯區域是修補的難點。圖5(c)和圖5(e)分別是傳統Criminisi算法和文獻[15]中算法的修復結果。明顯地，這2個修復結果中都出現了紋理延伸到其他區域的情況。圖5(d)和圖5(f)分別是文獻[14]中算法和本文算法的修復結果，可以看出這兩個修復結果都較好地重現了原圖的特征，基本上沒有出現紋理相互混疊的情況。但是通過PSNR和MSSIM值量化比較，本文算法的修復結果仍具有一定優勢。

圖5～圖7展示了4種算法對3幅自然圖像的修復結果。這3幅圖像含有豐富的紋理細節，人工選擇的待修補區域（白色區域）為細節豐富的、修復具有一定難度的大塊區域，圖5為墻面圖像，修補區域為部分墻面，此圖像的修補難點是墻縫的連通性和墻磚的整體性。圖6為Lena圖像，修補區域為帽檐、帽穗和Lena的部分前額，此圖像的修補難點是帽檐的連通性、額頭和帽子的交匯以及帽穗的完整性。圖7為秋天的樹林圖像，修補區域為綠色和紅色的樹林，此圖的修補難點是綠色樹林和紅色樹林的交匯。

圖4 人造圖像的修復結果

表1 不同算法修復結果的PSNR與MSSIM值

從實驗結果可以看出，Criminisi算法對于圖像中復雜結構處的修補存在較大缺陷，修復結果中產生了大量的“垃圾塊”。文獻[15]采用梯度項計算優先級，重點考慮了灰度劇烈變化區域，修復結果稍有改進，但是在修補區域的內部還是可能會出現“垃圾塊”。文獻[14]提出了基于結構張量的數據項。結構張量中的高斯卷積可以很好地刻畫結構的局部特征，所以文獻[14]算法可以在修復過程中更好地保持結構的一致性。本文算法由于采用了分層修復算法，通過在不同的圖層分別尋找匹配塊，排除了不同尺度特征的相互干擾，這樣可以較為容易地挑選出最優的匹配塊。從實驗結果也可以看出本文算法更好的修復了圖像的結構細節，很少出現“垃圾塊”，修復結果更符合人的主觀視覺。并且通過PSNR和MSSIM值量化比較（見表1），本文算法相對于其它3個算法更具有優勢。

圖5 墻面圖像的修復結果

Fig.5 The restoration results of wall image

圖6 Lena圖像的修復結果

Fig.6 The restoration results of Lena image

圖7 樹林圖像的修復結果

Fig.7 The restoration results of woods image

目標物體移除也是圖像修復算法的一個重要應用，本文也將分層修復算法應用到這個領域。圖8展示了4個算法對1幅自然圖像中目標物體移除實驗結果。移除目標為草地上的一棵樹。從實驗結果可以看出，Criminisi算法結果中，草地出現了不連續的現象，并且出現了“垃圾塊”，文獻[15]算法結果中也出現了大量的“垃圾塊”，本文算法和文獻[14]算法去除結果較好，但是仔細比較，本文移除結果更自然可信。

圖8 目標物體移除實驗結果

5 結論

在Criminisi圖像修復算法中，為了尋找最優的匹配塊，本文提出了一個分層Criminisi圖像修復算法。首先采用多尺度變分分解模型將圖像分解成一系列圖層之和，不同圖層包含不同尺度的圖像特征，而同一圖層包含幾乎相同的尺度特征。然后在每個圖層中分別采用Criminisi修復算法進行修補。由于同一圖層包含尺度大致相同的圖像特征，所以在匹配塊的搜索過程中，分層修復能較容易地搜尋到最優的匹配塊。最后結合分別修復的圖層，得到最終的修復結果。實驗結果表明，對于不同的人工圖像和自然圖像，本文模型都能取得較為滿意的修復結果。并且相對于傳統Criminisi算法以及文獻[14]和文獻[15]的修復算法具有一定優勢。另外說明本文的分層修復算法需要對多個圖層進行Criminisi算法修復，所以相對于傳統的Criminisi算法需要更多的計算時間。但是本文的分層修復算法也可以結合到目前一些快速的修復算法中，例如文獻[18]和文獻[24]中的快速修復算法，以提高修復效率。

[1] Imtiyaz M, Kumar A, Sreenivasulu G. Inpainting an Image based on Enhanced Resolution[J]., 2015, 6(1): 23-26.

[2] Guillemot C, Meur O L. Image Inpainting: Overview and Recent Advances[J]., 2014, 31(1):127-144.

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

ZHANG Hong-ying, PENG Qi-cong. A survey on digital image inpainting[J]., 2007, 12(1): 1-10．

[4] Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting[C]//27., 2000: 417-424.

[5] Shen J, Chan T F. Mathematical models for local nontexture inpaintings[J]., 2002, 62(3): 1019-1043.

[6] Chan T F, Shen J. Nontexture inpainting by curvature-driven diffusions[J]., 2001, 12(4): 436-449.

[7] Bildhauer M, Fuchs M. On Some Perturbations of the total variation image inpainting method. Part II: Relaxation and Dual Variational Formulation[J]., 2015, 205(2): 121-140.

[8] Yin X F, Duan J M, Pan Z K, et al. Nonlocal TV-L1 Inpainting Model and its Augmented Lagrangian Algorithm[C]//, 2014, 644: 4630-4636.

[9] Zhang Y, Pu Y F, Hu J R, et al. A Class of Fractional-Order Variational Image Inpainting Models[J]., 2012, 6(26):299-306.

[10] Li F, Zeng T. A New Algorithm Framework for Image Inpainting in Transform Domain[J]., 2016, 9(1): 24-51.

[11] Criminisi A, Pérez P, Toyama K. Region filling and object removal by exemplar-based image inpainting[J]., 2004, 13(9): 1200-1212.

[12] Zhou H, Zheng J. Adaptive patch size determination for patch-based image completion[C]//(), 2010 17, 2010: 421-424.

[13] Xu Z, Sun J. Image inpainting by patch propagation using patch sparsity[J]., 2010, 19(5): 1153-1165.

[14] Le Meur O, Gautier J, Guillemot C. Examplar-based inpainting based on local geometry[C]//(), 2011 18, 2011: 3401-3404.

[15] Huang H Y, Hsiao C N. A patch-based image inpainting based on structure consistence[C]/(), 2010, 2010: 165-170.

[16] 劉業妃, 王福龍, 奚祥艷, 等. 改進的Criminisi圖像修復算法[J]. 小型微型計算機系統, 2014(12): 2754-2758.

LIU Yefei, WANG Fulong, XI Xiangyan, et al. Improved algorithm for image inpainting based on texture synthesis[J]., 2014(12): 2754-2758.

[17] Liu Y, Caselles V. Exemplar-based image inpainting using multiscale graph cuts[J]., 2013, 22(5): 1699-1711.

[18] 張顯全, 高志卉. 一種塊匹配的圖像修復算法[J]. 光電子.激光, 2012, 23(4): 805-811.

ZHANG Xian-quan,GAO Zhi-hu. Image inpainting algorithm based on block matching[J]., 2012, 23(4): 805-811.

[19] 李尊, 吳謹, 劉勁. 數學形態學在Criminisi圖像修復算法中的應用[J]. 紅外技術, 2015, 37(7):574-578.

LI Zun, WU Jin, LIU Jin. The application of mathematical morphology in the criminisi algorithm of image inpainting[J]., 2015, 37(7): 574-578.

[20] Bertalmio M, Vese L, Sapiro G, et al. Simultaneous structure and texture image inpainting[J]., 2003, 12(8): 882-889.

[21] 唐利明, 黃大榮. 變分框架下的多尺度圖像恢復與重建[J]. 電子學報, 2013, 41(12):2353-2360.

TANG Liming, HANG Darong. Multiscale image restoration and reconstruction in the framework of variation[J]., 2013, 41(12):2353-2360.

[22] Chambolle A. An Algorithm for Total Variation Minimization and Applications[J]., 2004, 20(1/2):89-97.

[23] Wang Z, Bovik A C, Sheikh H R, et al. Image quality assessment: from error visibility to structural similarity[J]., 2004, 13(4):600-612.

[24] 李尊, 吳謹, 劉勁. 目標移除的Criminisi圖像修復算法[J].紅外技術, 2016, 38(1):28-32.

LI Zun, WU Jin, LIU Jin. Criminisi image restoration algorithm for object removal[J]., 2016, 38(1):28-32.

Multi-layer Criminisi Inpainting Algorithm for Non-Uniform Texture Images

PENG Chunhua1,2，TANG Liming1

(1.,,445000,; 2.,445000,)

To improve the inpainting quality of non-uniform texture images with extensive missing regions, we propose a multi-layer Criminisi image inpainting algorithm. First, a damaged image is decomposed into the sum of a few image layers using a multiscale variational decomposition model. The different image layers contain image features with different scales, and one layer contains features that are under a similar scale. Then, in each image layer, the Criminisi inpainting algorithm is applied. In the matching block search process, because one layer contains image features with roughly the same scale, the multi-layer inpainting algorithm can more easily locate the optimal matching block. Finally, combining the filled image layers, we obtain the final inpainting result. Experimental results on both synthetic and real non-uniform texture images demonstrate the effectiveness of the proposed algorithm.

image inpainting，Criminisi algorithm，variational image decomposition

TP391

A

1001-8891(2017)09-0814-10

2016-08-24；

2017-08-24.

彭春華（1979-），女，碩士研究生，主要研究方向為數字圖像處理。

唐利明(1978-)，男，博士，副教授，主要從事變分圖像修復、分割等方面研究。E-mail：tlmcs78@foxmail.com。

國家自然科學基金（61561019）；湖北省自然科學基金（2015CFB262）；國家科技支撐計劃課題（2015BAK27B03）；湖北民族學院博士啟動基金（MY2015B001）。