“Convolution pyramids”
Conference:
Type(s):
Title:
- Convolution pyramids
Session/Category Title: Image Processing
Presenter(s)/Author(s):
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. Google ScholarDigital Library
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. Google ScholarDigital Library
3. Brigham, E. O. 1988. The fast Fourier transform and its applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA. Google ScholarDigital Library
4. Burt, P. J., and Adelson, E. H. 1983. The Laplacian pyramid as a compact image code. IEEE Trans. Comm. 31, 4, 532–540.Google ScholarCross Ref
5. Burt, P. J. 1981. Fast filter transforms for image processing. Computer Graphics and Image Processing 16, 1 (May), 20–51.Google ScholarCross Ref
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. Google ScholarDigital Library
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.Google Scholar
8. Do, M., and Vetterli, M. 2003. Framing pyramids. IEEE Transactions on Signal Processing 51, 9 (Sept.), 2329–2342. Google ScholarDigital Library
9. Evans, L. C. 1998. Partial Differential Equations, vol. 19 of Graduate Series in Mathematics. American Mathematical Society.Google Scholar
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. Google ScholarDigital Library
11. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Trans. Graph. 21, 3 (July), 249–256. Google ScholarDigital Library
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. Google ScholarDigital Library
13. Heckbert, P. S. 1986. Filtering by repeated integration. In Proc. ACM SIGGRAPH 86, ACM, 315–321. Google ScholarDigital Library
14. Horn, B. K. P. 1974. Determining lightness from an image. Computer Graphics and Image Processing 3, 1 (Dec.), 277–299.Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarDigital Library
17. Mallat, S. 2008. A wavelet tour of signal processing, 3rd ed. Academic Press. Google ScholarDigital Library
18. McCann, J., and Pollard, N. S. 2008. Real-time gradient-domain painting. ACM Trans. Graph. 27, 3 (August), 93:1–93:7. Google ScholarDigital Library
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. Google ScholarDigital Library
20. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318. Google ScholarDigital Library
21. Perona, P. 1995. Deformable kernels for early vision. IEEE Trans. Pattern Anal. Mach. Intell. 17, 5, 488–499. Google ScholarDigital Library
22. Selesnick, I. 2006. A higher density discrete wavelet transform. IEEE Trans. Signal Proc. 54, 8 (Aug.), 3039–3048. Google ScholarDigital Library
23. Shanno, D. F. 1970. Conditioning of quasi-Newton methods for function minimization. Mathematics of Computation 24, 111 (July), 647.Google Scholar
24. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proc. 1968 23rd ACM National Conference, ACM, 517–524. Google ScholarDigital Library
25. Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Trans. Pattern Anal. Mach. Intell. 12, 6, 513–528. Google ScholarDigital Library
26. Szeliski, R. 2006. Image alignment and stitching: a tutorial. Found. Trends. Comput. Graph. Vis. 2 (January), 1–104. Google ScholarDigital Library
27. Trottenberg, U., Oosterlee, C., and Schüller, A. 2001. Multigrid. Academic Press. Google ScholarDigital Library
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. Google ScholarDigital Library
