US 8,478,005 B2Granted

Method of performing facial recognition using genetically modified fuzzy linear discriminant analysis

AssigneeKing Fahd University of Petroleum and Minerals

InventorsAmar Khoukhi, Syed Faraz Ahmed

Life of this patent

Estimating the term…

Abstract

The method of performing facial recognition using genetic algorithm-modified fuzzy linear discriminant analysis (LDA) is based on the Fisherface LDA, with a modification being made in calculation of the membership function. Particularly, the membership function is computed using a pair of parameters α and β, which are optimized by a genetic algorithm in order to minimize the recognition error.

Claims12

Dependent claims

A computer-implemented method of performing facial recognition using genetic algorithm-modified fuzzy linear discriminant analysis, comprising the steps of

a) establishing a set of N test face images, where N is a non-zero, positive integer;
b) establishing a set of N training face images;
c) calculating a mean vector of all test face images as
m
′
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
′
,
where x′i represents an i-th test face image vector having a size M′, where i is an integer;
d) calculating a mean vector of all training face images as
m
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
,
where xi represents an i-th training face image vector having a size M;
e) calculating a total scatter matrix ST as
S
T
=
∑
k
=
1
N
⁢
(
x
k
-
m
)
⁢
(
x
k
-
m
)
T
,
where k is an integer;
f) calculating a set of orthonormal image vectors wi, wherein the set of orthonormal image vectors wi are eigenvectors of a covariance matrix C =PTP, where P is a matrix composed of mean centered images mi as column vectors placed side by side;
g) forming a projection matrix W of order (M×T) from the set of orthonormal image vectors wi, where T represents the total number of orthonormal image vectors wi;
h) calculating a first projection matrix WPCA as WPCA =argWmax|WTSTW|;
i) calculating a membership grade of a j-th image vector in the i-th class μij as
μ
ij
=
α
+
β
⁢
⁢
(
n
ij
k
)
if i is the same as a label of the j-th pattern, and as
μ
ij
=
β
⁢
⁢
(
n
ij
k
)
if i is not the same as the label of the j-th pattern, where nij represents a number of neighbors of the j-th vector that belong to the i-th class, k is an integer representing a number of nearest neighbors of the j-th image vector, and wherein β=1−α, and α represents an offset in membership grading assigned to a vector in its class;
j) optimizing α using a genetic algorithm in order to minimize recognition error;
k) calculating a mean of all vectors belonging to the l-th class as
m
_
l
=
∑
j
=
1
N
⁢
μ
ij
p
⁢
x
j
∑
j
=
1
N
⁢
μ
ij
p
,
where l is an integer;
l) calculating a between-class scatter matrix SB and a within-class scatter matrix SW as
S
B
=
∑
i
=
1
C
⁢
∑
j
=
1
N
⁢
μ
ij
p
⁡
(
m
_
l
-
m
)
·
(
m
_
l
-
m
)
T
and
S
W
=
∑
i
=
1
C
⁢
∑
x
k
∈
X
i
⁢
μ
ij
p
⁡
(
x
i
-
m
_
l
)
·
(
x
i
-
m
_
l
)
T
,
respectively, where Xi, represents a set of samples belonging to the i-th class, xk is the k-th image of the i-th class, and i=1, 2, . . . , c, where p is a fuzzy modifier, which is a constant controlling influence of fuzzy membership degree;
m) calculating a second projection matrix WLDA as
W
LDA
=
arg
⁢
⁢
max
W
⁢

W
T
⁢
S
B
⁢
W


W
T
⁢
S
W
⁢
W

;
n) calculating a total transformation matrix WT as WT=WLDAT·WPCAT;
o) calculating a set of test feature vectors y′k as y′k=WTx′k;
p) calculating a set of training feature vectors yk as yk=WTxk;
q) calculating a Euclidean distance between each of the test feature vectors y′k and each of the training feature vectors yk;
and
r) calculating a classification based upon the calculated Euclidean distances.

230 more elements

A system for performing facial recognition using genetic algorithm-modified fuzzy linear discriminant analysis, comprising:

