loicland
commented
4 years ago Great question.
L0 cut pursuit is an algorithm that can be used to compute piecewise constant approximations of a signal on a graph (the generalized minimal partition problem). I encourage you to read th original cut pursuit paper, or at least the more recent ICML 2018 and 2019 (graph reasoning workshop) versions which are maybe more didactic (eventhough they only treat the convex formulation, the ideas are similar).
To put it simply, the algorithm operates by alternating between two steps: splitting and reduction. In the split step, the graph is partitioned into smaller and smaller components, in the reduction step, a piecewise constant solution wrt to the current partition is computed.
In the original paper, the split step is performed independently for each constant component by computing an optimal binary partition, whose goal is to split a component into 2 parts, if profitable wrt toi thev objective energy. This procedure alternates between computing the cut between the 2 parts and their respective values. These 2 values are initialized by ignoring the contour length, essentially computing a 2-mean problem.
We improved that step. Instead of ignoring the contour length (no spatial regularization, lambda=0) and then then directectly computing the cuts with the "full" regularization strength, we gradually increase the reg strength from 0 (initialization) to the target reg strength (the argument of the cut pursuit function).
The consequence is that the algorithm is less likely to get stuck because of a bad initialization, and it improves the final energy. Tbh the improvement is not major (a few %), but avoid some weirdly shaped components for cheap.
yaping222
Dear Loic,
Thank you very much for your great code! I have a question on the setup of weight_decay in cutpursuit algorithm. In the code: pred_components, pred_in_component = libcp.cutpursuit(ver_value, \ edg_source.astype('uint32'), edg_target.astype('uint32'), edge_weight, \ args.reg_strength / (4 * args.k_nn_adj), cutoff=args.CP_cutoff, spatial = use_spatial, weight_decay = 0.7)
In the paper, you mentioned 'we heuristically improved the forward step (8) from [31], such that the regularization strength increases geometrically by a factor (of 0.7) along the iterations.'. But I don't understand why you set this parameter and how this will influence the segmentation results.
I'm looking forward to your reply.
Best wishes, Yaping