Cut Pursuit: Fast Algorithms to Learn Piecewise Constant Functions


Loic Landrieu, Guillaume Obozinski ;
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1384-1393, 2016.


We propose working-set/greedy algorithms to efficiently solve problems penalized respectively by the total variation and the Mumford Shah boundary size when the piecewise constant solutions has a small number of levelsets. Our algorithms exploit this structure by recursively splitting the level-sets using graph cuts. We obtain significant speed up on images that can be approximated with few levelsets compared to state-of-the-art algorithms.

Related Material