as a function of the distance travelled around the curve [16]. 
It indicates abrupt changes of direction as breakpoints in the 
curve. These breakpoints are indicated as local maxima in the 
first-derivative of the ¢(s) function, representing the corners 
of the feature outline. 
Using the feature descriptor function, features are classified 
according to their size, type and number of corners. 
The size of a feature is the length of the feature outline in 
pixels. 
The feature type broadly classifies a feature into three basic 
types, namely ARCS, CIRCLES and POLYGONS. An ARC is 
a linked edge chain that has two nodes at spatially separated 
endpoints, i.e. an open line feature. A POLYGON is a closed 
line feature where the start and end nodes are at the same 
point. A CIRCLE is defined as a polygon that has zero corners 
and with the ratio between the mean and standard deviation 
of the d@(s) plot below a certain level. Ideally, the d¢(s) plot 
for a circle should be a horizontal line, but due to the discrete 
nature of the input data there is some variation around the 
: mean value, which is quantified by the standard deviation. 
The number of corners of a feature is calculated from the local 
maxima of the d¢(s) plot. Prominent local maxima of the 
dó(s) plot indicate a prominent corner, and statistically-based 
thresholds are calculated to ensure that only these corners are 
detected. 
The reader is referred to figure 1 for a plot of the LEFT and 
RIGHT image features after feature extraction and classifica- 
tion. The image features are obtained from a stereo pair of 
printed circuit board (PCB) images. 
The features have been classified and the results of the clas- 
sification can be found in table 1. For ease of comparison 
the Feature Classification Table has been arranged so that 
matching LEFT and RIGHT images features appear next to 
each other with corresponding numbers for ease of interpre- 
tation. Throughout this paper examples using LEFT features 
labelled L.. and RIGHT features labelled R.. will refer to the 
features as labelled in figure 1. 
Note that only polygons (P) and circles (C) have been used 
in this example. Arcs were very seldomly repeated in the 
right image and were thus not used in the feature matching 
scheme. 
4 FEATURE MATCHING 
The results of the feature classification stage are used to find 
suitable matching feature candidates during a candidate se- 
lection phase. These matching candidates are then matched 
using a novel two-stage matching process. In the first step 
an ordered "feature correspondence table" is generated. This 
table orders the matching probabilities between reference fea- 
tures and the matching candidates by calculating the nor- 
malized crosscorrelations between the feature signature func- 
tions. In this case the d@(s) function was used as feature 
signature function, but any suitable signature function could 
be applied. During the second step the resultant matching 
probabilities are used in conjunction with the feature topology 
to verify feature matches. The feature topology is utilized by 
forming triangles between the centre-of-mass points of the 
reference feature and the centre-of-mass points of its nearest 
neighbours in the left (L) image. The matching probabilities 
obtained from the first matching step indicate the features 
704 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
  
  
L | Type | Size | Corn R | Type | Size | Corn 
L6 IP 50 3 R6 | P 48 4 
Ig | P 237 4 R8|P 221 4 
L10 | P 104 4 RIO | P 102 4 
L14 | P 69 3 R14 | P 69 4 
Lio | P 283 5 R19 | P 268 6 
{21 | P 71 3 R21 | P 73 3 
125 | P 94 4 R25 | P 87 4 
L29 | P 160 4 R29 | P 157 4 
L32 | P 74 3 R32 | P 71 3 
E33 |. P 288 4 R33 | P 273 4 
L40 | P 113 4 R40 | P 115 4 
L46 | P 311 4 R46 | P 303 4 
{57 { P 116 4 R57.|P 105 4 
L58 | C 60 0 R58 | € 61 0 
E62. |.€ 61 0 R62 | C 56 0 
L64 | C 53 0 R64 | C 51 0 
L65 | € 56 0 R65 | P 67 3 
L67 | P 56 4 R67 |.P 50 2 
  
  
  
  
  
  
  
  
  
  
  
Table 1: Feature Classification Table for matching LEFT and 
RIGHT image features 
of which the centroids could form the matching triangle in 
the candidate image. The existence of a matching triangle 
verifies the feature match. 
In the following the details of the candidate selection and 
subsequent two-stage feature matching is described in more 
detail. 
4.1 Candidate Selection Phase 
To distinguish the feature candidates that are suitable for 
matching to a specific reference feature the feature attributes 
of size, type and number of corners are compared. 
A matching candidate has to fulfil the following criteria: 
e The feature sizes should differ by no more than ten 
percent 
e The number of corners should differ by no more than 
one 
e The feature types should be the same 
Candidates that do not fulfil all of these criteria are immedi- 
ately eliminated from the matching scheme. Successful can- 
didates now go through the following, two-step procedure: 
4.2 Matching d¢(s) Signatures Through Correlation 
In the field of signal processing a measure that gives an in- 
dication of the similarity between two random signals is the 
Correlation function [14] [18]. The d¢(s) plots from differ- 
ent images should be similar for the same feature, and the 
correlation function can be used to quantify this similarity. 
The dó(s) plot is a one-dimensional function representing 
the two-dimensional shape of the feature, and the "time" 
variable used in this case is "s", the distance travelled along 
the feature boundary. 
The time-domain correlation function for two discrete func- 
tions g[n] and h[n] of length N is defined as: 
N—1 
Bynfn] = 5 7 g[n 4 m]h[m] (1) 
m=0 
       
    
    
   
   
  
  
   
    
   
   
   
  
   
   
  
  
   
  
   
  
  
  
   
  
   
  
  
   
  
  
  
  
   
  
  
  
  
   
  
   
  
  
  
    
   
    
wher 
Figur 
and f 
Figur 
imag 
toget 
throu 
funct 
value 
two |‘ 
95.3 
featu 
accor 
The | 
but t 
to th 
and r 
to th 
correl 
other