Efficient Gradient-Domain Compositing Using Quadtrees

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.

Citation
Aseem Agarwala. Efficient Gradient-Domain Compositing Using Quadtrees. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007), 2007.

Paper
SIGGRAPH 2007 pre-print (1.4MB PDF)

Products
This algorithm forms a part of the "Auto-Blend Layers" and "Photomerge" features in Adobe Photoshop CS3.

Results

The results of our paper are divided into two sections. In the first, we show comparisons between results computed using our reduced linear system and the full linear system. Each thumbnail links to a full resolution version. The offset images are created by centering a zero offset at 128, and multiplying the offsets by 10 to better fill the gamut. In this section, both the offsets and final gradient-domain composites are stored with lossless PNG compression. By flipping between them rapidly, you can confirm that they are visually indistinguishable. In the second section, we show several very large panoramas computed using only the reduced linear system; in the interest of space, these are JPG-compressed. The names of each data set correspond to the names in the tables of the paper.

Comparisons

St. Emilion, 9.66 Megapixels

Color composite

Seams highlighted in red, & reduced space quadtree

Full gradient-domain composite & offset

Reduced gradient-domain composite & offset

Beynac, 11.6 Megapixels

Color composite

Seams highlighted in red, & reduced space quadtree

Full gradient-domain composite & offset

Reduced gradient-domain composite & offset

Rainier, 16.6 Megapixels (Copyright Tobias Oberlies, used with permission)

Color composite

Seams highlighted in red, & reduced space quadtree

Full gradient-domain composite & offset

Reduced gradient-domain composite & offset

Plane (image region copy-and-paste), 2.4 Megapixels

Color composite

Full gradient-domain composite

Reduced gradient-domain composite

Random, 12.6 Megapixels
This example is not included in the published paper, but is shown here as a "stress test" of the quadtree approximation. A "collage" of four random images is composited, leading to very large initial errors along the seams. This case exhibits slightly larger numerical differences (RMS of 0.137, maximum error of 3.89) between the full and reduced composites, but the composites are still visually indistinguishable.

Color composite

Seams highlighted in red, & reduced space quadtree

Full gradient-domain composite & offset

Reduced gradient-domain composite & offset

Koli, 10.4 Megapixels
This example is also not included in the published paper, but demonstrates some larger exposure and hue variations.

Color composite

Seams highlighted in red, & reduced space quadtree

Full gradient-domain composite & offset

Reduced gradient-domain composite & offset