Digital Image Processing Second Edition
Problem SolutionswStudent Set
Rafael C. Gonzalez Richard E. Woods
Prentice Hall Upper Saddle River, NJ 07458 www.prenhall.com/gonzalezwoods or www.imageprocessingbook.com
ii
Revision history 10 9 8 7 6 5 4 3 2 1
c Copyright °1992-2002 by Rafael C. Gonzalez and Richard E. Woods
1
Preface
This abbreviated manual contains detailed solutions to all problems marked with a star in Digital Image Processing, 2nd Edition. These solutions can also be downloaded from the book web site (www.imageprocessingbook.com).
2
Solutions (Students)
Problem 2.1 The diameter, x, of the retinal image corresponding to the dot is obtained from similar triangles, as shown in Fig. P2.1. That is, (d=2) (x=2) = 0:2 0:014 which gives x = 0:07d. From the discussion in Section 2.1.1, and taking some liberties of interpretation, we can think of the fovea as a square sensor array having on the order of 337,000 elements, which translates into an array of size 580 £ 580 elements. Assuming equal spacing between elements, this gives 580 elements and 579 spaces on a line 1.5 mm long. The size of each element and each space is then s = [(1:5mm)=1; 159] = 1:3 £ 10¡6 m. If the size (on the fovea) of the imaged dot is less than the size of a single resolution element, we assume that the dot will be invisible to the eye. In other words, the eye will not detect a dot if its diameter, d, is such that 0:07(d) < 1:3 £ 10¡6 m, or d < 18:6 £ 10¡6 m.
Figure P2.1
4
Chapter 2 Solutions (Students)
Problem 2.3 ¸ = c=v = 2:998 £ 108 (m/s)=60(1/s) = 4:99 £ 106 m = 5000 Km.
Problem 2.6 One possible solution is to equip a monochrome camera with a mechanical device that sequentially places a red, a green, and a blue pass ®lter in front of the lens. The strongest camera response determines the color. If all three responses are approximately equal, the object is white. A faster system would utilize three different cameras, each equipped with an individual ®lter. The analysis would be then based on polling the response of each camera. This system would be a little more expensive, but it would be faster and more reliable. Note that both solutions assume that the ®eld of view of the camera(s) is such that it is completely ®lled by a uniform color [i.e., the camera(s) is(are) focused on a part of the vehicle where only its color is seen. Otherwise further analysis would be required to isolate the region of uniform color, which is all that is of interest in solving this problem].
Problem 2.9 (a) The total amount of data (including the start and stop bit) in an 8-bit, 1024 £ 1024 image, is (1024)2 £ [8 + 2] bits. The total time required to transmit this image over a At 56K baud link is (1024)2 £ [8 + 2]=56000 = 187:25 sec or about 3.1 min. (b) At 750K this time goes down to about 14 sec.
Problem 2.11 Let p and q be as shown in Fig. P2.11. Then, (a) S1 and S2 are not 4-connected because q is not in the set N4 (p)u (b) S1 and S2 are 8-connected because q is in the set N8 (p)u (c) S1 and S2 are m-connected because (i) q is in ND (p), and (ii) the set N4 (p) N4 (q) is empty.
Problem 2.12
5
Figure P2.11
Problem 2.12 The solution to this problem consists of de®ning all possible neighborhood shapes to go from a diagonal segment to a corresponding 4-connected segment, as shown in Fig. P2.12. The algorithm then simply looks for the appropriate match every time a diagonal segment is encountered in the boundary.
Figure P2.12
Problem 2.15 (a) When V = f0; 1g, 4-path does not exist between p and q because it is impossible to
6
Chapter 2 Solutions (Students) get from p to q by traveling along points that are both 4-adjacent and also have values from V . Figure P2.15(a) shows this conditionu it is not possible to get to q. The shortest 8-path is shown in Fig. P2.15(b)u its length is 4. The length of shortest m- path (shown dashed) is 5. Both of these shortest paths are unique in this case. (b) One possibility for the shortest 4-path when V = f1; 2g is shown in Fig. P2.15(c)u its length is 6. It is easily veri®ed that another 4-path of the same length exists between p and q. One possibility for the shortest 8-path (it is not unique) is shown in Fig. P2.15(d)u its length is 4. The length of a shortest m-path (shoen dashed) is 6. This path is not unique.
Figure P2.15
Problem 2.16 (a) A shortest 4-path between a point p with coordinates (x; y) and a point q with coordinates (s; t) is shown in Fig. P2.16, where the assumption is that all points along the path are from V . The length of the segments of the path are jx ¡ sj and jy ¡ tj, respectively. The total path length is jx ¡ sj + jy ¡ tj, which we recognize as the de®nition of the D4 distance, as given in Eq. (2.5-16). (Recall that this distance is independent of any paths that may exist between the points.) The D4 distance obviously is equal to the length of the shortest 4-path when the length of the path is jx ¡ sj + jy ¡ tj. This occurs whenever we can get from p to q by following a path whose elements (1) are from V; and (2) are arranged in such a way that we can traverse the path from p to q by making turns in at most two directions (e.g., right and up). (b) The path may of may not be unique, depending on V and the values of the points along the way.
Problem 2.18
7
Figure P2.16
Problem 2.18 With reference to Eq. (2.6-1), let H denote the neighborhood sum operator, let S1 and S2 denote two different small subimage areas of the same size, and let S1 +S2 denote the corresponding pixel-by-pixel sum of the elements in S1 and S2 , as explained in Section 2.5.4. Note that the size of the neighborhood (i.e., number of pixels) is not changed by this pixel-by-pixel sum. The operator H computes the sum of pixel values is a given neighborhood. Then, H(aS1 + bS2 ) means: (1) multiplying the pixels in each of the subimage areas by the constants shown, (2) adding the pixel-by-pixel values from S1 and S2 (which produces a single subimage area), and (3) computing the sum of the values of all the pixels in that single subimage area. Let ap1 and bp2 denote two arbitrary (but corresponding) pixels from aS1 + bS2 . Then we can write X H(aS1 + bS2 ) = ap1 + bp2 p1 2S1 and p2 2S2
=
X
ap1 +
p1 2S1
= a
X
p1 2S1
X
bp2
p2 2S2
p1 + b
X
p2
p2 2S2
= aH(S1 ) + bH(S2 )
which, according to Eq. (2.6-1), indicates that H is a linear operator.
3
Solutions (Students)
Problem 3.2 (a) s = T (r) =
1 : 1 + (m=r)E
Problem 3.4 (a) The number of pixels having different gray level values would decrease, thus causing the number of components in the histogram to decrease. Since the number of pixels would not change, this would cause the height some of the remaining histogram peaks to increase in general. Typically, less variability in gray level values will reduce contrast.
Problem 3.5 All that histogram equalization does is remap histogram components on the intensity scale. To obtain a uniform (-at) histogram would require in general that pixel intensities be actually redistributed so that there are L groups of n=L pixels with the same intensity, where L is the number of allowed discrete intensity levels and n is the total number of pixels in the input image. The histogram equalization method has no provisions for this type of (arti®cial) redistribution process.
Problem 3.8 We are interested in just one example in order to satisfy the statement of the problem. Consider the probability density function shown in Fig. P3.8(a). A plot of the transformation T (r) in Eq. (3.3-4) using this particular density function is shown in Fig. P3.8(b). Because pr (r) is a probability density function we know from the discussion
10
Chapter 3 Solutions (Students) in Section 3.3.1 that the transformation T (r) satis®es conditions (a) and (b) stated in that section. However, we see from Fig. P3.8(b) that the inverse transformation from s back to r is not single valued, as there are an in®nite number of possible mappings from s = 1=2 back to r. It is important to note that the reason the inverse transformation function turned out not to be single valued is the gap in pr (r) in the interval [1=4; 3=4].
Figure P3.8.
Problem 3.9 (c) If none of the gray levels rk ; k = 1; 2; : : : ; L ¡ 1; are 0, then T (rk ) will be strictly monotonic. This implies that the inverse transformation will be of ®nite slope and this will be single-valued.
Problem 3.11 The value of the histogram component corresponding to the kth intensity level in a neighborhood is nk pr (rk ) = n
Problem 3.14
11
for k = 1; 2; : : : ; K ¡ 1;where nk is the number of pixels having gray level value rk , n is the total number of pixels in the neighborhood, and K is the total number of possible gray levels. Suppose that the neighborhood is moved one pixel to the right. This deletes the leftmost column and introduces a new column on the right. The updated histogram then becomes 1 p0r (rk ) = [nk ¡ nLk + nRk ] n for k = 0; 1; : : : ; K ¡ 1, where nLk is the number of occurrences of level rk on the left column and nRk is the similar quantity on the right column. The preceding equation can be written also as 1 p0r (rk ) = pr (rk ) + [nRk ¡ nLk ] n for k = 0; 1; : : : ; K ¡ 1: The same concept applies to other modes of neighborhood motion: 1 p0r (rk ) = pr (rk ) + [bk ¡ ak ] n for k = 0; 1; : : : ; K ¡ 1, where ak is the number of pixels with value rk in the neighborhood area deleted by the move, and bk is the corresponding number introduced by the move.
¾g2 = ¾2f +
1 2 [¾ + ¾2´ 2 + ¢ ¢ ¢ + ¾2´ ] K K 2 ´1
The ®rst term on the right side is 0 because the elements of f are constants. The various ¾2´i are simply samples of the noise, which is has variance ¾2´ . Thus, ¾2´i = ¾2´ and we have K 1 ¾ g2 = 2 ¾2´ = ¾2´ K K which proves the validity of Eq. (3.4-5).
Problem 3.14 Let g(x; y) denote the golden image, and let f (x; y) denote any input image acquired during routine operation of the system. Change detection via subtraction is based on computing the simple difference d(x; y) = g(x; y) ¡ f (x; y). The resulting image d(x; y) can be used in two fundamental ways for change detection. One way is use a pixel-by-pixel analysis. In this case we say that f (x; y) is }close enough} to the golden image if all the pixels in d(x; y) fall within a speci®ed threshold band [Tmin ; Tmax ] where Tmin is negative and Tmax is positive. Usually, the same value of threshold is
12
Chapter 3 Solutions (Students) used for both negative and positive differences, in which case we have a band [¡T; T ] in which all pixels of d(x; y) must fall in order for f (x; y) to be declared acceptable. The second major approach is simply to sum all the pixels in jd(x; y)j and compare the sum against a threshold S. Note that the absolute value needs to be used to avoid errors cancelling out. This is a much cruder test, so we will concentrate on the ®rst approach. There are three fundamental factors that need tight control for difference-based inspection to work: (1) proper registration, (2) controlled illumination, and (3) noise levels that are low enough so that difference values are not affected appreciably by variations due to noise. The ®rst condition basically addresses the requirement that comparisons be made between corresponding pixels. Two images can be identical, but if they are displaced with respect to each other, comparing the differences between them makes no sense. Often, special markings are manufactured into the product for mechanical or image-based alignment Controlled illumination (note that illumination} is not limited to visible light) obviously is important because changes in illumination can affect dramatically the values in a difference image. One approach often used in conjunction with illumination control is intensity scaling based on actual conditions. For example, the products could have one or more small patches of a tightly controlled color, and the intensity (and perhaps even color) of each pixels in the entire image would be modi®ed based on the actual versus expected intensity and/or color of the patches in the image being processed. Finally, the noise content of a difference image needs to be low enough so that it does not materially affect comparisons between the golden and input images. Good signal strength goes a long way toward reducing the effects of noise. Another (sometimes complementary) approach is to implement image processing techniques (e.g., image averaging) to reduce noise. Obviously there are a number if variations of the basic theme just described. For example, additional intelligence in the form of tests that are more sophisticated than pixel-bypixel threshold comparisons can be implemented. A technique often used in this regard is to subdivide the golden image into different regions and perform different (usually more than one) tests in each of the regions, based on expected region content.
Problem 3.17 (a) Consider a 3 £ 3 mask ®rst. Since all the coef®cients are 1 (we are ignoring the 1/9
Problem 3.19
13
scale factor), the net effect of the lowpass ®lter operation is to add all the gray levels of pixels under the mask. Initially, it takes 8 additions to produce the response of the mask. However, when the mask moves one pixel location to the right, it picks up only one new column. The new response can be computed as Rnew = Rold ¡ C1 + C3
where C1 is the sum of pixels under the ®rst column of the mask before it was moved, and C3 is the similar sum in the column it picked up after it moved. This is the basic box-®lter or moving-average equation. For a 3 £ 3 mask it takes 2 additions to get C3 (C1 was already computed). To this we add one subtraction and one addition to get Rnew . Thus, a total of 4 arithmetic operations are needed to update the response after one move. This is a recursive procedure for moving from left to right along one row of the image. When we get to the end of a row, we move down one pixel (the nature of the computation is the same) and continue the scan in the opposite direction. For a mask of size n £ n, (n ¡ 1) additions are needed to obtain C3 , plus the single subtraction and addition needed to obtain Rnew , which gives a total of (n + 1) arithmetic operations after each move. A brute-force implementation would require n2 ¡ 1 additions after each move.
Problem 3.19 (a) There are n2 points in an n £ n median ®lter mask. Since n is odd, the median value, ³, is such that there are (n2 ¡ 1)=2 points with values less than or equal to ³ and the same number with values greater than or equal to ³. However, since the area A (number of points) in the cluster is less than one half n2 , and A and n are integers, it follows that A is always less than or equal to (n2 ¡ 1)=2. Thus, even in the extreme case when all cluster points are encompassed by the ®lter mask, there are not enough points in the cluster for any of them to be equal to the value of the median (remember, we are assuming that all cluster points are lighter or darker than the background points). Therefore, if the center point in the mask is a cluster point, it will be set to the median value, which is a background shade, and thus it will be eliminated} from the cluster. This conclusion obviously applies to the less extreme case when the number of cluster points encompassed by the mask is less than the maximum size of the cluster.
14
Chapter 3 Solutions (Students)
Problem 3.20 (a) Numerically sort the n2 values. The median is ³ = [(n2 + 1)=2]-th largest value. (b) Once the values have been sorted one time, we simply delete the values in the trailing edge of the neighborhood and insert the values in the leading edge in the appropriate locations in the sorted array.
Problem 3.22 From Fig. 3.35, the vertical bars are 5 pixels wide, 100 pixels high, and their separation is 20 pixels. The phenomenon in question is related to the horizontal separation between bars, so we can simplify the problem by considering a single scan line through the bars in the image. The key to answering this question lies in the fact that the distance (in pixels) between the onset of one bar and the onset of the next one (say, to its right) is 25 pixels. Consider the scan line shown in Fig. P3.22. Also shown is a cross section of a 25£25 mask. The response of the mask is the average of the pixels that it encompasses. We note that when the mask moves one pixel to the right, it loses on value of the vertical bar on the left, but it picks up an identical one on the right, so the response doesnzt change. In fact, the number of pixels belonging to the vertical bars and contained within the mask does not change, regardless of where the mask is located (as long as it is contained within the bars, and not near the edges of the set of bars). The fact that the number of bar pixels under the mask does not change is due to the peculiar separation between bars and the width of the lines in relation to the 25-pixel width of the mask This constant response is the reason no white gaps is seen in the image shown in the problem statement. Note that this constant response does not happen with the 23 £ 23 or the 45 £ 45 masks because they are not }synchronized} with the width of the bars and their separation.
Figure P3.22
Problem 3.25
15
Problem 3.25 The Laplacian operator is de®ned as r2 f = for the unrotated coordinates and as r2 f =
@2 f @2 f + @x2 @y 2 @2f @2 f + : @x02 @y02
for rotated coordinates. It is given that x = x0 cos µ ¡ y 0 sin µ and y = x0 sin µ + y 0 cos µ
where µ is the angle of rotation. We want to show that the right sides of the ®rst two equations are equal. We start with @f = @x0
@f @x @f @y + 0 @x @x @y @x0 @f @f = cos µ + sin µ @x @y Taking the partial derivative of this expression again with respect to x0 yields @2 f @2 f @ = cos2 µ + 02 2 @x @x @x
µ
@f @y
¶
sin µ cos µ +
@ @y
µ
@f @x
¶
cos µ sin µ +
@2 f sin2 µ @y 2
Next, we compute @f @y 0
@f @x @f @y + @x @y0 @y @y 0 @f @f = ¡ sin µ + cos µ @x @y Taking the derivative of this expression again with respect to y 0 gives =
µ ¶ µ ¶ @2 f @2 f @ @f @ @f @ 2f 2 = sin µ ¡ cos µ sin µ ¡ sin µ cos µ + cos2 µ @y02 @x2 @x @y @y @x @y 2 Adding the two expressions for the second derivatives yields @2 f @ 2f @2 f @2 f + = + @x02 @y 02 @x2 @y2 which proves that the Laplacian operator is independent of rotation.
Problem 3.27 Consider the following equation:
16
Chapter 3 Solutions (Students) f(x; y) ¡ r2 f (x; y) = f (x; y) ¡ [f (x + 1; y) + f (x ¡ 1; y) + f (x; y + 1) +f (x; y ¡ 1) ¡ 4f (x; y)] = 6f (x; y) ¡ [f (x + 1; y) + f(x ¡ 1; y) + f (x; y + 1) +f (x; y ¡ 1) + f (x; y)] = 5 f1:2f(x; y)¡ 1 [f (x + 1; y) + f(x ¡ 1; y) + f (x; y + 1) 5 +f (x; y ¡ 1) + f(x; y)]g £ ¤ = 5 1:2f (x; y) ¡ f (x; y)
where f (x; y) denotes the average of f (x; y) in a prede®ned neighborhood that is centered at (x; y) and includes the center pixel and its four immediate neighbors. Treating the constants in the last line of the above equation as proportionality factors, we may write f (x; y) ¡ r2 f (x; y) s f(x; y) ¡ f (x; y): The right side of this equation is recognized as the de®nition of unsharp masking given in Eq. (3.7-7). Thus, it has been demonstrated that subtracting the Laplacian from an image is proportional to unsharp masking.
4
Solutions (Students)
Problem 4.1 By direct substitution of f (x) [Eq. (4.2-6)] into F (u) [Eq. (4.2-5)]: ' # M ¡1 M ¡1 1 X X F (u) = F (r)ej2¼rx=M e¡j2¼ux=M M x=0 r=0 =
M ¡1 M ¡1 X 1 X F (r) ej2¼rx=M e¡j2¼ux=M M r=0 x=0
1 F (u) [M ] M = F (u)
=
where the third step follows from the orthogonality condition given in the problem statement. Substitution of F (u) into f (x) is handled in a similar manner.
Problem 4.4 An important aspect of this problem is to recognize that the quantity (u2 + v2 ) can be replaced by the distance squared, D2 (u; v). This reduces the problem to one variable, which is notationally easier to manage. Rather than carry an award capital letter throughout the development, we de®ne w2 , D2 (u; v) = (u2 + v 2 ). Then we proceed as follows: 2 2 H(w) = e¡w =2¾ : The inverse Fourier transform is Z h(z) = = =
1
¡1 Z 1
¡1 Z 1 ¡1
H(w)ej2¼wz dw
e¡w
2
=2¾2 j2¼wz
e¡ 2¾2 [w 1
e
2
dw
¡j4¼¾2 wz ]
dw:
18
Chapter 4 Solutions (Students) We now make use of the identity e¡
(2¼)2 z2 ¾ 2 2
e
(2¼)2 z2 ¾2 2
= 1:
Inserting this identity in the preceding integral yields Z 1 2 2 2 4 2 (2¼)2 z2 ¾ 2 1 ¡ 2 e¡ 2¾2 [w ¡j4¼¾ wz¡(2¼) ¾ z ] dw h(z) = e ¡1 Z 1 2 2 (2¼)2 z2 ¾ 2 1 2 = e¡ e¡ 2¾2 [w ¡ j2¼¾ z] dw: ¡1
Next we make the change of variable r = w ¡ j2¼¾2 z. Then, dr = dw and the above integral becomes Z 1 (2¼)2 z 2 ¾2 r2 2 h(z) e¡ e¡ 2¾2 dr: ¡1 p Finally, we multiply and divide the right side of this equation by 2¼¾: · ¸ Z 1 p (2¼)2 z2 ¾2 r2 1 2 p h(z) = 2¼¾e¡ e¡ 2¾2 dr : 2¼¾ ¡1 The expression inside the brackets is recognized as a Gaussian probability density function, whose integral from ¡1 to 1 is 1. Then, p (2¼)2 z2 ¾ 2 2 h(z) = 2¼¾e¡ : p 2 2 2 2 Going back to two spatial variables gives the ®nal result:h(x; y) = 2¼¾ e¡2¼ ¾ (x +y ) :
Problem 4.6 (a) We note ®rst that (¡1)x+y = ej¼(x+y) . Then, M¡1 N¡1 h i i 1 X Xh = f(x; y)ej¼(x+y) = f (x; y)ej¼(x+y) e¡j2¼(ux=M + vy=N ) M N x=0 y=0 =
=
M¡1 N¡1 i yN 1 X Xh xM f (x; y)e¡j2¼(¡ 2M ¡ 2N ) M N x=0 y=0
e¡j2¼(ux=M + vy=N ) M¡1 N¡1 M N 1 X X f(x; y)e¡j2¼(x[u¡ 2 ]=M +y[v¡ 2 ]=N ) M N x=0 y=0
= F (u ¡ M=2; v ¡ N=2):
Problem 4.8 With reference to Eq. (4.4-1), all the highpass ®lters in discussed in Section 4.4 can be expressed a 1 minus the transfer function of lowpass ®lter (which we know do not have
Problem 4.11
19
an impulse at the origin). The inverse Fourier transform of 1 gives an impulse at the origin in the highpass spatial ®lters.
Problem 4.11 Starting from Eq. (4.2-30), we easily ®nd the expression for the de®nition of continuous convolution in one dimension: Z f (x) ¤ g(x) =
1
¡1
f (®)g(x ¡ ®)d®:
The Fourier transform of this expression is ¸ Z 1 ·Z 1 = [f (x) ¤ g(x)] = f(®)g(x ¡ ®)d® e¡j2¼uxdx ¡1 ¡1 ·Z 1 ¸ Z 1 = f(®) g(x ¡ ®)e¡j2¼ux dx d®: ¡1
¡1
The term inside the inner brackets is the Fourier transform of g(x ¡ ®). But, = [g(x ¡ ®)] = G(u)e¡j2¼u®
so
Z
1
£ ¤ f (®) G(u)e¡j2¼u® d® ¡1 Z 1 = G(u) f (®)e¡j2¼u® d®
= [f(x) ¤ g(x)] =
¡1
= G(u)F (u):
This proves that multiplication in the frequency domain is equal to convolution in the spatial domain. The proof that multiplication in the spatial domain is equal to convolution in the spatial domain is done in similar way.
Problem 4.13 (a) One application of the ®lter gives: G(u; v) = H(u; v)F (u; v) = e¡D
2
(u;v)=2D02
F (u; v):
Similarly, K applications of the ®lter would give GK (u; v) = e¡KD
2
(u;v)=2D02
F (u; v):
The inverse DFT of GK (u; v) would give the image resulting from K passes of the Gaussian ®lter. If K is large enough,} the Gaussian LPF will become a notch pass ®lter, passing only F (0; 0). We know that this term is equal to the average value of the image. So, there is a value of K after which the result of repeated lowpass ®ltering
20
Chapter 4 Solutions (Students) will simply produce a constant image. The value of all pixels on this image will be equal to the average value of the original image. Note that the answer applies even as K approaches in®nity. In this case the ®lter will approach an impulse at the origin, and this would still give us F (0; 0) as the result of ®ltering.
Problem 4.15 The problem statement gives the form of the difference in the x-direction. A similar expression gives the difference in the y-direction. The ®ltered function in the spatial domain then is: g(x; y) = f (x; y) ¡ f (x + 1; y) + f (x; y) ¡ f (x; y + 1): From Eq. (4.6-2), G(u; v) = F (u; v) ¡ F (u; v)ej2¼u=M + F (u; v) ¡ F (u; v)ej2¼v=N = [1 ¡ ej2¼u=M ]F (u; v) + [1 ¡ ej2¼v=N ]F (u; v)
= H(u; v)F (u; v); where H(u; v) is the ®lter function: h i H(u; v) = ¡2j sin(¼u=M )ej¼u=M + sin(¼v=N )ej¼v=N :
(b) To see that this is a highpass ®lter, it helps to express the ®lter function in the form of our familiar centered functions: h i H(u; v) = ¡2j sin(¼[u ¡ M=2]=M )ej¼u=M + sin(¼[v ¡ N=2]=N )ej¼v=N :
Consider one variable for convenience. As u ranges from 0 to M , H(u; v) starts at its maximum (complex) value of 2j for u = 0 and decreases from there. When u = M=2 (the center of the shifted function), A similar argument is easily carried out when considering both variables simultaneously. The value of H(u; v) starts increasing again and achieves the maximum value of 2j again when u = M . Thus, this ®lter has a value of 0 a the origin and increases with increasing distance from the origin. This is the characteristic of a highpass ®lter. A similar argument is easily carried out when considering both variables simultaneously.
Problem 4.18 The answer is no. The Fourier transform is a linear process, while the square and square roots involved in computing the gradient are nonlinear operations. The Fourier transform could be used to compute the derivatives (as differencesxsee Prob.4.15), but the
Problem 4.21
21
squares, square root, or absolute values must be computed directly in the spatial domain.
Problem 4.21 Recall that the reason for padding is to establish a }buffer} between the periods that are implicit in the DFT. Imagine the image on the left being duplicated in®nitely many times to cover the xy-plane. The result would be a checkerboard, with each square being in the checkerboard being the image (and the black extensions). Now imagine doing the same thing to the image on the right. The results would be indistinguishable. Thus, either form of padding accomplishes the same separation between images, as desired.
Problem 4.24 (a) and (b) See Figs. P4.24(a) and (b).
Figures P4.24(a) and (b)
Problem 4.25 Because M = 2n , we can write Eqs. (4.6-47) and (4.6-48) respectively as 1 m(n) = M n 2 and a(n) = Mn: Proof by induction begins by showing that both equations hold for n = 1: 1 m(1) = (2)(1) = 1 and a(1) = (2)(1) = 2: 2
22
Chapter 4 Solutions (Students) We know these results to be correct from the discussion in Section 4.6.6. Next, we assume that the equations hold for n. Then, we are required to prove that they also are true for n + 1. From Eq. (4.6-45), m(n + 1) = 2m(n) + 2n : Substituting m(n) from above, m(n + 1) = = = = Therefore, Eq. (4.6-47) is valid for all n.
µ
¶ 1 2 M n + 2n 2 µ ¶ 1 n 2 2 n + 2n 2 2n (n + 1) 1 ¡ n+1 ¢ (n + 1): 2 2
From Eq. (4.6-46), a(n + 1) = 2a(n) + 2n+1 : Substituting the above expression for a(n) yields a(n + 1) = 2M n + 2n+1 = 2(2n n) + 2n+1 = 2n+1 (n + 1) which completes the proof.
5
Solutions (Students)
Problem 5.1 The solutions to (a), (b), and (c) are shown in Fig. P5.1, from left to right:
Figure P5.1
Problem 5.3 The solutions to (a), (b), and (c) are shown in Fig. P5.3, from left to right:
Figure P5.3
24
Chapter 5 Solutions (Students)
Problem 5.5 The solutions to (a), (b), and (c) are shown in Fig. P5.5, from left to right:
Figure P5.5
Problem 5.7 The solutions to (a), (b), and (c) are shown in Fig. P5.7, from left to right:
Figure P5.7
Problem 5.9 The solutions to (a), (b), and (c) are shown in Fig. P5.9, from left to right:
Problem 5.10
25
Figure P5.9
Problem 5.10 (a) The key to this problem is that the geometric mean is zero whenever any pixel is zero. Draw a pro®le of an ideal edge with a few points valued 0 and a few points valued 1. The geometric mean will give only values of 0 and 1, whereas the arithmetic mean will give intermediate values (blur).
Problem 5.12 A bandpass ®lter is obtained by subtracting the corresponding bandreject ®lter from 1: Hbp (u; v) = 1 ¡ Hbr (u; v): Then: (a) Ideal bandpass ®lter:
8 W >< 0 if D(u; v) < D0 ¡ 2 HIbp (u; v) = 1 if D0 ¡ W 2 · D(u; v) · D0 + > : 0 D(u; v) > D0 + W 2
(b) Butterworth bandpass ®lter:
HBbp (u; v) = 1 ¡
=
h
1+
h
1 D(u;v)W D 2 (u;v)¡D02
D(u;v)W D 2 (u;v)¡D 20
1+
h
i2n
D(u;v)W D 2 (u;v)¡D02
i2n
i2n :
W 2
:
26
Chapter 5 Solutions (Students) (c) Gaussian bandpass ®lter:
'
¡ 12
HGbp (u; v) = 1 ¡ 1 ¡ e = e
¡ 12
·
·
2 D2 (u;v)¡D0 D(u;v)W
D 2 (u;v)¡D2 0 D(u;v)W
¸2
¸2 #
:
Problem 5.14 We proceed as follows: F (u; v) = =
ZZ
1
¡1 1
ZZ
f (x; y)e¡j2¼(ux + vy) dx dy A sin(u0 x + v0 y)e¡j2¼(ux + vy) dx dy:
¡1
Using the exponential de®nition of the sine function: ¢ 1 ¡ jµ e ¡ e¡jµ sin µ = 2j gives us ZZ 1 h i ¡jA F (u; v) = ej(u0 x + v0 y) ¡ e¡j(u0 x + v0 y) e¡j2¼(ux + vy) dx dy 2 ¡1 ·Z Z 1 ¸ ¡jA ej2¼(u0 x=2¼ + v0 y=2¼) e¡j2¼(ux + vy) dx dy ¡ = 2 ¡1 ·ZZ 1 ¸ jA ¡j2¼(u0 x=2¼ + v0 y=2¼) ¡j2¼(ux + vy) e e dx dy : 2 ¡1 These are the Fourier transforms of the functions 1 £ ej2¼(u0 x=2¼ + v0 y=2¼) and 1 £ e¡j2¼(u0 x=2¼ + v0 y=2¼) respectively. The Fourier transform of the 1 gives an impulse at the origin, and the exponentials shift the origin of the impulse, as discussed in Section 4.6.1. Thus, ³ u0 v0 ´ u0 v0 ´i ¡jA h ³ F (u; v) = ± u¡ ;v ¡ ¡± u+ ;v + : 2 2¼ 2¼ 2¼ 2¼
Problem 5.16 From Eq. (5.5-13), g(x; y) =
ZZ
1
¡1
f (®; ¯)h(x ¡ ®; y ¡ ¯) d® d¯:
Problem 5.18
27
It is given that f (x; y) = ±(x ¡ a); so f (®; ¯) = ±(® ¡ a): Then, using the impulse response given in the problem statement, ZZ 1 2 2 ±(® ¡ a)e¡[(x¡®) +(y¡¯) ] d® d¯ g(x; y) = ¡1 ZZ 1 2 2 = ±(® ¡ a)e¡[(x¡®) ] e¡[(y¡¯) ] d® d¯ ¡1 Z 1 Z 1 2 2 e¡[(y¡¯) ] d¯ ±(® ¡ a)e¡[(x¡®) ] d® = ¡1 ¡1 Z 1 ¡[(y¡¯)2 ] ¡[(x¡a)2 ] e d¯ = e ¡1
where we used the fact that the integral of the impulse is nonzero only when ® = a: Next, we note that Z 1 Z 1 2 ¡[(y¡¯)2 ] e d¯ = e¡[(¯¡y) ] d¯ ¡1
¡1
which is in the form of a constant times a Gaussian density with variance ¾2 = 1=2 or p standard deviation ¾ = 1= 2. In other words, · ¸# ' 2 p ¡(1=2) (¯¡y) 1 (1=2) ¡[(¯¡y)2 ] e = 2¼(1=2) p e : 2¼(1=2) The integral from minus to plus in®nity of the quantity inside the brackets is 1, so p 2 g(x; y) = ¼e¡[(x¡a) ]
which is a blurred version of the original image.
Problem 5.18 Following the procedure in Section 5.6.3, Z T H(u; v) = e¡j2¼ux0 (t) dt 0
=
Z
T
2 e¡j2¼u[(1=2)at ] dt
0
=
Z
T
2
e¡j¼uat dt
0
= = where
Z
T
r0
£ ¤ cos(¼uat2 ) ¡ j sin(¼uat2 ) dt
¤ p T2 £ p C( ¼uaT ) ¡ jS( ¼uaT ) 2¼uaT 2 r Z x 2¼ C(x) = cos t2 dt T 0
28
Chapter 5 Solutions (Students) and S(x) =
r
2 ¼
Z
x
sin t2 dt:
0
These are Fresnel cosine and sine integrals. They can be found, for example, the Handbook of Mathematical Functions, by Abramowitz, or other similar reference.
Problem 5.20 Measure the average value of the background. Set all pixels in the image, except the cross hairs, to that gray level. Denote the Fourier transform of this image by G(u; v). Since the characteristics of the cross hairs are given with a high degree of accuracy, we can construct an image of the background (of the same size) using the background gray levels determined previously. We then construct a model of the cross hairs in the correct location (determined from he given image) using the provided dimensions and gray level of the crosshairs. Denote by F (u; v) the Fourier transform of this new image . The ratio G(u; v)=F (u; v) is an estimate of the blurring function H(u; v). In the likely event of vanishing values in F (u; v), we can construct a radially-limited ®lter using the method discussed in connection with Fig. 5.27. Because we know F (u; v) and G(u; v), and an estimate of H(u; v), we can also re®ne our estimate of the blurring function by substituting G and H in Eq. (5.8-3) and adjusting K to get as close as possible to a good result for F (u; v) [the result can be evaluated visually by taking the inverse Fourier transform]. The resulting ®lter in either case can then be used to deblur the image of the heart, if desired.
Problem 5.22 This is a simple plugin problem. Its purpose is to gain familiarity with the various terms of the Wiener ®lter. From Eq. (5.8-3), ' # 1 jH(u; v)j2 HW (u; v) = H(u; v) jH(u; v)j2 + K where jH(u; v)j2 Then,
= H ¤ (u; v)H(u; v) = 2¼¾2 (u2 + v 2 )2 e¡4¼ '
2
¾ 2 (x2 +y 2 )
:
# p 2 2 2 2 2¼¾(u2 + v2 )e¡2¼ ¾ (x +y ) ¤ HW (u; v) = ¡ £ : 2¼¾2 (u2 + v 2 )2 e¡4¼2 ¾ 2 (x2 +y2 ) + K
Problem 5.25
29
Problem 5.25 (a) It is given that
¯ ¯2 ¯^ ¯ 2 2 ¯F (u; v)¯ = jR(u; v)j jG(u; v)j :
From Problem 5.24, ¯ ¯2 h i ¯^ ¯ 2 2 2 2 ¯F (u; v)¯ = jR(u; v)j jH(u; v)j jF (u; v)j + jN (u; v)j : ¯ ¯2 ¯ ¯ Forcing ¯F^ (u; v)¯ to equal jF (u; v)j2 gives ' #1=2 jF (u; v)j2 R(u; v) = : jH(u; v)j2 jF (u; v)j2 + jN (u; v)j2
Problem 5.27 The basic idea behind this problem is to use the camera and representative coins to model the degradation process and then utilize the results in an inverse ®lter operation. The principal steps are as follows: 1. Select coins as close as possible in size and content as the lost coins. Select a background that approximates the texture and brightness of the photos of the lost coins. 2. Set up the museum photographic camera in a geometry as close as possible to give images that resemble the images of the lost coins (this includes paying attention to illumination). Obtain a few test photos. To simplify experimentation, obtain a TV camera capable of giving images that resemble the test photos. This can be done by connecting the camera to an image processing system and generating digital images, which will be used in the experiment. 3. Obtain sets of images of each coin with different lens settings. The resulting images should approximate the aspect angle, size (in relation to the area occupied by the background), and blur of the photos of the lost coins. 4. The lens setting for each image in (3) is a model of the blurring process for the corresponding image of a lost coin. For each such setting, remove the coin and background and replace them with a small, bright dot on a uniform background, or other mechanism to approximate an impulse of light. Digitize the impulse. Its Fourier transform is the transfer function of the blurring process. 5. Digitize each (blurred) photo of a lost coin, and obtain its Fourier transform. At this point, we have H(u; v) and G(u; v) for each coin. 6. Obtain an approximation to F (u; v) by using a Wiener ®lter. Equation (5.8-3) is particularly attractive because it gives an additional degree of freedom (K) for experimenting.
30
Chapter 5 Solutions (Students) 7. The inverse Fourier transform of each approximate F (u; v) gives the restored image. In general, several experimental passes of these basic steps with various different settings and parameters are required to obtain acceptable results in a problem such as this.
6
Solutions (Students)
Problem 6.2 Denote by c the given color, and let its coordinates be denoted by (x0 ; y0 ). The distance between c and c1 is h i1=2 d(c; c1 ) = (x0 ¡ x1 )2 + (y0 ¡ y1 )2 :
Similarly the distance between c1 and c2 h i1=2 d(c1 ; c2 ) = (x1 ¡ x2 )2 + (y1 ¡ y2 )2 :
The percentage p1 of c1 in c is
d(c1 ; c2 ) ¡ d(c; c1 ) £ 100: d(c1 ; c2 ) The percentage p2 of c2 is simply p2 = 100 ¡ p1 . In the preceding equation we see, for example, that when c = c1 , then d(c; c1 ) = 0 and it follows that p1 = 100% and p2 = 0%. Similarly, when d(c; c1 ) = d(c1 ; c2 ); it follows that p1 = 0% and p2 = 100%. Values in between are easily seen to follow from these simple relations. p1 =
Problem 6.4 Use color ®lters sharply tuned to the wavelengths of the colors of the three objects. Thus, with a speci®c ®lter in place, only the objects whose color corresponds to that wavelength will produce a predominant response on the monochrome camera. A motorized ®lter wheel can be used to control ®lter position from a computer. If one of the colors is white, then the response of the three ®lters will be approximately equal and high. If one of the colors is black, the response of the three ®lters will be approximately equal and low.
Problem 6.6 For the image given, the maximum intensity and saturation requirement means that the
32
Chapter 6 Solutions (Students) RGB component values are 0 or 1. We can create the following table with 0 and 255 representing black and white, respectively: Table P6.6 Color
R
G
B
Mono R
Mono G
Mono B
Black Red Yellow Green Cyan Blue Magenta White
0 1 1 0 0 0 1 1
0 0 1 1 1 0 0 1
0 0 0 0 1 1 1 1
0 255 255 0 0 0 255 255
0 0 255 255 255 0 0 255
0 0 0 0 255 255 255 255
Gray
0.5
0.5
0.5
128
128
128
Thus, we get the monochrome displays shown in Fig. P6.6.
Figure P6.6
Problem 6.8 (a) All pixel values in the Red image are 255. In the Green image, the ®rst column is all 0zsu the second column all 1zsu and so on until the last column, which is composed of all 255zs. In the Blue image, the ®rst row is all 255zsu the second row all 254zs, and so on until the last row which is composed of all 0zs.
Problem 6.10 Equation (6.2-1) reveals that each component of the CMY image is a function of a single component of the corresponding RGB imagexC is a function of R, M of G, and Y of B. For clarity, we will use a prime to denote the CMY components. From Eq. (6.5-6),
Problem 6.12
33
we know that si = kri for i = 1; 2; 3 (for the R, G, and B components). And from Eq. (6.2-1), we know that the CMY components corresponding to the ri and si (which we are denoting with primes) are ri¶= 1 ¡ ri and si¶= 1 ¡ si : Thus, ri = 1 ¡ ri¶ and si¶= 1 ¡ si = 1 ¡ kri = 1 ¡ k (1 ¡ ri¶) so that si¶= kri¶+ (1 ¡ k) :
Problem 6.12 Using Eqs. (6.2-2) through (6.2-4), we get the results shown in Table P6.12. Table P6.12 Color
R
G
B
H
S
I
Mono H
Mono S
Mono I
Black Red Yellow Green Cyan Blue Magenta White
0 1 1 0 0 0 1 1
0 0 1 1 1 0 0 1
0 0 0 0 1 1 1 1
w 0 0.17 0.33 0.5 0.67 0.83 w
0 1 1 1 1 1 1 0
0 0.33 0.67 0.33 0.67 0.33 0.67 1
w 0 43 85 128 170 213 w
w 255 255 255 255 255 255 0
0 85 170 85 170 85 170 255
Gray
0.5
0.5
0.5
w
0
0.5
w
0
128
Note that, in accordance with Eq. (6.2-2), hue is unde®ned when R = G = B since ¡ ¢ µ = cos¡1 00 . In addition, saturation is unde®ned when R = G = B = 0 since Eq. (6.2-3) yields S = 1 ¡ 3 min(0) = 1 ¡ 00 . Thus, we get the monochrome display shown 3¢0 in Fig. P6.12.
34
Chapter 6 Solutions (Students)
Figure P6.12
Problem 6.14 There are two important aspects to this problem. One is to approach it in HSI space and the other is to use polar coordinates to create a hue image whose values grow as a function of angle. The center of the image is the middle of whatever image area is used. Then, for example, the values of the hue image along a radius when the angle is 0± would be all 0zs. The angle then is incremented by, say, one degree, and all the values along that radius would be 1zs, and so on. Values of the saturation image decrease linearly in all radial directions from the origin. The intensity image is just a speci®ed constant. With these basics in mind it is not dif®cult to write a program that generates the desired result.
Problem 6.16 (a) It is given that the colors in Fig. 6.16(a) are primary spectrum colors. It also is given that the gray-level images in the problem statement are 8-bit images. The latter condition means that hue (angle) can only be divided into a maximum number of 256 values. Since hue values are represented in the interval from 0± to 360± this means that for an 8-bit image the increments between contiguous hue values are now 360=255. Another way of looking at this is that the entire [0, 360] hue scale is compressed to the range [0, 255]. Thus, for example, yellow (the ®rst primary color we encounter), which is 60± now becomes 43 (the closest integer) in the integer scale of the 8-bit image shown in the problem statement. Similarly, green, which is 120± becomes 85 in this image. From this we easily compute the values of the other two regions as being 170 and 213. The region in the middle is pure white [equal proportions of red green and blue in Fig. 6.61(a)] so its hue by de®nition is 0. This also is true of the black background.
Problem 6.14
35
Problem 6.18 Using Eq. (6.2-3), we see that the basic problem is that many different colors have the same saturation value. This was demonstrated in Problem 6.12, where pure red, yellow, green, cyan, blue, and magenta all had a saturation of 1. That is, as long as any one of the RGB components is 0, Eq. (6.2-3) yields a saturation of 1. Consider RGB colors (1, 0, 0) and (0, 0.59, 0), which represent a red and a green. The HSI triplets for these colors [per Eq. (6.4-2) through (6.4-4)] are (0, 1, 0.33) and (0.33, 1, 0.2), respectively. Now, the complements of the beginning RGB values (see Section 6.5.2) are (0, 1, 1) and (1, 0.41, 1), respectivelyu the corresponding colors are cyan and magenta. Their HSI values [per Eqs. (6.4-2) through (6.4-4)] are (0.5, 1, 0.66) and (0.83, 0.48, 0.8), respectively. Thus, for the red, a starting saturation of 1 yielded the cyan complemented} saturation of 1, while for the green, a starting saturation of 1 yielded the magenta complemented} saturation of 0.48. That is, the same starting saturation resulted in two different complemented} saturations. Saturation alone is not enough information to compute the saturation of the complemented color.
Problem 6.20 The RGB transformations for a complement [from Fig. 6.33(b)] are: si = 1 ¡ ri
where i = 1; 2; 3 (for the R, G, and B components). But from the de®nition of the CMY space in Eq. (6.2-1), we know that the CMY components corresponding to ri and si , which we will denote using primes, are
Thus, and so that
ri¶= 1 ¡ ri si¶= 1 ¡ si ri = 1 ¡ ri¶ si¶= 1 ¡ si = 1 ¡ (1 ¡ ri ) = 1 ¡ (1 ¡ (1 ¡ ri¶)) s¶= 1 ¡ ri¶
36
Chapter 6 Solutions (Students)
Problem 6.22 Based on the discussion is Section 6.5.4 and with reference to the color wheel in Fig. 6.32, we can decrease the proportion of yellow by (1) decreasing yellow, (2) increasing blue, (3) increasing cyan and magenta, or (4) decreasing red and green.
Problem 6.24 The conceptually simplest approach is to transform every input image to the HSI color space, perform histogram speci®cation per the discussion in Section 3.3.2 on the intensity (I) component only (leaving H and S alone), and convert the resulting intensity component with the original hue and saturation components back to the starting color space.
Problem 6.27 (a) The cube is composed of 6 intersecting planes in RGB space. The general equation for such planes is a zR + b zG + c zB + d = 0 where a, b, c, and d are parameters and the zzs are the components of any point (vector) z in RGB space lying on the plane. If an RGB point z does not lie on the plane, and its coordinates are substituted in the preceding equation, then equation will give either a positive or a negative valueu it will not yield zero. We say that z lies on the positive or negative side of the plane, depending on whether the result is positive or negative. We can change the positive side of a plane by multiplying its coef®cients (except d) by ¡1. Suppose that we test the point a given in the problem statement to see whether it is on the positive or negative side each of the six planes composing the box, and change the coef®cients of any plane for which the result is negative. Then, a will lie on the positive side of all planes composing the bounding box. In fact all points inside the bounding box will yield positive values when their coordinates are substituted in the equations of the planes. Points outside the box will give at least one negative or zero value. Thus, the method consists of substituting an unknown color point in the equations of all six planes. If all the results are positive, the point is inside the boxu otherwise it is outside the box. A -ow diagram is asked for in the problem statement to make it simpler to evaluate the studentzs line of reasoning.
7
Solutions (Students)
Problem 7.2 A mean approximation pyramid is formed by forming 2 £ 2 block averages. Since the starting image is of size 4 £ 4, J = 2, and f(x; y) is placed in level 2 of the mean approximation pyramid. The level 1 approximation is (by taking 2 £ 2 block averages over f (x; y) and subsampling): ' # 3:5 5:5 11:5 13:5 and the level 0 approximation pyramid is 2 1 2 6 6 5 6 6 6 9 10 4 13 14
is similarly [8.5]. The completed mean approximation 3 4 7 8 11 12 15 16
3
# 7' i 7 3:5 5:5 h 7 : 8:5 7 11:5 13:5 5
Since no interpolation ®ltering is speci®ed, pixel replication is used in the generation of the mean prediction residual pyramid levels. Level 0 of the prediction residual pyramid is the lowest resolution approximation, [8.5]. The level 2 prediction residual is obtained by upsampling the level 1 approximation and subtracting it from the level 2 (original image). Thus, we get
2 6 6 6 6 4
3 2 1 2 3 4 7 6 6 5 6 7 8 7 7¡6 7 9 10 11 12 5 6 4 13 14 15 16
3 3:5 3:5 5:5 5:5 7 3:5 3:5 5:5 5:5 7 7 11:5 11:5 13:5 13:5 7 5 11:5 11:5 13:5 13:5 2 ¡2:5 6 6 1:5 =6 6 ¡2:5 4 1:5
¡1:5 ¡2:5 ¡1:5 2:5 1:5 2:5 ¡1:5 ¡2:5 ¡1:5 2:5 1:5 2:5
3
7 7 :7 7 5
38
Chapter 7 Solutions (Students) Similarly, the level 1 prediction residual is obtained by upsampling the level 0 approximation and subtracting it from the level 1 approximation to yield ' # ' # ' # 3:5 5:5 8:5 8:5 ¡5 ¡3 ¡ = : 11:5 13:5 8:5 8:5 3 5 The mean prediction residual pyramid is therefore 2 3 ¡2:5 ¡1:5 ¡2:5 ¡1:5 ' # 6 7 6 1:5 2:5 1:5 2:5 7 6 7 ¡5 ¡3 [8:5] : 6 ¡2:5 ¡1:5 ¡2:5 ¡1:5 7 3 5 4 5 1:5 2:5 1:5 2:5
Problem 7.3 The number of elements in a J + 1 level pyramid is bounded by 4/3 (see Section 7.1.1): ' # 1 1 1 4 2J 2 1+ + + ¢¢¢ + · 22J J 3 (4)1 (4)2 (4) for J > 0. We can generate the following table: Table P7.3 J
Pyramid Elements
Compression Ratio
0 1 2 3 . . 1
1 5 21 85
1 5=4 = 1:25 21=16 = 1:3125 85=86 = 1:328 4=3 = 1:33
All but the trivial case (J = 0) are expansions. The expansion factor is a function of and bounded by 4/3 or 1.33.
Problem 7.4 (a) The QMF ®lters must satisfy Eqs. (7.1-9) and (7.1-10). From Table 7.1, G0 (z) = H0 (z) and H1 (z) = H0 (¡z), so H1 (¡z) = H0 (z). Thus, beginning with Eq. (7.1-9), H0 (¡z)G0 (z) + H1 (¡z)G1 (z) = 0 H0 (¡z)H0 (z) ¡ H0 (z)H0 (¡z) = 0 0 = 0:
Problem 7.10
39
Similarly, beginning with Eq. (7.1-10) and substituting for H1 (z), G0 (z), and G1 (z) from rows 2, 3, and 4 of Table 7.1, we get H0 (z)G0 (z) + H1 (z)G1 (z) = 2 H0 (z)H0 (z) + H0 (¡z)[¡H0 (¡z)] = 2 H02 (z) ¡ H02 (¡z) = 2
which is the design equation for the H0 (z) prototype ®lter in row 1 of the table. PROBLEM 7.7 Reconstruction is performed by reversing the decomposition processu that is, by replacing the downsamplers with upsamplers and the analysis ®lters by their synthesis ®lter counterparts, as shown in Fig. P7.7.
Figure P7.7
Problem 7.10 (a) The basis is orthonormal and the coef®cients are computed by the vector equivalent
40
Chapter 7 Solutions (Students) of Eq. (7.2-5): ®0
h
=
p 5 2 = 2 h p1 = 2
®1
p
p p 5 2 2 '0 + ' 2 2 1
p1 2
¡ p12
2 2
= so,
p1 2
i
p ' 5 2 = 2 ' # 3 = : 2
p1 2 p1 2
'
i
3 2
#
'
3 2
#
#
p ' 1 # p 2 2 + 2 ¡ p12
Problem 7.13 From Eq. (7.2-19) we ®nd that à 3;3 (x) = 23=2 Ã(23 x ¡ 3) p = 2 2Ã(8x ¡ 3) and using the Haar wavelet function de®nition from Eq. (7.2-30), obtain the plot shown in Fig. P7.13. To express à 3;3 (x) as a function of scaling functions, we employ Eq. (7.2-28) and the p Haar wavelet vector de®ned in Example 7.6xthat is, hà (0) = 1= 2 and hà (1) = p ¡1= 2. Thus we get X p Ã(x) = hà (n) 2'(2x ¡ n) n
so that
Ã(8x ¡ 3) =
X n
p hà (n) 2'(2[8x ¡ 3] ¡ n)
µ ¶ 1 p ¡1 p p 2'(16x ¡ 6) + p 2'(16x ¡ 7) 2 2 = '(16x ¡ 6) ¡ '(16x ¡ 7): =
p Then, since à 3;3 = 2 2Ã(8x ¡ 3),
Problem 7.17 Ã 3;3
41
p = 2 2Ã(8x ¡ 3) p p = 2 2'(16x ¡ 6) ¡ 2 2'(16x ¡ 7):
Figure P7.13
Problem 7.17 Intuitively, the continuous wavelet transform (CWT) calculates a resemblance index} between the signal and the wavelet at various scales and translations. When the index is large, the resemblance is strongu else it is weak. Thus, if a function is similar to itself at different scales, the resemblance index will be similar at different scales. The CWT coef®cient values (the index) will have a characteristic pattern. As a result, we can say that the function whose CWT is shown is self-similarxlike a fractal signal.
Problem 7.18 (b) The DWT is a better choice when we need a space saving representation that is suf®cient for reconstruction of the original function or image. The CWT is often easier to interpret because the built-in redundancy tends to reinforce traits of the function or image. For example, see the self-similarity of Problem 7.18.
Problem 7.19 The ®lter bank is the ®rst bank in Fig. (7.17), as shown in Fig. P7.19:
42
Chapter 7 Solutions (Students)
Figure P7.19
PROBLEM 7.21 (a) Input '(n) = f1; 1; 1; 1; 1; 1; 1; 1g = '0;0 (n) for a three-scale wavelet transform with Haar scaling and wavelet functions. Since wavelet transform coef®cients measure the similarity of the input to the basis functions, the resulting transform is fW' (0; 0); WÃ (0; 0); WÃ (1; 0); WÃ (1; 1); WÃ (2; 0); WÃ (2; 1); WÃ (2; 2) p WÃ (2; 3)g = f2 2; 0; 0; 0; 0; 0; 0; 0g The W' (0; 0) term can be computed using Eq. (7.3-5) with j0 = k = 0. PROBLEM 7.22 They are both multi-resolution representations that employ a single reduced-resolution approximation image and a series of difference} images. For the FWT, these difference} images are the transform detail coef®cientsu for the pyramid, they are the prediction residuals. To construct the approximation pyramid that corresponds to the transform in Fig. 7.8(a), we will use the F W T ¡1 2-d synthesis bank of Fig. 7.22(c). First, place the 64 £ 64 approximation coef®cients} from Fig. 7.8(a) at the top of the pyramid being constructed. Then use it, along with 64 £ 64 horizontal, vertical, and diagonal detail coef®cients from the upper-left of Fig. 7.8(a), to drive the ®lter bank inputs in Fig. 7.22(c). The output will be a 128 £ 128 approximation of the original image and should be used as the next level of the approximation pyramid. The 128 £ 128 approximation is then used with the three 128 £ 128 detail coef®cient images in the upper 1/4 of the transform in Fig. 7.8(a) to drive the synthesis ®lter bank in Fig. 7.22(c) a second timexproducing a 256 £ 256 approximation that is placed as the next level of the approximation pyramid. This process is then repeated a third time to recover the 512 £ 512 original image, which is placed at the bottom of the approximation pyramid. Thus, the approximation pyramid would have 4 levels. PROBLEM 7.24
As can be seen in the sequence of images that are shown, the DWT
Problem 7.17
43
is not shift invariant. If the input is shifted, the transform changes. Since all original images in the problem are 128 £ 128, they become the W' (7; m; n) inputs for the FWT computation process. The ®lter bank of Fig. 7.22(a) can be used with j + 1 = 7. For a single scale transform, transform coef®cients W' (6; m; n) and WÃi (6; m; n) for i = H; V; D are generated. With Haar wavelets, the transformation process subdivides the image into non-overlapping 2 £ 2 blocks and computes 2-point averages and differences (per the scaling and wavelet vectors). Thus, there are no horizontal, vertical, or diagonal detail coef®cients in the ®rst two transforms shownu the input images are constant in all 2 £ 2 blocks (so all differences are 0). If the original image is shifted by 1 pixel, detail coef®cients are generated since there are then 2 £ 2 areas that are not constant. This is the case in the third transform shown.
8
Solutions (Students)
Problem 8.3 Table P8.3 shows the data, its 6-bit code, the IGS sum for each step, the actual IGS 3-bit code and its equivalent decoded value, the error between the decoded IGS value and the input values, and the squared error. Table P8.3 Data
6-bit Code
Sum
IGS Code
Decoded IGS
Error
Sq. Error
12 12 13 13 10 13 57 54
001100 001100 001101 001101 001010 001101 111001 110110
000000 001100 010000 001101 010010 001100 010001 111001 110111
001 010 001 010 001 010 111 110
8 16 8 16 8 16 56 48
4 -4 5 -3 2 -3 1 6
16 16 25 9 4 9 1 36
Problem 8.5 (b) For 1100111, construct the following three bit odd parity word: c1 = h1 © h3 © h5 © h7 = 1 © 0 © 1 © 1 = 1 c2 = h2 © h3 © h6 © h7 = 1 © 0 © 1 © 1 = 1 c4 = h4 © h5 © h6 © h7 = 0 © 1 © 1 © 1 = 1 A parity word of 1112 indicates that bit 7 is in error. The correctly decoded binary value is 01102 . In a similar manner, the parity words for 1100110 and 1100010 are 000 and 101, respectively. The decoded values are identical and are 0110.
46
Chapter 8 Solutions (Students)
Problem 8.6 The conversion factors are computed using the logarithmic relationship 1 loga x = logb x logb a Thus, 1 Hartley = 3.3219 bits and 1 nat = 1.4427 bits.
Problem 8.7 Let the set of source symbols be fa1 ; a2 ; :::; aq g and have probabilities z = [P (a1 ) ; P (a2 ) ; :::; P (aq )]T :
Then, using Eq. (8.3-3) and the fact that the sum of all P (ai ) is 1, we get q q X X log q ¡ H (z) = P (ai ) log q + P (ai ) log P (ai ) =
i=1
i=1
q X
P (ai ) log qP (ai )
i=1
Using the log relationship from Problem 8.6, this becomes q X = log e P (ai ) ln qP (ai ) i=1
Then, multiplying the inequality ln x · x ¡ 1 by -1 to get ln 1=x ¸ 1 ¡ x and applying it to this last result, ¸ · q X 1 log q ¡ H (z) ¸ log e P (ai ) 1 ¡ qP (ai ) i=1 # ' q q X 1 X P (ai ) ¸ log e P (ai ) ¡ q i=1 P (ai ) i=1 ¸ log e [1 ¡ 1]
¸ 0 so that log q ¸ H (z) Thus, H (z) is always less than, or equal to, log q. Furthermore, in view of the equality condition (x = 1) for ln 1=x ¸ 1 ¡ x, which was introduced at only one point in the above derivation, we will have strict equality if and only if P (ai ) = 1=q for all i.
Problem 8.6
47
Problem 8.9 (a) Substituting the given values of pbs and pe into the binary entropy function derived in the example, the average information or entropy of the source is 0.811 bits/symbol. (b) The equivocation or average entropy of the source given that the output has been observed (using Eq. 8.3-9) is 0.75 bits/symbol. Thus, the decrease in uncertainty is 0.061 bits/symbol. (c) It is the mutual information I(z; v) of the system and is less than the capacity of the channel, which is, in accordance with the equation derived in the example, 0.0817 bits/symbol.
Problem 8.10 (b) Substituting 0.5 into the above equation, the capacity of the erasure channel is 0.5. Substituting 0.125 into the equation for the capacity of a BSC given in Section 8.3.2, we ®nd that its capacity is 0.456. Thus, the binary erasure channel with a higher probability of error has a larger capacity to transfer information.
Problem 8.11 (a) The plot is shown in Fig. P8.11.
48
Chapter 8 Solutions (Students) Figure P8.11
Problem 8.14 The arithmetic decoding process is the reverse of the encoding procedure. Start by dividing the [0, 1) interval according to the symbol probabilities. This is shown in Table P8.14. Table P8.14 Symbol Probability Range a e i o u !
0.2 0.3 0.1 0.2 0.1 0.1
[0.0, 0.2) [0.2, 0.5) [0.5, 0.6) [0.6, 0.8) [0.8, 0.9) [0.9, 1.0)
The decoder immediately knows the message 0.23355 begins with an e}, since the coded message lies in the interval [0.2, 0.5). This makes it clear that the second symbol is an a}, which narrows the interval to [0.2, 0.26). To further see this, divide the interval [0.2, 0.5) according to the symbol probabilities. Proceeding like this, which is the same procedure used to code the message, we get eaii!}.
Problem 8.16 The input to the LZW decoding algorithm for the example in Example 8.12 is 39 39 126 126 256 258 260 259 257 126 The starting dictionary, to be consistent with the coding itself, contains 512 locationsw with the ®rst 256 corresponding to gray level values 0 through 255. The decoding algorithm begins by getting the ®rst encoded value, outputting the corresponding value from the dictionary, and setting the }recognized sequence} to the ®rst value. For each additional encoded value, we (1) output the dictionary entry for the pixel value(s), (2) add a new dictionary entry whose content is the }recognized sequence} plus the ®rst element of the encoded value being processed, and (3) set the }recognized sequence} to the encoded value being processed. For the encoded output in Example 8.12, the sequence of operations is as shown in Table P8.16. Note, for example, in row 5 of the table that the new dictionary entry for location 259
Problem 8.19
49
is 126-39, the concatenation of the currently recognized sequence, 126, and the ®rst element of the encoded value being processedwthe 39 from the 39-39 entry in dictionary location 256. The output is then read from the third column of the table to yield 39 39 126 126 39 39 126 126 39 39 126 126 39 39 126 126 where it is assumed that the decoder knows or is given the size of the image that was recieved. Note that the dictionary is generated as the decoding is carried out.
Table P8.16 Recognized
Encoded Value
Pixels
Dict. Address
Dict. Entry
39 39 126 126 256 258 260 259 257
39 39 126 126 256 258 260 259 257 126
39 39 126 126 39-39 126-126 39-39-126 126-39 39-126 126
256 257 258 259 260 261 262 263 264
39-39 39-126 126-126 126-39 39-39-126 126-126-39 39-39-126-126 126-39-39 39-126-126
Problem 8.19 (a) The motivation is clear from Fig. 8.17. The transition at c must somehow be tied to a particular transition on the previous line. Note that there is a closer white to black transition on the previous line to the right of c, but how would the decoder know to use it instead of the one to the left. Both are less than ec. The ®rst similar transition past e establishes the convention to make this decision.
Problem 8.21 The derivation proceeds by substituting the uniform probability function into Eqs. (8.520) - (8.5-22) and solving the resulting simultaneous equations with L = 4. Eq. (8.5-21)
50
Chapter 8 Solutions (Students) yields s0 = 0 s1 = 21 (t1 + t2 ) s2 = 1 Substituting these values into the integrals de®ned by Eq. (8.5-20), we get two equations. The ®rst is (assuming s1 · A) Z s1 (s ¡ t1 ) p (s) ds = 0 s0 ¯ Z 21 (t1 +t2 ) ¯ 1 (t + t ) s2 1 ¯ 1 2 (s ¡ t1 ) ds = ¡ t1 s ¯ 2 =0 ¯ 0 2A 0 2
(t1 + t2 )2 ¡ 4t1 (t1 + t2 ) = 0 (t1 + t2 ) (t2 ¡ 3t1 ) = 0 t1 = ¡t2 and t2 = 3t1 The ®rst of these relations does not make sense since both t1 and t2 must be positive. The second relationship is a valid one. The second integral yields (noting that s1 is less than A so the integral from A to 1 is 0 by the de®nition of p(s)) ¯ Z A ¯ A s2 1 ¯ ¡ t2 s ¯ 1 =0 (s ¡ t2 ) ds = ¯ 2 (t1 + t2 ) 2A 12 (t1 +t2 ) 2
4A2 ¡ 8At2 ¡ (t1 + t2 )2 ¡ 4t2 (t1 + t2 ) = 0 Substituting t2 = 3t1 from the ®rst integral simpli®cation into this result, we get 8t21 ¡ 6At1 + A2 = 0 £ ¤ t1 ¡ A2 (8t1 ¡ 2A) = 0 t1 = A2 and t1 = A4 Back substituting these values of t1 , we ®nd the corresponding t2 and s1 values:
A t2 = 3A 2 and s1 = A for t1 = 2 3A A t2 = 4 and s1 = 2 for t1 = A4 Since s1 = A is not a real solution (the second integral equation would then be evaluated from A to A, yielding 0 or no equation), the solution is given by the second. That is,
s0 = 0 t1 = A4
s1 = A2 t2 = 3A 4
s2 = 1
Problem 8.23 (a) - (b) Following the procedure outlined in Section 8.6.2, we obtain the results shown
Problem 8.27 in Table P8.23. Table P8.23 DC Coef®cient Difference
Twozs Complement Value
Code
-7 -6 -5 -4 4 5 6 7
1..1001 1..1010 1..1011 1..1100 0..0100 0..0101 0..0110 0..0111
00000 00001 00010 00011 00100 00101 00110 00111
Problem 8.27 The appropriate MPEG decoder is shown in Fig. P8.27
Figure P8.27
51
9
Solutions (Students)
Problem 9.2 (a) The answer is shown shaded in Fig. P9.2.
Figure P9.2
Problem 9.3 (a) With reference to the discussion in Section 2.5.2, m-connectivity is used to avoid multiple paths that are inherent in 8-connectivity. In one-pixel-thick, fully connected boundaries, these multiple paths manifest themselves in the four basic patterns shown in Fig. P9.3. The solution to the problem is to use the hit-or-miss transform to detect the patterns and then to change the center pixel to 0, thus eliminating the multiple paths. A
54
Chapter 9 Solutions (Students) basic sequence of morphological steps to accomplish this is as follows: X1
= A ~ B1
Y1
= A X1c
X2
= Y1 ~ B2
Y2
= Y1 X2c
X3
= Y2 ~ B3
Y3
= Y2 X3c
X4
= Y3 ~ B4
Y4
= Y3 X4c
where A is the input image.
Figure P9.3
Problem 9.5 (a) Erosion is set intersection. The intersection of two convex sets is convex also. See Fig. P9.5 the for solution to part (b). Keep in mind that the digital sets in question are the larger black dots. The lines are shown for convenience in visualizing what the continuous sets would be. In (b) the result of dilation is not convex because the center point is not in the set.
Problem 9.6 Refer to Fig. P9.6. The center of each structuring element is shown as a black dot. Solution (a) was obtained by eroding the original set (shown dashed) with the structuring element shown (note that the origin is at the bottom, right). Solution (b) was obtained by eroding the original set with the tall rectangular structuring element shown. Solution (c) was obtained by ®rst eroding the image shown down to two vertical lines using the rectangular structuring elementu this result was then dilated with the circular structuring
Problem 9.8
55
element. Solution (d) was obtained by ®rst dilating the original set with the large disk shown. Then dilated image was then eroded with a disk of half the diameter of the disk used for dilation.
Figure P9.5
Problem 9.8 (a) The dilated image will grow without bound. (b) A one-element set (i.e., a one-pixel image).
Problem 9.10 The approach is to prove that ¯ n o © ª ¯ ^ x 2 Z 2 ¯(B) A = 6 ; ´ x 2 Z 2 j x = a + b for a 2 A and b 2 B: x
^ x are of the form x ¡ b for b 2 B. The condition (B) ^ x A 6= ; The elements of (B) implies that for some b 2 B, x ¡ b 2 A, or x ¡ b = a for some a 2 A (note in the preceding equation that x = a + b). Conversely, if x = a + b for some a 2 A and b 2 B, ^ x A 6= ;. then x ¡ b = a or x ¡ b 2 A, which implies that (B)
Problem 9.12 The proof, which consists of proving that © ª © ª x 2 Z 2 j x + b 2 A , for every b 2 B ´ x 2 Z 2 j (B)x µ A ,
follows directly from the de®nition of translation because the set (B)x has elements of the form x + b for b 2 B. That is, x + b 2 A for every b 2 B implies that (B)x µ A. Conversely, (B)x µ A implies that all elements of (B)x are contained in A, or x+b 2 A for every b 2 B.
56
Chapter 9 Solutions (Students)
Figure P9.6
Problem 9.14 Starting with the de®nition of closing, (A ² B)c
= [(A © B) Ä B]c
^ = (A © B)c © B
^ ©B ^ = (Ac Ä B) ^ = Ac ± B:
Problem 9.15 (a) Erosion of a set A by B is de®ned as the set of all values of translates, z, of B such that (B)z is contained in A. If the origin of B is contained in B, then the set of points describing the erosion is simply all the possible locations of the origin of B such that (B)z is contained in A. Then it follows from this interpretation (and the de®nition of erosion) that erosion of A by B is a subset of A. Similarly, dilation of a set C by B is ^ such that the intersection of C and (B) ^ z is not the set of all locations of the origin of B empty. If the origin of B is contained in B, this implies that C is a subset of the dilation of C by B. Now, from Eq. (9.3-1), we know that A ± B = (A Ä B) © B. Let C denote the erosion of A by B. It was already established that C is a subset of A. From the
Problem 9.18
57
preceding discussion, we know also that C is a subset of the dilation of C by B. But C is a subset of A, so the opening of A by B (the erosion of A by B followed by a dilation of the result) is a subset of A.
Problem 9.18 It was possible to reconstruct the three large squares to their original size because they were not completely eroded and the geometry of the objects and structuring element was the same (i.e., they were squares). This also would have been true if the objects and structuring elements were rectangular. However, a complete reconstruction, for instance, by dilating a rectangle that was partially eroded by a circle, would not be possible.
Problem 9.20 The key difference between the Lake and the other two features is that the former forms a closed contour. Assuming that the shapes are processed one at a time, basic two-step approach for differentiating between the three shapes is as follows: Step 1. Apply an end-point detector to the object until convergence is achieved. If the result is not the empty set, the object is a Lake. Otherwise it is a Bay or a Line. Step 2. There are numerous ways to differentiate between a lake and a line. One of the simplest is to determine a line joining the two end points of the object. If the AND of the object and this line contains only two points, the ®gure is a Bay. Otherwise it is a line segment. There are pathological cases in which this test will fail, and additional }intelligence} needs to be built into the process, but these pathological cases become less probable with increasing resolution of the thinned ®gures.
Problem 9.22 (a) With reference to the example shown in Fig. P9.22(a), the boundary that results from using the structuring element in Fig. 9.15(c) generally forms an 8-connected path (leftmost ®gure), whereas the boundary resulting from the structuring element in Fig. 9.13(b) forms a 4-connected path (rightmost ®gure).
58
Chapter 9 Solutions (Students) (b) Using a 3 £ 3 structuring element of all 1zs would introduce corner pixels into segments characterized by diagonally-connected pixels. For example, square (2,2) in Fig. 9.15(e) would be a 1 instead of a 0. That value of 1 would carry all the way to the ®nal result in Fig. 9.15(i). There would be other 1zs introduced that would turn Fig. 9.15(i) into a much more distorted object.
Figure P9.22(a)
PROBLEM 9.24 Denote the original image by A. Create an image of the same size as the original, but consisting of all 0zs, call it B. Choose an arbitrary point labeled 1 in A, call it p1 , and apply the algorithm. When the algorithm converges, a connected component has been detected. Label and copy into B the set of all points in A belonging to the connected components just found, set those points to 0 in A and call the modi®ed image A1 . Choose an arbitrary point labeled 1 in A1 , call it p2 , and repeat the procedure just given. If there are K connected components in the original image, this procedure will result in an image consisting of all 0zs after K applications of the procedure just given. Image B will contain K labeled connected components.
Problem 9.25 (a) Equation (9.6-1) requires that the (x; y) used in the computation of dilation must satisfy the condition (x; y) 2 Db . In terms of the intervals given in the problem statement, this means that x and y must be in the closed interval x 2 [Bx1 ; Bx2 ] and
Problem 9.26
59
y 2 [By1 ; By2 ]. It is required also that (s ¡ x); (t ¡ y) 2 Df , which means that (s ¡ x) 2 [Fx1 ; Fx2 ] and (t ¡ y) 2 [Fy1 ; Fy2 ]. Since the valid range of x is the interval [Bx1 ; Bx2 ], the valid range of (s¡x) is [s¡Bx1 ; s¡Bx2 ]. But, since x must also satisfy the condition (s ¡ x) 2 [Fx1 ; Fx2 ], it follows that Fx1 · s ¡ Bx1 and Fx2 ¸ s ¡ Bx2 , which ®nally yields Fx1 + Bx1 · s · Fx2 + Bx2 . Following the same analysis for t yields Fy1 + By1 · t · Fy2 + By2 . Since dilation is a function of (s; t), these two inequalities establish the domain of (f © b)(s; t) in the st-plane.
Problem 9.26 (a) The noise spikes are of the general form shown in Fig. P9.26(a), with other possibilities in between. The amplitude is irrelevant in this caseu only the shape of the noise spikes is of interest. To remove these spikes we perform an opening with a cylindrical structuring element of radius greater than Rmax , as shown in Fig. P9.26(b) (see Fig. 9.30 for an explanation of the process). Note that the shape of the structuring element is matched to the known shape of the noise spikes.
Figure P9.26
Problem 9.27 (a) Color the image border pixels the same color as the particles (white). Call the resulting set of border pixels B. Apply the connected component algorithm. All connected components that contain elements from B are particles that have merged with the border of the image.
10
Solutions (Students)
Problem 10.1 The masks would have the coef®cients shown in Fig. P10.1. Each mask would yield a value of 0 when centered on a pixel of an unbroken 3-pixel segment oriented in the direction favored by that mask. Conversely, the response would be a +2 when a mask is centered on a one-pixel gap in a 3-pixel segment oriented in the direction favored by that mask.
Figure P10.1
Problem 10.3 (a) The lines were thicker than the width of the line detector masks. Thus, when, for example, a mask was centered on the line it }saw} a constant area and gave a response of 0.
Problem 10.5 The gradient and Laplacian (®rst and second derivatives) are shown in Fig. P10.5.
62
Chapter 10 Solutions (Students)
Figure P10.5
Problem 10.7 Consider ®rst the Sobel masks of Figs. 10.8 and 10.9. The easiest way to prove that these masks give isotropic results for edge segments oriented at multiples of 45± is to obtain the mask responses for the four general edge segments shown in Fig. P10.7, which are oriented at increments of 45± . The objective is to show that the responses of the Sobel masks are indistinguishable for these four edges. That this is the case is evident from Table P10.1, which shows the response of each Sobel mask to the four general edge segments. We see that in each case the response of the mask that matches the edge direction is (4a ¡ 4b), and the response of the corresponding orthogonal mask is 0. The response of the remaining two masks is either (3a ¡ 3b) or (3b ¡ 3a). The sign difference is not signi®cant because the gradient is computed by either squaring or taking the absolute value of the mask responses. The same line of reasoning applies to the Prewitt masks.
Problem 10.9 Table P10.7 Edge direction
Horizontal Sobel (Gx )
Vertical Sobel (Gy )
+45± Sobel (G45 )
Horizontal Vertical +45± ¡45±
4a ¡ 4b 0 3a ¡ 3b 3b ¡ 3a
0 4a ¡ 4b 3a ¡ 3b 3a ¡ 3b
3a ¡ 3b 3a ¡ 3b 4a ¡ 4b 0
¡45± Sobel (G¡45 ) 3b ¡ 3a 3a ¡ 3b 0 4a ¡ 4b
Figure P10.7
Problem 10.9 The solution is as follows (negative numbers are shown underlined): Edge direction E
NE
N
NW
W
SW
S
SE
SE
E
NE
Gradient direction N
NW
W
SW
S
Compass gradient operators 111
110
101
011
111
1 10
101
011
000
101
101
101
000
101
101
101
111
011
101
110
111
011
101
110
Problem 10.11 (a) With reference to Eq. (10.1-17), we need to prove that ¸ Z1 · 2 r ¡ ¾2 ¡ r22 e 2¾ dr = 0: ¾4 ¡1
63
64
Chapter 10 Solutions (Students) Expanding this equation results in the expression ¸ Z1 · 2 Z1 r2 1 r ¡ ¾2 ¡ r22 e 2¾ dr = r2 e¡ 2¾2 dr 4 4 ¾ ¾ ¡1
¡1
1 ¡ 2 ¾
Z1
r2
e¡ 2¾2 dr:
¡1
Recall from the de®nition of the Gaussian density that Z1 r2 1 p e¡ 2¾2 dr = 1 2 2¼¾ ¡1
and, from the de®nition of the variance of a Gaussian random variable that Z1 r2 r2 e¡ 2¾2 dr: Var(r) = ¾ 2 = ¡1
Thus, it follows from the preceding equations that p p ¸ Z1 · 2 r ¡ ¾2 ¡ r22 2¼¾2 2 2¼¾2 e 2¾ dr = ¾ ¡ = 0: 4 4 ¾ ¾ ¾2 ¡1
Problem 10.13 (a) Point 1 has coordinates x = 0 and y = 0. Substituting into Eq. (10.2-3) yields ½ = 0, which, in a plot of ½ vs. µ,is a straight line. (b) Only the origin (0; 0) would yield this result. (c) At µ = +90± , it follows from Eq. (10.2-3) that x ¢ (0) + y ¢ (1) = ½, or y = ½. At µ = ¡ 90± , x ¢ (0) + y ¢ (¡1) = ½, or ¡y = ½. Thus the re-ective adjacency.
Problem 10.16 (a) The paths are shown in Fig. P10.16. These paths are as follows: 1 : (1; 1)(1; 2) ! (2; 1)(2; 2) ! (3; 1)(3; 2) 2 : (1; 1)(1; 2) ! (2; 1)(2; 2) ! (3; 2)(2; 2) ! (3; 2)(3; 3)
Problem 10.18
65
3 : (1; 1)(1; 2) ! (2; 2)(1; 2) ! (2; 2)(2; 3) ! (3; 2)(3; 3) 4 : (1; 1)(1; 2) ! (2; 2)(1; 2) ! (2; 2)(2; 3) ! (2; 2)(3; 2) ! (3; 1)(3; 2) 5 : (1; 2)(1; 3) ! (2; 2)(2; 3) ! (3; 2)(3; 3) 6 : (1; 2)(1; 3) ! (2; 2)(2; 3) ! (2; 2)(3; 2) ! (3; 1)(3; 2) 7 : (1; 2)(1; 3) ! (1; 2)(2; 2) ! (2; 1)(2; 2) ! (3; 1)(3; 2) 8 : (1; 2)(1; 3) ! (1; 2)(2; 2) ! (2; 1)(2; 2) ! (3; 2)(2; 2) ! (3; 2)(3; 3) (b) From Fig. 10.24 and (a), we see that the optimum path is path 6. Its cost is c = 2 + 0 + 1 + 1 = 4.
Figure P10.16
Problem 10.18 (a) The number of boundary points between black and white regions is much larger in the image on the right. When the images are blurred, the boundary points will give rise to a larger number of different values for the image on the right, so the histograms of the two blurred images will be different. (b) To handle border effects, we surround the image with a border of 0zs. We assume that the image is of size N £ N (the fact that the image is square is evident from the right image in the problem statement). Blurring is implemented by a 3 £ 3 mask whose coef®cients are 1=9. Figure P10.18 shows the different types of values that the blurred left image (see problem statement) will have. These values are summarized in Table P10.18-1. It is easily veri®ed that the sum of the numbers on the left column of the table is N 2 .
66
Chapter 10 Solutions (Students) Table P10.18-1 No. of Points ¡ ¢ N N2 ¡ 1 2 N ¡2 4 3N ¡ 8 ¡ ¢ (N ¡ 2) N2 ¡ 2
Value 0 2=9 3=9 4=9 6=9 1
A histogram is easily constructed from the entries in this table. A similar (tedious, but not dif®cult) procedure yields the results shown in Table P10.18-2 for the checkerboard image. Table P10.18-2 No. of Points N2 2
¡ 14N + 98 28 14N ¡ 224 128 98 16N ¡ 256 N2 2 ¡ 16N + 128
Value 0 2=9 3=9 4=9 5=9 6=9 1
Figure P10.18
Problem 10.20 (a) A1 = A2 and ¾ 1 = ¾2 = ¾, which makes the two modes identical. If the number of samples is not large, convergence to a value at or near the mid point between the two
Problem 10.22
67
means also requires that a clear valley exist between the two modes. We can guarantee this by assuming that ¾ > A2 and ¾ 1 >> ¾2 ) the average value of the region to the left of the starting threshold will be smaller than the average of the region to the right because the modes are symmetrical about their mean, and the mode associated with m2 will bias the data to the right. Thus, the next iterative step will bring the value of the threshold closer to m1 , and eventually to the right of it. This analysis assumes that enough points are available in order to avoid pathological cases in which the algorithm can get }stuck} due to insuf®cient data that truly represents the shapes assumed in the problem statement.
Problem 10.22 From the ®gure in the problem statement, 8 > z : 0 z>3 and 8 > z : 0 z>2 The optimum threshold is the value z = T for which P1 p1 (T ) = P2 p2 (T ). In this case P1 = P2 , so 1 1 1 T ¡ = ¡ T +1 2 2 2 from which we get T = 1:5.
Problem 10.24 From Eq. (10.3-10), P1 p1 (T ) = P2 p2 (T ): Taking the ln of both sides yields ln P1 + ln p1 (T ) = ln P2 + ln p2 (T ):
68
Chapter 10 Solutions (Students) But
2
(T ¡¹1 ) ¡ 1 2¾ 2 1 p1 (T ) = p e 2¼¾ 1
and
2
so it follows that
(T ¡¹2 ) ¡ 1 2¾ 2 2 p2 (T ) = p e 2¼¾ 2
(T ¡ ¹1 )2 (T ¡ ¹2 )2 1 1 p ¡ ¡ = ln P + ln 2 2¾21 2¾22 2¼¾1 2¼¾2 2 2 (T ¡ ¹2 ) (T ¡ ¹1 ) ¡ ln P 2 + ln ¾ 2 + =0 ln P1 ¡ ln ¾1 ¡ 2¾ 21 2¾22 P1 1 ¾1 1 ln (T 2 ¡ 2¹1 T + ¹21 ) + 2 (T 2 ¡ 2¹2 T + ¹22 ) = 0 + ln ¡ P2 ¾2 µ 2¾21 2¾ 2 ¶ µ ¶ µ 2 ¶ 1 1 ¹2 ¹21 ¾ 2 P1 ¹1 ¹2 2 +T ¡ 2 +T ¡ + ¡ = 0: ln ¾ 1 P2 2¾22 2¾ 1 ¾21 ¾ 22 2¾22 2¾21 From this expression we get ln P1 + ln p
AT 2 + BT + C = 0 with A = (¾21 ¡ ¾22 ) B
= 2(¾22 ¹1 ¡ ¾21 ¹2 )
and C = ¾21 ¹22 ¡ ¾ 22 ¹21 + 2¾21 ¾22 ln
¾ 2 P1 : ¾ 1 P2
Problem 10.26 The simplest solution is to use the given means and standard deviations to form two Gaussian probability density functions, and then to use the optimum thresholding approach discussed in Section 10.3.5 (in particular, see Eqs. (10.3-11) through (10.3-13). The probabilities P1 and P2 can be estimated by visual analysis of the images (i.e., by determining the relative areas of the image occupied by objects and background). It is clear by looking at the image that the probability of occurrence of object points is less than that of background points. Alternatively, an automatic estimate can be obtained by thresholding the image into points with values greater than 200 and less than 110 (see problem statement). Using the given parameters, the results would be good estimates of the relative probability of occurrence of object and background points due to the separation between means, and the relatively tight standard deviations. A more sophisticated approach is to use the Chow-Kaneko procedure discussed in Section 10.3.5.
Problem 10.26
69
Problem 10.29 (a) The elements of T [n] are the coordinates of points in the image below the plane g(x; y) = n, where n is an integer that represents a given step in the execution of the algorithm. Since n never decreases, the set of elements in T [n ¡ 1] is a subset of the elements in T [n]. In addition, we note that all the points below the plane g(x; y) = n ¡ 1 are also below the plane g(x; y) = n, so the elements of T [n] are never replaced. Similarly, Cn (Mi ) is formed by the intersection of C(Mi ) and T [n], where C(Mi ) (whose elements never change) is the set of coordinates of all points in the catchment basin associated with regional minimum Mi . Since the elements of C(Mi ) never change, and the elements of T [n] are never replaced, it follows that the elements in Cn (Mi ) are never replaced either. In addition, we see that Cn¡1 (Mi ) µ Cn (Mi ):
Problem 10.31 The ®rst step in the application of the watershed segmentation algorithm is to build a dam of height max + 1 to prevent the rising water from running off the ends of the function, as shown in Fig. P10.31(b). For an image function we would build a box of height max + 1 around its border. The algorithm is initialized by setting C[1] = T [1]. In this case, T [1] = fg(2)g, as shown in Fig. P10.31(c) (note the water level). There is only one connected component in this case: Q[1] = fq1 g = fg(2)g: Next, we let n = 2 and, as shown in Fig. P10.31(d), T [2] = fg(2); g(14)g and Q[2] = fq1 ; q2 g, where, for clarity, different connected components are separated by semicolons. We start construction of C[2] by considering each connected component in Q[2]. When q = q1 , the term q C[1] is equal to fg(2)g, so condition 2 is satis®ed and, therefore, C[2] = fg(2)g. When q = q2 , q C[1] = ; (the empty set) so condition 1 is satis®ed and we incorporate q in C[2], which then becomes C[2] = fg(2); g(14)g where, as above, different connected components are separated by semicolons. When n = 3 [Fig. P10.31(e)], T [3] = f2; 3; 10; 11; 13; 14g and Q[3] = fq1 ; q2 ; q3 g =
f2; 3; 10; 11; 13; 14g where, in order to simplify the notation we let k denote g(k). Proceeding as above, q1 C[2] = f2g satis®es condition 2, so q1 is incorporated into the new set to yield C[3] = f2; 3; 14g. Similarly, q2 C[2] = ; satis®es condition 1 and C[3] = f2; 3; 10; 11; 14g. Finally, q3 C[2] = f14g satis®es condition 2 and C[3] = f2; 3; 10; 11; 13; 14g. It is easily veri®ed that C[4] = C[3] = f2; 3; 10; 11; 13; 14g.
70
Chapter 10 Solutions (Students)
Figure P10.31 When n = 5 [Fig. P10.31(f)], we have, T [5] = f2; 3; 5; 6; 10; 11; 12; 13; 14g and Q[5] = fq1 ; q2 ; q3 g = f2; 3; 5; 6; 10; 11; 12; 13; 14g (note the merging of two previously
Problem 10.29
71
distinct connected components). Is is easily veri®ed that q1 C[4] satis®es condition 2 and that q2 C[4] satis®ed condition 1. Proceeding with these two connected components exactly as above yields C[5] = f2; 3; 5; 6; 10; 11; 13; 14g up to this point. Things get more interesting when we consider q3 . Now, q3 C[4] = f10; 11; 13; 14g which, since it contains two connected components of C[4] satis®es condition 3. As mentioned previously, this is an indication that water from two different basins has merged and a dam must be built to prevent this. Dam building is nothing more than separating q3 into the two original connected components. In this particular case, this is accomplished by the dam shown in Fig. P10.31(g), so that now q3 = fq31 ; q32 g = f10; 11; 13; 14g. Then, q31 C[4] and q32 C[4] each satisfy condition 2 and we have the ®nal result for n = 5, C[5] = f2; 3; 5; 6; 10; 11; 13; 14g. Continuing in the manner just explained yields the ®nal segmentation result shown in Fig. P10.31(h), where the }edges} are visible (from the top) just above the water line. A ®nal post-processing step would remove the outer dam walls to yield the inner edges of interest.
11
Solutions (Students)
Problem 11.1 (a) The key to this problem is to recognize that the value of every element in a chain code is relative to the value of its predecessor. The code for a boundary that is traced in a consistent manner (e.g., clockwise) is a unique circular set of numbers. Starting at different locations in this set does not change the structure of the circular sequence. Selecting the smallest integer as the starting point simply identi®es the same point in the sequence. Even if the starting point is not unique, this method would still give a unique sequence. For example, the sequence 101010 has three possible starting points, but they all yield the same smallest integer 010101.
Problem 11.3 (a) The rubber-band approach forces the polygon to have vertices at every in-ection of the cell wall. That is, the locations of the vertices are ®xed by the structure of the inner and outer walls. Since the vertices are joined by straight lines, this produces the minimum-perimeter polygon for any given wall con®guration.
Problem 11.4 (a) The resulting polygon would contain all the boundary pixels.
Problem 11.5 (a) The solution is shown in Fig. P11.5(b).
74
Chapter 11 Solutions (Students)
Figure P11.5
Problem 11.6 (a) From Fig. P11.6(a), we see that the distance from the origin to the triangle is given by r(µ) = = = = = =
D0 cos µ
0± · µ < 60±
D0 cos(120± ¡ µ) D0 cos(180± ¡ µ) D0 cos(240± ¡ µ) D0 cos(300± ¡ µ) D0 cos(360± ¡ µ)
60± · µ < 120± 120± · µ < 180± 180± · µ < 240± 240± · µ < 300± 300± · µ < 360±
where D0 is the perpendicular distance from the origin to one of the sides of the triangle, and D = D0 = cos(60± ) = 2D0 . Once the coordinates of the vertices of the triangle are given, determining the equation of each straight line is a simple problem, and D0 (which is the same for the three straight lines) follows from elementary geometry. The signature is shown in Fig. P11.6(b).
Problem 11.7
75
Figure P11.6
Problem 11.7 The solutions are shown in Fig. P11.7.
Figure P11.7
Problem 11.8 (a) In the ®rst case, N(p) = 5, S(p) = 1, p2 ¢ p4 ¢ p6 = 0, and p4 ¢ p6 ¢ p8 = 0, so Eq. (11.1-1) is satis®ed and p is -agged for deletion. In the second case, N (p) = 1, so Eq. (11.1-1) is violated and p is left unchanged. In the third case p2 ¢ p4 ¢ p6 = 1 and p4 ¢ p6 ¢ p8 = 1, so conditions (c) and (d) of Eq. (11.1-1) are violated and p is left unchanged. In the forth case S(p) = 2, so condition (b) is violated and p is left unchanged.
Problem 11.9 (a) The result is shown in Fig. 11.9(b).
76
Chapter 11 Solutions (Students)
Figure P11.9
Problem 11.10 (a) The number of symbols in the ®rst difference is equal to the number of segment primitives in the boundary, so the shape order is 12.
Problem 11.12 The mean is suf®cient.
Problem 11.14 This problem can be solved by using two descriptors: holes and the convex de®ciency (see Section 9.5.4 regarding the convex hull and convex de®ciency of a set). The decision making process can be summarized in the form of a simple decision, as follows: If the character has two holes, it is an 8. If it has one hole it is a 0 or a 9. Otherwise, it is a 1 or an X. To differentiate between 0 and 9 we compute the convex de®ciently. The presence of a }signi®cant} de®ciency (say, having an area greater than 20% of the area of a rectangle that encloses the character) signi®es a 9u otherwise we classify the character as a 0. We follow a similar procedure to separate a 1 from an X. The presence of a convex de®ciency with four components whose centroids are located approximately in the North, East, West, and East quadrants of the character indicates that the character is an X. Otherwise we say that the character is a 1. This is the basic approach. Implementation of this technique in a real character recognition environment has to take into account other factors such as multiple }small} components in the convex de®ciency due to noise, differences in orientation, open loops, and the like. However, the material in Chapters 3, 9 and 11 provide a solid base from which to formulate solutions.
Problem 11.10
77
Problem 11.16 (a) The image is 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 : 1 0 1 0 1 0 1 0 1 0 Let z1 = 0 and z2 = 1. Since there are only two gray levels the matrix A is of order 2 £ 2. Element a11 is the number of pixels valued 0 located one pixel to the right of a 0. By inspection, a11 = 0. Similarly, a12 = 10, a21 = 10, and a22 = 0. The total number of pixels satisfying the predicate P is 20, so ' # 0 1=2 C= : 1=2 0
Problem 11.18 The mean square error, given by Eq. (11.4-12), is the sum of the eigenvalues whose corresponding eigenvectors are not used in the transformation. In this particular case, the four smallest eigenvalues are applicable (see Table 11.5), so the mean square error is 6 X ems = ¸j = 280: j=3
The maximum error occurs when K = 0 in Eq. (11.4-12) which then is the sum of all the eigenvalues, or 4421 in this case. Thus, the error incurred by using the two eigenvectors corresponding to the largest eigenvalues is only 6.3 % of the total possible error.
Problem 11.20 When the boundary is symmetric about the both the major and minor axes and both axes intersect at the centroid of the boundary.
Problem 11.22 We can compute a measure of texture using the expression 1 R(x; y) = 1 ¡ 1 + ¾2 (x; y)
78
Chapter 11 Solutions (Students) where ¾2 (x; y) is the gray-level variance computed in a neighborhood of (x; y). The size of the neighborhood must be suf®ciently large so as to contain enough samples to have a stable estimate of the mean and variance. Neighborhoods of size 7 £ 7 or 9 £ 9 generally are appropriate for a low-noise case such as this. Since the variance of normal wafers is known to be 400, we can obtain a normal value for R(x; y) by using ¾ 2 = 400 in the above equation. An abnormal region will have a variance of about (50)2 = 2; 500 or higher, yielding a larger value of R(x; y). The procedure then is to compute R(x; y) at every point (x; y) and label that point as 0 if it is normal and 1 if it is not. At the end of this procedure we look for clusters of 1zs using, for example, connected components (see Section 9.5.3 regarding computation of connected components) . If the area (number of pixels) of any connected component exceeds 400 pixels, then we classify the sample as defective.
12
Solutions (Students)
Problem 12.2 From the de®nition of the Euclidean distance, £ ¤1=2 Dj (x) = kx ¡ mj k = (x ¡ mj )T (x ¡ mj )
Since Dj (x) is non-negative, choosing the smallest Dj (x) is the same as choosing the smallest Dj2 (x), where Dj2 (x) = kx ¡ mj k2 = (x ¡ mj )T (x ¡ mj )
Problem 12.4
= xT x ¡ 2xT mj + mTj mj ¶ µ 1 T T T = x x ¡ 2 x mj ¡ mj mj 2 T We note that the term x x is independent of j (that is, it is a constant with respect to j in Dj2 (x), j = 1; 2; :::). Thus, choosing the minimum of Dj2 (x) is equivalent to choosing ¢ ¡ the maximum of xT mj ¡ 21 mTj mj .
The solution is shown in Fig. P12.4, where the xzs are treated as voltages and the Y zs denote impedances. From basic circuit theory, the currents, Izs, are the products of the voltages times the impedances.
Problem 12.6 The solution to the ®rst part of this problem is based on being able to extract connected components (see Chapters 2 and 11) and then determining whether a connected component is convex or not (see Chapter 11). Once all connected components have been extracted we perform a convexity check on each and reject the ones that are not convex. All that is left after this is to determine if the remaining blobs are complete or incomplete. To do this, the region consisting of the extreme rows and columns of the image is
80
Chapter 12 Solutions (Students) declared a region of 1zs. Then if the pixel-by-pixel AND of this region with a particular blob yields at least one result that is a 1, it follows that the actual boundary touches that blob, and the blob is called incomplete. When only a single pixel in a blob yields an AND of 1 we have a marginal result in which only one pixel in a blob touches the boundary. We can arbitrarily declare the blob incomplete or not. From the point of view of implementation, it is much simpler to have a procedure that calls a blob incomplete whenever the AND operation yields one or more results valued 1. After the blobs have been screened using the method just discussed, they need to be classi®ed into one of the three classes given in the problem statement. We perform the classi®cation problem based on vectors of the form x = (x1 ; x2 )T , where x1 and x2 are, respectively, the lengths of the major and minor axis of an elliptical blob, the only type left after screening. Alternatively, we could use the eigen axes for the same purpose. (See Section 11.2.1 on obtaining the major axes or the end of Section 11.4 regarding the eigen axes.) The mean vector of each class needed to implement a minimum distance classi®er is really given in the problem statement as the average length of each of the two axes for each class of blob. Ify they were not given, they could be obtained by measuring the length of the axes for complete ellipses that have been classi®ed a priori as belonging to each of the three classes. The given set of ellipses would thus constitute a training set, and learning would simply consist of computing the principal axes for all ellipses of one class and then obtaining the average. This would be repeated for each class. A block diagram outlining the solution to this problem is straightforward.
Figure P12.4
Problem 12.8
81
Problem 12.8 (a) As in Problem 12.7, m1 m1 1 C1 = 2 and
'
1 0 0 1
#
;
= =
' '
C¡1 1 =2
#
0 0
0 0 '
# 1 0
0 1
#
;
jC1 j = 0:25
'
# ' # 1 0 1 1 0 ¡1 C2 = 2 ; C2 = ; jC2 j = 4:00 2 0 1 0 1 Since the covariance matrices are not equal, it follows from Eq. (12.2-26) that ( ' # ) 2 0 1 1 T d1 (x) = ¡ ln(0:25) ¡ x x 2 2 0 2 1 = ¡ ln(0:25) ¡ (x21 + x22 ) 2 and ( ' # ) 0:5 0 1 1 T x x d2 (x) = ¡ ln(4:00) ¡ 2 2 0 0:5 1 1 = ¡ ln(4:00) ¡ (x21 + x22 ) 2 4 where the term ln P (!j ) was not included because it is the same for both decision functions in this case. The equation of the Bayes decision boundary is 3 d(x) = d1 (x) ¡ d2 (x) = 1:39 ¡ (x21 + x22 ) = 0: 4 (b) A plot of the boundary is shown in Fig. P12.8.
Figure P12.8
82
Chapter 12 Solutions (Students)
Problem 12.10 From basic probability theory, p(c) =
X
p(c=x)p(x):
x
For any pattern belonging to class !j , p(c=x) = p(!j =x). Therefore, X p(c) = p(!j =x)p(x): x
Substituting into this equation the formula p(! j =x) = p(x=!j )p(!j )=p(x) gives X p(c) = p(x=!j )p(!j ): x
Since the argument of the summation is positive, p(c) is maximized by maximizing p(x=!j )p(!j ) for each j. That is, if for each x we compute p(x=!j )p(!j ) for j = 1; 2; :::; W , and use the largest value each time as the basis for selecting the class from which x came, then p(c) will be maximized. Since p(e) = 1 ¡ p(c), the probability of error is minimized by this procedure.
Problem 12.12 We start by taking the partial derivative of J with respect to w: ¤ @J 1£ = ysgn(wT y) ¡ y @w 2 where, by de®nition, sgn(wT y) = 1 if wT y > 0, and sgn(wT y) = ¡1 otherwise. Substituting the partial derivative into the general expression given in the problem statement gives h io cn w(k + 1) = w(k) + y(k) ¡ y(k)sgn w(k)T y(k) 2 where y(k) is the training pattern being considered at the kth iterative step. Substituting the de®nition of the sgn function into this result yields ( T 0 if w(k) y(k) w(k + 1) = w(k) + c y(k) otherwise where c > 0 and w(1) is arbitrary. This expression agrees with the formulation given in the problem statement.
Problem 12.14 The single decision function that implements a minimum distance classi®er for two
Problem 12.16
83
classes is of the form 1 dij (x) = xT (mi ¡ mj ) ¡ (mTi mi ¡ mTj mj ): 2 Thus, for a particular pattern vector x, when dij (x) > 0, x is assigned to class !1 and, when dij (x) < 0, x is assigned to class !2 . Values of x for which dij (x) = 0 are on the boundary (hyperplane) separating the two classes. By letting w = (mi ¡ mj ) and wn+1 = ¡ 12 (mTi mi ¡ mTj mj ), we can express the above decision function in the form d(x) = wT x ¡ wn+1 :
This is recognized as a linear decision function in n dimensions, which is implemented by a single layer neural network with coef®cients wk = (mik ¡ mjk ) and
k = 1; 2; : : : ; n
1 µ = wn+1 = ¡ (mTi mi ¡ mTj mj ): 2
Problem 12.16 (a) When P (!i ) = P (! j ) and C = I. (b) No. The minimum distance classi®er implements a decision function that is the perpendicular bisector of the line joining the two means. If the probability densities are known, the Bayes classi®er is guaranteed to implement an optimum decision function in the minimum average loss sense. The generalized delta rule for training a neural network says nothing about these two criteria, so it cannot be expected to yield the decision functions in Problems 12.14 or 12.15.
Problem 12.18 All that is needed is to generate for each class training vectors of the form x = (x1 ; x2 )T , where x1 is the length of the major axis and x2 is the length of the minor axis of the blobs comprising the training set. These vectors would then be used to train a neural network using, for example, the generalized delta rule. (Since the patterns are in 2D, it is useful to point out to students that the neural network could be designed by inspection in the sense that the classes could be plotted, the decision boundary of minimum complexity obtained, and then its coef®cients used to specify the neural network. In this case the classes are far apart with respect to their spread, so most likely a single layer network implementing a linear decision function could do the job.)
84
Chapter 12 Solutions (Students)
Problem 12.20 The ®rst part of Eq. (12.3-3) is proved by noting that the degree of similarity, k, is nonnegative, so D(A; B) = 1=k ¸ 0. Similarly, the second part follows from the fact that k is in®nite when (and only when) the shapes are identical. To prove the third part we use the de®nition of D to write D(A; C) · max [D(A; B); D(B; C)] as or, equivalently,
¸ · 1 1 1 · max ; kac kab kbc
kac ¸ min [kab ; kbc ] where kij is the degree of similarity between shape i and shape j. Recall from the de®nition that k is the largest order for which the shape numbers of shape i and shape j still coincide. As Fig. 12.24(b) illustrates, this is the point at which the ®gures }separate} as we move further down the tree (note that k increases as we move further down the tree). We prove that kac ¸ min[kab ; kbc ] by contradiction. For kac · min[kab ; kbc ] to hold, shape A has to separate from shape C before (1) shape A separates from shape B; and (2) before shape B separates from shape C, otherwise kab · kac or kbc · kac , which automatically violates the condition kac < min[kab ; kbc ]. But, if (1) has to hold, then Fig. P12.20 shows the only way that A can separate from C before separating from B. This, however, violates (2), which means that the condition kac < min[kab ; kbc ] is violated (we can also see this in the ®gure by noting that kac = kbc which, since kbc < kab , violates the condition). We use a similar argument to show that if (2) holds then (1) is violated. Thus, we conclude that it is impossible for the condition kac < min[kab ; kbc ] to hold, thus proving that kac ¸ min[kab ; kbc ] or, equivalently, that D(A; C) · max[D(A; B); D(B; C)].
Figure P12.20
Problem 12.22
85
Problem 12.22 (a) An automaton capable of accepting only strings of the form abn a ¸ 1, shown in Fig. P12.22, is given by Af = (Q; §; ±; q0 ; F ); with Q = fq0 ; q1 ; q2 ; q3 ; q; g; § = fa; bg; mappings ±(q0 ; a) = fq1 g; ±(q1 ; b) = fq1 ; q2 g; ±(q2 ; a) = fq3 g and For completeness we write
F = fq3g:
±(q0 ; b) = ±(q1 ; a) = ±(q2 ; b) = ±(q3 ; a) = ±(q3 ; b) = ±(q; ; a) = ±(q; ; b) = fq; g; corresponding to the null state.
Figure P12.22
Problem 12.24 For the sample set R+ = faba; abba; abbbag it is easily shown that, for k = 1 and 2, h(¸; R+ ; k) = ;, the null set. Since q0 = h(¸; R+ ; k) is part of the inference procedure, we need to choose k large enough so that h(¸; R+ ; k) is not the null set. The shortest
86
Chapter 12 Solutions (Students) string in R+ has three symbols, so k = 3 is the smallest value that can accomplish this. For this value of k, a trial run will show that one more string needs to be added to R+ in order for the inference procedure to discover iterative regularity in symbol b. The sample string set then becomes R+ = faba; abba; abbba; abbbbag. Recalling that h(z; R+ ; k) = fw jzw in R+ ; jwj · kg we proceed as follows: z = ¸;
h(¸; R+ ; 3)
z = a;
h(a; R+ ; 3)
z = ab;
h(ab; R+ ; 3)
z = aba;
h(aba; R+ ; 3)
z = abb;
h(abb; R+ ; 3)
z = abba;
h(abba; R+ ; 3)
z = abbb;
h(abbb; R+ ; 3)
z = abbba;
h(abbba; R+ ; 3)
z = abbbb;
h(abbbb; R+ ; 3)
z = abbbba;
h(abbbba; R+ ; 3)
= fw j¸w in R+ ; jwj · 3 g = fabag = q0 ; = fw jaw in R+ ; jwj · 3 g = fba; bbag = q1 ; = fw jabw in R+ ; jwj · 3g = fa; ba; bbag = q2 ; = fw jabaw in R+ ; jwj · 3g = f¸g = q3 ; = fw jabbw in R+ ; jwj · 3 g = fa; ba; bbag = q2 ; = fw jabbaw in R+ ; jwj · 3 g = f¸g = q3 ; = fw jabbbw in R+ ; jwj · 3 g = fa; bag q4 ; = fw jabbbaw in R+ ; jwj · 3 g = f¸g = q3 ; = fw jabbbbw in R+ ; jwj · 3 g = fag = q5 ; = fw jabbbbaw in R+ ; jwj · 3 g = f¸g = q3 ;
Other strings z in §¤ = (a; b)¤ yield strings zw that do not belong to R+ , giving rise
Problem 12.22
87
to another state, denoted q; , which corresponds to the condition that h is the null set. Therefore, the states are q0 = fabag, q1 = fba; bbag, q2 = fa; ba; bbag, q3 = f¸g, q4 = fa; bag, and q5 = fag, which gives the set Q = fq0 ; q1 ; q2 ; q3 ; q4 ; q5 ; q; g. The next step is to obtain the mappings. We start by recalling that, in general, q0 = h(¸; R+ ; k). Also in general, ¯ ±(q; c) = fq 0 in Q ¯q 0 = h(zc; R+ ; k); with q = h(z; R+; k) g: In our case, q0 = h(¸; R+ ; 3) and, therefore,
±(q0 ; a) = h(¸a; R+ ; 3) = h(a; R+ ; 3) = fq1 g = q1 and ±(q0 ; b) = h(¸b; R+ ; 3) = h(b; R+ ; 3) = fq; g = q; ; where we have omitted the curly brackets for clarity in notation since the set contains only one element. Similarly, q1 = h(a; R+ ; 3), and ±(q1 ; a) = h(aa; R+ ; 3) = h(a; R+ ; 3) = q; ; ±(q1 ; b) = h(ab; R+ ; 3) = q2 :
Continuing in this manner gives q2 = h(ab; R+ ; 3) = h(abb; R+ ; 3), ±(q2; a) = h(aba; R+ ; 3) = h(abba; R+ ; 3) = q3; ±(q2 ; b) = h(abb; R+ ; 3) = q2 ; and, also, ±(q2 ; b) = h(abbb; R+ ; 3) = q4 : Next, q3 = h(aba; R+ ; 3) = h(abba; R+ ; 3) = h(abbba; R+ ; 3) = h(abbbba; R+ ; 3), from which we obtain ±(q3 ; a) = h(abaa; R+ ; 3) = h(abbaa; R+ ; 3) = h(abbbaa; R+ ; 3) = h(abbbbaa; R+ ; 3) = q;
±(q3; b) = h(abab; R+ ; 3) = h(abbab; R+ ; 3) = h(abbbab; R+ ; 3) = h(abbbbab; R+ ; 3) = q; ;
For the following state, q4 = h(abbb; R+ ; 3); ±(q4 ; a) = h(abbba; R+ ; 3) = q3 ; ±(q4 ; b) = h(abbbb; R+ ; 3) = q5 :
88
Chapter 12 Solutions (Students) Finally, for the last state, q5 = h(abbbb; R+ ; 3), and ±(q5 ; a) = h(abbbba; R+ ; 3) = q3 ; ±(q5 ; b) = h(abbbbb; R+ ; 3) = q; : We complete the elements of the automaton by recalling that F = fq jq in Q; ¸ in q g = q3 . We also include two remaining mappings that yield the null set: ±(q; ; a) = ±(q; ; b) = q; . Summarizing, the state mappings are: ±(q0 ; a) = q1 ; ±(q0 ; b) = q; ; ±(q1 ; a) = q; ; ±(q1 ; b) = q2 ; ±(q2 ; a) = q3 ; ±(q2 ; b) = fq2 ; q4 g; ±(q3 ; a) = q; ; ±(q3 ; b) = q; ; ±(q4 ; a) = q3 ; ±(q4 ; b) = q5 ; ±(q5 ; a) = q3 ; ±(q5 ; b) = q; ; ±(q; ; a) = q; ; ±(q; ; b) = q; : A diagram of the automaton is shown in Fig. P12.24. The iterative regularity on b is evident in state q2 . This automaton is not as elegant as its counterpart in Problem 12.22(a). This is not unexpected because nothing in the inference procedure deals with state minimization. Note, however, that the automaton accepts only strings of the form abn a, b ¸ 1, as desired. The minimization aspects of a design generally follow inference and are based on one of several standard methods (see, for example, Gonzalez and Thomason [1978]). In this particular example, even visual inspection reveals that states q4 and q5 are redundant.
Figure P12.24