Convex Variational Methods on Graphs for Multiclass Segmentation of High-Dimensional Data and Point Clouds

Author
Bae, Egil
Merkurjev, Ekaterina
Date Issued
2017
Keywords
Variasjonsregning
Grafiske modeller
Optimalisering
Maskinlæring
Permalink
http://hdl.handle.net/20.500.12242/628
https://publications.ffi.no/123456789/628
DOI
10.1007/s10851-017-0713-9
Collection
Articles
Description
Bae, Egil; Merkurjev, Ekaterina. Convex Variational Methods on Graphs for Multiclass Segmentation of High-Dimensional Data and Point Clouds. Journal of Mathematical Imaging and Vision 2017 ;Volum 58.(3) s. 468-493
1472461.pdf
Size: 5M
Abstract
Graph-based variational methods have recently shown to be highly competitive for various classification problems of high-dimensional data, but are inherently difficult to handle from an optimization perspective. This paper proposes a convex relaxation for a certain set of graph-based multiclass data segmentation models involving a graph total variation term, region homogeneity terms, supervised information and certain constraints or penalty terms acting on the class sizes. Particular applications include semi-supervised classification of high-dimensional data and unsupervised segmentation of unstructured 3D point clouds. Theoretical analysis shows that the convex relaxation closely approximates the original NP-hard problems, and these observations are also confirmed experimentally. An efficient duality-based algorithm is developed that handles all constraints on the labeling function implicitly. Experiments on semi-supervised classification indicate consistently higher accuracies than related non-convex approaches and considerably so when the training data are not uniformly distributed among the data set. The accuracies are also highly competitive against a wide range of other established methods on three benchmark data sets. Experiments on 3D point clouds acquired by a LaDAR in outdoor scenes demonstrate that the scenes can accurately be segmented into object classes such as vegetation, the ground plane and human-made structures.
View Meta Data