Please wait a minute...
J4  2011, Vol. 45 Issue (2): 247-252    DOI: 10.3785/j.issn.1008-973X.2011.02.009
Global optimization based image inpainting and
its implementation on GPU
LIU Jian-ming1,2, LU Dong-ming1, GE Rong1
1.College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China; 2. Department of
Computer and Information Engineering, Jiangxi Normal University, Nanchang 330022,China
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      


Since greedy image inpainting algorithms might cause visual inconsistency, and global optimization based inpainting algorithms didn’t consider structure information, a new fast image inpainting algorithm based on global optimization is proposed. The image inpainting was formulated as a global optimization problem by defining an improved energy function, and a non-local mean based label pruning algorithm was adopted to cut down the number of labels for each node so as to reduce the complexity of the optimization algorithm significantly. Graphic processing unit (GPU) was used to further improve the computing speed. Compared with greedy synthesis and global optimization based image inpainting methods, the proposed approach not only avoids the inter-block discontinuity but also achieves better efficiency.

Published: 17 March 2011
CLC:  TP 391.41  
Cite this article:

LIU Jian-ming, LU Dong-ming, GE Rong. Global optimization based image inpainting and
its implementation on GPU. J4, 2011, 45(2): 247-252.

URL:     OR



[1] BERTALMIO M, BERTOZZI A L, BALLESTER C, et al. Image inpainting [C]∥Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New Orleans, Louisiana, USA: ACM, 2000: 417-424.
[2] CHAN T F, SHEN J. Mathematical models for local nontexture inpaintings [J]. SIAM Journal on Applied Mathematics. 2002, 62 (3): 1019-1043.
[3] CHAN T F, SHEN J. Nontexture inpainting by curvaturedriven diffusions [J]. Visual Communication and Image Representation, 2001, 12(4): 436-449.
[4] ESEDOGLU S, SHEN J. Digital inpainting based on the mumford–shah–euler image model [J]. European Journal of Applied Mathematics, 2002, 13(4): 353-370.
[5] 侯正信,何宇清,许微.一种快速的图像修复算法[J].中国图象图形学报.2007,21(10): 1909-1912.
HOU Zhengxin, HE Yuqing, XU Wei. A fast algorithm of image inpainting[J].Journal of Image and Graphics,2007,21(10): 1909-1912
[6] 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.
[7] WU J, RUAN Q. Object removal by cross isophotes exemplarbased inpainting [C]∥Proceedings of the 18th International Conference on Pattern Recognition. Hong Kong: IEEE Computer Society, 2006,3: 810-813.
[8] GROVER S, MITTAL A, GUPTA S, et al. A unified approach for digital image inpainting using bounded search space [J]. International Journal on Graphics, Vision and Image Processing, 5(6): 17-24.
[9] SUN J, SHUM H Y. Image completion with structure propagation [J]. ACM Transactions on Graphics, 2005, 24(3): 861 -868.
[10] KOMODAKIS N, TZIRITAS G. Image completion using efficient belief propagation via priority scheduling and dynamic pruning [J]. IEEE Transactions on Image Processing. 2007, 16(11): 2649-2661.
[11] HUANG T, CHEN S, LIU J, et al. Image inpainting by global structure and texture propagation [C]∥ Proceedings of the 15th international conference on Multimedia. Augsburg, Germany: ACM, 2007, 901: 517-520.
[12] HAYS J, EFROS A A. Scene completion using millions of photographs [J]. ACM Transactions on Graphics, 2007,26(3): 4-10
[13] FELZENSZWALB P F, HUTTENLOCHER D P. Efficient belief propagation for early vision [J]. International Journal of Computer Vision. 2006, 70(1): 41-54.
[14] BUADES A, COLL B, MOREL J M. A nonlocal algorithm for image denoising [C]∥Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, CA, USA: IEEE Computer Society, 2005, 2: 60-65.
[15] NVIDIA C. Compute unified device architecture programming guide [M]. Santa Clara, CA: Nvidia Coporation, 2007: 7-11.

[1] YANH Yu-ting, SHI Yu-hui, XIA Shun-ren. Discussion mechanism based brain storm optimization algorithm[J]. J4, 2013, 47(10): 1705-1711.
[2] ZHU Xiao-en, HAO Xin, XIA Shun-ren. Feature selection algorithm based on Levy flight[J]. J4, 2013, 47(4): 638-643.
[3] SON Chang-il , ZHEN Shuai, XIA Shun-ren. Attractor range based affine registration of multi-modal
brain magnetic resonance images
[J]. J4, 2012, 46(9): 1722-1728.
[4] XIE Di, TONG Ruo-feng, TANG Min, FENG Yang. Distinguishable method for video fire detection[J]. J4, 2012, 46(4): 698-704.
[5] DAI Yuan-ming, WEI Wei, LIN Yi-ning. An improved Mean-shift tracking algorithm based on
color and texture feature
[J]. J4, 2012, 46(2): 212-217.
[6] Qi lei, JIN Wen-guang, GENG Wei-dong. Human motion capture using wireless inertial sensors[J]. J4, 2012, 46(2): 280-285.
[7] LIU Chen-bin, PAN Ying, ZHANG Hai-shi, HUANG Feng-ping, XIA Shun-ren. Detecting MGMT expression status of glioma with magnetic
resonance image
[J]. J4, 2012, 46(1): 170-176.
[8] QIAN Cheng, ZHANG San-yuan. Weighted incremental subspace learning algorithm
suitable for object tracking
[J]. J4, 2011, 45(12): 2240-2246.
[9] LV Gu-lai,LI Jian-ping,LI Qiang,YU Li-xing,ZHU Song-ming,LOU Jian-zhong. Method for rootstock position recognition based on machine vision[J]. J4, 2011, 45(10): 1766-1770.
[10] CAO Ying, HAO Xin, ZHU Xiao-en, XIA Shun-ren. Mammographic mass segmentation algorithm based on
automatic random walks
[J]. J4, 2011, 45(10): 1753-1760.
[11] LAI Xiao-bo , ZHU Shi-qiang. Mutual information based non-parametric
 transform stereo matching algorithm
[J]. J4, 2011, 45(9): 1636-1642.
[12] WANG Jin-de, SHOU Li-dan, LI Xiao-yan, CHEN Gang. Bundling features with multiple segmentations for
object-based image retrieval
[J]. J4, 2011, 45(2): 259-266.
[13] LIANG Wen-feng, XIANG Zhi-yu. Algorithm of robust object tracking using PTZ camera[J]. J4, 2011, 45(1): 59-63.
[14] ZHAN Jiang-tao, LIU Qiang, CHAI Chun-lei. Facial feature tracking using three-dimensional model and
Gabor wavelet
[J]. J4, 2011, 45(1): 30-36.
[15] SONG Kun-po, XIA Shun-ren, XU Qing. Algorithm considering correlation of wavelet coefficients for
ultrasound image denoising
[J]. J4, 2010, 44(11): 2203-2208.