Image Processing Reference
In-Depth Information
1.3.3.1
Contour Tracing
The contour of a connected component is defined as the connected sequence
of border points, so that the starting point and end point are neighbors and
no point is revisited in the sequence. In this case, a contour is a simple closed
curve in the digital grid, as defined previously. Such a contour is called a simple
contour. However, a contour may not always be simple; there may be a border
point having more than two neighbors. Given a simple contour and an object
point on it, we discuss an algorithm [162] in an (8,4) digital grid to trace the
sequence. The task is also called contour following. Let p be a border point
and q be its neighbor. We take this pair (p,q) as the starting configuration
of the contour and move forward to obtain succeeding pairs in it. To get
the next border point in the contour, we perform a clock-wise search among
the 8-neighbors starting from q. In Fig. 1.8 (a), the sequence of points to be
searched is shown as r
0
(= q),r
1
,...,r
7
. Suppose that r
i
the next immediate
object point occurs at. In that case, r
i
becomes the next point in the sequence
and r
i−1
is the corresponding neighboring background point of r
i
. We would
repeat the same process with the pair of (r
i
,r
i−1
) and it continues till we
reach at p again. A typical example of a contour-trace is shown in Fig. 1.8
(b). In the figure, the path is shown by red arrows. The staring pair of points
is taken at (p
0
,q
0
) and it continues till we get p
9
= p
0
. It may be noted that
a background border point (q
3
= q
4
) occurs twice in the trace. The contour
may also be traced counter-clockwise if the order of search for a neighboring
border point (refer to Fig. 1.8(a)) is made counter-clockwise.
There could be multiple contours in a picture. In that case, we perform
contour tracing after obtaining each unflagged border point. Once a contour
is obtained, all the points in it are flagged. However, the above algorithm
fails for non-simple contours. Interested readers may refer to work reported in
[196, 171] for the details about techniques for tracing complex contours.
There are various applications of contour tracing. Contours can be further
approximated by simple polygons (with many fever vertices). Polygons are
useful in representing shapes and other information. Using the sequence of
points, it is possible to compute various geometric features such as normals,
curvatures, etc., at any point of the contour.
1.3.3.2
Chain Code
A contour or an arc in a 2-D digital grid can be encoded by a sequence
of discrete orientations. The neighboring points [86] may be considered con-
nected by line segments in a digital arc, which is on a fixed grid of possible
orientations. There are 8 or 4 different orientations depending on the neigh-
borhood definitions as shown in Figs. 1.9 (a) and 1.10 (a). Freeman [86] used
this directional information in encoding the sequence of points (paths and
contours). The respective code is called a chain code. Here, the starting point
is explicitly stored and the subsequent points of the curve are represented by
encoding successive displacements from the preceding points. Contour trac-
