Projects / Efficient Gradient-Domain Compositing Using Quadtrees
Efficient Gradient-Domain Compositing Using Quadtrees
Aseem Agarwala| Adobe Systems
We developed 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. Instead, we can 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. Our approach allows us to perform panoramic stitching and image region copy-and-paste in significantly reduced time and memory while achieving visually identical results.
Products |
This algorithm forms a part of the "Auto-Blend Layers" and "Photomerge" features inAdobe Photoshop CS3, as well as the “Photomerge” features in Adobe Photoshop Elements 6.0.
Publications |
Efficient gradient-domain compositing using quadtrees
ACM Transactions on Graphics (Proc. SIGGRAPH), 26(3), 94:1–94:5.
