  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 problems, featuring region homogeneity terms, supervised
information and/or 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 indicates 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 local minimization 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 datasets. 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.
