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

  • ©Brian Summa, Julien Tierny, and Valerio Pascucci




    Panorama weaving: fast and flexible seam processing



    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

ACM Digital Library Publication: