Impact location, using four sound sensors.

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 :wink: ).

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)
#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();
}

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

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

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.

Marceldv:
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 :wink: ).

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/

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

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.

Would i be able to implement some form of an interrupt on analog sensors ?

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.

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 - Arduino Playground - PinChangeInt

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

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.

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: jayduino - Arduino stuff written by me (in 4 iterations you get a 1E-09 result).

scjurgen:
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

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

Nope

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

scjurgen:

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 (in 4 iterations you get a 1E-09 result).

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 :slight_smile:

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.

Hi Gentleman,

I am looking for some more advice on this project,
i am using this sound sensor..

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

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

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

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

Marceldv:
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 Index of /jayduino/fasterAnalogRead which gets you about 72Khz as sample rate (theoretically 83Khz, but it starts to get crappy) .

#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;
}