344 A Computational Introduction to Digital Image Processing, Second Edition
Python
def disttrans(image,mask):
backmask = np.rot90(np.rot90(mask))
mr,mc = mask.shape
if mr%2 == 0 or mc%2 == 0:
raise ValueError("Error:
Mask must have odd numbers of rows and
columns")
r,c = image.shape
nr = (mr-1)/2
nc = (mc-1)/2
image2 = np.float64(np.pad(image,[nr,nc],mode=’edge’))
image2[np.where(image2==0)]=float(’inf’)
image2[np.where(image2==1)]=0
for i in range(r):
for j in range(c):
image2[i+nr,j+nc] = (image2[i:i+mr,j:j+mc]+mask).
min()
for i in range(r)[::-1]:
for j in range(c)[::-1]:
image2[i+nr,j+nc] = (image2[i:i+mr,j:j+mc]+backmask).min()
return image2[nr:nr+r,nc:nc+c]
A program for Zhang-Suen skeletonization:
Python
from numpy import array
_
equal,copy,reshape
from scipy.ndimage import generic
_
filter as gfilt
from skimage.measure import label as bwlabel
def zs(im):
prev = copy(im)
curr = prev
*
(1-gfilt(prev,zs
_
fun,size=(3,3),extra
_
arguments=(1,)))
while True:
curr = curr
*
(1-gfilt(curr,zs
_
fun,size=(3,3),extra
_
arguments=(0,)))
curr = curr
*
(1-gfilt(curr,zs
_
fun,size=(3,3),extra
_
arguments=(1,)))
if array
_
equal(prev,curr):
break
else:
prev = copy(curr)
return curr
def zs
_
fun(x,parity):
n = np.reshape(x,[3,3])
n[1,1] = 0
B = n.sum()
X = bwlabel(n,background=0).max()+1
out = (B>=2) and (B<=6) and (X==1)
if parity==0:
out = out & (x[1]==0 or x[3]==0 or (x[5]==0 and x[7]==0))
elif parity==1:
out = out & (x[5]==0 or x[7] ==0 or (x[1]==0 and x[3]==0))
return out
And a program for Guo-Hall skeletonization:
Image Topology 345
Python
from numpy import reshape,zeros,copy,array
_
equal,array,tile
from scipy.ndimage import generic
_
filter as gfilt
from
skimage.measure
import label as bwlabel
def gh(im):
r,c = im.shape
im2 = tile(array([[1,2],[2,1]]),[r/2,c/2])
*
im
prev = copy(im2)
curr = prev
*
(1-gfilt(prev,gh
_
fun,size=(3,3),extra
_
arguments=(1,)))
while True:
curr = curr
*
(1-gfilt(curr,gh
_
fun,size=(3,3),extra
_
arguments=(2,)))
curr = curr
*
(1-gfilt(curr,gh
_
fun,size=(3,3),extra
_
arguments=(1,)))
if array
_
equal(prev,curr):
break
else:
prev = copy(curr)
return curr
def gh
_
fun(x,parity):
n = (reshape(x,[3,3])>0)
*
1
n[1,1] = 0
B = n.sum()
X = bwlabel(n,8,background=0).max()+1
return ((B>=2) and (X==1) and (x[1]
*
x[3]
*
x[5]
*
x[7]==0) and (x[4]==
parity))
Exercises
1. What are the coordinates of the 4-neighbors of the pixel (i, j)? What are the coordi-
nates of its 8-neighbors?
2. Find the length of the shortest 4-path from
(a) pixel (1, 1) to pixel (5, 4)
(b) pixel ( 3, 1) to pixel (1, 6)
(c) pixel ( i, j) to pixel (l, m)
For this question, if a path between pixels p and q consists of p = p
0
, p
1
, p
2
, . . . , p
n
= q
where all of the pixels in the path are different, then the length of that path is defined
to be n − 1.
3. Find the shortest 8-paths between each pair of pixels in the preceding question.
346 A Computational Introduction to Digital Image Processing, Second Edition
4. Consider the two images
• • · · · • • • • ·
• • · · · • • • • ·
· • • · · • • • • ·
• • · · · • • • • ·
• • · · · • • • • ·
· · • • • · · · · •
· · • • • · · · · •
• · · • • · · · · •
· · • • • · · · · •
· · • • • · · · · •
A
,
• • · · · • • · · ·
• • · · · • · · • ·
· • • · · · · • • ·
• • · · · · • • • ·
• • · · · • • • · ·
· · • • • · · · · •
· · • • • · · · · •
• · · • • · · · · •
· · • • • · · · · ·
· · • • • · · · · ·
B
Find the 4-components and 8-components of each image.
5. The above matrices were obtained with the MATLAB/Octave commands
MATLAB/Octave
>> A=magic(10)>50
>> B=magic(10)>60
If you use Python you will have to enter the matrices manually. Check your an-
swers of th e previous question with the
bwlabel function of MATLAB/Octave or
sk.measure.label in Python.
6. We can define the 6-neighbors of a pixel p with coordinates (x, y) to be the pixels with
coordinates (x + 1, y), (x −1, y), (x, y + 1), (x, y −1), (x + 1, y + 1), and (x −1, y −1).
Draw a diagram showing the six 6-neighbors of a pixel.
7. Prove the triangle inequality for the Euclidean distance metric, and for the 4-path
and 8-path metrics d
4
and d
8
.
8. Define the relation 6-connectedness as:
p is 6-connected to q if there is a path p = p
1
, p
2
, . . . , p
n
= q such that for
each i = 1, 2, . . . , n − 1, p
i
is 6-adj acent to p
i+1
.
Show that this is an equivalence relation.
9. Find the lengths of the shortest 6-paths between pixels with the following co ordinates:
(a) (0, 0) and (2, 2), (b) (1, 2) and (5, 4), (c) (2, 1) and (6, 8),
(d) (3, 1) and (7, 4)
Can you develop an expression for a 6-path metric?
10. Show how to refine the algorithms for component labeling to label the 6-comp onents
of a binary image.
Image Topology 347
11. For the following image:
· · · · · · · ·
· · · · • • • ·
· · · · • • • ·
· · • • · • • ·
· · • • · · · ·
· · • • • • · ·
· · • • • • · ·
· · • • • · · ·
· · • • • · · ·
· · • • • · · ·
· • • • • · • ·
· · · · · · · ·
use your algorithm developed in the previous question to label the 6-components.
12. Use
bwlabel or sk.measure.label to determine the number of blobs in the example
given at the beginning of this chapter. Is there any difference between the results
using 4 and 8 adjacency? Can you account for your answer?
13. Obtain the 6-components of the images A and B given in Question 4.
14. Let C be the image:
· · · · · · · · · · ·
· · · · • • • · · · ·
· · • • • • • • • · ·
· · • • • • • • • · ·
· • • • • • • • • • ·
· • • • • • • • • • ·
· • • • • • • • • • ·
· · • • • • • • • · ·
· · • • • • • • • · ·
· · · · • • • · · · ·
· · · · · · · · · · ·
Obtain the 4-boundary and 8-boundary of this image.
15. The image in the previous question was obtained with the MATLAB commands:
MATLAB/Octave
>> [x,y] = meshgrid(-5:5,-5:5);
>> C = (x.^2+y.^2)<20
or with the Python commands
Python
In : x,y = np.mgrid[-5:6,-5:6]
In : C = ((x
**
2+y
**
2)<20)
*
1
Check your answers to Question 14 with the bwperim or the sk.measure.perimeter
function.
348 A Computational Introduction to Digital Image Processing, Second Edition
16. Determine if each of the following foreground pixels is (a) 4-simple, (b) 8-simple.
• • •
• p ·
• • ·
• · ·
• p •
· • ·
· • ·
• p •
· · •
· • •
· p •
• • ·
· • •
· p ·
• • ·
· · •
• p ·
• · •
17. Calculate C
S
(p) for each configuration in the previous question, and show that the
result is equal to C(p) in each case.
18. Find configurations of pixels surrounding p for which
(a) C(p) = A( p) − 2
(b) C(p) = A(p) − 3
(c) C(p) = A(p) − 4
19. Show that C(p) ≤ A(p) for every configuration of pixels.
20. Skeletonize each of the following images using (a) the Zhang-Suen algorithm, and (b)
the Guo-Hall algorithm:
• • • • • • •
• • • • • • •
• • • • • • •
• • • · • • •
• • • • • • •
• • • • • • •
• • • • • • •
· · · • · · ·
· · • • • · ·
· • • • • • ·
• • • • • • •
· • • • • • ·
· · • • • · ·
· · · • · · ·
· • • • • • ·
• • • · • • •
• • • · • • •
• · · · · · •
• • • · • • •
• • • · • • •
· • • • • • ·
21. Consider the cross-shaped obj ect formed by starting with an 11 × 11 square and
removing a 3 × 3 square from each corner. Skeletonize it by each of the algorithms.
22. Check your answers to the previous two questions with your computer system.
23. Which of the algorithms seems to be the fastest, in requiring the least number of
iterations, or removing the greatest number of pixels at each step?
24. Sketch the medial axes of: (a) a 2 × 1 rectangle, and (b) a triangle.
25. Apply both algorithms to the image
circles2.png.
(a) Which one works faster?
(b) Which gives the best looking results?
26. Repeat the previous question on some other binary images.
27. For each of the following images:
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 1 1 1 0 0 0
0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1
0 1 1 1 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 1 1 1 1 0 0
0 1 1 1 1 1 1 0
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.