7A-1-1 
INTEGRATION OF FEATURE AND SIGNAL MATCHING FOR OBJECT SURFACE EXTRACTION 
Pakom Apaphant 
School of Civil Engineering 
Purdue University 
U.S.A. 
pakom@purdue.edu 
James Bethel 
School of Civil Engineering 
Purdue University 
U.S.A. 
bethel @ecn.purdue.edu 
KEY WORDS: Dynamic Programming, Stereo Matching, Feature Extraction, Signal Matching, Object Surface Reconstruction. 
ABSTRACT 
An integrated image matching method for object surface reconstruction is developed. The proposed method is rigorously based on 
photogrammetric principles incorporating some aspects of image understanding and computer vision. The matching problems are 
addressed by the integration of signal and feature matching. The innovative strategy arises within the framework of global optimization 
of the match function by dynamic programming. To increase computing speed, the algorithm is designed in such a way that it can be 
implemented in either a parallel or a sequential computing system. To evaluate the performance of the algorithm, images of both urban 
and non-urban scenes have been tested. The experiments have shown promising results using this approach. 
1 INTRODUCTION 
Complicated stereo matching problems are found in large scale 
images of urban scenes. Feature based matching (Medioni and 
Nevada, 1985), (Ayache and Faverjon, 1987), (Dhond and 
Aggarwal, 1989) has been used to address these problems. 
However the extraction process may yield ambiguous or incorrect 
solutions. Although successful feature matching may be achieved, 
the information from matched features is still not sufficient to 
reconstruct an entire object surface model. Signal based matching 
(Forstner, 1984), (Lobonc, 1996) can also be used for solving 
such a problem. This approach can work with images of rural 
scenes. Its results, however, suffer when the assumption that the 
terrain surface has smooth slope is violated. Many matching 
methods tend to be based on only one of these approaches. This 
trade-off is a dilemma in the matching process. In this research, 
the problems are addressed by the integration of signal and 
feature matching. 
Difficulties in matching can be exacerbated by badly chosen 
target search strategies. Using dynamic programming, object 
surface generation can be reduced to the problem of an optimal 
profile search from a cost matrix generated by a given stereo pair. 
Dynamic programming requires that the problem must be viewed 
as a multistage problem with interdependent variables. This 
technique generally consists of three parts which are (1) 
extracting the features to be matched and their descriptive 
attributes (2) generating a correspondence cost matrix and (3) 
searching for the optimal path in the cost matrix. Bernard 
(Benard, 1984) and Ohta and Kanade (Ohta and Kanade, 1985) 
can be regarded as the first groups among others who applied this 
concept to the stereo matching problem. Most current dynamic 
programming based matching techniques have been based on 
their frameworks (Lloyd et al., 1987), (Liu and Skerjanc, 1993), 
(Geiger et al., 1995), (Rojas et al., 1997). Dynamic programming 
has been proven to be an effective though time consuming 
strategy for stereo matching. Previous researchers applied this 
technique only for feature matching. In this research, the 
innovative strategy is the integration of feature and signal 
matching within the framework of the global optimization. 
Our matching process combines feature matching and signal 
matching, and into an integrated algorithm. The sequence of steps 
for feature matching would entail extracting features along 
epipolar lines in the images, matching the features on the left and 
right images. The conventional feature matching method by 
dynamic programming was modified to make the algorithm more 
robust. Then the feature coordinates are determined in the object 
space. After that the signal matching technique is applied to 
generate the elevation profiles. To increase the reliability of the 
searching technique, 3D information obtained from feature 
matching is integrated and used as constraints. The algorithm 
was based on line following by dynamic programming. (Bethel et 
al., 1998). Once all profiles in a model are determined, the 
surface in the object space can finally be reconstructed. To 
evaluate the performance of the algorithm, imageries of both 
urban and rural scenes have been tested. The experiments have 
shown promising results using this approach. 
2 PRIMITIVE FEATURE EXTRACTION 
Several types of primitive features are extracted from images, 
along with their positions in epipolar space. They are low level 
features which contain useful information for the matching 
process. These features are straight lines, edges, spikes, and 
plateaus. They not only contain significant information but also 
are not too difficult to extract. For all of these primitive features, 
either the extraction is done directly in the ID epipolar space, or 
the extraction is done in the 2D image space, and subsequently 
intersected with the ID epipolar lines. 
Straight line Extraction 
Straight line features occur predominantly in built-up or urban 
areas. This feature can contain much useful information for 
matching. In addition to the edge location; orientation, adjacent 
gray levels, and edge gradient are a few descriptive attributes. 
Generally, a straight line extraction process starts from extracting 
edge information, i.e. gradient magnitude and orientation. And 
then some refinements may be applied for line linking and line 
filtering. They are usually based on straight line parameters such