a processor;
computer readable memory coupled to the processor;
a user interface coupled to the processor;
a display coupled to the processor;
software stored in the memory and executable by the processor, the software having:
means for establishing a set of N test face images, where N is a non-zero, positive integer;
means for establishing a set of N training face images;
means for calculating a mean vector of all test face images as
m
′
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
′
,
where x′i, represents an i-th test face image vector having a size M′, where i is an integer;
means for calculating a mean vector of all training face images as
m
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
,
where xi, represents an i-th training face image vector having a size M;
means for calculating a total scatter matrix ST as
S
T
=
∑
k
=
1
N
⁢
(
x
k
-
m
)
⁢
(
x
k
-
m
)
T
,
where k is an integer;
means for calculating a set of orthonormal image vectors wi, wherein the set of orthonormal image vectors wi, are eigenvectors of a covariance matrix C=PTP , where P is a matrix composed of mean centered images mi, as column vectors, placed side by side;
means for forming a projection matrix W of order (MX T) from the set of orthonormal image vectors wi where T represents the total number of orthonormal image vectors wi;
means for calculating a first projection matrix WPCA as WPCA=argWmax|WTSTW|;
means for calculating a membership grade of a j-th image vector in the i-th class μij as
μ
ij
=
α
+
β
⁡
(
n
ij
k
)
if i is the same as a label of the j-th pattern, and as
μ
ij
=
β
⁡
(
n
ij
k
)
if i is not the same as the label of the j-th pattern, where nij represents a number of neighbors of the j-th vector that belong to the i-th class, k is an integer representing a number of nearest neighbors of the j-th image vector, and wherein β=1−α, and α represents an offset in membership grading assigned to a vector in its class;
means for optimizing α using a genetic algorithm in order to minimize recognition error;
means for calculating a mean of all vectors belonging to the l-th class as
m
_
l
=
∑
j
=
1
N
⁢
μ
ij
p
⁢
x
j
∑
j
=
1
N
⁢
μ
ij
p
,
where l is an integer;
means for calculating a between-class scatter matrix SB and a within-class scatter matrix SW as
S
B
=
∑
i
=
1
C
⁢
∑
j
=
1
N
⁢
μ
ij
p
⁡
(
m
_
l
-
m
)
·
(
m
_
l
-
m
)
T
and
S
W
=
∑
i
=
1
C
⁢
∑
x
k
∈
X
i
⁢
μ
ij
p
⁡
(
x
i
-
m
_
l
)
·
(
x
i
-
m
_
l
)
T
,
respectively, where Xi, represents a set of samples belonging to the i-th class, xk is the k-th image of the i-th class, and i=1, 2, . . . , c, where p is a fuzzy modifier which is a constant controlling influence of fuzzy membership degree;
means for calculating a second projection matrix WLDA as
W
LDA
=
arg
⁢
⁢
max
W
⁢

W
T
⁢
S
B
⁢
W


W
T
⁢
S
W
⁢
W

;
means for calculating a total transformation matrix WT as WT=WLDAT·WPCAT;
means for calculating a set of test feature vectors y′k as y′k=WTx′k;
means for calculating a set of training feature vectors yk as yk=WTXk;
means for calculating a Euclidean distance between each of the test feature vectors y′k and each of the training feature vectors yk;
and
means for calculating a classification based upon the calculated Euclidean distances.

233 more elements

A computer software product that includes a non-transitory storage medium readable by a processor, the non-transitory storage medium having stored thereon a set of instructions for performing facial recognition using genetic algorithm-modified fuzzy linear discriminant analysis, the instructions comprising:

(a) a first sequence of instructions which, when executed by the processor, causes the processor to establish a set of N test face images, where N is a non-zero, positive integer;
(b) a second sequence of instructions which, when executed by the processor, causes the processor to establish a set of N training face images;
(c) a third sequence of instructions which, when executed by the processor, causes the processor to calculate a mean vector of all test face images as
m
′
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
′
,
where x′i represents an i-th test face image vector having a size M′, where i is an integer;
(d) a fourth sequence of instructions which, when executed by the processor, causes the processor to calculate a mean vector of all training face images as
m
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
,
where xi represents an i-th training face image vector having a size M;
(e) a fifth sequence of instructions which, when executed by the processor, causes the processor to calculate a total scatter matrix ST as
S
T
=
∑
k
=
1
N
⁢
(
x
k
-
m
)
⁢
(
x
k
-
m
)
T
;
(f) a sixth sequence of instructions which, when executed by the processor, causes the processor to calculate a set of orthonormal image vectors Wi, wherein the set of orthonormal image vectors wi, are eigenvectors of a covariance matrix C=PTP, where P is a matrix composed of mean centered images Mi, as column vectors, placed side by side;
(g) a seventh sequence of instructions which, when executed by the processor, causes the processor to form a projection matrix W of order (M×T) from the set of orthonormal image vectors wi, where T represents the total number of orthonormal image vectors wi;
(h) an eighth sequence of instructions which, when executed by the processor, causes the processor to calculate a first projection matrix WPCA as WPCA=argWmax|WTSTW;
(i) a ninth sequence of instructions which, when executed by the processor, causes the processor to calculate a membership grade of a j-th image vector in the i-th class μijas
μ
ij
=
α
+
β
⁡
(
n
ij
k
)
if i is the same as a label of the j-th pattern, and as
μ
ij
=
β
⁡
(
n
ij
k
)
if i is not the same as the label of the j-th pattern, where nij represents a number of neighbors of the j-th vector that belong to the i-th class, k is an integer representing a number of nearest neighbors of the j-th image vector, and wherein) β=1−α, and α represents an offset in membership grading assigned to a vector in its class;
(j) a tenth sequence of instructions which, when executed by the processor, causes the processor to optimize a using a genetic algorithm in order to minimize recognition error;
(k) an eleventh sequence of instructions which, when executed by the processor, causes the processor to calculate a mean of all vectors belonging to the l-th class as
m
_
l
=
∑
j
=
1
N
⁢
μ
ij
p
⁢
x
j
∑
j
=
1
N
⁢
μ
ij
p
,
where l is an integer;
(l) a twelfth sequence of instructions which, when executed by the processor, causes the processor to calculate a between-class scatter matrix SB and a within-class scatter matrix SW as
S
B
=
∑
i
=
1
C
⁢
∑
j
=
1
N
⁢
μ
ij
p
⁡
(
m
_
l
-
m
)
·
(
m
_
l
-
m
)
T
and
S
W
=
∑
i
=
1
C
⁢
∑
x
k
∈
X
i
⁢
μ
ij
p
⁡
(
x
i
-
m
_
l
)
·
(
x
i
-
m
_
l
)
T
,
respectively, where X, represents a set of samples belonging to the i-th class, xk is the k-th image of the i-th class, and i=1, 2, . . . , c, where p is a fuzzy modifier which is a constant controlling influence of fuzzy membership degree;
(m) a thirteenth sequence of instructions which, when executed by the processor, causes the processor to calculate a second projection matrix WLDA as
W
LDA
=
arg
⁢
⁢
max
W
⁢

W
T
⁢
S
B
⁢
W


W
T
⁢
S
W
⁢
W

;
(n) a fourteenth sequence of instructions which, when executed by the processor, causes the processor to calculate a total transformation matrix WT as WT=WLDAT·WPCAT;
(o) a fifteenth sequence of instructions which, when executed by the processor, causes the processor to calculate a set of test feature vectors y′k as y′k=WTx′k;
(p) a sixteenth sequence of instructions which, when executed by the processor, causes the processor to calculate a set of training feature vectors yk as Yk =W TXk ;
(q) a seventeenth sequence of instructions which, when executed by the processor, causes the processor to calculate a Euclidean distance between each of the test feature vectors y′k and each of the training feature vectors yk;
and
(r) an eighteenth sequence of instructions which, when executed by the processor, causes the processor to calculate a classification based upon the calculated Euclidean distances.

227 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/084,406Filed 11 Apr 2011
Published: US 2012/0257798 A111 Oct 2012
Granted: 2 Jul 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06V 40/172
Human faces, e.g. facial parts, sketches or expressions: classification, e.g. identification
G06F 18/2132
Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods: based on discrimination criteria, e.g.…
G06V 10/7715
Processing image or video features in feature spaces; using data integration or data reduction, e.g. principal component analysis [PCA] or…:…
G06V
Image and video recognition

