The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part BI. Beijing 2008 
1111 
In this case, we have two stereo pairs, that is, the pair / 0 -/ y and 
Itrh- For a given point p 0 in the reference image, we can 
establish the image ray Cp 0 (here C denotes the instant 
perspective center related to point p 0 ), on which the 
correspondence of p 0 in object space should lie, with the known 
image orientation parameters. By intersecting the image ray Cp 0 
with a horizontal plane defined by a given approximate height Z 0 , 
we obtain P 0 (X 0 , Y 0 , Z 0 ) in object space. The approximate height 
Z 0 may have an increment AZ, such that the correct position of 
P 0 in object space should lie between P min and P max , with height 
values of Z 0 -AZ and Z 0 +AZ respectively, along the image ray 
Cp 0 ■ If we back-project the points between P min and P max onto 
the search images, the corresponding segments of the 
quasi-epipolar lines for the point p 0 can be easily defined. The 
correct matches p u i=l,2 in the search images I u i=I,2 must lie 
along its corresponding quasi-epipolar line segments. 
Fig. 2: Multiple image matching with the GC 3 algorithm. 
For details please refer to the text. 
Let I 0 (p) and Ifp) be the image intensity values of the reference 
and the z'th search image respectively. In the reference image, we 
define a correlation window W around the point p 0 . We assume 
that an approximate DSM is known either as a horizontal plane 
or from matching results at a higher level of the image pyramid. 
If we project this window onto the approximate DSM through 
the so-called mono-restitution procedure, we can obtain a piece 
of surface patch in object space. Then, we back-project this 
surface patch onto the search images, thus generating the 
corresponding image window in the search images. We named 
this process “correlation window warping procedure”. Through 
this reshaping procedure, a square correlation window in the 
reference image can be correlated with windows of different size, 
shape and orientation in the search images. Therefore, multiple 
images with different image scale and orientation can be 
matched straightforward. The distortions caused by terrain relief 
and imaging geometry can be compensated (more details please 
refer to Zhang, 2005. 
Now the Normalized Correlation Coefficient (NCC) value 
between the corresponding correlation windows in the reference 
image and the z'th search image can be defined, with respect to 
the height Z forp 0 , as: 
NCCf Po ,Z) 
^/„(sWoM/^XZ))-/,) 
sefV 
jXVoM-'ofjXaw 2 ))- 7 ') 2 
V self V self 
(1) 
Here, 
/„=—£/«(*); 
mxn,ew 
/,=—Z ; .( 5 .( z )) ,=1 ’ 2 
mxnidr 
Where, W and s denote the correlation window in the reference 
image and a pixel in this window respectively; m and n denote 
the dimension of the correlation window W. sfZ) denotes the 
corresponding point to s in the z'th search image. As mentioned 
before, sfZ) can be computed through the correlation window 
warping procedure. The intensity values for point sfZ) are 
interpolated from the z'th search image by using the bilinear 
interpolation method. 
As can be seen from equation (1), the value of NCC, is defined 
with respect to the height value Z, which could be any value 
between 7. 0 -A7. and Z 0 +AZ. Thus, given a point in the reference 
image, as well as its approximated height Z 0 and an increment 
zlZ in object space, the NCC functions for all individual stereo 
pairs are defined within a unique framework. We then follow the 
procedure proposed by Okutomi and Kanade (1993), instead of 
computing the correct match of point p 0 by evaluating the 
individual NCC functions between the reference I 0 and search 
image /,, z -1,2, we define the sum of NCC (SNCC) for point p 0 , 
with respect to Z, as: 
SNCC( Po , Z) = 1X zVCC, (p 0 ,Z) (2) 
^ /=1 
Therefore, by finding the value Z. Z e[Z (r AZ, Z 0 +AZ] which 
maximize the SNCC function, we can obtain the corresponding 
height value for point p 0 . Here, the height increment AZ 
determines the search distance along the corresponding 
quasi-epipolar lines. Through the definition of the SNCC 
function, which simply accumulates the NCC functions of 
cross-correlation from all the stereo pairs, the correct match or 
correct height in object space for a given point in the reference 
image can be obtained. In general, the matching candidates show 
maxima in the SNCC function and each peak of the function 
SNCC corresponds to an object point with a certain height value. 
In the GC 3 algorithm, these object points are defined as the 
matching candidates for the given point. The method can be 
easily extended to a more general case, which is suitable for n+1 
{n > 1) images. 
SNCC(p„Z) = 1Y j NCC,(p„Z) (3) 
n M 
In Fig. 3, an example of high-resolution airborne linear array 
image strips (ca. 5cm footprint) is shown in order to highlight 
the ability of the GC 3 algorithm to solve the multiple solution 
problem. Fig. 3 (b) shows that it is very difficult to determine the 
correct match by just evaluating each individual NCC value. 
However, the SNCC shows a sharp and clear maximum at the 
correct match, even within a large search distance. 
2.3 Summary of the DSM/DTM Generation Approach 
Our automatic DSM/DTM generation approach is characterized 
by the following items: 
(1) Multiple image matching: We have developed a new 
flexible and robust matching algorithm -GC 3 method in order to 
take advantage of the multiple images. The algorithm is based on 
the concept of multi-image matching guided from object space 
and allows reconstruction of 3D objects by matching all 
available images simultaneously, without having to match all 
individual stereo-pairs separately and merge the results. 
(2) Matching with multiple primitives: We have developed 
more robust hybrid image matching algorithms by taking 
advantage of both area-based matching and feature-based 
matching techniques and utilizing both local and global image 
information. In particular, we combine an edge matching method 
with a grid point matching method through a probability 
relaxation based relational matching process. The use of edges 
leads to the preservation of surface discontinuities, while grid 
points bridge areas with little or no texture. 
(3) Self-tuning matching parameters: The adaptive 
determination of the matching parameters results in higher