Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 1 of 21
`Case 1:14-cv-02396—PGG-MHD Document 153-14 Filed 06/28/19 Page 1 of 21
`
`EXHIBIT M
`
`EXHIBIT M
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 2 of 21
`
`Pattern Classification
`and Scene Analysis
`Richard O. Duda and
`Peter E. Hart
`
`It
`
`r’"
`
`e3
`
`t~
`
`Ct~
`
`0 Wiley-
`
`i nterscience
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 3 of 21
`
`PATTERN
`CLASSIFICATION
`AND SCENE
`ANALYSIS
`
`RICHARD O. DUDA
`PETER E. HART
`
`Stanford Research Institute,
`Menlo Park, California
`
`A WILEY-INTERSCIENCE PUBLICATION
`
`John Wiley & Sons
`
`New York London Sydney Toronto
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 4 of 21
`
`Copyright © 1973, by John Wiley & Sons, Inc.
`
`All rights reserved. Published simultaneously in Canada.
`
`No part of this book may be reproduced by any means,
`nor transmitted, nor translated into a machine language
`without the written permission of the publisher.
`
`Library of Congress Cataloging in Publication Data
`
`Duda, Richard O.
`Pattern classification and scene analysis.
`
`"A Wiley-interscience publication."
`Includes bibliographical references.
`1. Perceptrons. 2. Statistical decision.
`2. Hart, Peter E., joint author. II. Title.
`Q327.D83 001.53’3 72-7008
`
`ISBN 0-471-22361-1
`
`Printed in the United States of America
`
`109876543
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 5 of 21
`
`CONTENTS
`
`Part I PATTERN CLASSIFICATION
`
`1 INTRODUCTION
`
`1.1 Machine Perception
`1.2 An Example
`1.3 The Classification Model
`1.4 The Descriptive Approach
`1.5 Summary of the Book by Chapters
`1.6 Bibliographical Remarks
`
`2 BAYES DECISION THEORY
`
`Introduction
`2.1
`2.2 Bayes Decision Theory--The Continuous Case
`2.3 Two-Category Classification
`2.4 Minimum-Error-Rate Classification
`2.5 Classifiers, Discriminant Functions and Decision Surfaces
`2.5.1 The Multicategory Case
`2.5.2 The Two-Category Case
`2.6 Error Probabilities and Integrals
`2.7 The Normal Density
`2.7.1 The Univariate Normal Density
`2.7.2 The Multivariate Normal Density
`2.8 Discriminant Functions for the Normal Density
`2.8.1 Case 1: ~’i = O21
`2.8.2 Case 2: ~"i---- ~
`2.8.3 Case 3: ~’i Arbitrary
`2.9 Bayesian Decision Theory--The Discrete Case
`2.10 Independent Binary Features
`2.11 Compound Bayes Decision Theory and Context
`
`1
`2
`4
`5
`6
`7
`
`10
`
`10
`13
`15
`16
`17
`17
`20
`20
`22
`22
`23
`24
`26
`27
`3O
`31
`32
`34
`
`xi
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 6 of 21
`
`xii
`
`CONTENTS
`
`2.12 Remarks
`2.13 Bibliographical and Historical Remarks
`Problems
`
`3 PARAMETER ESTIMATION AND SUPERVISED
`LEARNING
`
`3.1 Parameter Estimation and Supervised Learning
`3.2 Maximum Likelihood Estimation
`3.2.1 The General Principle
`3.2.2 The Multivariate Normal Case: Unknown Mean
`3.2.3 The General Multivariate Normal Case
`3.3 The Bayes Classifier
`3.3.1 The Class-Conditional Densities
`3.3.2 The Parameter Distribution
`3.4 Learning the Mean of a Normal Density
`3.4.1 The Univariate Case: p(~ I~c)
`3.4.2 The Univariate Case: p(x IX)
`3.4.3 The Multivariate Case
`3.5 General Bayesian Learning
`3.6 Sufficient Statistics
`3.7 Sufficient Statistics and the Exponential Family
`3.8 Problems of Dimensionality
`3.8.1 An Unexpected Problem
`3.8.2 Estimating a Covariance Matrix
`3.8.3 The Capacity of a Separating Plane
`3.8.4 The Problem-Average Error Rate
`¯ 3.9 Estimating the Error Rate
`3.10 Bibliographical and Historical Remarks
`Problems
`
`4 NONPARAMETRIC TECHNIQUES
`
`Introduction
`4.1
`4.2 Density Estimation
`4.3 Parzen Windows
`4.3.1 General Discussion
`4.3.2 Convergence of the Mean
`4.3.3 Convergence of the Variance
`4.3.4 Two Examples
`4.4 k-Nearest Neighbor Estimation
`
`35
`36
`39
`
`44
`
`44
`45
`45
`47
`48
`49
`50
`51
`52
`52
`55
`55
`57
`59
`62
`66
`66
`67
`69
`70
`73
`76
`80
`
`85
`
`85
`85
`88
`88
`90
`91
`91
`95
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 7 of 21
`
`CONTENTS
`
`4.5 Estimation of A Posteriori Probabilities
`4.6 The Nearest-Neighbor Rule
`4.6.1 General Considerations
`4.6.2 Convergence of the Nearest-Neighbor
`4.6.3 Error Rate for the Nearest-Neighbor Rule
`4.6.4 Error Bounds
`4.7 The k-Nearest-Neighbor Rule
`4.8 Approximations by Series Expansions
`4.9 Approximations for the Binary Case
`4.9.1 The Rademacher-Walsh Expansion
`4.9.2 The Bahadur-Lazarsfeld Expansion
`4.9.3 The Chow Expansion
`4.10 Fisher’s Linear Discriminant
`4.11 Multiple Discriminant Analysis
`4.12 Bibliographical and Historical Remarks
`Problems
`
`5
`
`LINEAR DISCRIMINANT FUNCTIONS
`
`5.1
`5.2
`
`Introduction
`Linear Discriminant Functions and Decision Surfaces
`5.2.1 The Two-Category Case
`5.2.2 The Multicategory Case
`5.3 Generalized Linear Discriminant Functions
`5.4 The Two-Category Linearly-Separable Case
`5.4.1 Geometry and Terminology
`5.4.2 Gradient Descent Procedures
`5.5 Minimizing the Perceptron Criterion Function
`5.5.1 The Perceptron Criterion Function
`5.5.2 Convergence Proof for Single-Sample Correction
`5.5.3 Some Direct Generalizations
`5.6 Relaxation Procedures
`5.6.1 The Descent Algorithm
`5.6.2 Convergence Proof
`5.7 Nonseparable Behavior
`5.8 Minimum Squared Error Procedures
`5.8.1 Minimum Squared Error and the Pseudoinverse
`5.8.2 Relation to Fisher’s Linear Discriminant
`5.8.3 Asymptotic Approximation to an Optimal Discriminant
`5.8.4 The Widrow-Hoff Procedure
`5.8.5 Stochastic Approximation Methods
`
`.°.
`XIII
`
`97
`98
`98
`99
`100
`101
`103
`105
`108
`108
`111
`113
`114
`118
`121
`126
`
`130
`
`130
`131
`131
`132
`134
`138
`138
`140
`141
`141
`142
`146
`147
`147
`148
`149
`151
`151
`152
`154
`155
`156
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 8 of 21
`
`xiv
`
`CONTENTS
`
`5.9 The Ho-Kashyap Procedures
`5.9.1 The Descent Procedure
`5.9.2 Convergence Proof
`5.9.3 Nonseparable Behavior
`5.9.4 Some Related Procedures
`5.10 Linear Programming Procedures
`5.10.1 Linear Programming
`5.10.2 The Linearly Separable Case
`5.10.3 Minimizing the Perceptron Criterion Function
`5.10.4 Remarks
`5.11 The Method of Potential Functions
`5.12 Multicategory Generalizations
`5.12.1 Kesler’s Construction
`5.12.2 The Fixed-Increment Rule
`5.12.3 Generalization for MSE Procedures
`5.13 Bibliographical and Historical Remarks
`Problems
`
`6 UNSUPERVISED LEARNING AND CLUSTERING
`
`Introduction
`6.1
`6.2 Mixture Densities and Identifiability
`6.3 Maximum Likelihood Estimates
`6.4 Application to Normal Mixtures
`6.4.1 Case 1: Unknown Mean Vectors
`6.4.2 An Example
`6.4.3 Case 2: All Parameters Unknown
`6.4.4 A Simple Approximate Procedure
`6.5 Unsupervised Bayesian Learning
`6.5.1 The Bayes Classifier
`6.5.2 Learning the Parameter Vector
`6.5.3 An Example
`6.5.4 Decision-Directed Approximations
`6.6 Data Description and Clustering
`6.7 Similarity Measures
`6.8 Criterion Functions for Clustering
`6.8.1 The Sum-of-Squared-Error Criterion
`6.8.2 Related Minimum Variance Criteria
`6.8.3 Scattering Criteria
`6.8.3.1 The Scatter Matrices
`
`159
`159
`161
`163
`163
`166
`166
`167
`168
`169
`172
`174
`174
`176
`177
`179
`186
`
`189
`
`189
`190
`192
`193
`194
`195
`198
`201
`203
`203
`204
`207
`210
`211
`213
`217
`217
`219
`221
`221
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 9 of 21
`
`CONTENTS
`
`xv
`
`6.8.3.2 The Trace Criterion
`6.8.3.3 The Determinant Criterion
`6.8.3.4
`Invariant Criteria
`Iterative Optimization
`6.9
`6.10 Hierarchical Clustering
`6.10.1 Definitions
`6.10.2 Agglomerative Hierarchical Clustering
`6.10.2.1 The Nearest-Neighbor Algorithm
`6.10.2.2 The Furthest-Neighbor Algorithm
`6.10.2.3 Compromises
`6.10.3 Stepwise-Optimal Hierarchical Clustering
`6.10.4 Hierarchical Clustering and Induced Metrics
`6.11 Graph Theoretic Methods
`6.12 The Problem of Validity
`6.13 Low-Dimensional Representations and Multidimensional Scaling
`6.14 Clustering and Dimensionality Reduction
`6.15 Bibliographical and Historical Remarks
`Problems
`
`Part II SCENE ANALYSIS
`
`7 REPRESENTATION AND INITIAL
`SIMPLIFICATIONS
`
`Introduction
`7.1
`7.2 Representations
`7.3 Spatial Differentiation
`7.4 Spatial Smoothing
`7.5 Template Matching
`7.5.1 Template Matching--Metric Interpretation
`7.5.2 Template Matching--Statistical Interpretation
`7.6 Region Analysis
`7.6.1 Basic Concepts
`7.6.2 Extensions
`7.7 Contour Following
`7.8 Bibliographical and Historical Remarks
`Problems
`
`222
`222
`223
`225
`228
`228
`230
`233
`233
`235
`235
`236
`237
`239
`243
`246
`248
`256
`
`263
`
`263
`264
`267
`272
`276
`276
`282
`284
`284
`288
`290
`293
`297
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 10 of 21
`
`xvi
`
`CONTENTS
`
`8 THE SPATIAL FREQUENCY DOMAIN
`
`Introduction
`8.1
`8.2 The Sampling Theorem
`8.3 Template Matching and the Convolution Theorem
`8.4 Spatial Filtering
`8.5 Mean Square Estimation
`8.6 Bibliographical and Historical Remarks
`Problems
`
`9 DESCRIPTIONS OF LINE AND SHAPE
`
`Introduction
`9.1
`9.2 Line Description
`9.2.1 Minimum-Squared-Error Line Fitting
`9.2.2 Eigenvector Line Fitting
`9.2.3 Line Fitting by Clustering
`9.2.4 Line Segmentation
`9.2.5 Chain Encoding
`9.3 Shape Description
`9.3.1 Topological Properties
`9.3.2 Linear Properties
`9.3.3 Metric Properties
`9.3.4 Descriptions Based on Irregularities
`9.3.5 The Skeleton of a Figure
`9.3.6 Analytic Descriptions of Shape
`Integral Geometric Descriptions
`9.3.7
`9.4 Bibliographical and Historical Remarks
`Problems
`
`10 PERSPECTIVE TRANSFORMATIONS
`
`Introduction
`10.1
`10.2 Modelling Picture Taking
`10.3 The Perspective Transformation in Homogeneous Coordinates
`10.4 Perspective Transformations With Two Reference Frames
`Illustrative Applications
`10.5
`10.5.1 Camera Calibration
`10.5.2 Object Location
`10.5.3 Vertical Lines: Perspective Distortion
`10.5.4 Horizontal Lines and Vanishing Points
`
`298
`
`298
`302
`305
`308
`318
`322
`325
`
`327
`
`327
`328
`328
`332
`335
`337
`339
`341
`342
`345
`348
`352
`356
`362
`367
`372
`377
`
`379
`
`379
`380
`382
`386
`392
`392
`393
`394
`396
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 11 of 21
`
`CONTENTS
`
`10.6 Stereoscopic Perception
`10.7 Bibliographical and Historical Remarks
`Problems
`
`11 PROJECTIVE INVARIANTS
`
`Introduction
`11.1
`11.2 The Cross Ratio
`11.3 Two-Dimensional Projective Coordinates
`11.4 The Inter-Lens Line
`11.5 An Orthogonal Projection Approximation
`11.6 Object Reconstruction
`11.7 Bibliographical and Historical Remarks
`Problems
`
`12 DESCRIPTIVE METHODS IN SCENE ANALYSIS
`
`Introduction
`12.1
`12.2 Descriptive Formalisms
`12.2.1 Syntactic Descriptions
`12.2.2 Relational Graphs
`12.3 Three-Dimensional Models
`12.4 The Analysis of Polyhedra
`12.4.1 Line Semantics
`12.4.2 Grouping Regions into Objects
`12.4.3 Monocular Determination of Three-Dimensional
`Structure
`12.5 Bibliographical and Historical Remarks
`Problems
`
`AUTHOR INDEX
`
`SUBJECT INDEX
`
`xvii
`
`398
`401
`404
`
`405
`
`405
`407
`411
`414
`418
`421
`422
`424
`
`425
`
`425
`426
`426
`434
`436
`441
`442
`449
`
`456
`462
`465
`
`467
`
`472
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 12 of 21
`
`Part I
`
`PATTERN
`CLASSIFICATION
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 13 of 21
`
`Chapter 1
`
`INTRODUCTION
`
`1.1 MACHINE PERCEPTION
`
`Since the advent of the digital computer there has been a constant effort to
`expand the domain of computer applications. Some of the motivation for
`this effort comes from important practical needs to find more efficient ways
`of doing things. Some of the motivation comes from the sheer challenge of
`building or programming a machine to do things that machines have never
`done before. Both of these motives are found in that area of artificial
`intelligence that we shall call machine perception.
`At present, the ability of machines to perceive their environment is very
`limited. A variety of transducers are available for converting light, sound,
`temperature, etc., to electrical signals. When the environment is carefully
`controlled and the signals have a simple interpretation, as is the case with
`the standard computer input devices, the perceptual problems become
`trivial. But as we move beyond having a computer read punched cards or
`magnetic tapes to having it read hand-printed characters or analyze bio-
`medical photographs, we move from problems of sensing the data to much
`more difficult problems of interpreting the data.
`The apparent ease with which vertebrates and even insects perform per-
`ceptual tasks is at once encouraging and frustrating. Psychological and
`physiological studies have given us a great many interesting facts about
`animal perception, but no understanding sufficient for us to duplicate their
`performance with a computer. The problem area has a certain unique
`fascination to it because perception is something everyone experiences but
`no one really understands. Introspection has not proved as helpful in dis-
`covering the nature of perception as one might hope, apparently because most
`everyday perceptual processes are carried out below the conscious level.
`Paradoxically, we are all expert at perception, but none of us knows much
`about it.
`The lack of a complete theory of perception has not prevented people
`from trying to solve more modest problems. Many of these involve pattern
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 14 of 21
`
`2
`
`INTRODUCTION
`
`classification--the assignment of a physical object or event to one of several
`prespecified categories. Extensive study of classification problems has led
`to an abstract mathematical model that provides the theoretical basis for
`classifier design. Of course, in any specific application one ultimately must
`come to grips with the special characteristics of the problem at hand. Of the
`various problem areas, the domain of pictorial problems has received by
`far the most attention. The purpose of this book is to give a systematic
`account of those principles of pattern classification and those techniques of
`pictorial scene analysis that seem to have the widest applicability and interest.
`
`1.2 AN EXAMPLE
`
`To illustrate some of the types of problems we shall address, let us consider
`the following imaginary and somewhat fanciful example. Suppose that a
`lumber mill producing assorted hardwoods wants to automate the process of
`sorting finished lumber according to species of tree. As a pilot project, it is
`decided to try first to distinguish birch lumber from ash lumber using optical
`sensing. A system to perform this very specific task might well have the form
`shown in Figure 1.1. The camera takes a picture of the lumber and passes
`the picture on to a feature extractor, whose purpose is to reduce the data by
`measuring certain "features" or "properties" that distinguish pictures of
`birch lumber from pictures of ash lumber. These features (or, more precisely,
`the values of these features) are then passed to a classifier that evaluates
`the evidence presented and makes a final decision about the lumber type.
`Let us consider how the feature extractor and classifier might be designed.
`Suppose somebody at the lumber mill tells us that birch is often lighter
`colored than ash. Then brightness becomes an obvious feature, and we might
`attempt to classify the lumber merely by seeing whether or not the average
`brightness x exceeds some critical value x0. To choose x0, we could obtain
`some samples of the different types of wood, make brightness measurements,
`and inspect the results. Suppose that we do this, and obtain the histograms
`
`TRANSDUCER
`
`FEATURE L------J
`EXTRACTOR i
`r’~"~t CLASSIFIER ~ DECLSION
`
`FIGURE 1.1. A pattern classification system.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 15 of 21
`
`AN EXAMPLE ’ 3
`
`BIRCH
`
`Xo
`
`BRIGHTNESS --’ X
`
`FIGURE 1.2. Histograms for the brightness feature.
`
`shown in Figure 1.2. These histograms bear out the statement that birch is
`usually lighter than ash, but it is clear that this single criterion is not in-
`fallible. No matter how we choose x0, we can not reliably separate birch
`from ash by brightness alone.
`In our search for other features, we might try to capitalize on the observa-
`tion that ash typically has a more prominent grain pattern than birch. This
`feature is much more difficult to measure than average brightness, but it is
`reasonable to assume that we can obtain a measure of grain prominence from
`the magnitude and frequency of occurrence of light-to-dark transitions in
`the picture. Now we have two features for classifying lumber, the brightness
`x1 and the grain prominence x~. The feature extractor has thus reduced each
`picture to a point or feature vector x in a two-dimensional feature space,
`where
`
`X2
`
`Our problem now is to partition the feature space into two regions, where
`all the points in one region correspond to birch, and all points in the other
`correspond to ash. Suppose that we measure the feature vectors for our
`samples and obtain the scattering of points shown in Figure 1.3. This plot
`suggests the following rule for classifying the data: Classify the lumber as
`ash if its feature vector falls above the line AB, and as birch otherwise.
`While this rule appears to do a good job of separating our samples, we
`have no guarantee that it Will perform as well on new samples. It would
`certainly be prudent to obtain some more samples and see how many are
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 16 of 21
`
`4
`
`INTRODUCTION
`
`¯ ASH
`
`O BIRCH
`
`o
`Oo o
`
`0000 0
`0
`
`mUm|
`
`o
`
`oB
`
`BRIGHTNESS -- Xi
`
`FIGURE 1.3. Scatter diagram for
`the feature vectors.
`
`correctly classified. This suggests that our problem has a statistical com-
`ponent, and that perhaps we should look for a Classification procedure that
`minimizes the probability of error.
`Without forgetting this idea, we should remember that we chose a simple
`problem for a pilot project. A more realistic problem might involve sorting
`many different classes of lumber. To separate oak from birch and ash, we
`might well require less obvious features, such as "straightness-of-grain."
`With more categories and more features, the graphical approach to designing
`the classifier will probably have to be abandoned. To proceed further, we
`shall need whatever theoretical help we can get.
`
`1.3 THE CLASSIFICATION MODEL
`
`The preceding example contains many of the elements of the most commonly
`used abstract model for pattern recognition, the classification model. This
`model contains three parts: a transducer, a feature extractor, and a classifier
`The transducer senses the input and converts it into a form suitable for
`machine processing. The feature extractor (also called the. receptor, property
`filter, attribute detector, or preprocessor) extracts presumably relevant
`information from the input data. The classifier uses this information to
`assign the input data to one of a finite number of categories.
`A discussion of transducer specification or design lies outside the province
`of this book. However, we shall be concerned with both feature extraction
`and classification. From a theoretical viewpoint, the line between these topics
`is arbitrary. An ideal feature extractor would make the job of the classifier
`trivial, and an omnipotent classifier would not need the help of a feature
`extractor. The distinction is forced upon us for practical, not theoretical
`reasons, but the distinction is important nevertheless.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 17 of 21
`
`THE DESCRIPTIVE APPROACH 5
`
`Generally speaking, the problem of feature extraction is much more
`problem dependent than the problem of classification. A good feature
`extractor for sorting lumber would probably be of little use for identifying
`fingerprints or classifying photomicrographs of blood cells. Nevertheless, a
`substantial body of techniques has been developed for extracting useful
`information from pictures. Part II of this book is devoted to an exposition
`of these techniques and their properties.
`The problem of classification is basically one of partitioning the feature
`space into regions, one region for each category. Ideally, one would like to
`arrange this partitioning so that none of the decisions is ever wrong. When
`this cannot be done, one would like to minimize the probability of error, or,
`if some errors are more costly than others, the average cost of errors. In
`this case, the problem of classification becomes a problem in statistical
`decision theory, a subject that has many applications to pattern classification.
`Part I of this book is concerned with these and related topics in classification
`theory.
`
`1.4 THE DESCRIPTIVE APPROACH
`
`There are many problems in pattern recognition and machine perception for
`which the classification model is clearly inappropriate. For example, in
`analyzing a picture of bubble-chamber particle tracks, one wants a descrip-
`tion, rather than just a classification, of the picture, Such a description should
`contain information about both the individual parts of the picture and about
`the relations among the parts. Ideally, it should directly reflect the structure
`present in the original scene.
`Consider, for example, the simple scene shown in Figure 1.4. It is possible
`that a simple classification such as "office scene" or "telephone present"
`would be adequate for some purposes. A more complete analysis would
`include an identification of all the major objects present--the telephone,
`note pad, cup, pencils, eraser, etc. An even more complete analysis would
`indicate the relations between these objects, and might result in a description
`such as "(Two pencils on top of a pad) in front of (a cup to the left of (an
`eraser in front of a telephone))."
`The problem of analyzing a visual scene and producing a structural de-
`scription has proved to be quite difficult. A generally accepted formalization
`of the problem, analogous to the classification model, has yet to emerge
`from the work that has been done to date. Attempts have been made to
`borrow concepts from the theory of formal languages and to produce a
`linguistic model for scene analysis. Here the scene is viewed as a statement
`in a language whose grammar defines the allowed structural relations. With
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 18 of 21
`
`6
`
`INTRODUCTION
`
`FIGURE 1.4. A simple scene.
`
`this formulation, scene analysis is viewed as the process of using a picture
`grammar to parse the scene, producing a description of the scene as a com-
`position of related subscenes.
`The linguistic model does not exhaust the ways of using known structural
`relations among the elements of a picture to guide its analysis and produce
`a useful description. Some of the most interesting procedures that have been
`developed are ad hoc and heuristic; a unifying conceptual framework en-
`compassing all of these methods has not yet been developed. The procedures
`themselves can be described, however, and this general topic of descriptive
`approaches to scene analysis concludes Part II.
`
`1.5 SUMMARY OF THE BOOK BY CHAPTERS
`
`The orientation of Part I of this book is primarily statistical. Chapter 2 states
`the classification problem in decision-theoretic terms, and derives the general
`form for an optimal classifier. This solution is obtained under the assumption
`that all of the probability distributions involved are known. The remainder
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 19 of 21
`
`BIBLIOGRAPHICAL REMARKS 7
`
`of Part I is concerned with ways of proceeding when the probabilistic structure
`is not known.
`In Chapter 3 we assume that everything is known except for some param-
`eters of the distributions. Both maximum likelihood and Bayesian pro-
`cedures for estimating parameters from samples are described. If none of the
`standard ways of parameterizing unknown distributions is suitable, one can
`resort to nonparametric techniques. These procedures, which are discussed
`in Chapter 4, exchange the need for knowledge of the forms of the distri-
`butions for the need for a large number of samples.
`In Chapter 5 we parameterize the classifier and study ways of using samples
`to determine the classifier directly. These techniques have their origin in
`Fisher’s linear discriminant, and include the well known perceptron and
`relaxation procedures, minimum-squared-error methods, stochastic approxi-
`mation, the method of potential functions, and linear programming tech-
`niques. Chapter 6 concludes Part I with a discussion of various techniques
`for unsupervised learning and clustering.
`Chapter 7 begins Part II with a discussion of procedures for representing
`pictures, and for performing such basic operations as sharpening, smoothing,
`template matching, and partitioning a picture into homogeneous regions.
`Chapter 8 develops the concept of spatial filtering, and interprets some of
`these operations in the frequency domain. Chapter 9 is concerned with a
`great variety of procedures for describing lines and shapes in pictures.
`Topological, linear, and metric properties of shape are described, together
`with a number of descriptive techniques based on these properties.
`Chapters 10 and 11 present important mathematical background relevant
`to pictures of three-dimensional objects. Chapter 10 develops the equations
`for perspective transformation, and shows how they can be usefully employed
`in scene analysis. Chapter 11 treats the subject of projective invariants,
`quantities that are the same in different pictures of the same object. Finally,
`Chapter 12 discusses some of the more important contemporary approaches
`to the difficult problem of completely analyzing visual scenes.
`
`1.6 BIBLIOGRAPHICAL REMARKS
`
`The published literature on pattern classification and scene analysis has grown
`to the point where even specialized bibliographies can contain hundreds of
`references. The references that we give at the end of each chapter hopefully
`will provide the reader with some historical perspective and a good starting
`point for further study. Additional guidance can be obtained from other
`texts and from a number of valuable survey articles.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 20 of 21
`
`8
`
`INTRODUCTION
`
`For a brief overview that treats pattern recognition as one topic in arti-
`ficial intelligence, the influential article by Minsky (1961) is highly recom-
`mended. Nagy (1968) provides an excellent survey of work done using the
`classification model. The text by Nilsson (1965) provides an exceptionally
`clear treatment of classification procedures. A lucid and more recent survey
`of these procedures is given by Ho and Agrawala (1968). Levine (1969) gives
`a comprehensive survey of the techniques that have been used to extract
`features from pictures. The general subject of automatic picture processing
`is well surveyed by Hawkins (1970), and is systematically treated in the
`scholarly text by Rosenfeld (1969).
`There are many interesting subject areas that are related to this book but
`beyond its scope. Readers interested in image enhancement and picture
`coding should be aware of the survey by Huang, Schreiber and Tretiak
`(1971). Those interested in the fascinating area of human and animal per-
`ception will find the surveys by Kolers (1968) and Gose (1969) most useful.
`Those interested in philosophical issues will find the books by Watanabe
`(1969) and Bongard (1970)thought provoking. Finally, those interested in
`the practical applications of all of this theory will find a wealth of references
`in the literature survey by Stevens (1970).
`
`REFERENCES
`
`1. Bongard, M., Pattern Recognition (Spartan Books, Washington, D.C.,
`1970).
`2. Gose, E. E., "Introduction to biological and mechanical pattern recognition,"
`in Methodologies of Pattern Recognition, pp. 203-252, S. Watanabe, ed. (Academic
`Press, New York, 1969).
`3. Hawkins, J. K., "Image processing principles and techniques," in Advances in
`Information Systems, Vol. 3, pp. 113-214, J. T. Tou, ed. (Plenum Press, New York
`and London, 1970).
`4. Ho, Y. C. and A. Agrawala, "On pattern classification algorithms: introduc-
`tion and survey," Proe. IEEE, 56, 2101-2114 (December 19"68).
`
`5. Huang, T. S., W. F. Schreiber, and O. J. Tretiak, "Image Processing," Proe.
`IEEE, 59, 1586-1609 (November 1971).
`6. Kolers, P. A., "Some psychological aspects of pattern recognition," in
`Recognizing Patterns, pp. 4-61, P. A. Kolers and M. Eden, eds. (MIT Press,
`Cambridge, Massachusetts, 1968).
`7. Levine, M.D., "Feature extraction: a survey," Proc. IEEE, 57, 1391-1407
`(August 1969).
`8. Minsky, M., "Steps toward artificial intelligence," Proe. IRE, 49, 8-30
`(January 1961); also in Computers and Thought, pp. 406--450, E. A. Feigenbaum
`and J. Feldman, eds. (McGraw-Hill, New York, 1963).
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 153-14 Filed 06/28/19 Page 21 of 21
`
`REFERENCES "9
`
`9. Nagy, G., "State of the art in pattern recognition," Proc. IEEE, 56, 836-862
`(May 1968).
`10. Nilsson, N. J., Learning Machines (McGraw-Hill, New York, 1965).
`11. Rosenfeld, A., Picture Processing by Computer (Academic Press, New
`York, 1969).
`12. Stevens, M. E.,"Research and development in the computer and information
`sciences. Volume 1. Information acquisition, sensing, and input--a selective
`literature review," National Bureau of Standards Monograph 113, Vol. 1 (March
`1970).
`13. Watanabe, M. S., Knowing and Guessing (John Wiley, New York, 1969).
`
`