For my final undergraduate project I joined a fellow student, Renan Gutman, to conduct a comparative examination of two image colorization algorithms. Each of us chose one algorithm to work on. I implemented an existing image colorization algorithm (Yatziv and Sapiro) based on multiple sources’ shortest paths in graphs. I started with a careful implementation and continued with improving the algorithm beyond the description given in the paper. The first optimization was based on looking only on the most important data, thus drastically reducing the runtime without lowering the quality of the output. Following I extended the algorithm’s functionality, as I discovered that it can be used for other image processing applications. Since the algorithm proved to have some serious issues with certain types of textures (more on that below), it wasn’t perfect for the colorization task. However, the extended uses of the algorithm didn’t face these difficulties and for these cases the algorithm proved to be a good tool. For our submission my partner and I prepared a presentation comparing the algorithms. We received a grade of 100. Following our project, my optimized implementation was used in Microsoft’s research labs in China.
Below is a detailed review of the Yatziv-Sapiro algorithm, my implementation and my enhancements:
To summarize this project me and my partner delivered a presentation with a side-by-side comparison of the Yatziv-Sapiro algorithm and the Colorization Optimization algorithm by Levin et al., which my partner implemented and researched. It was a bit hard to compare running times as I implemented mine in C++ and she in Matlab. However, after the optimizations, the shortest paths algorithm appeared to be significantly faster. It also seemed to deal better with most situations with one significant exception: it failed in complex textures (think about a polka dot pattern). The same problem proved to be a difficulty when dealing with natural textures as well. The colorization optimization algorithm proved to work better on such cases. However, in natural cases placing the color user input in a smart manner overcame the problem.
Below is the final comparative presentation we gave: