TEST BANK FOR Digital Image Processing 3ed Edition By Rafael C. Gonzalez and Richard E. Woods (Solution Manual)

TEST BANK FOR Digital Image Processing 3ed Edition By Rafael C. Gonzalez and Richard E. Woods (Solution Manual) Digital Image Processing Third Edition Instructor's Manual Version 3.0 Rafael C. Gonzalez Richard E. Woods Prentice Hall Upper Saddle River, NJ 07458 Copyright © R. C. Gonzalez and R. E. Woods Chapter 1 Introduction The purpose of this chapter is to present suggested guidelines for teachingmaterial fromDigital Image Processing at the senior and first-year graduate levels. We also discuss use of the book web site. Although the book is totally self-contained, the web site offers, among other things, complementary review material and computer projects that can be assigned in conjunction with classroom work. Detailed solutions to all problems in the book also are included in the remaining chapters of thismanual. 1.1 Teaching Features of the Book Undergraduate programs that offer digital image processing typically limit coverage to one semester. Graduate programs vary, and can include one or two semesters of the material. In the following discussion we give general guidelines for a one-semester senior course, a one-semester graduate course, and a fullyear course of study covering two semesters. We assume a 15-week programper semester with three lectures per week. In order to provide flexibility for exams and review sessions, the guidelines discussed in the following sections are based on forty, 50-minute lectures per semester. The background assumed on the part of the student is senior-level preparation in mathematical analysis, matrix theory, probability, and computer programming. The Tutorials section in the book web site contains review materials on matrix theory and probability, and has a brief introduction to linear systems. PowerPoint classroom presentation material on the review topics is available in the Faculty section of the web site. The suggested teaching guidelines are presented in terms of general objectives, and not as time schedules. There is so much variety in the way image processingmaterial is taught that itmakes little sense to attempt a breakdown of the material by class period. In particular, the organization of the present edition of 1 2 CHAPTER 1. INTRODUCTION the book is such that it makes it much easier than before to adopt significantly different teaching strategies, depending on course objectives and student background. For example, it is possible with the new organization to offer a course that emphasizes spatial techniques and covers little or no transform material. This is not something we recommend, but it is an option that often is attractive in programs that place little emphasis on the signal processing aspects of the field and prefer to focus more on the implementation of spatial techniques. 1.2 One Semester Senior Course A basic strategy in teaching a senior course is to focus on aspects of image processing in which both the inputs and outputs of those processes are images. In the scope of a senior course, this usually means the material contained in Chapters 1 through 6. Depending on instructor preferences, wavelets (Chapter 7) usually are beyond the scope of coverage in a typical senior curriculum. However, we recommend covering at least some material on image compression (Chapter 8) as outlined below. We have found in more than three decades of teaching this material to seniors in electrical engineering, computer science, and other technical disciplines, that one of the keys to success is to spend at least one lecture on motivation and the equivalent of one lecture on review of background material, as the need arises. The motivational material is provided in the numerous application areas dis1.2 One Semester Senior Coursecussed in Chapter 1. This chapter was prepared with this objective in mind. Some of this material can be covered in class in the first period and the rest assigned as independent reading. Background review should cover probability theory (of one randomvariable) before histogram processing (Section 3.3). A brief review of vectors andmatricesmay be required later, depending on the material covered. The review material in the book web site was designed for just this purpose. Chapter 2 should be covered in its entirety. Some of the material (Sections 2.1 through 2.3.3) can be assigned as independent reading, but more detailed explanation (combined with some additional independent reading) of Sections 2.3.4 and 2.4 through 2.6 is time well spent. The material in Section 2.6 covers concepts that are used throughout the book and provides a number of image processing applications that are useful as motivational background for the rest of the book Chapter 3 covers spatial intensity transformations and spatial correlation and convolution as the foundation of spatial filtering. The chapter also covers a number of different uses of spatial transformations and spatial filtering for image enhancement. These techniques are illustrated in the context enhancement 1.2. ONE SEMESTER SENIOR COURSE 3 (as motivational aids), but it is pointed out several times in the chapter that the methods developed have a much broader range of application. For a senior course, we recommend covering Sections 3.1 through 3.3.1, and Sections 3.4 through 3.6. Section 3.7 can be assigned as independent reading, depending on time. The key objectives of Chapter 4 are (1) to start frombasic principles of signal sampling and from these derive the discrete Fourier transform; and (2) to illustrate the use of filtering in the frequency domain. As in Chapter 3, we usemostly examples from image enhancement, but make it clear that the Fourier transform has a much broader scope of application. The early part of the chapter through Section 4.2.2 can be assigned as independent reading. We recommend careful coverage of Sections 4.2.3 through 4.3.4. Section 4.3.5 can be assigned as independent reading. Section 4.4 should be covered in detail. The early part of Section 4.5 deals with extending to 2-D the material derived in the earlier sections of this chapter. Thus, Sections 4.5.1 through 4.5.3 can be assigned as independent reading and then devote part of the period following the assignment to summarizing that material. We recommend class coverage of the rest of the section. In Section 4.6, we recommend that Sections 4.6.1-4.6.6 be covered in class. Section 4.6.7 can be assigned as independent reading. Sections 4.7.1-4.7.3 should be covered and Section 4.7.4 can be assigned as independent reading. In Sections 4.8 through 4.9 we recommend covering one filter (like the ideal lowpass and highpass filters) and assigning the rest of those two sections as independent reading. In a senior course, we recommend covering Section 4.9 through Section 4.9.3 only. In Section 4.10, we also recommend covering one filter and assigning the rest as independent reading. In Section 4.11, we recommend covering Sections 4.11.1 and 4.11.2 and mentioning the existence of FFT algorithms. The log2 computational advantage of the FFT discussed in the early part of Section 4.11.3 should bementioned, but in a senior course there typically is no time to cover development of the FFT in detail. Chapter 5 can be covered as a continuation of Chapter 4. Section 5.1 makes this an easy approach. Then, it is possible to give the student a “flavor” of what restoration is (and still keep the discussion brief ) by covering only Gaussian and impulse noise in Section 5.2.1, and two of the spatial filters in Section 5.3. This latter section is a frequent source of confusion to the student who, based on discussions earlier in the chapter, is expecting to see amore objective approach. It is worthwhile to emphasize at this point that spatial enhancement and restoration are the same thing when it comes to noise reduction by spatial filtering. A good way to keep it brief and conclude coverage of restoration is to jump at this point to inverse filtering (which follows directly from the model in Section 5.1) and show the problems with this approach. Then, with a brief explanation 4 CHAPTER 1. INTRODUCTION regarding the fact that much of restoration centers around the instabilities inherent in inverse filtering, it is possible to introduce the “interactive” formof the Wiener filter in Eq. (5.8-3) and discuss Examples 5.12 and 5.13. At a minimum, we recommend a brief discussion on image reconstruction by covering Sections 5.11.1-5.11-2 and mentioning that the rest of Section 5.11 deals with ways to generated projections in which blur is minimized. Coverage of Chapter 6 also can be brief at the senior level by focusing on enough material to give the student a foundation on the physics of color (Section 6.1), two basic color models (RGB and CMY/CMYK), and then concluding with a brief coverage of pseudocolor processing (Section 6.3). We typically conclude a senior course by covering some of the basic aspects of image compression (Chapter 8). Interest in this topic has increased significantly as a result of the heavy use of images and graphics over the Internet, and students usually are easily motivated by the topic. The amount of material covered depends on the time left in the semester. 1.3 One Semester Graduate Course (No Background in DIP) Themain difference between a senior and a first-year graduate course in which neither group has formal background in image processing is mostly in the scope of thematerial covered, in the sense thatwe simply go faster in a graduate course and feel much freer in assigning independent reading. In a graduate course we add the following material to thematerial suggested in the previous section. Sections 3.3.2-3.3.4 are added as is Section 3.3.8 on fuzzy image processing. We cover Chapter 4 in its entirety (with appropriate sections assigned as independent readying, depending on the level of the class). To Chapter 5 we add Sections 5.6-5.8 and cover Section 5.11 in detail. In Chapter 6 we add the HSImodel (Section 6.3.2) , Section 6.4, and Section 6.6. A nice introduction to wavelets (Chapter 7) can be achieved by a combination of classroom discussions and independent reading. The minimum number of sections in that chapter are 7.1, 7.2, 7.3, and 7.5, with appropriate (but brief) mention of the existence of fast wavelet transforms. Sections 8.1 and 8.2 through Section 8.2.8 provide a nice introduction to image compression. If additional time is available, a natural topic to cover next is morphological image processing (Chapter 9). The material in this chapter begins a transition from methods whose inputs and outputs are images tomethods in which the inputs are images, but the outputs are attributes about those images, in the sense defined in Section 1.1. We recommend coverage of Sections 9.1 through 9.4, and 1.4. ONE SEMESTERGRADUATE COURSE (WITHSTUDENT HAVINGBACKGROUNDINDIP)5 some of the algorithms in Section 9.5. 1.4 One Semester Graduate Course (with Student Having Background in DIP) Some programs have an undergraduate course in image processing as a prerequisite to a graduate course on the subject, in which case the course can be biased toward the latter chapters. In this case, a good deal of Chapters 2 and 3 is review, with the exception of Section 3.8, which deals with fuzzy image processing. Depending on what is covered in the undergraduate course, many of the sections in Chapter 4 will be review as well. For Chapter 5 we recommend the same level of coverage as outlined in the previous section. In Chapter 6 we add full-color image processing (Sections 6.4 through 6.7). Chapters 7 and 8 are covered as outlined in the previous section. As noted in the previous section, Chapter 9 begins a transition from methods whose inputs and outputs are images tomethods in which the inputs are images, but the outputs are attributes about those images. As a minimum, we recommend coverage of binary morphology: Sections 9.1 through 9.4, and some of the algorithms in Section 9.5. Mention should be made about possible extensions to gray-scale images, but coverage of this material may not be possible, depending on the schedule. In Chapter 10, we recommend Sections 10.1 through 10.4. In Chapter 11 we typically cover Sections 11.1 through 11.4. 1.5 Two Semester Graduate Course (No Background in DIP) In a two-semester course it is possible to cover material in all twelve chapters of the book. The key in organizing the syllabus is the background the students bring to the class. For example, in an electrical and computer engineering curriculum graduate students have strong background in frequency domain processing, so Chapter 4 can be covered much quicker than would be the case in which the students are from, say, a computer science program. The important aspect of a full year course is exposure to the material in all chapters, even when some topics in each chapter are not covered. 1.6 Projects One of the most interesting aspects of a course in digital image processing is the pictorial nature of the subject. It has been our experience that students truly enjoy and benefit from judicious use of computer projects to complement the 6 CHAPTER 1. INTRODUCTION material covered in class. Because computer projects are in addition to course work and homework assignments, we try to keep the formal project reporting as brief as possible. In order to facilitate grading, we try to achieve uniformity in the way project reports are prepared. A useful report format is as follows: Page 1: Cover page. • Project title • Project number • Course number • Student’s name • Date due • Date handed in • Abstract (not to exceed 1/2 page) Page 2: One to two pages (max) of technical discussion. Page 3 (or 4): Discussion of results. One to two pages (max). Results: Image results (printed typically on a laser or inkjet printer). All images must contain a number and title referred to in the discussion of results. Appendix: Program listings, focused on any original code prepared by the student. For brevity, functions and routines provided to the student are referred to by name, but the code is not included. Layout: The entire reportmust be on a standard sheet size (e.g., letter size in the U.S. or A4 in Europe), stapled with three or more staples on the left margin to form a booklet, or bound using clear plastic standard binding products.1.2 One Semester Senior Course Project resources available in the book web site include a sample project, a list of suggested projects from which the instructor can select, book and other images, and MATLAB functions. Instructors who do not wish to use MATLAB will find additional software suggestions in the Support/Software section of the web site. 1.7. THE BOOKWEB SITE 7 1.7 The Book Web Site The companion web site (or itsmirror site) is a valuable teaching aid, in the sense that it includes material that previously was covered in class. In particular, the review material on probability, matrices, vectors, and linear systems, was prepared using the same notation as in the book, and is focused on areas that are directly relevant to discussions in the text. This allows the instructor to assign the material as independent reading, and spend no more than one total lecture period reviewing those subjects. Another major feature is the set of solutions to problems marked with a star in the book. These solutions are quite detailed, and were prepared with the idea of using them as teaching support. The on-line availability of projects and digital images frees the instructor fromhaving to prepare experiments, data, and handouts for students. The fact that most of the images in the book are available for downloading further enhances the value of the web site as a teaching resource. NOTICE This manual is intended for your personal use only. Copying, printing, posting, or any form of printed or electronic distribution of any part of this manual constitutes a violation of copyright law. As a security measure, this manual was encrypted during download with the serial number of your book, and with your personal information. Any printed or electronic copies of this file will bear that encryption, which will tie the copy to you. Please help us defeat piracy of intellectual property, one of the principal reasons for the increase in the cost of books. ------------------------------- Chapter 2 Problem Solutions 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) 0.2 = (x/2) 0.017 which gives x = 0.085d . 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.085(d ) <1.3×10−6 m, or d < 15.3×10−6 m. Image of the dot x x/2 on the fovea Edge view of dot d d/2 0.2 m 0.017 m Figure P2.1 9 10 CHAPTER 2. PROBLEM SOLUTIONS Problem 2.2 Brightness adaptation. Problem 2.3 The solution is λ = c /v = 2.998×108(m/s)/60(1/s) = 4.997×106m=4997Km. Problem 2.4 (a) From the discussion on the electromagnetic spectrum in Section 2.2, the source of the illumination required to see an object must have wavelength the same size or smaller than the object. Because interest lies only on the boundary shape and not on other spectral characteristics of the specimens, a single illumination source in the far ultraviolet (wavelength of .001 microns or less) will be able to detect all objects. A far-ultraviolet camera sensor would be needed to image the specimens. (b) No answer is required because the answer to (a) is affirmative. Problem 2.5 From the geometry of Fig. 2.3, (7mm)/(35mm) = (z )/(500mm), or z = 100mm. So the target size is 100 mm on the side. We have a total of 1024 elements per line, so the resolution of 1 line is 1024/100 = 10 elements/mm. For line pairs we divide by 2, giving an answer of 5 lp/mm. 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 filter 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 filter. The analysis then would be 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 field of view of the camera(s) is such that it is com11 Intensity Intensity 0 255 0 255 (x , y ) 0 0 G Equally spaced subdivisions (a) (b) Figure P2.7 pletely filled 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.7 The image in question is given by f (x,y ) = i (x,y )r (x,y ) = 255e −[(x−x0)2+(y−y0)2] ×1.0 = 255e −[(x−x0)2+(y−y0)2] A cross section of the image is shown in Fig. P2.7(a). If the intensity is quantized using m bits, then we have the situation shown in Fig. P2.7(b), where G = (255 +1)/2m. Since an abrupt change of 8 intensity levels is assumed to be detectable by the eye, it follows that G = 8 = 256/2m, or m = 5. In other words, 32, or fewer, intensity levels will produce visible false contouring. 12 CHAPTER 2. PROBLEM SOLUTIONS Intensity 0 63 127 191 255 Image quantized into four levels 255 191 127 63 Figure P2.8 Problem 2.8 The use of two bits (m = 2) of intensity resolution produces four intensity levels in the range 0 to 255. One way to subdivide this range is to let all levels between 0 and 63 be coded as 63, all levels between 64 and 127 be coded as 127, and so on. The image resulting from this type of subdivision is shown in Fig. P2.8. Of course, there are other ways to subdivide the range [0,255] into four bands. 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 56K baud link is (1024)2 ×[8+2]/56000 = 187.25 sec or about 3.1 min. (b) At 3000K this time goes down to about 3.5 sec. Problem 2.10 The width-to-height ratio is 16/9 and the resolution in the vertical direction is 1125 lines (or, what is the same thing, 1125 pixels in the vertical direction). It is given that the resolution in the horizontal direction is in the 16/9 proportion, so the resolution in the horizontal direction is (1125)×(16/9) = 2000 pixels per line. The system“paints” a full 1125×2000, 8-bit image every 1/30 sec for each of the 13 Figure P2.11 red, green, and blue component images. There are 7200 sec in two hours, so the total digital data generated in this time interval is (1125)(2000)(8)(30)(3)(7200) = 1.166 × 1013 bits, or 1.458 ×1012 bytes (i.e., about 1.5 terabytes). These figures show why image data compression (Chapter 8) is so important. 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); (b) S1 and S2 are 8-connected because q is in the set N8(p); (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 The solution of this problem consists of defining all possible neighborhood shapes to go froma diagonal segment to a corresponding 4-connected segments as Fig. P2.12 illustrates. The algorithmthen simply looks for the appropriatematch every time a diagonal segments is encountered in the boundary. Problem 2.13 The solution to this problem is the same as for Problem2.12 because converting from an m-connected path to a 4-connected path simply involves detecting diagonal segments and converting them to the appropriate 4-connected segment. Problem 2.14 The difference between the pixels in the background that are holes and pixels that are not holes is than no paths exist between hole pixels and the boundary of the image. So, the definition could be restated as follows: The subset of pixels 14 CHAPTER 2. PROBLEM SOLUTIONS  or  or  or  or Figure P2.12 of (RU)c that are connected to the border of the image is called the background. All other pixels of (RU)c are called hole pixels. Problem 2.15 (a) When V = {0,1}, 4-path does not exist between p and q because it is impossible to 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 condition; it is not possible to get to q. The shortest 8-path is shown in Fig. P2.15(b); its length is 4. The length of the shortest m- path (shown dashed) is 5. Both of these shortest paths are unique in this case. (b)One possibility for the shortest 4-pathwhen V ={1,2} is shown in Fig. P2.15(c); its length is 6. It is easily verified 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); its length is 4. The length of a shortest m-path (shown dashed) is 6. This path is not unique. 15 Figure P.2.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 |x −s | and  y −t  , respectively. The total path length is |x −s |+  y −t  , whichwe recognize as the definition of the D4 distance, as given in Eq. (2.5-2). (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 |x −s |+  y −t  . 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 fromp to q bymaking turns in atmost two directions (e.g., right and up). (b) The path may or may not be unique, depending on V and the values of the points along the way. Problem 2.17 (a) The D8 distance between p and q [see Eq. (2.5-3) and Fig. P2.16] is D8  p,q  = max  |x −s | ,  y −t   . Recall that the D8 distance (unlike the Euclidean distance) counts diagonal segments the same as horizontal and vertical segments, and, as in the case of the D4 distance, is independent of whether or not a path exists between p and q. As in the previous problem, the shortest 8-path is equal to the D8 distance when the path length ismax  |x −s | ,  y −t   . This occurs when we can get from p to q 16 CHAPTER 2. PROBLEM SOLUTIONS Figure P2.16 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 traveling diagonally in only one direction and, whenever diagonal travel is not possible, by making turns in the horizontal or vertical (but not both) direction. (b) The path may or may not be unique, depending on V and the values of the points along the way. Problem 2.18 With reference to Eq. (2.6-1), let H denote the 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 sumof the elements in S1 and S2, as explained in Section 2.6.1. 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 in a given neighborhood. Then, H(aS1 +bS2) means: (1) multiply the pixels in each of the subimage areas by the constants shown, (2) add the pixel-by-pixel values from aS1 and bS2 (which produces a single subimage area), and (3) compute the sumof the values of all the pixels in that single subimage area. Let ap1 and bp2 denote two arbitrary (but corresponding) pixels from aS1 +bS2. Thenwe canwrite H(aS1 +bS2) =  p1∈S1 and p2∈S2 ap1 +bp2 =  p1∈S1 ap1 +  p2∈S2 bp2 =a  p1∈S1 p1 +b  p2∈S2 p2 =aH(S1)+bH(S2) 17 which, according to Eq. (2.6-1), indicates that H is a linear operator. Problem 2.19 The median, ζ, of a set of numbers is such that half the values in the set are below ζ and the other half are above it. A simple example will suffice to show that Eq. (2.6-1) is violated by the median operator. Let S1 = {1,−2,3}, S2 = {4, 5,6}, and a = b = 1. In this case H is the median operator. We then have H(S1 +S2) =median{5, 3,9} = 5, where it is understood that S1 +S2 is the array sum of S1 and S2. Next,we compute H(S1) = median{1,−2,3} = 1 and H(S2) = median{4, 5,6} = 5. Then, because H(aS1 +bS2) = aH(S1) +bH(S2), it follows that Eq. (2.6-1) is violated and themedian is a nonlinear operator. Problem 2.20 From Eq. (2.6-5), at any point (x,y ), g = 1 K K i=1 gi = 1 K K i=1 f i + 1 K K i=1 ηi . Then E{g }= 1 K K i=1 E{f i }+ 1 K K i=1 E{ηi }. But all the f i are the same image, so E{f i } = f . Also, it is given that the noise has zero mean, so E{ηi } = 0. Thus, it follows that E{g } = f , which proves the validity of Eq. (2.6-6). To prove the validity of Eq. (2.6-7) consider the preceding equation again: g = 1 K K i=1 gi = 1 K K i=1 f i + 1 K K i=1 ηi . It is known fromrandom-variable theory that the variance of the sum of uncorrelated randomvariables is the sum of the variances of those variables (Papoulis [1991]). Because it is given that the elements of f are constant and the ηi are uncorrelated, then σ2 g = σ2f + 1 K 2 [σ2 η1 +σ2 η2 +· · ·+σ2 ηK ]. The first termon 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, 18 CHAPTER 2. PROBLEM SOLUTIONS σ2η i =σ2η and we have σ2 g = K K 2σ2 η = 1 K σ2 η which proves the validity of Eq. (2.6-7). Problem 2.21 (a) Pixels are integer values, and 8 bits allowrepresentation of 256 contiguous integer values. In ourwork, the range of intensity values for 8-bit images is [0,255]. The subtraction of values in this range cover the range [−255,255]. This rangeof values cannot be covered by 8 bits, but it is given in the problem statement that the result of subtraction has to be represented in 8 bits also, and, consistent with the range of values used for 8-bit images throughout the book, we assume that values of the 8-bit difference images are in the range [0,255]. What thismeans is that any subtraction of 2 pixels that yields a negative quantity will be clipped at 0. The process of repeated subtractions of an image b(x,y ) froman image a(x,y ) can be expressed as dK (x,y ) = a(x,y )− K k=1 b(x,y ) = a(x,y )−K ×b(x,y ) where dK (x,y ) is the difference image resulting after K subtractions. Because image subtraction is an array operation (see Section 2.6.1), we can focus attention on the subtraction of any corresponding pair of pixels in the images. We have already stated that negative results are clipped at 0. Once a 0 result is obtained, it will remain so because subtraction of any nonnegative value from 0 is a negative quantity which, again, is clipped at 0. Similarly, any location  x0,y0  for which b  x0,y0  = 0, will produce the result dK  x0,y0  = a  x0,y0  . That is, repeatedly subtracting 0 from any value results in that value. The locations in b(x,y ) that are not 0 will eventually decrease the corresponding values in dK (x,y ) until they are 0. The maximum number of subtractions in which this takes place in the context of the present problem is 255, which corresponds to the condition at a location in which a(x,y ) is 255 and b(x,y ) is 1. Thus, we conclude from the preceding discussion that repeatedly subtracting an image from another will result in a difference image whose components are 0 in the locations in b(x,y ) that are not zero and equal to the original values of a(x,y ) at the locations in b(x,y ) that are 0. This result will be achieved in, at most, 255 subtractions. 19 (b) The order does matter. For example, suppose that at a pair of arbitrary coordinates,  x0,y0  , a  x0,y0  = 128 and b  x0,y0  = 0. Subtracting b  x0,y0  from a  x0,y0  will result in dK  x0,y0  = 128 in the limit. Reversing the operation will result in a value of 0 in that same location. Problem 2.22 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 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 specified threshold band [Tmin,Tmax ] where Tmin is negative and Tmax is positive. Usually, the same value of threshold is used for both negative and positive differences, so that 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  d (x,y )  and compare the sum against a thresholdQ. Note that the absolute value needs to be used to avoid errors canceling out. This is amuch cruder test, so we will concentrate on the first approach. There are three fundamental factors that need tight control for differencebased 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 first condition basically addresses the requirement that comparisons bemade 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 used often 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 modified 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 notmaterially affect comparisons between the golden and input images. Good signal strength goes a long way toward reducing the effects of noise. 20 CHAPTER 2. PROBLEM SOLUTIONS Figure P2.23 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-by-pixel threshold comparisons can be implemented. A technique used often 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 2.23 (a) The answer is shown in Fig. P2.23. (b) With reference to the sets in the problem statement, the answers are, from left to right, (A ∩ B ∩C)−(B ∩C) ; (A ∩ B ∩C)∪(A ∩C)∪(A ∩ B) ;  B ∩(A ∪C)c ∪{(A ∩C)−[(A ∩C) ∩(B ∩C)]} . Problem 2.24 Using triangular regionsmeans three tiepoints, so we can solve the following set of linear equations for six coefficients: x = c1x +c2y +c3 y  = c4x +c5y +c6 21 to implement spatial transformations. Intensity interpolation is implemented using any of themethods in Section 2.4.4. Problem 2.25 The Fourier transformation kernel is separable because r (x,y ,u,v) = e −j 2π(ux/M+vy /N) = e −j 2π(ux/M)e −j 2π(vy /N) = r1(x,u)r2(y ,v ). It is symmetric because e −j 2π(ux/M+vy /N) = e −j 2π(ux/M)e −j 2π(vy /N) = r1(x,u)r1(y ,v ). Problem 2.26 From Eq. (2.6-27) and the definition of separable kernels, T(u,v) = M−1 x=0 N−1 y=0 f (x,y )r (x,y ,u,v ) = M−1 x=0 r1(x,u) N−1 y=0 f (x,y )r2(y ,v ) = M−1 x=0 T(x,v )r1(x,u) where T (x,v) = N−1 y=0 f (x,y )r2(y ,v ). For a fixed value of x, this equation is recognized as the 1-D transform along one row of f (x,y ). By letting x vary from0 toM −1 we compute the entire array T(x,v ). Then, by substituting this array into the last line of the previous equation we have the 1-D transform along the columns of T(x,v ). In otherwords, when a kernel is separable, we can compute the 1-D transform along the rows of the image. Then we compute the 1-D transformalong the columns of this intermediate result to obtain the final 2-D transform, T (u,v ). Weobtainthe same result by computing the 1-D transformalong the columns of f (x,y ) followed by the 1-D transformalong the rows of the intermediate result. 22 CHAPTER 2. PROBLEM SOLUTIONS This result plays an important role in Chapter 4 when we discuss the 2-D Fourier transform. From Eq. (2.6-33), the 2-D Fourier transformis given by T (u,v) = M−1 x=0 N−1 y=0 f (x,y )e −j 2π(ux/M+vy /N). It is easily verified that the Fourier transform kernel is separable (Problem2.25), so we can write this equation as T(u,v) = M−1 x=0 N−1 y=0 f (x,y )e −j 2π(ux/M+vy /N) = M−1 x=0 e −j 2π(ux/M) N−1 y=0 f (x,y )e −j 2π(vy /N) = M−1 x=0 T(x,v )e −j 2π(ux/M) where T (x,v) = N−1 y=0 f (x,y )e −j 2π(vy /N) is the 1-D Fourier transformalong the rows of f (x,y ), aswe let x = 0,1, . . . ,M−1. Problem 2.27 The geometry of the chips is shown in Fig. P2.27(a). From Fig. P2.27(b) and the geometry in Fig. 2.3, we know that Δx = λ×80 λ−z where Δx is the side dimension of the image (assumed square because the viewing screen is square) impinging on the image plane, and the 80 mm refers to the size of the viewing screen, as described in the problem statement. The most inexpensive solutionwill result from using a camera of resolution 512×512. Based on the information in Fig. P2.27(a), a CCD chip with this resolution will be of size (16μ) × (512) = 8 mm on each side. Substituting Δx = 8 mm in the above equation gives z = 9λ as the relationship between the distance z and the focal length of the lens, where a minus sign was ignored because it is just a coordinate inversion. If a 25 mm lens is used, the front of the lens will have to be located at approximately 225mmfromthe viewing screen so that the size of the 23 Figure P2.27 image of the screen projected onto the CCD image plane does not exceed the 8 mmsize of the CCD chip for the 512×512 camera. This value of z is reasonable, but any other given lens sizes would be also; the camera would just have to be positioned further away. Assuming a 25 mm lens, the next issue is to determine if the smallest defect will be imaged on, at least, a 2×2 pixel area, as required by the specification. It is given that the defects are circular, with the smallest defect having a diameter of 0.8 mm. So, all that needs to be done is to determine if the image of a circle of diameter 0.8mmor greater will, at least, be of size 2×2 pixels on theCCD imaging plane. This can be determined by using the same model as in Fig. P2.27(b) with the 80 mm replaced by 0.8 mm. Using λ = 25 mm and z = 225 mm in the above equation yields Δx = 100 μ. In other words, a circular defect of diameter 0.8 mm will be imaged as a circle with a diameter of 100 μ on the CCD chip of a 512×512 camera equipped with a 25 mm lens and which views the defect at a distance of 225 mm. If, in order for a CCD receptor to be activated, its area has to be excited in its entirety, then, it can be seen from Fig. P2.27(a) that to guarantee that a 2 × 2 array of such receptors will be activated, a circular area of diameter no less than (6)(8) = 48 μ has to be imaged onto the CCD chip. The smallest defect is imaged as a circle with diameter of 100 μ, which is well above the 48 μ minimum requirement. 24 CHAPTER 2. PROBLEM SOLUTIONS Therefore, we conclude that a CCD camera of resolution 512 × 512 pixels, using a 25 mm lens and imaging the viewing screen at a distance of 225 mm, is sufficient to solve the problem posed by the plantmanager. Chapter 3 Problem Solutions Problem 3.1 Let f denote the original image. First subtract theminimum value of f denoted f min from f to yield a function whoseminimum value is 0: g1 = f − f min Next divide g1 by its maximum value to yield a function in the range [0,1] and multiply the result by L −1 to yield a function with values in the range [0,L −1] g = L −1 max  g 1  g 1 = L −1 max  f − f min   f − f min  Keep inmind that f min is a scalar and f is an image. Problem 3.2 (a) General form: s =T (r) = Ae−K r2 . For the condition shown in the problem figure, Ae−K L2 0 =A/2. Solving for K yields −KL2 0 =ln(0.5) K =0.693/L2 0. Then, s = T(r) = Ae −0.693 L2 0 r 2 . (b) General form: s = T(r) = B(1−e −K r2). For the condition shown in the prob- 25 26 CHAPTER 3. PROBLEM SOLUTIONS Figure P3.3 lem figure, B(1−e −K L2 0) = B/2. The solution for K is the same as in (a), so s =T (r) = B(1−e −0.693 L2 0 r 2 ) (c) General form: s = T(r) = (D −C)(1−e −K r2)+C. Problem 3.3 (a) s = T(r) = 1 1+(m/r )E . (b) See Fig. P3.3. (c) We want s to be 0 for r < m, and s to be 1 for values of r > m. Whenr =m, s =1/2. But, because the values of r are integers, the behavior we want is s = T(r) = ⎧ ⎨ ⎩ 0.0 when r ≤m −1 0.5 when r =m 1.0 when r ≥m +1. The question in the problem statement is to find the smallest value of E that will make the threshold behave as in the equation above. When r = m, we see from (a) that s = 0.5, regardless of the value of E. If C is the smallest positive 27 number representable in the computer, and keeping in mind that s is positive, then any value of s less than C/2 will be called 0 by the computer. To find the smallest value of E for which this happens, simply solve the following equation for E, using the given valuem =128: 1 1+[m/(m −1)]E <C/2. Because the function is symmetric about m, the resulting value of E will yield s = 1 for r ≥m +1. Problem 3.4 The transformations required to produce the individual bit planes are nothing more than mappings of the truth table for eight binary variables. In this truth table, the values of the 8th bit are 0 for byte values 0 to 127, and 1 for byte values 128 to 255, thus giving the transformationmentioned in the problem statement. Note that the given transformed values of either 0 or 255 simply indicate a binary image for the 8th bit plane. Any other two values would have been equally valid, though less conventional. Continuing with the truth table concept, the transformation required to produce an image of the 7th bit plane outputs a 0 for byte values in the range [0, 63], a 1 for byte values in the range [64, 127], a 0 for byte values in the range [128, 191], and a 1 for byte values in the range [192, 255]. Similarly, the transformation for the 6th bit plane alternates between eight ranges of byte values, the transformation for the 5th bit plane alternates between 16 ranges, and so on. Finally, the output of the transformation for the lowest-order bit plane alternates between 0 and 255 depending on whether the byte values are even or odd. Thus, this transformation alternates between 128 byte value ranges, which explains why an image of that bit plane is usually the “busiest” looking of all the bit plane images. Problem 3.5 (a) The number of pixels having different intensity level values would decrease, thus causing the number of components in the histogram to decrease. Because the number of pixels would not change, this would cause the height of some of the remaining histogram peaks to increase in general. Typically, less variability in intensity level values will reduce contrast. (b) The most visible effect would be significant darkening of the image. For example, dropping the highest bit would limit the brightest level in an 8-bit im28 CHAPTER 3. PROBLEM SOLUTIONS age to be 127. Because the number of pixels would remain constant, the height of some of the histogram peaks would increase. The general shape of the histogram would now be taller and narrower, with no histogram components being located past 127. Problem 3.6 All that histogram equalization does is remap histogram components on the intensity scale. To obtain a uniform(flat) histogram would require in general that pixel intensities actually be 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 =MN is the total number of pixels in the input image. The histogram equalizationmethod has no provisions for this type of (artificial) intensity redistribution process. Problem 3.7 Let n = MN be the total number of pixels and let nrj be the number of pixels in the input image with intensity value rj . Then, the histogram equalization transformation is sk =T (rk) = k j=0 nrj /n = 1 n k j=0 nrj . Because every pixel (and no others) with value rk is mapped to value sk, it follows that nsk = nrk . A second pass of histogram equalization would produce values vk according to the transformation vk = T(sk) = 1 n k j=0 ns j . But, ns j = nrj , so vk =T (sk) = 1 n k j=0 nrj =sk which shows that a second pass of histogram equalization would yield the same result