“Edge-avoiding wavelets and their applications” by Fattal

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