'ested algorithm meet 
' point by the interest 
as a corner point. 
lines is less than 30 
corner point and also 
straight line. 
>, and shadow cast by 
ach the corner points 
asses over the corner 
int is searched inside 
and distance d. The 
llowing two rules: 
starts from the end 
8 neighborhood. The 
rch follows primarily 
int is not found after 
the line, it moves one 
edure repeats until a 
(arch area. When the 
he corner point that is 
direction is selected 
CHING SCHEME 
hing utilizes straight 
A potential problem 
ace which may result 
easures are introduced 
only a limited number 
ves are allowed. The 
| approximations. 
ions do not match 
ict matching and nil 
ons have been widely 
nd the solution. To 
arch with respect to 
tions (cost and benefit 
ic tree search method 
d modified forward 
napping between two 
ons 
nitives and relational 
itives are used in this 
:n straight line and (3) 
ray have none, one or 
| straight line has no 
has one corner point, 
rner points. Each line 
ientation and Contrast. 
in pixels and degrees, 
r 1 depending on the 
orientation. Figure 1 
ves. 
relational description: 
between the centers of 
distance between two 
a 1996 
  
straight 
line 
gradient 
direction 
® — orientation 
contrast = 0 
  
  
  
se 
Figure 1: The attributes of straight line primitive. 
3. Angle: the angle between two straight lines. 
Figure 2 illustrates the binary relations and their attributes. All 
three relations are necessary for unambiguously describing the 
spatial relationship between line primitives. It must be noted 
that all attributes of the straight line primitives and of the binary 
relational tuples implemented are orientation-invariant 
quantities except for line primitive orientation. Obviously, the 
proposed procedure cannot be used for matching stereopairs 
with large rotations. However, the relational descriptions 
described above are valid for the aerial images where small 
rotation exists in two images. 
= 
  
  
   
   
  
  
angle 
central 
ul distance 
short 
distance 
| 6 
  
  
  
  
Figure 2: Three 2-D binary relations and their attributes. 
3.2 2-D Binary Relations from 2-D Tree Technique 
Each primitive is only allowed to have a small number of 
binary relations with its neighboring primitives. Since the 
density and distribution of line primitives varies over the image, 
the straight-forward approach of using a circle, centered around 
the midpoint, would not do a good job. Instead, the following 
approach is chosen. Its goal is to subdivide the image into 
rectangles such that every rectangular area has the same number 
of line primitives. 
Two-dimensional (2-D) tree approach is suitable to divide the 
image into a number of small rectangular planes that contain a 
certain number of primitives. The primitives contained in a 
rectangular plane have binary relations with the primitives in 
the neighboring rectangular planes. In this way, the number of 
binary relations can efficiently be manipulated. The subdivision 
of a 2-D image plane and its corresponding 2-D tree are 
represented in Figure 3. In Figure 3, the black dots represent the 
centers of line primitives and each subdivision is designed to 
have 4 or 5 line primitives in this example. 
In the interest of brevity, the implementation details of the 
approach are skipped. Each rectangular plane is called a bucket. 
In summary, the nodes at the lowest level of a 2-D tree are 
neighborhoods if one of following six conditions are fulfilled : 
1. Their parent nodes are the same. 
Their nodes are the same and their parent nodes are 
different. 
3. Their nodes are different and their parent nodes (Left 
and Right) are different, and grandparents are the same 
and their row bounds overlap. 
4. Their nodes are different and their parent nodes (Up and 
Down) are different, and grandparents are the same and 
their column bounds overlap. 
Their nodes are different. their grandparent nodes (Left 
and Right) are different, and their row bounds overlap. 
6. Their nodes are different, their grandparent nodes (Up 
and Down) are different, and their column bounds 
overlap. 
The conditions described above are valid for a binary tree with 
depth 3. If the depth of the binary tree gets deeper, the 
conditions can be easily expanded in an alternating manner. 
N 
Un 
  
  
  
[e e e | e e e e| 
e e | | 
ee e | e e * 
e e|e e e| 
e e e | 
; = e "s eo | 
© ZA 
(b) 
  
     
U DU DUO pu D 
A 1. A CB DE'GFr H 
(c) (d) 
Figure 3: A subdivision of 2-D image plane and corresponding 
2-D tree. 
3.3 Special Relation 
The half-open and closed line primitives have one and two 
corner points at the ends, respectively. These two line 
primitives may share the same corner points as their end points. 
In that case, the identical corner point is called node point. 
Now, the binary relations between two line primitives which 
share the same corner point at the end are called node relations 
in this study. Since the node relations are distinct from the other 
binary relations the node relations are particularly suited to be 
matched beforehand in order to determine approximations. 
Each node relation has three attributes: 
1. Angles between two line primitives (à, B). 
2. Orientation between two node points (®). 
3. Distance between two node points (d). 
Figure 4 illustrates the node relations and their attributes. 
Whereas the angles (cf) and distance (d) are orientation- 
invariant quantities, orientation (®) is orientation variant. 
Thus, the node relation cannot be used for matching a stereopair 
with a large kappa angle. 
All pairs of line primitives with node points are extracted and 
all combinations of node relations are created. Relational 
matching is performed by A* search with forward checking. 
For the matched node points, the mismatch detection process is 
113 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996