基于样图的纹理合成算法优化
|
摘要
纹理是在计算机图形学中一种普遍存在的视觉现象。纹理通常用来描述自然界中具有重复性的现象,如机房中的噪声,物体移动,物体表面细节特征以及人类的活动等等。计算机图形学的主要目标就是再现真实世界,那么纹理合成在图像处理和动画领域上有着重要的意义。
首先,提炼多种纹理合成算法共性,提出一种基于马尔可夫随机场(MRF)的纹理合成算法框架设计,该架构比较简单灵活,由两个相对独立的模块组成:多分辨率图像金字塔和匹配查询。每个模块都可以进行独立的扩展。该框架是本文纹理合成算法扩展和优化的原型。
其次,基于这种算法框架,提出一系列应在纹理合成过程中进行提取的纹理特征。假设纹理为空间上分布的信号,挖掘出四个纹理特征作为合成过程的参考:纹理能量,像素颜色值,梯度和空间频率。纹理能量是纹理的全局信息,那么纹理合成过程就转换为能量最小化的优化过程。在能量约束下误差不会在纹理生成过程中累积,纹理的全局信息可以在大范围内得到交换。像素颜色值是纹理合成的基本依据。梯度为合成过程加入了高通滤波效应,增强了合成纹理的高频信息。邻域尺寸的设置对最终结果影响颇大,通过动态空间频率检测,可以在适当的场景中使用适当的邻域尺寸。
最后,对算法的迭代过程和匹配查询过程进行加速。提出基于遗传算法的混合迭代优化以及多分辨率多尺度的方式进行纹理合成,可以有效降低在迭代过程中陷入局部极值的可能性。同时,使用k-d树或TSVQ(tree-structured vector quantization)树等技术,对邻域匹配操作进行加速。
Textures can describe a wide variety of natural phenomena with random variations over repeating patterns. Examples of textures include images, motions, and surface geometry. Since reproducing the realism of the physical world is a major goal for computer graphics, texture synthesis is important for rendering synthetic images and animations.
Firstly, we introduce a basic architecture of texture synthesis based upon Markov Random Field. The architecture is flexible and it is composed from several orthogonal components: multi-resolution image pyramid and searching. Each component can be extended or optimized independently. The architecture is the prototype for further extension and optimization in this paper.
Secondly, based upon the architecture, we put forward a series of texture variables which should be considered in the process of texture synthesis. On the assumption that texture is a kind of signal distributed spatially, we find out four useful variables for reference: global energy, pixel color, gradient and space frequency. Texture energy is the global information and this allows us to formulate the synthesis problem as minimization of an energy function, which can be optimized. Error can’t be accumulated through the process of synthesis and information is exchanged in a large-scale domain. Pixel color is the basis of synthesis. Gradient works as a high pass filter which enhances high frequency component of the texture synthesis. Final synthesis result is sensitive to initial neighborhood setting. Through dynamic space frequency detection, proper neighborhood can be set in the algorithm context.
Finally, we introduce several solutions for acceleration. The prototype can get stuck in local minima. Hybrid generic algorithm decreases iteration count in each resolution. Multi-level-multi-scale synthesis partially alleviates this problem by bringing distant neighborhoods closer to each other via down-sampling. In addition, our algorithm can be directly accelerated by a point searching algorithm such as tree-structured vector quantization and k-d tree.
首先,提炼多种纹理合成算法共性,提出一种基于马尔可夫随机场(MRF)的纹理合成算法框架设计,该架构比较简单灵活,由两个相对独立的模块组成:多分辨率图像金字塔和匹配查询。每个模块都可以进行独立的扩展。该框架是本文纹理合成算法扩展和优化的原型。
其次,基于这种算法框架,提出一系列应在纹理合成过程中进行提取的纹理特征。假设纹理为空间上分布的信号,挖掘出四个纹理特征作为合成过程的参考:纹理能量,像素颜色值,梯度和空间频率。纹理能量是纹理的全局信息,那么纹理合成过程就转换为能量最小化的优化过程。在能量约束下误差不会在纹理生成过程中累积,纹理的全局信息可以在大范围内得到交换。像素颜色值是纹理合成的基本依据。梯度为合成过程加入了高通滤波效应,增强了合成纹理的高频信息。邻域尺寸的设置对最终结果影响颇大,通过动态空间频率检测,可以在适当的场景中使用适当的邻域尺寸。
最后,对算法的迭代过程和匹配查询过程进行加速。提出基于遗传算法的混合迭代优化以及多分辨率多尺度的方式进行纹理合成,可以有效降低在迭代过程中陷入局部极值的可能性。同时,使用k-d树或TSVQ(tree-structured vector quantization)树等技术,对邻域匹配操作进行加速。
Textures can describe a wide variety of natural phenomena with random variations over repeating patterns. Examples of textures include images, motions, and surface geometry. Since reproducing the realism of the physical world is a major goal for computer graphics, texture synthesis is important for rendering synthetic images and animations.
Firstly, we introduce a basic architecture of texture synthesis based upon Markov Random Field. The architecture is flexible and it is composed from several orthogonal components: multi-resolution image pyramid and searching. Each component can be extended or optimized independently. The architecture is the prototype for further extension and optimization in this paper.
Secondly, based upon the architecture, we put forward a series of texture variables which should be considered in the process of texture synthesis. On the assumption that texture is a kind of signal distributed spatially, we find out four useful variables for reference: global energy, pixel color, gradient and space frequency. Texture energy is the global information and this allows us to formulate the synthesis problem as minimization of an energy function, which can be optimized. Error can’t be accumulated through the process of synthesis and information is exchanged in a large-scale domain. Pixel color is the basis of synthesis. Gradient works as a high pass filter which enhances high frequency component of the texture synthesis. Final synthesis result is sensitive to initial neighborhood setting. Through dynamic space frequency detection, proper neighborhood can be set in the algorithm context.
Finally, we introduce several solutions for acceleration. The prototype can get stuck in local minima. Hybrid generic algorithm decreases iteration count in each resolution. Multi-level-multi-scale synthesis partially alleviates this problem by bringing distant neighborhoods closer to each other via down-sampling. In addition, our algorithm can be directly accelerated by a point searching algorithm such as tree-structured vector quantization and k-d tree.
引文
[1] Alexei Efros and Thomas Leung. Texture synthesis by non-parametric sampling. In: International Conference on Computer Vision, 1999-09. Volume 2, 1033–1041
[2] Heeger David J,James R Bergen.Pyramid-Based Texture Analysis Synthesis. In: Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH 95), 1995-08. 229~238
[3] Emil Praun, Adam Finkelstein, Hugues Hoppe. Lapped textures. In: Proceedings of SIGGRAPH 2000, 2000-07.465~470
[4] Li-Yi Wei, Marc Levoy. Fast texture synthesis using tree-structured vector quantization. In: Proceedings of SIGGRAPH 2000, 2000. 479-488
[5] Michael Ashikhmin. Synthesizing natural textures. In: 2001 ACM Symposium on Interactive 3D Graphics, 2001. 217~216
[6] Alexei, Thomas Leung. Texture synthesis by non-parametric sampling. In: International Conference on Computer Vision, 1999-09. Volume 2, 1033–1041.
[7] Alexei Efros, W T Freeman. Image quilting for texture synthesis and transfer. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 2001. 341~347
[8] Georges Winkenbach, David H. Salesin. Computer-generated pen-and-ink illustration. In: Proceedings of SIGGRAPH 94, 1994-07. 91–100
[9] Georges Winkenbach and David H. Salesin. Rendering parametric surfaces in pen and ink. In: Proceedings of SIGGRAPH 96, 1996-01. 469–476
[10] Martin Szummer, Rosalind W. Picard. Temporal texture modeling. In: International Conference on Image Processing, 1996-09. Volume 3,823–829
[11] Andrew C. Beers, Maneesh Agrawala, and Navin Chaddha. Rendering from compressed textures. Proceedings of SIGGRAPH 96, 1996-08. 373–378
[12] Homan Igehy, Lucas Pereira. Image replacement through texture synthesis. In: International Conference on Image Processing, 1997-10. Volume 3, 186–189
[13] J J Gibson. The Perception of the Visual World. Houghton Mifflin, Boston, Massachusetts, 1950
[14] E Catmull. Subdivision algorithm for computer display of curved surfaces. PhD dissertation. Department of Computer Science, University of Utah, Salt Lake City, Utah, 1974
[15] L Bruno, J L Mallet. Non-distortion texture mapping for sheared triangulated meshes.In : Proceeding of ACM SIGGRAPH, Florida, ACMPress, 1998. 343~352
[16] M Jerome, H Yahia,A Verroust. Interactive texture mapping. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1993. 27~34
[17] P Dan, G Borshukov. Seamless texture mapping of subdivision surfaces by model pelting and texture blending. In: Proceeding of ACM SIGGRAPH, New Orleans, ACM Press, 2000. 471~478
[18] B Linn J, NEWELL M. Texture and reflection in computer generated images. Communications of the ACM 19, 1976. 542~547
[19] K Perlin. An image synthesizer. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1985. 287~296
[20] D R Peachey. Solid texturing of complex surfaces. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1985. 279~286
[21] S Worley. A cellular texture basis function. In: Proceeding of ACM SIGGAPH, New Orleans, ACM Press, 1996. 291~294
[22] F Neyret, M P Cani. Pattern-based texturing revisited. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1999. 235~242
[23] Witkin M Kass. Reaction-diffusion textures. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1991 299~308
[24] G Turk. Generationg textures on arbitrary surface susingreation-diffusion. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1991 289~298
[25] K Fleisher, D Laidlaw, B Currinetal. Cellular texture generation. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1995 239~248
[26] M Walter, A Fournier. Clonalmosaic model for the synthesis of mammalian coat patterns. In: Proceeding of Graphics Interface
[27] Greg Turk. Texture synthesis on surfaces. In: Proceedings of SIGGRAPH 2001, 2001. 347~354
[28] L Liang, C Liu, Y Xu etal. Real-time texture synthesis by patch-based sampling. Microsoft Research, Technical Report: MSR-TR-2001-40, 2001
[29] Xinguo Liu, Yizhou Yu, Heung-Yeung Shum. Synthesizing bidirectional texture functions for real-world surfaces. In: Proceedings of SIGGRAPH 2001, 2001. 96~106
[30] Paget R, Longstaff I D. Texture synthesis via a noncausal nonparametric multiscale markov random field. In: IEEE Transactions on Image Processing 7, 6 (June), 1998. 925–931
[31] Portilla J, Simoncelli E P. A parametric texture model based on joint statistics of complex wavelet coefficients. In: International Journal of Computer Vision 40, 1, 2000-10. 49–70
[32] Freeman W T. Examplebased super-resolution. In: IEEE Computer Graphics and application. 2002. 22(2), 56–65
[33] Vivek Kwatra, Irfan E A. Texture Optimization for Example-based Synthesis. In: ACM Transactions on Graphics, SIGGRAPH 2005, 2005-07. 24(3), 795-802
[34] Vivek Kwatra, SCH?DL, A., ESSA, I., TURK, G., AND BOBICK, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. In: ACM Transactions on Graphics, SIGGRAPH 2003, 2003-07. 277–286
[35] Andrew Nealen, Marc Alexa. Hybrid texture synthesis. In: Proceedings of the 14th Eurographics workshop on Rendering, ACM International Conference Proceeding Series, 2003. 44, 97-105
[36] P. J. Burt, E. H. Adelson. A multiresolution spline with application to image mosaics. In: ACM Transactions on Graphics, 1983-10. 2(4),217–236
[37] Li-Yi Wei. Texture synthesis by fixed neighborhood searching. PhD dissertation. Department of Electrical engineering, Stanford University, Palo Alto, California, 2001
[38] K. Popat, R.W. Picard. Novel cluster-based probability model for texture synthesis, classification, and compression. In: Visual Communications and Image Processing, 1993. 756–68
[39] Yu Hen Hu, Sambhare, R.A. Constrained texture synthesis for image post processing. In: Multimedia and Expo, ICME '03, 2003. 1,113-119
[40] Marquardt D. An Algorithm for Least-Squares Estimation of Nonlinear Parameters. In: SIAM Journal on Applied Mathematics, 1963. 11, 431-441
[41] Thierens, D., Goldberg, D. (1994b). Elitist recombination: An integrated selection recombination GA. In: Proceedings of the First IEEE Conference on Evolutionary Computation, 1994. 1, 508-512
[42] Fernando G L, Goldberg D E. Decision making in a hybrid genetic algorithm. IEEE International Conference on Evolutionary Computation, 1997. 122-125
[43] L. Davis. Adapting operator probabilities in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, 1989. 61-69
[44] B. A. Julstrom. What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. In: Proceedings of the Sixth International Conference on Genetic Algorithms, 1995. 81-87
[45] Pérez P, Gangnet M, Blake A. Poisson image editing. In: ACM Transactions on Graphics, SIGGRAPH 2003, 2003. 22(3), 313–318
[46] Coggins, J.M., A.K. Jain. A Spatial Filtering Approach to Texture Analysis. In: Pattern Recognition Letters, 1985. 3, 195-203
[47] Allen Gersho, Robert M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publishers, 1992
[48] S. Nene, S. Nayar. A simple algorithm for nearest neighbor search in high dimensions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997. 19, 989–1003
[49] Sylvain Lefebvre, Hugues Hoppe. In: SESSION of Texture synthesis, ACM SIGGRAPH 2005, 2005. 777-786
[50] Aaron Hertzmann, Charles Jacobs, Nuria Oliver etal. Image analogies. In: Proceedings of SIGGRAPH 2001, 2001-08
[51] Freeman W T. Examplebased super-resolution. In: IEEE Computer Graphics and application, 2002. 22(2), 56–65
[52] Jeremy S. De Bonet. Multiresolution sampling procedure for analysis and synthesis of texture images. In: SIGGRAPH 97 Conference Proceedings, Annual Conference Series, AddisonWesley, 1997-08. 361–368
[53] Zelink, S., Garland, M. 2002. Towards real-time texture synthesis with the jump map. In: Proceedings of the 13th Eurographics workshop on Rendering, Pisa, Italy. 99 – 104
[54] Harrison, P. A non-hiearachical procedure for re-synthesis of complex textures. In: WSCG'2001, 2001. 190-197
[55] Tonietto, L., Walter, M.. Towards local control for image-based texture synthesis. In: Computer Graphics and Image Processing, Proceedings. XV Brazilian Symposium, 7-10 Oct, 2002. 252-258
[2] Heeger David J,James R Bergen.Pyramid-Based Texture Analysis Synthesis. In: Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH 95), 1995-08. 229~238
[3] Emil Praun, Adam Finkelstein, Hugues Hoppe. Lapped textures. In: Proceedings of SIGGRAPH 2000, 2000-07.465~470
[4] Li-Yi Wei, Marc Levoy. Fast texture synthesis using tree-structured vector quantization. In: Proceedings of SIGGRAPH 2000, 2000. 479-488
[5] Michael Ashikhmin. Synthesizing natural textures. In: 2001 ACM Symposium on Interactive 3D Graphics, 2001. 217~216
[6] Alexei, Thomas Leung. Texture synthesis by non-parametric sampling. In: International Conference on Computer Vision, 1999-09. Volume 2, 1033–1041.
[7] Alexei Efros, W T Freeman. Image quilting for texture synthesis and transfer. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 2001. 341~347
[8] Georges Winkenbach, David H. Salesin. Computer-generated pen-and-ink illustration. In: Proceedings of SIGGRAPH 94, 1994-07. 91–100
[9] Georges Winkenbach and David H. Salesin. Rendering parametric surfaces in pen and ink. In: Proceedings of SIGGRAPH 96, 1996-01. 469–476
[10] Martin Szummer, Rosalind W. Picard. Temporal texture modeling. In: International Conference on Image Processing, 1996-09. Volume 3,823–829
[11] Andrew C. Beers, Maneesh Agrawala, and Navin Chaddha. Rendering from compressed textures. Proceedings of SIGGRAPH 96, 1996-08. 373–378
[12] Homan Igehy, Lucas Pereira. Image replacement through texture synthesis. In: International Conference on Image Processing, 1997-10. Volume 3, 186–189
[13] J J Gibson. The Perception of the Visual World. Houghton Mifflin, Boston, Massachusetts, 1950
[14] E Catmull. Subdivision algorithm for computer display of curved surfaces. PhD dissertation. Department of Computer Science, University of Utah, Salt Lake City, Utah, 1974
[15] L Bruno, J L Mallet. Non-distortion texture mapping for sheared triangulated meshes.In : Proceeding of ACM SIGGRAPH, Florida, ACMPress, 1998. 343~352
[16] M Jerome, H Yahia,A Verroust. Interactive texture mapping. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1993. 27~34
[17] P Dan, G Borshukov. Seamless texture mapping of subdivision surfaces by model pelting and texture blending. In: Proceeding of ACM SIGGRAPH, New Orleans, ACM Press, 2000. 471~478
[18] B Linn J, NEWELL M. Texture and reflection in computer generated images. Communications of the ACM 19, 1976. 542~547
[19] K Perlin. An image synthesizer. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1985. 287~296
[20] D R Peachey. Solid texturing of complex surfaces. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1985. 279~286
[21] S Worley. A cellular texture basis function. In: Proceeding of ACM SIGGAPH, New Orleans, ACM Press, 1996. 291~294
[22] F Neyret, M P Cani. Pattern-based texturing revisited. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1999. 235~242
[23] Witkin M Kass. Reaction-diffusion textures. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1991 299~308
[24] G Turk. Generationg textures on arbitrary surface susingreation-diffusion. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1991 289~298
[25] K Fleisher, D Laidlaw, B Currinetal. Cellular texture generation. In: Proceeding of ACM SIGGRAPH, Los Angeles, ACM Press, 1995 239~248
[26] M Walter, A Fournier. Clonalmosaic model for the synthesis of mammalian coat patterns. In: Proceeding of Graphics Interface
[27] Greg Turk. Texture synthesis on surfaces. In: Proceedings of SIGGRAPH 2001, 2001. 347~354
[28] L Liang, C Liu, Y Xu etal. Real-time texture synthesis by patch-based sampling. Microsoft Research, Technical Report: MSR-TR-2001-40, 2001
[29] Xinguo Liu, Yizhou Yu, Heung-Yeung Shum. Synthesizing bidirectional texture functions for real-world surfaces. In: Proceedings of SIGGRAPH 2001, 2001. 96~106
[30] Paget R, Longstaff I D. Texture synthesis via a noncausal nonparametric multiscale markov random field. In: IEEE Transactions on Image Processing 7, 6 (June), 1998. 925–931
[31] Portilla J, Simoncelli E P. A parametric texture model based on joint statistics of complex wavelet coefficients. In: International Journal of Computer Vision 40, 1, 2000-10. 49–70
[32] Freeman W T. Examplebased super-resolution. In: IEEE Computer Graphics and application. 2002. 22(2), 56–65
[33] Vivek Kwatra, Irfan E A. Texture Optimization for Example-based Synthesis. In: ACM Transactions on Graphics, SIGGRAPH 2005, 2005-07. 24(3), 795-802
[34] Vivek Kwatra, SCH?DL, A., ESSA, I., TURK, G., AND BOBICK, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. In: ACM Transactions on Graphics, SIGGRAPH 2003, 2003-07. 277–286
[35] Andrew Nealen, Marc Alexa. Hybrid texture synthesis. In: Proceedings of the 14th Eurographics workshop on Rendering, ACM International Conference Proceeding Series, 2003. 44, 97-105
[36] P. J. Burt, E. H. Adelson. A multiresolution spline with application to image mosaics. In: ACM Transactions on Graphics, 1983-10. 2(4),217–236
[37] Li-Yi Wei. Texture synthesis by fixed neighborhood searching. PhD dissertation. Department of Electrical engineering, Stanford University, Palo Alto, California, 2001
[38] K. Popat, R.W. Picard. Novel cluster-based probability model for texture synthesis, classification, and compression. In: Visual Communications and Image Processing, 1993. 756–68
[39] Yu Hen Hu, Sambhare, R.A. Constrained texture synthesis for image post processing. In: Multimedia and Expo, ICME '03, 2003. 1,113-119
[40] Marquardt D. An Algorithm for Least-Squares Estimation of Nonlinear Parameters. In: SIAM Journal on Applied Mathematics, 1963. 11, 431-441
[41] Thierens, D., Goldberg, D. (1994b). Elitist recombination: An integrated selection recombination GA. In: Proceedings of the First IEEE Conference on Evolutionary Computation, 1994. 1, 508-512
[42] Fernando G L, Goldberg D E. Decision making in a hybrid genetic algorithm. IEEE International Conference on Evolutionary Computation, 1997. 122-125
[43] L. Davis. Adapting operator probabilities in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, 1989. 61-69
[44] B. A. Julstrom. What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. In: Proceedings of the Sixth International Conference on Genetic Algorithms, 1995. 81-87
[45] Pérez P, Gangnet M, Blake A. Poisson image editing. In: ACM Transactions on Graphics, SIGGRAPH 2003, 2003. 22(3), 313–318
[46] Coggins, J.M., A.K. Jain. A Spatial Filtering Approach to Texture Analysis. In: Pattern Recognition Letters, 1985. 3, 195-203
[47] Allen Gersho, Robert M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publishers, 1992
[48] S. Nene, S. Nayar. A simple algorithm for nearest neighbor search in high dimensions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997. 19, 989–1003
[49] Sylvain Lefebvre, Hugues Hoppe. In: SESSION of Texture synthesis, ACM SIGGRAPH 2005, 2005. 777-786
[50] Aaron Hertzmann, Charles Jacobs, Nuria Oliver etal. Image analogies. In: Proceedings of SIGGRAPH 2001, 2001-08
[51] Freeman W T. Examplebased super-resolution. In: IEEE Computer Graphics and application, 2002. 22(2), 56–65
[52] Jeremy S. De Bonet. Multiresolution sampling procedure for analysis and synthesis of texture images. In: SIGGRAPH 97 Conference Proceedings, Annual Conference Series, AddisonWesley, 1997-08. 361–368
[53] Zelink, S., Garland, M. 2002. Towards real-time texture synthesis with the jump map. In: Proceedings of the 13th Eurographics workshop on Rendering, Pisa, Italy. 99 – 104
[54] Harrison, P. A non-hiearachical procedure for re-synthesis of complex textures. In: WSCG'2001, 2001. 190-197
[55] Tonietto, L., Walter, M.. Towards local control for image-based texture synthesis. In: Computer Graphics and Image Processing, Proceedings. XV Brazilian Symposium, 7-10 Oct, 2002. 252-258