Pattern Recognition in Computer Science
undefined
Mestrado em Ciência de Computadores
Mestrado Integrado em Engenharia de Redes e
Sistemas Informáticos
VC 15/16 – TP14
Pattern Recognition
M
i
g
u
e
l
T
a
v
a
r
e
s
C
o
i
m
b
r
a
VC 15/16 - TP14 - Pattern Recognition
Outline
•
Introduction to Pattern Recognition
•
Statistical Pattern Recognition
•
Classifiers
VC 15/16 - TP14 - Pattern Recognition
Topic: Introduction to Pattern
Recognition
•
Introduction to Pattern Recognition
•
Statistical Pattern Recognition
•
Classifiers
VC 15/16 - TP14 - Pattern Recognition
http://www.flickr.com/photos/kimbar/2027234083/
This is a
horse
VC 15/16 - TP14 - Pattern Recognition
This is a
horse
http://www.flickr.com/photos/genewolf/2031802050/
VC 15/16 - TP14 - Pattern Recognition
This is a...
Horse?
http://www.flickr.com/photos/masheeebanshee/413465808/
VC 15/16 - TP14 - Pattern Recognition
•
I
c
a
n
m
a
n
i
p
u
l
a
t
e
i
m
a
g
e
s
.
•
I
w
a
n
t
t
o
m
a
k
e
d
e
c
i
s
i
o
n
s
!
•
C
l
a
s
s
i
f
y
/
I
d
e
n
t
i
f
y
f
e
a
t
u
r
e
s
.
•
R
e
c
o
g
n
i
z
e
p
a
t
t
e
r
n
s
.
Decisions
VC 15/16 - TP14 - Pattern Recognition
One definition
•
Pattern recognition
"the act of taking in raw data and taking an
action based on the category of the data".
Wikipedia
•
How do I do this so well?
•
How can I make machines do this?
VC 15/16 - TP14 - Pattern Recognition
The problem
Do you ‘see’
a horse?
VC 15/16 - TP14 - Pattern Recognition
Mathematics
•
We only deal with numbers.
–
How do we represent knowledge?
–
How do we represent visual features?
–
How do we classify them?
•
Very complex problem!!
–
Let’s break it into smaller ones...
Typical PR system
VC 15/16 - TP14 - Pattern Recognition
VC 15/16 - TP14 - Pattern Recognition
Sensor
•
In our specific case:
–
Image acquiring mechanism.
–
Let’s assume we don’t control it.
One observation = One Image
Video = Multiple Observations
VC 15/16 - TP14 - Pattern Recognition
Feature Extraction
•
What exactly are features?
–
Colour, texture, shape, etc.
–
Animal with 4 legs.
–
Horse.
–
Horse jumping.
•
These vary a lot!
•
Some imply some sort of ‘recognition’
e.g. How do I know the horse is jumping?
VC 15/16 - TP14 - Pattern Recognition
Broad classification of features
•
Low-level
–
Colour, texture
•
Middle-level
–
Object with head and four legs.
–
Object moving up.
–
Horse
•
High-level
–
Horse jumping.
–
Horse competition.
VC 15/16 - TP14 - Pattern Recognition
•
Objective
•
Directly reflect specific image and video
features.
–
Colour
–
Texture
–
Shape
–
Motion
–
Etc.
Low-level features
VC 15/16 - TP14 - Pattern Recognition
•
Some degree of subjectivity
•
They are typically one solution of a
problem with multiple solutions.
•
Examples:
–
Segmentation
–
Optical Flow
–
Identification
–
Etc.
Middle-level features
VC 15/16 - TP14 - Pattern Recognition
High-level features
•
Semantic Interpretation
•
Knowledge
•
Context
•
Examples:
–
This person suffers from epilepsy.
–
The virus attacks the cell with some degree of
intelligence.
–
This person is running from that one.
How do humans
do this so well?
VC 15/16 - TP14 - Pattern Recognition
The semantic gap
•
Fundamental problem of current research!
L
o
w
-
l
e
v
e
l
:
-
Colour
-
Texture
-
Shape
-
…
H
i
g
h
-
l
e
v
e
l
:
-
Interpretation
-
Decision
-Understanding
-
…
Now what??
How do i cross this
bridge?
VC 15/16 - TP14 - Pattern Recognition
Features & Decisions
L
o
w
-
L
e
v
e
l
F
e
a
t
u
r
e
s
M
i
d
d
l
e
-
L
e
v
e
l
F
e
a
t
u
r
e
s
H
i
g
h
-
L
e
v
e
l
F
e
a
t
u
r
e
s
Decision
Decision
Various
Possible
Solutions
One
Solution
How do I
decide?
VC 15/16 - TP14 - Pattern Recognition
Classification
C
l
a
s
s
i
f
i
e
r
Middle-Level Features
High-Level Features
M inputs, N outputs
VC 15/16 - TP14 - Pattern Recognition
Layers of classification
S
e
c
o
n
d
l
a
y
e
r
o
f
c
l
a
s
s
i
f
i
c
a
i
t
o
n
F
i
r
s
t
l
a
y
e
r
o
f
c
l
a
s
s
i
f
i
c
a
i
t
o
n
VC 15/16 - TP14 - Pattern Recognition
Classifiers
•
How do I map my M inputs to my N
outputs?
•
Mathematical tools:
–
Distance-based classifiers.
–
Rule-based classifiers.
–
Neural Networks.
–
Support Vector Machines
–
...
VC 15/16 - TP14 - Pattern Recognition
Types of PR methods
•
Statistical pattern recognition
–
based on statistical characterizations of
patterns, assuming that the patterns are
generated by a probabilistic system.
•
Syntactical (or structural) pattern
recognition
–
based on the structural interrelationships of
features.
VC 15/16 - TP14 - Pattern Recognition
Topic: Statistical Pattern
Recognition
•
Introduction to Pattern Recognition
•
Statistical Pattern Recognition
•
Classifiers
VC 15/16 - TP14 - Pattern Recognition
Is Porto in Portugal?
VC 15/16 - TP14 - Pattern Recognition
Porto is in Portugal
•
I want to make decisions.
–
Is Porto in Portugal?
•
I know certain things.
–
A world map including cities and countries.
•
I can make this decision!
–
P
o
r
t
o
i
s
i
n
P
o
r
t
u
g
a
l
.
•
I
h
a
d
e
n
o
u
g
h
a
p
r
i
o
r
i
k
n
o
w
l
e
d
g
e
t
o
m
a
k
e
t
h
i
s
d
e
c
i
s
i
o
n
.
VC 15/16 - TP14 - Pattern Recognition
What if I don’t have a map?
•
I still want to make this decision.
•
I observe:
–
Amarante has coordinates x
1
,y
1
and is in Portugal.
–
Viseu has coordinates x
2
, y
2
and is in Portugal.
–
Vigo has coordinates x
3
, y
3
and is in Spain.
•
I classify:
–
P
o
r
t
o
i
s
c
l
o
s
e
t
o
A
m
a
r
a
n
t
e
a
n
d
V
i
s
e
u
s
o
P
o
r
t
o
i
s
i
n
P
o
r
t
u
g
a
l
.
•
What if I try to classify
Valença
?
VC 15/16 - TP14 - Pattern Recognition
Statistical PR
•
I
u
s
e
d
s
t
a
t
i
s
t
i
c
s
t
o
m
a
k
e
a
d
e
c
i
s
i
o
n
.
–
I
c
a
n
m
a
k
e
d
e
c
i
s
i
o
n
s
e
v
e
n
w
h
e
n
I
d
o
n
’
t
h
a
v
e
f
u
l
l
a
p
r
i
o
r
i
k
n
o
w
l
e
d
g
e
o
f
t
h
e
w
h
o
l
e
p
r
o
c
e
s
s
.
–
I
c
a
n
m
a
k
e
m
i
s
t
a
k
e
s
.
•
H
o
w
d
i
d
I
r
e
c
o
g
n
i
z
e
t
h
i
s
p
a
t
t
e
r
n
?
–
I
l
e
a
r
n
e
d
f
r
o
m
p
r
e
v
i
o
u
s
o
b
s
e
r
v
a
t
i
o
n
s
w
h
e
r
e
I
k
n
e
w
t
h
e
c
l
a
s
s
i
f
i
c
a
t
i
o
n
r
e
s
u
l
t
.
–
I
c
l
a
s
s
i
f
i
e
d
a
n
e
w
o
b
s
e
r
v
a
t
i
o
n
.
What
pattern?
VC 15/16 - TP14 - Pattern Recognition
Back to the Features
•
F
e
a
t
u
r
e
F
i
•
F
e
a
t
u
r
e
F
i
w
i
t
h
N
v
a
l
u
e
s
.
•
Feature vector F with
M features.
•
Naming conventions:
–
E
l
e
m
e
n
t
s
o
f
a
f
e
a
t
u
r
e
v
e
c
t
o
r
a
r
e
c
a
l
l
e
d
c
o
e
f
f
i
c
i
e
n
t
s
.
–
F
e
a
t
u
r
e
s
m
a
y
h
a
v
e
o
n
e
o
r
m
o
r
e
c
o
e
f
f
i
c
i
e
n
t
s
.
–
F
e
a
t
u
r
e
v
e
c
t
o
r
s
m
a
y
h
a
v
e
o
n
e
o
r
m
o
r
e
f
e
a
t
u
r
e
s
.
VC 15/16 - TP14 - Pattern Recognition
Back to our Porto example
•
I’ve classified that Porto is in Portugal.
•
What feature did I use?
–
Spatial location
•
Let’s get more formal
–
I
’
v
e
d
e
f
i
n
e
d
a
f
e
a
t
u
r
e
v
e
c
t
o
r
F
w
i
t
h
o
n
e
f
e
a
t
u
r
e
F
1
,
w
h
i
c
h
h
a
s
t
w
o
c
o
e
f
f
i
c
i
e
n
t
s
f
1
x
,
f
1
y
.
VC 15/16 - TP14 - Pattern Recognition
Feature Space
•
Feature Vector
–
Two total coefficients.
–
Can be seen as a
feature ‘space’ with
two orthogonal axis.
•
Feature Space
–
Hyper-space with N
dimensions where N is
the total number of
coefficients of my
feature vector.
VC 15/16 - TP14 - Pattern Recognition
A Priori
Knowledge
•
I
h
a
v
e
a
p
r
e
c
i
s
e
m
o
d
e
l
o
f
m
y
f
e
a
t
u
r
e
s
p
a
c
e
b
a
s
e
d
o
n
a
p
r
i
o
r
i
k
n
o
w
l
e
d
g
e
.
City is in Spain if F
1Y
>23
•
Great models = Great
classifications.
F
1Y
(London) = 100
London is in Spain (??)
I know the
border is
here
P
o
r
t
o
i
s
i
n
P
o
r
t
u
g
a
l
!
VC 15/16 - TP14 - Pattern Recognition
What if I don’t have a model?
•
I
n
e
e
d
t
o
l
e
a
r
n
f
r
o
m
o
b
s
e
r
v
a
t
i
o
n
s
.
–
Derive a model.
–
Direct classification.
•
Training stage.
–
Learn model
parameters.
•
Classification
‘Learned’
Model
VC 15/16 - TP14 - Pattern Recognition
Classes
•
In our example, cities
can belong to:
–
Portugal
–
Spain
•
I
h
a
v
e
t
w
o
c
l
a
s
s
e
s
o
f
c
i
t
i
e
s
.
•
A
c
l
a
s
s
r
e
p
r
e
s
e
n
t
s
a
s
u
b
-
s
p
a
c
e
o
f
m
y
f
e
a
t
u
r
e
s
p
a
c
e
.
SPAIN
PORTUGAL
VC 15/16 - TP14 - Pattern Recognition
Classifiers
•
A
C
l
a
s
s
i
f
i
e
r
C
m
a
p
s
a
c
l
a
s
s
i
n
t
o
t
h
e
f
e
a
t
u
r
e
s
p
a
c
e
.
•
Various types of classifiers.
–
Nearest-Neighbours.
–
Bayesian.
–
Soft-computing machines.
–
Etc...
VC 15/16 - TP14 - Pattern Recognition
Topic: Classifiers
•
Introduction to Pattern Recognition
•
Statistical Pattern Recognition
•
Classifiers
VC 15/16 - TP14 - Pattern Recognition
Distance to Mean
•
I can represent a
class by its mean
feature vector.
•
To classify a new
object, I choose the
class with the closest
mean feature vector.
•
Different distance
measures!
Euclidean
Distance
VC 15/16 - TP14 - Pattern Recognition
Possible Distance Measures
•
L1 Distance
•
Euclidean Distance
(L2 Distance)
L1 or
Taxicab
Distance
VC 15/16 - TP14 - Pattern Recognition
Gaussian Distribution
•
Defined by two
parameters:
–
Mean:
μ
–
Variance:
σ
2
•
Great approximation
to the distribution of
many phenomena.
–
Central Limit Theorem
VC 15/16 - TP14 - Pattern Recognition
Multivariate Distribution
•
For N dimensions:
•
Mean feature vector:
•
Covariance Matrix:
VC 15/16 - TP14 - Pattern Recognition
Mahalanobis Distance
•
Based on the
covariance of
coefficients.
•
Superior to
the Euclidean
distance.
VC 15/16 - TP14 - Pattern Recognition
K-Nearest Neighbours
•
Algorithm
–
Choose the closest K
neighbours to a new
observation.
–
C
l
a
s
s
i
f
y
t
h
e
n
e
w
o
b
j
e
c
t
b
a
s
e
d
o
n
t
h
e
c
l
a
s
s
o
f
t
h
e
s
e
K
o
b
j
e
c
t
s
.
•
Characteristics
–
Assumes no model.
–
Does not scale very
well...
VC 15/16 - TP14 - Pattern Recognition
Resources
•
Gonzalez & Woods, 3rd Ed, Chapter 12.
•
Andrew Moore, Statistic Data Mining
Tutorial,
http://www.autonlab.org/tutorials/
Dive into the world of pattern recognition, where data is analyzed to make decisions and identify features. Explore statistical pattern recognition, classifiers, and the process of recognizing patterns in images. Learn how computers see and interpret visual data, and the challenges of representing knowledge and features mathematically. Discover the complex problem-solving involved in pattern recognition systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
VC 15/16 TP14 Pattern Recognition Mestrado em Ci ncia de Computadores Mestrado Integrado em Engenharia de Redes e Sistemas Inform ticos Miguel Tavares Coimbra
Outline Introduction to Pattern Recognition Statistical Pattern Recognition Classifiers VC 15/16 - TP14 - Pattern Recognition
Topic: Introduction to Pattern Recognition Introduction to Pattern Recognition Statistical Pattern Recognition Classifiers VC 15/16 - TP14 - Pattern Recognition
This is a horse VC 15/16 - TP14 - Pattern Recognition http://www.flickr.com/photos/kimbar/2027234083/
This is a horse VC 15/16 - TP14 - Pattern Recognition http://www.flickr.com/photos/genewolf/2031802050/
This is a... Horse? VC 15/16 - TP14 - Pattern Recognition http://www.flickr.com/photos/masheeebanshee/413465808/
Decisions I can manipulate images. I want to make decisions! Classify / Identify features. Recognize patterns. VC 15/16 - TP14 - Pattern Recognition
One definition Pattern recognition "the act of taking in raw data and taking an action based on the category of the data". Wikipedia How do I do this so well? How can I make machines do this? VC 15/16 - TP14 - Pattern Recognition
The problem Do you see a horse? What a computer sees VC 15/16 - TP14 - Pattern Recognition
Mathematics We only deal with numbers. How do we represent knowledge? How do we represent visual features? How do we classify them? Very complex problem!! Let s break it into smaller ones... VC 15/16 - TP14 - Pattern Recognition
Typical PR system Sensor Gathers the observations to be classified or described Feature Extraction Computes numeric or symbolic information from the observations; Classifier Does the actual job of classifying or describing observations, relying on the extracted features. VC 15/16 - TP14 - Pattern Recognition
Sensor In our specific case: Image acquiring mechanism. Let s assume we don t control it. One observation = One Image Video = Multiple Observations VC 15/16 - TP14 - Pattern Recognition
Feature Extraction What exactly are features? Colour, texture, shape, etc. Animal with 4 legs. Horse. Horse jumping. These vary a lot! Some imply some sort of recognition e.g. How do I know the horse is jumping? VC 15/16 - TP14 - Pattern Recognition
Broad classification of features Low-level Colour, texture Middle-level Object with head and four legs. Object moving up. Horse High-level Horse jumping. Horse competition. VC 15/16 - TP14 - Pattern Recognition
Low-level features Objective Directly reflect specific image and video features. Colour Texture Shape Motion Etc. VC 15/16 - TP14 - Pattern Recognition
Middle-level features Some degree of subjectivity They are typically one solution of a problem with multiple solutions. Examples: Segmentation Optical Flow Identification Etc. VC 15/16 - TP14 - Pattern Recognition
High-level features Semantic Interpretation Knowledge Context Examples: This person suffers from epilepsy. The virus attacks the cell with some degree of intelligence. This person is running from that one. How do humans do this so well? VC 15/16 - TP14 - Pattern Recognition
The semantic gap Fundamental problem of current research! High-level: -Interpretation -Decision -Understanding - Low-level: -Colour -Texture -Shape - Now what?? How do i cross this bridge? VC 15/16 - TP14 - Pattern Recognition
Features & Decisions Various Possible Solutions How do I decide? Middle-Level Features High-Level Features Low-Level Features Decision Decision One Solution VC 15/16 - TP14 - Pattern Recognition
Classification Middle-Level Features High-Level Features Horse Competition Classifier Rider Horse Jumping Upward Motion M inputs, N outputs VC 15/16 - TP14 - Pattern Recognition
Layers of classification Brown Second layer of classificaiton First layer of classificaiton Horse Head Competition Four legs Rider ... Horse Jumping Upward Motion ... ... VC 15/16 - TP14 - Pattern Recognition
Classifiers How do I map my M inputs to my N outputs? Mathematical tools: Distance-based classifiers. Rule-based classifiers. Neural Networks. Support Vector Machines ... VC 15/16 - TP14 - Pattern Recognition
Types of PR methods Statistical pattern recognition based on statistical characterizations of patterns, assuming that the patterns are generated by a probabilistic system. Syntactical (or structural) pattern recognition based on the structural interrelationships of features. VC 15/16 - TP14 - Pattern Recognition
Topic: Statistical Pattern Recognition Introduction to Pattern Recognition Statistical Pattern Recognition Classifiers VC 15/16 - TP14 - Pattern Recognition
Is Porto in Portugal? VC 15/16 - TP14 - Pattern Recognition
Porto is in Portugal I want to make decisions. Is Porto in Portugal? I know certain things. A world map including cities and countries. I can make this decision! Porto is in Portugal. I had enough a priori knowledge to make this decision. VC 15/16 - TP14 - Pattern Recognition
What if I dont have a map? I still want to make this decision. I observe: Amarante has coordinates x1,y1 and is in Portugal. Viseu has coordinates x2, y2 and is in Portugal. Vigo has coordinates x3, y3 and is in Spain. I classify: Porto is close to Amarante and Viseu so Porto is in Portugal. What if I try to classify Valen a? VC 15/16 - TP14 - Pattern Recognition
Statistical PR I used statistics to make a decision. I can make decisions even when I don t have full a priori knowledge of the whole process. I can make mistakes. How did I recognize this pattern? I learned from previous observations where I knew the classification result. I classified a new observation. What pattern? VC 15/16 - TP14 - Pattern Recognition
Back to the Features Feature Fi Naming conventions: Elements of a feature vector are called coefficients. Features may have one or more coefficients. Feature vectors may have one or more features. f F = i i Feature Fiwith N values. i i f F , 1 = ,..., f f 2 i iN Feature vector F with M features. F F F | 2 1 = | ... | F M VC 15/16 - TP14 - Pattern Recognition
Back to our Porto example I ve classified that Porto is in Portugal. What feature did I use? Spatial location Let s get more formal I ve defined a feature vector Fwith one feature F1, which has two coefficients f1x, f1y. ] [ 1 F F = = [ , ] f xf 1 1 y VC 15/16 - TP14 - Pattern Recognition
Feature Space Feature Vector Two total coefficients. Can be seen as a feature space with two orthogonal axis. Feature Space Hyper-space with N dimensions where N is the total number of coefficients of my feature vector. Feature Space 35 30 Vigo 25 20 Y Coordinate 15 10 Braga 5 Amarante 0 Porto -2 0 2 4 6 8 10 12 -5 -10 X Coordinate VC 15/16 - TP14 - Pattern Recognition
A Priori Knowledge I have a precise model of my feature space based on a priori knowledge. City is in Spain if F1Y>23 Great models = Great classifications. F1Y(London) = 100 London is in Spain (??) I know the border is here Feature Space 35 30 Vigo 25 20 Y Coordinate 15 10 Braga 5 Amarante 0 Porto -2 0 2 4 6 8 10 12 Porto is in Portugal! -5 -10 X Coordinate VC 15/16 - TP14 - Pattern Recognition
What if I dont have a model? I need to learn from observations. Derive a model. Direct classification. Training stage. Learn model parameters. Classification Feature Space 35 30 Vigo 25 20 Y Coordinate Learned Model 15 10 Braga 5 Amarante 0 Porto -10 0 10 20 30 -5 -10 X Coordinate VC 15/16 - TP14 - Pattern Recognition
Classes In our example, cities can belong to: Portugal Spain I have two classes of cities. A class represents a sub-space of my feature space. Feature Space SPAIN 35 30 Vigo 25 20 Y Coordinate 15 10 Braga PORTUGAL 5 Amarante 0 Porto -2 0 2 4 6 8 10 12 -5 -10 X Coordinate VC 15/16 - TP14 - Pattern Recognition
Classifiers A Classifier C maps a class into the feature space. , true y K = ( , ) C x y Spain , false otherwise Various types of classifiers. Nearest-Neighbours. Bayesian. Soft-computing machines. Etc... VC 15/16 - TP14 - Pattern Recognition
Topic: Classifiers Introduction to Pattern Recognition Statistical Pattern Recognition Classifiers VC 15/16 - TP14 - Pattern Recognition
Distance to Mean I can represent a class by its mean feature vector. C = Feature Space 35 30 Spain Euclidean Distance F 25 To classify a new object, I choose the class with the closest mean feature vector. Different distance measures! 20 Y Coordinate 15 10 Portugal 5 0 Porto -10 0 10 20 30 -5 -10 X Coordinate VC 15/16 - TP14 - Pattern Recognition
Possible Distance Measures L1 Distance N = x 1 L1 or Taxicab Distance = L 1 ( ) ( ) S x v x N 1 Euclidean Distance (L2 Distance) N ( ) = x 1 2 = L2 ( ) ( ) S x v x N 1 VC 15/16 - TP14 - Pattern Recognition
Gaussian Distribution Defined by two parameters: Mean: Variance: 2 Great approximation to the distribution of many phenomena. Central Limit Theorem 2 1 ( ) x u = ( ) exp f x 2 2 2 VC 15/16 - TP14 - Pattern Recognition
Multivariate Distribution For N dimensions: Mean feature vector: Covariance Matrix: = F VC 15/16 - TP14 - Pattern Recognition
Mahalanobis Distance Based on the covariance of coefficients. Superior to the Euclidean distance. VC 15/16 - TP14 - Pattern Recognition
K-Nearest Neighbours Algorithm Choose the closest K neighbours to a new observation. Classify the new object based on the class of these K objects. Characteristics Assumes no model. Does not scale very well... VC 15/16 - TP14 - Pattern Recognition
Resources Gonzalez & Woods, 3rd Ed, Chapter 12. Andrew Moore, Statistic Data Mining Tutorial, http://www.autonlab.org/tutorials/ VC 15/16 - TP14 - Pattern Recognition
