李光耀，耿瑞全，譚云蘭2,，肖 莽

基于區(qū)域分割和均方誤差改進的圖像修復(fù)算法

*李光耀1，耿瑞全1，譚云蘭2,1，肖 莽1

（1.同濟大學(xué)電子與信息工程學(xué)院，上海 201804；2. 井岡山大學(xué)電子與信息工程學(xué)院，江西，吉安 343009)

基于樣本塊的Criminisi圖像修復(fù)算法在搜索匹配塊時，使用全局搜索并用均方誤差（sum of squared differences）來衡量樣本塊差異。該方法存在搜索范圍過大，效率較低，僅考慮顏色的差異，容易導(dǎo)致修復(fù)結(jié)果邊界錯位等不足，本文提出了一種基于區(qū)域分割和均方誤差改進的圖像修復(fù)算法。為了提高樣本塊匹配速度，先采用區(qū)域分割法分割整個圖像區(qū)域，使待修復(fù)樣本塊只在對應(yīng)區(qū)域內(nèi)搜索。在比較樣本塊差異時，本文算法對顏色差異、紋理差異、曲線特征差異進行了加權(quán)綜合，從而保證了修復(fù)后圖像在顏色和紋理上均與已知區(qū)域保持一致，解決了Criminisi算法效率低且容易出錯等問題。實驗結(jié)果表明本文算法修復(fù)結(jié)果在執(zhí)行效率、視覺效果上要比Criminisi算法好。

圖像修復(fù)；區(qū)域分割；均方誤差；紋理合成

0 引言

圖像修復(fù)是計算機圖形學(xué)中的一個研究熱點，具有廣泛的應(yīng)用前景。圖像修復(fù)是為了讓破損的圖像恢復(fù)視覺上“合理”而且“完整”[1]。從視覺心理學(xué)出發(fā)，向內(nèi)按一定的方向進行擴展延伸、連接邊界、合成紋理，以達到視覺上的連通性和一致性。其目的是研究和解決如何更好地實現(xiàn)檢測圖像上的受損部分，并根據(jù)受損圖像周圍的有效信息自動進行恢復(fù)。從數(shù)學(xué)角度來看，圖像修復(fù)就是要根據(jù)待修補區(qū)域周圍的信息將圖像填充到待修補區(qū)域中。如圖1所示，設(shè)為一副圖像，為信息丟失的待修復(fù)區(qū)域，為圖像中完好的可利用的圖像部分。圖像修復(fù)的問題即用已知信息填充區(qū)域，使整幅圖像取得良好的視覺效果，圖1（c）為修復(fù)后的結(jié)果。

圖1 (a) 原圖，(b) 修復(fù)掩膜圖（黑色部分為修復(fù)區(qū)域），(c) 圖修復(fù)結(jié)果。

圖像修復(fù)算法大體分為兩大類，基于變分偏微分方程的算法和基于紋理合成算法?；诩y理合成算法[3]把待修復(fù)圖像的已知區(qū)域作為紋理樣本，對于丟失區(qū)域基于紋理合成生成新的圖像塊，以解決基于變分偏微分方程修復(fù)算法出現(xiàn)模糊的問題?；诩y理合成的算法是對已知圖像塊進行采樣，對丟失的像素及相鄰像素組成的塊從樣本中查找與之最相似的匹配塊來修補，該迭代過程反復(fù)進行直到所有丟失區(qū)域被修復(fù)完。但是這種方法很難保持圖像的結(jié)構(gòu)信息，Criminisi等人[4]從人工依據(jù)圖像結(jié)構(gòu)信息依次修復(fù)圖像中得到啟發(fā)，即對于修復(fù)圖像中的每個部分的修復(fù)先后順序非常關(guān)鍵，因此對待修復(fù)區(qū)域邊界上的像素計算其修復(fù)優(yōu)先級，從而確定其修復(fù)順序，使得圖像修復(fù)質(zhì)量得到質(zhì)的提升，該算法在解決圖像修復(fù)問題中具有里程碑意義。隨后，研究人員基于Criminisi算法提出了多種改進算法。Tang等人[5]通過減少最佳匹配塊的搜索范圍來加快算法的運行，同時改進了匹配準則來避免計算錯誤。Nie等人[6]對Criminisi算法進行改進，對構(gòu)成優(yōu)先權(quán)的置信項和數(shù)據(jù)項進行了歸一化，這樣保證了兩者對優(yōu)先權(quán)的影響程度一致，同時修正了塊之間差異的計算方法。Wong等人[7]采用線性加權(quán)的方式合成最佳匹配塊填充待修復(fù)塊。肖春霞等人[8]提出了一種結(jié)合圖像細節(jié)特征的全局優(yōu)化紋理合成算法，利用非線性分解方法獲取紋理細節(jié)作為特征圖，將其作為紋理圖像一個新的信息通道來引導(dǎo)紋理合成。Xu等人[9]借助稀疏表示的概念指導(dǎo)修復(fù)順序并合成最佳匹配塊，大大提高了修復(fù)質(zhì)量。劉建明等人[10]則采用組合樣本塊匹配度量來加強結(jié)構(gòu)的傳播也得到不錯的效果。

