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 -