Thesis: Accurate and Discernible Photocollages
Jordan William Miller: Thesis: Accurate and Discernible Photocollages. MS Thesis, Department of Computer Science, University of Saskatchewan, Saskatoon, 2010.
There currently exist several techniques for selecting and combining images from a digital image library into a single image so that the result meets certain prespecified visual criteria. Image mosaic methods, first explored by Connors and Trivedi, arrange library images according to some tiling arrangement, often a regular grid, so that the combination of images, when viewed as a whole, resembles some input target image. Other techniques, such as Autocollage of Rother et al., seek only to combine images in an interesting and visually pleasing manner, according to certain composition principles, without attempting to approximate any target image. Each of these techniques provide a myriad of creative options for artists who wish to combine several levels of meaning into a single image or who wish to exploit the meaning and symbolism contained in each of a large set of images through an efficient and easy process.
We first examine the most notable and successful of these methods, and summarize the ad- vantages and limitations of each. We then formulate a set of goals for an image collage system that combines the advantages of these methods while addressing and mitigating the drawbacks. Particularly, we propose a system for creating photocollages that approximate a target image as an aggregation of smaller images, chosen from a large library, so that interesting visual correspon- dences between images are exploited. In this way, we allow users to create collages in which multiple layers of meaning are encoded, with meaningful visual links between each layer. In service of this goal, we ensure that the images used are as large as possible and are combined in such a way that boundaries between images are not immediately apparent, as in Autocollage. This has required us to apply a multiscale approach to searching and comparing images from a large database, which achieves both speed and accuracy. We also propose a new framework for color post-processing, and propose novel techniques for decomposing images according to object and texture information.
 Aseem Agarwala, Mira Dontcheva, Maneesh Agrawala, Steven Drucker, Alex Colburn, Brian Curless, David Salesin, and Michael Cohen. Interactive digital photomontage. In SIGGRAPH ’04: ACM Transactions on Graphics (TOG) 2004 Papers, pages 294–302, New York, NY, USA, 2004. ACM.
 Michael Ashikhmin. Synthesizing natural textures. In I3D ’01: Proceedings of the 2001 symposium on Interactive 3D graphics, pages 217–226, New York, NY, USA, 2001. ACM.
 Soonmin Bae, Sylvain Paris, and Fr ́edo Durand. Two-scale tone management for photographic look. ACM Trans. Graph., 25(3):637–645, 2006.
 Nick Bantock. Nickbantock.com. Website, July 2009. http://www.nickbantock.com/index.html; Last accessed: 02/11/2010.
 P. Bao and Lei Zhang. Scale correlation-based edge detection. In Video/Image Processing and Multimedia Communications 4th EURASIP-IEEE Region 8 International Symposium on VIPromCom, pages 345–350, 2002.
 Sebastiano Battiato, Gianpiero Blasi, Giovanni Gallo, Giuseppe Claudio Guarnera, and Gio- vanni Puglisi. A novel artificial mosaic generation technique driven by local gradient analysis. In ICCS ’08: Proceedings of the 8th international conference on Computational Science, Part II, pages 76–85, Berlin, Heidelberg, 2008. Springer-Verlag.
 Sebastiano Battiato, Gianpiero Di Blasi, Giovanni Maria Farinella, and Giovanni Gallo. A Novel Technique for Opus Vermiculatum Mosaic Rendering. In Joaquim Jorge and Vaclav Skala, editors, Proceedings of the 14th International Conference in Central Europe on Com- puter Graphics, Visualization and Computer Vision (WSCG 2006, February, 2006, Plzen, Czech Republic), pages 133–140, Plzen, 2006. University of West Bohemia, UNION Agency.
 Sebastiano Battiato, Gianpiero di Blasi, Giovanni Maria Farinella, and Giovanni Gallo. A survey of digital mosaic techniques. In Giovanni Gallo, Sebastiano Battiato, and Filippo Stanco, editors, Eurographics Italian Chapter Conference, pages 129–135. Eurographics, 2006.
 Gianpiero Di Blasi, Giovanni Gallo, and Petralia Maria. Puzzle image mosaic. In In proceed- ings of IASTED/VIIP2005, 2005.
 Gianpiero Di Blasi, Giovanni Gallo, and Maria Pia Petralia. Smart ideas for photomosaic rendering. In G. Gallo, S. Battiato, and F. Stanco, editors, Proceedings of Eurographics Italian Chapter Conference, 2006.
 Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 23(11):1222–1239, Nov 2001.
 Philip Brodatz. Textures: A Photographic Album for Artists and Designers. Dover Publica- tions, New York, 1966.
 Peter J. Burt and Edward H. Adelson. The Laplacian pyramid as a compact image code. Readings in computer vision: issues, problems, principles, and paradigms, pages 671–679, 1987.
