Stereo by Two-Level Dynamic Programming

1. Introduction

Stereo is a useful method of obtaining depth information. The key problern in stereo is a search problern which finds the correspondence points between the left and right images, so !hat,

This research was done while Y.Ohta was visiting the Department of Computer Science, Carnegie-Mellon University. The research was sponsored in part by the Defence Advanced Research Projects Agency (DOD), ARPA Order No.3597, monitared by the Air Force Avionics Labaratory under Contract F33615-81-K-1539, and in part by the Air Force Office of Scientific Research under Contract F49620-83-C-0100.

Takeo Kanade

Computer Science Department Carnegie-Mellon University Pittsburgh, PA 15213

given the camera model (ie., the relationship between the right and left cameras of the stereo pair), the depth can be computed by triangulation. In edge-based techniques, edges in the images are used as the elements whose correspondences to be found [3,4,6]. Even though a general problern of finding correspondences between images involves the search within the whole image, the knowledge of the camera model simplifies this image-to-image correspondence problern into a set of scanline-to-scanline correspondence problems. That is, once a pair of stereo images is rectified so that the epipolar lines are horizontal scanlines, a pair of corresponding edges in the right and left images should be searched for only within the same horizontal scanlines. We call this search intra-scanline search. This intra-scanline search can be treated as the problern of finding a matehing path on a !wo-dimensional (20) search plane whose vertical and horizontal axes are the right and left scanlines. A dynamic programming technique can handle this search efficiently [2,3,7].

However, if there is an edge extending across scanlines, the correspondences in one scanline have streng dependency on the correspondences in the neighboring scanlines, because if two points are on a vertically connected edge in the left image, their corresponding points should, most likely, lie on a vertically connected edge in the right image. The intra-scanline search alol"e does not take into account this mutual dependency between scanlines. Therefore, analher search is necessary which tries to find the consistency among the scanlines, which we call

inter-scanline search.

By considering both intra- and inter-scanline searches, the correspondence problern in stereo can be cast as that of finding in a three-dimensional (3D) search space an optimal matehing surface that most satisfies the intra-scanline matches and inter-scanline consistency. Here, a matehing surface is defined by stacking 20 matehing paths, where the 20 matehing paths are found in a 20 search plane whose axes are left-image column position and right-image column position, and the stacking is done in the direction of the row (scanline) number of the images. The cost of the matehing surface is defined as the sum of the costs of the intra-scanline matches on the 20 search planes, while vertically connected edges provide the consistency constraints across the 20 search planes and thus penalize those intra-scanline matches which are not consistent across the scanlines. Our stereo matehing uses dynamic programming for performing both the intra-scanline and the inter-scanline searehes, and both searehes proeeed simultaneously in two Ieveis. This method reduees the eomputation to a feasible amount.

2. Use of Inter-Scanline Constraints

As mentioned above, for a pair of rectified stereo images, matehing edges within the same seanline (ie., the intra-seanline seareh) should be suffieient in prineiple. However, in praetiee, there is mueh ambiguity in finding eorrespondenees solely by the intra-seanline search. To resolve the ambiguity, we ean exploit the eonsisteney eonstraints that vertically eonneeted edges aeross the seanlines provide. Suppose a point on a conneeted edge u in the right image matehes with a point on a connected edge 11 in the left image on seanline t. Then, other points on these edges should also match on other seanlines. If edges u and 11 do not mateh on seanline t, they should not match on other seanlines, either. We call this property inter-seanline consisteney constraint. Thus, our problem is to search for a set of matehing paths whieh gives the optimal eorrespondence of edges within seanlines under the inter-seanline eonsistency eonstraint.

• A few methods have been used to eombine the inter-scanline search with the intra-scanline seareh. Henderson [7] sequentially proeessed each pair of seanlines and used the result of one scanline to guide the search in the next scanline. However, this method suffers by that the errors made in the earlier seanlines signifieantly affect the total results.
• Baker [2] first proeessed eaeh pair of seanlines independently. After all the intra-seanline matehing was done, he used a eooperative process to detect and correct the matehing results whieh violate the eonsistency eonstraints. Since this method, however, does not use the inter-scanline eonstraints directly in the seareh, the result from the eooperative proeess is not guaranteed to be optimal. Baker ·suggested the neeessity of a search which finds an optimal result satisfying the eonsisteney eonstraints in a 30 seareh space, but a feasible method was left as an open problem.
• A straighttorward way to aehieve a matehing whieh satisfies the inter-seanline eonstraints is to consider all matehings between eonneeted edges in the right and left images. However, sinee the typieal number of eonneeted edges is a few to several hundred in eaeh image, this brute foree method is usually infeasible.

