What's even cooler is adding support for human annotations so users can selectively give colorization hints for different parts of the image to customize the output.
A GAN style approach to learning and generating variants could be interesting as well. It could generate a couple of hundred plausible versions. Then you have another network that is trained to differentiate between fake and real colored photos which picks the best version.