118 Chad Carson, Serge Belongie, Hayit Greenspan, and Jitendra Malik. Blobworld: Image segmentation using expectation-maximization and its application to image querying. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24:1026–1038, 1999.
 Prasun Choudhury and Jack Tumblin. The trilateral filter for high contrast images and meshes. In SIGGRAPH ’05: ACM ACM Transactions on Graphics (TOG) 2005 Courses, page 5, New York, NY, USA, 2005. ACM.
 Christopher M. Christoudias. Synergism in low level vision. In ICPR ’02: Proceedings of the 16 th International Conference on Pattern Recognition (ICPR’02) Volume 4, page 40150, Washington, DC, USA, 2002. IEEE Computer Society.
 D. Comaniciu and P. Meer. Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):603–619, 2002.
 R. W. Connors, M. M. Trivedi, and C. A. Harlow. Segmentation of a high-resolution urban scene using texture operators. Computer Vision, Graphics, and Image Processing, 25(3):273– 310, 1984.
 A. Criminisi, P. Perez, and K. Toyama. Object removal by exemplar-based inpainting. In Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, volume 2, pages II–721–II–728 vol.2, June 2003.
 Ignacio Gomez de Liano. Dali. Rizzoli International Publications Inc., 712 Fifth Avenue/New York 10019, 1982.
 Andre Pieyre de Mandiargues. Arcimboldo the marvelous. Harry N. Abrams, Inc., New York, 1977.
 Doug DeCarlo and Anthony Santella. Stylization and abstraction of photographs. In SIG- GRAPH ’02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques, pages 769–776, New York, NY, USA, 2002. ACM.
 N. Diakopoulos, I. Essa, and R. Jain. Content based image synthesis. In Conference on Image and Video Retrieval (CIVR), pages 299–307, Dublin, Ireland, July 2004.
 E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271, December 1959.
 Yoshinori Dobashi, Toshiyuki Haga, Henry Johan, and Tomoyuki Nishita. A method for cre- ating mosaic images using Voronoi diagrams. In Proceedings of Eurographics 2002, September 2002.
 Iddo Drori, Daniel Cohen-Or, and Hezy Yeshurun. Fragment-based image completion. ACM Trans. Graph., 22(3):303–312, 2003.
 Qiang Du, Maria Emelianenko, and Lili Ju. Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM J. Numer. Anal., 44(1):102–119, 2006.
 Qiang Du, Faber V., and Gunzburger M. Centroidal Voronoi tessellations : Applications and algorithms. SIAM J. Numer. Anal., 41(4):637–676, 1999.
 Alexei A. Efros and William T. Freeman. Image quilting for texture synthesis and transfer. Proceedings of SIGGRAPH 2001, pages 341–346, August 2001.
 Alexei A. Efros and Thomas K. Leung. Texture synthesis by non-parametric sampling. In IEEE International Conference on Computer Vision, pages 1033–1038, Corfu, Greece, September 1999.
 Elmar Eisemann and Fr ́edo Durand. Flash photography enhancement via intrinsic relighting. ACM Trans. Graph., 23(3):673–678, 2004.
