Interactive color image segmentation with linear programming
Date
2008
Authors
Li, Hongdong
Shen, Chunhua
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Abstract
Image 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.
Description
Keywords
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 cutout
Citation
Collections
Source
Machine Vision and Applications
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31