Convex Variational Methods on Graphs for Multiclass Segmentation of High-Dimensional Data and Point CloudsReportar como inadecuado

Convex Variational Methods on Graphs for Multiclass Segmentation of High-Dimensional Data and Point Clouds - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Journal of Mathematical Imaging and Vision

, Volume 58, Issue 3, pp 468–493

First Online: 22 March 2017Received: 31 October 2016Accepted: 16 February 2017DOI: 10.1007-s10851-017-0713-9

Cite this article as: Bae, E. & Merkurjev, E. J Math Imaging Vis 2017 58: 468. doi:10.1007-s10851-017-0713-9


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 acquire by a LaDAR in outdoor scenes and demonstrate that the scenes can accurately be segmented into object classes such as vegetation, the ground plane and human-made structures.

KeywordsVariational methods Graphical models Convex optimization Semi-supervised classification Point cloud segmentation 

Autor: Egil Bae - Ekaterina Merkurjev


Documentos relacionados