119 Gershon Elber and George Wolberg. Rendering traditional mosaics. The Visual Computer, 19:67–78, 2003.
 Zeev Farbman, Raanan Fattal, Dani Lischinski, and Richard Szeliski. Edge-preserving de- compositions for multi-scale tone and detail manipulation. ACM Trans. Graph., 27(3):1–10, 2008.
 Raanan Fattal, Maneesh Agrawala, and Szymon Rusinkiewicz. Multiscale shape and detail enhancement from multi-light image collections. In SIGGRAPH ’07: ACM ACM Transac- tions on Graphics (TOG) 2007 papers, page 51, New York, NY, USA, 2007. ACM.
 Geisa Martins Faustino and Luiz Henrique de Figueiredo. Simple adaptive mosaic effects. Computer Graphics and Image Processing, Brazilian Symposium on, 0:315–322, 2005.
 Adam Finkelstein and Marisa Range. Image mosaics. In Roger D. Hersch, Jacques Andr, and Heather Brown, editors, Electronic Publishing, Artistic Imaging and Digital Typography, Proceedings of the EP98 and RIDT98 Conferences, St Malo: March 30 - April 3, 1998, Lecture Notes in Computer Science Series, number 1375, pages 11–22. Springer-Verlag, 1998.
 Ran Gal, Olga Sorkine, Tiberiu Popa, Alla Sheffer, and Daniel Cohen-Or. 3D collage: expres- sive non-realistic modeling. In NPAR ’07: Proceedings of the 5th international symposium on Non-photorealistic animation and rendering, pages 7–14, New York, NY, USA, 2007. ACM.
 Bogdan Georgescu and Chris Christoudias. Edge detection and image segmentation system (EDISON)v1.1. Software, 2002.
 Bruce Gooch and Amy Ashurst Gooch. Non-Photorealistic Rendering. AK Peters, Ltd., 2001.
40] Derek Gores.Derek gores: Original artwork. Website, November http://www.derekgores.com/collage.php; Last accessed: 02/11/2010. 2009.
 Nouchine Hadjikhani, Kestutis Kveraga, Paulami Naik, and Seppo Ahlfors. Early (m170) activation of face-specific cortex by face-like objects. Neuroreport, 20(4):403–407, March 2009.
 Paul Haeberli. Paint by numbers: Abstract image representation. In Proceedings of SIG- GRAPH 1990, August 1990.
 Alejo Hausner. Simulating decorative mosaics. In SIGGRAPH ’01: Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 573–580, New York, NY, USA, 2001. ACM.
 James Hays and Alexei A. Efros. Scene completion using millions of photographs. In SIG- GRAPH ’07: ACM ACM Transactions on Graphics (TOG) 2007 papers, page 4, New York, NY, USA, 2007. ACM.
 I. Herman and D. Duke. Minimal graphics. Computer Graphics and Applications, IEEE, 21(6):18–21, Nov/Dec 2001.
 Aaron Hertzmann. Painterly rendering with curved brush strokes of multiple sizes. In SIG- GRAPH ’98: Proceedings of the 25th annual conference on Computer graphics and interactive techniques, pages 453–460, New York, NY, USA, 1998. ACM.
 Aaron Hertzmann. A survey of stroke-based rendering. Computer Graphics and Applications, IEEE, 23(4):70–81, July-Aug. 2003.
 Helen Hutton. The Technique of Collage, chapter Part one: Techniques, pages 11–13. B.T. Batsford Ltd, Watson-Guptill Publications, 1968.
