Techniques are described for generating a distance map (e.g., a map of disparity, depth or other distance values) for image elements (e.g., pixels) of an image capture device. The distance map is generated based on an initial distance map (obtained, e.g., using a block or code matching algorithm) and a segmentation map (obtained using a segmentation algorithm). In some instances, the resulting distance map can be less sparse than the initial distance map, can contain more accurate distance values, and can be sufficiently fast for real-time or near real-time applications. The resulting distance map can be converted, for example, to a color-coded distance map of a scene that is presented on a display device.