“AutoCollage” by Rother, Bordeaux, Hamadi and Blake

The paper defines an automatic procedure for constructing a visually appealing collage from a collection of input images. The aim is that the resulting collage should be representative of the collection, summarising its main themes. It is also assembled largely seamlessly, using graph-cut, Poisson blending of alpha-masks, to hide the joins between input images. This paper makes several new contributions. Firstly, we show how energy terms can be included that: encourage the selection of a representative set of images; that are sensitive to particular object classes; that encourage a spatially efficient and seamless layout. Secondly the resulting optimization poses a search problem that, on the face of it, is computationally in-feasible. Rather than attempt an expensive, integrated optimization procedure, we have developed a sequence of optimization steps, from static ranking of images, through region of interest optimization, optimal packing by constraint satisfaction, and lastly graph-cut alpha-expansion. To illustrate the power of AutoCollage, we have used it to create collages of many home photo sets; we also conducted a user study in which AutoCollage outperformed competitive methods.

1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. Graph. 23, 3, 294–302. Google ScholarDigital Library
2. Aggoun, A., and Beldiceanu, N. 1993. Extending CHIP in order to solve complex scheduling and placement problems. Mathematical Computer Modelling 17, 7, 57–73.Google ScholarDigital Library
3. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. on Pattern Analysis and Machine Intelligence 23, 11. Google ScholarDigital Library
4. Crow, F. 1984. Summed area tables for texture mapping. In Proc. ACM Siggraph, ACM, 207–212. Google ScholarDigital Library
5. Dechter, R. 2003. Constraint Processing. Morgan Kaufmann. Google ScholarDigital Library
6. Diakopoulos, N., and Essa, I. 2005. Mediating photo collage authoring. In UIST, CD–ROM. Google ScholarDigital Library
7. Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. Proc. ACM Siggraph. Google ScholarDigital Library
8. Itti, L., Koch, C., and Niebur, E. 1998. A model of saliency based visual attention for rapid scene analysis. IEEE Trans. on Pattern Analysis and Machine Intelligence 20, 11. Google ScholarDigital Library
9. Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. In Proc. ACM Siggraph, ACM, 657–664. Google ScholarDigital Library
10. Kwatra, V., Schodl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: image and video synthesis using graph cuts. ACM Trans. Graph. 22, 3, 277–286. Google ScholarDigital Library
11. Marriott, K., and Stuckey, P. 1998. Programming with Constraints. The MIT Press.Google Scholar
12. Perez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318. Google ScholarDigital Library
13. Rother, C., Kolmogorov, V., and Blake, A. 2004. Grabcut: Interactive foreground extraction using iterated graph cuts. ACM Trans. Graph. 23, 3, 309–314. Google ScholarDigital Library
14. Rother, C., Kumar, S., Kolmogorov, V., and Blake, A. 2005. Digital tapestry. In Proc. Conf. Comp. Vision and Pattern Recog. Google ScholarDigital Library
15. Shotton, J., Winn, J., Rother, C., and Criminisi, A. 2006. Textonboost: Joint appearance, shape and context modelling for multi-class object recognition and segmentation. In Europ. Conf. Comp. Vision. Google ScholarDigital Library
16. Suh, B., Ling, H., Bederson, B. B., and Jacobs, D. W. 2005. Automatic thumbnail cropping and its effectiveness. In UIST, CD–ROM. Google ScholarDigital Library
17. Viola, P., and Jones, M. 2001. Rapid object detection using a boosted cascade of simple features. In Proc. Conf. Comp. Vision and Pat. Recog.Google Scholar
18. Waltz, D. 1975. Understanding line drawings of scenes with shadows. In The Psychology of Vision, W. P. H., Ed. McGraw-Hill, New York.Google Scholar