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

Exam (elaborations) 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