According to an embodiment of the invention, a method and apparatus for image segmentation are described. An embodiment of a method comprises inserting a state comprising a set of image segmentations into a queue, the queue being ordered by priority, the set of image segmentations having a priority representing a bound for a quality of the segmentations; extracting the state in the queue having the highest priority; if the extracted state is a terminal state, halting and outputting the extracted state as a solution; if the extracted state is not a terminal state refining the extracted state into a plurality of sets of segmentations, each of the plurality of sets having a priority, inserting the plurality of sets of segmentations into the queue, and iteratively repeating the extraction of the state in the queue having the highest priority.