Abstract
The Constrained Optimal Surface Tracking algorithm (COST) is developed for object surface construction. The proposed algorithm makes use of both signal and feature data in its stereo matching method. A global optimization concept is applied in several matching method based on dynamic programming is investigated and extended in this research. Several types of primitive features are extracted and matched. The signal matching process is driven from the object space. The concept of dynamic programming for line following is applied here to determine the optimal elevation profile of a grid line. The object coordinates from the results of feature matching are used as weighted constraints during this process. Once the entire area is searched, the surface model is then constructed. The capability of the algorithm is evaluated through the test on aerial imageries. The experiments yield the impressive results.

1.Introduction
The construction of 3D urban area spatial models from aerial images is a difficult problem that continues to challenge the researchers in photogrammerty and image processing fields. The main problems are occlusion, large parallax range, and feature textures which are not amenable to the matching process. Feature based matching has been used to address these problems (Huertas and Modioni, 1986) (Ayachea and Faverjon, 1987) (Dhond and Aggarwal, 1989). However, if only matched feature information is exploited, it is not possible to reconstruct a surface model completely. Signal based matching has been used for solving such problems as well (Canny, 1986). This approach is often not successful when the assumption of moderate slopes and transitions are violated. Several methods are based on only one of these matching approaches.

In this investigation, some of the problems found in stereo matching, will be addressed by a strategy of combined signal and feature matching based on a global search technique. The sequence of steps for the feature matching component would entail extracting features along epipolar lines in the images, and matching the features by a dynamic programming based approach (Bellman and Dreyfus, 1962) (Otha and Kanade, 1987). The feature coordinates in the object space are then determined. After that a signal matching technique with feature constraints is applied to generate the elevation profile. The integrated algorithm is based on a line following method (Bethel et al., 1998). Once all profiles in a model are determined, the surface in the object space can finally be constructed. In this research, imageries from several scenes have been processed with results compared against manual collection.

2. Feature Matching
Several types features are extracted from images, along with their positions in epipolar space. Some features used in this research are already well defined from elsewhere, such as the straight line feature, and some are developed here such as end points of a plateau feature, and the spike point feature (Apaphant and Bethel, 1999). The features are extracted and tagged with attribute values. These values contain useful information for matching process. For example, the attributes of straight-line feature employed here are line orientation and length of a line. After the extraction process, the features for each epipolar line are identified and ordered along each line independently from left to right.

Correspondence metrics are defined in order to quantify the similarity of pairs of these features. In the matrix, the feature points on a density profile from one image represent stages (or columns) while the ones from the other image represent the possible states (or rows) for each stage. Each node formed by one feature point, I, on the left and one feature point, j, on the right yields a cost c(ij). The calculation of the correspondence cost c(ij) generally depends on the descriptive attributes of the pair. A good match yield low cost, a poor match yields a high cost. A very high non-correspondence cost, c(nc) is assigned when the two considered feature points are determined to not correspond. The costs are computed for every combination. A two dimensional array of the correspondence cost matrix can then be constructed (Figure 1).


Figure 1: Feature matching by dynamic programming
Assume that the correspondence is known at the first and last column. The task is then to find the least cost path from the start point to the end point. Some stabilizing constraints are typically included to decrease the number of admissible paths. These constraints arise from the fundamental theory of stereo vision (Ballard and Brown, 1982).

By defining fi(j) as the minimum cost of the partial path from the first point to node (I,j), then fi. (j) is given by Equation1. For each node (i,j), the node (i-1,k) that gives the minimum partial path fi(j) is recorded.

f_i(j) =mink[c((i-1,k), (i,j)) + f_i-1(k)], where 1£k £ n (1)
Finally the optimal path can be found by backtracking from the last node (m,n) until the first node is reached. The path that sequentially connects these minimum nodes is the optimal path. The assigning of left and right to stages and states is arbitrary and in fact we do it both ways, with a consistency check between the two. Once the match pairs are determined, object coordinates of feature points can be computed by using the collinearity equations.