120 Kohei Inoue and Kiichi Urahama. Generating stained glass-like images by bilateral Voronoi tessellation(<special section >computer graphics). The journal of the Institute of Image Information and Television Engineers, 61(10):1467–1471, 20071001.
 Charles E. Jacobs, Adam Finkelstein, and David H. Salesin. Fast multiresolution image query- ing. In SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pages 277–286, New York, NY, USA, 1995. ACM.
 Junhwan Kim and Fabio Pellacini. Jigsaw image mosaics. ACM Trans. Graph., 21(3):657–664, 2002.
 Junhwan Kim and Fabio Pellacini. Jigsaw image mosaics. In SIGGRAPH ’02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques, pages 657–664, New York, NY, USA, 2002. ACM.
 Ken Knowlton. Knowlton mosaics: Computer assisted portrait art by computer graphics pioneer Ken knowlton. Website, October 2009. http://www.knowltonmosaics.com/; Last accessed: 02/16/2010.
 I. Kokkinos, G. Evangelopoulos, and P. Maragos. Texture analysis and segmentation using modulation features, generative models, and weighted curve evolution. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 31(1):142–157, Jan. 2009.
 Nikos Komodakis. Image completion using global optimization. In CVPR ’06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 442–452, Washington, DC, USA, 2006. IEEE Computer Society.
 R. Kumar, H.S. Sawhney, J.C. Asmuth, A. Pope, and S. Hsu. Registration of video to geo-referenced imagery. In Pattern Recognition, 1998. Proceedings. Fourteenth International Conference on, volume 2, pages 1393 –1400 vol.2, August 1998.
 Peter Litwinowicz. Processing images and video for an impressionist effect. In SIGGRAPH ’97: Proceedings of the 24th annual conference on Computer graphics and interactive tech- niques, pages 407–414, New York, NY, USA, 1997. ACM Press/Addison-Wesley Publishing Co.
 Yu Liu, Olga Veksler, and Olivier Juan. Simulating classic mosaics with graph cuts. Lecture Notes in Computer Science, 4679/2007:55–70, 2007.
 M.A. Lozano and F. Escolano. Progress in Pattern Recognition, Speech and Image Analysis, chapter Two New Scale-Adapted Texture Descriptors for Image Segmentation, pages 137–144. Springer Berlin / Heidelberg, 2003.
 Trˆan-Quˆan Luong, Ankush Seth, Allison Klein, and Jason Lawrence. Isoluminant color pick- ing for non-photorealistic rendering. In GI ’05: Proceedings of Graphics Interface 2005, pages 233–240, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 2005. Canadian Human-Computer Communications Society.
 Lee Markosian, Michael A. Kowalski, Daniel Goldstein, Samuel J. Trychin, John F. Hughes, and Lubomir D. Bourdev. Real-time nonphotorealistic rendering. In SIGGRAPH ’97: Pro- ceedings of the 24th annual conference on Computer graphics and interactive techniques, pages 415–420, New York, NY, USA, 1997. ACM Press/Addison-Wesley Publishing Co.
 David Marr. Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. Henry Holt and Co., Inc., New York, NY, USA, 1982.
 P. Meer and B. Georgescu. Edge detection with embedded confidence. IEEE Trans. Pattern Anal. Mach. Intell., 23(12):1351–1365, 2001.
121 Grant Morrison(w) and Dave McKean(a). Arkham Asylum: A Serious House on Serious Earth, chapter 2, page 36. DC Comics, College Station, Texas, 1989.
 David Mould. Image-guided fracture. In GI ’05: Proceedings of Graphics Interface 2005, pages 219–226, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 2005. Canadian Human-Computer Communications Society.
 The Library of Congress. The Library of Congress’ photostream. Website, 2011. http: //www.flickr.com/photos/library_of_congress/; Last accessed: 02/18/2010.
 Aude Oliva and Antonio Torralba. Building the gist of a scene: the role of global image features in recognition. Progress in brain research, 155:23–36, 2006.
 Aude Oliva, Antonio Torralba, and Philippe G. Schyns. Hybrid images. ACM Trans. Graph., 25(3):527–532, 2006.
 Jeff Orchard and Craig S. Kaplan. Cut-out image mosaics. In NPAR ’08: Proceedings of the 6th international symposium on Non-photorealistic animation and rendering, pages 79–87, New York, NY, USA, 2008. ACM.
 Alexandrina Orzan, Adrien Bousseau, Pascal Barla, and Jo ̈elle Thollot. Structure-preserving manipulation of photographs. In NPAR ’07: Proceedings of the 5th international symposium on Non-photorealistic animation and rendering, pages 103–110, New York, NY, USA, 2007. ACM.
 Sylvain Paris and Fr ́edo Durand. A fast approximation of the bilateral filter using a signal processing approach. Int. J. Comput. Vision, 81(1):24–52, 2009.
 Patrick P ́erez, Michel Gangnet, and Andrew Blake. Poisson image editing. ACM Trans. Graph., 22(3):313–318, 2003.
 P. Perona and J. Malik. Scale-space and edge detection using anisotropic diffusion. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 12(7):629–639, Jul 1990.
 Georg Petschnigg, Richard Szeliski, Maneesh Agrawala, Michael Cohen, Hugues Hoppe, and Kentaro Toyama. Digital photography with flash and no-flash image pairs. ACM Trans. Graph., 23(3):664–672, 2004.
 Fatih Porikli. Constant time O(1) bilateral filtering. Computer Vision and Pattern Recogni- tion, IEEE Computer Society Conference on, 0:1–8, 2008.
 David M. Regan. Human Perception of Objects: Early Visual Processing of Spatial Form Defined by Luminance, Color, Texture, Motion, and Binocular Disparity. Sinauer Associates, 2000.
 C. Rother, S. Kumar, V. Kolmogorov, and A. Blake. Digital tapestry [automatic image synthesis]. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 589–596 vol. 1, June 2005.
 Carsten Rother, Lucas Bordeaux, Youssef Hamadi, and Andrew Blake. Autocollage. ACM Trans. Graph., 25(3):847–852, 2006.
 Carsten Rother, Lucas Bordeaux, Youssef Hamadi, and Andrew Blake. Microsoft Autocollage 2008. Software, 2008.
 David Salomon. Data Compression: The Complete Reference, chapter Statistical Methods, page 47. Springer, 2004.
 Otmar Scherzer and Joachim Weickert. Relations between regularization and diffusion filter- ing. J. Math. Imaging Vis., 12(1):43–63, 2000.
