The Mahalanobis Distance in Character
Recognition
Authored by Dan Frey 31 July 98
This sheet explores the use of the Mahalanobis Distance in character
recognition.
It defines a letters A, B, C, and D.
It creates a population of distorted letters to train a classifier.
It creates a test population of letters to test the classifier.
It allows you to compete against the Mahalanobis classifier.
ORIGIN := 1 Every matrix and vector in this sheet will begin with index number 1.
Here are the Canonical letters A B C and
D defined as matrices of 1s and 0s
?
0 0 1 0 0
? ?
1 1 1 1 0
? ?
0 1 1 1 0
? ?
1 1 1 1 0
?
? ? ? ? ? ? ? ?
?
0 1 0 1 0
? ?
1 0 0 1 1
? ?
1 0 0 0 1
? ?
1 0 0 0 1
?
A :=
?
1 0 0 0 1
?
B :=
?
1 1 1 1 0
?
C :=
?
1 0 0 0 0
?
D :=
?
1 0 0 0 1
?
?
1 1 1 1 1
? ?
1 0 0 1 1
? ?
1 0 0 0 1
? ?
1 0 0 0 1
?
? ? ? ? ? ? ? ?
?
1 0 0 0 1
? ?
1 1 1 1 0
? ?
0 1 1 1 0
? ?
1 1 1 1 0
?
Stretch the letters out into a vector of "features".
k := 1.. 25
Alin
k
:= A
k+ 5-5? ceil
?
?
k
?
?
, ceil
?
?
k
?
?
Blin
k
:= B
k+ 5-5? ceil
?
?
k
?
?
, ceil
?
?
k
?
?
?
5
? ?
5
? ?
5
? ?
5
?
Clin
k
:= C
k+ 5-5? ceil
?
?
k
?
?
, ceil
?
?
k
?
?
Dlin
k
:= D
k+ 5-5?ceil
?
?
k
?
?
, ceil
?
?
k
?
?
?
5
? ?
5
? ?
5
? ?
5
?
Reverse the letters. This makes the plots easier to read.
Alin
k
:= Alin
k
= 0 Blin
k
:= Blin
k
= 0 Clin
k
:= Clin
k
= 0 Dlin
k
:= Dlin
k
= 0
1
Define a function that will display the vector of
features as a matrix
DISPLAY(Llin) := for i ∈ 1.. 5
for j ∈ 1.. 5
L
i, j
← Llin
i+ 5?( j-1)
L
Here are a couple of plots that show what the Cononical letters look like.
DISPLAY Alin( )
DISPLAY Blin( )
DISPLAY Clin( )
DISPLAY Dlin( )
2
Create a population of fuzzed up letters
training_population := 300 Size of the training population. Has to be bigger than
the number of pixels.
pop := 1.. training_population
s
t
:= 0.01 How much random noise is superposed onto the pixels.
? ?
?????????????→
APOP
pop
:=
?
?
(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Alin
?
?
+ rnorm(25, 0, s
t
)
These populations have
? ?
?????????????→
been switched from
BPOP
pop
:=
?
?
(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Blin
?
?
+ rnorm(25, 0, s
t
)
positive to negative with
? ?
?????????????→
a 50/50 probability, then
CPOP
pop
:=
?
?
(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Clin
?
?
+ rnorm(25, 0, s
t
)
superposed with white
? ?
?????????????→
noise.
DPOP
pop
:=
?
?
(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Dlin
?
?
+ rnorm(25, 0, s
t
)
Here is an example of a fuzzed up A and a fuzzed up B.
DISPLAY APOP
5
? ?
( )
DISPLAY BPOP
3
? ?
( )
3
Compute Statistics of the Training Population
To create a Mahananobis distanace classifier, we need to deternime the mean and
cavariance matrices from the population of letters.
n := 1.. 25 m := 1.. 25
COVA := cvar
?
?
(
APOP
T
)
?
n
?
,
(
APOP
T
)
?
m
?
?
?
MEANA := mean
?
?
(
APOP
T
)
?
n
?
?
?
n, m n
COVB := cvar
?
?
(
BPOP
T
)
?
n
?
,
(
BPOP
T
)
?
m
?
?
?
MEANB := mean
?
?
(
BPOP
T
)
?
n
?
?
?
n, m n
COVC := cvar
?
?
(
CPOP
T
)
?
n
?
,
(
CPOP
T
)
?
m
?
?
?
MEANC := mean
?
?
(
CPOP
T
)
?
n
?
?
?
n, m n
COVD := cvar
?
?
(
DPOP
T
)
?
n
?
,
(
DPOP
T
)
?
m
?
?
?
MEAND := mean
?
?
(
DPOP
T
)
?
n
?
?
?
n , m n
The classifier will use the inverse of the covariance matrix, so let's compute it ahead of time.
- 1 - 1
INVCOVA := COVA INVCOVB := COVB
- 1 - 1
INVCOVC := COVC INVCOVD := COVD
4
I think it's interesting to note that the "mean" appearance of the letter A is incomprehensible
as an A. The reason is that we had an equal number of positive images and negative
images of A. The same applies to all the other letters. And yet the classifier successfully
identifies the letter A because it has a map of the correlations within the letter A.
DISPLAY MEANA( )
5
Define the Classifier
Here is the classifier function. It is very simple. You send it a letter (L) as an argument. It
computes the Mahalanobis distance from the letter to the class A, B, C, and D. Finally, it
classifies L as the letter with the smallest Mahalanobis distance.
Class(L) := MDA ← (L - MEANA)
T
?INVCOVA ?(L - MEANA)
MDB ← (L - MEANB)
T
?INVCOVB?(L - MEANB)
MDC ← (L - MEANC)
T
?INVCOVC?(L - MEANC)
MDD ← (L - MEAND)
T
?INVCOVD?(L - MEAND)
"A" if (MDA < MDB)?(MDA < MDC)?(MDA < MDD)
otherwise
"B" if (MDB < MDC)?(MDB < MDD)
otherwise
"C" if (MDC < MDD)
"D" otherwise
6
Test the Classifier
s := 0.6 How badly should the letters be fuzzed up.
tests := 10000 How many times should you test the classifier
test := 1.. tests
Answer
test
:= rand ← runif(1, 0, 4)
1
Make the four letters equally likely to appear
"A" if 0 ≤ rand ≤ 1
within the test batch.
"B" if 1 < rand ≤ 2
"C" if 2 < rand ≤ 3
"D" if 3 < rand ≤ 4
Create a batch of letters corresponding to the desired correct answers and appropriately
fuzzed up. This will be the batch of data to test our classifier.
?????????????→
L
test
:=
?
?
(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Alin
?
?
+ rnorm(25, 0, s) if Answer
test
= "A"
?????????????→
?(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Blin
?
?
+ rnorm(25, 0, s) if Answer
test
= "B"
?
?????????????→
?(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Clin
?
?
+ rnorm(25, 0, s) if Answer
test
= "C"
?
?????????????→
?(
2?floor
(
runif(1, 0, 2)
1
)
- 1
)
?Dlin
?
?
+ rnorm(25, 0, s) if Answer
test
= "D"
?
RIGHT
test
:=
(
Class
(
L
test
)
= Answer
test
)
mean(RIGHT) = 0.905
At sigma=0.6, the Mahalanobis classifier is right about 94% of the time!
Can you do as well in classifying the letters?
Also note how fast the Mahalanobis classifier operates.
7
Try Your Hand at Classification Answ 1 :=
Take a guess at which letter is represented in the following four graphs. When you're done,
change the varaible "Answ" to 1 and the answers will display. Did you get it right? Did the MD
C
DISPLAY L
1
( )
classifier?
D
DISPLAY L
2
( )
Answer
1?(Answ=1)
= "C"
Answer
2?(Answ=1)
= "D"
Class
?
?
L
1? (Answ=1)
?
?
= "C"
Class
?
?
L
2? (Answ=1)
?
?
= "D"
DISPLAY L
3
( )
DISPLAY L
4
( )
A
Answer
3?(Answ=1)
= "A" A Answer
4?(Answ=1)
= "A"
Class
?
?
L
3? (Answ=1)
?
?
= "A" Class
?
?
L
4? (Answ=1)
?
?
= "A"
8