Here’s the abstract of a paper by Anat Levin, Dani Lischinski, and Yair Weiss:
Colorization is a computer-assisted process of adding color to a monochrome image or movie. The process typically involves segmenting images into regions and tracking these regions across image sequences. Neither of these tasks can be performed reliably in practice; consequently, colorization requires considerable user intervention and remains a tedious, time-consuming, and expensive task.
In this paper we present a simple colorization method that requires neither precise image segmentation, nor accurate region tracking. Our method is based on a simple premise: neighboring pixels in space-time that have similar intensities should have similar colors. We formalize this premise using a quadratic cost function and obtain an optimization problem that can be solved efficiently using standard techniques. In our approach an artist only needs to annotate the image with a few color scribbles, and the indicated colors are automatically propagated in both space and time to produce a fully colorized image or sequence. We demonstrate that high quality colorizations of stills and movie clips may be obtained from a relatively modest amount of user input.
Both the interface and the results are rather amazing. Tons of examples and Matlab source code included.
It’s surprising that an algorithm similar to that one wasn’t developed earlier. Upon reading the abstract the solution seems like an obvious and elegant one… but it’s easy to say that in hindsight.
I went through the exact same thought progression!