Correlation Pattern Recognition

Correlation is a robust and general technique for pattern recognition and is used in many applications, such as automatic target recognition, biometric recognition and optical character recognition. The design, analysis and use of correlation pattern recognition algorithms requires background information, including linear systems theory, random variables and processes, matrix/vector methods, detection and estimation theory, digital signal processing and optical processing. This 2005 book provides a needed review of this diverse background material and develops the signal processing theory, the pattern recognition metrics, and the practical application know-how from basic premises. It shows both digital and optical implementations. It also contains technology presented by the team that developed it and includes case studies of significant interest, such as face and fingerprint recognition. Suitable for graduate students taking courses in pattern recognition theory, whilst reaching technical levels of interest to the professional practitioner. Cover......Page 1 Half-Title......Page 3 Title......Page 5 Copyright......Page 6 Contents......Page 7 Preface......Page 9 1 Introduction......Page 15 1.1 Pattern recognition......Page 16 1.2 Correlation......Page 18 1.3 Organization......Page 23 2 Mathematical background......Page 27 2.1 Matrix–vector notation and basic definitions......Page 28 2.2 Basic matrix–vector operations......Page 29 2.2.1 Vector norms and the Cauchy–Schwarz inequality......Page 31 2.2.2 Linear independence, rank, matrix inverse and determinant......Page 32 2.2.3 Partitioned matrices......Page 34 2.3 Eigenvalues and eigenvectors......Page 35 2.3.1 Some properties of eigenvalues and eigenvectors of real, symmetric matrices......Page 36 2.3.2 Relationship between the eigenvalues and eigenvectors of the inner product matrices and outer product matrices......Page 37 2.4.1 Derivatives of linear and quadratic functions......Page 39 2.4.3 Constrained optimization with Lagrange multipliers......Page 40 2.4.4 Maximizing a ratio of two quadratic terms......Page 41 2.5.1 Basics of probability theory......Page 42 2.5.2 Random variables......Page 44 2.5.3 Probability density functions......Page 45 2.5.4 Expectation......Page 49 2.5.5 Two random variables......Page 50 2.5.6 Random vectors......Page 55 2.5.7 Linear transformations......Page 58 2.6 Chapter summary......Page 60 3.1 Basic systems......Page 62 3.2 Signal representation......Page 64 3.3 Linear shift-invariant systems......Page 69 3.3.1 Impulse response, convolution, and correlation......Page 70 3.3.2 Two-dimensional LSI systems......Page 73 3.4.1 Fourier series of a periodic signal......Page 75 3.4.2 One-dimensional CTFT......Page 76 3.4.3 Continuous-time Fourier transform properties......Page 77 3.4.4 Convolution and correlation using the CTFT......Page 79 3.4.5 Auto-correlation function peak......Page 81 3.4.7 Two-dimensional CTFT......Page 82 3.4.8 Two-dimensional CTFT properties......Page 84 3.5 Sampling theory......Page 88 3.5.1 Sampling in two dimensions......Page 94 3.6.1 Discrete Fourier transform......Page 96 3.6.2 Fast Fourier transform......Page 99 3.6.3 Correlation and convolution via FFT......Page 103 3.6.4 Overlap-add and overlap-save methods......Page 106 3.7 Random signal processing......Page 109 3.7.1 Random process characterization......Page 111 3.7.2 Second-order characterizations......Page 112 3.7.3 Gaussian processes......Page 115 3.7.4 Filtering of random processes......Page 117 3.8 Chapter summary......Page 120 4.1 Binary hypothesis testing......Page 122 4.1.1 Minimum probability of error detection......Page 124 4.1.2 Binary hypotheses testing with Gaussian noise......Page 125 4.1.3 Receiver operating curves......Page 130 4.2.1 MAP classifier......Page 132 4.2.2 Additive Gaussian noise model......Page 133 4.2.3 Error probability for 2-class case......Page 134 4.3 Estimation theory......Page 136 4.3.1 Maximum likelihood estimation......Page 137 4.3.2 Other estimators......Page 139 4.3.3 Error rate estimation......Page 141 4.4 Chapter summary......Page 142 5 Correlation filter basics......Page 144 5.1 Matched filter......Page 145 5.1.1 Known signal in additive noise......Page 146 5.1.2 Maximal SNR filter......Page 147 5.1.3 White noise case......Page 151 5.1.4 Colored noise......Page 152 5.2 Correlation implementation......Page 153 5.2.1 VanderLugt correlator......Page 154 5.2.2 Digital correlation......Page 158 5.3.1 Signal-to-noise ratio......Page 162 5.3.2 Peak sharpness measures......Page 163 5.3.3 Optimal tradeoff correlation filters......Page 165 5.4 Correlation filter variants......Page 169 5.4.1 Phase-only filters......Page 170 5.4.2 Binary phase-only filters......Page 178 5.4.3 Saturated filters......Page 182 5.4.4 Constrained filters......Page 186 5.4.5 Binarized correlations......Page 190 5.5 Minimum Euclidean distance optimal filter......Page 198 5.6 Non-overlapping noise......Page 200 5.6.1 Effect of constant background......Page 201 5.6.2 Non-overlapping noise......Page 202 5.6.3 Optimal detection strategy for non-overlapping noise......Page 203 5.7 Chapter summary......Page 206 6 Advanced correlation filters......Page 210 6.1.1 A basic coordinate transform method......Page 212 6.1.2 Circular harmonic functions......Page 215 6.2 Composite correlation filters......Page 219 6.2.1 Early synthetic discriminant function (SDF) filters: The projection SDF filter......Page 220 6.2.2 Minimum average correlation energy filter......Page 223 6.2.3 Minimum variance synthetic discriminant function......Page 225 6.2.4 Designing distortion tolerant filters without hard constraints......Page 228 6.2.5 Relationship between the MACH filter and SDF filters......Page 235 6.2.6 Optimal tradeoff filters......Page 236 6.2.7 Lock-and-tumbler filters......Page 238 6.3 Distance classifier correlation filters......Page 239 6.3.1 Designing the classifier transform......Page 242 6.3.2 Calculating distances with DCCFs......Page 244 6.4 Polynomial correlation filters......Page 245 6.4.1 Derivation of the solution......Page 246 6.4.2 PCF extensions......Page 248 6.5 Basic performance prediction techniques......Page 249 6.6 Advanced pattern recognition criteria......Page 253 6.7 Chapter summary......Page 255 7.1 Introduction......Page 258 7.2.1 Description of plane electromagnetic waves......Page 260 7.2.2 Diffraction of light and the Fourier transform......Page 262 7.2.3 Coherence, interference, and polarized light......Page 269 7.2.4 Jones calculus for fully polarized light......Page 273 7.2.5 Another formalism for polarized and partially polarized light......Page 285 7.2.6 Which formalism to use?......Page 291 7.3.2 Birefringence (Jones matrix) SLMs......Page 292 7.3.3 Direct action SLMs......Page 293 7.4 Calibration of SLMs and their drive circuitry......Page 294 7.4.1 Interference fringe analysis for uniform and non-uniform SLMs......Page 295 7.4.2 "Depth" fringe analysis for spatially variant SLMs......Page 302 7.4.3 Establishing synchronism of D/A/D mappings......Page 303 7.5 Analytic signal......Page 305 8.1 Introduction......Page 309 8.2 History, formulas, and philosophy......Page 314 8.2.1 Nomenclature......Page 316 8.2.2 Getting specific to optical correlation......Page 318 8.3 Physical view of the OCPR process......Page 322 8.3.1 Mathematical representation of SLM action......Page 323 8.3.2 Bumpy-lens analogy......Page 326 8.4.1 Variance in magnitude, intensity, and measurement......Page 329 8.4.2 Known problems with the DFT representation......Page 333 8.5.1 The statistical pattern recognition metrics......Page 334 8.5.3 Fisher ratio......Page 335 8.5.4 Area under ROC curve......Page 336 8.5.6 Bayes error......Page 337 8.5.7 Nonlinearities in filter design and in metrics......Page 338 8.6 Gradient concepts......Page 339 8.7 Optimization of the metrics......Page 342 8.7.1 Intensity......Page 343 8.7.2 Magnitude SNR......Page 344 8.7.4 Peak-to-correlation energy (PCE)......Page 345 8.8 SLMs and their limited range......Page 346 8.8.1 Continuous mode......Page 347 Magnitude-only (1-DOF)......Page 348 Coupled SLMs......Page 349 8.8.2 Discrete mode......Page 352 8.8.3 Unit disk......Page 353 8.9 Algorithm for optical correlation filter design......Page 354 8.10.2 Specifying lot uniformity......Page 356 8.10.4 MED maps......Page 358 8.10.5 MED map for a uniform SLM......Page 359 8.10.6 MED maps for a spatially variant SLM......Page 361 8.11 Some heuristic filters......Page 363 8.12 Chapter summary......Page 369 9.1 Recognition of targets in SAR imagery......Page 371 9.1.1 SAR ATR using MACH and DCCF filters......Page 372 9.1.2 MACH filter design and performance analysis......Page 373 9.1.3 Performance improvements using DCCFs......Page 381 9.1.4 Clutter tests of the MACH/DCCF algorithms for SAR ATR......Page 387 9.2 Face verification using correlation filters......Page 391 9.3 Chapter summary......Page 396 References......Page 397 Index......Page 402 Cover 1 Half-Title 3 Title 5 Copyright 6 Contents 7 Preface 9 1 Introduction 15 1.1 Pattern recognition 16 1.2 Correlation 18 1.3 Organization 23 2 Mathematical background 27 2.1 Matrix–vector notation and basic definitions 28 2.2 Basic matrix–vector operations 29 2.2.1 Vector norms and the Cauchy–Schwarz inequality 31 2.2.2 Linear independence, rank, matrix inverse and determinant 32 2.2.3 Partitioned matrices 34 2.3 Eigenvalues and eigenvectors 35 2.3.1 Some properties of eigenvalues and eigenvectors of real, symmetric matrices 36 2.3.2 Relationship between the eigenvalues and eigenvectors of the inner product matrices and outer product matrices 37 2.4 Quadratic criterion optimization 39 2.4.1 Derivatives of linear and quadratic functions 39 2.4.2 System of linear equations and least squares 40 2.4.3 Constrained optimization with Lagrange multipliers 40 2.4.4 Maximizing a ratio of two quadratic terms 41 2.5 Probability and random variables 42 2.5.1 Basics of probability theory 42 2.5.2 Random variables 44 2.5.3 Probability density functions 45 2.5.4 Expectation 49 2.5.5 Two random variables 50 2.5.6 Random vectors 55 2.5.7 Linear transformations 58 2.6 Chapter summary 60 3 Linear systems and filtering theory 62 3.1 Basic systems 62 3.2 Signal representation 64 3.3 Linear shift-invariant systems 69 3.3.1 Impulse response, convolution, and correlation 70 3.3.2 Two-dimensional LSI systems 73 3.4 Continuous-time Fourier analysis 75 3.4.1 Fourier series of a periodic signal 75 3.4.2 One-dimensional CTFT 76 3.4.3 Continuous-time Fourier transform properties 77 3.4.4 Convolution and correlation using the CTFT 79 3.4.5 Auto-correlation function peak 81 3.4.6 Periodic or circular convolution 82 3.4.7 Two-dimensional CTFT 82 3.4.8 Two-dimensional CTFT properties 84 3.5 Sampling theory 88 3.5.1 Sampling in two dimensions 94 3.6 Fourier transform of DT signals 96 3.6.1 Discrete Fourier transform 96 3.6.2 Fast Fourier transform 99 3.6.3 Correlation and convolution via FFT 103 3.6.4 Overlap-add and overlap-save methods 106 3.7 Random signal processing 109 3.7.1 Random process characterization 111 3.7.2 Second-order characterizations 112 3.7.3 Gaussian processes 115 3.7.4 Filtering of random processes 117 3.8 Chapter summary 120 4 Detection and estimation 122 4.1 Binary hypothesis testing 122 4.1.1 Minimum probability of error detection 124 4.1.2 Binary hypotheses testing with Gaussian noise 125 4.1.3 Receiver operating curves 130 4.2 Multiple hypotheses testing 132 4.2.1 MAP classifier 132 4.2.2 Additive Gaussian noise model 133 4.2.3 Error probability for 2-class case 134 4.3 Estimation theory 136 4.3.1 Maximum likelihood estimation 137 4.3.2 Other estimators 139 4.3.3 Error rate estimation 141 4.4 Chapter summary 142 5 Correlation filter basics 144 5.1 Matched filter 145 5.1.1 Known signal in additive noise 146 5.1.2 Maximal SNR filter 147 5.1.3 White noise case 151 5.1.4 Colored noise 152 5.2 Correlation implementation 153 5.2.1 VanderLugt correlator 154 5.2.2 Digital correlation 158 5.3 Correlation performance measures 162 5.3.1 Signal-to-noise ratio 162 5.3.2 Peak sharpness measures 163 5.3.3 Optimal tradeoff correlation filters 165 5.4 Correlation filter variants 169 5.4.1 Phase-only filters 170 5.4.2 Binary phase-only filters 178 5.4.3 Saturated filters 182 5.4.4 Constrained filters 186 5.4.5 Binarized correlations 190 5.5 Minimum Euclidean distance optimal filter 198 5.6 Non-overlapping noise 200 5.6.1 Effect of constant background 201 5.6.2 Non-overlapping noise 202 5.6.3 Optimal detection strategy for non-overlapping noise 203 5.7 Chapter summary 206 6 Advanced correlation filters 210 6.1 In-plane distortion invariance 212 6.1.1 A basic coordinate transform method 212 6.1.2 Circular harmonic functions 215 6.2 Composite correlation filters 219 6.2.1 Early synthetic discriminant function (SDF) filters: The projection SDF filter 220 6.2.2 Minimum average correlation energy filter 223 6.2.3 Minimum variance synthetic discriminant function 225 6.2.4 Designing distortion tolerant filters without hard constraints 228 6.2.5 Relationship between the MACH filter and SDF filters 235 6.2.6 Optimal tradeoff filters 236 6.2.7 Lock-and-tumbler filters 238 6.3 Distance classifier correlation filters 239 6.3.1 Designing the classifier transform 242 6.3.2 Calculating distances with DCCFs 244 6.4 Polynomial correlation filters 245 6.4.1 Derivation of the solution 246 6.4.2 PCF extensions 248 6.5 Basic performance prediction techniques 249 6.6 Advanced pattern recognition criteria 253 6.7 Chapter summary 255 7 Optical considerations 258 7.1 Introduction 258 7.2 Some basic electromagnetics 260 7.2.1 Description of plane electromagnetic waves 260 7.2.2 Diffraction of light and the Fourier transform 262 7.2.3 Coherence, interference, and polarized light 269 7.2.4 Jones calculus for fully polarized light 273 7.2.5 Another formalism for polarized and partially polarized light 285 7.2.6 Which formalism to use? 291 7.3 Light modulation 292 7.3.1 Architecture and diffraction from a Cartesian SLM 292 7.3.2 Birefringence (Jones matrix) SLMs 292 7.3.3 Direct action SLMs 293 7.3.4 Optically addressed and electrically addressed SLMs 294 7.4 Calibration of SLMs and their drive circuitry 294 7.4.1 Interference fringe analysis for uniform and non-uniform SLMs 295 7.4.2 "Depth" fringe analysis for spatially variant SLMs 302 7.4.3 Establishing synchronism of D/A/D mappings 303 7.5 Analytic signal 305 8 Limited-modulation filters 309 8.1 Introduction 309 8.2 History, formulas, and philosophy 314 8.2.1 Nomenclature 316 8.2.2 Getting specific to optical correlation 318 8.3 Physical view of the OCPR process 322 8.3.1 Mathematical representation of SLM action 323 8.3.2 Bumpy-lens analogy 326 8.4 Model, including circular Gaussian noise 329 8.4.1 Variance in magnitude, intensity, and measurement 329 8.4.2 Known problems with the DFT representation 333 8.5 Metrics and metric potential 334 8.5.1 The statistical pattern recognition metrics 334 8.5.2 Rayleigh quotient 335 8.5.3 Fisher ratio 335 8.5.4 Area under ROC curve 336 8.5.5 Expected information 337 8.5.6 Bayes error 337 8.5.7 Nonlinearities in filter design and in metrics 338 8.6 Gradient concepts 339 8.7 Optimization of the metrics 342 8.7.1 Intensity 343 8.7.2 Magnitude SNR 344 8.7.3 Statistical pattern recognition metrics 345 8.7.4 Peak-to-correlation energy (PCE) 345 8.8 SLMs and their limited range 346 8.8.1 Continuous mode 347 Phase-only (1-DOF) 348 Magnitude-only (1-DOF) 348 Coupled SLMs 349 8.8.2 Discrete mode 352 8.8.3 Unit disk 353 8.9 Algorithm for optical correlation filter design 354 8.10 Some practical points 356 8.10.1 Storage and representation of filters 356 8.10.2 Specifying lot uniformity 356 8.10.3 Choosing a finite subset of filter SLM values 358 8.10.4 MED maps 358 8.10.5 MED map for a uniform SLM 359 8.10.6 MED maps for a spatially variant SLM 361 8.11 Some heuristic filters 363 8.12 Chapter summary 369 9 Application of correlation filters 371 9.1 Recognition of targets in SAR imagery 371 9.1.1 SAR ATR using MACH and DCCF filters 372 9.1.2 MACH filter design and performance analysis 373 9.1.3 Performance improvements using DCCFs 381 9.1.4 Clutter tests of the MACH/DCCF algorithms for SAR ATR 387 9.2 Face verification using correlation filters 391 9.3 Chapter summary 396 References 397 Index 402 "Correlation is a robust and general technique for pattern recognition and is used in many applications, such as automatic target recognition, biometric recognition and optical character recognition. The design, analysis, and use of correlation pattern recognition algorithms require background information, including linear systems theory, random variables and processes, matrix/vector methods, detection and estimation theory, digital signal processing, and optical processing." "This book provides a needed review of this diverse background material and develops the signal processing theory, the pattern recognition metrics, and the practical application know-how from basic premises. It shows both digital and optical implementations. It also contains state-of-the-art technology presented by the team that developed it and includes case studies of significant current interest, such as face and target recognition." This book provides a needed review of the diverse background material needed for correlation pattern recognition, developing the signal processing theory, the pattern recognition metrics, and the practical application know-how from basic premises. Includes case studies of current interest, such as face and fingerprint recognition. For graduate students and practitioners