# Mapping with Pleiades--End-to-End Workflow
## 4 Methods
### Digital Surface Model Generation
#### 4.2.2 Image Matching  
As the image matching is employed on epipolar images, the disparities have to be searched along one dimension only, that is, the column direction. The classical matching paradigm is depicted in Figure 9 and consists of three main steps: disparity space image calculation (i.e., creation of the 3D cost volume), cost aggregation (i.e., an optimization by incorporating the neighborhood of a pixel) and disparity section (i.e., selection of the final disparity per pixel from the aggregated cost volume). The current state-of-the-art in cost volume calculation is the normalized Hamming distance of the Census transform [72], as it is invariant to non-linear radiometric distortions and very efficient in its calculation. Since it compares all pixels within a patch to the central pixel value the transform becomes ambiguous when the patch holds homogeneous, that is, textureless, values. Therefore, the modified Census can be used that compares the pixels to the mean value of the patch [75; 111]. We propose another option that works well for satellite-based images, which is to stabilize the Census transform by combination with a _sum of absolute differences_ (SAD) cost function. SAD is normalized by the bit depth of the images, that is, 216 for Pleiades. Normalized cross-correlation yields more blurring at 3D breaklines than Census transform such that it is not applied (cf. Reference [73]). It is also important to note that within this work the matching only uses the panchromatic band of the image. Obviously, the pansharpened multi-spectral information could be used as well. In this case, the combined cost-function is defined as the weighted sum of the costs for each spectral band. However, previous  
Figure 8: Relation of stereo input images, their epipolar rectified versions, forward and backward addresses and both disparity maps. Boxes represent images and arrows the geometric transformation between them. experiments showed that color information is not helping much but slows down the calculation of the disparity image significantly [112]. The influence of the patch size on the performance in terms of runtime and accuracy is evaluated in Reference [73], where a \(9\times 9\) pixel patch performs best. In literature often \(9\times 7\) pixel patches are used as those 63 bits can be efficiently stored in a 64-bit register (cf. Reference [113]). After calculation of the cost volume the cost aggregation is performed with semi-global matching (SGM) introduced in Reference [61]. It combines the efficiency of a local method with an accuracy comparable to global methods. This is achieved by approximating a 2D Markov random field (MRF) optimization with several 1D scanline optimizations (cf. Reference [71]). Those scanline optimizations can be efficiently solved via dynamic programming yielding low runtimes. It has been shown that SGM is a special case of message passing algorithms like belief propagation and tree-reweighted message passing [69]. Overall, SGM approximates the energy minimization of a 2D Markov random field  
\[E(D)=\sum_{\mathbf{p}}C_{\mathbf{p}}(d_{\mathbf{p}})+\sum_{\mathbf{p},\mathbf{q}\in\mathcal{N}}V(d _{\mathbf{p}},d_{\mathbf{q}})\, \tag{2}\]  
with \(C_{\mathbf{p}}(d_{\mathbf{p}})\) being a unary data term that represents the matching cost of a matching pixel \(\mathbf{p}\) at disparity \(d\in\mathcal{D}=[d_{\min},d_{\max}]\) and \(V(d,d^{\prime})\) is a pairwise smoothness term that penalizes disparity differences between neighboring pixels in the neighborhood \(\mathcal{N}\). In SGM, \(V\) implements a first-order smoothness constraint as  
\[V(d,d^{\prime})= \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\,,\end{cases}  \tag{3}\]  
with the penalty values \(P_{1}\) and \(P_{2}\). They penalize disparity jumps of 1 pixel and of multiple pixels. Now instead of minimizing the MRF, which is NP-hard, SGM minimizes a 1D version of Equation (2) along 8 cardinal directions \(\mathbf{r}\) via dynamic programming [61].