# Mapping with Pleiades--End-to-End Workflow
## 4 Methods
### Digital Surface Model Generation
#### 4.2.2 Image Matching
Since the Pleiades images are huge, we propose an algorithmic extension mainly resulting in speed-up as follows. While in Reference [61] a hierarchical image pyramid based approach is used to determine the disparity search range for the final level (i.e., the original image), we apply the paradigm first presented in Reference [114] to limit the search range for each pyramid level (visualized in Figure 10). Instead of operating on the complete cost volume we propose to only use a band of this volume for disparity search. This change results in a significant speed-up, especially for scenes with large height variation, since we only have to search for a given number of disparities in the last level (e.g., 41 pixels instead of 2000 pixels, which is the average disparity range of the Ljubljana data set). Depending on the topography of the scene this cost volume (and also the aggregated cost volume) can be extremely large. For instance, on the Ljubljana test set this volume has a size of about 20 terabytes in 32 bit float encoding. With the proposed extension it shrinks to 2% of the original size, which is still around 400 gigabytes. We call this method _truncated SGM_. As depicted in Figure 10 it might be the case that for a disparity \(d\) the adjacent disparity \(d^{\prime}\) is not calculated thus does not exist. Therefore, we propose to modify the smoothness term given in Equation (3) to  
\[V(d,d^{\prime})=\left\{ \begin{array}{ll}\text{if $d^{\prime}$ exists}&\begin{cases}0&\text{if $d=d^{ \prime}$}\\ P_{1}&\text{if $|d-d^{\prime}|=1$}\\ P_{2}&\text{if $|d-d^{\prime}|\geq 2$}\\ \text{else}&P_{2}\,.\end{array} \right.\end{array} \tag{8}\]  
Depending on the 3D structure of the scene maximal memory consumption reduction between 65% to 99% is achieved while the runtime is reduced by 30% to 98% (also cf. Reference [65]). In addition, instead of storing the cost volume and the aggregate cost volume as 32-bit float values, we discretize them to 16-bit unsigned integers (uint16). This is done by introducing a scaling factor and yields another 50% memory reduction. This discretization obviously affects the results. However, the rationale is that the discretization changes the original values only a little bit (some fractions as the initial costs are in the range \([0,1]\)). Thus, if those small changes influence the argument of the minimum of the aggregated costs given in Equation (6), then those disparity values are very likely incorrect anyway. Such regions are later detected in blunder and occlusion classification and removed. Overall, the discretization has a non-significant influence on the final disparity map. Next, we observe that due to the prior epipolar rectification a significant region on the border of the input images consists of nodata values. In cases where all disparities of investigation only contain such invalid regions, the SGM optimization could be skipped. Therefore, we introduce a specific uint16 value for the disparity space image that indicates those regions. The runtime of the SGM optimization can then be reduced by around 33% (mean value over our test images). To gain speedup and accuracy, we incorporate a coarse DSM (e.g., SRTM DEM [115], ASTER GDEM [116], World DEM [117]) on the top pyramid level to calculate disparity predictions and thus to limit the search space and reduce ambiguities. For a grid of pixels in the reference image,  
Figure 10: Cost volume \(C_{P}(d)\) of classical SGM versus our implementation is shown on a toy example. While SGM evaluates the whole cost volume, we only check the disparities visualized in light blue color around the disparity predictions from the previous pyramid level depicted in dark blue color. In this toy example the search space is reduced to 44%, however, the reduction is larger in real satellite images. an image-to-map transformation is calculated using the coarse DSM. The resulting map coordinates are then projected into the search image with a map-to-image transformation.