There was a popular post a little over a month ago [2] about this very topic. That particular example used deep learning in a similar way to what you described.

It looks like there are previous attempts [2] that have even been turned into APIs [3]

[1] https://news.ycombinator.com/item?id=18363870

[2] https://github.com/richzhang/colorization

[3] https://demos.algorithmia.com/colorize-photos/