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:
minx ∈ ΩV f(x) + ∑(u,v) ∈ E w(u,v) φ(xu - xv)
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, ℓ1-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 - δ0(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||xv - yv||² with y an observed value associated with node v (best for partitioning)
linear fidelity: φ: x ↦ - ∑v in V<xv, yv> with yv a weight associated with node v
Kullback leibler fidelity φ: x ↦ ∑v in V KL(xv, pv) with pv a probability associated with node v. Only apply when Ω is a simplex
You need boost 1.58, or 1.65 if you want the python wrapper.
conda install -c anaconda boost
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.
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')
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.
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