mined through the least squares solution. Therefore, 
either the affine transformation describing the rela- 
tionship between template and image patch has to be 
substituted by a simpler three-parameter one 
X; = AX+ (Xxcosg — ysin) (16) 
y; = Ay+ (xsing —- ycose) (17) 
or, equivalently, three shape constraints should be in- 
troduced in the solution to effectively reduce the num- 
ber of affine transformation parameters. These three 
constraints are formulated as 
2 2 
a2 = Dy 8 =-by, a +by=1 (18) 
and are subsequently linearized and introduced to 
the adjustment solution as weighted constraints 
-0; 7 B,Xtk : Pa (19) 
In addition, since the edges to be measured are es- 
sentially uni-directional, a linear template edge would 
perpetually slide along the edge during matching. 
This effect is compensated by restricting the shift 
vector of the patch approximately prependicular to 
the local edge direction as 
Axsin® + Aycos6 = 0 (20) 
where 0 is the angle formed between the edge nor- 
mal and the y direction [Gruen & Stallmann, 1993]. In 
matrix form, this condition is expressed as a weighted 
constraint 
gy Box + 5s P, (21) 
The least squares solution for the joint system of 
equations (14), (19), and (21) is obtained as 
s ss 
. T T T =] 
X x (A PA*B,P,B,* B PB.) 
T T T 
.(A PI- B, Pt, -B.P.) (22) 
Iterations are obviously required due to the non-lin- 
earity of the mathematical model. From the final up- 
dated transformation parameters, an edge point is 
precisely located in the image as the conjugate of the 
prespecified edge position in the template. 
This edge measurement procedure has been ex- 
tended into an edge tracking technique, which auto- 
matically extracts the complete edge. The user gives 
an approximate position for the first edge point, the 
matching algorithm then precisely locates this point 
and subsequently tracks the edge (Fig. 4). The new 
approximate match point for the next patch is deter- 
mined using the previous matched position, its local 
edge direction and a user-defined incremental dis- 
tance (in pixels). Edge tracking stops either after the 
measurement of a prespecified number of edge 
points or if matching actually fails because the tem- 
plate can no longer find a conjugate window in the im- 
age (e.g. the end of an edge or a corner is reached). 
  
Fig. 4: Edge tracking 
Patch sizes typically range between 5x5 and 9x9 pix- 
els. Choice of a smaller patch size results in greater 
sensitivity to noise, while larger patch sizes increase 
the probability of interferences by other features 
close to the current edge. 
The significant advantage of the described method 
lies on the fact that it offers very high positioning ac- 
curacies. In addition, its familiar and well established 
mathematical formulation allows statistical analysis 
of the results and realistic evaluation of its perfor- 
mance. At the same time though, it is a localized pro- 
cess and as such it is very sensitive to noise and fails 
in the presence of edge gaps and outline break 
points. 
6. GLOBALLY ENFORCED LEAST SQUARES 
TEMPLATE MATCHING 
The limitations of least squares template matching, 
due to the use of highly localized radiometric informa- 
tion, can be overcome by its extention into a globally 
enforced least squares template matching strategy 
(Fig. 5). 
An operator initially selects the class to which the ob- 
ject to be extracted belongs (e.g. house, road, land 
parcel etc.) from an available object class menu and 
provides manually on-screen approximations of ob- 
ject outline breakpoints, which in essence define a 
150 
| | 
Man 
  
11 
  
Globally E 
Fig. 5: G 
polygonic & 
terpolating 
nodes at u 
are extract 
interest. Th 
tions for tl 
through lea 
thetic matc 
as the 2-D 
extracted [ 
tion at the i 
tion, howev 
for the var 
the mathen 
tended to pi 
lution, whe 
candidates 
More speci 
by least sq 
object outli 
condition, c 
try. For exai 
formed by 
Smooth spli 
metric relat 
matching a 
Assuming « 
ing the not: 
that edge 
the conditic