Color Image Labelling Using Linear Programming

Abstract

This paper describes a linear programming (LP) algorithm for labelling (segmenting) a color image into multiple regions. Compared with the recently-proposed semi-definite programming (SDP) relaxation based algorithm, our algorithm has a simpler mathematical formulation, and a much lower computational complexity. In particular, to segment an image of M × N pixels into k classes, our algorithm requires only O((M N k)m) complexity - a sharp contrast to the complexity of O((M N k)2n) offered by the SDP algorithm, where m and n are the polynomial degrees-of-complexity of the corresponding LP solver and SDP solver, respectively (in general we have m ≪ n). Moreover, LP has a significantly better scalability than SDP generally. This dramatic reduction in complexity enables our algorithm to process color images of reasonable sizes. For example, while the existing SDP relaxation algorithm is only able to segment a toy-size image of e.g. 10 × 10 - 30 × 30 pixels in a few hours, our algorithm can process larger color image of, say, 100 × 100 - 500 × 500 image in a much shorter time.