cut pursuit: a working-set strategy to compute piecewise constant functions on graphs

C/C++ implementation of the L0-cut pursuit algorithms with Matlab and Python interfaces.

Cut pursuit is a graph-cut-based working-set strategy to minimize functions regularized by graph-structured regularizers. For G = (V, E, w) a graph with edges weighted by w, the problem writes:

    min_{x ∈ Ω^V}    f(x) + ∑_{(u,v) ∈ E} w_(u,v) φ(x_u - x_v)

where Ω is the space in which lie the values associated with each node.

We distinguish two different cases for φ, corresponding to different implementations:

• φ: t ↦ |t|: the convex case, the regularizer is the graph total variation. Implemented for many different functionals f, such as quadratic, ℓ₁-norm, box constraints, simplex constraints, linear, smoothed Kullback–Leibler. See repository CP_PFDR_graph_d1, by Hugo Raguet. It is well-suited for regularization and inverse problems with a low total variation prior.
• φ: t ↦ δ(t ≠ 0) = 1 - δ₀(t): the nonconvex case, the regularizer is the weight of the cut between the adjacent constant components. It is well-suited for segmentation/partitioning tasks. This repository corresponds to this problem.

Current implementation supports the following fidelity functions:

• quadratic fidelity: φ: x ↦ ∑_{v in V}||x_v - y_v||² with y an observed value associated with node v (best for partitioning)
• linear fidelity: φ: x ↦ - ∑_{v in V}<x_v, y_v> with y_v a weight associated with node v
• Kullback leibler fidelity φ: x ↦ ∑_{v in V} KL(x_v, p_v) with p_v a probability associated with node v. Only apply when Ω is a simplex

Requirement

You need boost 1.58, or 1.65 if you want the python wrapper.

conda install -c anaconda boost

Compilation

C++

make sure that you use the following CPPFLAGS: set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pthread -fopenmp -O3 -Wall -std=c++11")

add include<./cut-pursuit/include/API.h> and call any of the interface functions.

MATLAB

To compile the MATLAB mex file type the following in MATLAB in the workspace containing the cut-pursuit folder:

mkdir ./cut-pursuit/bin
addpath('./cut-pursuit/bin/')
mex CXXFLAGS="\$CXXFLAGS -pthread -Wall -std=c++11 -fopenmp -O3"...
    LDFLAGS="\$LDFLAGS -fopenmp" cut-pursuit/mex/L0_cut_pursuit.cpp ...
    -output cut-pursuit/bin/L0_cut_pursuit
mex CXXFLAGS="\$CXXFLAGS -pthread -Wall -std=c++11 -fopenmp -O3"...
    LDFLAGS="\$LDFLAGS -fopenmp" cut-pursuit/mex/L0_cut_pursuit_segmentation.cpp ...
    -output cut-pursuit/bin/L0_cut_pursuit_segmentation

You can test the compilation with the following minimal example:

n_nodes = 100;
y = rand(3,n_nodes);
Eu = 0:(n_nodes-2);
Ev = 1:(n_nodes-1);
edge_weight = ones(numel(Eu),1);
node_weight = ones(n_nodes,1);
lambda = .1;
mode = 1;
cutoff = 0;
weigth_decay = 0;
speedmode = 2;
verbosity = 2;

[solution, in_component, components] = L0_cut_pursuit_segmentation(single(y),...
        uint32(Eu), uint32(Ev), single(lambda),...
        single(edge_weight), single(node_weight), mode, cutoff, speedmode,...
        weigth_decay, verbosity);

subplot(3,1,1)
imagesc(repmat(y, [1 1 1]))
title('input data')
subplot(3,1,2)
imagesc(solution)
title('piecewise constant approximation')
subplot(3,1,3)
imagesc(in_component')
title('components')

Python

Compile the library from the cut-pursuit folder

mkdir build
cd build
cmake .. -DPYTHON_LIBRARY=$CONDAENV/lib/libpython3.6m.so -DPYTHON_INCLUDE_DIR=$CONDAENV/include/python3.6m -DBOOST_INCLUDEDIR=$CONDAENV/include  -DEIGEN3_INCLUDE_DIR=$CONDAENV/include/eigen3
make

This creates build/src/libcp.so which can be imported in python. see test.py to test it out.

References:

Cut Pursuit: fast algorithms to learn piecewise constant functions on general weighted graphs, L. Landrieu and G. Obozinski, SIAM Journal on Imaging Science 2017, Vol. 10, No. 4 : pp. 1724-1766 [hal link]

Cut-pursuit algorithm for nonsmooth functionals regularized by graph total variation, H. Raguet and L. Landrieu, in preparation.

if using the L0-cut pursuit algorithm with \Omega other than R, one must also cite:

A structured regularization framework for spatially smoothing semantic labelings of 3D point clouds. Loic Landrieu, Hugo Raguet , Bruno Vallet , Clément Mallet, Martin Weinmann