5.4 Periodic Noise Reduction by Frequency Domain Filtering 243 5.4.1 Bandreject Filters 244 5.4.2 Bandpass Filters 245 5.4.3 Notch Filters 246 5.4.4 Optimum Notch Filtering 248 5.5 Linear, Position-Invariant Degradations 254 5.6 Estimating the Degradation Function 256 5.6.1 Estimation by Image Observation 256 5.6.2 Estimation by Experimentation 257 5.6.3 Estimation by Modeling 258 5.7 Inverse Filtering 26 5.8 Minimum Mean Square Error(Wiener)Filtering 262 5.9 Constrained Least Squares Filtering 266 5.10 Geometric mean filter 270 5.11 Geometric Transformations 270 5. 11.1 Spatial Transformations 271 5.11.2 Gray-Level Interpolation 272 Su References and Further Reading 277 Problems 278 Color image processing 282 6.1 Color Fundamentals 283 6.2 Color Models 289 6.2.1 The RGB Color Model 290 6.2.2 The CMY and CMYK Color Models 294 6.2.3 The HSI Color Model 295 6.3 Pseudocolor Image Processing 302 6.3.2 Gray Level to Color Transformations 30 6.4 Basics of Full-Color Image Processing 313 6.5 Color Transformations 315 6.5.1 Formulation 315 6.5.2 Color Complements 318 6.5.3 Color Slicing 320 6.5.4 Tone and Color Corrections 322 6.5.5 Histogram Processing 326 6.6 Smoothing and Sharpening 327 6.6.1 Color Image Smoothing 328 6.6.2 Color Image Sharpening 330 6.7 Color Segmentation 331 6.7.1 Segmentation in HSI Color Space 6.7.2 Segmentation in RGB Vector Sp 6.7.3 Color Edge Detection 335
5.4 Periodic Noise Reduction by Frequency Domain Filtering 243 5.4.1 Bandreject Filters 244 5.4.2 Bandpass Filters 245 5.4.3 Notch Filters 246 5.4.4 Optimum Notch Filtering 248 5.5 Linear, Position-Invariant Degradations 254 5.6 Estimating the Degradation Function 256 5.6.1 Estimation by Image Observation 256 5.6.2 Estimation by Experimentation 257 5.6.3 Estimation by Modeling 258 5.7 Inverse Filtering 261 5.8 Minimum Mean Square Error (Wiener) Filtering 262 5.9 Constrained Least Squares Filtering 266 5.10 Geometric Mean Filter 270 5.11 Geometric Transformations 270 5.11.1 Spatial Transformations 271 5.11.2 Gray-Level Interpolation 272 Summary 276 References and Further Reading 277 Problems 278 6 Color Image Processing 282 6.1 Color Fundamentals 283 6.2 Color Models 289 6.2.1 The RGB Color Model 290 6.2.2 The CMY and CMYK Color Models 294 6.2.3 The HSI Color Model 295 6.3 Pseudocolor Image Processing 302 6.3.1 Intensity Slicing 303 6.3.2 Gray Level to Color Transformations 308 6.4 Basics of Full-Color Image Processing 313 6.5 Color Transformations 315 6.5.1 Formulation 315 6.5.2 Color Complements 318 6.5.3 Color Slicing 320 6.5.4 Tone and Color Corrections 322 6.5.5 Histogram Processing 326 6.6 Smoothing and Sharpening 327 6.6.1 Color Image Smoothing 328 6.6.2 Color Image Sharpening 330 6.7 Color Segmentation 331 6.7.1 Segmentation in HSI Color Space 331 6.7.2 Segmentation in RGB Vector Space 333 6.7.3 Color Edge Detection 335 x ■ Contents GONZFM-i-xxii. 5-10-2001 14:22 Page x
6.8 Noise in Color Images 339 6.9 Color Image Compression 342 Summary 343 References and Further Reading 34 Problems 344 Wavelets and Multiresolution processing 349 7.1 Background 350 7.1.1 Image Pyramids 351 7.1.2 Subband Coding 354 7. 1.3 The Haar Transform 36 7.2 Multiresolution Expansions 363 7.2.1 Series Expansions 36 7. 2.2 Scaling Functions 365 7.2.3 Wavelet Functions 369 7.3 Wavelet Transforms in One dimension 372 7.3.1 The Wavelet Series Expansions 372 7. 3.2 The Discrete Wavelet Transform 375 7.3.3 The Continuous Wavelet Transform 376 4 The Fast Wavelet Transform 379 7.5 Wavelet Transforms in Two dimensions 386 7.6 Wavelet Packets 394 References and Further Reading 404 Problems 404 Image Compression 409 8.1 Fundamentals 411 8.1.1 Coding Redundancy -%A17 8.1.2 Interpixel Redundancy 8.1.3 Psychovisual Redundancy 8.1.4 Fidelity Criteria 419 8.2 Image Compression Models 421 8.2.1 The Source Encoder and Decoder 421 8.2.2 The Channel Encoder and Decoder 423 8.3 Elements of Information Theory 424 8.3.1 Measuring Information 424 3.2 The Information Channel 425 8.3.3 Fundamental Coding Theorems 430 8.3.4 Using Information Theory 4 8.4 Error-Free Compression 8.4.1 Variable-Length Coding 440
6.8 Noise in Color Images 339 6.9 Color Image Compression 342 Summary 343 References and Further Reading 344 Problems 344 7 Wavelets and Multiresolution Processing 349 7.1 Background 350 7.1.1 Image Pyramids 351 7.1.2 Subband Coding 354 7.1.3 The Haar Transform 360 7.2 Multiresolution Expansions 363 7.2.1 Series Expansions 364 7.2.2 Scaling Functions 365 7.2.3 Wavelet Functions 369 7.3 Wavelet Transforms in One Dimension 372 7.3.1 The Wavelet Series Expansions 372 7.3.2 The Discrete Wavelet Transform 375 7.3.3 The Continuous Wavelet Transform 376 7.4 The Fast Wavelet Transform 379 7.5 Wavelet Transforms in Two Dimensions 386 7.6 Wavelet Packets 394 Summary 402 References and Further Reading 404 Problems 404 8 Image Compression 409 8.1 Fundamentals 411 8.1.1 Coding Redundancy 412 8.1.2 Interpixel Redundancy 414 8.1.3 Psychovisual Redundancy 417 8.1.4 Fidelity Criteria 419 8.2 Image Compression Models 421 8.2.1 The Source Encoder and Decoder 421 8.2.2 The Channel Encoder and Decoder 423 8.3 Elements of Information Theory 424 8.3.1 Measuring Information 424 8.3.2 The Information Channel 425 8.3.3 Fundamental Coding Theorems 430 8.3.4 Using Information Theory 437 8.4 Error-Free Compression 440 8.4.1 Variable-Length Coding 440 ■ Contents xi GONZFM-i-xxii. 5-10-2001 14:22 Page xi
xll Contents 8.4.2 LZW Coding 446 8.4.3 Bit-Plane Coding 448 8.4.4 Lossless Predictive Coding 456 8.5 Lossy Compression 459 8.5.1 Lossy Predictive Coding 459 6.5.2 Transform Coding 8.5.3 Wavelet Coding 8.6 Image Compression Standards 492 8.6.1 Binary Image Compression Standards 493 8.6.2 Continuous Tone Still Image Compression Standards 498 8.6.3 Video Compression Standards 510 Summary 513 eferences and Further Reading 513 Problems 514 Morphological Image processing 519 9.1 Preliminaries 520 9.1.1 Some Basic Concepts from Set Theory 520 9.1.2 Logic Operations Involving Binary Images 522 9.2 Dilation and Erosion 523 9.2.1 Dilation 523 9.2.2 Erosion 525 9.3 Opening and Closing 528 9.4 The hit-or-Miss Transformation 532 9.5 Some Basic Morphological Algorithms 534 9.5.1 Boundary Extraction 534 9.5.2 Region Filling 535 9.5.3 Extraction of Connected Components 536 9.5.4 Convex Hull 539 9.5.6 Thickening 541 9.5.7 Skeletons 543 9.5.8 Pruning 545 9.5.9 Summary of Morphological Operations on Binary Images 547 9.6 Extensions to Gray-Scale Images 550 9.6.1 Dilation 550 9.6.2 Erosion 552 9.6.3 Opening and Closing 554 9.6.4 Some Applications of Gray-Scale Morphology 556 Summary 560 References and Further Reading 560 Problems 560
8.4.2 LZW Coding 446 8.4.3 Bit-Plane Coding 448 8.4.4 Lossless Predictive Coding 456 8.5 Lossy Compression 459 8.5.1 Lossy Predictive Coding 459 8.5.2 Transform Coding 467 8.5.3 Wavelet Coding 486 8.6 Image Compression Standards 492 8.6.1 Binary Image Compression Standards 493 8.6.2 Continuous Tone Still Image Compression Standards 498 8.6.3 Video Compression Standards 510 Summary 513 References and Further Reading 513 Problems 514 9 Morphological Image Processing 519 9.1 Preliminaries 520 9.1.1 Some Basic Concepts from Set Theory 520 9.1.2 Logic Operations Involving Binary Images 522 9.2 Dilation and Erosion 523 9.2.1 Dilation 523 9.2.2 Erosion 525 9.3 Opening and Closing 528 9.4 The Hit-or-Miss Transformation 532 9.5 Some Basic Morphological Algorithms 534 9.5.1 Boundary Extraction 534 9.5.2 Region Filling 535 9.5.3 Extraction of Connected Components 536 9.5.4 Convex Hull 539 9.5.5 Thinning 541 9.5.6 Thickening 541 9.5.7 Skeletons 543 9.5.8 Pruning 545 9.5.9 Summary of Morphological Operations on Binary Images 547 9.6 Extensions to Gray-Scale Images 550 9.6.1 Dilation 550 9.6.2 Erosion 552 9.6.3 Opening and Closing 554 9.6.4 Some Applications of Gray-Scale Morphology 556 Summary 560 References and Further Reading 560 Problems 560 xii ■ Contents GONZFM-i-xxii. 5-10-2001 14:22 Page xii
Contents xlll Image segmentation 567 10.1 Detection of Discontinuities 568 10.1.1 Point Detection 569 10.1.2 Line Detection 570 10.1.3 Edge Detection 572 10.2 Edge Linking and Boundary Detection 585 10.2.2 Global Processing via the Hough Transform 587 10.2.3 Global Processing via Graph-Theoretic Techniques 591 10.3 Thresholding 595 10.3.1 Foundation 595 10.3.2 The Role of lllumination 596 10.3.3 Basic Global Thresholding 598 10.3.4 Basic Adaptive Thresholding 600 10.3.5 Optimal Global and Adaptive Thresholding 602 10.3.6 Use of Boundary Characteristics for Histogram Improveme and Local Thresholding 608 10.3.7 Thresholds Based on Several Variables 611 10.4 Region-Based Segmentation 61 10.4.1 Basic Formulation 612 10.4.2 Region Growing 613 10.4.3 Region Splitting ergin 5 10.5 Segmentation by Morphological Watersheds 617 10.5.1 Basic Concepts 617 10.5.2 Dam Construction 620 10.5.3 Watershed Segmentation Algorithm 622 10.5.4 The Use of Markers 624 10.6 The Use of Motion in Segmentation 626 0.6.1 Spatial Techniques 626 10.6.2 Frequency Domain Techniques 630 References and Further Reading 634 Problems 636 Representation and Description 643 11.1 Representation 644 11.1.1 Chain Codes 644 11.1.2 Polygonal Approximations 646 11.1.3 Signatures 648 11.1.4 Boundary Segments 649 11.1.5 Skeletons 650
10 Image Segmentation 567 10.1 Detection of Discontinuities 568 10.1.1 Point Detection 569 10.1.2 Line Detection 570 10.1.3 Edge Detection 572 10.2 Edge Linking and Boundary Detection 585 10.2.1 Local Processing 585 10.2.2 Global Processing via the Hough Transform 587 10.2.3 Global Processing via Graph-Theoretic Techniques 591 10.3 Thresholding 595 10.3.1 Foundation 595 10.3.2 The Role of Illumination 596 10.3.3 Basic Global Thresholding 598 10.3.4 Basic Adaptive Thresholding 600 10.3.5 Optimal Global and Adaptive Thresholding 602 10.3.6 Use of Boundary Characteristics for Histogram Improvement and Local Thresholding 608 10.3.7 Thresholds Based on Several Variables 611 10.4 Region-Based Segmentation 612 10.4.1 Basic Formulation 612 10.4.2 Region Growing 613 10.4.3 Region Splitting and Merging 615 10.5 Segmentation by Morphological Watersheds 617 10.5.1 Basic Concepts 617 10.5.2 Dam Construction 620 10.5.3 Watershed Segmentation Algorithm 622 10.5.4 The Use of Markers 624 10.6 The Use of Motion in Segmentation 626 10.6.1 Spatial Techniques 626 10.6.2 Frequency Domain Techniques 630 Summary 634 References and Further Reading 634 Problems 636 11 Representation and Description 643 11.1 Representation 644 11.1.1 Chain Codes 644 11.1.2 Polygonal Approximations 646 11.1.3 Signatures 648 11.1.4 Boundary Segments 649 11.1.5 Skeletons 650 ■ Contents xiii GONZFM-i-xxii. 5-10-2001 14:22 Page xiii
xIv■ Contents 11.2 Boundary Descriptors 653 11.2.1 Some Simple Descriptors 653 11.2.2 Shape Numbers 654 11.2.3 Fourier Descriptors 655 11.2.4 Statistical Moments 65 11.3 Regional Descriptors 660 11.3.1 Some Simple Descriptors 661 11.3.2 Topological Descriptors 661 11.3.3 Texture 665 11.3.4 Moments of Two-Dimensional Functions 672 11.4 Use of Principal Components for Description 675 11.5 Relational Descriptors 683 Summary 687 References and Further Reading 687 Problems 689 12i Object Recognition 693 12.1 Patterns and Pattern Classes 693 12.2 Recognition Based on Decision-Theoretic Methods 698 12.2.1 Matching 698 12.2.2 Optimum Statistical Classifiers 704 12.2.3 Neural Networks 712 12.3 Structural Methods 732 12.3.1 Matching Shape Numbers 732 12.3.2 String Matching 734 12.3.3 Syntactic Recognition of Strings 73 12.3.4 Syntactic Recognition of Trees 740 Summary 750 References and Further Reading 750 Problems 750 Bibliography 755 Index 779
11.2 Boundary Descriptors 653 11.2.1 Some Simple Descriptors 653 11.2.2 Shape Numbers 654 11.2.3 Fourier Descriptors 655 11.2.4 Statistical Moments 659 11.3 Regional Descriptors 660 11.3.1 Some Simple Descriptors 661 11.3.2 Topological Descriptors 661 11.3.3 Texture 665 11.3.4 Moments of Two-Dimensional Functions 672 11.4 Use of Principal Components for Description 675 11.5 Relational Descriptors 683 Summary 687 References and Further Reading 687 Problems 689 12 Object Recognition 693 12.1 Patterns and Pattern Classes 693 12.2 Recognition Based on Decision-Theoretic Methods 698 12.2.1 Matching 698 12.2.2 Optimum Statistical Classifiers 704 12.2.3 Neural Networks 712 12.3 Structural Methods 732 12.3.1 Matching Shape Numbers 732 12.3.2 String Matching 734 12.3.3 Syntactic Recognition of Strings 735 12.3.4 Syntactic Recognition of Trees 740 Summary 750 References and Further Reading 750 Problems 750 Bibliography 755 Index 779 xiv ■ Contents GONZFM-i-xxii. 5-10-2001 14:22 Page xiv