We propose to use dynamie programming, which is used for the intra-seanline seareh, also for the inter-seanline seareh. These two searches are eombined as shown in figure 1. One is for the eorrespondence of all eonnected edges in right and left images, and the other is for the eorrespondence of edges (actually, intervals delimited by edges) on right and left scanlines under the constraint given by the former. The scheme to use dynamic programming in two Ieveis was first employed in the recognition of connected spoken words [10]. They used one search for the possible segmentation at word boundaries and the other for the time-warping word matehing under the eonstraint given by the former. In eonneeted word recognition, however, the pattern to be proeessed is a single 10 vector. In our ease, a connected edge crosses over multiple seanlines (ie., 10 vectors). This means !hat we need a 30 search space whieh is a stack of 20 search planes for intra-seanline matching.

Oynamie programming [1] solves an N-stage decision proeess as N si ngle-stage processes. This reduces the computational eomplexity to the logarithm of the original eombinatorical one. In order to apply dynamic programming, however, the original decision process must satisfy the following two requirements. First, the decision stages must be ordered so that all the stages whose results are needed at a given stage have been proeessed before them. Second, the decision process should be Mo.rko11io.n: that is, at any stage the behavior of the process depends solely on the current state and does not depend on the previous history. It is not obvious whether these properlies exist in the problem of finding correspondences between connected edges in stereo images, but we clarify them in the following sections.

3. Correspondence Search Using Two-Level Dynamic Programming

3.1. Inlra-stanline searth on 20 plane

The problem of obtaining a correspondence between edges on the right and left epipolar scanlines can be solved as a path finding problem on a 20 plane. Figure 2 illustrates this 20 search plane. The vertical lines show the positions of edges on the left scanline and the horizontal ones show those on the right scanline. We refer to the intersections of those lines as nodes. Nodes in this plane correspond to the stages in dynamic programming where a decision should be made to select an optimal path to !hat node. In the intra-scanline search, the stages must be ordered as follows: When we ezo.mine the correspondence of two edges, one on the right o.nd one on the left sco.nüne, the edges which o.re on the left of these edges on eo.ch sco.nüne must o.lreo.dy be processed. For this purpose, we give indices for edges in left-to-right order on each scanline: [O:M) on the right and [O:N] on the left. 8oth ends of a scanline are also treated as edges for convenience. It is obvious that the condition above is satisfied if we process the nodes with smaller indices first. Legal paths which must be considered are sequences of straight line segments from node (0,0) at the upper Jett corner to node (M,N) al the Jower right corner on a 20 array [O:M,O:N]. They must go from the upper Jett to the Jower right corners monotonically due to the above-mentioned condition on ordering. This is equivalent to the no-reversal constraints in edge correspondence: that is, the order of matched edges has to be preserved in the right and left scanlines. This constraint excludes from analysis thin objects such as wires and poles which may result in positional reversals in the image. A path has a vertex at node m=(m,n) when right edge m and Jett edge n are matched.

The cost of a path is defined as follows. Let O(m,k) be the minimal cost of the partial path from node k to node m. O(m,O) is the cost of the optimal path to node m from the origin (0,0). A primitive path is a partial path which contains no vertices and it is represented by a straight line segment as shown on figure 2. It should be noted that a primitive path actually corresponds to matehing the intervals delimited by edges at the start and end nodes rather than edges themselves. The cost of a path is the sum of those of its primitive paths. Let d(m,k) be the cost of the primi tive path from node k to node m. (Our actual definition of d(m,k) will be given in section 4.) Obviously, d(m,k)2:0(m,k) and on an optimal path d(m,k)aO(m,k).

Now, O(m,k) can be defined recursively as: O(m,k) =min ( d(m,m-i)+D(m-i,k)) {i} O(k,k) = 0 where m=(m,n), k=(k,l), i=(i,j), O~i~m-k, O~j~n-l, i+ )'10. (1)

I ntensity profiles are shown along each axis. The horizontal axis corres ponds to the left scanüne and the vertical one corresponds to the right scanline. Vertical and horizontal ünes are the edge positions and path selection is done at their intersections.

Vector i represents a primitive path coming to node m. When i=O, the primitive path is horizontal, as shown at (a) in figure 2. It corresponds to the case in which a visible part in the left image is occluded in the right image. When )=0, the primitive path is vertical, as shown al (b). When i>1 and/or j>1, the primitive palh skips or ignores beyond i-1 and/or j-1 edges on the right and/or Jett scanlines as shown at (c) in the figure. Such a path corresponds to the case where some edges have no corresponding ones on the other scanline because of noise.

The palh with cost O(M,O) gives the optimal .correspondence between a pair of scanlines.

3.2. Inter-scanline search in 3D space

