Image smoothing via L₀ gradient minimization

Abstract

We present a new image editing method, particularly effective for sharpening major edges by increasing the steepness of transition while eliminating a manageable degree of low-amplitude structures. The seemingly contradictive effect is achieved in an optimization framework making use of L₀ gradient minimization, which can globally control how many non-zero gradients are resulted in to approximate prominent structure in a sparsity-control manner. Unlike other edge-preserving smoothing approaches, our method does not depend on local features, but instead globally locates important edges. It, as a fundamental tool, finds many applications and is particularly beneficial to edge extraction, clip-art JPEG artifact removal, and non-photorealistic effect generation.

References

1. Arbelaez, P., Maire, M., Fowlkes, C., and Malik, J. 2011. Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 33, 898--916.
2. Bae, S., and Durand, F. 2007. Defocus magnification. Comput. Graph. Forum 26, 3, 571--579.
3. Bae, S., Paris, S., and Durand, F. 2006. Two-scale tone management for photographic look. ACM Trans. Graph. 25, 3, 637--645.
4. Baek, J., and Jacobs, D. E. 2010. Accelerating spatially varying gaussian filters. ACM Trans. Graph..
5. Black, M. J., Sapiro, G., Marimont, D. H., and Heeger, D. 1998. Robust anisotropic diffusion. IEEE Transactions on Image Processing 7, 3, 421--432.
6. Blake, A., and Zisserman, A. 1987. Visual reconstruction. The MIT Press.
7. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 11, 1222--1239.
8. Chen, J., Paris, S., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. ACM Trans. Graph. 26, 3, 103.
9. Choudhury, P., and Tumblin, J. 2003. The trilateral filter for high contrast images and meshes. In Rendering Techniques, 186--196.
10. Comaniciu, D., and Meer, P. 2002. Mean shift: A robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24, 5, 603--619.
11. Criminisi, A., Sharp, T., Rother, C., and Pérez, P. 2010. Geodesic image and video editing. ACM Trans. Graph. 29, 5, 134.
12. Dabov, K., Foi, A., Katkovnik, V., and Egiazarian, K. O. 2007. Image denoising by sparse 3-d transform-domain collaborative filtering. IEEE Transactions on Image Processing 16, 8, 2080--2095.
13. DeCarlo, D., and Santella, A. 2002. Stylization and abstraction of photographs. ACM Trans. Graph. 21, 3, 769--776.
14. Donoho, D. 2006. Compressed sensing. IEEE Transactions on Information Theory 52, 4, 1289--1306.
15. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. ACM Trans. Graph. 21, 3, 257--266.
16. Farbman, Z., Fattal, R., Lischinski, D., and Szeliski, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Trans. Graph. 27, 3.
17. Farbman, Z., Fattal, R., and Lischinski, D. 2010. Diffusion maps for edge-aware image editing. ACM Trans. Graph..
18. Fattal, R., Agrawala, M., and Rusinkiewicz, S. 2007. Multiscale shape and detail enhancement from multi-light image collections. ACM Trans. Graph. 26, 3, 51.
19. Fattal, R. 2009. Edge-avoiding wavelets and their applications. ACM Trans. Graph. 28, 3.
20. Kass, M., and Solomon, J. 2010. Smoothed local histogram filters. ACM Trans. Graph. 29, 4.
21. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Trans. Graph. 23, 3, 689--694.
22. Levin, A., Fergus, R., Durand, F., and Freeman, W. T. 2007. Image and depth from a conventional camera with a coded aperture. ACM Trans. Graph. 26, 3, 70.
23. Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazy snapping. ACM Trans. Graph. 23, 3, 303--308.
24. Li, Y., Sharan, L., and Adelson, E. H. 2005. Compressing and companding high dynamic range images with subband architectures. ACM Trans. Graph. 24, 3, 836--844.
25. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. ACM Trans. Graph. 25, 3, 646--653.
26. Liu, J., Sun, J., and Shum, H.-Y. 2009. Paint selection. ACM Trans. Graph. 28, 3.
27. Mairal, J., Bach, F., Ponce, J., Sapiro, G., and Zisserman, A. 2009. Non-local sparse models for image restoration. In ICCV, 2272--2279.
28. Maji, S., Vishnoi, N., and Malik, J. 2011. Biased normalized cuts. In CVPR.
29. Paris, S., and Durand, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In ECCV (4), 568--580.
30. Paris, S., Hasinoff, S. W., and Kautz, J. 2011. Local laplacian filters: Edge-aware image processing with a laplacian pyramid. ACM Trans. Graph..
31. Perona, P., and Malik, J. 1990. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7, 629--639.
32. Rother, C., Kolmogorov, V., and Blake, A. 2004. "grab-cut": interactive foreground extraction using iterated graph cuts. ACM Trans. Graph. 23, 3, 309--314.
33. Rudin, L., Osher, S., and Fatemi, E. 1992. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena 60, 1--4, 259--268.
34. Subr, K., Soler, C., and Durand, F. 2009. Edge-preserving multiscale image decomposition based on local extrema. ACM Trans. Graph. 28, 5.
35. Tomasi, C., and Manduchi, R. 1998. Bilateral filtering for gray and color images. In ICCV, 839--846.
36. Tumblin, J., and Turk, G. 1999. Lcis: A boundary hierarchy for detail-preserving contrast reduction. In SIGGRAPH, 83--90.
37. Wang, Z., Bovik, A. C., Sheikh, H. R., and Simoncelli, E. P. 2004. Image quality assessment: from error visibility to structural similarity. IEEE Transactions on Image Processing 13, 4, 600--612.
38. Wang, G., Wong, T.-T., and Heng, P.-A. 2006. Deringing cartoons by image analogies. ACM Trans. Graph. 25, 4, 1360--1379.
39. Wang, Y., Yang, J., Yin, W., and Zhang, Y. 2008. A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sciences 1, 3, 248--272.
40. Weiss, B. 2006. Fast median and bilateral filtering. ACM Trans. Graph. 25, 3, 519--526.
41. Winnemöller, H., Olsen, S. C., and Gooch, B. 2006. Realtime video abstraction. ACM Trans. Graph. 25, 3, 1221--1226.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision tasks

  • Computer graphics

    • Image manipulation