Li, HongdongShen, Chunhua2015-12-080932-8092http://hdl.handle.net/1885/34808Image segmentation is an important and fundamental task for image and vision understanding. This paper describes a linear programming (LP) approach for segmenting a color image into multiple regions. Compared with the recently proposed semi-definite programming (SDP)-based approach, our approach has a simpler mathematical formulation, and a far lower computational complexity. In particular, to segment an image of M × N pixels into κ classes, our method requires only O ((MNκ)m) complexity-a sharp contrast to the complexity of O ((MNκ)2n) if the SDP method is adopted, where m and n are the polynomial complexity of the corresponding LP solver and SDP solver, respectively (in general we have ≤ n). Such a significant reduction in computation readily 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 to 30 × 30 pixels in hours time, our algorithm can process larger color image of, say, 100 × 100 to 500 × 500 image in much shorter time.Keywords: Color image segmentation; Color images; Interactive image segmentation; Mathematical formulation; Multiple regions; Object cutout; Polynomial complexity; Process colors; Sdp methods; SDP relaxation; Semi-definite programming; Sharp contrast; Algorithms; C Interactive image segmentation; Linear programming; Object cutout200810.1007/s00138-008-0171-x2016-02-24