Efficient manifold-preserving edit propagation using quad-tree data structures

In this paper, we propose an edit propagation algorithm using quad-tree data structures for image manipulation. First, we use a quad-tree to adaptively group all pixels into clusters. Then, we build a manifold-preserving propagation function based on clusters using locally linear embedding for improved distance. Moreover, we employ an adaptive weight function built on cell corners instead of individual pixels. Because the number of corners is smaller than the number of individual pixels, it results in runtime performance improvement. Finally, the edits of all pixels can be computed by interpolating the edits solved from the clusters. Compared with previous approaches, our method requires less time without sacrificing the visualization quality. Experimental results demonstrate two applications of our algorithm: grayscale image colorization and color image recoloring.