122 Stefan Schlechtweg, Tobias Germer, and Thomas Strothotte. Renderbots: Multi-agent sys- tems for direct image generation. Computer Graphics Forum, 24(2):137–148, 2005.
 Philippe G. Schyns and Aude Oliva. From blobs to boundary edges: Evidence for time- and spatial-scale dependent scene recognition. Psychological Science, 5(4):195–200, 1994.
 Al Seckel. Masters of Deception: Escher, Dali & Artists of Optical Illusion. Sterling Pub- lishing Co., Inc., 387 Park Avenue South, New York, NY 10016, 2004.
 Michio Shiraishi and Yasushi Yamaguchi. An algorithm for automatic painterly rendering based on local source image approximation. In NPAR ’00: Proceedings of the 1st international symposium on Non-photorealistic animation and rendering, pages 53–58, New York, NY, USA, 2000. ACM.
 R. Silvers and M.Hawley. Photomosaics. Henry Holt and Co., 1997.
 Jack Sklansky. Image segmentation and feature extraction. Systems, Man and Cybernetics, IEEE Transactions on, 8(4):237–247, April 1978.
 Sara L. Su, Fr ́edo Durand, and Maneesh Agrawala. De-emphasis of distracting image regions using texture power maps. In APGV ’05: Proceedings of the 2nd symposium on Applied perception in graphics and visualization, pages 164–164, New York, NY, USA, 2005. ACM.
 Terrie Sultan. Chuck Close Prints: Process and Collaboration. Princeton University Press, 2003.
 William B. Thompson. Fundamentals of Computer Graphics, chapter Chapter 21: Visual Perception, pages 477–519. A K Peters, Ltd., 888 Worcester Street, Suite 230, Wellesley, MA 02482, 2 edition, 2005.
 C. Tomasi and R. Manduchi. Bilateral filtering for gray and color images. In Computer Vision, 1998. Sixth International Conference on, pages 839–846, Jan 1998.
 Nicholas Tran. Generating photomosaics: an empirical study. In SAC ’99: Proceedings of the 1999 ACM symposium on Applied computing, pages 105–109, New York, NY, USA, 1999. ACM.
 Mihran Tuceryan and Anil K. Jain. Handbook of Pattern Recognition and Computer Vision, chapter Chapter 2.1: Texture Analysis, pages 207–248. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 2 edition, 1998.
 Robert Ulichney. Digital Halftoning. The MIT Press, Cambridge, Massachusetts, 1987.
 Li-Yi Wei. Deterministic texture analysis and synthesis using tree structure vector quantiza- tion. In SIBGRAPI ’99: Proceedings of the XII Brazilian Symposium on Computer Graphics and Image Processing, pages 207–214, Washington, DC, USA, 1999. IEEE Computer Society.
 Li-Yi Wei and Marc Levoy. Fast texture synthesis using tree-structured vector quantization. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and in- teractive techniques, pages 479–488, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
 Holger Winnem ̈oller, Sven C. Olsen, and Bruce Gooch. Real-time video abstraction. ACM Trans. Graph., 25(3):1221–1226, 2006.
 R. Y. Wong and E. L. Hall. Sequential hierarchical scene matching. IEEE Trans. Comput., 27(4):359–366, 1978.
 Yue Zhang. On the use of CBIR in image mosaic generation. Technical Report TR 02-17, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, 2002.
123 Q. Zheng and R. Chellappa. A computational vision approach to image registration. In Pattern Recognition, 1992. Vol.I. Conference A: Computer Vision and Applications, Proceed- ings., 11th IAPR International Conference on, pages 193–197, August, September 1992.
 Barbara Zitov ́a and Jan Flusser. Image registration methods: a survey. Image and Vision Computing, 21(11):977 – 1000, 2003.