Template Matching Techniques in Computer Vision: Theory and Practice Book

Preface ix

1 Introduction 1

1.1 Template Matching and Computer Vision 1

1.2 The Book 3

1.3 Bibliographical Remarks 7

References 8

2 The Imaging Process 9

2.1 Image Creation 9

2.1.1 Light 9

2.1.2 Gathering Light 13

2.1.3 Diffraction-limited Systems 20

2.1.4 Quantum Noise 21

2.2 Biological Eyes 23

2.2.1 The Human Eye 25

2.2.2 Alternative Designs 26

2.3 Digital Eyes 28

2.4 Digital Image Representations 33

2.4.1 The Sampling Theorem 33

2.4.2 Image Resampling 36

2.4.3 Log-polar Mapping 38

2.5 Bibliographical Remarks 40

References 41

3 Template Matching as Testing 43

3.1 Detection and Estimation 43

3.2 Hypothesis Testing 45

3.2.1 The Bayes Risk Criterion 47

3.2.2 The Neyman-Pearson Criterion 48

3.3 An Important Example 50

3.4 A Signal Processing Perspective: Matched Filters 54

3.5 Pattern Variability and the Normalized Correlation Coefficient 57

3.6 Estimation 60

3.6.1 Maximum Likelihood Estimation 61

3.6.2 Bayes Estimation 64

3.6.3 James-Stein Estimation 65

3.7 Bibliographical Remarks 70

References 71

4 Robust Similarity Estimators 73

4.1 Robustness Measures 73

4.2 M-estimators 81

4.3 L1 Similarity Measures 88

4.4 Robust Estimation of Covariance Matrices 92

4.5 Bibliographical Remarks 94

References 94

5 Ordinal Matching Measures 97

5.1 Ordinal Correlation Measures 97

5.1.1 Spearman Rank Correlation 100

5.1.2 Kendall Correlation 101

5.1.3 Bhat-Nayar Correlation 102

5.2 Non-parametric Local Transforms 104

5.2.1 The Census and Rank Transforms 104

5.2.2 Incremental Sign Correlation 107

5.3 Bibliographical Remarks 109

References 110

6 Matching Variable Patterns 113

6.1 MulticlassSynthetic Discriminant Functions 113

6.2 Advanced Synthetic Discriminant Functions 118

6.3 Non-orthogonal Image Expansion 121

6.4 Bibliographical Remarks 123

References 124

7 Matching Linear Structure: The Hough Transform 125

7.1 Getting Shapes: Edge Detection 125

7.2 The Radon Transform 129

7.3 The Hough Transform: Line and Circle Detection 132

7.4 The Generalized Hough Transform 141

7.5 Bibliographical Remarks 145

References 145

8 Low-dimensionality Representations and Matching 147

8.1 Principal Components 147

8.1.1 Probabilistic PCA 153

8.1.2 How Many Components? 155

8.2 A Nonlinear Approach: Kernel PCA 159

8.3 Independent Components 162

8.4 Linear Discriminant Analysis 167

8.4.1 Bayesian Dual Spaces 172

8.5 A Sample Application: Photographic-quality Facial Composites 173

8.6 Bibliographical Remarks 176

References 178

9 Deformable Templates 181

9.1 A Dynamic Perspective on the Hough Transform 181

9.2 Deformable Templates 184

9.3 Active Shape Models 188

9.4 Diffeomorphic Matching 192

9.5 Bibliographical Remarks 199

References 199

10 Computational Aspects of Template Matching 201

10.1 Speed 201

10.1.1 Early Jump-out 201

10.1.2 The Use of Sum Tables 203

10.1.3 Hierarchical Template Matching 204

10.1.4 Metric Inequalities 206

10.1.5 The FFT Advantage 208

10.1.6 PCA-based Speed-up 208

10.1.7 A Combined Approach 209

10.2 Precision 211

10.2.1 A Perturbative Approach 213

10.2.2 Phase Correlation 215

10.3 Bibliographical Remarks 216

References 218

11 Matching Point Sets: The Hausdorff Distance 221

11.1 Metric Pattern Spaces 221

11.2 Hausdorff Matching 224

11.3 Efficient Computation of the Hausdorff Distance 225

11.4 Partial Hausdorff Matching 228

11.5 Robustness Aspects 229

11.6 A Probabilistic Perspective 231

11.7 Invariant Moments 233

11.8 Bibliographical Remarks 234

References 235

12 Support Vector Machines and Regularization Networks 237

12.1 Learning and Regularization 237

12.2 RBF Networks 243

12.2.1 RBF Networks for Gender Recognition 244

12.3 Support Vector Machines 247

12.3.1 Improving Efficiency 254

12.3.2 Multiclass SVMs 256

12.3.3 Best Practice 258

12.4 Bibliographical Remarks 260

References 261

13 Feature Templates 263

13.1 Detecting Templates by Features 263

13.2 Parametric Feature Manifolds 269

13.3 Multiclass Pattern Rejection 272

13.4 Template Features 274

13.5 Bibliographical Remarks 278

References 279

14 Building a Multibiometric System 281

14.1 Systems 281

14.2 The Electronic Librarian 282

14.3 Score Integration 287

14.4 Rejection 290

14.5 Bibliographical Remarks 291

References 292

Appendices 293

A AnImAl: A Software Environment for Fast Prototyping 295

A.1 AnImAl: An Image Algebra 295

A.2 Image Representation and Processing Abstractions 297

A.3 The AnImAl Environment 300

A.4 Bibliographical Remarks 304

References 305

B Synthetic Oracles for Algorithm Development 307

B.1 Computer Graphics 307

B.2 Describing Reality: Flexible Rendering Languages 312

B.3 Bibliographical Remarks 316

References 317

C On Evaluation 319

C.1 A Note on Performance Evaluation 319

C.2 Training a Classifier 321

C.3 Analyzing the Performance of a Classifier 325

C.4 Evaluating a Technology 330

C.5 Bibliographical Remarks 333

References 333

Index 335