Arduino Forum

Using Arduino => Sensors => Topic started by: MarcelDv on Feb 17, 2011, 02:47 pm

Title: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 17, 2011, 02:47 pm
I am not sure where this topic belongs, it is also posted in Science and Measurement...

Hi, i am quite new to the arduino and micro controller world, i have picked myself an project which is driving
me through the roof, and that is the Math around this.

The basics are an impact detection system using three 4 sound sensors and an Arduino Uno.
My problem and honestly i might be over complicating this is as follow.

(http://www.selectsafaris.com/problem.jpg)

while drawing a possible scenario i realized that there is a few things i did not take into consideration while doing my programming..
The problem i see, once i get an input on my first sensor (right Bottom ) Sensor 0,
that sets the base for the rest of the calculations to happen.
but at the moment the sensor is triggered there is already a set distance covered, meaning that the distance i calculate for sensor 1,2,3 will not be from the impact area, but rather from
A-1 B-2 and C-3 which leaves a big hole in my calculations.... smiley-cry

i have been looking at crating triangles from example 3-1-A to determine the XY Coordinate for A, the same for B and C....

Then using Equation of a Circle from 3 Points to determine the center point of the circle..

My problem is angels, i do not have any incoming angels to determine the XY of ABC...

Could anyone offer me a fresh approach to this, either better mathematical approach, or a different way i should be looking at this problem..

Thank you for your time...
Marcel
Title: Re: Impact location, using four sound sensors.
Post by: Grumpy_Mike on Feb 17, 2011, 03:14 pm
Quote
it is also posted in Science and Measurement...

Do not do this, it is called cross posting and makes people here cross. Go and delete one of them.
Title: Re: Impact location, using four sound sensors.
Post by: CrossRoads on Feb 17, 2011, 03:19 pm
You need a minimum of 3 readings to determine the source, 4 increases your confidence.
Typically you have a circle of uncertainty around each point, and where those circles intersect is the origin point.

How are you determining the distance from ABC to an impact point?
With things like earthquakes, they work backwards using time.
An event is known to have occurred.
They know the time that each sensor first felt it.
They know the time of the impact.
They know (more or less) the speed of the wavefront thru water, rock etc.
So (sensor_time - impact_time)/speed of propagation = distance away.  There's your circle of uncertainty.
Then do the math to find the intersection point.
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 17, 2011, 03:21 pm
Apologies, i have removed the post in "Science and Measurement"...

Was not sure where it belonged... but seems sensors is the better place..

Thanks for the warning  :smiley-eek-blue:
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 17, 2011, 03:32 pm
I have a Temp Sensor to calculate the correct speed of sound,
then i calculate the distance by using the time traveled with a formula
to distance..

Does that make sense to you ?



You need a minimum of 3 readings to determine the source, 4 increases your confidence.
Typically you have a circle of uncertainty around each point, and where those circles intersect is the origin point.

How are you determining the distance from ABC to an impact point?
With things like earthquakes, they work backwards using time.
An event is known to have occurred.
They know the time that each sensor first felt it.
They know the time of the impact.
They know (more or less) the speed of the wavefront thru water, rock etc.
So (sensor_time - impact_time)/speed of propagation = distance away.  There's your circle of uncertainty.
Then do the math to find the intersection point.
Title: Re: Impact location, using four sound sensors.
Post by: CrossRoads on Feb 17, 2011, 03:46 pm
So you can determine 3 distances then. All you need is the math to find the intersection point. Should be a google-able topic.
Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Feb 17, 2011, 03:52 pm

I don't think he got an impact time.
The first signal that triggers is then defined as t=0. The others are delta values (so called TDOA) to the first dtn=tn - t etc. So, when you put up your equation of the circles, your radii of 3 circles will have an unknown delta in common for which you have also to resolve (resolve for x,y, and r). BTW, this problem is actually called multilateration http://en.wikipedia.org/wiki/Multilateration (http://en.wikipedia.org/wiki/Multilateration).
Title: Re: Impact location, using four sound sensors.
Post by: johnwasser on Feb 17, 2011, 04:00 pm
Based on timing and the speed of sound you have the length of line segments A1, B2 and C3.  You want to find the point of impact in the center of the circle.   Call the radius of that circle R.  The distance of the impact from the four corners is 0:R, 1:A1+R, 2:B2+R, 3:C3+R.  Write out the four equations and solve for the three unknowns: R, Xi and Yi (the coordinates of impact).

For example:
SQRT((Xi-X0)**2+(Yi-Y0)**2) = SQRT((Xi-X1)**2+(Yi-Y1)**2) - AI = SQRT((Xi-X2)**2+(Yi-Y2)**2) - B2 = SQRT((Xi-X3)**2+(Yi-Y3)**2) - C3 = R

You can probably just drop out the R and solve for (Xi,Yi).
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 17, 2011, 04:02 pm


I don't think he got an impact time.
The first signal that triggers is then defined as t=0. The others are delta values (so called TDOA) to the first dtn=tn - t etc. So, when you put up your equation of the circles, your radii of 3 circles will have an unknown delta in common for which you have also to resolve (resolve for x,y, and r). BTW, this problem is actually called multilateration http://en.wikipedia.org/wiki/Multilateration (http://en.wikipedia.org/wiki/Multilateration).



That is correct, i do not have the impact time, i only have the first trigger on sensor 0, which is already
and x distance from the impact point..

Also as to my initial line of thought, i do not have the incoming signal angle, which would help to solve the problem
with triangle formulas.. so the next option :)

Thank you for the link, i will do some reading and see if i understand the principals of the multilateration
Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Feb 17, 2011, 04:21 pm
Quote
Also as to my initial line of thought, i do not have the incoming signal angle, which would help to solve the problem
with triangle formulas..


Just some food for thought  8), (not a solution for your current problem which has been addressed quite well by the previous post of johnwasser):

