Geodesic image and video editing

Abstract

This article presents a new, unified technique to perform general edge-sensitive editing operations on n-dimensional images and videos efficiently.

The first contribution of the article is the introduction of a Generalized Geodesic Distance Transform (GGDT), based on soft masks. This provides a unified framework to address several edge-aware editing operations. Diverse tasks such as denoising and nonphotorealistic rendering are all dealt with fundamentally the same, fast algorithm. Second, a new Geodesic Symmetric Filter (GSF) is presented which imposes contrast-sensitive spatial smoothness into segmentation and segmentation-based editing tasks (cutout, object highlighting, colorization, panorama stitching). The effect of the filter is controlled by two intuitive, geometric parameters. In contrast to existing techniques, the GSF filter is applied to real-valued pixel likelihoods (soft masks), thanks to GGDTs and it can be used for both interactive and automatic editing. Complex object topologies are dealt with effortlessly. Finally, the parallelism of GGDTs enables us to exploit modern multicore CPU architectures as well as powerful new GPUs, thus providing great flexibility of implementation and deployment. Our technique operates on both images and videos, and generalizes naturally to n-dimensional data.

The proposed algorithm is validated via quantitative and qualitative comparisons with existing, state-of-the-art approaches. Numerous results on a variety of image and video editing tasks further demonstrate the effectiveness of our method.

References

