Efficient gradient-domain compositing using quadtrees
Author:
Open Access
- 29 July 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 26 (3) , 94
Abstract
We describe a hierarchical approach to improving the efficiency of gradient-domain compositing, a technique that constructs seamless composites by combining the gradients of images into a vector field that is then integrated to form a composite. While gradient-domain compositing is powerful and widely used, it suffers from poor scalability. Computing an n pixel composite requires solving a linear system with n variables; solving such a large system quickly overwhelms the main memory of a standard computer when performed for multi-megapixel composites, which are common in practice. In this paper we show how to perform gradient-domain compositing approximately by solving an O(p) linear system, where p is the total length of the seams between image regions in the composite; for typical cases, p is O(√n). We achieve this reduction by transforming the problem into a space where much of the solution is smooth, and then utilize the pattern of this smoothness to adaptively subdivide the problem domain using quadtrees. We demonstrate the merits of our approach by performing panoramic stitching and image region copy-and-paste in significantly reduced time and memory while achieving visually identical results.Keywords
This publication has 25 references indexed in Scilit:
- Scene completion using millions of photographsACM Transactions on Graphics, 2007
- Photographing long scenes with multi-viewpoint panoramasACM Transactions on Graphics, 2006
- Removing photography artifacts using gradient projection and flash-exposure samplingACM Transactions on Graphics, 2005
- Poisson mattingACM Transactions on Graphics, 2004
- Poisson image editingACM Transactions on Graphics, 2003
- Graphcut texturesACM Transactions on Graphics, 2003
- Motion estimation with quadtree splinesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1996
- Fast surface interpolation using hierarchical basis functionsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990
- Quadtree traversal algorithms for pointer-based and depth-first representationsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1988
- The Retinex Theory of Color VisionScientific American, 1977