Diffusion Maps for Edge-Aware Image Editing

Abstract:

Edge-aware operations, such as edge-preserving smoothing and edge-aware interpolation, require assessing the degree of similarity between pairs of pixels, typically defined as a simple monotonic function of the Euclidean distance between pixel values in some feature space.
In this work we introduce the idea of replacing these Euclidean distances with diffusion distances, which better account for the global distribution of pixels in their feature space.These distances are approximated using diffusion maps: a set of the dominant eigenvectors of a large affinity matrix, which may be computed efficiently by sampling a small number of matrix columns (the Nystrom method).
We demonstrate the benefits of using diffusion distances in a variety of image editing contexts, and explore the use of diffusion maps as a tool for facilitating the creation of complex selection masks.
Finally, we present a new analysis that establishes a connection between the maximal spatial interaction range between two pixels, and the number of samples necessary for accurate Nystrom approximations.

Full paper: Paper, 19.4MB

Supplementary Materials:

It can be difficult to fully appreciate the differences between the small side-by-side images in the paper. Therefore, in these supplementary materials we include larger format versions of the images in the paper, with the ability to easily flip between them. We also include additional comparisons, examples, and visualizations. The material is organized in several pages, roughly corresponding to the figures in the paper.

Note: In order to view these pages properly, JavaScript must be enabled in your browser. In Internet Explorer, you may also need to allow blocked active content to run.

Sections:

1. Local edit propagation: Fig. 1, Fig.3, Valley of Fire, Santa Fe1, Santa Fe2, Into the Sky, Boston, Shirt
2. Eigenvectors and gradients: Fig. 2, Giraffe, Sunflower, Synagogue, Rocks
3. WLS with diffusion distances: Fig. 4, Sunflowers, Brewery, Red rock
4. A comparison with the method of Subr et al.: Fig. 5
5. Distance-based blending: Meadow
6. Matting: Fig. 6, Toy(Scribble Set 1, Scribble Set 2), Troll - dense trimap
7. Fuzzy selection example: Fig. 7
8. Spatial range and sampling: Fig. 9
9. Failure cases: Market05, Skirt

Code:

Matlab script for (Fig. 2) and C++ code that uses WLS with diffusion distances (Fig. 4) are available here.