In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Voi. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009 
The 
ac- 
are 
the 
of 
to reduce the effect of canopy occlusions. The non-linear filter is 
a moving kernel of 7x7 that substitutes pixels classified as “tree” 
if and only if neighbours are “land”. In Fig. 7 red blobs put in 
evidence the reduction of occlusions due to the presence of trees. 
4.2 Roundabout Extraction 
After filtering, before extract roads, roundabouts are identified us 
ing a Hough transform applied to circular shapes. Hough trans 
form is useful to extract well-defined shapes as lines, circles or 
ellipse; the major drawback is the computational time, which is 
high especially for complex shapes (in terms of number of pa 
rameters) as ellipses. In Fig. 8, a roundabout extracted from 
Mannheim dataset is shown. 
Figure 8: Hough transform applied to Mannheim dataset to find 
circular shapes as roundabouts 
The Hough transform usually tends to overfit the real number of 
circular shapes; we use a double thresholding (min - max) to fil 
ter the output of Hough. Roundabout shown in Fig. 8 is cen 
tred on x = 1194, y = 378 with a radius of 47 pixels (about 
22m); min-max values are determined from typical values for 
small and/or large roundabouts. The input image for the Hough 
transform is obtained by the classified data; in Fig.7 the binary 
image is shown; the approach was tested also on different im 
ages to validate the extraction procedure; it is also possible to 
extract more complex roundabouts (e.g., elliptical) using the Ran 
domized Hough Transform also in presence of partial occlusions 
(Hahn et ah, 2007). The roundabouts identified with Hough trans 
form mask the filtered data supporting the next step: line extrac 
tion and clustering. 
4.3 Linear Road Extraction 
Segment extraction approach starts from the filtered data masked 
with roundabouts. Proposed method is similar to region growing 
technique usually applied in image segmentation; starting from 
a seed point of size one, classified as “land” the algorithm ex 
pand regions (in this case a segment) adding one or more pix 
els of same class; growing process ends when the region meets 
a set of N pixels classified as not-land. The main difference 
with the classical region growing is the size of growing space. 
In the case of image segmentation, growing space is 2D; in the 
case examined in this paper, the expansion is one-dimensional; 
next pixel (in both direction left and right) is calculated using 
the line parameters in terms of angular value; the pseudo-code 
of proposed algorithm is shown in Algorithm 1. The algorithm 
has two parameters: Tl and T2. Tl is used to stop growing 
process if Tl consecutive points (spurious pixels) classified as 
Algorithm 1 Extraction of linear segments 
Require: x vector of classified data 
1: S vector of extracted segments 
2: s vector of candidate pixels belonging to a segment 
3: p vector of aligned pixels 
4: for j = 0 to j < height do 
5: for i = 0 to i < width do 
6: for 0 = — 7t/2 to 7t/2 do 
7: p <— calculatesegmentjpoints(i,j, 9) 
8: start <— 0 
9: s.clear 
10: for k = 0 to k < p.size do 
11: n = count spurious „pixel s(s, start, x) 
12: ifn > T2Vi == (width— 1)Vj == (height — 
1) then 
13: if p.length > Tl then 
14: S.add(s) 
15: s.clear 
16: start «— k + 1 
17: else 
18: s.add(p[k\) 
19: end if 
20: end if 
21: k <- k + 1 
22: end for 
23: 9 «- 9 + 1 
24: end for 
25: i «- * + 1 
26: end for 
27: j «- j + 1 
28: end for 
not-land are encountered. T2 is a criteria to specify the mini 
mum length of segment; the values of these parameters were set 
to Tl = 2 and T2 = 30; a pyramidal down-scaling (factor 0.5) is 
performed on filtered data to reduce the complexity of computa 
tion. The calculatesegment-points(j,i,9) function, given an 
origin (j, i) in the image reference system, and an orientation 9, 
returns a list of pixels that belongs to the parametrized line, while 
the count spur iousjpixels(s, start, x) returns the number of 
spurious pixels (classified as not land) along the segment. The 
add function adds a segment to vector S or adds a pixel p[k] to 
the vector of candidate pixels belonging to a segment. In Fig.9 an 
example of segment extraction on a synthetic image is shown; the 
best segment orientation is chosen as the angular value that min 
imizes the number of segments extracted; if thresholds Tl and 
T2 are set properly, the minimum point is not strongly afflicted 
by the presence of noise. 
Figure 9: Segment extraction. Top image represent an ideal seg 
ment extraction while in the bottom it is tested a noisy image 
17