An Automated Digital Elevation Extraction System
5.1 1D vs 2D matching
Mathematical matching processes involve finding a best match in the right image for a given point, area or feature in the left image. The best match is obtained by finding a minimum or maximum of a quantitative measure such as a correlation coefficient, mean square error (MSE) and mean absolute error (MAE). For a candidate pixel in the left image the matching pixel is displaced from the corresponding location in the right image, the displacement proportional to the height of the feature images by the pixel. Since individual pixels are hard to match a group of pixels centered around the candidate pixel is taken. This is called the candidate area. The area to be searched in the right image to find the best matching area is called the search area. The size of the search area is dependent on the maximum possible displacement. The candidate area and the search area can be one dimensional since the displacement due to the heights is only along the X direction on the epipolar line. Though processing one dimensional areas are easier in computation and hence the throughput, matching becomes a more difficult task. Since actual features are three dimensional and images in two dimensions the reliability of a one dimensional match is lesser when compared to match between two dimensional areas. Imaging an operator positioning the floating mark seeing only two lines from the stereo pair. In addition, practically it is very hard to have no Y-parallax. The possibility of no reliable match that meets some criteria leads to elevations not available for a given location . A worse situation is the possibility of false matches which lead to erroneous elevation values that can cause bigger problems when the elevation values are interpolated to a finer grid. Though these possibilities still hold for two dimensional matches the complexity of the problem is much lesser. for this reason two dimensional matching is adopted.
5.2. Block Matching Method
Automating the cross correlation process is typically done by a block matching approach. For a candidate block from the left image a best match is found by searching in neighborhood of the corresponding area from the right image. Though intelligence can be added in the search process we will examine a brute force search in two dimensions. A Small candidate area, an NxN block of pixles, is chosen on the left image centered around a specific the corresponding location in the right image a search area is chosen of size MxM where m=N+2* p where p is the maximum possible absolute parallax. Though a square block size is discussed , the blocks can be rectangular to take advantage of the extent of the residual Y-parallax. The candidate block is compared against a same sized block from the search area and a quantitative measure ( correlation coefficient, mean square error, mean of absolute error) of matching obtained. The process is repeated at all possible (2p+1)x(2p+1) locations on which the block from the search area can be centered. A best matching block is regarded as one that has the maximum correlation coefficient or minimum mean square error (MSE). The center of best matching block from the search area ( right image) is considered to be the match point for the center of the candidate block (left image). The parallax is computed from the locations of the candidate point and the match point. The camera models of the two images and the parallax gives the ground location and the elevation at that point. Elevations have to be computed in a similar manner for all desired points. This methods is computationally
heavy. A large number ( 2p+1) x(2p+1)) of correlation coefficients have to be computed and maximum among them found for every elevation value.
5.3 The Correlation Surface Method
The proposed method uses the cross correlation surface created using basic ED-FFT processes to obtain the matching point. Once the images are initially registered and a stereo pair obtained, corresponding matching points are only displaced mostly in the X direction due to elevation. However for reliability as explained earlier two dimensional areas are considered. An NxN candidate block is chosen in the left image and another NxN block centered at the same location is picked in the right image. The two block are transformed by two dimensional Fourier transforms (2D-FFT), the transformations multiplied in the frequency domain and the result is inverse transformed to obtain a two dimensional cross correlation surface. The cross correlation surface values indicate the extent of matching to the candidate block at each possible shift location in the right image. The peak of the correlation surface indicates the location of the best match. A zero parallax is indicated by a peak at the center of the cross correlation surface which is the null shift location. The location of the peak from the null shift location indicates the parallax or the displacement vector. If the images are in perfect stereo pair there will be no shift in Y but only in X. From the X-displacement value are obtained. By this method the maximum detected pixel displacement can only be half the size of the block i.e. N/2. It is hence important that the block size be bigger than twice the maximum possible displacement.
The primary differences between the correlation surface method and the block matching (BM) method discussed earlier are as follows. The BM method performs computations in the spatial domain while the correlation surface method performs operations mostly through frequency domain. In the BM method the candidate block can be of any size. The maximum possible X-parallax influences only the size of the search area in the right image. Several correlation coefficients are computed for each possible shift location and the maximum among them is found . In the correlation surface method the candidate block from the left image and the corresponding block from the right image have the same dimensions. Both have to be at least of size 2p in the X dimension to detect the maximum possible parallax, p. We will discuss later how this can be avoided. In the new method only one correlation surface ( not coefficient) is computed from basic principles. Conceptually both methods are very similar.
5.3.1 False Mathces
The use of correlation surfaces or coefficients poses problems. False matches result as high cross correlation values where there is no suitable match at all. This can happen if the area under consideration is over structure less areas such as water, clouds, homogenous features etc. The quality and reliability in results from cross correlation based methods should hence be primarily based on how effective the method is to detect false correlations so that elevations computed from such matches are dropped. Studies have been conducted on a variety of image to develop a set of tests fro analysing the cross correlation surface. Currently about two dozen tests are
