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