|
Matching of IKONOS Stereo and Multitemporal GEO Images for DSM Generation
3.2 Derivation of Approximations by Using Grid Point Matching based on Relaxation
The matching procedure can be treated as a labeling problem and solved by the relaxation technique. That is, we regard the template image (in our case, the left quasi-epipolar image) as the model and another image as the scene, and then use the feature points in the model as a set of labels to label the feature points extracted from the scene. Relaxation is one of the efficient methods to solve the labeling problem. The work of Hancock and Kittler (1990) that uses Bayesian probability theory has provided a theoretical framework and rigorous basis for the relaxation method. The important aspect of the relaxation matching algorithm that distinguishes it from the single point matching is its compatible coefficient function and its smoothness constraint satisfaction scheme (Baltsavias, 1991; Zhang et al., 1992). This is most important for areas with homogeneous or only little texture. In such areas, the single point matching is unable to match images because of the lack of information. With the smoothness constraint, such areas can be bridged over, assuming that the terrain surface varies smoothly over the area. Firstly, the match points are selected and distributed in the form of a regular grid in the template image. Given a grid point in the template image, a search window in the search image (the right quasi-epipolar image, in our case) can be determined. The correct match of this point should lie in this search window. However, due to repetitive texture or poor texture information, there could be several candidate matches appearing in the search window. These candidate matches are located along the epipolar curve. They can be derived by traditional cross-correlation technique, and the candidate matches are selected if their correlation coefficient lies above a certain user-defined threshold (we choose this threshold value as 0.7). The approximate centers of the search windows can be derived from the matching results of the previous pyramid level. Let Ii be one of the grid points on the template image and Ij (j=1,…,m) its candidate matches in the search image. P(i,j) is the probability of match Ik¬Ii. Moreover, let Ik be one of the points located in the neighborhood of point Ii and Il (l=1,…,m) be its corresponding candidate matches. In order to link the matching results of the neighboring grid points to each other, we define the following compatible coefficient function C(i,j;k,l) which quantifies the compatibility 
between the match Ii?Ij and a neighboring match Ik¬Ii: In equation (2), Dp expresses the difference of the x-parallaxes in point Ii and its neighboring point Ik. The bigger the Dp, the smaller the compatibility. This corresponds to a smoothness constraint on the image matching results, and it provides an ability to bridge over the poor texture areas. T is a value quantified by the texture information and it is defined as inversely proportional to the minimum of four gray value variances (horizontal, vertical, and along the two main diagonals) at the image window around the point Ii. Normally, if one point is located in rich texture areas or at linear features, this value is small. This value can be treated as the weight of the smoothness constraint and it provides the possibility to control the continuity of the terrain surface. ß is a constant and its value was set to 400 empirically. In the relaxation scheme, the so-called global consistency of matching can be achieved by an iterative scheme where the probabilities P(i,j) in iteration n+1are updated by the following rule: 
C(i,j;k,l) is the compatible coefficient function defined as above, W(Ii) is the neighbourhood of point Ii (can be its 8 or 24 neighboring points), and n is the iteration number. The quantity Q(n)(i,j) expresses the support the match Ik¬Ii receives at the nth iteration step from the matches Ik?Il in its neighbourhood W(Ii). The iteration scheme can be initialized by assigning the normalized correlation coefficient to P(0)(i,j) and, ideally the process will terminate when an unambiguous match result is reached, that is when each point Ii is matched with one candidate with probability 1, the probabilities for all other candidate matches for this point being zero. In practice, we terminate the process if any one of the following two conditions holds:
|