There is a technique to get an angle from an impact with 2 sensors using an... tada: artificial head. The mics are mounted in the ears. As the sound arrives at two different times, while one of them impacts directly you will have a slight phase shift from which you can determine a rough determination of angle (as long as you don't have sine sounds, which makes it complicate with high tones. Humans are quite good in this technique. the phase shift determination is done using autocorrelation functions, and this technique works also quite well in a noisy ambient.
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Feb 17, 2011, 04:22 pm
--update --
Sorry, my first reasoning was far too simplified ==> removed; a retry.

You need the distance between the microphones and the two delta T arrival times of the shockwave to do the math.

If you have three points A, B and C.
arrival times of soundwave (in order)
A - T0
B - T1
C - T2

The fact that the soundwave arrived at A first defines an area(1)  of all points P:  d.PA < d.PB and d.PA < d.PC   (d.PA = distance PA)

The delta-time AB = T1 - T0 defines a distance d1 = (T1 - T0) /so  (so = speed Sound)
The delta-time AC = T2 - T0 defines a distance d2 = (T2 - T0) /so

define the curve of all points Q: d.QA - d.QB = d1    (.QA = distance QA)
define the curve of all points R: d.RA - d.RC = d2

These two curves cross each other in area (1) => the point of impact ==>  Q == R.

-- update --
if you knew the time of impact the d.QA, dQB and d.QC would be known, making the math faaaaar simpler as these curves are not trivial - quadratic asymptotic beasts with sqrts in it -   :(

Think it is easier to write an approximating algorithm that searches the point.
The fact that point A heard the soundwave first => d.QA < d.QB

-- update 2 --

from: - http://www.mathwarehouse.com/hyperbola/graph-equation-of-a-hyperbola.php
Quote
A hyperbola is a set of all points P such that the difference between the distances from P to the foci, F1 and F2, are a constant K


so my "quadratic asymptotic beasts with sqrts in it" can be rewritten as hyperbola with A and B  (A & C) as foci.

using the drawing of the webpage above:
Assume A = (0,-c) and B = (0,c)  and the constant K = d1 = (T1 - T0) /so.   The point (0,-a) where the hyperbola crosses the Y-axis is (0, -d1/2)

-->  http://www.mathwarehouse.com/hyperbola/focus-of-hyperbola.php

To determine the foci  one uses a^2 + b^2 = c^2 => b^2 = c^2 - a^2  =  (d.AB/2)^2 - (d1/2)^2

The formula of the hyperbola becomes : y^2 / (-d1/2)^2  - x^2 / (d.AB/2)^2 - (-d1/2)^2 = 1

Same trick for the points A & C  (hint: it is easier to use another reference framework to determine the formula and do a translation afterwards: X -> X-xdelta Y -> Y-ydelta)

TODO: determine intersection points of the two hyperbolas and then your close...

-- update 3 --

intersection points
-- http://www.analyzemath.com/HyperbolaProblems/hyperbola_intersection.html

Difference with the location problem is that the hyperbola defined by points AB and the one defined by points AC are 'orthogonal' - think of it as the red in the drawing rotated 90 degrees (make a drawing!!) There will be two intersection points and because the soundwave arrived first at A it becomes obvious which one to choose.

The code is left as an exercise ....
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 17, 2011, 06:05 pm
Thank you guys for all the information, i have allot of thinking to do now,
i am not the sharpest pencil in the pack when it comes to math..

I will be playing with these options and update you guys on the results.

Thank you all again....

If you have any other suggestion please let me know, i would deeply appreciate it..
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 17, 2011, 06:11 pm
This sounds interesting, i will play with this at some stage, i think i have an application where that would be helpful..

Thanks for the Info..


Quote
Also as to my initial line of thought, i do not have the incoming signal angle, which would help to solve the problem
with triangle formulas..


Just some food for thought  8), (not a solution for your current problem which has been addressed quite well by the previous post of johnwasser):

There is a technique to get an angle from an impact with 2 sensors using an... tada: artificial head. The mics are mounted in the ears. As the sound arrives at two different times, while one of them impacts directly you will have a slight phase shift from which you can determine a rough determination of angle (as long as you don't have sine sounds, which makes it complicate with high tones. Humans are quite good in this technique. the phase shift determination is done using autocorrelation functions, and this technique works also quite well in a noisy ambient.
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 18, 2011, 02:46 pm
I might be missing something in this formula,
the problem i see is that Xi and Yi is unknown to me, thus i cannot manipulate the formula to give me the results Yi or Xi,

or am i just not understanding what you are trying to show me ?


Based on timing and the speed of sound you have the length of line segments A1, B2 and C3.  You want to find the point of impact in the center of the circle.   Call the radius of that circle R.  The distance of the impact from the four corners is 0:R, 1:A1+R, 2:B2+R, 3:C3+R.  Write out the four equations and solve for the three unknowns: R, Xi and Yi (the coordinates of impact).

For example:
SQRT((Xi-X0)**2+(Yi-Y0)**2) = SQRT((Xi-X1)**2+(Yi-Y1)**2) - AI = SQRT((Xi-X2)**2+(Yi-Y2)**2) - B2 = SQRT((Xi-X3)**2+(Yi-Y3)**2) - C3 = R

You can probably just drop out the R and solve for (Xi,Yi).
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 18, 2011, 10:23 pm
Honesty, i have lost you at the first part already........ =(
But i will spend some time on this and see if i can get some
understanding of how this all fits together..

Thank you for the effort you put in it is appreciated..


--update --
Sorry, my first reasoning was far too simplified ==> removed; a retry.

You need the distance between the microphones and the two delta T arrival times of the shockwave to do the math.

If you have three points A, B and C.
arrival times of soundwave (in order)
A - T0
B - T1
C - T2

The fact that the soundwave arrived at A first defines an area(1)  of all points P:  d.PA < d.PB and d.PA < d.PC   (d.PA = distance PA)

The delta-time AB = T1 - T0 defines a distance d1 = (T1 - T0) /so  (so = speed Sound)
The delta-time AC = T2 - T0 defines a distance d2 = (T2 - T0) /so

define the curve of all points Q: d.QA - d.QB = d1    (.QA = distance QA)
define the curve of all points R: d.RA - d.RC = d2

These two curves cross each other in area (1) => the point of impact ==>  Q == R.

-- update --
if you knew the time of impact the d.QA, dQB and d.QC would be known, making the math faaaaar simpler as these curves are not trivial - quadratic asymptotic beasts with sqrts in it -   :(

Think it is easier to write an approximating algorithm that searches the point.
The fact that point A heard the soundwave first => d.QA < d.QB

-- update 2 --

from: - http://www.mathwarehouse.com/hyperbola/graph-equation-of-a-hyperbola.php
Quote
A hyperbola is a set of all points P such that the difference between the distances from P to the foci, F1 and F2, are a constant K


so my "quadratic asymptotic beasts with sqrts in it" can be rewritten as hyperbola with A and B  (A & C) as foci.

using the drawing of the webpage above:
Assume A = (0,-c) and B = (0,c)  and the constant K = d1 = (T1 - T0) /so.   The point (0,-a) where the hyperbola crosses the Y-axis is (0, -d1/2)

-->  http://www.mathwarehouse.com/hyperbola/focus-of-hyperbola.php

To determine the foci  one uses a^2 + b^2 = c^2 => b^2 = c^2 - a^2  =  (d.AB/2)^2 - (d1/2)^2

The formula of the hyperbola becomes : y^2 / (-d1/2)^2  - x^2 / (d.AB/2)^2 - (-d1/2)^2 = 1

Same trick for the points A & C  (hint: it is easier to use another reference framework to determine the formula and do a translation afterwards: X -> X-xdelta Y -> Y-ydelta)

TODO: determine intersection points of the two hyperbolas and then your close...

-- update 3 --

intersection points
-- http://www.analyzemath.com/HyperbolaProblems/hyperbola_intersection.html

Difference with the location problem is that the hyperbola defined by points AB and the one defined by points AC are 'orthogonal' - think of it as the red in the drawing rotated 90 degrees (make a drawing!!) There will be two intersection points and because the soundwave arrived first at A it becomes obvious which one to choose.

The code is left as an exercise ....

Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Feb 19, 2011, 10:43 am
Another line of thought.
When the soundwaves arrive the soundwave has a definite form which will be slightly different at the three points ABC. The essence is that the peakvolume of the soundwave is proportional (linear, quadratic or otherwise) with the distance. The farther away the weaker the sound. As one could calibrate the micro's with a signalstrength/distance table the math would become simpler again.

Don't know if the differences are within the noise-level of the signals/ micro's/arduino ADC but a simple test could reveal this. Furthermore soundwaves can be deformed by obstacles in the open field etc. Still it has some potential worth investigating.

Question: How big is ABCD in square meters? smaller/bigger?

Some additional hyperbola math: - http://www.codecogs.com/reference/maths/geometry/coordinate/hyperbola.php
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 19, 2011, 11:51 pm
Hi Rob,

i have been working on the method you sent me most of the day, but something
just caught my attention..
Using the Hyperbola will give me a XY coordinate on the Hyperbola's Dimensions A-B, not on the the larger
grid..
I still have no Idea mathematically where on the target area A-B is located, so those coordinates
results in another set of unusable data..

Does this make any sense to you ?
Or am i missing something here ?



--update --
Sorry, my first reasoning was far too simplified ==> removed; a retry.

You need the distance between the microphones and the two delta T arrival times of the shockwave to do the math.

If you have three points A, B and C.
arrival times of soundwave (in order)
A - T0
B - T1
C - T2

The fact that the soundwave arrived at A first defines an area(1)  of all points P:  d.PA < d.PB and d.PA < d.PC   (d.PA = distance PA)

The delta-time AB = T1 - T0 defines a distance d1 = (T1 - T0) /so  (so = speed Sound)
The delta-time AC = T2 - T0 defines a distance d2 = (T2 - T0) /so

define the curve of all points Q: d.QA - d.QB = d1    (.QA = distance QA)
define the curve of all points R: d.RA - d.RC = d2

These two curves cross each other in area (1) => the point of impact ==>  Q == R.

-- update --
if you knew the time of impact the d.QA, dQB and d.QC would be known, making the math faaaaar simpler as these curves are not trivial - quadratic asymptotic beasts with sqrts in it -   :(

Think it is easier to write an approximating algorithm that searches the point.
The fact that point A heard the soundwave first => d.QA < d.QB

-- update 2 --

from: - http://www.mathwarehouse.com/hyperbola/graph-equation-of-a-hyperbola.php
Quote
A hyperbola is a set of all points P such that the difference between the distances from P to the foci, F1 and F2, are a constant K


so my "quadratic asymptotic beasts with sqrts in it" can be rewritten as hyperbola with A and B  (A & C) as foci.

using the drawing of the webpage above:
Assume A = (0,-c) and B = (0,c)  and the constant K = d1 = (T1 - T0) /so.   The point (0,-a) where the hyperbola crosses the Y-axis is (0, -d1/2)

-->  http://www.mathwarehouse.com/hyperbola/focus-of-hyperbola.php

To determine the foci  one uses a^2 + b^2 = c^2 => b^2 = c^2 - a^2  =  (d.AB/2)^2 - (d1/2)^2

The formula of the hyperbola becomes : y^2 / (-d1/2)^2  - x^2 / (d.AB/2)^2 - (-d1/2)^2 = 1

Same trick for the points A & C  (hint: it is easier to use another reference framework to determine the formula and do a translation afterwards: X -> X-xdelta Y -> Y-ydelta)

TODO: determine intersection points of the two hyperbolas and then your close...

-- update 3 --

intersection points
-- http://www.analyzemath.com/HyperbolaProblems/hyperbola_intersection.html

Difference with the location problem is that the hyperbola defined by points AB and the one defined by points AC are 'orthogonal' - think of it as the red in the drawing rotated 90 degrees (make a drawing!!) There will be two intersection points and because the soundwave arrived first at A it becomes obvious which one to choose.

The code is left as an exercise ....

Title: Re: Impact location, using four sound sensors.
Post by: andywatson on Feb 20, 2011, 03:39 am
What kind of distance are you expecting between the receivers?  Will they all be connected to the uno via wires? 
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 20, 2011, 09:35 am
Yes they will be connected via wire to the Uno,

My current test is based on 1200mm x 800mm but later on i would like to scale it up
more to about 2.5m x 2m...




What kind of distance are you expecting between the receivers?  Will they all be connected to the uno via wires? 
Title: Re: Impact location, using four sound sensors (sampling considerations).
Post by: scjurgen on Feb 20, 2011, 12:41 pm

Quote
My current test is based on 1200mm x 800mm but later on i would like to scale it up


Did you make considerations about the precision you'll obtain?
Using the standard max sample rate of the Arduino ADC (prescaled with 128) you will get these readings AFAIK:

4 sensors dividing an expected sample rate of 8.9 Khz:
340m/s speed of sound (22oC)= 340000mm/s
340000/(8900/4) ~= 153 mm.

This means a medium sampling distance of sound vs distance of about 15cm for a single sensor and of about 4 cm for the single fronts delta between adjacent sensors (which makes the error considerations tricky).

Title: Re: Impact location, using four sound sensors (sampling considerations).
Post by: MarcelDv on Feb 20, 2011, 02:00 pm
Being new to Arduino, i have not really considered that, but i have read quite a few references
of using external timing methods to improve the accuracy..

Honestly at this moment i am less concerned about the accuracy than figuring out the
mathematics to solve this problem..

The hardware is something i will work on fine tuning later if needed, that is luckily the part where there is
way more information available to improve the solution....
The math seems to be a challenge any way i look at it.

I have read a post on this forum of a Guy using a similar setup who achieved something like
1.4mm accuracy, now if that is true it is more than i need..
unfortunately i need to find the location before i can determine the accuracy of the solution
and start working on that problem...

Is there anyone out there who has done something similar, who can help me PLEASE  =(



Quote
My current test is based on 1200mm x 800mm but later on i would like to scale it up


Did you make considerations about the precision you'll obtain?
Using the standard max sample rate of the Arduino ADC (prescaled with 128) you will get these readings AFAIK:

4 sensors dividing an expected sample rate of 8.9 Khz:
340m/s speed of sound (22oC)= 340000mm/s
340000/(8900/4) ~= 153 mm.

This means a medium sampling distance of sound vs distance of about 15cm for a single sensor and of about 4 cm for the single fronts delta between adjacent sensors (which makes the error considerations tricky).


Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Feb 21, 2011, 09:21 pm
played with the math today and couldn't figure out a nice formula, so I tried another approach, simulation.

When an impact is made one knows three time differences (these are simulated in the code below). In the simulation I try (not) all points of the grid:
- if this point is the point of impact would it (re)create the observation made?

Based upon a grid of 1000x1000 the first approach (brute force) worked well but too slow. The current version starts with the middle of the grid and searches for the points with a lower error around it. This repeats until no better point is found (and the error == 0).

The timing improved dramatically, brute force took several minutes while the current algorithm is in order of 100 msec on my 328 - at least as far as I tested.

Comments and improvements are as allways welcome.

- update -
patched a bug; 
timing now averaging around ~100 msec  (sometimes one pixel off)

Code: [Select]

//
//    FILE: impactSearch.pde
//  AUTHOR: Rob Tillaart
//    DATE: 2011-02-21
//
// PURPOSE: determine impact location based upon arrival time of signal at 4 sensors
//

#define SQR(x) ((x)*(x))

// THE GRID = 1000 x 1000;
// p[] = point A, B, C, D
const long p[8] = { 0,0, 0,1000, 1000,0, 1000,1000 };

int best_x = 0;  // point to be found
int best_y = 0;  // idem
float best_SE = 0;   // Square Error

unsigned long start = 0;  // timer

void setup()
{
 Serial.begin(115200);
 Serial.println("Start...");
}

void loop()
{
 // simulation random impact near point A then B then c then D
 // as the grid is 1000x1000 the max location is 500-500 as otherwise
 // it would be closer to B, C or D
 long px = random(499);
 long py = random(499);

 Serial.print(px);
 Serial.print(",");
 Serial.print(py);
 Serial.print("\t\t");

 // The distances to the 4 mikes are calculated
 // and the value of TA is subtracted as there the sound arrives first.
 // Note distance is time * speed of sound
 // the values here are calculated
 // one could add random noise for the simulation
 float TA = sqrt(SQR(px) + SQR(py));
 float TB = sqrt(SQR(px) + SQR(1000L - py)) - TA;
 float TC = sqrt(SQR(1000L-px) + SQR(py)) - TA;
 float TD = sqrt(SQR(1000L-px) + SQR(1000L - py)) - TA;
 
 start = millis();
 impactSearch(TA, TB, TC, TD);    
 Serial.print(millis() - start);  // how fast
 Serial.print("\t");
 
 // print delta + error
 Serial.print(best_x - px);
 Serial.print(",");
 Serial.print(best_y - py);
 Serial.print("\t");
 Serial.println(best_SE);
}

// impactSearch detemines the point of impact by searching
// the point with a smart trial and error method
// in essence:
// It first takes the middle and tests if that was the point of
// impact what would be the timing and compares that to the factual
// times. Then it does the same for the points around it and
// moves from point to point decreasing the error.
// if there is no better point, the point of impact has been found
//
// This code uses an optimization by doing big steps in the beginning
// and decreasing the stepsize until 0 in the end
//
// Some optimizations are under investigation
// e.g. 3 mikes seems to be enough, but when noise is added
// a fourth mike reduces the overall error I think.
void impactSearch(float t1, float t2, float t3, float t4)
{
 // start in the middle
 // in fact (250,250) is a better point to start as this
 // is the middle of the grid
 best_x = 500;
 best_y = 500;
 best_SE = 100000000L;
 int step = 16;
 
 boolean found = false; // point not found yet
 while (false == found)
 {
   boolean decreaseStep = true;
   
   for (int x = best_x-step; x <= best_x+step; x+=step)
     for (int y = best_y-step; y <= best_y+step; y+=step)
     {
        // optimization, same point is never better
        if (y== best_y && x==best_x) continue;

       // determine what would be the arrival time
       // for point x,y
       // DA = distance to point A - etc
       float DA = sqrt( SQR(p[0]-x) + SQR(p[1]-y) );
       float DB = sqrt( SQR(p[2]-x) + SQR(p[3]-y) );
       float DC = sqrt( SQR(p[4]-x) + SQR(p[5]-y) );
       float DD = sqrt( SQR(p[6]-x) + SQR(p[7]-y) );
       
       // use square error when compared to the real arrival times.
       float se = SQR(DA + t2 - DB);
       se += SQR(DA + t3 - DC);
       se += SQR(DA + t4 - DD);
       
       // remember the one with the smallest error
       if (se < best_SE)
       {
         decreaseStep = false;
         best_SE = se;
         best_x  = x;
         best_y  = y;
       }
     }
   // if no better point found decrease the search area
   // by decreaing the step size
   if (decreaseStep) step--;  // was step = step/2;
   found = (step == 0);
 }
}
Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Feb 22, 2011, 02:45 am
Nice, I like that approach, being a non-linear problem it seems to be a good idea.
Some considerations. The changes between to guessed positions are 'near' linear. So, a kind o 2-D triangled bsearch should be possible (I think a Newton approximation using the f'() is overkill).

Another point is the first guess. There are physical minimum and maximum values, some are trivial. If the 2 deltatimes (dt) are the same (impacts: 0,dt,dt) they must lie on the diagonal between the 2 other sensors. Therefore, the distance should be a trivial 500-dt*sqrt(2)/2 (sound travels linear in time). On the other hand, if one delta is 0 (impacts: 0,0,dt), it is on a line that is orthogonal to the 2 sensors. And the position should be between 500 (dt near 0) and 0 for dt=500*2/(1+sqrt(5)). Interpolating linear between these 2 should be a good first guess (I guess).
Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Feb 23, 2011, 05:37 pm

Ok, here a numerical solution for your problem.  Couldn't find an elegant solution that resolves this complex system (but still, it looks like it is possible). 8)

Some facts: you need 4 sensors, as one does only determine the first time impact, so you actually have only 3 data values, and as someone maybe remembers, with 3 values you can determine a triangle, not with 2. The following algorithm proves that (generating a lot of solutions if you don't consider the 3rd value, and they are all ok  ;) ).

The algorithm is based on this idea.
Not knowing the time to first impact I assume that I know it anyway, I calculate for a guessed value what x y should be, knowing two delta times (easy application of law of cosines).  The third delta time cross checks the initial guess of t. Varying the guess of t you find the minimum error.
This small program has also a routine for testing some points on a grid.

What you need to do:
1) ordering of impacts and mirroring the result values for the 4 different quadrants.
2) feed the sound data to the guessing routine with the sound correction constant (speed of sound + temperature.
3) it is highly optimizable (i think in 20 steps you can obtain an error of 0.01%, not sure, if I have time I will try that, it doesn't look necessary)

Code: [Select]

#include <stdlib.h>
#include <math.h>
/* quick and dirty code, not written on the arduino
*/

double a=1000,b=700; // this is all ugly, better create a class for the whole thingy


/* equations system is:
x=(p^2-t^2-a^2)/(-2*a), // cosine law, p and q the t1+t and p=t2+t
y=(q^2-t^2-b^2)/(-2*b)
*/
#define SQR(x) ((x)*(x))

void getxy(double t, double p, double q, double *x, double *y)
{
*x=(SQR(q)-SQR(t)-SQR(a))/(-2*a);
*y=(SQR(p)-SQR(t)-SQR(b))/(-2*b);
}

void findXY(double t1, double t2, double t3, double eps, double *xres, double *yres)
{
double t,x,y;
double mineps=sqrt(a*a+b*b);

/* this can be highly optimized !!!
  the minimum t depends on the maximum time on the diagonal of the opposite sensor (or something like that)
*/

for (t=0; t < sqrt(a*a+b*b); t+=0.1)
{
getxy(t,t1+t,t2+t,&x,&y);
double t3e=sqrt(SQR(a-x)+SQR(b-y)); // cross check with opposite point (latest arrival)
// printf("t=%f x=%f y=%f t3=%f eps=%f\n ", t,x,y, t3e, fabs(t3+t-t3e));
if (fabs(t3+t-t3e) < mineps)
{
/* you can optimize this too, once we have a local minimum for 3 values (epsilon[0]>epsilon[1] < epsilon[2]), we can refine the search  (t+=0.01 starting with t-0.1 until t+0.1) or exit
*/
mineps=fabs(t3+t-t3e);
*xres=x;
*yres=y;
}
}
}

void test(double x, double y)
{
double t1=sqrt(SQR(x)+SQR(y));
double t2=sqrt(SQR(x)+SQR(b-y));
double t3=sqrt(SQR(a-x)+SQR(y));
double t4=sqrt(SQR(a-x)+SQR(b-y));

printf("%.1f %.1f %.1f %.1f: ", t1,t2,t3,t4);

// printf("%f x ", (SQR(t2)-SQR(t1)-SQR(b))/(-2*b));
// printf("%f\n", (SQR(t3)-SQR(t1)-SQR(a))/(-2*a));

t2-=t1;
t3-=t1;
t4-=t1;
t1=0;
printf("t1=%.1f t2=%.1f t3=%.1f ", t2,t3,t4);
findXY(t2,t3,t4,0.01,&x,&y);
printf("~ {%.2f;%.2f}\n",x,y);
}


void testgrid()
{
for (double y=0; y <= b/2; y+=50.0)
{
for (double x=0; x <= a/2; x+=50.0)
{
test(x,y);
}
}
}

int main(int argc, char *argv[])
{
testgrid();
}

Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 23, 2011, 09:53 pm
Thanks Juergen,

I will start playing with this one aswell,
Thank all you guys again, i appreciate all the effort you put in to try and help resolve this
problem..

Hopefully one day i can also contribute as mush to your or someone else s project..
Might take time but hope to get there...

Thanks Rob and Jeurgen.. i will test and post my results..

Regards
Marcel
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Feb 27, 2011, 11:46 pm
Hi Gentlemen,

I have a new question... relating to the same topic...
I have been doing some reading on the various ways to get the audio data
into the Arduino.

Well i am at the point where i am not sure what is the correct direction to take..

Option one:
Using the pre-ams on the analog ports as i am doing now.

Option two:
Using a OpAmp as a comparator and putting the data into the Digital ports,
and using one of the Hardware timers to create an interrupt to signal the arrival
of a new input..

Would Digital be faster than Analog, or the other way around ?

Does anyone have any advice regarding these options, it seems the prediction that
i will loose accuracy due to the speed of the processor.
so any improvements i can make will help me get more reliable data.

currently i get very random data, still trying to figure it out why, that is why i am looking at way to improve that
data input...

here is what i currently get, five impacts at roughly a similar location on a surface 940mm x 640mm
the times are in millisecond....

------1---------   
Time1 = 0.00
Time2 = 0.94
Time3 = 2.84
Time4 = 5.69

------2---------   
Time1 = 0.00
Time2 = 2.34
Time3 = 4.69
Time4 = 13.19

------3---------
Time1 = 0.00
Time2 = 3.75
Time3 = 4.70
Time4 = 5.65

------4---------
Time1 = 0.00
Time2 = 0.47
Time3 = 1.88
Time4 = 3.78

------5---------
Time1 = 0.00
Time2 = 3.76
Time3 = 4.70
Time4 = 8.03
---------------

Any Ideas????

Thank you
Marcel

Title: Re: Impact location, using four sound sensors.
Post by: rocketgeek on Feb 28, 2011, 03:40 pm
Hyperbolas are the way to go for this, because what you have is differences in arrival times, not absolute times. You know the arrival times at all four locations, t0, t1, t2, t3. That gives you six differences: (t3 - t2), (t3 - t1), (t3 - t0), (t2 - t1), (t2 - t0), (t1 - t0); each of these generates a hyperbola. The intersection of six hyperbolas gives you one and only one point.

Four is the minimum number of sensors this will work with, absent other constraints. You need a minimum of six hyperbolas to get a unique intersection point. If you have three sensors, you get three hyperbolas, which gives you two intersections points. If you can rule one out (i.e. you know the impact is in a given area), you're good, but four sensors gives you a unique solution as long as the placement of the sensors does not give degenerate geometry.
Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Feb 28, 2011, 06:39 pm

I have been doing some reading on the various ways to get the audio data into the Arduino.
Well i am at the point where i am not sure what is the correct direction to take..

Option one:
Using the pre-ams on the analog ports as i am doing now.

Option two:
Using a OpAmp as a comparator and putting the data into the Digital ports,
and using one of the Hardware timers to create an interrupt to signal the arrival
of a new input..

Would Digital be faster than Analog, or the other way around ?


Digital is way faster, and the routines of the standard digital acquisition can be optimized.
I did an analysis (Arduino 2009) some time ago using different techniques (and then I switched the micro ;) ).

digitalRead non optimized: 165672 samples/second
digitalRead optimized: 265111 samples/second

analogRead not optimized: 8927 samples/second
analogRead prescale=64: 16603 samples/second
analogRead prescale=32: 31250 samples/second
analogRead prescale=16: 52521 samples/second
analogRead prescale8: 82987 samples/second

These are crude times in a simple loop, meaning, not considering eventual processing. Analogread can be very much enhanced if you split the request for a value and the reading (request value, do other stuff, read value)
the routines for changing analog reads you find here (you will need to change the code I guess, it was for reading 8 channels circulary)
http://www.schwietering.com/jayduino/fasterAnalogRead/ (http://www.schwietering.com/jayduino/fasterAnalogRead/)

Also consider in your code that the sampling of the data channels is not at the same moment and introduces a fixed delay between 2 channels (t=1/samplerate) that you need to compensate for on each channel when you detect a signal.

You also need to consider doing these actions in a timer interrupt, your timing must be impeccable and not disturbed by processing. So, in the interrupt you get the value, save it to a ring buffer and get quickly out of there. The processing you do in the main loop by reading the data in the ring buffers and doing what you need to do.

HTH
Title: Re: Impact location, using four sound sensors.
Post by: rocketgeek on Feb 28, 2011, 06:56 pm
Digital is way faster, but it requires you to put all of the things you need to discriminate between an impact and other ambient sounds. There is a guy here in Seattle by the name of Tangent makes a nifty little OSHW pendant that flashes some LEDs in response to the beat of ambient music and he appears to have tackled most of the relevant issues. There are some kits in the vending machine at Metrix, but I can't seem to find a link to his website.
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Mar 01, 2011, 09:30 am
Would i be able to implement some form of an interrupt on analog sensors ?
Title: Re: Impact location, using four sound sensors.
Post by: rocketgeek on Mar 01, 2011, 09:32 am
You can set an interrupt on the acquisition of a sample. Then you can decide whether to fall through to whatever else you want to do.
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Mar 01, 2011, 10:01 am
As far as I know only digital signal can trigger IRQs so you need to make electronics that makes a square wave of the analog signal when a threshold (soundlevel) is reached.

The Arduino 328/UNO has only two direct IRQ lines but also has a collective IRQ on the other pins. So you need to determinew which pin was triggered. See - http://www.arduino.cc/playground/Main/PinChangeInt
Title: Re: Impact location, using four sound sensors.
Post by: Yot on Mar 01, 2011, 10:10 am
Another option could be using the a/d converter in free running mode. Than at least the samples are taken with a known interval.

Following this thread with interest,

Jeroen
Title: Re: Impact location, using four sound sensors.
Post by: Artem_F on Mar 02, 2011, 12:30 am
if you have 4 known locations (x1,y1, x2,y2, x3,y3, and x4,y4),
3 times after the trigger event, and you want to determine x0,y0 that is the location
of the sound source then you have 7 equations and 6 variables that means that the task is
solvable.
the equations are:
(x_i-x0)^2 + (y_i-y0)^2 = R_i^2    for i=1..4
+ 3 equations of type:
R_i-R_earliest = v_sound*(t_i-t_earliest)=v_sound*t_i    since t_earliest=0 as it syncs everything.
R_earliest is one of R_i, each time it's a different one but it doesn't change anything

rewrite this system to express x0 and y0 and you're done.


Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Mar 02, 2011, 12:49 am
Quote
rewrite this system to express x0 and y0 and you're done.


funny that many come out on how to solve this (oh yeah, it's trivial, search wiki) problem, without actually presenting a working solution! In the end I got really annoyed, and here is a a solution to calculate the positions (mathemetica, matlab did not help much so I did it by hand) and you can find here the algo for this particular problem: http://www.schwietering.com/jayduino/#newtonmethod (http://www.schwietering.com/jayduino/#newtonmethod) (in 4 iterations you get a 1E-09 result).
Title: Re: Impact location, using four sound sensors.
Post by: Artem_F on Mar 02, 2011, 01:10 am

In the end I got really annoyed

so next time you'd suggest people to forget about everything and start coding
and testing anything they suggest? Really? lol
Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Mar 02, 2011, 01:22 am

so next time you'd suggest people to forget about everything and start coding
and testing anything they suggest? Really? lol

Nope
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Mar 03, 2011, 10:24 am
Thank you..

Will start working on this approach,

Honestly, i understand you frustration, i have been trying to solve this for a long time now, and
every single person i present with the challenge says it is easy, until they need to prove it..

I have rewritten this application about 20 times now...

Hope this is the last one...

Thank again for all your inputs gents..


Quote
rewrite this system to express x0 and y0 and you're done.


funny that many come out on how to solve this (oh yeah, it's trivial, search wiki) problem, without actually presenting a working solution! In the end I got really annoyed, and here is a a solution to calculate the positions (mathemetica, matlab did not help much so I did it by hand) and you can find here the algo for this particular problem: http://www.schwietering.com/jayduino/#newtonmethod (http://www.schwietering.com/jayduino/#newtonmethod) (in 4 iterations you get a 1E-09 result).

Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Mar 05, 2011, 01:53 pm

Just found this contest - https://gw.innocentive.com/ar/challenge/overview/9932699 - related to this subject. The difficulty is that there are (at least) 3 dimensions iso 2 changing the number of micros to 8? -think cubistic - and the math will be squared too :)

Think the solution is a mesh-networked-zigbee-arduino-with-rtc-combination at every corner of the cube or so.

Real problem is how to detect the shot/impact in the first place, distinguish it from other noise and as it is a soundWAVE which point to take.



Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Mar 08, 2011, 03:06 pm
Hi Gentleman,

I am looking for some more advice on this project,
i am using this sound sensor..
http://tinkerlog.com/2007/05/20/cheap-sound-sensor-for-avr/

(http://farm1.static.flickr.com/209/505756876_a77b9ac912_m.jpg)

I would like to add a comparator to the circuit so i can send the data to
the Digital inputs..
or do the ADC Conversion externally...

I have read quite a bit and most people advise OPAMP's but i have no idea
about the electronics, so some guidance or direction would be helpfull.

Thank you
Marcel
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Mar 09, 2011, 11:42 am
Have you considered - http://www.arduino.cc/en/Tutorial/KnockSensor ?

Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Mar 09, 2011, 07:37 pm
Hi Rob,

yes, i did try that, i seem to be getting better data from the preamp and mics...

The digital input i need to improve the acquisition speed..

Regards
Marcel


Have you considered - http://www.arduino.cc/en/Tutorial/KnockSensor ?


Title: Re: Impact location, using four sound sensors.
Post by: scjurgen on Mar 11, 2011, 04:03 pm

The digital input i need to improve the acquisition speed..


I wrote some code to get faster digital reads.
You will initialize the drbit and drport arrays using initDigitalRead() in setup. Then, when calling digitalRead2() you can get 265Khz max sample rate (instead of 166Khz).

for faster analogread refer to http://www.schwietering.com/jayduino/fasterAnalogRead/ (http://www.schwietering.com/jayduino/fasterAnalogRead/) which gets you about 72Khz as sample rate (theoretically 83Khz, but it starts to get crappy) .

Code: [Select]



#ifndef cbi
#define cbi(sfr, bit) (_SFR_BYTE(sfr) &= ~_BV(bit))
#endif
#ifndef sbi
#define sbi(sfr, bit) (_SFR_BYTE(sfr) |= _BV(bit))
#endif

static inline void turnOffPWM(uint8_t timer) __attribute__ ((always_inline));
static inline void turnOffPWM(uint8_t timer)
{
if (timer == TIMER1A) cbi(TCCR1A, COM1A1);
if (timer == TIMER1B) cbi(TCCR1A, COM1B1);

#if defined(__AVR_ATmega8__)
if (timer == TIMER2) cbi(TCCR2, COM21);
#else
if (timer == TIMER0A) cbi(TCCR0A, COM0A1);
if (timer == TIMER0B) cbi(TCCR0A, COM0B1);
if (timer == TIMER2A) cbi(TCCR2A, COM2A1);
if (timer == TIMER2B) cbi(TCCR2A, COM2B1);
#endif

#if defined(__AVR_ATmega1280__)
if (timer == TIMER3A) cbi(TCCR3A, COM3A1);
if (timer == TIMER3B) cbi(TCCR3A, COM3B1);
if (timer == TIMER3C) cbi(TCCR3A, COM3C1);
if (timer == TIMER4A) cbi(TCCR4A, COM4A1);
if (timer == TIMER4B) cbi(TCCR4A, COM4B1);
if (timer == TIMER4C) cbi(TCCR4A, COM4C1);
if (timer == TIMER5A) cbi(TCCR5A, COM5A1);
if (timer == TIMER5B) cbi(TCCR5A, COM5B1);
if (timer == TIMER5C) cbi(TCCR5A, COM5C1);
#endif
}


uint8_t drbit[50];
uint8_t drport[50];

int initDigitalRead(uint8_t pin)
{
   uint8_t timer = digitalPinToTimer(pin);
   drbit[pin] = digitalPinToBitMask(pin);
   drport[pin] = digitalPinToPort(pin);
   if (timer != NOT_ON_TIMER) turnOffPWM(timer);
}


int digitalRead2(uint8_t pin)
{
   if (*portInputRegister(drport[pin]) & drbit[pin]) return HIGH;
   return LOW;
}

Title: Re: Impact location, using four sound sensors.
Post by: fileark on May 13, 2011, 07:17 pm
Marcel, I had some questions that I asked a while back trying to make a sound localization sensor. I am delighted to find this thread as it is good reading for me. I will be paying close attention to your progress as I am still thinking about my next step in making a better sensor.
http://arduino.cc/forum/index.php/topic,55578.0.html

I made a prototype sensor that did sound localization using some LM324N op amps first as amplifiers then as comparitors. I have a video and also schematic diagram that may help you build your own circuits.
http://filear.com/index.php/arduino/90-diy-sound-localization-sensor

Title: Re: Impact location, using four sound sensors.
Post by: necromancer on May 15, 2011, 04:25 pm
Hey there.. got to this topic from electronics-lab.com, via Fileark sound localization sensor.

I am doing very similar product like you - sound localization based on impact of metal BB pellet on metal target (square).

Long story short, so I am not boring - most probably, math won't be your biggest problem, in fact, it is/was the simplest problem of my setup.

So you have four sensors like in your image
(http://www.selectsafaris.com/problem.jpg)

From your input, you get 4 values. In example on picture, let's say that they were:

0: 0000
1: 1200 (A..1)
2: 2000 (B..2)
3: 2500 (C..3)
(the unit is not important for now.. in this case, it could be CPU cycles or whatever)

my default, most simple algorithm did this:

Imagine four circles, with their center in microphones. Lets call those circles M0, M1, M2, M3.

You know delta times.. so let's do this:

M0 radius = 0000
M1 radius = 1200
M2 radius = 2000
M3 radius = 2500

Now you have four imaginary circles (one is in fact point - zero radius) and they are touching big circle on your picture.

What you have to do is start adding number one to each of those circle radii.

M0 = 1, M1 = 1201, M2 = 2001, M3 = 2501..

Four imaginary circles are now a bit bigger and closer to impact zone.

After each addition, you have to calculate intersections of neighbour circles. In ideal case, they will all end up in the same point - point of impact. In real world, there will be some error.. then you have to calculate when where all intersection closest and pick a point between them.

*EDIT*: i forgot that you need to know distance between neighbour microphones in our imaginary unit (miliseconds, CPU cycles, whatever) to calculate the intersection - simple triangle.

Also - this is a solution for 2D, not for 3D. If you want to minimize error, mic's should be as close to edges of measured plane as possible. If they are not, then you have to use 3D coordinates for microphones, edges of target and do lots of triangle math in 3D.

I hope it was understandable - English is not my native language :)

And in real world, there will be many problems, as I have said, math is nothing. Problem is with intensity of signals at microphones - it goes down with distance squared, also with precise measuring the difference between signal arrival at microphones. Don't even think about using piezoelectric disks clamped onto surface of the target. Speed of sound in steel is nearly 6000 m/s, there will be various reflections and therefore it is virtually impossible to calculate with cross-corelation, because the signal from each sensor is different. A lot! It is possible to try triggering with first sine wave coming from sensor, but it is about milivolt levels, very picky on environment and if you are shooting, it will register shooting sound before impact sound - not good.

Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Jun 11, 2011, 03:28 pm
Thanks you guys for all the input, i have been busy with another project the past few months and did not get allot of time to work on this, but yes, it is not an easy solution but i am will find a way to make it work...

Thank you for all the new ideas, i must say the approach from necromancer sounds like it would be the simplest way..

I will keep you up to date as i make progress, still struggling to get the Comparator part sorted out, i am stupid with the electronics, so i need to go by trial and error..

Marcel
Title: Re: Impact location, using four sound sensors.
Post by: hotchk155 on Nov 01, 2011, 10:51 pm
This is an interesting thread as I've been trying something similar. I think I will give Necromancers approach a try as it sounds pretty simple and sensible at first glance.
On the sensor side I might have something to contribute. I need to detect a "knock" on a 2d surface so I am using piezo contact mikes. I posted my schematic here
http://hotchk155.blogspot.com/2011/10/musical-ping-pong-tables-and.html
Title: Re: Impact location, using four sound sensors.
Post by: Aplonis on Nov 02, 2011, 12:30 pm
I'm just now having to leave for work. I'll try and get back later in detail. Know, however, that this equation can be solved WITHOUT angles using Law of Cosines, which is straightforward algebra without recourse to esoteric functions.

I did it once using string pots, where I had only three string potentiometers giving distance only from three corners of a right angle to the point of intersection. This was done to record the 3D displacement of a car axle being exercised on a tramp test machine for the automotive industry so as to calculate the angle of oversteer.

I saved that info someplace. I'll try to find it for you, if you care to go that route.
Title: Re: Impact location, using four sound sensors.
Post by: hotchk155 on Nov 05, 2011, 03:17 pm
I've been looking at this some more, based on Necromancers iterative method (which I think might be quite slow in practice). I think I'm getting somewhere with a fast and dirty calculation to get the start point for the iteration, but it seems to show potential as a method by itself. I wanted to share the idea (and also see if anyone can suggest where to go with it  :)) here http://hotchk155.blogspot.com/2011/11/lost-in-maths.html
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Nov 05, 2011, 03:51 pm
Quote
which I think might be quite slow in practice

Can you share the arguments for that thought? in short why?

What is the speed you want?

In my simulation to solve this problem I came to ~100 msec  (code see - http://arduino.cc/forum/index.php/topic,52583.msg379029.html#msg379029 - )
Title: Re: Impact location, using four sound sensors.
Post by: raalst on Nov 05, 2011, 04:34 pm
@Rob,

You can speed up your simulator/trial/error approach by a factor of about 4.

say the  sound arrives in sequence abcd on mic's a,b,c and d.
then you know the point of origin is closer to a than to b, closer to b as to c, etc.
draw the line between a & b; find the point in the middle on the line and draw line 90deg perpendicular
to first line. you only need to search the points on a's side of that line.
same  for b-c and c-d (and a-d as well and maybe even for the diagonals a-c and d-b).
so it is quick to create a sector where to look. then in the sector use the simulation.

strangely, the more regular you position the mic's, the bigger the sector seems to get.
for a square arrangement, a-b and c-d are parallel and their perpendiculars are the same so you loose information.
therefore for a square of mic's you only have two perpendicular lines and 4 sectors (if you do not use the diagonals). 
It somehow seems to pay off to place the mic's in an irregular pattern
Title: Re: Impact location, using four sound sensors.
Post by: hotchk155 on Nov 05, 2011, 10:16 pm
@robtillaart - the reason for thinking the iterative method would be slow is that it would need a lot of calls to sqrt() as the intersection points of the circles are repeatedly recalculated...  Perhaps I'm worrying too much, but I can happily trade off some accuracy for speed in my application. Basically I want to react to an impact to produce a sound (via a MIDI synthesiser) without any perceivable delay, and I'd want to be ready to detect the next impact very soon after. The surface would be divided into a number of areas triggering different sounds (e.g. imagine someone playing drums by tapping fingers on a tabletop)
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Nov 06, 2011, 09:13 am
@raalst
Quote
You can speed up your simulator/trial/error approach by a factor of about 4.

I know, you are right - in fact one can speed up even more

- assume a square with mic on the corners and M in the middle
   A  B
    M
   C  D


- the first mic (A) divides the area in two. All the points that are closer to A than to the others.
 That is the quadrant around A  == your optimization

The next mic to trigger is either B or C as these are closest to A. (only for the exact middle M this is not true)
The cases B and C are symmetrical / identical so I refer to B as the second one

- the second mic (B) divides the initial quadrant in the triangle  A-M- (mid-AB)

- the third mic will allways be C but that will not decrease the area as all points in the triangle are closer to C than to B
 except for the line M - (mid-AB) in which case C and D will trigger simultaneously.

- D will allways be last ...

So only after the first two signals coming in you can choose the right enclosing triangle meaning a factor 8 smaller area. However the algorithm would become more complex as iterating through a triangle is not as straightforward as a square. Furthermore as the simulation does a first iteration with big steps the gain will not be an extra factor 2. OK one can optimize the code so there will be a gain, but mostly at costs of complexity and I've learned throught the years that you don't need to optimize an algorithm for speed if it is fast enough.

Note that the simulation approach is in fact independant of the position of the microphones, only the distance function changes of course.

Quote
It somehow seems to pay off to place the mic's in an irregular pattern

This might be true and needs some thinking....

Thinking which positions would be hit most we will see a concentration of points in the middle (M) and points becoming less near the sides. points near the middle also mean that the arrival times or better said the difference in arrival times of the sound will be smaller (assuming corner mic's). And this leads to less precision in the math given the inaccuracy of the mic readings themselves. This leads me to the statement (not proofed) that the microphones should have different distances to the center of concentration of points to increase the precision. In theory you want a mic near the center but in practice it will not survive ....

I propose 3 micros on one side and one in the corner. Then there is no point causing the sound to arrive simultaneously.
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Nov 06, 2011, 09:49 am
@hotchk155
Quote
the reason for thinking the iterative method would be slow is that it would need a lot of calls to sqrt() as the intersection points of the circles are repeatedly recalculated.


All the floating point math can slow down an algorithm, but there are several optimizations that could speed it up process. Not looked at that algorithm in detail
1) use an integer sqrt function, ==> less precise but might be precise enough until a certain level, 
    see picture - http://ww1.microchip.com/downloads/en/AppNotes/91040a.pdf  -
1) use an approx sqrt function, a lookup table with interpolation. see -http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

2) if you need to compare a distance A-B  with another distance  C-D you don't need the sqrt as one can compare the "squared" values

d1 = (Ax - Bx)^2 + (Ay - By)^2;
d2 = (Cx - Dx)^2 + (Cy - Dy)^2;

just test d1 > d2  iso sqrt(d1) > sqrt(d2) => same result, less math => faster,

just a few thought...



Title: Re: Impact location, using four sound sensors.
Post by: Peter_I on Jan 11, 2013, 11:35 pm
I know this is a necro-post, but here I go anyway:

Basically this is the same problem as in sound ranging an artillery piece.

Sir William Lawrence Bragg, one of the grand men of crystallography, did his share of the math (ensuring that it is not a trivial problem!) during WW I.

http://en.wikipedia.org/wiki/Sound_ranging is absolutely worth reading.

And http://www.waterloolabs.com/#!episode-02/cgue is worth seeing.
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Jan 11, 2013, 11:45 pm
INteresting (and fun) material,

Thanks for posting!
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Dec 01, 2013, 06:15 pm
Hi guys, i ma finally back to this project, or have been for a while but have been trying to sort out the hardware first..

I have now built a new sensor circuit, using 2xlm324n quad op-amps the first one amplifies the mic inputs, the second one is a comparator on which i have a pot to adjust the comparators voltage it compares with..

Hopefully this will help me improve my accuracy on the  inputs..

I have also played with different hardware, the Uno and a raspberry pi and python..

I am leaning on going back to the Uno, as i does not get constancy on the sensor values on the Pi.

Has anyone made any progress on this subject, i know there where a few geniuses here and they where interested
In this project...

Thanks again for everyone who have shared their inputs, and i hope this time round i can get this one figured out..


Regards
Marcel
Title: Re: Impact location, using four sound sensors.
Post by: robtillaart on Dec 01, 2013, 06:31 pm
Hi Marcel,
long time no see :)

Still interested in this project as it is a nice showcase what an Arduino can do.

The PI is not "as realtime as " an Arduino in its IO, heart that more often. That means that it adds "noise/inaccuracy" in the timing.
proposal: Do the IO with the Arduino and send it to the PI for processing,

Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Dec 01, 2013, 07:32 pm
Hi Rob, thanks for all the messages you sent, for some reason i never saw them,
What you are proposing is my plan, to try and do just the data acquisition on the uno
And the analyze and process the data on the pi..

I think the largest part of my failure the first time round was my sensor circuit..

Hope the improved circuit will increase the accuracy plus the fact that i will be reading
Digital instal of analog.. Hope that improves speeds as well.

Thanks for all your inputs thus far.. Hope we figure this out :-)

Marcel
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Dec 02, 2013, 02:43 pm
Just did some interesting Math... Do you guys agree with the results..

In my mind the most practical method of getting accurate data is using Digital Interrupts to listen
to the sensors, to get the best accuracy..

Assuming the target size is 2.2M high by 3.2M Wide.. with the speed of sound at 340m/s
it should take sound 6.47 Mili Seconds to travel the 2.2Meters and 9.42 to travel the 3.2Meters.

According to this document http://www.gammon.com.au/forum/?id=11488
"I count 82 cycles there (5.125 µS in total at 16 MHz) as overhead plus whatever is actually done in the supplied interrupt routine. That is, 2.9375 µS before entering your interrupt handler, and another 2.1875 µS after it returns."

Based on the figures i tried to determine the expected accuracy of the Uno at this target size.
so i worked with 1cm to get an idea..

it works down to 0.029 Milliseconds to travel a CM...
if the process time is 0.005125 Milliseconds as per the reference information,

i should be able to get a expected resolutions of about 2 mm...

does this make sense.. or have i smoked something not good for me :-)

Marcel
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Dec 02, 2013, 02:48 pm
Another Question,

How large do you guys think the effect of surface tension would be..
at this moment the target is made of a canvas material loosely fitted..

Would a hard surface improve the accuracy, and then if i use something rubber,
as the impact surface, would that have a huge impact on accuracy..

Conveyer belt works great as a target back stop as it heals (does not leave holes)
but i am concerned with the effect rubber would have..

I am rebuilding the target area, so i am considering all aspects that could affect accuracy..

Marcel
Title: Re: Impact location, using four sound sensors.
Post by: Peter_I on Dec 02, 2013, 02:56 pm

Just did some interesting Math... Do you guys agree with the results..

... with the speed of sound at 340m/s
........
does this make sense.. or have i smoked something not good for me :-)



Unless your target is made of air or smoke, you have smoked something.

340 m/s is the speed of sound in air at normal pressure and temperature.
In other materials it is significantly different.
Title: Re: Impact location, using four sound sensors.
Post by: MarcelDv on Dec 02, 2013, 03:04 pm
The frame is constructed that the Mics listen in the thin air/smoke  :)..
so the sound of impact will travel trough the air, it is not measuring the surface
vibration..

Depending on the target material the sound should be a hard thumb,
this i say based on me being on a military spec shooting range where you
sit bellow the targets in a bunker, and there i could hear a very distinctive thumb
sound on impact.. :smiley-roll-sweat:

But yes, i did not smoke anything on the speed of sound :-)
the calculations maybe.. :-)
Title: Re: Impact location, using four sound sensors.
Post by: SinatraV on May 04, 2018, 05:44 am
Dragging up an old thread, I know. I have found a few similar threads. Just wondering if this idea was ever actually worked out? Looks like it died in 2010 and then resurfaced in 2013. I am soon to start a project using the same idea, just hate to find out it's not possible. Seems like some great minds have been hard at work already.