Is it possible to provide a differentiable version of cut-pursuit?

[THHHomas]

Is it possible to provide a differentiable version of cut-pursuit? such as the code written in pytorch with Variable. In this way, we can put the cut-pursuit in an end-to-end pipeline. Although there might be no weights need training in cut-pursuit, a differentiable version can pass the gradient to other parts.

[loicland]

Solving L0-Cut Pursuit cannot be backrpopagated through because it is non-differentiable (and even non-continuous). This is due to the two following reasons:

• the generalized minimal partition problem is a nondifferentiable, noncontinuous, nonconvex problem. minimal changes in the signal to approximate can have huge consequences in the resulting partition
• the constant connected component operator is noncontinuous

However, you can use a surrogate loss which allows to learn the input and edge parametersof L0-CP. See this paper: https://arxiv.org/abs/1905.04014 and its application to point cloud partition: https://arxiv.org/pdf/1904.02113

[THHHomas]

Thanks for your Detailed answer. Do you think K-means is a good substitute for L0-CP in point cloud segmentation? And What are the advantages of L0-CP for point cloud segmentation comparing with the traditional clustering methods?

[loicland]

K-means is not a spatial clustering algorithm natively, although it can be adapted (see SLIC3D, ref in the second paper I linked).

L0-CP has several advantages, depending on your application:

• it is fast (up to 2 million points/s with parallel version, 100k with this version).
• it produced superpoints with simple contours by design
• the superpoints are contiguous/connected (not the case for slic3d)
• it has adaptive granularity, producing big superpoints where the geometry/radiometer is simple, and small ones where it is more complex, whereas means based approaches produces superpoint with similar size regardless of the local complexity
• see benchmark in second paper, even without learning the points descriptors, it produces partitions that are more "pure" semantically than other STOTA approaches for similar number of superpoints
• it is already integrated in a superpoint-based semantic segmentation network https://github.com/loicland/superpoint_graph

[THHHomas]

Thanks a lot.