research-article

Geodesic image and video editing

Authors: Antonio Criminisi, Toby Sharp, Carsten Rother, Patrick P'erezAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 29, Issue 5

Article No.: 134, Pages 1 - 15

https://doi.org/10.1145/1857907.1857910

Published: 05 November 2010 Publication History

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.

Supplementary Material

MP4 File (tp104_11.mp4)

Download
82.94 MB

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.

Digital Library

[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.

Digital Library

[4]

Bousseau, A., Neyret, F., Thollot, J., and Salesin, D. 2007. Video watercolorization using bidirectional texture advection. In Proceedings of ACM SIGGRAPH.

Digital Library

[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.

Digital Library

[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.

Digital Library

[8]

Chen, J., Paris, J., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. In Proceedings of ACM SIGGRAPH.

Digital Library

[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.

Digital Library

[11]

Criminisi, A., Sharp, T., and Blake, A. 2008. GeoS: Geodesic image segmentation. In Proceedings of the European Conference on Computer Vision.

Digital Library

[12]

Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.

Digital Library

[13]

Durand, F. and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. In Proceedings of ACM SIGGRAPH.

Digital Library

[14]

Fabbri, R., Costa, L., Torrelli, J., and Bruno, O. 2008. 2D euclidean distance transform algorithms: A comparative survey. ACM Comput. Surv. 40, 1.

Digital Library

[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.

Digital Library

[16]

Felzenszwalb, P. and Huttenlocher, D. P. 2004. Efficient belief propagation for early vision. Int. J. Comput. Vision 70, 1, 41--54.

Digital Library

[17]

Grady, L. 2006. Random walks for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 11.

Digital Library

[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.

Digital Library

[20]

Jones, M., Baerentzen, J., and Sramek, M. 2006. 3D distance fields: a survey of techniques and applications. IEEE Trans. Visualiz. Comput. Graph. 12.

Digital Library

[21]

Juan, O. and Boykov, J. 2006. Active graph cuts. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.

Digital Library

[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.

Digital Library

[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.

Digital Library

[24]

Kolmogorov, V. and Zabih, R. 2004. What energy functions can be minimized via graph cuts&quest; IEEE Trans. Pattern Anal. Mach. Intell. 26, 2.

Digital Library

[25]

Kopf, J., Cohen, M., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM Trans. Graph. 26, 3.

Digital Library

[26]

Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Trans. Graph.

Digital Library

[27]

Li, Y., Sun, J., Tang, C.-K., and H.-Y., S. 2004. Lazy snapping. ACM Trans. Graph. 23, 3.

Digital Library

[28]

Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. ACM Trans. Graph. 25, 3, 646--653.

Digital Library

[29]

Liu, J., Sun, J., and Shum, H.-Y. 2009. Paint selection. ACM Trans. Graph. 28, 3.

Digital Library

[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.

Digital Library

[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.

Digital Library

[32]

Paris, S. and Durand, F. 2009. A fast approximation of the bilateral filter. Int. J. Comput. Vision.

Digital Library

[33]

Perona, P. and Malik, J. 1990. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7.

Digital Library

[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.

Digital Library

[35]

Rother, C., Kolmogorov, V., and Blake, A. 2004. GrabCut: Interactive foreground extraction using iterated graph cuts. In ACM Trans. Graph.

Digital Library

[36]

Sethian, J. A. 1999. Fast marching methods. SIAM Rev. 41, 2.

Digital Library

[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.

Digital Library

[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.

Digital Library

[40]

Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Trans. Graph. 25, 3, 1135--1143.

Digital Library

[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.

Digital Library

[42]

Toivanen, P. J. 1996. New geodesic distance transforms for gray-scale images. Pattern Recogn. Lett. 17, 5, 437--450.

Digital Library

[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.

Digital Library

[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.

Digital Library

[45]

Wang, J., Xu, Y., Shum, H.-Y., and Cohen, M. 2004. Video tooning. In Proceedings of ACM SIGGRAPH.

Digital Library

[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.

Digital Library

[47]

Weiss, B. 2006. Fast median and bilateral filtering. In ACM SIGGRAPH.

Digital Library

[48]

Weiss, Y. and Freeman, W. T. 2007. What makes a good model of natural images&quest; 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.

Digital Library

[50]

Yatziv, L., Bartesaghi, A., and Sapiro, G. 2006. O(n) implementation of the fast marching algorithm. J. Computat. Phys. 212, 393--399.

Digital Library

[51]

Yatziv, L. and Sapiro, G. 2006. Fast image and video colorization using chrominance blending. IEEE Trans. Image Proces. 15, 5.

Digital Library

Cited By

Smolka BKusnik DSmolka MKawulok MCyganek B(2024)Color image denoising: a hybrid approach for mixed Gaussian and impulsive noiseReal-Time Image Processing and Deep Learning 202410.1117/12.3013424(6)Online publication date: 7-Jun-2024
https://doi.org/10.1117/12.3013424
Shi QLi YDi HWu E(2024)Self-Supervised Interactive Image SegmentationIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.329506234:8(6797-6808)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TCSVT.2023.3295062
Xi LChen WWu XLiu ZLi Z(2024)Online Unsupervised Video Object Segmentation via Contrastive Motion ClusteringIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.328887834:2(995-1006)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TCSVT.2023.3288878
Show More Cited By

Index Terms

Geodesic image and video editing
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Image segmentation
        Video segmentation
  2. Computer graphics
    1. Image manipulation
    2. Rendering

Recommendations

An Improved Image Denoising and Segmentation Approach for Detecting Tumor from 2-D MRI Brain Images
ACSAT '12: Proceedings of the 2012 International Conference on Advanced Computer Science Applications and Technologies

Image denoising and segmentation are the two most challenging fields in medical image processing particularly when it is application specific. The presence of noise not only degrades the visual quality but also immensely affects the accuracies of ...
Segmentation of brain magnetic resonance images through morphological operators and geodesic distance

When segmenting magnetic resonance (MR) images, a wide range of useless information arises, which has to be discarded as a step prior to classifying the different cerebral cortex areas. To obtain effective results during the classification process, it ...
Authoring and animating painterly characters

Artists explore the visual style of animated characters through 2D concept art, since it affords them a nearly unlimited degree of creative freedom. Realizing the desired visual style, however, within the 3D character animation pipeline is often ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 29, Issue 5

October 2010

58 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1857907

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2010

Accepted: 01 August 2010

Revised: 01 April 2010

Received: 01 September 2008

Published in TOG Volume 29, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

148
Total Citations
View Citations
1,497
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Smolka BKusnik DSmolka MKawulok MCyganek B(2024)Color image denoising: a hybrid approach for mixed Gaussian and impulsive noiseReal-Time Image Processing and Deep Learning 202410.1117/12.3013424(6)Online publication date: 7-Jun-2024
https://doi.org/10.1117/12.3013424
Shi QLi YDi HWu E(2024)Self-Supervised Interactive Image SegmentationIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.329506234:8(6797-6808)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TCSVT.2023.3295062
Xi LChen WWu XLiu ZLi Z(2024)Online Unsupervised Video Object Segmentation via Contrastive Motion ClusteringIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.328887834:2(995-1006)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TCSVT.2023.3288878
Yang YSun YGao WWang XZeng L(2024)Bilateral regularized optimization model for edge-preserving image smoothingImage and Vision Computing10.1016/j.imavis.2024.105031146(105031)Online publication date: Jun-2024
https://doi.org/10.1016/j.imavis.2024.105031
Yang YMa WGao WZeng LPan Z(2024)Hyperbolic tangent penalty function for edge-preserving image filteringDigital Signal Processing10.1016/j.dsp.2024.104591153(104591)Online publication date: Oct-2024
https://doi.org/10.1016/j.dsp.2024.104591
Bu PWang HYang TZhao H(2024)Linear time manageable edge-aware filtering on complementary tree structuresComputers & Graphics10.1016/j.cag.2023.12.006118(133-145)Online publication date: Feb-2024
https://doi.org/10.1016/j.cag.2023.12.006
Acharjya PJoardar SKoley SBarman S(2023)A Study on Evaluation and Analysis of Edge Detection OperatorsMeta-Learning Frameworks for Imaging Applications10.4018/978-1-6684-7659-8.ch004(65-102)Online publication date: 20-Oct-2023
https://doi.org/10.4018/978-1-6684-7659-8.ch004
Lin CQiu CWu CFeng SHuang M(2023)Adaptive Noise Detector and Partition Filter for Image RestorationComputers, Materials & Continua10.32604/cmc.2023.03624975:2(4317-4340)Online publication date: 2023
https://doi.org/10.32604/cmc.2023.036249
Zhang QJiang HNie YZheng W(2023)Pyramid Texture FilteringACM Transactions on Graphics10.1145/359212042:4(1-11)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592120
Zhou TPorikli FCrandall DVan Gool LWang W(2023)A Survey on Deep Learning Technique for Video SegmentationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.322557345:6(7099-7122)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TPAMI.2022.3225573
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents