This paper deals with a scene pre-processing task — depth image segmentation. Efficiency and accuracy of several methods for depth map segmentation are explored. To meet real-time capable constraints, state-of-the-art techniques needed to be modified. Along with these modifications, new segmentation approaches are presented which aim at optimizing performance characteristics. They benefit from an assumption of human-made indoor environments by focusing on detection of planar regions. All methods were evaluated on datasets with manually annotated real environments. A comparison with alternative solutions is also presented.