euclidean distance calculation

[jimgardener]

hi
i was trying to learn face recognition using eigenfaces .i came across
a face recog engine written by konrad at www.darnok.com. I came
across the part about euclidean distance calculation in this..can
someone explain the mechanism/maths in it
here are some code snippets in java (from
apollo.nemesis.EigenFaceComputation.java)

the program creates a matrix of weights from training images and then
creates a 1 dim array containing weights calculated from an image to
be checked.

/* wk=weights from taining images , nrfaces=total images in training
set
MAGIC_NR=number of facespaces used for recognition
faceSpace is a double[][] containig calculated facespace
*/
double[][] wk = new double[nrfaces][MAGIC_NR];

for (image = 0; image < nrfaces; image++) {
for (j = 0; j < MAGIC_NR; j++) {
temp = 0.0;
for ( pix=0; pix< length; pix++)
temp += faceSpace[j][pix] * faces[image][pix];
wk[image][j] = Math.abs( temp );
}
}

then input weights is calculated from image to be checked
inputFace is a double[] to represent image to be checked

double[] input_wk = new double[MAGIC_NR];
for (j = 0; j < MAGIC_NR; j++) {
temp = 0.0;
for ( pix=0; pix <length; pix++)
temp += faceSpace[j][pix] * inputFace[pix];

input_wk[j] = Math.abs( temp );
}
I understood the maths till now..
here is the euclidean distance calculation..this is the part i wish to
know in detail..is this the correct way from a maths viewpoint? Can
someone explain the maths pls?

int idx = 0;
double[] distance = new double[MAGIC_NR];
double[] minDistance = new double[MAGIC_NR];

for (image = 0; image < nrfaces; image++) {
for (j = 0; j < MAGIC_NR; j++)
distance[j] = Math.abs(input_wk[j] - wk[image][j]);
if (image == 0)
System.arraycopy(distance,0,minDistance,0,MAGIC_NR);
if (sum(minDistance) > sum(distance)) {
idx = image;
System.arraycopy(distance,0,minDistance,0,MAGIC_NR);

}
}
divide(minDistance, max(minDistance)+1);
double minD = sum(minDistance);
System.out.println("image is idx "+idx+" distance from face: "+minD);

thanx
jim

 

[Lew]

here is the euclidean distance calculation..this is the part i [sic] wish to
know in detail..is this the correct way from a maths viewpoint? Can
someone explain the maths pls?

int idx = 0;
double[] distance = new double[MAGIC_NR];
double[] minDistance = new double[MAGIC_NR];

for (image = 0; image < nrfaces; image++) {
for (j = 0; j < MAGIC_NR; j++)
distance[j] = Math.abs(input_wk[j] - wk[image][j]);
if (image == 0)
System.arraycopy(distance,0,minDistance,0,MAGIC_NR);
if (sum(minDistance) > sum(distance)) {
idx = image;
System.arraycopy(distance,0,minDistance,0,MAGIC_NR);

}
}
divide(minDistance, max(minDistance)+1);
double minD = sum(minDistance);
System.out.println("image is idx "+idx+" distance from face: "+minD);

The notation with vectors (not Vectors as in Java, but vectors as in maths) is
always a bit hairy, so be patient.

System.arraycopy( distance, 0, minDistance, 0. MAGIC_NR ) copies from the left
'distance' array to the right 'minDistance' array.

The Euclidean distance is a measure, or metric, of "distance" between two
vectors of the same length. The length in this case is MAGIC_NR. Let's
abstract out the vector part to make life easier.

The distance between two vectors 'input' and 'image' is a vector, 'distance'.
Each component of this difference vector is the absolute value of the
difference between corresponding components of the operands.

{ 3, 3, 2, 1 } .distanceFrom( { 1, 4, 2, 3 } ) == { 2, 1, 0, 2 }.

It's sort of like subtraction: distance = Math.abs( input - image );

What we have is a pool of faces, size 'nrfaces', that we compare to the
'input' face for the closest one. So we iterate through the pool, and compare
each face, index 'image', to the 'input' one.

Face closestTo( Face input )
{
Face minD = facePool.get( Random.nextInt( nrFaces )); //
for ( Face face : facePool )
{
Face distance = face.distanceFrom( input );
if ( distance.compareTo( minD ) < 0 )
{
minD = distance;
}
}
return minD;
}

Face.sum() simply returns the sum of the double components of the Face array.
Face.max() returns the max double value in the Face array.
Face.divide( double value ) divides every array component by the double value.

minD.divide( minD.max() + 1 ) normalizes all the values of the internal array
so that none reaches 1.0.

Now to the importance of sum(). The compareTo() compares two Faces by the sum
of their component array values.

{1, 2, 3, 4}.compareTo( {4, 2, 2, 3} ) == (10 - 11) == -1, so less than 0.

That means {1, 2, 3, 4} becomes the new 'minD' in that iteration of the loop.

If it wins, then normalization brings it down to {0.2, 0.4, 0.6, 0.8}. The
sum of all that is 2.0, and that is the "Euclidean distance" by the cited
algorithm.

 

[Lew]

