“Diffusion maps for edge-aware image editing”
Conference:
Type(s):
Title:
- Diffusion maps for edge-aware image editing
Session/Category Title: Image & video editing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Edge-aware operations, such as edge-preserving smoothing and edge-aware interpolation, require assessing the degree of similarity between pairs of pixels, typically defined as a simple monotonic function of the Euclidean distance between pixel values in some feature space. In this work we introduce the idea of replacing these Euclidean distances with diffusion distances, which better account for the global distribution of pixels in their feature space. These distances are approximated using diffusion maps: a set of the dominant eigenvectors of a large affinity matrix, which may be computed efficiently by sampling a small number of matrix columns (the Nyström method). We demonstrate the benefits of using diffusion distances in a variety of image editing contexts, and explore the use of diffusion maps as a tool for facilitating the creation of complex selection masks. Finally, we present a new analysis that establishes a connection between the spatial interaction range between two pixels, and the number of samples necessary for accurate Nyström approximations.
References:
1. An, X., and Pellacini, F. 2008. AppProp: all-pairs appearance-space edit propagation. ACM Trans. Graph. 27, 3, Article 40. Google ScholarDigital Library
2. Belkin, M., and Niyogi, P. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation 15, 6 (June), 1373–1396. Google ScholarDigital Library
3. Black, M. J., Sapiro, G., Marimont, D. H., and Heeger, D. 1998. Robust anisotropic diffusion. IEEE Trans. Image Proc. 7, 3 (Mar.), 421–432. Google ScholarDigital Library
4. Chang, H., and Yeung, D.-Y. 2008. Robust path-based spectral clustering. Pattern Recogn. 41, 1, 191–203. Google ScholarDigital Library
5. Chen, J., Paris, S., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. ACM Trans. Graph. 26, 3 (July), Article 103. Google ScholarDigital Library
6. Coifman, R., and Lafon, S. 2006. Diffusion maps. Applied and Computational Harmonic Analysis 21, 1, 5–30.Google ScholarCross Ref
7. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. ACM Trans. Graph. 21, 3 (July), 257–266. Google ScholarDigital Library
8. 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, Article 67. Google ScholarDigital Library
9. Fattal, R., Agrawala, M., and Rusinkiewicz, S. 2007. Multiscale shape and detail enhancement from multi-light image collections. ACM Trans. Graph. 26, 3 (July), Article 51. Google ScholarDigital Library
10. Fattal, R. 2009. Edge-avoiding wavelets and their applications. ACM Trans. Graph. 28, 3 (August), Article 22. Google ScholarDigital Library
11. Fischer, B., and Buhmann, J. M. 2003. Path-based clustering for grouping of smooth curves and texture segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 25, 4, 513–518. Google ScholarDigital Library
12. Fowlkes, C., Belongie, S., Chung, F., and Malik, J. 2004. Spectral grouping using the Nyström method. IEEE Trans. Pattern Anal. Mach. Intell. 26, 2, 214–225. Google ScholarDigital Library
13. Golub, G. H., and Van Loan, C. F. 1998. Matrix Computations, 2nd ed. The John Hopkins University Press.Google Scholar
14. Grady, L., and Sinop, A. K. 2008. Fast approximate random walker segmentation using eigenvector precomputation. In Proc. IEEE CVPR, IEEE Computer Society.Google Scholar
15. Grady, L. 2006. Random walks for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28, 11 (Nov.), 1768–1783. Google ScholarDigital Library
16. Kopf, J., Cohen, M. F., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM Trans. Graph. 26, 3, Article 96. Google ScholarDigital Library
17. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Trans. Graph. 23, 3, 689–694. Google ScholarDigital Library
18. Levin, A., Lischinski, D., and Weiss, Y. 2008. A closed-form solution to natural image matting. IEEE Trans. Pattern Anal. Mach. Intell. 30, 2, 228–242. Google ScholarDigital Library
19. Levin, A., Rav-Acha, A., and Lischinski, D. 2008. Spectral matting. IEEE Trans. Pattern Anal. Mach. Intell. 30, 10, 1699–1712. Google ScholarDigital Library
20. Li, Y., Adelson, E. H., and Agarwala, A. 2008. Scribble-Boost: adding classification to edge-aware interpolation of local image and video adjustments. Computer Graphics Forum 27, 4 (June), 1255–1264. Google ScholarDigital Library
21. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. ACM Trans. Graph. 25, 3 (July), 646–653. Google ScholarDigital Library
22. Malik, J., Belongie, S., Leung, T., and Shi, J. 2001. Contour and texture analysis for image segmentation. Int. J. Comput. Vision 43, 1, 7–27. Google ScholarDigital Library
23. Meila, M., and Shi, J. 2001. A random walks view of spectral segmentation. In Proc. AISTATS 2001.Google Scholar
24. Nadler, B., Lafon, S., Coifman, R., and Kevrekidis, I. 2005. Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators. Neural Information Processing Systems (NIPS) 18.Google Scholar
25. Omer, I., and Werman, M. 2006. The bottleneck geodesic: Computing pixel affinity. In Proc. IEEE CVPR, IEEE Computer Society, 1901–1907. Google ScholarDigital Library
26. Oppenheim, A. V., and Schafer, R. W. 1975. Digital Signal Processing. Prentice Hall.Google Scholar
27. Paris, S., and Durand, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In Proc. ECCV ’06, IEEE, IV: 568–580. Google ScholarDigital Library
28. Perona, P., and Malik, J. 1990. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7 (July), 629–639. Google ScholarDigital Library
29. Rhemann, C., Rother, C., Wang, J., Gelautz, M., Kohli, P., and Rott, P. 2009. A perceptually motivated online benchmark for image matting. In CVPR, IEEE, 1826–1833.Google Scholar
30. Roweis, S. T., and Saul, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500, 2323–2326.Google Scholar
31. Shi, J., and Malik, J. 1997. Normalized cuts and image segmentation. In Proc. IEEE CVPR, IEEE, 731–737. Google ScholarDigital Library
32. Singer, A., Shkolnisky, Y., and Nadler, B. 2009. Diffusion interpretation of nonlocal neighborhood filters for signal denoising. SIAM J. Imag. Sciences 2, 1, 118–139. Google ScholarDigital Library
33. Subr, K., Soler, C., and Durand, F. 2009. Edge-preserving multiscale image decomposition based on local extrema. ACM Trans. Graph. 28, 5 (December), Article 147. Google ScholarDigital Library
34. Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Trans. Pattern Anal. Mach. Intell. 12, 6, 513–528. Google ScholarDigital Library
35. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Trans. Graph. 25, 3, 1135–1143. Google ScholarDigital Library
36. Tenenbaum, J. B., de Silva, V., and Langford, J. C. 2000. A global geometric framework for non- linear dimensionality reduction. Science 290, 5500, 2319–2323.Google Scholar
37. Tomasi, C., and Manduchi, R. 1998. Bilateral filtering for gray and color images. In Proc. ICCV ’98, IEEE, 839–846. Google ScholarDigital Library
38. Trottenberg, U., Oosterlee, C., and Schüller, A. 2001. Multigrid. Academic Press. Google ScholarDigital Library
39. Turner, M. R. 1986. Texture discrimination by Gabor functions. Biol. Cybern. 55, 2–3, 71–82. Google ScholarDigital Library
40. Weiss, Y. 1999. Segmentation using eigenvectors: A unifying view. In Proc. ICCV, IEEE Computer Society, 975–982. Google ScholarDigital Library
41. Williams, C., and Seeger, M. 2000. Using the Nyström method to speed up kernel machines. Advances in Neural Information Processing Systems 13, 682–688.Google Scholar
42. Xu, K., Li, Y., Ju, T., Hu, S.-M., and Liu, T.-Q. 2009. Efficient affinity-based edit propagation using k-d tree. ACM Trans. Graph. 28, 5 (December), Article 118. Google ScholarDigital Library
43. Yatziv, L., and Sapiro, G. 2006. Fast image and video colorization using chrominance blending. IEEE Trans. Image Proc. 15, 5 (May), 1120–1129. Google ScholarDigital Library
