基于分形的数字图像修复算法研究
|
摘要
数字图像修复是当前图形图像处理的研究热点,在文物保护、影视特技制作、虚拟实现、多余物剔除等方面有重要的应用价值,数字图像修复是指用一定的算法来对指定区域缺损数据进行填充的过程,包括受损图像恢复,剔除或者取代图像中指定对象,达到图像复原或者接近原图像的视觉效果。其基本原理是利用受损区域和区域边界图像的相关信息来修复受损图像。
从数学角度来说,图像修复问题属于病态问题,因为没有足够的信息可以保证能唯一正确地恢复被损坏部分,其修复值就是在已知周围像素扩散的基础上对原图像像素值的近似。通常,图像修复在视觉上要达到的效果是:如果观察者事先没有见过原始的图像,那他就分辨不出来图像是否被修复过。实际上各种算法的修复结果基本能够满足视觉要求,但在算法复杂度,适用范围等方面有较大差异。
本文首先将图像分解为结构和纹理两部分,对于结构部分,本文采用成熟的基于PDE的图像修复技术;对于纹理部分,本文采用分形维度作为纹理的主要特征,用分形纹理合成的方法进行修复。
由于纹理和结构并行进行修复,使得本文算法的修复速度大大提高,同时克服了原有的图像修复技术在边界,拐角点不连续等缺点。实验结果表明,本算法具有复杂度低,计算速度快、修复效率高等显著特点。
Digital Image inpainting is a research focus of the graphic image processing, it have important value in the protection of cultural relics, video graphics production, virtual realization and the surplus removed, digital image inpainting refers to using a certain algorithms to filling the data into damage areas, including damage image restoration, remove or replace designated part of the image. Achieve visual effects as original image or close to original image. Its basic principle is to use correlation information of damaged regional and it’s edge to restoration damaged image.
From the mathematical point of view, image inpainting is a sick problem, because not enough information is available to ensure that only correct and restore the damaged part of its restoration is known around the proliferation of pixels on the basis of the original image pixel approximation, we therefore propose the algorithm is to meet certain false the conditions set down problem. Usually, image repair in order to achieve the visual effect is: If the observers had no seen the original image, which he resolved not by the image should be restored. Virtually all the inpainting algorithm results to meet the visual requirements, but the complexity of the algorithm, and the scope have a greater difference.
This paper will decomposed image into structure and texture firstly ,for the structure component, the mature inapainting techniques based on PDE is used. for the texture component, texture synthesis technology is used for restoration.
The texture and structure parallel to inapaingting, making the speed of inpingting is enhanced fast when using the algorithm proposed in this paper , the defect of previous algorithm such as not continuous at boundary or corner is overcomed. The experimental results indicate that this algorithm have some notable feature as low algorithm complexity high efficiency ,high calculation speed, and so on.
从数学角度来说,图像修复问题属于病态问题,因为没有足够的信息可以保证能唯一正确地恢复被损坏部分,其修复值就是在已知周围像素扩散的基础上对原图像像素值的近似。通常,图像修复在视觉上要达到的效果是:如果观察者事先没有见过原始的图像,那他就分辨不出来图像是否被修复过。实际上各种算法的修复结果基本能够满足视觉要求,但在算法复杂度,适用范围等方面有较大差异。
本文首先将图像分解为结构和纹理两部分,对于结构部分,本文采用成熟的基于PDE的图像修复技术;对于纹理部分,本文采用分形维度作为纹理的主要特征,用分形纹理合成的方法进行修复。
由于纹理和结构并行进行修复,使得本文算法的修复速度大大提高,同时克服了原有的图像修复技术在边界,拐角点不连续等缺点。实验结果表明,本算法具有复杂度低,计算速度快、修复效率高等显著特点。
Digital Image inpainting is a research focus of the graphic image processing, it have important value in the protection of cultural relics, video graphics production, virtual realization and the surplus removed, digital image inpainting refers to using a certain algorithms to filling the data into damage areas, including damage image restoration, remove or replace designated part of the image. Achieve visual effects as original image or close to original image. Its basic principle is to use correlation information of damaged regional and it’s edge to restoration damaged image.
From the mathematical point of view, image inpainting is a sick problem, because not enough information is available to ensure that only correct and restore the damaged part of its restoration is known around the proliferation of pixels on the basis of the original image pixel approximation, we therefore propose the algorithm is to meet certain false the conditions set down problem. Usually, image repair in order to achieve the visual effect is: If the observers had no seen the original image, which he resolved not by the image should be restored. Virtually all the inpainting algorithm results to meet the visual requirements, but the complexity of the algorithm, and the scope have a greater difference.
This paper will decomposed image into structure and texture firstly ,for the structure component, the mature inapainting techniques based on PDE is used. for the texture component, texture synthesis technology is used for restoration.
The texture and structure parallel to inapaingting, making the speed of inpingting is enhanced fast when using the algorithm proposed in this paper , the defect of previous algorithm such as not continuous at boundary or corner is overcomed. The experimental results indicate that this algorithm have some notable feature as low algorithm complexity high efficiency ,high calculation speed, and so on.
引文
1. 姚敏 《数字图像处理》 (第一版),机械工业出版社 2003 年
2.孙霞 吴自勤 《分形原理及其应用》(第一版)中国科学技术大学出版社 2003 年
3.A.C.kokaram “motion picture restoration”, ph.D, thesis,Department of Engineering university of Cambridge ,1993
4. A. Hirani and T. Totsuka. Combining Frequency and spatialdomain information for fast interactive image noise removal. Computer Graphics, pp. 269-276, SIGGRAPH 96, 1996.
5. M. Nitzberg, D. Mumford, and T. Shiota, Filtering, Segmentation,and Depth, Springer-Verlag, Berlin, 1993.
6.S.masnou and J.morel,”levellines,based disocclusion”,presented at the 5th IEEE Int ,conf, image processing ,Chicago, IL,oct,4-7 1989
7. T. Chan and J. Shen, “Mathematical models for local deterministic inpaintings,” UCLA CAM TR 00-11, March 2000.
8. M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester,“Image inpainting,” Computer Graphics (SIGGRAPH 2000), pp. 417–424, July 2000.
9.chang E. “An image coding reconstruct scheme for mobile computing” proceedings of 5th IDMS. Springer-Verlag LNCS 1483,1998: 5-10
10.Rudin L, Osher S,Faterni E.”Nonlinear total variation based noise removal algorithms” [J]. Physica D,1992,60(1-4);259-268
11.Chan T F,Shen J H “Mathematical model for local non-texture inpainting”[J] SIAM Journal of Applied Mathematics,2001,62(3):564-592
12. Chan T F,Shen J H “non-texture inpainting by curature-driven diffusions”[J] Journal of Vision communication and Image Representation,2001,12(4):436-449
13. Jian Sun Lu Yuan “image completion with structure propagation” 2005
14. Luminita A.Vese and Stanley J.Osher ” Modeling Textures with Total Variation Minimization and Oscillating Patterns in Image Processing” [J] Journal of Scientific computing ,2003 ,19(1),553-572,
15. Harsh Potlapalli and Ren C.Luo “fractal-based classification of natural textures” IEEE transanctions on industrial electronics,vol.45.NO.1 1998
17. Xie H , Wang J A. Direct Fractal Measurement of Fracture Surfaces [ J ] . Int J Solids & Structures ,1999 , 36 : 3073 - 3084.
18.聂笃宪,曾文曲 文有为 《分形维数计算方法研究》 [J] 微机发展 第 4 卷 9 期,2004年 9 月。
19.Mandelbrot B. Les objects fractal : forme , hazard et dimesion[M] . Paris :Flammarion ,1995.
20. A Cisi, P Perez, K Toyama. Object Removal by Exemp lar2based npainting[C]. Proceedings of Euro, Graph, 2003.
21.戴磊 《基于纹理合成的图像复原算法研究》 浙江大学硕士论文 2005 年 3 月
22.张跃飞 《基于稀疏分解的图像压缩》西南交通大学硕士论文 2006 年 1 月
23. Mallat S, Zhang Z. Matching pursuit with time-frequency dictionaries[JJ, IEEE Trans. On Signal Processing, 1993, 41(12 ) :3397-3415.
24. Chen S S, D L Donoho,M A Saunders. Atomic decompositiom by basis pursuit[J]. SIAM J. Sci Comp, 1999, 20(1): 33-61.
25.David L. Donoho, Member, IEEE, and Xiaoming Huo. Uncertainty Principles and Ideal Atomic Decomposition[J]. IEEE Transactions on Information Theroy, 2001,47(11):2845-2862.
26.Joel A. Tropp, Greed is Good: Algorithmic Results for Sparse Approximation [J]. IEEE Transactions on Information Theroy, 2004,50(10):2231-2242.
27.Gribonval, Remi; Nielsen, Morten. Sparse Representations in Unions of Bases[J]. IEEE Transactions on Information Theory, 2003,49 (12):3320-3325.
28.A.Criminisi, Perez,K.Toyama. Object Removal by exemplar-based inpainting IEEE.Conference on computer vision and pattern recognition 2003,
29.Marcelo Bertalmio, Luminita Vese, Guillermo Sapiro Simultaneous Structure and Texture Image Inpainting IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 12, NO. 8, AUGUST 2003
2.孙霞 吴自勤 《分形原理及其应用》(第一版)中国科学技术大学出版社 2003 年
3.A.C.kokaram “motion picture restoration”, ph.D, thesis,Department of Engineering university of Cambridge ,1993
4. A. Hirani and T. Totsuka. Combining Frequency and spatialdomain information for fast interactive image noise removal. Computer Graphics, pp. 269-276, SIGGRAPH 96, 1996.
5. M. Nitzberg, D. Mumford, and T. Shiota, Filtering, Segmentation,and Depth, Springer-Verlag, Berlin, 1993.
6.S.masnou and J.morel,”levellines,based disocclusion”,presented at the 5th IEEE Int ,conf, image processing ,Chicago, IL,oct,4-7 1989
7. T. Chan and J. Shen, “Mathematical models for local deterministic inpaintings,” UCLA CAM TR 00-11, March 2000.
8. M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester,“Image inpainting,” Computer Graphics (SIGGRAPH 2000), pp. 417–424, July 2000.
9.chang E. “An image coding reconstruct scheme for mobile computing” proceedings of 5th IDMS. Springer-Verlag LNCS 1483,1998: 5-10
10.Rudin L, Osher S,Faterni E.”Nonlinear total variation based noise removal algorithms” [J]. Physica D,1992,60(1-4);259-268
11.Chan T F,Shen J H “Mathematical model for local non-texture inpainting”[J] SIAM Journal of Applied Mathematics,2001,62(3):564-592
12. Chan T F,Shen J H “non-texture inpainting by curature-driven diffusions”[J] Journal of Vision communication and Image Representation,2001,12(4):436-449
13. Jian Sun Lu Yuan “image completion with structure propagation” 2005
14. Luminita A.Vese and Stanley J.Osher ” Modeling Textures with Total Variation Minimization and Oscillating Patterns in Image Processing” [J] Journal of Scientific computing ,2003 ,19(1),553-572,
15. Harsh Potlapalli and Ren C.Luo “fractal-based classification of natural textures” IEEE transanctions on industrial electronics,vol.45.NO.1 1998
17. Xie H , Wang J A. Direct Fractal Measurement of Fracture Surfaces [ J ] . Int J Solids & Structures ,1999 , 36 : 3073 - 3084.
18.聂笃宪,曾文曲 文有为 《分形维数计算方法研究》 [J] 微机发展 第 4 卷 9 期,2004年 9 月。
19.Mandelbrot B. Les objects fractal : forme , hazard et dimesion[M] . Paris :Flammarion ,1995.
20. A Cisi, P Perez, K Toyama. Object Removal by Exemp lar2based npainting[C]. Proceedings of Euro, Graph, 2003.
21.戴磊 《基于纹理合成的图像复原算法研究》 浙江大学硕士论文 2005 年 3 月
22.张跃飞 《基于稀疏分解的图像压缩》西南交通大学硕士论文 2006 年 1 月
23. Mallat S, Zhang Z. Matching pursuit with time-frequency dictionaries[JJ, IEEE Trans. On Signal Processing, 1993, 41(12 ) :3397-3415.
24. Chen S S, D L Donoho,M A Saunders. Atomic decompositiom by basis pursuit[J]. SIAM J. Sci Comp, 1999, 20(1): 33-61.
25.David L. Donoho, Member, IEEE, and Xiaoming Huo. Uncertainty Principles and Ideal Atomic Decomposition[J]. IEEE Transactions on Information Theroy, 2001,47(11):2845-2862.
26.Joel A. Tropp, Greed is Good: Algorithmic Results for Sparse Approximation [J]. IEEE Transactions on Information Theroy, 2004,50(10):2231-2242.
27.Gribonval, Remi; Nielsen, Morten. Sparse Representations in Unions of Bases[J]. IEEE Transactions on Information Theory, 2003,49 (12):3320-3325.
28.A.Criminisi, Perez,K.Toyama. Object Removal by exemplar-based inpainting IEEE.Conference on computer vision and pattern recognition 2003,
29.Marcelo Bertalmio, Luminita Vese, Guillermo Sapiro Simultaneous Structure and Texture Image Inpainting IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 12, NO. 8, AUGUST 2003