Image segmentation utilizing 3D image data. A plurality of pixels of an image frame may be segmented based at least on a function of pixel color and a pixel depth over the spatial positions within the image frame. A graph-cut technique may be utilized to optimize a data cost and smoothness cost in which at least the data cost function includes a component that is a dependent on a depth associated with a given pixel in the frame. In further embodiments, both the data cost and smoothness functions are dependent on a color and a depth associated with each pixel. Components of at least the data cost function may be weighted for each pixel to arrive at most likely segments. Segmentation may be further predicated on a pre-segmentation label assigned based at least on a 3D spatial position clusters.