本文分析了Criminisi算法搜索效率和修復(fù)效果方面的不足，本文提出了一種基于區(qū)域分割和均方誤差改進的圖像修復(fù)算法。

1 Criminisi基于樣本塊紋理合成修復(fù)算法

Criminisi等[4]采用一種基于樣本塊的紋理合成修補算法，其實質(zhì)是使用紋理合成的方法來移除圖像中的物體，取得了較好的修復(fù)效果。Criminisi算法由優(yōu)先權(quán)計算、搜索和復(fù)制3步組成。具體方法如下：

其中：為的信心因子項，是的數(shù)據(jù)因子項，計算方法如下：

圖2 優(yōu)先權(quán)符號注釋圖

3）復(fù)制：將最佳匹配塊復(fù)制到中處于待修復(fù)區(qū)域內(nèi)的部分。

Criminisi算法由于引進了修復(fù)次序優(yōu)先權(quán)，算法取得了很好的修復(fù)效果。但同時由于使用整個塊的復(fù)制填充而不是單個像素點，算法的速度相對更快，仍存在一些不足。首先，搜索時在整個已知區(qū)域內(nèi)搜索，該過程非常耗時。其次在搜索最佳相似塊時使用均方誤差（SSD）來衡量樣本塊差異，僅考慮了兩個樣本塊之間顏色差異，修復(fù)結(jié)果有時存在邊界錯位的情況。

2 區(qū)域分割和均方誤差改進的圖像修復(fù)算法

針對Criminisi算法上述兩方面的不足，本文首先分割整個圖像區(qū)域，使待修復(fù)樣本塊只在對應(yīng)區(qū)域內(nèi)搜索，提高了算法的執(zhí)行效率；同時在比較樣本塊差異時，對顏色差異、紋理差異、曲線特征差異進行了加權(quán)綜合，彌補了單純考慮顏色誤差的不足，保證了修復(fù)結(jié)果在顏色和紋理曲線上的一致性。

2.1 圖像區(qū)域分割

Criminisi算法搜索樣本塊時采用全局搜索，樣本量巨大，非常耗時。本文首先對待修復(fù)圖進行區(qū)域分割，搜索匹配塊時只在對應(yīng)區(qū)域，而不是全局搜索，提高了算法的執(zhí)行效率。

在紋理合成的過程，塊搜索被限制在當前待修復(fù)樣本塊覆蓋的相關(guān)區(qū)域中：

圖3 區(qū)域分割圖

2.2 均方誤差改進

Criminisi算法在搜索最佳匹配塊時使用均方誤差SSD，只考慮了兩個樣本塊之間顏色差異，導(dǎo)致修復(fù)結(jié)果有時存在邊界錯位的情況。受基于內(nèi)容的圖像檢索（CBIR）的啟發(fā)，在搜索最佳匹配塊時，本文使用在比較樣本快差異時，除了顏色信息，還包含紋理、曲線特征方面的差異，其中顏色差異描述了兩個樣本塊局部顏色成分差異，紋理差異描述了兩個樣本塊的局部灰度級成分差異，而曲線特征描述了顯著結(jié)構(gòu)的幾何差異性，這三個方面能簡潔且有效地描述樣本塊之間的差異，分別在下面論述。

2.2.1 顏色差異

2.2.2 紋理差異

2.2.3 曲線特征差異

