Antonio Criminisi, Toby Sharp, and Patrick Perez
11 August 2011
A Geodesic Forest is a new representation of digital color images which yields flexible and efficient 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 efficient 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 unifies a number of previously diverse editing techniques; ii)We present a GPU-CUDA algorithm for the efficient 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 flattening, 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.