1. Agarwala, A., Dontcheva, M., Agrawala, M., Druker, A., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. In Proceedings of ACM SIGGRAPH.
2. Bai, X. and Sapiro, G. 2007. A geodesic framework for fast interactive image and video segmentation and matting. In Proceedings of the IEEE International Conference on Computer Vision.
3. Borgefors, G. 1986. Distance transformations in digital images. In Proceedings of Conference on Computer Vision, Graphics and Image Processing.
4. Bousseau, A., Neyret, F., Thollot, J., and Salesin, D. 2007. Video watercolorization using bidirectional texture advection. In Proceedings of ACM SIGGRAPH.
5. Boykov, J. and Jolly, M.-P. 2001. Interactive graph cuts for optimal boundary and region segmentation of objects in n-D images. In Proceedings of the IEEE International Conference on Computer Vision.
6. Brown, M., Szeliski, R., and Winder, S. 2005. Multi-image matching using multi-scale oriented patches. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 510--517.
7. Buades, A., Coll, B., and Morel, J.-M. 2005. A non-local algorithm for image denoising. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
8. Chen, J., Paris, J., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. In Proceedings of ACM SIGGRAPH.
9. Couprie, C., Grady, L. amd Najman, L., and Talbot, H. 2009. Power watersheds: A new image segmentation framework extending graph cuts, random walker and optimal spanning forest. In Proceedings of the IEEE International Conference on Computer Vision.
10. Criminisi, A., Cross, G., Blake, A., and kolmogorov, V. 2006. Bilayer segmentation of live video. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
11. Criminisi, A., Sharp, T., and Blake, A. 2008. GeoS: Geodesic image segmentation. In Proceedings of the European Conference on Computer Vision.
12. Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.
13. Durand, F. and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. In Proceedings of ACM SIGGRAPH.
14. Fabbri, R., Costa, L., Torrelli, J., and Bruno, O. 2008. 2D euclidean distance transform algorithms: A comparative survey. ACM Comput. Surv. 40, 1.
15. Felsberg, M., Forssen, P.-E., and Scharr, H. 2006. Efficient robust smoothing of low-level signal features. IEEE Trans. Pattern Anal. Mach. Intell. 28, 2, 209--222.
16. Felzenszwalb, P. and Huttenlocher, D. P. 2004. Efficient belief propagation for early vision. Int. J. Comput. Vision 70, 1, 41--54.
17. Grady, L. 2006. Random walks for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 11.
18. Grady, L. and Sinop, A. K. 2008. Fast approximate random walker segmentation using eigenvector precomputation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
19. Heijmans, H. J. A. M. 1995. Mathematical morphology: A modern approach in image processing based on algebra and geometry. SIAM Rev. 37, 1, 1--36.
20. Jones, M., Baerentzen, J., and Sramek, M. 2006. 3D distance fields: a survey of techniques and applications. IEEE Trans. Visualiz. Comput. Graph. 12.
21. Juan, O. and Boykov, J. 2006. Active graph cuts. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
22. Kohli, P. and Torr, P. H. S. 2007. Dynamic graph cuts for efficient inference in Markov Random Fields. IEEE Trans. Pattern Anal. Mach. Intell. 29, 12, 2079--2088.
23. Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., and Rother, C. 2005. Bilayer segmentation of binocular stereo video. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
24. Kolmogorov, V. and Zabih, R. 2004. What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26, 2.
25. Kopf, J., Cohen, M., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM Trans. Graph. 26, 3.
26. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Trans. Graph.
27. Li, Y., Sun, J., Tang, C.-K., and H.-Y., S. 2004. Lazy snapping. ACM Trans. Graph. 23, 3.
28. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. ACM Trans. Graph. 25, 3, 646--653.
29. Liu, J., Sun, J., and Shum, H.-Y. 2009. Paint selection. ACM Trans. Graph. 28, 3.
30. Lombaert, H., Sun, Y., Grady, L., and Xu, C. 2005. A multilevel banded graph cuts method for fast image segmentation. In Proceedings of the IEEE International Conference on Computer Vision.
31. Luan, Q., Wen, F., Cohen-Or, D., Liang, L., Xu, Y. Q., and Shum, H. Y. 2007. Natural image colorization. In Proceedings of the Eurographics Symposium on Rendering. J. Kautz and S. Pattanaik. Eds. Eurographics.
32. Paris, S. and Durand, F. 2009. A fast approximation of the bilateral filter. Int. J. Comput. Vision.
33. Perona, P. and Malik, J. 1990. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7.
34. Roth, S. and Black, M. 2005. Fields of experts: A framework for learning image priors. In Proceedings of the IEEE Computer Conference on Vision and Pattern Recognition.
35. Rother, C., Kolmogorov, V., and Blake, A. 2004. GrabCut: Interactive foreground extraction using iterated graph cuts. In ACM Trans. Graph.
36. Sethian, J. A. 1999. Fast marching methods. SIAM Rev. 41, 2.
37. Shotton, J., Winn, J., Rother, C., and Criminisi, A. 2007. Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling appearance, shape and context. Int. J. Comput. Vision.
38. Sinop, A. and Grady, L. 2007. A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm. In Proceedings of the IEEE International Conference on Computer Vision.
39. Soille, P. 1999. Morphological Image Analysis. Springer.
40. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Trans. Graph. 25, 3, 1135--1143.
41. Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., and Rother, C. 2007. A comparative study of energy minimization methods for Markov Random Fields with smoothness-based priors. Int. J. Comput. Vision. 30, 6, 1068--1080.
42. Toivanen, P. J. 1996. New geodesic distance transforms for gray-scale images. Pattern Recogn. Lett. 17, 5, 437--450.
43. Tomasi, C. and Manduchi, R. 1998. Bilateral filtering for gray and color images. In Proceeding of the IEEE International Conference on Computer Vision. 839--846.
44. Wang, J., Bhat, P., Colburn, R. A., Agrawala, M., and Cohen, M. F. 2005. Interactive video cut out. ACM Trans. Graph. 24, 585--594.
45. Wang, J., Xu, Y., Shum, H.-Y., and Cohen, M. 2004. Video tooning. In Proceedings of ACM SIGGRAPH.
46. Weber, O., Devir, Y. S., Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2008. Parallel algorithms for approximation of distance maps on parametric surfaces. In Proceedings of ACM SIGGRAPH.
47. Weiss, B. 2006. Fast median and bilateral filtering. In ACM SIGGRAPH.
48. Weiss, Y. and Freeman, W. T. 2007. What makes a good model of natural images? In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
49. Winnemoller, H., Olsen, S. C., and Gooch, B. 2006. Real time video abstraction. In Proceedings of ACM SIGGRAPH.
50. Yatziv, L., Bartesaghi, A., and Sapiro, G. 2006. O(n) implementation of the fast marching algorithm. J. Computat. Phys. 212, 393--399.
51. Yatziv, L. and Sapiro, G. 2006. Fast image and video colorization using chrominance blending. IEEE Trans. Image Proces. 15, 5.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision problems

        • Image segmentation

        • Video segmentation

  • Computer graphics

    • Image manipulation

    • Rendering