除了顏色和紋理差異，本文考慮樣本塊曲線特征差異。通過上述區(qū)域分割圖，可以得到的曲線信息圖，從而進行曲線級別的匹配，衡量兩個樣本塊的曲線特征差異。

其中為對應(yīng)曲線的數(shù)目。

綜合式（7）（8）（10），改進的均方誤差綜合加權(quán)計算公式如下：

2.3 本文算法步驟

本文提出了一種基于區(qū)域分割和均方誤差改進的圖像修復(fù)算法。主要分成兩個步驟：區(qū)域分割和最佳匹配塊的生成。初始時，人工選擇帶修復(fù)區(qū)域，算法流程見圖4。其中從帶修復(fù)塊相關(guān)區(qū)域中選擇最相似塊步驟中使用改進的均方誤差。

3 實驗結(jié)果與分析

3.1 實驗修復(fù)效果對比

本實驗首先使用區(qū)域分割算法得到分割圖和曲線信息圖，如圖5、圖6。其中：圖5大小416*316，算法耗時1.05 s，圖6大小為206*308，耗時0.37 s。

本實驗選取了一些比較的圖像，樣本塊大小設(shè)定為9*9。圖像的修復(fù)結(jié)果以盡可能合理為目的，而非與原圖像一致。圖7-9為本文算法和Criminisi算法修復(fù)結(jié)果比較。圖7：（c）中修復(fù)結(jié)果紅色圈出的部分海平面存在錯位，藍天部分由于未對搜索區(qū)域進行限制，結(jié)果中存在大量白云，不夠合理。（d）中修復(fù)結(jié)果存在少量瑕疵，但相比較更為合理；圖8：（c）中修復(fù)結(jié)果的河岸交界處出現(xiàn)了多余塊，屋頂線結(jié)構(gòu)也出現(xiàn)斷裂，這些在（d）中都得到了改善；圖9：（c）中紅圈內(nèi)修復(fù)結(jié)果應(yīng)該為山和樹木的部分被填充為房屋，而（d）中更加合理。

圖4 本文算法步驟

綜上，Criminisi 算法的修復(fù)結(jié)果存在明顯的邊界不連續(xù)和錯位現(xiàn)象，同時存在大量的冗余圖像塊。而使用本文算法由于限制了搜索區(qū)域，改進了均方誤差，修復(fù)結(jié)果相對較好。

圖5 (a)待修復(fù)圖 (b)區(qū)域分割圖 (c)曲線信息圖

圖6 (a)待修復(fù)圖 (b)區(qū)域分割圖 (c)曲線信息圖

圖7 (a)原圖 (b)待修復(fù)圖 (c) Criminisi 修復(fù)結(jié)果 (d)本文算法修復(fù)結(jié)果

圖8 (a)原圖 (b)待修復(fù)圖 (c) Criminisi 修復(fù)結(jié)果 (d)本文算法修復(fù)結(jié)果

圖9 (a)原圖 (b)待修復(fù)圖 (c) Criminisi 修復(fù)結(jié)果 (d)本文算法修復(fù)結(jié)果

3.2 執(zhí)行效率對比

表1對Criminisi算法和本文算法作具體的比較，表中數(shù)據(jù)表明本文算法由于限制了搜索區(qū)域，顯著地縮短了修復(fù)時間，提高了圖像修復(fù)的效率。

表1 Criminisi算法和本文算法執(zhí)行效率比較

4 總結(jié)

本文提出了一種基于區(qū)域分割和均方誤差改進的圖像修復(fù)算法。該方法在比較樣本塊相差異的時候不僅考慮了它們之間的顏色差異，而且也整合了樣本塊間的紋理、曲線特征差異，保證了修復(fù)后圖像在顏色和紋理上均與已知區(qū)域保持一致。同時采用區(qū)域分割，在搜索匹配塊時只在對應(yīng)區(qū)域內(nèi)搜索，提高了算法的執(zhí)行效率。實驗結(jié)果表明，本文算法修復(fù)結(jié)果在執(zhí)行效率、視覺效果上要比Criminisi算法好。本文算法也存在著其他不足：部分實驗結(jié)果存在少量冗余圖像塊；算法對區(qū)域分割結(jié)果比較依賴，因此，如何有效地提高區(qū)域分割的質(zhì)量、加強綜合系數(shù)的感知，從而改進修復(fù)的效果是今后進一步研究的方向。

[1] Zhang H Y, Peng Q C. A survey on digital image inpainting[J]. Journal of Image and Graphics, 2007; 12(1): 1-10.

[2] Bertalmio M, Bertozzi AL, Ballester C, etal. Image inpainting [C]. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New Orleans, Louisiana, USA: ACM Press, 2000: 417-424.

[3] Efros A, Leung TK. Texture synthesis by non-parametric sampling [C]. IEEE International Conference on Computer Vision, Greece, 1999: 1033-1038.

[4] Criminisi A, Perez P, Toyama K. Object removal by exemplar-based inpainting[C].In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2003.

[5] Tang F, Ying Y T, Wang J, Peng Q S. A Novel Texture Synthesis Based Algorithm for Object Removal in Photographs [C]. In Proceedings of Ninth Asian Computing Science Conference, Chiang Mai, Thailand, 2004: 248-258.

[6] Nie D L M, Xiao S. Similarity based image inpainting method [C]. Proceedings of 12th international Conference on Multi-Media Modeling, Beijing: IEEE, 2006: 344-347.

[7] Wong A, Orchard J. A nonlocal-means approach to exemplar-based inpainting [C]. Proceedings of 15th IEEE International Conference on Image Processing, California: IEEE, 2008: 2600-2603.

[8] 肖春霞, 黃志勇, 聶勇偉, 等. 結(jié)合圖像細節(jié)特征的全局優(yōu)化紋理合成[J].計算機學(xué)報, 2009,32(6): 1196-1205.]

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

[10] 劉建明，魯東明.采用加權(quán)優(yōu)化的圖像修復(fù)[J]. 中國圖像圖形學(xué)報，2011,16(4):528-532.

[11] Liu M, Tuzel O, Ramalingam S, Chellappa R. Entropy rate superpixel segmentation[C]. CVPR, 2011.

[12] Chen J Q, Pappas T N, Mojsilovic A, et al. Adaptive perceptual color-texture image segmentation[J]. IEEE Trans, 2005，14 (10)： 1524-1536.

[13] Varma M, Zisserman A. Statistical approach to material classification using image patch Exemplars[J]. IEEE Trans. Pattern Anal. Machine Intell, 2009,13(11): 2032-2047.

Based region segmentation and improved sum of squared differences image completion algorithm

*LI Guang-yao1, GENG Rui-quan1, TAN Yun-lan2,1, XIAO Mang1

(1. College of Electronic Information and Engineering, Tongji University, Shanghai 201804, China; 2．School of Electronic Information and Engineering，Jinggangshan University，Ji’an，Jiangxi 343009，China)

Image inpainting is one of important and challenging research topics in computer graphics, video processing, and computer vision. It provides a strong tool for the reuse of captured images and photos. It also shows extensive applications in cultural heritage protection, special visual effects, image and video editing and virtual reality. The traditional Criminisi based patch image completion algorithms only consider the intensity difference when computing the difference within patches and search the most similar exemplar patches in the source region of image, the computation is too large. A new difference measure for completion is presented. This measure considers the intensity difference, texture difference and curve difference when computing the difference within patches. It successfully overcomes the drawbacks the general intensity difference method has, ensuring the content continuity within the textures and retaining perceptual coherence in synthesized texture and inpainted image. The experiment shows the result inpainted images using our algorithm are better than Criminisi algorithm, and the repair time also has a considerable decrease.

image completion; region segmentation; sum of squared differences; texture synthesis

O159.1

A

10.3969/j.issn.1674-8085.2013.06.010

1674-8085(2013)06-0044-07

2013-10-08；

2013-10-15

國家自然科學(xué)基金項目(60771065)

*李光耀(1965-），男，安徽安慶人，教授，博導(dǎo)，主要從事大規(guī)模城市建模與仿真、圖形圖像處理研究(E-mail: lgy@#edu.cn)；

耿瑞全(1991-），男，安徽蚌埠人，碩士生，主要從事圖形圖像處理，機器學(xué)習(xí)等研究(E-mail: 871342796@qq.com);

譚云蘭(1972-），女，江西新干人，副教授，博士生，主要從事虛擬現(xiàn)實,圖像處理研究(E-mail:tanyunlan@163.com);

肖 莽(1982-），男，江西吉安人，博士生，主要從事圖像處理研究(E-mail:122018922@qq.com).