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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 圖像區(qū)域分割

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

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

圖3 區(qū)域分割圖

2.2 均方誤差改進(jìn)

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

2.2.1 顏色差異

2.2.2 紋理差異

2.2.3 曲線(xiàn)特征差異

除了顏色和紋理差異，本文考慮樣本塊曲線(xiàn)特征差異。通過(guò)上述區(qū)域分割圖，可以得到的曲線(xiàn)信息圖，從而進(jìn)行曲線(xiàn)級(jí)別的匹配，衡量?jī)蓚€(gè)樣本塊的曲線(xiàn)特征差異。

其中為對(duì)應(yīng)曲線(xiàn)的數(shù)目。

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

2.3 本文算法步驟

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

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

3.1 實(shí)驗(yàn)修復(fù)效果對(duì)比

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

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

圖4 本文算法步驟

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

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

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

圖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í)行效率對(duì)比

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

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

4 總結(jié)

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

[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é)合圖像細(xì)節(jié)特征的全局優(yōu)化紋理合成[J].計(jì)算機(jī)學(xué)報(bào), 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]. 中國(guó)圖像圖形學(xué)報(bào)，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

國(guó)家自然科學(xué)基金項(xiàng)目(60771065)

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

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

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

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