This algorithm reminded me of the Active Appearance Model algorithm, which is used to estimate the shape of an image by trying out different parameterizations of the shape, warping a generated image of average shape to fit the generated shape, and testing the similarity between the warped image and the actual image. So it's like the depth map is the shape in AAM.

I'm confused about Section 2.2. Am I right to think the neighborhood hypothesis is that, for unmatched regions, the depth is probably the depth of it's neighbors? Why are there only k+1 depth hypotheses for each segment? Is that just it's ordinate depth compared to its neighbors? Aren't you trying to get some sort of relative measure? Maybe my confusion on this matter is causing my added confusion about why there are (k+1)^s total hypotheses. It seems like this calculation is too simple and is double counting.