“Edge-avoiding wavelets and their applications” by Fattal

  • ©Raanan Fattal




    Edge-avoiding wavelets and their applications



    We propose a new family of second-generation wavelets constructed using a robust data-prediction lifting scheme. The support of these new wavelets is constructed based on the edge content of the image and avoids having pixels from both sides of an edge. Multi-resolution analysis, based on these new edge-avoiding wavelets, shows a better decorrelation of the data compared to common linear translation-invariant multi-resolution analyses. The reduced inter-scale correlation allows us to avoid halo artifacts in band-independent multi-scale processing without taking any special precautions. We thus achieve nonlinear data-dependent multi-scale edge-preserving image filtering and processing at computation times which are linear in the number of image pixels. The new wavelets encode, in their shape, the smoothness information of the image at every scale. We use this to derive a new edge-aware interpolation scheme that achieves results, previously computed by solving an inhomogeneous Laplace equation, through an explicit computation. We thus avoid the difficulties in solving large and poorly-conditioned systems of equations.We demonstrate the effectiveness of the new wavelet basis for various computational photography applications such as multi-scale dynamic-range compression, edge-preserving smoothing and detail enhancement, and image colorization.


    1. An, X., and Pellacini, F. 2008. Appprop: all-pairs appearancespace edit propagation. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 1–9. Google ScholarDigital Library
    2. Barash, D., and Comaniciu, D. 2004. A common framework for nonlinear diffusion, adaptive smoothing, bilateral filtering and mean shift. Image and Video Computing 22, 73–81.Google ScholarCross Ref
    3. Black, M. J., Sapiro, G., Marimont, D. H., and Heeger, D. 1998. Robust anisotropic diffusion. Image Processing, IEEE Transactions on 7, 3, 421–432. Google ScholarDigital Library
    4. Burrus, C., Gopinath, R., and Guo, H. 1998. Introduction to Wavelets and Wavelet Transforms, A Primer. Prentice Hall, N.J.Google Scholar
    5. Burt, P. J., and Adelson, E. H. 1983. The laplacian pyramid as a compact image code. IEEE Transactions on Communications COM-31, 4, 532–540.Google ScholarCross Ref
    6. Burt, P. J. 1981. Fast filter transforms for image processing. Proc. SPIE 2825, vol. 16, 396–408.Google ScholarCross Ref
    7. Chan, T., and Zhou, H. M. 2003. ENO-wavelet Transforms and Some Applications in the book Beyond Wavelets. Academic Press.Google Scholar
    8. Chan, T. F., Osher, S., and Shen, J. 2001. The digital tv filter and nonlinear denoising. IEEE Trans. Image Process 10, 231–241. Google ScholarDigital Library
    9. Choudhury, P., and Tumblin, J. 2005. The trilateral filter for high contrast images and meshes. In ACM SIGGRAPH Courses, ACM, New York, NY, USA, 5. Google ScholarDigital Library
    10. Claypoole, R., Davis, G., Sweldens, W., and Baraniuk, R. 1998. Adaptive wavelet transforms for image coding using lifting. In Proceedings of Data Compression Conference, 537–543. Google ScholarDigital Library
    11. Cohen, A., and Masson, R. 1999.Wavelet methods for secondorder elliptic problems, preconditioning, and adaptivity. SIAM J. Sci. Comput. 21, 3, 1006–1026. Google ScholarDigital Library
    12. Cohen, A., Daubechies, I., and Feauveau, J. C. 1992. Biorthogonal bases of compactly supported wavelets. In Comm. Pure Applied Math.Google Scholar
    13. Dahmen, W. 1994. Some remarks on multiscale transformations, stability and biorthogonality. In Wavelets, Images, and Surface Fitting, Academic Press, 157–188. Google ScholarDigital Library
    14. Donoho, D. L. 1994. On minimum entropy segmentation. Tech. rep., Preprint:, Departement of Statistics, Standford University, Stanford, CA, 1994.Google Scholar
    15. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 257–266. Google ScholarDigital Library
    16. Farbman, Z., Fattal, R., Lischinski, D., and Szeliski, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM, New York, NY, USA, vol. 27, 1–10. Google ScholarDigital Library
    17. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 249–256. Google ScholarDigital Library
    18. Fattal, R., Agrawala, M., and Rusinkiewicz, S. 2007. Multiscale shape and detail enhancement from multi-light image collections. In ACM TOG, ACM, New York, NY, USA, 51. Google ScholarDigital Library
    19. Fattal, R., Carroll, R., and Agrawala, M. 2009. Edge-based image coarsening. to appear in ACM Trans. Graph. available at: www.cs.huji.ac.il/~raananf/projects/bic/m_paper.pdf. Google ScholarDigital Library
    20. Fattal, R. 2008. Single image dehazing. In Proc. ACM SIGGRAPH 27, 3, 1–9. Google ScholarDigital Library
    21. Fattal, R. 2009. A brief introduction to first- and second-generation wavelets. Tech. rep., Leibniz Center, Hebrew University, URL www.cs.huji.ac.il/~raananf/projects/eaw/sup_text.pdf.Google Scholar
    22. Finlayson, G. D., Hordley, S. D., Drew, M. S., and Tj, E. N. 2002. Removing shadows from images. In In ECCV 2002: European Conference on Computer Vision, 823–836. Google ScholarDigital Library
    23. Fleishman, S., Drori, I., and Cohen-Or, D. 2003. Bilateral mesh denoising. ACM Trans. Graph. 22, 3, 950–953. Google ScholarDigital Library
    24. Gonzalez, R. C., and Woods, R. E. 2001. Digital Image Processing. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. Google ScholarDigital Library
    25. Gortler, S. J., Schröder, P., Cohen, M. F., and Hanrahan, P. 1993. Wavelet radiosity. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 221–230. Google ScholarDigital Library
    26. Gortler, S. J., Grzeszczuk, R., Szeliski, R., and Cohen, M. F. 1996. The lumigraph. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 43–54. Google ScholarDigital Library
    27. Harten, A. 1996. Multiresolution representation of data: a general framework. SIAM J. Numer. Anal. 33, 3, 1205–1256. Google ScholarDigital Library
    28. Khan, E. A., Reinhard, E., Fleming, R. W., and Bülthoff, H. H. 2006. Image-based material editing. ACM Trans. Graph. 25, 3, 654–663. Google ScholarDigital Library
    29. Lagendijk, R. L., Biemond, J., and Boekee, D. E. 1988. Regularized iterative image restoration with ringing reduction. Acoustics, Speech, and Signal Processing {see also IEEE Transactions on Signal Processing}, IEEE Transactions on 36, 12, 1874–1888.Google Scholar
    30. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. In Proc. ACM SIGGRAPH 23, 3, 689–694. Google ScholarDigital Library
    31. Li, Y., Sharan, L., and Adelson, E. H. 2005. Compressing and companding high dynamic range images with subband architectures. In Proc. ACM SIGGRAPH 24, 3, 836–844. Google ScholarDigital Library
    32. Li, Y., Adelson, E. H., and Agarwala, A. 2008. Scribbleboost: Adding classification to edge-aware interpolation of local image and video adjustments. Comput. Graph. Forum 27, 4, 1255–1264. Google ScholarDigital Library
    33. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 646–653. Google ScholarDigital Library
    34. Lounsbery, M., DeRose, T. D., and Warren, J. 1997. Multiresolution analysis for surfaces of arbitrary topological type. ACM Trans. Graph. 16, 1, 34–73. Google ScholarDigital Library
    35. Mallat, S. 1999. A Wavelet Tour of Signal Processing, Second Edition (Wavelet Analysis & Its Applications). Academic Press, September.Google Scholar
    36. Paris, S., and Durand, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In In Proceedings of the European Conference on Computer Vision, 568–580. Google ScholarDigital Library
    37. Pellacini, F., and Lawrence, J. 2007. Appwand: editing measured materials using appearance-driven optimization. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 54. Google ScholarDigital Library
    38. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. In Proc. ACM SIGGRAPH 22, 3, 313–318. Google ScholarDigital Library
    39. Perona, P., and Malik, J. 1990. Scale-space and edge detection using anisotropic diffusion. In IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, 629–639. Google ScholarDigital Library
    40. Petschnigg, G., Szeliski, R., Agrawala, M., Cohen, M., Hoppe, H., and Toyama, K. 2004. Digital photography with flash and no-flash image pairs. ACM Trans. Graph. 23, 3, 664–672. Google ScholarDigital Library
    41. Peyré, G., and Mallat, S. 2005. Surface compression with geometric bandelets. ACM Trans. Graph. 24, 3, 601–608. Google ScholarDigital Library
    42. Schlick, C. 1994. Quantization techniques for visualization of high dynamic range pictures. In Photorealistic rendering techniques, proc. EGWR, Springer-Verlag, 7–20.Google Scholar
    43. Schröder, P., and Sweldens, W. 1995. Spherical wavelets: efficiently representing functions on the sphere. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 161–172. Google ScholarDigital Library
    44. Secker, A., and Taubman, D. 2003. Lifting-based invertible motion adaptive transform (limat) framework for highly scalable video compression. Image Processing, IEEE Transactions on 12, 12 (Dec.), 1530–1542. Google ScholarDigital Library
    45. Shen, J., Jin, X., Zhou, C., and Wang, C. C. L. 2007. Technical section: Gradient based image completion by solving the poisson equation. Comput. Graph. 31, 1, 119–126. Google ScholarDigital Library
    46. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 1968 23rd ACM national conference, ACM, New York, NY, USA, 517–524. Google ScholarDigital Library
    47. Sun, J., Jia, J., Tang, C.-K., and Shum, H.-Y. 2004. Poisson matting. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 315–321. Google ScholarDigital Library
    48. Sweldens, W. 1995. The lifting scheme: A new philosophy in biorthogonal wavelet constructions. In in Wavelet Applications in Signal and Image Processing III, 68–79.Google Scholar
    49. Sweldens, W. 1998. The lifting scheme: a construction of second generation wavelets. SIAM J. Math. Anal. 29, 2, 511–546. Google ScholarDigital Library
    50. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. In In Proc. ACM SIGGRAPH, ACM, New York, NY, USA, 1135–1143. Google ScholarDigital Library
    51. Tomasi, C., and Manduchi, R. 1998. Bilateral filtering for gray and color images. In ICCV ’98: Proceedings of the Sixth International Conference on Computer Vision, IEEE Computer Society, Washington, DC, USA, 839. Google ScholarDigital Library
    52. Tumblin, J., and Turk, G. 1999. Lcis: a boundary hierarchy for detail-preserving contrast reduction. In In Proc. ACM SIGGRAPH, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 83–90. Google ScholarDigital Library
    53. Uytterhoeven, G., Roose, D., and Bultheel, A. 1999. Integer wavelet transforms using the lifting scheme. World Scientific and Engineering Society Press, 198–200.Google Scholar
    54. Weiss, Y. 2001. Deriving intrinsic images from image sequences. IEEE International Conference on Computer Vision 2.Google ScholarCross Ref
    55. Yatziv, L., and Sapiro, G. 2006. Fast image and video colorization using chrominance blending. Image Processing, IEEE Transactions on 15, 5, 1120–1129. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: