International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B4, 2012 
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia 
© Find the pixel with minimum original grey-scale value along 
L; (i=1,3,5,7) within the target region as a new seed if the initial 
direction is d; (i=1,3,5,7). 
© Find the pixel with minimum original grey-scale value along 
L;, and L;-, (i=2,4,6,8; Ls-1=L; ) within the target region as a 
new seed if the initial direction is d; (i=2,4,6,8). 
Step 2: Perform k-means clustering within the 5 X 5 
neighbourhood of the seed, obtaining new clustering centre C 
and Ca - 
Step 3: Find the pixels in the 5X 5 neighbourhood meeting the 
following two rules, add them into the object region, and set 
their grey-scale values to be 1. 
Rule 1. The grey-scale difference between the pixel and the 
object clustering centre is smaller than that between the pixel 
91 
z 
and background clustering centre, i.c., | eg a| < | ge 
  
Rule 2. There is at least one pixel with binary value 1 in the 8- 
neighborhood. 
Step 4: Find the pixel with minimum original grey-scale value 
in those pixels belonging to the newly grown target region at 
the four sides of the 5X 5 neighbourhood as a new seed. 
Step 5: Repeat Step2-Step4 until the edge of the sliding 
window is reached. 
Step 6: Set the grey-scale values of pixels belonging to the 
background region to be 0. 
After the above steps, the segmentation result in the sliding 
window is obtained (see Figure 6). 
  
167 161 136 161 169 152 132 133 143 101 293 124 140 133 146 150 138 138 145 140|146 142 131 127 132 
  
131 131 144 131 122 129 139 121 91 102 120 117 126 149 139 129 139 152|139 1310146 1385120 i0g i19 
; i 
131 128 141 135 132 135 132 103 294 125 132 137 143 139 145 1521145 133|137 123$ 106 in 3 98 .91 
153 155 133 146 145 119 92 96 133 130 129 151 155 1351145 157{142 1191118 102 107 1091108 114 
d pe 
144 140 129 126 108 97 110 118 130 140 143 137 134 144! 142 1298118 106K 974102{133/140 130130 141 
  
  
  
  
  
  
  
  
137 128 143 112 86 105 141 136 135 149 147 13711351146:131 108 L9 9511972130 145/149 152]156 151 
  
145 144 142 103 100 127 137 135 149 147135 148]157:121, 101,109]1101112:136,156 148]152 168 L74 164 
164 158 143 104 111 138 140 150 160 151}145 154] 152 4160p} 1261142} 152 158}164 170 173 172 166 179 
165 148 153 119 100 128 158 172 161|t66]iT5 1501017 121] 1381147 163178 169 167 188 190 175 168 185 
IST 150 159 129 98 111 145 159 161]171} 165}13a] 108 128} 159 {176 1791164 170 186 176 174 191 179 179 
  
  
  
  
  
  
  
  
  
  
164 184 183 127 118 106 111 136 166{161}131 (119) 129. 141] 166] 192 188 164 176 195 178 181 200 179 167 
168 176 159 151 129 105 114 144 160]161 [138 1iQl20 67] 187170 176 197 185 165 191 202 198 187 179 
  
168 134 170 186 135 110 120 137 1491167 1561118 i160 1901172 178 187 182 179 201 210 182 189 208 
  
  
  
164 167 168 169 173 156 117 136 182 167|148 153 119 114 143]175 179 152 170 209 190 182 186 185 181 
154 179 162 154 181 175 135 132 168 165]156 153] 142 110 112]128 132 128 163 201 170 159 191 183 156 
160 146 160 175 159 153 163 143 120 160 187 174 185 151 141 117 100 125 162 170 171 183 181 177 181 
  
  
  
161 146 160 168 156 156 165 139 106 138 163 167 169 164 158 139 115 123 136 147 176 190 178 174 178 
157 171 164 150 167 173 160 135 110 116 136 162 175 163 156 166 160 129 109 133 151 161 180 177 156 
153 161 162 160 164 163 169 154 110 112 140 169 173 168 169 188 186 158 121 116 114 128 161 177 165 
157 146 167 171 155 152 172 166 115 115 148 173 171 186 190 178 177 175 149 121 108 109 121 153 177 
156 154 159 153 159 170 163 146 126 113 143 177 169 189 194 181 181 180 161 150 140 118 101 114 142 
143 166 165 139 157 177 159 138 134 112 112 157 180 172 173 194 198 182 166 174 162 130 115 97 97 
154 152 157 160 142 155 160 146 139 113 111 159 180 175 173 185 184 175 163 151 147 156 135 95 88 
167 140 146 160 145 148 162 159 115 103 132 174 158 184 186 159 148 157 154 131 135 156 134 103 99 
127 140 136 122 143 137 151 147 107 97 112 145 158 163 161 163 154 130 148 151 147 130 132 142 102 
Figure 6. K-means clustering and directional region growing in 
the sliding window 
3.2 Sequential line tracking 
After image segmentation, a thinning operation is performed, 
followed by a line tracking process in the sliding window. By 
moving the window continuously along the line and doing the 
above operations iteratively, the line is tracked sequentially 
until an endpoint or an intersection is met. 
Before giving the algorithm, we first introduce several terms in 
binary thinned images (see Figure 7). 
Endpoint: The point with one black pixel in the 3 X 3 
neighbourhood. 
Connecting point: The point with two black pixels in the 
3 X 3 neighbourhood. 
Crossing point: The point with more than three black pixels in 
the 3 X 3 neighbourhood. 
(a) (b) (c) 
Figure 7. a Endpoint. b Connecting point. c Crossing point 
The sequential line tracking algorithm is described as follows. 
Step 1: Find a connecting point P, as the starting point in a 
3 X 3 neighbourhood in the centre area of the sliding window. 
Step 2: Select a point from the two black pixels in the 3X3 
neighbourhood of P, with a close direction d to the current 
direction (The initial direction is input by a human operator). 
Step 3: Make the current point invisible (set it to be white), and 
track to the next point P; in direction d Ci is counted from 1) . 
Step 4: Distinguish P; in 3 X 3 neighbourhood. There are three 
cases as follows. 
@ If P; is a connecting point, there remains only one black 
pixel in its 3 X 3 neighbourhood but the invisible point, use its 
direction as tracking direction d, go to Step 3. 
(2) If P; is a crossing point, judge that it is a true or pseudo 
crossing point (more is said about this in the following). If it is 
true, stop tracking; otherwise, judge the forward direction d, go 
to Step 3. 
(3) If P; is an endpoint or a side point of the sliding window, go 
to Step 5. 
Step 5: Count the number of the tracking points. If it is less 
than 3, stop tracking; otherwise, move the centre of the sliding 
window to the current point, and restart Step 1. 
In the above process, crossing points may be encountered due to 
intersections between different linear features, or due to noise. 
The former is called true crossing point while the latter is called 
pseudo crossing point. When a true crossing point is met, 
automatic line tracking stops for a moment, and the next point 
is input manually. After that, the line tracking continues as 
before. When a pseudo crossing point is met, an automatic 
judgment of forward direction is needed to across the pseudo 
crossing point. 
To handle the pseudo crossing point, a concentration degree 
X 7; is defined, which means the total number of black pixels 
within a limited region. Suppose that 5 is the point in the un- 
thinned binary image corresponding to the crossing point P. If 
the concentration degree around S is larger than a preset value, 
then P is treated as a true crossing point. Otherwise it is a 
pseudo one. For topographic maps with resolution of 300 dpi, 
102 
the 
to 
the 
Cro 
arc 
Sca 
ave 
res 
ne 
  
  
  
  
Fig 
Cor 
Cor