Face closestTo( Face input )
{
Face minD = facePool.get( Random.nextInt( nrFaces ));

My mistake, should be

Face closest = facePool.get( 0 );
Face minD = closest.distanceFrom( input );

 

[jimgardener]

Face closest = facePool.get( 0 );
Face minD = closest.distanceFrom( input );

Lew
thanx,that made a lot of things clearer to me..however i have some
more doubts..silly as they may seem..

1.when normalising an array(of doubles)

is it myarray.divide(myarray.max())//this way there will be a 1 in the
array
or
myarray.divide(myarray.max()+1)// all vals will be less than 1

the reason why i ask is in the code he does at one
point(EigenFaceComputation.java:143)

for ( image = 0; image < nrfaces; image++) {
temp = max(faceSpace[image]); // Our max
for ( pix = 0; pix < faceSpace[0].length; pix++)
// Normalize
faceSpace[image][pix] = Math.abs( faceSpace[image][pix] / temp);
}

and then later to do normalisation of array minDistance
(EigenFaceComputation.java:273)

divide(minDistance, max(minDistance)+1);

 

[Lew]

1.when normalising an array(of doubles)

is it myarray.divide(myarray.max())//this way there will be a 1 in the
array
or
myarray.divide(myarray.max()+1)// all vals will be less than 1

the reason why i ask is in the code he does at one
point(EigenFaceComputation.java:143)

for ( image = 0; image < nrfaces; image++) {
temp = max(faceSpace[image]); // Our max
for ( pix = 0; pix < faceSpace[0].length; pix++)
// Normalize
faceSpace[image][pix] = Math.abs( faceSpace[image][pix] / temp);
}

You did not cite this code in your earlier post.

and then later to do normalisation of array minDistance
(EigenFaceComputation.java:273)

divide(minDistance, max(minDistance)+1);

That is a good question. What does your analysis of the code show you?

I ask because absolutely everything I told you before was based entirely and
only on information that you yourself posted. Now you ask a question based on
more information that you have that I don't. Therefore you are in a better
position to answer it than I am.

What I tried to show you before was how to reason about the information that
you have. I did not add to the information that you posted, nor bring in any
side research (e.g., I figured you were perfectly capable of researching
<http://en.wikipedia.org/wiki/Euclidean_distance>
without my having to point it out to you), nor comment on the correctness of
the algorithm (what if temp == 0.0?). In other words, all I did was rephrase
what you had already said - and it looked like an answer.

Apply the same principle to the parts of the code you have not yet shared with us.

 

[Dag Sunde]

Apply the same principle to the parts of the code you have not yet shared
with us.

Lew...

Your way of answering in this thread is a shining example on how
it _should_ be done!

As opposed to others (who I will not name here), you never berate,
descend into calling them idiots, or any unneccessary abuse.

Helpful, patient and polite.

Let us all spend a minute comparing our own way of responding to
this NG, and compare it to Lew's in this thread...

Thanks!

 

[jimgardener]

You did not cite this code in your earlier post.

Lew
thanx for the detailed reply..in fact i was referring to code written
by another one (konrad at www.darnok.com)..i forgot to include the
code..sorry

as for research..i am still in final school..not yet done college
maths..was doing a project about facerecognition subject..but i
learned some java ,c and python so thought i could come up with some
working code if i understood the mechanism involved..the java code at
darnok.com was my first intro to these calculations and math.. and
also bit unsure about the calc involved..is why i have to resort to
experts in groups..even my teachers couldn't help me much..(and in
this part of the world getting info from people(experts at that)is not
as easy as in U.S or Europe..)

thanx again
jim

 

[Lew]

Lew
thanx for the detailed reply..in fact i was referring to code written
by another one (konrad at www.darnok.com)..i forgot to include the
code..sorry

There is no need to apologize. My point was not that you should have included
the code - that was not necessary. Besides, you gave a link to it in your
first post - that is all that's really needed.

My point was for you to look at the pattern of how to think about the
darnok.com code. I purposefully did not follow the link you gave, in order to
provide an answer based entirely on the information you had cited. I was not
rebuking you but pointing out by example how the conclusions I reached were
derived entirely in the information you cited.

I could have easily applied the same reasoning myself to your follow-up
question. Remember, I pointed out, then asked,

That is a good question. What does your analysis of the code show you?

Seriously, it is an excellent question. Why did the author seemingly define
"normalization" one way in one part of the code, and differently in another?

The first step is to trust your insight. You had a mental alarm bell go off
on the contradiction. TRUST YOURSELF! If there's something tickling your
instincts, there probably *is* something to investigate. Investigate the hell
out of it!

I suspect a mistake on the author's part, myself. What happens if you divide
by 0.0 in the formula involving the simple max(), the one that does not add
one to the denominator?

Another concern: what if the factors exceed
(Double.MAX_VALUE / Face.length())?
(Here 'Face.length()' is a static method to report the internal (maths) vector
length.)

Then the sum() method of Face could return a value in excess of
Double.MAX_VALUE. Oh, my.

One might have numerics concerns about extremely small component values, too,
relevant perhaps to the difference calculations. We're just talking about the
normal numerics concerns when you deal with doubles. Presumably a custom Face
(or parent MathsVector) class would handle stuff like that under the hood.

Leading to your next Google task, Grasshopper. What do you bet that there
already exists out there an open-source maths library in Java that handles
vectors with appropriate numerics caution?

Assuming you find them, do they handle normalizing calculations efficiently?

Anyhow, use things like the Wikipedia article
<http://en.wikipedia.org/wiki/Euclidean_distance>
and other searches to double-check the author's algorithms and expressions
thereof. Trust your suspicions, they're usually well founded. Understanding
what predecessor coders /intended/ to do based on what they actually did is an
invaluable skill.