PATTERN RECOGNITION
Team teaching
OUTLINES
Whats
is pattern? What is class pattern? What is pattern recognition? Human perception Application example Statistically way Human and machine perception Pattern recognition process Topic Searching
2
WHAT IS A PATTERN?
A
pattern is an abstract object, or a set of measurements describing a physical object.
WHAT IS A PATTERN CLASS?
A
pattern class (or category) is a set of patterns sharing common attributes. collection of similar (not necessarily identical) objects.
During
recognition given objects are assigned to prescribed classes.
4
WHAT IS PATTERN RECOGNITION?
Theory,
Algorithms, Systems to put Patterns into Categories Perceived Pattern to Previously Perceived Patterns to distinguish patterns of interest from their background
Relate
Learn
HUMAN PERCEPTION
Humans
have developed highly sophisticated skills for sensing their environment and taking actions according to what they observe, e.g.,
Recognizing a face. Understanding spoken words. Reading handwriting. Distinguishing fresh food from its smell.
We
would like to give similar capabilities to machines.
6
EXAMPLES OF APPLICATIONS
Optical Character Recognition (OCR)
Handwritten: sorting letters by postal code. Printed texts: reading machines for blind people, digitalization of text documents.
Biometrics
Face recognition, verification, retrieval. Finger prints recognition. Speech recognition.
Diagnostic systems
Medical diagnosis: X-Ray, EKG (ElectroCardioGraph) analysis.
Military applications
Automated Target Recognition (ATR). Image segmentation and analysis (recognition from aerial or satelite photographs).
PATTERN RECOGNITION APPLICATIONS BY PROBLEM DOMAINS
PATTERN RECOGNITION MODEL
THE STATISTICAL WAY
10
GRID BY GRID COMPARISON
A A B
Grid by Grid Comparison
11
GRID BY GRID COMPARISON
A A B
0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1
No of Mismatch= 3
12
GRID BY GRID COMPARISON
A A B
Grid by Grid Comparison
13
GRID BY GRID COMPARISON
A A B
0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1
No of Mismatch= 9
1 0 0 0 1
1 1 1 1 1
1 0 1 0 1
0 1 1 1 0
14
*/-+1@# PROBLEM WITH GRID BY GRID COMPARISON
Time
to recognize a pattern - Proportional to the number of stored patterns ( Too costly with the increase of number of patterns stored )
A-Z
a-z
0-9
Solution Artificial Intelligence
15
HUMAN AND MACHINE PERCEPTION
We are often influenced by the knowledge of how patterns are modeled and recognized in nature when we develop pattern recognition algorithms. Research on machine perception also helps us gain deeper understanding and appreciation for pattern recognition systems in nature. Yet, we also apply many techniques that are purely numerical and do not have any correspondence in natural systems.
16
PATTERN RECOGNITION
Two
Phase : Learning and Detection. to learn is higher.
Time
Driving a car
Difficult
natural.
to learn but once learnt it becomes
Can
use AI learning methodologies such as:
Neural Network. Machine Learning.
17
BASIC CONCEPT
Hidden state Feature vector
Feature
Cannot be directly measured. - Patterns with equal hidden state belong to the same class.
vectorPatterns with equal hidden state belong to the same class. Task- To design a classifer (decision rule) which decides about a hidden state based on an observation.
18
Task: jockey-hoopster recognition. The set of hidden state Y is {H,J}
EXAMPLE
The feature space is X2
19
LEARNING
How can machine learn the rule from data?
Supervised learning: a teacher provides a category label or cost for each pattern in the training set. Unsupervised learning: the system forms clusters or natural groupings of the input patterns.
20
CLASSIFICATION VS. CLUSTERING
Classification
(known categories) Clustering (creation of new categories)
Category A
Category B
(Supervised Classification)
Classification
(Unsupervised Classification) 21
Clustering
PATTERN RECOGNITION PROCESS (CONT.)
Decision
Post- processing
Classification
Feature Extraction
Segmentation
Sensing
22
input
PATTERN RECOGNITION PROCESS
Data acquisition and sensing: Measurements of physical variables. Important issues: bandwidth, resolution , etc. Pre-processing: Removal of noise in data. Isolation of patterns of interest from the background. Feature extraction: Finding a new representation in terms of features. Classification Using features and learned models to assign a pattern to a category. Post-processing Evaluation of confidence in decisions.
23
Sistem PR
Pattern
Sensors and preprocessing
Feature extraction
Classifier
Class assignment
Teacher
Learning algorithm
24
CASE STUDY
Fish
Classification:
Sea Bass / Salmon.
Salmon
Problem:
Sorting incoming fish on a conveyor belt according to species.
Assume that we have only two kinds of fish:
Sea bass. Salmon.
25
Sea-bass
CASE STUDY (CONT.)
What
can cause problems during sensing?
Lighting conditions. Position of fish on the conveyor belt. Camera noise. etc
What
are the steps in the process?
1. Capture
image. 2. Isolate fish 3. Take measurements 4. Make decision
26
CASE STUDY (CONT.)
Pre-processing
Feature Extraction
Classification
Sea Bass
Salmon
27
CASE STUDY (CONT.)
Pre-Processing:
Image enhancement Separating touching or occluding fish. Finding the boundary of the fish.
28
HOW TO SEPARATE SEA BASS FROM SALMON?
Possible
features to be used:
Length Lightness Width Number and shape of fins Position of the mouth Etc
Assume a fisherman told us that a sea bass is generally longer than a salmon. Even though sea bass is longer than salmon on the average, there are many examples of fish where this observation does not hold.
29
HOW TO SEPARATE SEA BASS FROM SALMON?
To
improve recognition, we might have to use more than one feature at a time.
Single features might not yield the best performance. Combinations of features might yield better performance.
x1 x1 : lightness x x : width 2 2
30
FEATURE SELECTION
Good features
Bad features
31
DECISION BOUNDARY
32
DECISION BOUNDARY (CONT.)
More complex model result more complex boundary
33
DECISION BOUNDARY (CONT.)
Different criteria lead to different decision boundaries
34
DECISION BOUNDARY (CONT.)
What
if a customers find Sea bass in there Salmon can? should also consider costs of different errors we make in our decisions.
We
35
DECISION BOUNDARY (CONT.)
For
example, if the fish packing company knows that:
Customers who buy salmon will object vigorously if they see sea bass in their cans. Customers who buy sea bass will not be unhappy if they occasionally see some expensive salmon in their cans.
How
does this knowledge affect our decision?
36
CASE STUDY (CONT.)
Issues
with feature extraction:
Correlated features do not necessary improve performance. It might be difficult to extract certain features. It might be computationally expensive to extract many features. Missing Features. Domain Knowledge.
37
THE DESIGN CYCLE
Collect Data
Collecting training and testing data.
Chose Features.
Domain dependence.
Chose Model
Domain dependence.
Train
Supervised learning Unsupervised learning.
Evaluate
Performance with future data
38
Q&A
39
TOPIC SEARCHING
40
