Abstract: This paper proposes a structure-aware nonlocal energy optimization framework for interactive image colorization with sparse scribbles. Our colorization technique propagates colors to both local intensity-continuous regions and remote texture-similar regions without explicit image segmentation. We implement the nonlocal principle by computing K nearest neighbors in the high-dimensional feature space. The feature space contains not only image coordinates and intensities but also statistical texture features obtained with the direction-aligned Gabor wavelet filter. Structure maps are utilized to scale texture features to avoid artifacts along high-contrast boundaries. We show various experimental results and comparisons on image colorization, selective recoloring and decoloring, and progressive color editing to demonstrate the effectiveness of the proposed approach.