The problern of obtaining a correspondence between edges under the inter-scanline consistency constraints can be viewed as the problern of finding a set of paths in a 30 space which is a stack of 20 planes for intra-scanline search. Figure 3 illustrates this 30 space. The side faces of this space correspond to the right and Jett images of a stereo pair. The cost of a set of paths is defined as the sum of the costs of the individual paths in the set. We want to obtain an optimal (ie., the minimal cost) set of paths satisfying the inter-scanline constraints. A pair of connected edges in the right and left images make a set of 20 nodes in the 30 space when they share scanline pairs. We refer

This may be viewed as a reetangular solid seen from above. The side faces correspond to the right and left stereo images. Connected edges in each image form sets of intersections (nodes) in this space. Each set is called a 30 node. Selection of a set of paths is done at every 30 node.

to this set of 2D nodes as a single 3D node. The optimal path on a 2D plane is obtained by iterating the selection of an optimal path at each 2D node. Similarly, the optimal set of paths in a 3D space is obtained by iterating the selection of an optimal set of paths at each 3D node. Connected edges, 3D nodes, and sets of paths between 3D nodes are illustrated in figure 3.

As described in section 2, the decision stages must be erdered in dynamic programming. In the intra-scanline search, their erdering was straightforward; it was done by erdering edges from left to right on each scanline. A similar consideration must be given to the inter-scanline search in 3D space where the decision stages are the 3D nodes. A 3D node is actually a set of 2D nodes, and the cost at a 3D node is computed based on the cost obtained by the intra-scanline search on each 2D search plane. This Ieads to the following condition: When we exo.mine the correspondence of two connected edf{es, one in the right o.nd one in the left imo.ge, the connected edges which o.re on the left of these connected edf{es in eo.ch imo.ge must o.lreo.dy be processed.

A connected edge u 1 is said to be on the left of u2, if all the edges in u 1 on the scanlines which u1 and u2 share are on the left of those in u 2 . The "left-of" relationship is transitive; if there is a connected edge u 3 and u 1 is on the left of u3 and u3 is on the left of u 2 , then u 1 is on the left of u2" The order of two connected edges which do not satisfy both the relations described above may be arbitrarily specified. We assign an erdering index from left to right for every connected edge in an image. This erdering is possible without contradiction when a connected edge never crosses a scanline more than once and when !wo connected edges never intersect each other. Our edge-linking process is devised so !hat it does not make such cases.

Now we will present how the cost of a 3D path is defined. Suppose we assign indices [O:U] to connected edges in the right image, and [O:V) in the left. The left and right ends of an image are treated as connected edges for ·convenience: the left ends are assigned index O's. Let u=(u,v) be a 3D node made by a connected edge u in the right image and a connected edge 11 in the left image. Let C(u) be the cost of the optimal sei of paths which reach to the 3D node u. The cost C(u) is computed as follows:

Here, C(u;t) is the cost of the path on scanline t in the optimal sei; !hat is, C(u)= LC(u;t), and D(m,k;t) is the cost of the optimal 3D primitive path from node k to node m on the 2D plane for scanline t. A 3D primitive path is a partial path between !wo 3D nodes on a 2D search plane and it has no vertices at the nodes belonging to a 3D node. So a 3D primitive path is a chain of 2D primitive paths and an intra-scanline search is necessary to obtain the optimal 3D primitive path on a 2D plane between given !wo given 3D nodes. The function l(u;t) gives the index of a 2D node belonging to the 3D node u on the 2D plane for scanline t. The numbers s(u) and e(u) specify respectively the starting and ending scanlines between which the 3D node u exists. The cost C(u) is minimized on the function i(t). A 3D node u-i(t) gives the start node of the 3D primitive path on scanline t. The inter-scanline constraints is represented by i(t). For example, if i(t) is independent of i(t-1 ), there are no constraints between scanlines and the search represented by equation (2) becomes equivalent to a set of intra-scanline searches which are performed independently on each scanline. Intuitively, i(t) must be equal to i(t-1) in order to keep the consistency constraint.

The iteration starts at u=(O,O) and computes C(u) for each 3D node u in ascending order of u. At each 3D node the i(t)'s which give the minimum are recorded. The sequence of 2D primitive paths which forms the 3D primitive path is also recorded on each scanline. The sei of paths which gives C(U) at the 3D node U={U,V) (which is the 3D node formed by the right ends of stereo images) is obtained as the optimal set. It should be noted !hat when there are no connected edges except for the right and left sides of the images, the algorithm (2) works as a sei of intra-scanline searches repeated on each scanline independent ly. In this sense, the 3D algorithm completely contains the 2D one.

3.3. Consistency constraints in inter-scanline

Using the term 3D node defined in the previous section, we can describe the inter-scanline consistency constraints as follows: F or o.ny 30 node, either o./.1 corresponding 20 nodes o.re the vertices on the set of po.ths in the 30 seo.rch spo.ce or none of them o.re the vertices on the set of po.ths. We need to represent this constraints as the relation between i(t) and i(t-1) in equat ion (2). To do this, Iet us consider the example in figure 4. Suppose we are trying to obtain a set of 3D primitive paths which reach to node u. In order to satisfy the consistency constraints above, all the slarting points of these paths should be the same 3D node; !hat is i(t)=i(t-1). The cases when the starting point is a different 3D node are shown as case2 and case3 in the figure. In case2, a new 3D node appears at scanline t and the starting point changes to the new one. Of course, it is possible that the starting point does not change to the new 3D node. This will happen if the cost of the paths having vertices on the 3D node is higher than the cost of the paths not having vertices on it. In case3, the 3D node u-i(t-1) disappears on scanline t and the starting point is forced

case 2

case 3

Figure 4. Three cases for consistency constraint.

to move elsewhere.

Let us denote the 3D node u-i(t), from which the 3D primitive path starts and reaches to the 3D node u on scanline t, by frm(u;t). Then the following rules should be satisfied in each case.

The rules in case2 and case3 require that the decision at 3D node u depend on decisions at preceding 3D nodes. Unfortunately, a decision system with such a property is not Mo.rkovio.n as described in section 2, and therefore there is no guarantee of obtaining an optimal solution by using dynamic programming. This means if we search for a solution using dynamic programming with those rules, the result might be poorer than that of the 2D algorithm.

In order to assure optimality in dynamic programming, we modify the rules in (3) as follows.

co.se3: frm(u;t) :s frm(u;t-1)

The new rule for case2 requires the new 3D node on scanline t be on the right of the 3D node !hat is the starting point on scanline t-1. For case3, the new starting node on scanline t should be on the left of that on scanline t-1. It should be noted !hat though the new rules are always satisfied when the rules in equation (3) are satisfied, the converse is not true. Thus, under the new rules, the consistency constraint might not be satisfied at all places. In other words, the constraints represented by the rules in equation (4) are weaker than those of equation (3). However, since we can expect to obtain an optimal solution in dynamic programming, we can expect better results by the 3D search algorithm than by the 2D search algorithm.

4. Experiments

Implementation of the stereo algorithm which has been presented requires a method of detecting edges, linking them into connected edges, and ordering the connected edges. We do not describe, however, the details of the method in this paper because of space Iimitation and it can be found elsewhere [9].

The computation of cost in our search algorithm is based on the cost of a primitive path on the 2D search plane. We define the cost of a 2D primitive path as the similarity between intervals delimited by edges in the right and left images on the same scanline. If we Iet a. 1 ··· a.k and b 1 ... b 1 be the intensity values of the pixels which comprise the two intervals, then the mean and variance of all pixels in the two intervals are computed as:

In the definition above, both intervals give the same contribution to the mean 1J. and variance r/ even when their lengths are different. The cost of the primitive path which matches those intervals is defined as follows:

We have applied our stereo algorithm to images from various domains including synthesized images, urban aerial images, and block scenes. Only a result with urban aerial images is presented here.

The stereo pairs used are aeri al photographs of the Washington, D.C. area. They have been rectified using the camera models which was computed by Gennery's program [5] using manually selected point pairs.

Figures 5, 6, and 7 show the original stereo pair, edges, and connected edges for the "white house" scene, respectively. The image size is 388x388 pixels and the intensity resolution is 8 bits. This example is an interesting and difficult one because it includes both buildings and highly textured trees. Many connected edges are obtained around the building while few are obtained in the textural part. The disparity maps obtained by the 2D and 3D search algorithms are shown in figure 8. Since the maps are registered in the right image coordinates, the disparity values for pixels on the right wall of the central building, which is visible in the right image but occluded in the left, are uridetermined. Considerable improvements can be observed at the boundaries of buildings. In the textural part, the two algorithms provide approximately the same results.

We counted the number of positions where the consistency constraint, described in section 3.3, is not satisfied. It is 436 in the 2D search and 32 in the 3D search. These numbers quantitatively show a significant improvement achieved by the 3D search algorithm. The reason why the inconsistency is not completely removed in the 3D case is that we used "weaker" rules for the constraint as described earlier.

5. Conclusion

In this paper, we have described a stereo algorithm which searches for an optimal solution in a 3D search space using dynamic programming. The algorithm has been applied to urban aerial images successfully. Perhaps one of the major reasons that our algorithm works weil for such a complex images is as follows. For images which contain long connected edges such as linear structures in urban scenes, our 3D search scheme works effectively to enforce the consistency constraint. When images do not contain long connected edges, our stereo algorithm reduces to the ordinary 2D search which works efficiently to match isolated edges within each scanline pair. In other words, when inter-scanline constraints are available, our algorithm fully utilizes them, otherwise it works as the 2D search. This feature will be less obvious in segment-based algorithms, such as in [8], which depend heavily on the connectivity of edges.

left image

Figure 7. Connected edges obtained from figure 6.