Convolution pyramids

Abstract

We present a novel approach for rapid numerical approximation of convolutions with filters of large support. Our approach consists of a multiscale scheme, fashioned after the wavelet transform, which computes the approximation in linear time. Given a specific large target filter to approximate, we first use numerical optimization to design a set of small kernels, which are then used to perform the analysis and synthesis steps of our multiscale transform. Once the optimization has been done, the resulting transform can be applied to any signal in linear time. We demonstrate that our method is well suited for tasks such as gradient field integration, seamless image cloning, and scattered data interpolation, outperforming existing state-of-the-art methods.

References

1. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Trans. Graph. 26, 3 (July), Article 94.
2. Bhat, P., Curless, B., Cohen, M., and Zitnick, C. L. 2008. Fourier analysis of the 2D screened Poisson equation for gradient domain problems. In Proc. ECCV, 114--128.
3. Brigham, E. O. 1988. The fast Fourier transform and its applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
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. Burt, P. J. 1981. Fast filter transforms for image processing. Computer Graphics and Image Processing 16, 1 (May), 20--51.
6. Carr, J. C., Beatson, R. K., McCallum, B. C., Fright, W. R., McLennan, T. J., and Mitchell, T. J. 2003. Smooth surface reconstruction from noisy range data. In Proc. GRAPHITE '03, ACM, 119--ff.
7. Derpanis, K., Leung, E., and Sizintsev, M. 2007. Fast scale-space feature representations by generalized integral images. In Proc. ICIP, vol. 4, IEEE, 521--524.
8. Do, M., and Vetterli, M. 2003. Framing pyramids. IEEE Transactions on Signal Processing 51, 9 (Sept.), 2329--2342.
9. Evans, L. C. 1998. Partial Differential Equations, vol. 19 of Graduate Series in Mathematics. American Mathematical Society.
10. Farbman, Z., Hoffer, G., Lipman, Y., Cohen-Or, D., and Lischinski, D. 2009. Coordinates for instant image cloning. ACM Trans. Graph. 28, 3, Article 67.
11. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Trans. Graph. 21, 3 (July), 249--256.
12. 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.
13. Heckbert, P. S. 1986. Filtering by repeated integration. In Proc. ACM SIGGRAPH 86, ACM, 315--321.
14. Horn, B. K. P. 1974. Determining lightness from an image. Computer Graphics and Image Processing 3, 1 (Dec.), 277--299.
15. Kazhdan, M., and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27, 3 (Aug.), 21:1--21:10.
16. Lewis, J. P., Pighin, F., and Anjyo, K. 2010. Scattered data interpolation and approximation for computer graphics. In ACM SIGGRAPH ASIA 2010 Courses, ACM, 2:1--2:73.
17. Mallat, S. 2008. A wavelet tour of signal processing, 3rd ed. Academic Press.
18. McCann, J., and Pollard, N. S. 2008. Real-time gradient-domain painting. ACM Trans. Graph. 27, 3 (August), 93:1--93:7.
19. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: a vector representation for smooth-shaded images. ACM Trans. Graph. 27, 3 (August), 92:1--92:8.
20. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313--318.
21. Perona, P. 1995. Deformable kernels for early vision. IEEE Trans. Pattern Anal. Mach. Intell. 17, 5, 488--499.
22. Selesnick, I. 2006. A higher density discrete wavelet transform. IEEE Trans. Signal Proc. 54, 8 (Aug.), 3039--3048.
23. Shanno, D. F. 1970. Conditioning of quasi-Newton methods for function minimization. Mathematics of Computation 24, 111 (July), 647.
24. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proc. 1968 23rd ACM National Conference, ACM, 517--524.
25. Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Trans. Pattern Anal. Mach. Intell. 12, 6, 513--528.
26. Szeliski, R. 2006. Image alignment and stitching: a tutorial. Found. Trends. Comput. Graph. Vis. 2 (January), 1--104.
27. Trottenberg, U., Oosterlee, C., and Schüller, A. 2001. Multigrid. Academic Press.
28. Wells, III, W. M. 1986. Efficient synthesis of Gaussian filters by cascaded uniform filters. IEEE Trans. Pattern Anal. Mach. Intell. 8, 2 (March), 234--239.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry