Shapes and Boundaries 361
FIGURE 12.6: A simple L-shape
The normalized version of these differences is the shape number for this L shape and can
be found to be
0 1 0 1 1 3 1 1.
The chain code for the rotated L can be found to be
3 2 3 0 0 1 1 2.
Even when normalized the result is not the same as the chain code for this shape in its
original orientation. But if the differences are obtained:
3 2 3 0 0 1 1 2
− 2 3 2 3 0 0 1 1
1 3 1 1 0 1 0 1
then the normalized third row is
0 1 0 1 1 3 1 1.
which is exactly the same code obtained above.
This can be done easily in MATLAB or Octave: given a chain code
c, simply normalize
the difference with a cyclic shift:
MATLAB/Octave
>> c = shape(a)
c =
3 3 0 0 1 1 2 2
>> d = mod(c - circshift(c’,1)’,4)
d =
1 0 0 0 1 0 1 0
>> chain
_
norm(d)
ans =
0 0 0 1 0 1 0 1
Let’s try this with our L shape and its rotation.
362 A Computational Introduction to Digital Image Processing, Second Edition
MATLAB/Octave
>> c = shape(L,4);
>> d = mod(c - circshift(c’,1)’,4);
>> chain
_
norm(d)
ans =
0 0 0 1 0 0 1 1 0 3 0 0 1 1
>> c2 = shape(L2,4);
>> d2 = mod(c2 - circshift(c2’,1)’,4);
>> chain
_
norm(d2)
ans =
0 0 0 1 0 0 1 1 0 3 0 0 1 1
and both results are exactly the same. With Python, the following commands obtain the
same outcome:
Python
In : c = shape(a,4)
In : d = (c-np.roll(c,1))%4
In : print(d)
[1 0 1 0 1 0 1 0]
In :
12.3 Fourier Descriptors
The idea is this: suppose we walk around an object, but instead of writing down the
directions, we write down the boundary coordinates. The final list of (x, y) coordinates can
be turned into a list of complex numbers z = x + yi. The Fourier transform of this list of
numbers is a Fourier descriptor of the object.
The beauty of a Fourier descriptor is that often only a few low frequency terms around
the DC coefficient are enough to distinguish objects, or to classify them.
The chain code functions at the end of the chapter also produce the list of boundary
pixels, so that, for example, with the L shape from the previous section:
MATLAB/Octave
>> [cc,bdy] = shape(L);
>> bdy’
ans =
3 4 5 6 6 6 6 5 5 5 4 3 2 2
2 2 2 2 3 4 5 5 4 3 3 3 3 2
Turning these into complex numbers is easy:
Shapes and Boundaries 363
MATLAB/Octave
>> c = complex(bdy(:,1),bdy(:,2)); c’
ans =
Columns 1 through 8:
3 - 2i 4 - 2i 5 - 2i 6 - 2i 6 - 3i 6 - 4i 6 - 5i 5 - 5i
Columns 9 through 14:
5 - 4i 5 - 3i 4 - 3i 3 - 3i 2 - 3i 2 - 2i
The same array can be obtained with Python:
Python
In : cc,bdy = shape(L)
In : c = bdy[:,0] + bdy[:,1]
*
1j
These can be plotted:
MATLAB/Octave
>> plot(c,’.-’,"markersize",10),axis([1,7,1,6]),axis equal
or with
Python
In : import matplotlib.pyplot as plt
In : plt.plot(c.real,c.imag,’.-b’,markersize=10)
In : plt.axis([0,6,0,5])
In : plt.show()
and the result is shown in Figure 12.7. Supposing we take the Fourier transform, and from
it extract only a few terms:
MATLAB/Octave
>> cf = fft(c)
cf =
62.00000 + 43.00000i
-9.76237 - 18.27796i
-5.69003 - 0.64111i
2.87152 - 2.43834i
0.52068 + 0.82866i
1.45451 - 0.95368i
-0.16670 + 0.47640i
0.00000 + 1.00000i
-0.47640 + 0.16670i
0.75862 + 0.27672i
-0.82866 - 0.52068i
-0.64200 - 0.93602i
0.64111 + 5.69003i
-8.68028 + 0.32927i
364 A Computational Introduction to Digital Image Processing, Second Edition
FIGURE 12.7: Boundary pixels
Note that as this transform is not shifted, the first term will be the DC coefficient, and low
frequency terms occur after the DC coefficient, and at the end. What we can do is pick a
value k, and keep k terms after the DC coefficient, and at the end:
MATLAB/Octave
>> k = 2
>> cf2 = cf;
>> N = len(cf);
>> cf2(k+2:N-k) = 0;
At this stage, 9 of the original 14 values have been removed. They can be plotted with lines
and points, and to ensure the lines meet up the first values will b e repeated as the last:
MATLAB/Octave
>> bdy2 = ifft(cf2);
>> bdy2 = [bdy2;bdy2(1,:)];
>> plot(bdy2,’.-’,"markersize",10),axis([1,7,1,6]),axis equal
The result is shown in Figure 12.8(a).
Images (b) and (c) show the result by keeping a few more pairs of transform values.
However even with k = 2 there is enough information to gauge the size and rough shape of
the object; and with k = 4 (five transf orm values removed) the result is very close.
Recall that in an unshifted transform, the DC coefficient is at the start, and the high
frequency values are toward the middle, as shown in Figure 12.9.
In this figure, the arrows give the direction of increasing frequency; the elements labeled
X and Y are those of highest frequency. Around those central values, and excluding the
DC coefficient, all other elements can be paired together with equal frequencies, as shown.
Shapes and Boundaries 365
(a) k = 2 (b) k = 3 (c) k = 4
FIGURE 12.8: Fourier descriptors of an L shape
DC X
0 1
n − 2
n
n + 1 n + 2 2n − 2 2n − 1
Number of elements is even, 2n
DC X Y
0 1
n − 2
n
n + 1 n + 2 2n − 1
2n
Number of elements is odd, 2n + 1
FIGURE 12.9: Unshifted one-dimensional DFT
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.