Pattern Theory: The Stochastic Analysis of Real-World Signals (Applying Mathematics)

This book is an introduction to pattern theory, the theory behind the task of analyzing types of signals that the real world presents to us. It deals with generating mathematical models of the patterns in those signals and algorithms for analyzing the data based on these models. It exemplifies the view of applied mathematics as starting with a collection of problems from some area of science and then seeking the appropriate mathematics for clarifying the experimental data and the underlying processes of producing these data. An emphasis is placed on finding the mathematical and, where needed, computational tools needed to reach those goals, actively involving the reader in this process. Among other examples and problems, the following areas are treated: music as a realvalued function of continuous time, character recognition, the decomposition of an image into regions with distinct colors and textures, facial recognition, and scaling effects present in natural images caused by their statistical selfsimilarity. Contents......Page 8 Preface......Page 10 Notation......Page 12 0.1 The Manifesto of Pattern Theory......Page 14 0.2 The Basic Types of Patterns......Page 18 0.3 Bayesian Probability Theory: Pattern Analysis and Pattern Synthesis......Page 22 1. English Text and Markov Chains......Page 30 1.1 Basics I: Entropy and Information......Page 34 1.2 Measuring the n-gram Approximation with Entropy......Page 39 1.3 Markov Chains and the n-gram Models......Page 42 1.4 Words......Page 52 1.5 Word Boundaries via Dynamic Programming and Maximum Likelihood......Page 58 1.6 Machine Translation via Bayes' Theorem......Page 61 1.7 Exercises......Page 64 2. Music and Piecewise Gaussian Models......Page 74 2.1 Basics III: Gaussian Distributions......Page 75 2.2 Basics IV: Fourier Analysis......Page 81 2.3 Gaussian Models for Single Musical Notes......Page 85 2.4 Discontinuities in One-Dimensional Signals......Page 92 2.5 The Geometric Model for Notes via Poisson Processes......Page 99 2.6 Related Models......Page 104 2.7 Exercises......Page 113 3. Character Recognition and Syntactic Grouping......Page 124 3.1 Finding Salient Contours in Images......Page 126 3.2 Stochastic Models of Contours......Page 135 3.3 The Medial Axis for Planar Shapes......Page 147 3.4 Gestalt Laws and Grouping Principles......Page 155 3.5 Grammatical Formalisms......Page 160 3.6 Exercises......Page 176 4. Image Texture, Segmentation and Gibbs Models......Page 186 4.1 Basics IX: Gibbs Fields......Page 189 4.2 (u + v)-Models for Image Segmentation......Page 199 4.3 Sampling Gibbs Fields......Page 208 4.4 Deterministic Algorithms to Approximate the Mode of a Gibbs Field......Page 215 4.5 Texture Models......Page 227 4.6 Synthesizing Texture via Exponential Models......Page 234 4.7 Texture Segmentation......Page 241 4.8 Exercises......Page 247 5. Faces and Flexible Templates......Page 262 5.1 Modeling Lighting Variations......Page 266 5.2 Modeling Geometric Variations by Elasticity......Page 272 5.3 Basics XI: Manifolds, Lie Groups, and Lie Algebras......Page 275 5.4 Modeling Geometric Variations by Metricson Diff......Page 289 5.5 Comparing Elastic and Riemannian Energies......Page 298 5.6 Empirical Data on Deformations of Faces......Page 304 5.7 The Full Face Model......Page 307 5.8 Appendix: Geodesics in Diff and Landmark Space......Page 314 5.9 Exercises......Page 320 6. Natural Scenes and their Multiscale Analysis......Page 330 6.1 High Kurtosis in the Image Domain......Page 331 6.2 Scale Invariance in the Discrete and Continuous Setting......Page 335 6.3 The Continuous and Discrete Gaussian Pyramids......Page 341 6.4 Wavelets and the "Local" Structure of Images......Page 348 6.5 Distributions Are Needed......Page 361 6.6 Basics XIII: Gaussian Measures on Function Spaces......Page 366 6.7 The Scale-, Rotation- and Translation-Invariant Gaussian Distribution......Page 373 6.8 Model II: Images Made Up of Independent Objects......Page 379 6.9 Further Models......Page 387 6.10 Appendix: A Stability Property of the Discrete Gaussian Pyramid......Page 390 6.11 Exercises......Page 392 Bibliography......Page 400 A K Peters Contents 8 Preface 10 Notation 12 0. What Is Pattern Theory? 14 0.1 The Manifesto of Pattern Theory 14 0.2 The Basic Types of Patterns 18 0.3 Bayesian Probability Theory: Pattern Analysis and Pattern Synthesis 22 1. English Text and Markov Chains 30 1.1 Basics I: Entropy and Information 34 1.2 Measuring the n-gram Approximation with Entropy 39 1.3 Markov Chains and the n-gram Models 42 1.4 Words 52 1.5 Word Boundaries via Dynamic Programming and Maximum Likelihood 58 1.6 Machine Translation via Bayes' Theorem 61 1.7 Exercises 64 2. Music and Piecewise Gaussian Models 74 2.1 Basics III: Gaussian Distributions 75 2.2 Basics IV: Fourier Analysis 81 2.3 Gaussian Models for Single Musical Notes 85 2.4 Discontinuities in One-Dimensional Signals 92 2.5 The Geometric Model for Notes via Poisson Processes 99 2.6 Related Models 104 2.7 Exercises 113 3. Character Recognition and Syntactic Grouping 124 3.1 Finding Salient Contours in Images 126 3.2 Stochastic Models of Contours 135 3.3 The Medial Axis for Planar Shapes 147 3.4 Gestalt Laws and Grouping Principles 155 3.5 Grammatical Formalisms 160 3.6 Exercises 176 4. Image Texture, Segmentation and Gibbs Models 186 4.1 Basics IX: Gibbs Fields 189 4.2 (u + v)-Models for Image Segmentation 199 4.3 Sampling Gibbs Fields 208 4.4 Deterministic Algorithms to Approximate the Mode of a Gibbs Field 215 4.5 Texture Models 227 4.6 Synthesizing Texture via Exponential Models 234 4.7 Texture Segmentation 241 4.8 Exercises 247 5. Faces and Flexible Templates 262 5.1 Modeling Lighting Variations 266 5.2 Modeling Geometric Variations by Elasticity 272 5.3 Basics XI: Manifolds, Lie Groups, and Lie Algebras 275 5.4 Modeling Geometric Variations by Metricson Diff 289 5.5 Comparing Elastic and Riemannian Energies 298 5.6 Empirical Data on Deformations of Faces 304 5.7 The Full Face Model 307 5.8 Appendix: Geodesics in Diff and Landmark Space 314 5.9 Exercises 320 6. Natural Scenes and their Multiscale Analysis 330 6.1 High Kurtosis in the Image Domain 331 6.2 Scale Invariance in the Discrete and Continuous Setting 335 6.3 The Continuous and Discrete Gaussian Pyramids 341 6.4 Wavelets and the "Local" Structure of Images 348 6.5 Distributions Are Needed 361 6.6 Basics XIII: Gaussian Measures on Function Spaces 366 6.7 The Scale-, Rotation- and Translation-Invariant Gaussian Distribution 373 6.8 Model II: Images Made Up of Independent Objects 379 6.9 Further Models 387 6.10 Appendix: A Stability Property of the Discrete Gaussian Pyramid 390 6.11 Exercises 392 Bibliography 400 9781568815794 Pattern theory is a distinctive approach to the analysis of all forms of real-world signals. At its core is the design of a large variety of probabilistic models whose samples reproduce the look and feel of the real signals, their patterns, and their variability. Bayesian statistical inference then allows you to apply these models in the analysis of new signals. This book treats the mathematical tools, the models themselves, and the computational algorithms for applying statistics to analyze six representative classes of signals of increasing complexity. The book covers patterns in text, sound, and images. Discussions of images include recognizing characters, textures, nature scenes, and human faces. The text includes online access to the materials (data, code, etc.) needed for the exercises. Pattern Theory, pioneered by Ulf Grenander, is a distinctive approach to the analysis of all forms of real-world signals. At its core is the design of a large variety of probabilistic models whose samples reproduce the look and feel of the real signals, their patterns, and their variability. Bayesian statistical inference then allows you to apply these models in the analysis of new signals. This book treats the mathematical tools, the models themselves, and the computational algorithms for applying statistics to analyze six representative classes of signals of increasing complexity