356 A Computational Introduction to Digital Image Processing, Second Edition
2. Traverse the 3 × 3 neighborhood of the current pixel in an anticlockwise direction,
beginning the search at the pixel in direction
dir + 7 (mod 8) if dir is even
dir + 6 (mod 8) if
dir is odd
This simp ly sets the current direction to the first direction anticlockwise from
dir
:
dir 0 1 2 3 4 5 6 7
dir + 7 (mod 8) 7 0 1 2 3 4 5 6
dir + 6 (mod 8) 6 7 0 1 2 3 4 5
The first foreground pixel will be the new boundary element. Update
dir.
3. Stop when the current boundary element P
n
is equal to the second element P
1
and
the previous boundary pixel P
n−1
is equal to the first boundary element P
0
.
Note that the choosing of the starting direction in Step 2 can be implemented by
MATLAB/Octave
newdir = mod(dir+7-mod(dir,2),8);
or
Python
newdir = (dir+7-dir%2)%8
which produces dir + 7 if dir is even, and dir + 6 if dir is odd. As well as this, we need
to take into account all possible directions from a pixel; the index increments are:
−1 −1 −1 0 −1 1
0 −1 0 0 0 1
1 −1 1 0 1 1
These will all be placed in the array
n =
0 1
−1 1
−1 0
−1 −1
0 −1
1 −1
1 0
1 1
where as before, direction 0 corresponds to the top row of n. This can be tested on the test
image
test:
Shapes and Boundaries 357
MATLAB/Octave
>> uint8(shape(test,8))
ans =
6 6 5 6 6 0 0 0 1 2 2 2 3 4 4
and the answer is indeed the code obtained earlier by following the arrows around the object.
Programs are given at the end of the chapter.
Normalization of Chain Codes
There are two problems with the definition of the chain code as given in previous sections:
1. The chain code is dependent on the starting pixel
2. The chain code is dependent on the orientation of the object
First look at Problem (1). The idea is to “normalize” the chain code as follows: imaging
the code to be written around the edge of a circle. We choose as our starting place the
position for which the code, when read off, will be the lowest possible integer. The result is
the normalized chain code for our object.
For example, supp ose we have an object consisting of a 3 × 3 square:
MATLAB/Octave
>> a=zeros(5,5);a(2:4,2:4)=1
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
>> shape(a,4)
ans =
3 3 0 0 1 1 2 2
Now let’s put these codes around a circle as shown in Figure 12.5.
The arrow indicates where we should start reading off the code to obtain the lowest
integer; in this case it is
0 0 1 1 2 2 3 3
But we can do this easily in MATLAB or Octave by using the circshift function to create
every possible shift. For our chain code above, we can do this:
358 A Computational Introduction to Digital Image Processing, Second Edition
0
3
3
2
2
1
1
0
FIGURE 12.5: A chain code written cyclically
MATLAB/Octave
>> N = length(c);
>> z = zeros(N);
>> for i = 1:N, z(i,:) = circshift(c’,i)’;end
>> z
ans =
2 3 3 0 0 1 1 2
2 2 3 3 0 0 1 1
1 2 2 3 3 0 0 1
1 1 2 2 3 3 0 0
0 1 1 2 2 3 3 0
0 0 1 1 2 2 3 3
3 0 0 1 1 2 2 3
3 3 0 0 1 1 2 2
To find the row that contains the least integer, we use the handy sortrows function, which
sorts the rows “lexicographically”: first on the first element, then on the second element,
and so on:
MATLAB/Octave
>> zs = sortrows(z)
zs =
0 0 1 1 2 2 3 3
0 1 1 2 2 3 3 0
1 1 2 2 3 3 0 0
1 2 2 3 3 0 0 1
2 2 3 3 0 0 1 1
2 3 3 0 0 1 1 2
3 0 0 1 1 2 2 3
3 3 0 0 1 1 2 2
Now the normalized chain code is just the first row:
Shapes and Boundaries 359
MATLAB/Octave
>> zs(1,:)
ans
=
0 0 1 1 2 2 3 3
In Python this can also easily be done; first create the test object and obtain its chain code:
Python
In : a = zeros((5,5))
In : a[1:4,1:4]=1
In : c = shape(a,4)
Now create an array whose rows contain the cyclic shifts; these can be obtained using the
roll method of numpy:
Python
In : N = len(c)
In : z = zeros((N,N))
In : for i in range(N):
...: z[i,:] = np.roll(c,i)
...:
The array z can now be sorted in place along whichever axis we choose. For sorting the
rows, the axis number is 1:
Python
In : z.sort(axis=1)
In : print(z[0,:])
[ 0. 0. 1. 1. 2. 2. 3. 3.]
Let’s try this with a slightly larger example: the test object from Figure 12.2:
MATLAB/Octave
>> c = shape(test,4);
>> N = length(c);
>> z = zeros(N)
>> for i = 1:N, z(i,:) = circshift(c’,i)’;end
>> zs = sortrows(z);
>> zs(1,:)
ans =
0 0 0 1 0 1 1 1 2 1 2 2 3 3 3 2 3 3
This can be easily turned into a function. With Python we just repeat the commands above,
starting with the new chain code array.
Shape Numbers
We now consider the second problem from above: defining a chain code that is indepen-
dent of orientation of the object. For example, consider a simple “L” shape:
360 A Computational Introduction to Digital Image Processing, Second Edition
MATLAB/Octave
>> L = zeros(7,6); L(2:6,2:3) = 1; L(5:6,4:5) = 1
L =
0 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0
0 1 1 1 1 0
0 1 1 1 1 0
0 0 0 0 0 0
The normalized chain code can be found by the commands above to be
0 0 0 1 2 2 1 1 1 2 3 3 3 3
Now suppose we rotate the shape so that it has a different orientation (we use the rot90
function which rotates a matrix by 90 degrees):
MATLAB/Octave
>> L2 = rot90(L)
L2 =
0 0 0 0 0 0 0
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
The normalized chain code for this new orientation can b e computed to be:
0 0 0 0 1 1 1 2 3 3 2 2 2 3
Even when normalized, the chain codes are different.
To overcome this, take the differences of the chain code: for each two consecutive
elements c
i
and c
i+1
, their difference is defined as
c
i+1
− c
i
(mod 4).
(If we were dealing with 8-connected boundaries, then we would take differences mod 8).
For an example, take the simple L shape and its rotation shown in Figure 12.6. The chain
code for the first shape can be read off easily starting from the point shown; it is
3 3 0 0 1 2 1 2.
To apply differences, subtract this list from a cyclic shift of itself:
3 3 0 0 1 2 1 2
− 2 3 3 0 0 1 2 1
= 1 0 1 0 1 1 3 1 (mod4)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.