Thing about NNs is that they cannot encode structure, or, to be more precise, they cannot optimize over joint loss (except RNNs but training is a pain). For example, the color of the current pixel can depend on the inferenced color of upper neighbors and neighbors on the left (we would be coloring pixels from left to right, going row by row). NN in the article is coloring locally without any kind of reference of what the whole picture looks, NN can encode the information of what the pictures look since it has a lot of representation power but that requires large amounts of data, and parameter tweaking.

Optimizing over joint loss (maximizing the probability of the full image colorization) would work extremely well.

Tools like vowpal wabbit can easily be adapted to learn a chain classifier over colors and it should work insanely fast.