TY - GEN

T1 - Color image labelling using linear programming

AU - Hongdong, Li

AU - Chunhua, Shen

AU - Wen, Zhiying

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=44949242716&partnerID=8YFLogxK

U2 - 10.1109/DICTA.2007.4426802

DO - 10.1109/DICTA.2007.4426802

M3 - Conference contribution

SN - 0769530672

SN - 9780769530673

T3 - Proceedings - Digital Image Computing Techniques and Applications: 9th Biennial Conference of the Australian Pattern Recognition Society, DICTA 2007

SP - 239

EP - 244

BT - Proceedings - Digital Image Computing Techniques and Applications

T2 - Australian Pattern Recognition Society (APRS)

Y2 - 3 December 2007 through 5 December 2007

ER -