Family

US 2012/0257798 A1Pre-grant publication · published 11 Oct 2012
US 8,478,005 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

A computer-implemented method of performing facial recognition using genetic algorithm-modified fuzzy linear discriminant analysis, comprising the steps of

a) establishing a set of N test face images, where N is a non-zero, positive integer;
b) establishing a set of N training face images;
c) calculating a mean vector of all test face images as
m
′
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
′
,
where x′i represents an i-th test face image vector having a size M′, where i is an integer;
d) calculating a mean vector of all training face images as
m
=
1
N
⁢
∑
i
=
1
N
⁢
x
i
,
where xi represents an i-th training face image vector having a size M;
e) calculating a total scatter matrix ST as
S
T
=
∑
k
=
1
N
⁢
(
x
k
-
m
)
⁢
(
x
k
-
m
)
T
,
where k is an integer;
f) calculating a set of orthonormal image vectors wi, wherein the set of orthonormal image vectors wi are eigenvectors of a covariance matrix C =PTP, where P is a matrix composed of mean centered images mi as column vectors placed side by side;
g) forming a projection matrix W of order (M×T) from the set of orthonormal image vectors wi, where T represents the total number of orthonormal image vectors wi;
h) calculating a first projection matrix WPCA as WPCA =argWmax|WTSTW|;
i) calculating a membership grade of a j-th image vector in the i-th class μij as
μ
ij
=
α
+
β
⁢
⁢
(
n
ij
k
)
if i is the same as a label of the j-th pattern, and as
μ
ij
=
β
⁢
⁢
(
n
ij
k
)
if i is not the same as the label of the j-th pattern, where nij represents a number of neighbors of the j-th vector that belong to the i-th class, k is an integer representing a number of nearest neighbors of the j-th image vector, and wherein β=1−α, and α represents an offset in membership grading assigned to a vector in its class;
j) optimizing α using a genetic algorithm in order to minimize recognition error;
k) calculating a mean of all vectors belonging to the l-th class as
m
_
l
=
∑
j
=
1
N
⁢
μ
ij
p
⁢
x
j
∑
j
=
1
N
⁢
μ
ij
p
,
where l is an integer;
l) calculating a between-class scatter matrix SB and a within-class scatter matrix SW as
S
B
=
∑
i
=
1
C
⁢
∑
j
=
1
N
⁢
μ
ij
p
⁡
(
m
_
l
-
m
)
·
(
m
_
l
-
m
)
T
and
S
W
=
∑
i
=
1
C
⁢
∑
x
k
∈
X
i
⁢
μ
ij
p
⁡
(
x
i
-
m
_
l
)
·
(
x
i
-
m
_
l
)
T
,
respectively, where Xi, represents a set of samples belonging to the i-th class, xk is the k-th image of the i-th class, and i=1, 2, . . . , c, where p is a fuzzy modifier, which is a constant controlling influence of fuzzy membership degree;
m) calculating a second projection matrix WLDA as
W
LDA
=
arg
⁢
⁢
max
W
⁢

W
T
⁢
S
B
⁢
W


W
T
⁢
S
W
⁢
W

;
n) calculating a total transformation matrix WT as WT=WLDAT·WPCAT;
o) calculating a set of test feature vectors y′k as y′k=WTx′k;
p) calculating a set of training feature vectors yk as yk=WTxk;
q) calculating a Euclidean distance between each of the test feature vectors y′k and each of the training feature vectors yk;
and
r) calculating a classification based upon the calculated Euclidean distances.

230 more elements

Facts

Application

13/084,406Filed 11 Apr 2011

Published

US 2012/0257798 A111 Oct 2012

Granted

2 Jul 2013

Term ends

Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06V 40/172
Human faces, e.g. facial parts, sketches or expressions: classification, e.g. identification
G06F 18/2132
Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods: based on discrimination criteria, e.g.…
G06V 10/7715
Processing image or video features in feature spaces; using data integration or data reduction, e.g. principal component analysis [PCA] or…:…
G06V
Image and video recognition