Various implementations relate to improving depth maps. This may be done, for example, by identifying bad depth values and modifying those values. The values may represent, for example, holes and/or noise. According to a general aspect, a segmentation is determined based on an intensity image. The intensity image is associated with a corresponding depth image that includes depth values for corresponding locations in the intensity image. The segmentation is applied to the depth image to segment the depth image into multiple regions. A depth value is modified in the depth image based on the segmentation. A two-stage iterative procedure may be used to improve the segmentation and then modify bad depth values in the improved segmentation, and iterating until a desired level of smoothness is achieved. Both stages may be based, for example, on average depth values in a segment.