“Panorama weaving: fast and flexible seam processing” by Summa, Tierny and Pascucci

A fundamental step in stitching several pictures to form a larger mosaic is the computation of boundary seams that minimize the visual artifacts in the transition between images. Current seam computation algorithms use optimization methods that may be slow, sequential, memory intensive, and prone to finding suboptimal solutions related to local minima of the chosen energy function. Moreover, even when these techniques perform well, their solution may not be perceptually ideal (or even good). Such an inflexible approach does not allow the possibility of user-based improvement. This paper introduces the Panorama Weaving technique for seam creation and editing in an image mosaic. First, Panorama Weaving provides a procedure to create boundaries for panoramas that is fast, has low memory requirements and is easy to parallelize. This technique often produces seams with lower energy than the competing global technique. Second, it provides the first interactive technique for the exploration of the seam solution space. This powerful editing capability allows the user to automatically extract energy minimizing seams given a sparse set of constraints. With a variety of empirical results, we show how Panorama Weaving allows the computation and editing of a wide range of digital panoramas including unstructured configurations.

1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S. M., Colburn, A., Curless, B., Salesin, D., and Cohen, M. F. 2004. Interactive digital photomontage. ACM Trans. Graph 23, 3, 294–302. Google ScholarDigital Library
2. Agarwala, A., Zheng, K. C., Pal, C., Agrawala, M., Cohen, M. F., Curless, B., Salesin, D., and Szeliski, R. 2005. Panoramic video textures. ACM Trans. Graph 24, 3, 821–827. Google ScholarDigital Library
3. Agarwala, A., Agrawala, M., Cohen, M. F., Salesin, D., and Szeliski, R. 2006. Photographing long scenes with multi-viewpoint panoramas. ACM Trans. Graph 25, 3, 853–861. Google ScholarDigital Library
4. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Trans. Graph 26, 3, 94. Google ScholarDigital Library
5. Boykov, Y. Y., and Jolly, M. P. 2001. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. In ICCV, I: 105–112.Google Scholar
6. Boykov, Y., and Kolmogorov, V. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell 26, 9, 1124–1137. Google ScholarDigital Library
7. Boykov, Y. Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence 23, 11 (Nov.), 1222–1239. Google ScholarDigital Library
8. Chandran, S. L., Francis, M., and Sivadasan, N. 2006. Geometric representations of graphs in low dimension.Google Scholar
9. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. Graph 22, 3, 287–294. Google ScholarDigital Library
10. Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. MIT Press, Cambridge. Google ScholarDigital Library
11. Correa, C. D., and Ma, K.-L. 2010. Dynamic video narratives. ACM Trans. Graph 29, 4. Google ScholarDigital Library
12. Davis, J. E. 1998. Mosaics of scenes with moving objects. In CVPR, 354–360. Google ScholarDigital Library
13. Delong, A., and Boykov, Y. 2008. A scalable graph-cut algorithm for N-D grids. In CVPR, IEEE Computer Society.Google Scholar
14. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271.Google ScholarDigital Library
15. Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In SIGGRAPH, 341–346. Google ScholarDigital Library
16. Freedman, D., and Zhang, T. 2005. Interactive graph cut based segmentation with shape priors. In CVPR, I: 755–762. Google ScholarDigital Library
17. Gracias, N. R. E., Mahoor, M. H., Negahdaripour, S., and Gleason, A. C. R. 2009. Fast image blending using watersheds and graph cuts. Image and Vision Computing 27, 5 (Apr.), 597–607. Google ScholarDigital Library
18. Hassin, R. 1981. Maximum flow in (s, t)-planar networks. Inform. Proc. Lett. 13, 107.Google ScholarCross Ref
19. Kazhdan, M. M., and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph 27, 3. Google ScholarDigital Library
20. Kazhdan, M. M., Surendran, D., and Hoppe, H. 2010. Distributed gradient-domain processing of planar and spherical images. ACM Trans. Graph 29, 2. Google ScholarDigital Library
21. Kolmogorov, V., and Zabih, R. 2004. What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell 26, 2, 147–159. Google ScholarDigital Library
22. Kopf, J., Uyttendaele, M., Deussen, O., and Cohen, M. F. 2007. Capturing and viewing gigapixel images. ACM Trans. Graph 26, 3, 93. Google ScholarDigital Library
23. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM Trans. Graph 22, 3 (July), 277–286. Google ScholarDigital Library
24. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In ECCV, Vol IV: 377–389.Google Scholar
25. Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazy snapping. ACM Trans. Graph 23, 3, 303–308. Google ScholarDigital Library
26. Liu, J., and Sun, J. 2010. Parallel graph-cuts by adaptive bottom-up merging. In CVPR, IEEE, 2181–2188.Google Scholar
27. Lombaert, H., Sun, Y. Y., Grady, L., and Xu, C. Y. 2005. A multilevel banded graph cuts method for fast image segmentation. In ICCV, I: 259–265. Google ScholarDigital Library
28. Milgram, D. L. 1975. Computer methods for creating photomosaics. IEEE Trans. Computer 23, 1113–1119. Google ScholarDigital Library
29. Milgram, D. L. 1977. Adaptive techniques for photomosaicking. IEEE Trans. Computer 26, 1175–1180. Google ScholarDigital Library
30. Nagahashi, T., Fujiyoshi, H., and Kanade, T. 2007. Image segmentation using iterated graph cuts based on multi-scale smoothing. In ACCV, II: 806–816. Google ScholarDigital Library
31. Peleg, S., Rousso, B., Acha, A. R., and Zomet, A. 2000. Mosaicing on adaptive manifolds. IEEE Trans. Pattern Analysis and Machine Intelligence 22, 10 (Oct.), 1144–1154. Google ScholarDigital Library
32. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph 22, 3, 313–318. Google ScholarDigital Library
33. PTgui, 2012. http://www.ptgui.com.Google Scholar
34. Roberts, F. 1969. On the boxicity and cubicity of a graph. Recent Progress in Combinatorics.Google Scholar
35. Rosgen, B., and Stewart, L. 2007. Complexity results on graphs with few cliques. Discrete Mathematics & Theoretical Computer Science 9, 1.Google Scholar
36. 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
37. Shum, H. Y., and Szeliski, R. S. 1998. Construction and refinement of panoramic mosaics with global and local alignment. In ICCV, 953–956. Google ScholarDigital Library
38. Szeliski, R. S. 1996. Video mosaics for virtual environments. IEEE Computer Graphics and Applications 16, 2 (Mar.), 22–30. Google ScholarDigital Library
39. Szeliski, R. 2006. Image alignment and stitching: A tutorial. Foundations and Trends in Computer Graphics and Vision 2, 1. Google ScholarDigital Library
40. Uyttendaele, M. T., Eden, A., and Szeliski, R. S. 2001. Eliminating ghosting and exposure artifacts in image mosaics. II:509–516.Google Scholar
41. Vineet, V., and Narayanan, P. J. 2008. CUDA cuts: Fast graph cuts on the GPU. In Computer Vision on GPU, 1–8.Google Scholar
42. Wood, D. N., Finkelstein, A., Hughes, J. F., Thayer, C. E., and Salesin, D. 1997. Multiperspective panoramas for cel animation. In SIGGRAPH, 243–250. Google ScholarDigital Library
43. Xu, D., Chen, Y., Xiong, Y., Qiao, C., and He, X. 2006. On the complexity of/and algorithms for finding shortest path with a disjoint counterpart. IEEE/ACM Trans. on Networking 14, 1, 147–158. Google ScholarDigital Library