Impact location, using four sound sensors.

[MarcelDv]

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

[hotchk155]

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

[Aplonis]

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.

[hotchk155]

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

[robtillaart]

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 - )

[raalst]

@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

[hotchk155]

@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)

[robtillaart]

@raalst

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.

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.

[robtillaart]

@hotchk155

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...

[Peter_I]

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.

[robtillaart]

INteresting (and fun) material,

Thanks for posting!

[MarcelDv]

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

[robtillaart]

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,

[MarcelDv]

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

[MarcelDv]

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