Cut Pursuit: Fast Algorithms to Learn Piecewise Constant Functions on General Weighted Graphs

作     者：Landrieu, Loic Obozinski, Guillaume 

作者机构：Univ Paris Est ENSG IGN LASTIG MATIS F-94160 St Mande France Univ Paris Est UPEM ESIEE Paris ENPCLIGMUMR 8049CNRS F-77455 Marne La Vallee 2 France 

出 版 物：《SIAM JOURNAL ON IMAGING SCIENCES》 (SIAM J. Imaging Sci.)

年 卷 期：2017年第10卷第4期

页      面：1724-1766页

核心收录：

学科分类：1002[医学-临床医学] 070207[理学-光学] 07[理学] 08[工学] 0835[工学-软件工程] 0803[工学-光学工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0702[理学-物理学] 

基　　金：ANR project Semapolis [ANR-13-CORD-0003] Agence Nationale de la Recherche (ANR) [ANR-13-CORD-0003] Funding Source: Agence Nationale de la Recherche (ANR) 

主　　题：working set total variation sparsity Mumford-Shah greedy algorithm 

摘      要：We propose working-set/greedy algorithms to efficiently solve problems penalized respectively by the total variation on a general weighted graph and its l(0) counterpart the Mumford Shah total level-set boundary size when the piecewise constant solutions have a small number of distinct level-sets;this is typically the case when the total level-set boundary size is small, which is encouraged by these two forms of penalization. Our algorithms exploit this structure by recursively splitting the level-sets of a piecewise-constant candidate solution using graph cuts. We obtain significant speed-ups over state-of-the-art algorithms for images that are well approximated with few level-sets.