“Edge-Based Image Coarsening” by Fattal, Carroll and Agrawala

  • ©Raanan Fattal, Robert Carroll, and Maneesh Agrawala




    Edge-Based Image Coarsening



    This article presents a new dimensionally-reduced linear image space that allows a number of recent image manipulation techniques to be performed efficiently and robustly. The basis vectors spanning this space are constructed from a scale-adaptive image decomposition, based on kernels of the bilateral filter. Each of these vectors locally binds together pixels in smooth regions and leaves pixels across edges independent. Despite the drastic reduction in the number of degrees of freedom, this representation can be used to perform a number of recent gradient-based tonemapping techniques. In addition to reducing computation time, this space can prevent the bleeding artifacts which are common to Poisson-based integration methods. In addition, we show that this reduced representation is useful for energy-minimization methods in achieving efficient processing and providing better matrix conditioning at a minimal quality sacrifice.


    1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. Graph. 23, 294–302. 
    2. Bae, S., Paris, S., and Durand, F. 2006. Two-Scale tone management for photographic look. ACM Trans. Graph. 25, 637–645. 
    3. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Patt. Anal. Mach. Intell. 23, 11, 1222–1239. 
    4. Burt, P. J. and Adelson, E. H. 1983. The Laplacian pyramid as a compact image code. IEEE Trans. Comm. 31, 4, 532–540.
    5. Chen, J., Paris, S., and Durand, F. 2007. Real-Time edge-aware image processing with the bilateral grid. ACM Trans. Graph. 26, 103. 
    6. Chen, K. 2005. Matrix Preconditioning Techniques and Applications. Number 19. Cambridge University Press.
    7. Durand, F. and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. ACM Trans. Graph. 21, 257–266. 
    8. Efros, A. A. and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In Proceedings of the International Conference on Computer Vision (ICCV’99). 1033–1038. 
    9. Eisemann, E. and Durand, F. 2004. Flash photography enhancement via intrinsic relighting. ACM Trans. Graph. 23, 673–678. 
    10. Fattal, R., Agrawala, M., and Rusinkiewicz, S. 2007. Multiscale shape and detail enhancement from multi-light image collections. ACM Trans. Graph. 26, 51. 
    11. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Trans. Graph. 21, 249–256. 
    12. Finlayson, G. D., Hordley, S. D., Drew, M. S., and Tj, E. N. 2002. Removing shadows from images. In Proceedings of the European Conference on Computer Vision (ECCV’02). 823–836. 
    13. Finlayson, G. D., Hordley, S. D., Lu, C., and Drew, M. S. 2006. On the removal of shadows from images. IEEE Trans. Patt. Anal. Mach. Intell. 28, 1, 59–68. 
    14. Grady, L., Tasdizen, T., and Whitaker, R. T. 2005. A geometric multigrid approach to solving the 2d inhomogeneous laplace equation with internal dirichlet boundary conditions. In Proceedings of the IEEE International Conference on Image Processing (ICIP’05). Vol. 2. 642–645.
    15. Hackbusch, W. 1994. Iterative Solution of Large Sparse Systems of Equations. Springer-Verlag, Berlin.
    16. Kopf, J., Cohen, M. F., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM Trans. Graph. 26, 96. 
    17. Levin, A., Fergus, R., Durand, F., and Freeman, W. T. 2007a. Image and depth from a conventional camera with a coded aperture. ACM Trans. Graph. 26, 3, 70. 
    18. Levin, A., Lischinski, D., and Weiss, Y. 2004a. Colorization using optimization. ACM Trans. Graph. 23, 689–694. 
    19. Levin, A., Lischinski, D., and Weiss, Y. 2006. A closed form solution to natural image matting. In Proceedings of the Computer Vision and Pattern Recognition (CVPR’06). IEEE Computer Society, 61–68. 
    20. Levin, A., Rav-Acha, A., and Lischinski, D. 2007b. Spectral matting. In Proceedings of the Computer Vision and Pattern Recognition (CVPR’07). 1–8.
    21. Levin, A., Zomat, A., Peleg, S., and Weiss, Y. 2004b. Seamless image stitching in the gradient domain. In Proceedings of the European Conference on Computer Vision (ECCV’04).
    22. Li, Y., Sun, J., Tang, C.-K., and Shum, H.-Y. 2004. Lazy snapping. ACM Trans. Graph. 23, 303–308. 
    23. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. ACM Trans. Graph. 25, 646–653. 
    24. Mallat, S. G. 1989. A theory for multiresolution signal decomposition: The wavelet representation. IEEE Trans. Patt. Anal. Mach. Intell. 11, 7, 674–693. 
    25. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 313–318. 
    26. Petschnigg, G., Agrawala, M., Hoppe, H., Szeliski, R., Cohen, M., and Toyama, K. 2004. Digital photography with flash and no-flash image pairs. ACM Trans. Graph. 23, 664–672. 
    27. Rudin, L. I., Osher, S., and Fatemi, E. 1992. Nonlinear total variation based noise removal algorithms. Phys. D 60, 1-4, 259–268. 
    28. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics. 
    29. Skalicky, T. 1995. Package for solving large sparse systems of linear equations. http://www.mgnet.org/mgnet/Codes/laspack/html/laspack.html.
    30. Strang, G. 2003. Introduction to Linear Algebra, 3rd ed. Wellesley, Cambridge, MA.
    31. Sun, J., Jia, J., Tang, C.-K., and Shum, H.-Y. 2004. Poisson matting. ACM Trans. Graph. 23, 315–321. 
    32. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Trans. Graph. 25, 1135–1143. 
    33. Tappen, M. F., Russell, B. C., and Freeman, W. T. 2001. Exploiting the sparse derivative prior for super-resolution and image demosaicing. Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision.
    34. Tomasi, C. and Manduchi, R. 1998. Bilateral filtering for gray and color images. In Proceedings of the International Conference on Computer Vision (ICCV’98). IEEE Computer Society, 839. 
    35. Tumblin, J. and Turk, G. 1999. Lcis: A boundary hierarchy for detail-preserving contrast reduction. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’99). ACM Press/Addison-Wesley, New York, 83–90. 
    36. Xu, L., Qi, F., and Jiang, R. 2006. Shadow removal from a single image. In Proceedings of the 6th International Conference on Intelligent Systems Design and Applications (ISDA’06). IEEE Computer Society, 1049–1054. 
    37. Zienkiewicz, O. and Taylor, R. 2000. The Finite Element Method. Butterworth-Heinemann.

ACM Digital Library Publication: