Geodesic Forests for Image Editing - Sharp, Toby; Criminisi, Antonio; Perez, Patrick (Microsoft Research, 2011)
A Geodesic Forest is a new representation of digital color images which yields ﬂexible and efﬁcient editing algorithms. In this paper an image is decomposed into a collection of trees (a forest) whose branches follow directions of minimum variation. This representation enables expensive, 2D, edge-aware processing to be cast as efﬁcient one-dimensional operations along the tree branches. Existing and novel contrast-sensitive editing tasks can now be achieved by simple and effective algorithms acting on the same tree-based image decomposition. The contribution of this paper is three-fold: i) We introduce the Geodesic Forests image representation which uniﬁes a number of previously diverse editing techniques; ii) We present a GPU-CUDA algorithm for the efﬁcient decomposition of an image into a complete set of disjoint geodesic trees; iii) We describe a number of simple algorithms to generate existing and new edge-aware image and video effects. The effectiveness of our algorithms is demonstrated with a number of applications such as: texture ﬂattening, ink painting, data-aware resizing, diffusive painting and geodesic plotting. The high level of parallelism of our algorithms enables them to be applied interactively to high-resolution images (∼ 15Mpixel), and video data.