Transcript Pattern Recognition

Pattern Recognition
9/23/2008
Instructor: Wen-Hung Liao, Ph.D.
Administrative Information





E-mail: [email protected]
Office: 大仁樓三樓
Office hours: TBA
Course web page:
http://www.cs.nccu.edu.tw/~whliao/pr2008/
Textbook: Pattern Classification, 2nd Edition
by Duda, Hart and Stork. (歐亞書局)
Definition

Pattern recognition is the study of how
machines can
- observe the environment,
- learn to distinguish patterns of interest,
- make decisions about the categories of
the patterns.
What is a pattern?


Watanabe defines a pattern “as opposite of
chaos; it is an entity, vaguely defined, that
could be given a name”.
Examples:
- fingerprint,
- handwritten cursive word,
- a human face,
- a speech signal...
Types of recognition


Supervised classification: input pattern is
identified as a member of a pre-defined class.
Unsupervised classification: input pattern is
assigned to a hitherto unknown class.
Applications
Problem
Domain
Application
Bioinformatics
Sequence Analysis DNA/Protein
Sequence
Known types of
genes
Data Mining
Search for
meaningful
patterns
Internet Search
Points in
multi-dimension
al space
Text document
Compact and
well-separated
clusters
Semantic
categories
Document Image Reading machine
Analysis
for the blind
Document
image
Alphanumeric
characters, words
Industrial
Automation
Intensity or
range image
Defective/non-de
fective
Document
Classification
PCB inspection
Input
Pattern
Classes
Applications (2)
Problem
Domain
Application
Input
Pattern
Classes
Multimedia
database
retrieval
Biometrics
recognition
Internet Search
Video clip
Video genres
Personal
identification
Face, iris,
fingerprint
Authorized users
for access control
Remote sensing
Forecasting crop
yield
Multi-spectral
image
Land use
categories
Speech
recognition
Telephone
directory inquiry
Speech
waveform
Spoken words
Components of a PR System



Data acquisition and pre-processing
Data representation
Decision making
Pattern Recognition Methods




Template matching
Statistical approach
Syntactic approach
Neural networks
Template Matching



A template (typically a 2D shape) or a
prototype of the pattern to be recognized is
available.
Compute the similarity between the template
and the pattern to be matched.
Take into account pose(rotation, translation)
and scale changes.
Issues of concern



Choice of template
Computational complexity
Rigidity assumption (use deformable
template models)
Statistical Approach


Each pattern is represented in terms of d
features, and is viewed as a point in a ddimensional space
The goal is to choose those features that
allow pattern vectors belonging to different
categories to occupy compact and disjoint
regions in a d-dimensional feature space.
Syntactic Approach




Use hierarchical structures to represent
complex patterns.
The simplest unit is called: primitives
Complex pattern is represented in terms of
the interrelationships (grammars) between
the primitives.
Grammatical rules can be learned by training.
Issues of concern



Can be used in situations where the patterns
have a definite structure such as EKG
waveforms, shape analysis of contours.
However, it’s usually difficult to segment
noisy patterns and infer grammar from the
training set.
May yield a combinatorial explosions of
possibilities to be investigated.
Neural Networks



Massively parallel computing systems
consisting of an extremely large number of
simple processors with many interconnections.
Can learn complex non-linear input-output
relationships.
Feed-forward networks such as multilayer
perceptron and Radial Basis Function network
are useful for pattern classification.
Pattern Recognition Models
Approach Representation Recognition Typical
Function
Criterion
Template
Matching
Statistical
Samples, pixels,
curves
Features
Correlation,
distance
measure
Discriminant
function
Classification
error
Classification
error
Syntactic or Primitives
structural
Rules, grammar Acceptance
error
Neural Nets Samples, pixels,
features
Network
function
Mean square
error
Reference

A.K. Jain, R.P.W. Duin and J. Mao,
“Statistical Pattern Recognition: A Review”,
IEEE Transactions on Pattern Analysis and
Machine Intelligence (PAMI), Vol. 22, No. 1,
pp. 4-37, Jan. 2000.