A depth sensing system receives an image pair showing objects in a scene. The system generates binary hashes for pixels in the image pair by performing a random walk. The system matches pixels in the first image to pixels in the second image that depict the same point in the scene by generating cost values representing differences between the binary hashes for pairs of pixels in the images. The system generates a disparity map containing disparity vectors representing coordinate differences between matched pixels in the first and second images. The system generates and outputs a depth map based on the disparity map. The depth map represents the distances between an image acquisition system that acquired the image pair and the objects in the scene.