euclidean distance calculation

Discussion in 'Java' started by jimgardener, Jan 25, 2008.

  1. jimgardener

    jimgardener Guest

    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
     
    jimgardener, Jan 25, 2008
    #1
    1. Advertising

  2. jimgardener

    Lew Guest

    jimgardener wrote:
    > 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
     
    Lew, Jan 25, 2008
    #2
    1. Advertising

  3. jimgardener

    Lew Guest

    Lew wrote:
    > 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 );

    > for ( Face face : facePool )
    > {
    > Face distance = face.distanceFrom( input );
    > if ( distance.compareTo( minD ) < 0 )
    > {

    closest = face;
    > minD = distance;
    > }
    > }

    return closest;
    > }


    --
    Lew
     
    Lew, Jan 25, 2008
    #3
  4. jimgardener

    jimgardener Guest


    >
    > Face closest = facePool.get( 0 );
    > Face minD = closest.distanceFrom( input );
    >
    > > for ( Face face : facePool )
    > > {
    > > Face distance = face.distanceFrom( input );
    > > if ( distance.compareTo( minD ) < 0 )
    > > {

    > closest = face;
    > > minD = distance;
    > > }
    > > }

    > return closest;
    > > }

    >


    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);
     
    jimgardener, Jan 26, 2008
    #4
  5. jimgardener

    Lew Guest

    jimgardener wrote:
    > 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.

    --
    Lew
     
    Lew, Jan 26, 2008
    #5
  6. jimgardener

    Dag Sunde Guest

    "Lew" <> wrote in message
    news:...
    <snipped/>
    > 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!

    --
    Dag.
     
    Dag Sunde, Jan 27, 2008
    #6
  7. jimgardener

    jimgardener Guest


    > 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
     
    jimgardener, Jan 27, 2008
    #7
  8. jimgardener

    Lew Guest

    jimgardener wrote:
    >> 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


    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.

    --
    Lew
     
    Lew, Jan 27, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick

    euclidean divider

    Patrick, Jan 25, 2005, in forum: VHDL
    Replies:
    0
    Views:
    518
    Patrick
    Jan 25, 2005
  2. Patrick

    Euclidean Multiplier (RS CODEC)

    Patrick, Feb 4, 2005, in forum: VHDL
    Replies:
    6
    Views:
    877
    Pieter Hulshoff
    Feb 7, 2005
  3. Tiza Naziri

    polynomial extended euclidean algorithm

    Tiza Naziri, Mar 15, 2005, in forum: C Programming
    Replies:
    14
    Views:
    2,038
    Randy Howard
    Mar 20, 2005
  4. Replies:
    15
    Views:
    878
    Steven D'Aprano
    Mar 29, 2008
  5. Hendrik van Rooyen

    Re; finding euclidean distance,better code?

    Hendrik van Rooyen, Mar 29, 2008, in forum: Python
    Replies:
    2
    Views:
    339
    Steven D'Aprano
    Mar 29, 2008
Loading...

Share This Page