International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012 
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia 
  
  
I X I^ x 
N 90° / 135° 
y ^ y| 45 t 
07 
  
  
  
  
  
  
(a) 8 paths (b) 4 paths 
Figure 1: Investigated path orientations for eight and four paths. 
where p = [pz,Py]" is the pixel location in the left image and 
R is the area-based non-parametric rank-transform. It is defined 
as the number of pixels p' in a square M x M (here: M — 9) 
neighborhood A(p) of the center pixel p with a luminous inten- 
sity I less than I(p) 
R(p) ^ |(p' € A(p)| 1(p) « 1(p))|. Q) 
2.2 Census Transform 
The census transform (CT) maps the square M x M (here: M — 5) 
neighborhood A(p) of the center pixel p to a bit string where pix- 
els with an intensity less than I(p) are 1, else 0. Thus, 
Rp)z € ¢{Hp) Ip) 3) 
p'€A(p) 
with & the concatenation and£(a,b) 2 1 V a«b, 0 else. 
The matching cost between two pixels is the Hamming distance 
of the corresponding census transformed pixels, i. e. 
C (p.d) = 
|i € 0... M* — 1|Re (pz y) Rmi (ps — d. )]| 
where 2 indexes the bit position. The census transform is also 
non-parametric and area based. 
(4) 
Both methods are able to deal with radiometric differences since 
they depend on the ordering of the pixel's intensities rather than 
the absolute values. In contrast to the rank transform, spatial in- 
formation is retained by the census transform. 
2.3 Semi-Global Matching 
In many cases, pixel-wise calculated matching costs (i.e. locally 
calculated) yield non-unique or wrong correspondences due to 
low texture and ambiguity. Therefore, semi-global matching in- 
troduces global consistency constraints by aggregating matching 
costs along several independent, one-dimensional paths across 
the image. Thereby, SGM aims to approximate a global energy 
minimization problem which is NP-hard. The paths are formu- 
lated recursively by the definition of the path costs L, (p, d) along 
a path r. 
L,(p, d) = C(p, d) + min [Z-(p —r,d), 
LADE 
L.(p — r,d+ 1) + Pi, 
min Lr (p —r,i)+ Pa] — 
S) 
min L.(p — r,l) 
The first term describes the initial matching costs. The second 
term adds the minimal path costs of the previous pixel p — r 
including a penalty P; for disparity changes and P» for dispar- 
ity discontinuities, respectively. Discrimination of small changes 
|Ad| = 1pixel (px) and discontinuities |Ad| > 1 px allows for 
slanted and curved surfaces on the one hand and preserves dis- 
parity discontinuities on the other hand. The last term prevents 
constantly increasing path costs. For a detailed discussion refer to 
(Hirschmiiller, 2008). P; is an empirically determined constant. 
120 -l 
  
costs 
> 4 
\ Fier ias  ——— e] 
we : NY i i» Matching Costs || 
ivi N 7777 Path Costs 1 | 
| 
j —PathCosts2 | | 
i PathCosts3 | | 
| 7 Path Costs 4 = 
i | Path CostsS | 
|-——PathCosts6 | 
A x ss Path Costs 7 
2% 5 054 all . ¢ Num Path Costs 8 
y i > 
> 
* 
© some Sum Costs /6 | | 
  
ee 
“> 
  
  
0 10 20 30 40 50 60 70 
disparity 
Figure 2: Matching costs, aggregated path costs, and sum costs 
for the pixel p — [183; 278] of the Teddy image calculated with 
census transform and SGM. 
P» can also a empirically determined constant or can be adapted 
to the image content. The selection of these penalty functions is 
focus of this contribution and will be discussed in 3 in detail. 
Quasi-global optimization across the entire image is achieved by 
calculating path costs from multiple directions to a pixel, as shown 
in Fig. 1. The aggregated costs S are the sum of the path costs 
S (p.d) — 5 L. (p, d). (6) 
The disparity map Dj (pz, py) from the perspective of the base 
camera is calculated by selecting the disparity with the minimal 
aggregated costs 
min S(p, d) (7) 
for each pixel. For calculating Dy, (gz, gy), the minimal aggre- 
gated costs along the corresponding epipolar lines are selected: 
min S(qz +d, qy,d). (8) 
The effect of the path costs aggregation and the disparity selec- 
tion is illustrated in Fig. 2. The initial matching costs (dotted line) 
exhibit a high level of ambiguity. Seven of the eight aggregated 
paths costs already show distinct minima. The summed path costs 
(thick red line) clearly identify the minimum at a disparity level of 
32 resolving all ambiguities. However, the cost difference for the 
positions 32 and 33 is minimal indicating that the correct position 
is located a sub-pel precision. Half-pel accuracy is obtained by 
quadratic curve fitting through the neighboring sum costs around 
the minimum. An evaluation of sub-pel interpolation methods 
can be found in (Haller and Nedevschi, 2012). 
Both, uniqueness check and left/right check are performed to en- 
sure that only valid disparities with high confidence level are pro- 
duced. The uniqueness check sets disparities invalid if the min- 
imum ming S(p, d) is not unique. The left/right-check sets dis- 
parities invalid if the disparity Dy(p) and its corresponding dis- 
parity of D,, differ by more than 1 px. No post-processing steps, 
e. g. hole-filling or interpolation, are performed. An overview of 
the processing steps is given in Fig. 3. From (5) and Fig. 2 the 
crucial role of a "*good" selection of P, and P5 for the overall 
performance is obvious. It is suggested in (Hirschmüller, 2008) 
to adapt P»(I) to the image content in order to penalize abrupt 
disparity changes when, according to image content, a depth dis- 
continuity is unlikely. Therefore, it is clearly necessary to assess 
different functions for P; (I) and their influence on the algorith- 
mic performance, which is the scope of this paper. 
The 
(a)e 
(b)r 
dien 
(c) i 
dien 
lows 
(d) : 
sity 
In al 
boui 
upp 
P, ( 
shift 
(b) : 
ofte: 
poth 
disc 
ject 
3.1 
For 
data 
and 
tory 
ben 
32 | 
is p 
tion 
uate 
occ] 
defi 
ered 
folk 
pixe 
disp 
man 
proc