Could this be used for image/video compression? Sounds like a greyscale image + colorization metadata (the "marks" in the article) should take less space than a 3-channel image, no matter how you compress a colour channels. I'd guess the compressor and the decompressor may be slower (because of the need to find a set of colorization marks that reproduce the original image under whatever threshold is required) but achieve higher compression rates?
Of course lossy compression uses other tricks like using different color representations (YUV, YCbCr) where the techniques described in this article may not work, and downsampling, but at least it could be an improvement over lossless image compression?
I like the idea, I guess the question becomes how to pick the colorization data. Perhaps picking semi-random pixels within regions similar to how the algorithm picks colors? Who knows! I like the line of thought though.
As a complement of information, the question of colorization was recently revisited using deep learning methods [1]. All very interesting work!
[1] Zhang, Richard, Phillip Isola, and Alexei A. Efros. "Colorful image colorization." European Conference on Computer Vision (2016) http://richzhang.github.io/colorization/
Of course lossy compression uses other tricks like using different color representations (YUV, YCbCr) where the techniques described in this article may not work, and downsampling, but at least it could be an improvement over lossless image compression?