edge probability and the new edge angle uses the 
compatibility coefficients Ree, Ren, Rne, Rnn. 
These coefficients are used to determine the 
relationship between a pixel (i,j) and one of its 
neighbors at (u.v). For example, if an edge 
exists at (i,j) and an edge exists at (u,v), one 
must have a quantitative relationship which ex- 
plains how an edge at (u,v) will affect the edge 
at (i,j). In this example the relation is given 
by the compatibility coefficient Ree. If an edge 
exists at (i,j) and no edge exists at (u,v), the 
relation is given by the compatibility coeffici- 
ent Ren. Ree is known as the edge/edge coeffici- 
ent and depends upon the edge angles at the two 
points, on the angle between a line joining the 
point (i,j) with (u,v), and the x-axis, and on the 
distance between (i,j) and (u,v). Collinear edges 
will reinforce one another, while edges at dif- 
ferent angles will weaken one another. Similarly, 
edge points are weakened by points containing no 
edges that are collinear with them, and the no- 
edge points are strengthened by edges alongside 
them. The definitions of the compatibility co- 
efficients, the method of computing the edge 
probability, and the method of computing the new 
edge angle are the same as those given by 
Schachter, et al. (Schachter, et al., 1977). The 
details of the derivation of the relaxation 
equations are given in the paper by Schachter, 
et al. (Schachter, et al., 1977) and also in the 
report by Hevenor and Chen (Hevenor and Chen, 
1990). 
Thinning 
After several iterations of relaxation, the image 
is essentially binary. However, some of the 
strong edges are now too thick, and a thinning 
routine must be used in order to obtain linelike 
patterns. We assume that the image consists of 
only two gray values, represented by 0 and 1. A 
frame around the image consisting of the first 
row, the first column, the last row, and the last 
column will be assumed to contain only 0 pixels. 
Consider a pixel and its eight neighbors. If the 
center pixel has the value of 1, then a 1 in any 
of the 8 neighboring positions will be considered 
connected to the center pixel. This is known as 
8-connectivity. We will assume 8-connectivity 
exists for 1-pixels and 4-connectivity exists for 
O-pixels. A thinning routine was used which makes 
use of computing the eight connectivity number 
developed by Yokoi, Toriwaki, and Fukumura 
(Yokoi, et al., 1975) to analyze the topological 
properties of a binary image. The details of the 
thinning routine are presented in the report by 
Hevenor and Chen (Hevenor and Chen, 1990). 
Connected Components 
  
The purpose of the connected components routine is 
to provide a unique label for each component of 
l-pixels in the binary image that has been thinned 
Each label is a number that is assigned to every 
pixel in a given connected component. This label- 
ing operation can be performed by scanning the 
entire binary image with a 3 by 3 array and con- 
sidering the following pattern: 
C B E 
D A 
If we scan along the image from left to right and 
from top to bottom, and if pixel A is the pixel 
presently being considered and it has a value of 1, 
then a label must be assigned to A. If the pizels 
810 
at D, C, B and E are all 0, then A is given a new 
label. If pixels C, B and E are all O and D s 1, 
then A is given the label of D. Each possible con- 
struction of O's and 1's for the pixels D, C, B 
and E must be considered when providing a label 
for A. If two or more pixels in the set D, C, B 
and E are equal to 1 and they all have the same 
label, then A is also given the same label. The 
real difficulty comes when two or more of the 
pixels D, C, B and E have different labels. This 
can occur when two or more separate components, 
which were originally assigned different labels 
are found to be connected at or near pixel A. For 
these cases the pixel A is given the label of any 
one of the pixels D, C, B or E, which has a value 
of 1. An equivalence list consisting of pairs of 
equivalent labels is formed. After the binary 
image has been completely scanned, the equivalence 
list is restructured in such a way as to contain a 
number of lists. Each of these lists contains all 
of the equivalent labels associated with a parti- 
cular connected component. A new label is then 
given to each of the new lists and is assigned to 
each of the appropriate pixels. 
Region Property Calculations 
  
The purpose of region property calculation is to 
determine if the computation of certain quantities 
can be used to isolate the particular connected 
components that belong only to the airfield runway 
pattern. Computations are performed on each con- 
nected component. Eleven region properties were 
used in this research and are: 
1. Area 
2. Centroid 
3. Orientation of the axis of 
least inertia 
4. Maximum moment of inertia 
5. Minimum moment of inertia 
6. Elongation 
7. Measure of region spread 
8. Scatter matrix 
9. Eigenvalues of the scatter matrix 
10. Perimeter 
11. Compactness 
Border Following 
Border following determines and uniquely labels all 
l-pixels that exist between a given connected com- 
ponent of l-pixels and a connected component of 
O-pixels. A border point is defined as a l-pixel 
that has at least one O-pixel in its 4-neighbor- 
hood. A border point can also be described as a 
l-pixel located on the boundary between a connect- 
ed component of l-pixels and a connected component 
of O-pixels. The frame of a binary image consists 
of the first row, the last row, the first column 
and the last column. It will be assumed that all 
the pixels on the frame have a gray value of 0. 
There are two types of borders that can exist in 
binary images of interest, outer borders and hole 
borders. An outer border is defined as the set of 
l-pixels located between a connected component of