Graphics Reference
In-Depth Information
(a)
(b)
occlusion
scanline in I
1
(c)
Figure 5.16.
Scanline matching using dynamic programming, as described by Ohta and Kanade
[
352
]. (a) and (b) Two rectified images of the same scene from different perspectives, with an
overlaid scanline. (c) The matching path for the dynamic programming problemmust go through
the nodes generated by pairs of edges in each scanline. The path must proceed from the lower
left corner to the upper right corner without doubling back on itself; occlusions can be modeled
as horizontal or vertical lines.
where
C
could be any of the cost functions discussed earlier. Appendix
A.1
describes
how to set up and solve the dynamic programming problem. Limiting the maximum
allowable disparity can greatly reduce the complexity of finding the solution.
As illustrated in Figure
5.16
, occlusions in either image can bemodeled as horizon-
tal or vertical segments in the dynamic programming graph. However, note that this
formulation requires
monotonicity
—that is, the property that corresponding points
appear in the same order along matching scanlines. This assumption is not always
justified for real images, as characterized by the
double nail illusion
illustrated in
Figure
5.17
.
Extensions to the basic dynamic programming approach involved determining
the best cost function
C
in Equation (
5.49
), and more importantly, determining
how to assign reasonable costs to occluded regions. For example, Belhumeur [
37
]
