Guide to Signals and Patterns in Image Processing: Foundations, Methods and Applications
By Apurba Das
Contents
1 Introduction to Digital Image …………………………………………………………. 1
1.1 Formation of an Image …………………………………………………………….. 1
1.2 Definition of Signal …………………………………………………………………. 3
1.3 Analog and Digital Image as 2D Signal ……………………………………… 6
1.3.1 Continuous Time Continuous Valued Electrical Signal ……… 7
1.3.2 Continuous Space Continuous Intensity (CSCI) Image ……… 7
1.3.3 Sampling: Discrete Time Continuous Valued (DTCV)
Electrical Signal …………………………………………………………… 8
1.3.4 Concept of Sampling in Images (2D Signal) ……………………. 9
1.3.5 Quantization: Discrete Time Discrete Valued (DTDV)
Electrical Signal …………………………………………………………… 10
1.3.6 Quantization in Images (2D Signal) ……………………………….. 12
1.3.7 Encoding in Images (2D Signal) …………………………………….. 14
1.4 Relationships Between Pixels …………………………………………………… 14
1.4.1 Neighborhood ……………………………………………………………… 14
1.4.2 Adjacency ……………………………………………………………………. 16
1.4.3 Distance Measures ……………………………………………………….. 16
1.5 Geometric Transformations ……………………………………………………… 18
1.5.1 Translation …………………………………………………………………… 18
1.5.2 Scaling ………………………………………………………………………… 21
1.5.3 Rotation ………………………………………………………………………. 22
1.5.4 Homogeneous Transformation ……………………………………….. 25
1.5.5 Concatenation of Transformation …………………………………… 27
1.5.6 Affine Transformation …………………………………………………… 30
1.6 Convolution ……………………………………………………………………………. 31
1.6.1 Transformed Domain Simplicity …………………………………….. 33
1.6.2 2D Convolution: Convolution in Image Processing ………….. 35
1.7 Correlation …………………………………………………………………………….. 36
1.7.1 Case Study: Pattern (Shape Feature) Matching Between
Two Objects Using Cross-Correlation …………………………….. 37
1.8 MATLAB Codes …………………………………………………………………….. 40
1.8.1 Sampling of a Sweep Image ………………………………………….. 40
1.8.2 Resolution of Image ……………………………………………………… 40
1.8.3 Quantization of Image …………………………………………………… 41
1.8.4 Correlation Subroutine ………………………………………………….. 42
Reference ………………………………………………………………………………………. 42
2 Image Enhancement in Spatial Domain ………………………………………….. 43
2.1 Intensity Transformations ………………………………………………………… 44
2.1.1 Linear Transformation ………………………………………………….. 44
2.1.2 Contrast Stretching and Thresholding ……………………………… 46
2.1.3 Negative Intensity Transform ………………………………………… 46
2.1.4 Logarithmic Intensity Transformation …………………………….. 46
2.1.5 Power-Law Intensity Transform and Gamma Correction …… 47
2.2 Histogram of an Image …………………………………………………………….. 49
2.2.1 Skewness …………………………………………………………………….. 51
2.2.2 Kurtosis ………………………………………………………………………. 51
2.3 Histogram Equalization and Histogram Specification ………………….. 52
2.4 Image Smoothing ……………………………………………………………………. 58
2.4.1 Mean Filter ………………………………………………………………….. 58
2.4.2 Ordered Statistics Filter ………………………………………………… 61
2.5 Image Sharpening …………………………………………………………………… 63
2.5.1 Image Sharpening by Gradient Mask: First-Order
Derivative ……………………………………………………………………. 65
2.5.2 Image Sharpening by Laplacian mask: Second-Order
Derivative ……………………………………………………………………. 67
2.6 Image Interpolation and Resampling …………………………………………. 68
2.6.1 B-Spline Function ………………………………………………………… 72
2.6.2 Interpolation of 1D Signal by B-Spline …………………………… 74
2.6.3 Interpolation of 2D Image ……………………………………………… 80
2.7 MATLAB codes ……………………………………………………………………… 88
2.7.1 Image Transformation Without Interpolation …………………… 88
2.7.2 Image Rotation with Different Interpolation Techniques …… 89
2.7.3 Mean and Median Filter Response on Noisy Image ………….. 90
2.7.4 Image Sharpening by Laplacian Mask …………………………….. 91
Reference ………………………………………………………………………………………. 91
3 Interpretation and Processing of Image in Frequency Domain …………. 93
3.1 Concept of Frequency in Image ………………………………………………… 94
3.1.1 Fourier Series ………………………………………………………………. 94
3.1.2 Interpretation and Direction of Frequency in Image ………….. 99
3.2 Phase Congruency and Edge Detection in an Image ……………………. 100
3.3 Fourier Transform for Continuous and Discrete Time Signals ………. 106
3.3.1 Discrete Time Fourier Transform ……………………………………. 107
3.3.2 DFT and FFT ………………………………………………………………. 109
3.4 DFT of Digital Image ………………………………………………………………. 110
3.5 Translation and Scaling Properties of 2D Fourier Transform ………… 112
3.5.1 Translation: Dragging the LF (DC) Component at the
Center of the 2D Spectra ……………………………………………….. 112
3.5.2 Scaling: Space-Frequency Relationship in Image …………….. 114
3.6 Concept of Image Filtering in Frequency Domain ………………………. 120
3.7 Smoothing Filter …………………………………………………………………….. 124
3.7.1 Ideal LPF …………………………………………………………………….. 125
3.7.2 Butterworth LPF ………………………………………………………….. 126
3.7.3 Gaussian LPF ………………………………………………………………. 129
3.8 Sharpening Filter …………………………………………………………………….. 130
3.8.1 Ideal HPF ……………………………………………………………………. 132
3.8.2 Butterworth HPF ………………………………………………………….. 133
3.8.3 Gaussian HPF ………………………………………………………………. 135
3.9 Case Studies …………………………………………………………………………… 136
3.9.1 Importance of Phase over Amplitude in DFT Spectrum …….. 136
3.9.2 DFT over DFT …………………………………………………………….. 138
3.10 Matlab Codes ……………………………………………………………………….. 143
3.10.1 Ideal 2D Filters in Frequency Domain …………………………… 143
3.10.2 Subroutine of 2D Butterworth Filter ……………………………… 145
3.10.3 Subroutine of 2D Gaussian Filter …………………………………. 145
3.10.4 Importance of Phase over Amplitude in Image Spectrum … 146
References ……………………………………………………………………………………… 147
4 Color Science and Color Technology ……………………………………………….. 149
4.1 Light and Primary Colors …………………………………………………………. 149
4.1.1 Device-Dependent Primary Colors: Additive Color Model … 151
4.1.2 Device-Dependent Primary Colors: Subtractive Color
Model …………………………………………………………………………. 152
4.1.3 Reflectance and Its Spectra ……………………………………………. 154
4.2 Psycho-Visual Color: Human Vision System ……………………………… 158
4.2.1 Photoreceptors: Rods and Cones ……………………………………. 158
4.3 Color Description Systems ………………………………………………………. 161
4.3.1 Munsell System ……………………………………………………………. 162
4.3.2 Pantone System ……………………………………………………………. 163
4.4 Colorimetry: CIE Standards ……………………………………………………… 166
4.4.1 CIE Standard Illuminant ……………………………………………….. 167
4.4.2 CIE Standard Observer …………………………………………………. 169
4.5 CIE Color Spaces ……………………………………………………………………. 170
4.5.1 Non-uniform Perceptual Color Spaces ……………………………. 171
4.5.2 Uniform Perceptual Color Spaces …………………………………… 174
4.5.3 Xerox/YES Color Space ……………………………………………….. 176
4.6 Halftone Screening ………………………………………………………………….. 177
4.6.1 Moire Pattern and Screen Angle …………………………………….. 178
4.6.2 Growth Sequence of Halftone Dot ………………………………….. 179
4.7 Color Management ………………………………………………………………….. 181
4.7.1 Profile Connection Space (PCS) …………………………………….. 184
4.7.2 Gamut Mapping …………………………………………………………… 184
4.7.3 Rendering Intents …………………………………………………………. 185
4.8 Matlab Codes …………………………………………………………………………. 189
4.8.1 Halftone Screening by Error Diffusion ……………………………. 189
4.8.2 Error Diffusion Subroutine ……………………………………………. 190
Reference ………………………………………………………………………………………. 190
5 Wavelets: Multiresolution Image Processing ……………………………………. 191
5.1 Introduction ……………………………………………………………………………. 191
5.2 Short-Time Fourier Transform ………………………………………………….. 191
5.2.1 Continuous-time STFT …………………………………………………. 194
5.2.2 Discrete-time STFT ………………………………………………………. 194
5.2.3 Spectrogram ………………………………………………………………… 194
5.2.4 Limitation ……………………………………………………………………. 195
5.3 Wavelet Function and Scaling Function …………………………………….. 196
5.4 Wavelet Series ………………………………………………………………………… 202
5.5 Discrete Wavelet Transform and Multiresolution analysis ……………. 203
5.5.1 Analysis Filter Bank ……………………………………………………… 205
5.5.2 Synthesis Filter Bank ……………………………………………………. 206
5.6 Image Decomposition Using DWT ……………………………………………. 207
5.6.1 Concept of 2D Signal Decomposition Using Analysis
Filter …………………………………………………………………………… 207
5.6.2 DWT on Images (Fig. 5.16) …………………………………………… 208
5.7 Image Compression Using DWT: EZW Encoding ………………………. 210
5.7.1 Relationship Between Decomposed Sub-bands ………………… 211
5.7.2 Successive Approximation Quantization in EZW …………….. 212
5.7.3 EZW Encoding Algorithm …………………………………………….. 213
5.7.4 Image Compression using EZW: An Example …………………. 214
5.7.5 Experimental Results of Image Compression Using EZW …. 216
5.8 MATLAB Programs ………………………………………………………………… 218
5.8.1 Haar Scaling and Wavelet Function ………………………………… 218
5.8.2 Wavelet Series Expansion ……………………………………………… 219
5.8.3 Wavelet Decomposition of Image (4 level) ……………………… 220
5.8.4 Image Compression by EZW Encoding …………………………… 221
References ……………………………………………………………………………………… 221
6 Compression and Encoding of Image: Image Formats …………………….. 223
6.1 Redundancy: Fundamentals of Compression ………………………………. 224
6.2 Entropy: The Measure of Information ……………………………………….. 226
6.3 Entropy Coding ………………………………………………………………………. 227
6.3.1 Shannon–Fano Coding ………………………………………………….. 228
6.3.2 Huffman Coding ………………………………………………………….. 229
6.4 Lossy Compression …………………………………………………………………. 230
6.4.1 Block Truncation Compression (BTC) ……………………………. 230
6.4.2 Vector Quantization Compression (VQC) ……………………….. 233
6.5 Lossless Compression ……………………………………………………………… 236
6.5.1 Run Length Coding (RLC) ……………………………………………. 236
6.5.2 Block Coding ………………………………………………………………. 237
6.6 QPAC: Quality Preserving Adaptive Compression ……………………… 238
6.7 Some Common Image Formats ………………………………………………… 239
6.7.1 C++ Code for Reading BMP Image ……………………………….. 240
6.7.2 JPEG ………………………………………………………………………….. 245
6.7.3 GIF …………………………………………………………………………….. 254
6.8 Matlab Codes and Pseudocodes ………………………………………………… 258
6.8.1 Block Truncation Compression (BTC) ……………………………. 258
6.8.2 JPEG Compression ………………………………………………………. 261
6.8.3 GIF: LZW Compression ……………………………………………….. 266
6.8.4 GIF: LZW Decompression ……………………………………………. 267
References ……………………………………………………………………………………… 267
7 Morphology-Based Image Processing ……………………………………………… 269
7.1 Basics of Set Theory ……………………………………………………………….. 269
7.2 Logic Operations on Binary Images ………………………………………….. 271
7.3 Dilation and Erosion ……………………………………………………………….. 273
7.3.1 Dilation ………………………………………………………………………. 273
7.3.2 Erosion ……………………………………………………………………….. 276
7.4 Opening and Closing ……………………………………………………………….. 279
7.5 Hit–Miss Transform ………………………………………………………………… 280
7.6 Morphological Algorithms for Feature Extraction ………………………. 280
7.6.1 Boundary Extraction …………………………………………………….. 282
7.6.2 Region Filling ……………………………………………………………… 283
7.6.3 Pixel Connectivity ………………………………………………………… 284
7.6.4 Convex Hull ………………………………………………………………… 285
7.6.5 Thinning ……………………………………………………………………… 286
7.6.6 Thickening ………………………………………………………………….. 288
7.6.7 Object Skeletons ………………………………………………………….. 289
7.6.8 Pruning ……………………………………………………………………….. 290
7.7 Case Studies …………………………………………………………………………… 293
7.7.1 Boundary Detection ……………………………………………………… 293
7.7.2 Region Filling ……………………………………………………………… 295
7.7.3 Binary Skeleton ……………………………………………………………. 295
7.8 MATLAB Codes …………………………………………………………………….. 296
7.8.1 Dilation ………………………………………………………………………. 296
7.8.2 Erosion ……………………………………………………………………….. 297
7.8.3 Boundary Detection ……………………………………………………… 297
Reference ………………………………………………………………………………………. 298
8 Patterns in Images and Their Applications ……………………………………… 299
8.1 Introduction to Pattern …………………………………………………………….. 299
8.2 Features …………………………………………………………………………………. 300
8.2.1 Feature Selection and Extraction ……………………………………. 301
8.3 Principal Component Analysis ………………………………………………….. 302
8.3.1 Algorithm of PCA ………………………………………………………… 303
8.3.2 Application of PCA in Face Recognition …………………………. 305
8.3.3 Limitations of PCA-Based Face Recognition …………………… 307
8.4 Face Detection Based on Haar-Like Features ……………………………… 308
8.5 Elastic Branch Graph Matching and Face Manifold …………………….. 311
8.6 Decision Tree and Feature Hierarchy ………………………………………… 314
8.6.1 Information Gain ………………………………………………………….. 314
8.6.2 Information Gain Ratio …………………………………………………. 315
8.6.3 Selection of Optimized Set of Features …………………………… 316
8.6.4 Feature Hierarchy for Gabor Features in Face
Recognition …………………………………………………………………. 317
8.7 Scale Invariant Feature Transform …………………………………………….. 319
8.7.1 Scale–Space Concept: Multiscale Singularity Tree …………… 320
8.7.2 SIFT: Representation of Image in Scale–Space ………………… 322
8.7.3 SIFT: Detection of Local Scale–Space Extrema ……………….. 324
8.7.4 SIFT: Accurate Keypoint Localization ……………………………. 325
8.7.5 SIFT: Orientation Assignment ……………………………………….. 326
8.7.6 SIFT: Keypoint Descriptor …………………………………………….. 327
8.7.7 SIFT: Results ……………………………………………………………….. 328
8.8 Histogram of Oriented Gradient ……………………………………………….. 332
8.8.1 HOG: Dividing Image into Blocks …………………………………. 333
8.8.2 HOG: Quantization of Gradient Histogram ……………………… 333
8.8.3 HOG: Feature Vector Synthesis ……………………………………… 335
8.8.4 HOG: Design of Classifier by Training …………………………… 335
8.9 Matlab Codes …………………………………………………………………………. 336
8.9.1 PCA of a 2D data set …………………………………………………….. 336
8.9.2 Scale–Space: Multiscale Singularity Tree ……………………….. 337
Reference ………………………………………………………………………………………. 338
9 Psycho-visual pattern recognition: Computer Vision ………………………. 341
9.1 Introduction ……………………………………………………………………………. 341
9.2 Receptive Field ………………………………………………………………………. 342
9.2.1 On-Center Off-Surround ……………………………………………….. 343
9.2.2 Off-Center On-Surround ……………………………………………….. 344
9.2.3 Edge Detection in Retinal Receptive Field ………………………. 345
9.3 Modeling of Retinal Receptive Field from Optical Illusions …………. 347
9.3.1 Optical Illusions: A study ………………………………………………. 347
9.3.2 Illustration of the Illusions in Terms of DoG Model of
Retinal Receptive Field …………………………………………………. 348
9.4 Three Levels of Psycho-Visual System for Pattern Recognition ……. 352
9.5 Neuro-Visually Inspired Figure-Ground Segregation …………………… 353
9.5.1 The Detailed Algorithm for NFGS ………………………………….. 355
9.6 “Where” and “What” Visual Pathways: Modeling in Computer
Vision ……………………………………………………………………………………. 358
References ……………………………………………………………………………………… 362
10 Appendix A: Digital Differentiation and Edge Detection ………………….. 365
10.1 Edge in an Image ……………………………………………………………………. 365
10.2 Digital Differentiation ……………………………………………………………… 366
10.2.1 Digital Differentiation of One-Dimensional (1D) Signal …… 367
10.3 Digital Differentiation for Edge Detection …………………………………. 369
10.4 Convolution and Correlation for Edge Detection ………………………… 371
10.5 Prewitt and Sobel Mask for Edge Detection of Digital Image ………. 374
10.6 Canny Edge Detector ………………………………………………………………. 375
10.6.1 Noise Reduction …………………………………………………………… 375
10.6.2 Non-Maxima Suppression …………………………………………….. 376
10.6.3 Hysteresis Thresholding ………………………………………………… 376
10.7 MATLAB Codes …………………………………………………………………….. 378
10.7.1 Digital Differentiation of 1D Signal ……………………………….. 378
10.7.2 Detection of Edges in Orthogonal Directions by Convolu-tion Interpretation of Digital Differentiation ……………………. 379
References ……………………………………………………………………………………… 381
11 Appendix B: Elementary Probability Theory …………………………………… 383
11.1 Concept of Probability …………………………………………………………….. 385
11.1.1 Random Experiments and Sample Space …………………………. 385
11.1.2 Events …………………………………………………………………………. 385
11.1.3 Probability: Understanding Approaches ………………………….. 386
11.2 Random Variable …………………………………………………………………….. 386
11.3 Mean, Variance, Skewness, and Kurtosis ……………………………………. 387
11.4 Cumulative Distribution Function …………………………………………….. 389
11.5 Probability Density Function ……………………………………………………. 392
11.5.1 Uniform PDF ……………………………………………………………….. 393
11.6 Frequently Used Probability Distribution …………………………………… 393
References ……………………………………………………………………………………… 397
12 Appendix C: Frequently Used MATLAB Functions ………………………… 399
12.1 plot() ……………………………………………………………………………………… 399
12.1.1 Syntax ………………………………………………………………………… 399
12.1.2 Description ………………………………………………………………….. 399
12.2 imshow() ……………………………………………………………………………….. 400
12.2.1 Syntax ………………………………………………………………………… 400
12.2.2 Description ………………………………………………………………….. 400
12.3 drawnow() ……………………………………………………………………………… 401
12.3.1 Syntax ………………………………………………………………………… 401
12.3.2 Description ………………………………………………………………….. 401
12.4 stairs() …………………………………………………………………………………… 401
12.5 int2str() ………………………………………………………………………………….. 402
12.5.1 Syntax ………………………………………………………………………… 402
12.5.2 Description ………………………………………………………………….. 402
12.6 conv() ……………………………………………………………………………………. 402
12.7 conv2() ………………………………………………………………………………….. 403
12.8 Two-Dimensional Convolution …………………………………………………. 403
12.9 ginput() ………………………………………………………………………………….. 404
12.10 bitget() …………………………………………………………………………………. 405
12.11 bitset() …………………………………………………………………………………. 405
12.12 dec2bin() ……………………………………………………………………………… 406
12.12.1 Syntax ………………………………………………………………………. 406
12.12.2 Description ………………………………………………………………… 406
12.13 fft2() ……………………………………………………………………………………. 407
12.13.1 Syntax ………………………………………………………………………. 407
12.13.2 Description ………………………………………………………………… 407
12.14 fftshift() ……………………………………………………………………………….. 407
12.14.1 Syntax ………………………………………………………………………. 407
12.14.2 Description ………………………………………………………………… 408
12.15 wavefun() …………………………………………………………………………….. 409
12.15.1 Syntax ………………………………………………………………………. 409
12.15.2 Description ………………………………………………………………… 410
12.16 Fourier Synthesizer GUI ………………………………………………………… 412
Reference ………………………………………………………………………………………. 412
Index …………………………………………………………………………………………………… 413