Image segmentation for stylized non-photorealistic rendering and animation
Inhaltsverzeichnis
Reference
Kolliopoulos, A.: Image segmentation for stylized non-photorealistic rendering and animation. Master’s thesis, Univ. Toronto (2005).
DOI
Abstract
This thesis approaches the problem of non-photorealistic rendering by identifying seg- ments in the image plane and filling them using algorithms to render in artistic styles. Using segments as a 2D primitive for non-photorealistic styles is a natural extension of techniques artists often implicitly employ for purposes such as abstraction of unnec- essary detail. The problem of segmenting an arbitrary 3D scene in a 2D view using geometric scene information is presented, and a solution based on spectral clustering is proposed. With an acceleration technique, segmentation can be performed in near real-time for interactive, artistic environments. This approach is automatic beyond the setting of segmentation parameters by a user, and it can be extended to temporally coher- ent non-photorealistic animation by segmenting adjacent frames together. A number of artistic rendering styles are applied within this segmentation framework to demonstrate the effects that such a system makes possible.
Extended Abstract
Bibtex
Used References
[1] Aseem Agarwala. SnakeToonz: A Semi-Automatic Approach to Creating Cel Ani- mation from Video. In NPAR ’02: Proceedings of the 2nd International Symposium on Non-Photorealistic Animation and Rendering, pages 139–146. ACM Press, 2002.
[2] Aseem Agarwala, Aaron Hertzmann, David H. Salesin, and Steven M. Seitz. Keyframe-Based Tracking for Rotoscoping and Animation. ACM Transactions on Graphics, 23(3):584–591, 2004.
[3] Arthur Appel. The Notion of Quantitative Invisibility and the Machine Rendering of Solids. In Proceedings of the 1967 22nd National Conference, pages 387–393. ACM Press, 1967.
[4] Arthur Appel, F. James Rohlf, and Arthur J. Stein. The Haloed Line Effect for Hidden Line Elimination. In Proceedings of the 6th Annual Conference on Computer Graphics and Interactive Techniques, pages 151–157. ACM Press, 1979.
[5] J. Andrew Bangham, Stuart E. Gibson, and Richard Harvey. The Art of Scale- Space. In Proceedings of British Machine Vision Conference, 2003.
[6] Asa Ben-Hur, David Horn, Hava T. Siegelmann, and Vladimir Vapnik. Support Vector Clustering. Journal of Machine Learning Research, 2:125–137, 2002.
[7] Mario Botsch, Stephan Steinberg, Stephan Bischoff, and Leif Kobbelt. OpenMesh – A Generic and Efficient Polygon Mesh Data Structure. In OpenSG Symposium, 2002.
[8] David Bourguignon, Marie-Paul Cani, and George Drettakis. Drawing for Illustra- tion and Annotation in 3D. In Computer Graphics Forum (Proceedings of Euro- graphics 2001), volume 20, pages 114–122, September 2001.
[9] Yuri Boykov and Vladimir Kolmogorov. An Experimental Comparison of Min- Cut/Max-Flow Algorithms for Energy Minimization in Vision. In Energy Min- imization Methods in Computer Vision and Pattern Recognition, pages 359–374, 2001.
[10] Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast Approximate Energy Minimiza- tion via Graph Cuts. In Proceedings of the International Conference on Computer Vision, volume 1, pages 377–384, 1999.
[11] Yuri Y. Boykov and Marie-Pierre Jolly. Interactive Graph Cuts for Optimal Bound- ary and Region Segmentation of Objects in N-D Images. In Proceedings of the In- ternational Conference on Computer Vision, volume 1, pages 105–112. ACM Press, 2001.
[12] John W. Buchanan and Mario C. Sousa. The Edge Buffer: A Data Structure for Easy Silhouette Rendering. In NPAR ’00: Proceedings of the 1st International Symposium on Non-Photorealistic Animation and Rendering, pages 39–42. ACM Press, 2000.
[13] Chris Buck and Kevin Lima. Tarzan, 1999. Disney.
[14] Capcom. Auto Modellista, 2003.
[15] Chakra Chennubhotla and Allan Jepson. Hierarchical Eigensolver for Transition Matrices in Spectral Methods. In Lawrence K. Saul, Yair Weiss, and L ́eon Bottou, editors, Advances in Neural Information Processing Systems 17, pages 273–280. MIT Press, Cambridge, MA, 2005.
[16] Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
[17] Jonathan M. Cohen, John F. Hughes, and Robert C. Zeleznik. Harold: A World Made of Drawings. In NPAR ’00: Proceedings of the 1st International Symposium on Non-Photorealistic Animation and Rendering, pages 83–90. ACM Press, 2000.
[18] Patrick Coleman. Interactive control of nonlinear projection for complex animated scenes. Master’s thesis, University of Toronto, 2004.
[19] J. P. Collomosse, D. Rowntree, and P. M. Hall. Cartoon-Style Rendering of Motion from Video. In Proceedings of Video, Vision and Graphics (VVG), pages 117–124, July 2003.
[20] J. P. Collomosse, D. Rowntree, and P. M. Hall. Stroke Surfaces: A Spatio-temporal Framework for Temporally Coherent Non-photorealistic Animations. Technical Report 2003–01, University of Bath, U.K., June 2003.
[21] Dorin Comaniciu and Peter Meer. Mean Shift: A Robust Approach Toward Feature Space Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):603–619, 2002.
[22] I. J. Cox, S. B. Rao, and Y. Zhong. Ratio Regions: A Technique for Image Segmen- tation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 2, pages 557–564. IEEE Computer Society, 1996.
[23] Cassidy J. Curtis, Sean E. Anderson, Joshua E. Seims, Kurt W. Fleischer, and David H. Salesin. Computer-Generated Watercolor. In SIGGRAPH ’97: Pro- ceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, pages 421–430, August 1997.
[24] Eric Daniels. Deep Canvas in Disney’s Tarzan. In SIGGRAPH ’99: ACM SIG- GRAPH 99 Electronic Art and Animation Catalog, page 124. ACM Press, 1999.
[25] Doug DeCarlo, Adam Finkelstein, Szymon Rusinkiewicz, and Anthony Santella. Suggestive Contours for Conveying Shape. ACM Transactions on Graphics, 22(3):848–855, 2003.
[26] Doug DeCarlo and Anthony Santella. Stylization and Abstraction of Photographs. In SIGGRAPH ’02: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, pages 769–776, New York, NY, USA, 2002. ACM Press.
[27] Oliver Deussen and Thomas Strothotte. Computer-Generated Pen-and-Ink Illus- tration of Trees. In SIGGRAPH ’00: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, pages 13–18. ACM Press/Addison- Wesley Publishing Co., 2000.
[28] D. Sim Dietrich Jr. GPU Toon Shading. NVIDIA Corporation. http://developer.nvidia.com/object/toon shading geforce256.html.
[29] Pat Duke. Personal communication, 2004.
[30] Gershon Elber. Line Art Rendering via a Coverage of Isoparametric Curves. IEEE Transactions on Visualization and Computer Graphics, 1(3):231–239, September 1995.
[31] Gershon Elber. Line Art Illustrations of Parametric and Implicit Forms. IEEE Transactions on Visualization and Computer Graphics, 4(1), January–March 1998. [32] Gershon Elber. Interactive Line Art Rendering of Freeform Surfaces. Computer Graphics Forum, 18(3):1–12, September 1999.
[33] Gershon Elber and Elaine Cohen. Hidden Curve Removal for Free Form Sur- faces. In SIGGRAPH ’90: Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques, volume 24, pages 95–104, August 1990.
[34] Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Image Segmentation Using Local Variation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, page 98. IEEE Computer Society, 1998.
[35] Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Distance Transforms for Sam- pled Functions. Technical Report TR2004-1963, Cornell Computing and Informa- tion Science, 2004.
[36] Max Fleischer. Method of Producing Moving Picture Cartoons, 1917. US Patent no. 1,242,674.
[37] L. R. Ford and D. R. Fulkerson. Maximal Flow Through a Network. Canadian Journal of Mathematics, 8:399–404, 1956.
[38] R. E. Gomory and T. C. Hu. Multi-Terminal Network Flows. Journal of SIAM, 9(4):551–570, December 1961.
[39] Bruce Gooch, Greg Coombe, and Peter Shirley. Artistic Vision: Painterly Ren- dering Using Computer Vision Techniques. In NPAR ’02: Proceedings of the 2nd International Symposium on Non-Photorealistic Animation and Rendering, pages 83–90. ACM Press, 2002.
[40] St ́ephane Grabli, Fr ́edo Durand, and Fran ̧cois Sillion. Density Measure for Line- Drawing Simplification. In Proceedings of Pacific Graphics, 2004.
[41] St ́ephane Grabli, Emmanuel Turquin, Fr ́edo Durand, and Fran ̧cois Sillion. Pro- grammable Style for NPR Line Drawing. In Rendering Techniques 2004 (Euro- graphics Symposium on Rendering). ACM Press, June 2004.
[42] Matt Groening. Futurama, 1999–2003. 20th Century Fox.
[43] Paul Haeberli. Paint by Numbers: Abstract Image Representations. In Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques, pages 207–214. ACM Press, 1990.
[44] Alejo Hausner. Simulating Decorative Mosaics. In SIGGRAPH ’01: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, pages 573–580. ACM Press, 2001.
[45] Aaron Hertzmann. Painterly Rendering with Curved Brush Strokes of Multiple Sizes. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, pages 453–460. ACM Press, 1998.
[46] Aaron Hertzmann. Fast Paint Texture. In NPAR ’02: Proceedings of the 2nd International Symposium on Non-Photorealistic Animation and Rendering, pages 91–96. ACM Press, 2002.
[47] Aaron Hertzmann and Ken Perlin. Painterly Rendering for Video and Interac- tion. In NPAR ’00: Proceedings of the 1st International Symposium on Non- Photorealistic Animation and Rendering, pages 7–12. ACM Press, 2000.
[48] Aaron Hertzmann and Denis Zorin. Illustrating Smooth Surfaces. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, pages 517–526. ACM Press/Addison-Wesley Publishing Co., 2000.Bibliography 102
[49] D. Hochbaum and D. Shmoys. A Best Possible Heuristic for the K-Center Problem. Mathematics of Operations Research, 1985.
[50] Tobias Isenberg, Bert Freudenberg, Nick Halper, Stefan Schlechtweg, and Thomas Strothotte. A Developer’s Guide to Silhouette Algorithms for Polygonal Models. IEEE Computer Graphics and Applications, 23(4):28–37, 2003.
[51] Tobias Isenberg, Nick Halper, and Thomas Strothotte. Stylizing Silhouettes at Interactive Rates: From Silhouette Edges to Silhouette Strokes. In Computer Graphics Forum (Proceedings of EUROGRAPHICS), volume 21, pages 249–258. Blackwell Publishing, September 2002.
[52] Robert D. Kalnins, Philip L. Davidson, Lee Markosian, and Adam Finkelstein. Coherent Stylized Silhouettes. ACM Transactions on Graphics, 22(3):856–861, July 2003.
[53] Robert D. Kalnins, Lee Markosian, Barbara J. Meier, Michael A. Kowalski, Joseph C. Lee, Philip L. Davidson, Matthew Webb, John F. Hughes, and Adam Finkelstein. WYSIWYG NPR: Drawing Strokes Directly on 3D Models. In SIG- GRAPH ’02: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, pages 755–762. ACM Press, 2002.
[54] R. Kannan, S. Vempala, and A. Veta. On Clusterings: Good, Bad and Spectral. In FOCS ’00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 367. IEEE Computer Society, 2000.
[55] Allison W. Klein, Wilmot Li, Michael M. Kazhdan, Wagner T. Corrˆea, Adam Finkelstein, and Thomas A. Funkhouser. Non-Photorealistic Virtual Environments. In SIGGRAPH ’00: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, pages 527–534. ACM Press/Addison-Wesley Publishing Co., 2000.
[56] Michael A. Kowalski, Lee Markosian, J. D. Northrup, Lubomir Bourdev, Ronen Barzel, Loring S. Holden, and John F. Hughes. Art-Based Rendering of Fur, Grass, and Trees. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, pages 433–438. ACM Press/Addison-Wesley Publishing Co., 1999.
[57] John Lansdown and Simon Schofield. Expressive Rendering: A Review of Nonpho- torealistic Techniques. IEEE Computer Graphics and Applications, 15(3):29–37, May 1995.
[58] Anat Levin, Dani Lischinski, and Yair Weiss. Colorization Using Optimization. ACM Transactions on Graphics, 23(3):689–694, 2004.
[59] Yin Li, Jian Sun, Chi-Keung Tang, and Heung-Yeung Shum. Lazy Snapping. ACM Transactions on Graphics, 23(3):303–308, 2004.
[60] Richard Linklater. A Scanner Darkly. To be released.
[61] Richard Linklater. Waking Life, 2001. 20th Century Fox.
[62] Peter Litwinowicz. Processing Images and Video for an Impressionist Effect. In SIGGRAPH ’97: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, pages 407–414, New York, NY, USA, August 1997. ACM Press/Addison-Wesley Publishing Co.
[63] J. MacQueen. Some Methods for Classification and Analysis of Multivariate Obser- vations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, pages 281–297. University of California Press, 1967.
[64] Lee Markosian, Michael A. Kowalski, Daniel Goldstein, Samuel J. Trychin, John F. Hughes, and Lubomir D. Bourdev. Real-Time Nonphotorealistic Rendering. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, pages 415–420. ACM Press/Addison-Wesley Publishing Co., 1997.
[65] D. Mart ́ın, J. D. Fekete, and J. C. Torres. Flattening 3D Objects Using Sil- houettes. In Computer Graphics Forum (Proceedings of EUROGRAPHICS), vol- ume 21, pages 239–248. Blackwell Publishing, September 2002.
[66] Scott McCloud. Understanding Comics: The Invisible Art. Kichen Sink Press, 1993.
[67] Morgan McGuire and John F. Hughes. Hardware-determined feature edges. In NPAR ’04: Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, pages 35–147. ACM Press, 2004.
[68] TDK Mediactive. RoboTech: Battlecry, 2002.
[69] Barbara J. Meier. Painterly Rendering for Animation. In SIGGRAPH ’96: Proceed- ings of the 23rd Annual Conference on Computer Graphics and Interactive Tech- niques, Computer Graphics Proceedings, Annual Conference Series, pages 477–484, August 1996.
[70] A. Ng, M. Jordan, and Y. Weiss. On Spectral Clustering: Analysis and an Algo- rithm. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, 2002.
[71] J. D. Northrup and Lee Markosian. Artistic Silhouettes: A Hybrid Approach. In NPAR ’00: Proceedings of the 1st International Symposium on Non-Photorealistic Animation and Rendering, pages 31–38. ACM Press, 2000.
[72] Ken Perlin. An Image Synthesizer. In SIGGRAPH ’85: Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques, pages 287– 296. ACM Press, 1985.
[73] Pietro Perona and William T. Freeman. A Factorization Approach to Grouping. In ECCV ’98: Proceedings of the 5th European Conference on Computer Vision, pages 655–670. Springer-Verlag, 1998.
[74] Ferdinand Petrie and John Shaw. The Big Book of Painting Nature in Watercolor. Watson-Guptill Publications, 1990.
[75] Alexander Petrov. The Old Man and the Sea, 1999. Panorama Film Studio of Yaroslav.
[76] Abhishek Ranjan. Motion Segmentation Using Spanning Trees and Graph Cuts. Bachelor’s thesis, IIT Bombay, 2003.
[77] Ramesh Raskar. Hardware Support for Non-Photorealistic Rendering. In Proceed- ings of the ACM SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hard- ware, pages 41–47. ACM Press, 2001.
[78] Carsten Rother, Vladimir Kolmogorov, and Andrew Blake. “Grabcut”: Interac- tive Foreground Extraction Using Iterated Graph Cuts. ACM Transactions on Graphics, 23(3):309–314, 2004.
[79] Szymon Rusinkiewicz. Estimating Curvatures and Their Derivatives on Triangle Meshes. In Symposium on 3D Data Processing, Visualization, and Transmission, September 2004.
[80] Takafumi Saito and Tokiichiro Takahashi. Comprehensible Rendering of 3-D Shapes. In SIGGRAPH ’90: Proceedings of the 17th Annual Conference on Com- puter Graphics and Interactive Techniques, pages 197–206. ACM Press, 1990.
[81] Michael P. Salisbury, Sean E. Anderson, Ronen Barzel, and David H. Salesin. Interactive Pen-and-Ink Illustration. In SIGGRAPH ’94: Proceedings of the 21stBibliography 106
Annual Conference on Computer Graphics and Interactive Techniques, pages 101– 108. ACM Press, 1994.
[82] Michael P. Salisbury, Michael T. Wong, John F. Hughes, and David H. Salesin. Orientable Textures for Image-Based Pen-and-Ink Illustration. In SIGGRAPH ’97: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, pages 401–406. ACM Press/Addison-Wesley Publishing Co., 1997.
[83] Anthony Santella and Doug DeCarlo. Visual Interest and NPR: An Evaluation and Manifesto. In NPAR ’04: Proceedings of the 3rd International Symposium on Non-Photorealistic Animation and Rendering, pages 71–150. ACM Press, 2004.
[84] Georges Schwizgebel. L’homme sans ombre, 2004. Studio GDS, the National Film Board of Canada, T ́el ́evision Suisse Romande.
[85] E. Sharon, A. Brandt, and R. Basri. Fast Multiscale Image Segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 70–77. IEEE Computer Society, 2000.
[86] Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, August 2000.
[87] Smilebit and Sega. Jet Set Radio Future, 2002.
[88] Daniel A. Spielman and Shang-Hua Teng. Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. In Proceedings of the 37th Annual IEEE Con- ference on Foundations of Computer Science, pages 96–105, 1996. [89] Jhonen Vasquez. Invader Zim, 2001–2003. Viacom.
[90] Olga Veksler. Image Segmentation by Nested Cuts. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 1, page 1339. IEEE Computer Society, June 2000.
[91] Jue Wang, Yingqing Xu, Heung-Yeung Shum, and Michael F. Cohen. Video Toon- ing. ACM Transactions on Graphics, 23(3):574–583, August 2004.
[92] Yair Weiss. Segmentation Using Eigenvectors: A Unifying View. In ICCV ’99: Proceedings of the International Conference on Computer Vision, volume 2, pages 975–982. IEEE Computer Society, 1999.
[93] Brett Wilson and Kwan-Liu Ma. Rendering Complexity in Computer-Generated Pen-and-Ink Illustrations. In Proceedings of the 3rd International Symposium on Non-Photorealistic Animation and Rendering, pages 129–137. ACM Press, 2004.
[94] Georges Winkenbach and David H. Salesin. Computer-Generated Pen-And-Ink Illustration. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, pages 91–100. ACM Press, 1994.
[95] Georges Winkenbach and David H. Salesin. Rendering Parametric Surfaces in Pen and Ink. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, pages 469–476. ACM Press, 1996.
[96] Z. Wu and R. Leahy. An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(11):1101–1113, 1993.
[97] Brian Wyvill, Kees van Overveld, and Sheelagh Carpendale. Rendering Cracks in Batik. In NPAR ’04: Proceedings of the 3rd International Symposium on Non- Photorealistic Animation and Rendering, pages 61–70. ACM Press, 2004.108 Bibliography
[98] T. Yamazaki. Introduction of EM Algorithm into Color Image Segmentation. In IEEE International Conference on Intelligent Processing Systems, pages 368–371, August 1998.
[99] Stella X. Yu and Jianbo Shi. Multiclass Spectral Clustering. In Ninth IEEE Inter- national Conference on Computer Vision, pages 313–319, October 2003.
[100] Lihi Zelnik-Manor and Pietro Perona. Self-Tuning Spectral Clustering. In Lawrence K. Saul, Yair Weiss, and L ́eon Bottou, editors, Advances in Neural In- formation Processing Systems 17. MIT Press, 2005.
Links
Full Text
http://www.dgp.toronto.edu/~alexk/kolliopoulos-thesis2005.pdf
Sonstige Links
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.3711
