Ahmed Elaksher 
  
selected direction. The VLL concept is adopted for use in this algorithm. Each grid line is extruded vertically to create a 
2D grid in a vertical plane. Grid cells are defined by a planimetric interval and a vertical interval. Each cell in this array 
is projected into the left and right photos and a match coefficient is computed over a small region surrounding the point. 
This process is done similarly for all points in a grid profile creating a vertical plane of grid cells, each characterized by 
a match coefficient. If these coefficients are scaled into gray levels for display, then one can visualize the process. The 
picture of an approximated elevation profile would appear as a line on a noisy background, see Figure 4. 
m m! 
BEEENENEBEN En 
mEB EE EG NH BE 
EN BENBENN HEB m 
BRENNEN = NS ne 
: mESE N 
  
Figure 4. Cost Matrix with Costs Coded by Gray Value 
3.3 Searching Procedure 
A 2D dynamic programming technique for arbitrary line following is applied at this point to determine the low cost path 
between the endpoints of the terrain profile in each vertical plane. This variation of the technique uses path length as 
the stage and direction as the state. The arbitrary line following is modified in this case to restrict the search to paths 
that proceed from left to right, i.e. no overhangs or concavities in vertical segments. Thus at any given point in the cost 
matrix there are only five possible directions to move versus eight in the general line tracking problem. This path | 
propagation mask is stepped exhaustively through the the cost matrix for each increment in path length, from 2 to the 
maximum specified. 
3.4 Integration of Signal and Feature Matching 
During the optimization process, the object coordinates from matched features are used as constraints. An elevation 
profile should pass through these feature points. Because the correlation method may not work well in the vicinity of 
some features, the signal-derived profile in the vicinity of such features may be in error. Conversely, the DP search 
would try to pass through the feature points if they were assigned a very low cost. To achieve this goal, we can compel 
or encourage the search algorithm to pass through features by providing a very small cost to any cells which represent 
feature points. 
Although the feature matching algorithm is based on an optimization technique coupled with rigorous photogrammetry 
and image processing concepts, incorrect matches can still occur. If we therefore integrate features into the signal 
matching by the requirement that an optimal path must pass through the feature points, an incorrect result may be 
obtained. Our approach does not force the profile to pass through the feature points, it only encourages this by a very 
low (or negative) cost. This integration of feature matching and signal matching can work to achieve a result such that, 
Q The correct path will be obtained. The search technique will benefit from the redundant information in the intensity 
profile as well in the features. 
Q A consistency check for feature matching can be accomplished. For most good matches, there will be at least an 
accessible path to it. 
Once the optimal profiles from all grid lines are obtained, the object surface model can then be reconstructed. 
4 EXPERIMENTS 
A number of experiments have been carried out to verify the working of the above algorithm. A summary of one such 
experiment will be presented based on imagery over the Purdue University campus. 
  
270 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.