A method and an apparatus for multi-label segmentation of an image are described. First an energy function is determined for the image. Then for a homogeneous region of the image variables of the energy function are grouped to a single variable. Subsequently the energy function is minimized and labels are assigned to regions of the image based on the minimized energy function.