A multilevel image segmentation technique using graph cuts is disclosed. A reduced resolution image is generated from a full resolution image which is to be segmented. The reduced resolution image is then segmented in order to identify a boundary between an object and a background within the image. The identified boundary then identifies a portion of an increased resolution image which is segmented in order to refine the earlier identified boundary. The steps may be iterated for successively increasing image resolutions in order to refine the boundary as required by a particular application. An initial identification of object and background portions of the image may be provided as input by a user. Alternatively, a user may identify only the object portion, and the background portion may be automatically determined.