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
