Convex Optimisation for Multiclass Image Labeling

In this paper, we address multiclass pairwise labeling problems by proposing an alternative approach to continuous relaxation techniques which makes use of a quadratic cost function over the class labels. Here, we relax the discrete labeling problem by abstracting the problem of multiclass semi-supervised labeling to a graph regularisation one. By doing this, we can perform multiclass labeling using a cost function which is convex and related to the target function used in discrete Markov Random Field approaches. Moreover, the Hessian of our cost function is given by the graph Laplacian of the adjacency matrix. Therefore, the optimisation of the cost function is governed by the pairwise interactions between pixels in the local neighbourhood. Since the Hessian is sparse in nature, we can find the global minimum of the continuous relaxation problem efficiently by solving a linear equation using Cholesky factorization. In constrast to other segmentation algorithms elsewhere in the literature, the general nature of the cost function we employ is capable of capturing arbitrary pairwise relations. We provide results on synthetic and real- world imagery and demonstrate the efficacy of our method compared to competing approaches.