nd 
onal 
tions 
rom 
ness 
ve is 
> the 
, the 
ality. 
oted 
dy if 
n the 
how: 
xels, 
it is 
necessary to generate chains of connected edge pixels. 
A chain of pixels along an edge will be called an 
edge streak. We define a corner as a discontinuity in the 
direction of an edge streak, which subdivides the edge 
streak into edge segments. Corner points of the edge 
streaks support the finding of correct matches. 
3.1 Generation of Edge Streaks 
Generation of edge streaks can be organized in the 
form of a minimum cost search (Shu, 1986). The general 
case of combining pixels to form edge streaks can be 
explained as follows (see Fig. 3.1): 
Pixel P is part of an edge streak. The combination of 
P with one of the neighbouring pixels po to p; which are 
not yet part of an edge streak is considered.Thus, the 
costs C of the combinations (P, po), (P, pj), ... (P, p7) 
have to be computed. The combination (P, Prin) Which 
results in the minimum cost C,,;, among the costs C(P, 
pi) is candidate for a link operation. If the cost C(P, Pmin) 
is less than a user-defined threshold Cy, the link (P, Pmin) 
is conducted. 
   
Fig. 3.1. Minimum-cost search for edge streak generation. 
The search operation is shown twice. 
As can be seen, two cost functions C and C are used 
in order to decide about a link (P, p;) . The cost C is 
determined by the difference in gradient direction, the 
difference in gradient magnitude, a non-edge pixel 
property and the divergence from straightness of the 
generated edge streak. The cost components resulting 
from the non-straightness of an edge streak is only 
considered for the finding of the minimum cost C,,;,, but 
not for the comparison with the threshold C;, as there are 
no objections against the generation of an edge streak that 
includes a corner point. 
3.2 Detection of Edge-Streak Corners 
Corner points are of special importance for the 
derivation of correct matches between edge segments 
from two images. Firstly, corner points are descriptive 
parameters which contribute to the distinctiveness of an 
edge feature. Thus, they improve the feature matching. 
Secondly, once a match of two segments has been 
established, corner points can serve the purpose of 
mutually fitting the two edge curves in order to get 
point-oriented information. 
The corners of the chain-coded edge streaks are 
detected according to the algorithm of Beus and Tiu 
(1987). It is based on an algorithm developed by 
Freeman and Davis (1977). 
4. Generation of an Edge Neighbourhood 
Graph 
In this approach the distribution of edges over an 
image and the relations between edges are controlling and 
309 
supporting the matching. 
The algorithm for edge neighbourhood detection is 
based on the philosophy that an edge segment "owns" all 
pixels of an image which are situated closer to it than to 
any other edge segment. The set of pixels owned by an 
edge segment constitutes an edge region. The Region 
Adjacency Graph RAG of the edge region image is the 
desired edge neighbourhood graph. 
The edge regions are found by growing layers of 
neighbouring pixels around the edge segments. At the 
beginning of the process all edge segment pixels are 
considered initial pixels of the edge regions. The set of 
four-neighbouring pixels of the edge-region pixels which 
is not yet integrated into the region, is the layer of pixels 
surrounding an edge region. The region growing process 
successively integrates layers into all regions. First, one 
layer is grown around each region. The pixels of a layer 
are only integrated into a region when they do not 
already belong to another region. This region would be 
considered being a next neighbour. After one layer is 
grown for all segments the sequence of regions is 
reversed. This makes up for the fact that regions which 
grow first, potentially grow faster than regions which 
grow later. Subsequently, further layers are grown, and 
the process is repeated until all image pixels belong to 
certain regions, or until a predefined maximum number 
of layers was handled. The latter provides the possibility 
not to include the whole image into processing, but to 
stop the layer growing when the distances between edge 
segments are too large for neighbourhood relations. 
The RAG is build according to the algorithm shown 
in pseudo-code in Fig. 4.1. It could also be regarded as a 
contour-based dilation algorithm for non-binary images. 
Fig. 4.2 shows the final state of a RAG generation. 
  
1. For all regions { 
If a pixel of another region is contained 
in the surrounding layer of the region ( 
Register that this region is adjacent to the 
processed region. 
) 
Grow the region such that the surrounding layer is 
integrated into the region according to the rule 
described above. 
If all image pixels that are to be evaluated 
are members of an edge region, exit. 
3. Invert the order of the regions and execute step 1. again. 
  
  
  
Fig 4.1. Algorithm for the generation of a Region Adjacency 
Graph. 
4.2 Establishing Edge Parameters 
Matches of edge segment pairs are established by 
comparing parameters which describe the edge segments. 
All of these edge parameters are contained in the 
brightness function at and in the vicinity of an edge 
segment. Scanning the vicinity of an edge segment, the 
search for next neighbours can be used in order to 
extract descriptive and relational edge parameters from 
the brightness function. 
Descriptive parameters describe the properties of an 
edge segment and, hence, make them distinctive from 
other segments. The descriptive parameters are derived 
by an analysis of edge-support regions. The problem of 
which edge pixel belongs to the edge support region and