na 
se 
to 
ell 
rst 
the 
tor 
uld 
ine 
his 
us 
be 
re. 
> a 
Ahmed Elaksher 
2.4 Spike Feature 
In two-dimensional space, several methods have been successfully developed for point feature extraction. The spike 
feature is characterized by the appearance of a sharp peak or valley within a homogeneous region of an intensity profile. 
Like the plateau feature, ideal spike points should be easily detected from a profile by human eyes. In an image, spikes 
may include both point features such as manholes, and also linear features which cross the epipolar line. From this point 
of view, it is possible that some spike points may produce multiple detections as both spike points and line features. 
Actually one of the objectives in pursuing spikes was to recover missing straight line points. Although some features 
may be extracted twice, the matching logic precludes matching across feature types. 
3 CONSTRAINED OPTIMAL SURFACE TRACKING (COST) ALGORITHM 
3.1 Feature Based Matching 
The features described are extracted and tagged with attribute values. After the extraction process, the features for each 
line are identified and ordered along each line independently from left to right. In a 2D (feature only) cost 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. 
Correspondence metrics are defined in order to quantify the similarity of pairs of these features. Each pair formed by 
one feature point, 7, on the left and one feature point, j, on the right yields a correspondence cost ci. The calculation of 
the correspondence cost cj; generally depends on the descriptive attributes of the pair. A good match yields a low cost, a 
poor match yields a high cost. A very high non-correspondence cost, c, is assigned when the two considered feature 
points are determined to not correspond. A two dimensional array, the correspondence cost matrix, can then be 
constructed. At every transition path from an element in one column to an element in the next column, there is a path 
cost. This path cost is a function of the correspondence costs of the two elements in the adjacent columns. 
Assume that the correspondence is known at column 1 and column m. 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. Since one point on the left has at most one 
corresponding point on the right, the admissible path must proceed monotonically left to right and top to bottom. 
Another necessary constraint is a parallax constraint. Given a minimum and maximum allowable elevation jump, there 
is a corresponding minimum and maximum parallax or disparity change between successive features (columns). This 
constraint maintains the path within a parallax~band from upper left to lower right in the cost matrix. Among the set of 
all possible paths, one is optimal, i.e. it corresponds to a minimum total cost. This path determines the conjugate feature 
pairs, and these can be intersected via the usual photogrammetric equations to yield object space coordinates. Figure 3 
shows a typical set of matched features in urban imagery. 
  
  
No 
  
  
  
Figure 3. Typical Results from Feature Matching 
3.2 Signal Based Matching 
Correct correspondence at the signal level needs to be accomplished to supplement and densify the results of feature 
matching. The results from feature matching are only the coordinates of some points on extracted features, or all of the 
feature points at best. It thus represents only a sparse surface model. The proposed signal matching algorithm is driven 
from ground space so it is, initially, completely separate from the feature matching process. A regular grid is first 
established in object space. The method is designed to find the elevation profile along each gridline, for an arbitrarily 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 269