Image scene labeling with 3D image data. A plurality of pixels of an image frame may be label 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 neighborhood 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 some embodiments, in the MRF formulation pixels are adaptively merged into pixel groups based on the constructed data cost(s) and neighborhood cost(s). These pixel groups are then made nodes in the directed graphs. In some embodiments, a hierarchical expansion is performed, with the hierarchy set up within the label space.