Object description - Feature Extraction and Image Processing - page 249

A boundary and a region can be defined using both types of connectivity and they are
always complementary . That is, if the boundary pixels are connected in 4-way, then the
region pixels will be connected in 8-way and vice versa. This relationship can be seen in
the example shown in Figure 7.2 . In the example in this figure, the boundary is shown in
dark grey and the region in light grey. We can observe that for a diagonal boundary, the 4-
way connectivity gives a staircase boundary whereas 8-way connectivity gives a diagonal
line formed from the points at the corners of the neighbourhood. Notice that all the pixels
that form the region in Figure 7.2 (b) have 8-way connectivity, whilst the pixels in Figure
7.2 (c) have 4-way connectivity. This is complementary to the pixels in the border.

(a) Original region (b) Boundary and region for

4-way connectivity

(c) Boundary and region for
8-way connectivity

Figure 7.2 Boundaries and regions

7.2.2 Chain codes

In order to obtain a representation of a contour, we can simply store the co-ordinates of a
sequence of pixels in the image. Alternatively, we can just store the relative position
between consecutive pixels. This is the basic idea behind chain codes. Chain codes are
actually one of the oldest techniques in computer vision originally introduced in the 1960s
(Freeman, 1961) (an excellent review came later (Freeman, 1974). Essentially, the set of
pixels in the border of a shape is translated into a set of connections between them. Given
a complete border, one that is a set of connected points, then starting from one pixel we
need to be able to determine the direction in which the next pixel is to be found. Namely,
the next pixel is one of the adjacent points in one of the major compass directions. Thus,
the chain code is formed by concatenating the number that designates the direction of the
next pixel. That is, given a pixel, the successive direction from one pixel to the next pixel
becomes an element in the final code. This is repeated for each point until the start point
is reached when the (closed) shape is completely analysed.
Directions in 4-way and 8-way connectivity can be assigned as shown in Figure 7.3 . The
chain codes for the example region in Figure 7.2 (a) are shown in Figure 7.4 . Figure 7.4 (a)
shows the chain code for the 4-way connectivity. In this case, we have that the direction
from the start point to the next is south (i.e. code 2), so the first element of the chain code