# How many thresholds and distance matrix are in Eigenface?

I edited my question trying to make it as short and precise.

I am developing a prototype of a facial recognition system for my Graduation Project. I use Eigenface and my main source is the document Turk and Pentland. It is available here: http://www.face-rec.org/algorithms/PCA/jcn.pdf.

My doubts focus on step 4 and 5.

I can not correctly interpret the number of thresholds: If two types of thresholds, or only one (Notice that the text speaks of two types but uses the same symbol). And again, my question is whether this (or these) threshold(s) is unique and global for all person or if each person has their own default.

I understand the steps to be calculated until an matrix O() of classes with weights or weighted. So this matrix O() is of dimension M'x P. Since M' equal to the amount of eigenfaces chosen and P the number of people.

What follows and confuses me. He speaks of two distances: the distance of a class against another, and also from a distance of one face to another. I call it D1 and D2 respectively. NOTE: In the training set there are M images in total, with F = M / P the number of images per person.

I understand that threshold(s) should be chosen empirically. But there must be a way to approximate. I was initially designing a matrix of distances D1() of dimension PxP. Where the row vector D(i) has the distances from the vector average class O(i) to each O(j), j = 1..P. Ie a "all vs all."

Until I came here, and what follows depends on whether I should actually choose a single global threshold for all. Or if I should be chosen for each individual value. Also not if they are 2 types: one for distance classes, and one for distance faces.

I have a theory as could proceed but not so supported by the concepts of Turk:

Stage Pre-Test:

Gender two matrices of distances D1 and D2: In D1 would be stored distances between classes, and in D2 distances between faces. This basis of the matrices W and A respectively.

Then, as indeed in the training set are P people, taking the F vectors columns D1 for each person and estimate a threshold T1 was in range [Min, Max]. Thus I will have a T1(i), i = 1..P

Separately have a T2 based on the range [Min, Max] out of all the matrix D2. This define is a face or not.

Step Test:

Buid a test set of image with a 1 image for each known person Itest = {Itest(1) ... Itest(P)}

For every image Itest(i) test:

Calculate the space face Atest = Itest - Imean

Calculate the weight vector Otest = UT * Atest

Calculating distances:


dist1(j) = distance(Otest, O (j)), j = 1..P

Af = project(Otest, U)

dist2 = distance(Atest, Af)

Evaluate recognition:


MinDist = Min(dist1)

For each j = 1..P

If dist2 > T2 then "not is face" else:

If MinDist <= T1(j) then "Subject identified as j" else "subject unidentified"

Then I take account of TFA and TFR and repeat the test process with different threshold values until I find the best approach gives to each person.

Already defined thresholds can put the system into operation unknown images. The algorithm is similar to the test.

I know I get out of "script" of the official documentation but at least this reasoning is the most logical place my head. I wondered if I could give guidance.

EDIT:

i No more to say that has not already been said and that may help clarify things.

Could anyone tell me if I'm okay tackled with my "theory"? I'm moving into my project, and if this is not the right way would appreciate some guidance and does not work and you wrong.

I'll begin with an apology since I will probably not answer your question as you expect (mostly because I don't understand exactly what you are asking).

Let's recap the process of face recognition using Eigenfaces.

1. take each image of $d_1$ by $d_2$ and treat it as a $d_1\cdot d_2$ vector (images should be in greyscale).
2. compute the mean of the vectors in hand, i.e. if you have m images, $X_{mean}=\frac{1}{m}\sum_{i=1}^mX_i$ and move your samples such that the a-prior mean is is zero, (this is an important step that is commonly forgotten).
3. compute the covariance matrix, $X^TX$. I assume in your scenario $d_1\cdot d_2>>m$, so you obtain the same information by finding $XX^T$ eigenvalues, this could improve your running time significantly.
4. project the $m$ images over the $p$ eigenvectors corresponding to the largest eigenvalues.
5. Given a new image, project it using the matrix $[u_1,...,u_p]$ and run K-Nearest-Neighbour (it should be more than sufficient for your purpose).

I think your original question is regarding the classification process after you have projected the images over the principal components. I the algorithm above, I suggest using KNN.

A few notes:

1. Eigenfaces don't work so well in reality, you must use images with very similar orientation, otherwise you won't achieve good results.
2. How to choose the k in the nearest neighbour algorithm? it depends on the number of training examples you have, obviously, there is no point of choosing k to be larger then the number of examples per person.
3. regarding point 3 above, $X^TX\in M_{(d_1\cdot d_2)\ x\ (d_1\cdot d_2)}, XX^T\in M_{mxm}$, so if your images are over 100 by 100, it's practically a must.
4. a couple of useful links:

Good Luck!

• http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
• After obtaining the first p Eigenfaces (which are the first p eigenvectors of $X^TX$), you have a matrix $O\in M_{(d_1\cdot d_2)\cdot p}$, given a new image $x\in \mathbb{R}^{d_1\cdot d_2}$, project $O^Tx$, this is a vector in $\mathbb{R}^p$.
• Now you have your samples in $\mathbb{R}^p$, your original training samples, and a new image that was projected over $O$, you know want to ask yourself how to classify the new image, one way is to decide by finding the closest vector using $L_2$ or $L_1$ this is the same as using KNN with k=1.
• compute the projection matrix $O$
• project your training data $z_i=O^Tx_i$.
• given a new sample, $\overline{x}$, compute $\overline{z}=O^T\cdot\overline{x}$
• now you have vectors in $\mathbb{R}^p$, you run the KNN which is an iterative way to find the k closest vectors, and classify your new vector as the majority of the k vectors.