TDOA, multilateration etc. on small uC

Scenario: a small solid plate of a material yet to decide
with equally spaced vibration sensors along its outer sides.
An user knocks (or throws a small object) on a random point
on the surface and the logic finds the point by only reading
the sensors, ie time and intensity of the events.

The plate is small, 1 meter or less, and can be made of
wood, acrylic etc. The number of sensors is not strictly
defined as well, although I believe 6 to 8 would be ideal.
If it helps, all sensors can be arranged in a circle or 
a square pattern.
No need for precision, a 5% position error would be perfectly
acceptable. OTOH speed is important: it should be able to 
sustain at least 50 reads per second.

(Nope, I'm not designing a machine gun target. No weapons
involved, although in a broad sense we're somewhat close:*)

It doesnt' seem that hard (I thought), just read all sensors
in a tight loop, find the first pulse for each sensor to
discriminate against reflections and calculate the distance
based on delay/intensity differences from other sensors
taking into account the different speed of sound in the 
given material, then repeat.
That would be trivial if only I wasn't a total math illiterate.
After some searches the magic words I stumbled upon were
"multilateration" and "TDOA", so I looked for examples,
source code or anything that could be made into a small
microcontroller but no cigar. One matlab example aside, I
couldn't find anything practical, except for some long math
papers not even my cat (way better at math than I) could
understand:)

So the question is: could such a beast be implemented using
low cost microcontrollers? Any pointers on similar projects
with portable source code (hopefully C) to be studied? 
Thanks!

asdf wrote:

> Scenario: a small solid plate of a material yet to decide
> with equally spaced vibration sensors along its outer sides.
> An user knocks (or throws a small object) on a random point
> on the surface and the logic finds the point by only reading
> the sensors, ie time and intensity of the events.
>
> The plate is small, 1 meter or less, and can be made of
> wood, acrylic etc. The number of sensors is not strictly
> defined as well, although I believe 6 to 8 would be ideal.
> If it helps, all sensors can be arranged in a circle or 
> a square pattern.
> No need for precision, a 5% position error would be perfectly
> acceptable. OTOH speed is important: it should be able to 
> sustain at least 50 reads per second.
>
> (Nope, I'm not designing a machine gun target. No weapons
> involved, although in a broad sense we're somewhat close:*)
>
> It doesnt' seem that hard (I thought), just read all sensors
> in a tight loop, find the first pulse for each sensor to
> discriminate against reflections and calculate the distance
> based on delay/intensity differences from other sensors
> taking into account the different speed of sound in the 
> given material, then repeat.
> That would be trivial if only I wasn't a total math illiterate.
> After some searches the magic words I stumbled upon were
> "multilateration" and "TDOA", so I looked for examples,
> source code or anything that could be made into a small
> microcontroller but no cigar. One matlab example aside, I
> couldn't find anything practical, except for some long math
> papers not even my cat (way better at math than I) could
> understand:)
>
> So the question is: could such a beast be implemented using
> low cost microcontrollers? Any pointers on similar projects
> with portable source code (hopefully C) to be studied? 
> Thanks!

http://www.classltd.com/sound_velocity_table.html gives the propagation
of sound in plexi at 1.7 mm/us.  So if you wanted 50mm resolution, you'd
need to resolve the time difference between the sensors to about 30 us. 
(Want to use steel instead, you've need 10 us).

6 sensors / 30 us = 200 ksps, so figure you probably need an aggregate 1
Msps to actually get enough data.  Probably challenging to pull off on
some toy micro, though not clearly impossible.


-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com

Email address domain is currently out of order.  See above to fix.

On Fri, 06 May 2016 22:57:18 +0000, asdf wrote:

> Scenario: a small solid plate of a material yet to decide with equally
> spaced vibration sensors along its outer sides. An user knocks (or
> throws a small object) on a random point on the surface and the logic
> finds the point by only reading the sensors, ie time and intensity of
> the events.
> 
> The plate is small, 1 meter or less, and can be made of wood, acrylic
> etc. The number of sensors is not strictly defined as well, although I
> believe 6 to 8 would be ideal.
> If it helps, all sensors can be arranged in a circle or a square
> pattern.
> No need for precision, a 5% position error would be perfectly
> acceptable. OTOH speed is important: it should be able to sustain at
> least 50 reads per second.
> 
> (Nope, I'm not designing a machine gun target. No weapons involved,
> although in a broad sense we're somewhat close:*)
> 
> It doesnt' seem that hard (I thought), just read all sensors in a tight
> loop, find the first pulse for each sensor to discriminate against
> reflections and calculate the distance based on delay/intensity
> differences from other sensors taking into account the different speed
> of sound in the given material, then repeat.
> That would be trivial if only I wasn't a total math illiterate.
> After some searches the magic words I stumbled upon were
> "multilateration" and "TDOA", so I looked for examples,
> source code or anything that could be made into a small microcontroller
> but no cigar. One matlab example aside, I couldn't find anything
> practical, except for some long math papers not even my cat (way better
> at math than I) could understand:)
> 
> So the question is: could such a beast be implemented using low cost
> microcontrollers? Any pointers on similar projects with portable source
> code (hopefully C) to be studied?
> Thanks!

Hire me to do the math!  I'm available.

As far as "can it be done with low cost microcontrollers", you need to 
specify what you mean by "low cost".  ST and TI both make some pretty 
nifty parts that are under $5 in quantity, and have ARM cores and fast 
ADCs.  They should be more than fast enough.  I suspect that there's 
something out there that has a fast-enough ADC and costs less, if $5 
isn't "low cost" to you.

If you don't mind some delay while the thing crunches numbers the actual 
microprocessor core can be darned near anything -- how long can it stop 
to think after you whack it with a stick?

Three sensors ought to be enough, but more is probably better.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On 5/6/2016 7:24 PM, Tim Wescott wrote:
> On Fri, 06 May 2016 22:57:18 +0000, asdf wrote:
>
>> Scenario: a small solid plate of a material yet to decide with equally
>> spaced vibration sensors along its outer sides. An user knocks (or
>> throws a small object) on a random point on the surface and the logic
>> finds the point by only reading the sensors, ie time and intensity of
>> the events.
>>
>> The plate is small, 1 meter or less, and can be made of wood, acrylic
>> etc. The number of sensors is not strictly defined as well, although I
>> believe 6 to 8 would be ideal.
>> If it helps, all sensors can be arranged in a circle or a square
>> pattern.
>> No need for precision, a 5% position error would be perfectly
>> acceptable. OTOH speed is important: it should be able to sustain at
>> least 50 reads per second.
>>
>> (Nope, I'm not designing a machine gun target. No weapons involved,
>> although in a broad sense we're somewhat close:*)
>>
>> It doesnt' seem that hard (I thought), just read all sensors in a tight
>> loop, find the first pulse for each sensor to discriminate against
>> reflections and calculate the distance based on delay/intensity
>> differences from other sensors taking into account the different speed
>> of sound in the given material, then repeat.
>> That would be trivial if only I wasn't a total math illiterate.
>> After some searches the magic words I stumbled upon were
>> "multilateration" and "TDOA", so I looked for examples,
>> source code or anything that could be made into a small microcontroller
>> but no cigar. One matlab example aside, I couldn't find anything
>> practical, except for some long math papers not even my cat (way better
>> at math than I) could understand:)
>>
>> So the question is: could such a beast be implemented using low cost
>> microcontrollers? Any pointers on similar projects with portable source
>> code (hopefully C) to be studied?
>> Thanks!
>
> Hire me to do the math!  I'm available.
>
> As far as "can it be done with low cost microcontrollers", you need to
> specify what you mean by "low cost".  ST and TI both make some pretty
> nifty parts that are under $5 in quantity, and have ARM cores and fast
> ADCs.  They should be more than fast enough.  I suspect that there's
> something out there that has a fast-enough ADC and costs less, if $5
> isn't "low cost" to you.
>
> If you don't mind some delay while the thing crunches numbers the actual
> microprocessor core can be darned near anything -- how long can it stop
> to think after you whack it with a stick?
>
> Three sensors ought to be enough, but more is probably better.

I'd like to throw an FPGA at this using 1 bit ADCs.  FPGAs have 
differential inputs that serve as an adequate comparator for may signal 
processing needs.

-- 

Rick C

On 07/05/16 09:07, Rob Gaddi wrote:
> asdf wrote:
>
>> Scenario: a small solid plate of a material yet to decide
>> with equally spaced vibration sensors along its outer sides.
>> An user knocks (or throws a small object) on a random point
>> on the surface and the logic finds the point by only reading
>> the sensors, ie time and intensity of the events.
>>
>> The plate is small, 1 meter or less, and can be made of
>> wood, acrylic etc. The number of sensors is not strictly
>> defined as well, although I believe 6 to 8 would be ideal.
>> If it helps, all sensors can be arranged in a circle or
>> a square pattern.
>> No need for precision, a 5% position error would be perfectly
>> acceptable. OTOH speed is important: it should be able to
>> sustain at least 50 reads per second.
>>
>> (Nope, I'm not designing a machine gun target. No weapons
>> involved, although in a broad sense we're somewhat close:*)
>>
>> It doesnt' seem that hard (I thought), just read all sensors
>> in a tight loop, find the first pulse for each sensor to
>> discriminate against reflections and calculate the distance
>> based on delay/intensity differences from other sensors
>> taking into account the different speed of sound in the
>> given material, then repeat.
>> That would be trivial if only I wasn't a total math illiterate.
>> After some searches the magic words I stumbled upon were
>> "multilateration" and "TDOA", so I looked for examples,
>> source code or anything that could be made into a small
>> microcontroller but no cigar. One matlab example aside, I
>> couldn't find anything practical, except for some long math
>> papers not even my cat (way better at math than I) could
>> understand:)
>>
>> So the question is: could such a beast be implemented using
>> low cost microcontrollers?

I tried that with my electronic Vibraphone MIDI controller
using a MC68HC11, in 2005, and couldn't get it working,
even with S/H. I only had one ADC, with an on-chip
8:1 multiplexer and an off-chip 64:8 one, and 64 simple
pulse stretchers acting as pseudo S/H. That worked fine
for 2 octaves (25 pads; each with birthday-card piezo
sensors on plywood under a rubber/silicone pad), but when
I wanted synchronized readings from each end of a 120mm
pad so I could tell where the strike occurred, just not
fast enough. It was a cool project, I'd like to try again
sometime.

It's probably feasible using an ARM, say an STM32. You *do*
need to sample adjacent sensors at the same time, but the
SM32s have up to three fast ADCs that can be synchronized.
If you lay out your vibration sensors in a triangular matrix,
and digitize adjacent sets of three in rapid rotation, you
have a chance.

> http://www.classltd.com/sound_velocity_table.html gives the propagation
> of sound in plexi at 1.7 mm/us.

Sound propagation across a thin plate is much slower than
through the bulk material, depending strongly on the thickness.
Halving the thickness means halving areal density, but 1/8
stiffness, so the speed of sound drops to 1/4.

These equations drive the selection of tone-woods for guitar
tops, for example. The maximum size of a top is completely
determined by the speed of sound in the plate, which determines
the frequency of the resonant modes. Spruce is exceptional
for its high ratio of stiffness to density, which is what
makes it desirable for guitars.

Clifford Heath.

On 05/07/2016 12:57 AM, asdf wrote:
> Scenario: a small solid plate of a material yet to decide
> with equally spaced vibration sensors along its outer sides.
> An user knocks (or throws a small object) on a random point
> on the surface and the logic finds the point by only reading
> the sensors, ie time and intensity of the events.
> 
> The plate is small, 1 meter or less, and can be made of
> wood, acrylic etc. The number of sensors is not strictly
> defined as well, although I believe 6 to 8 would be ideal.
> If it helps, all sensors can be arranged in a circle or 
> a square pattern.
> No need for precision, a 5% position error would be perfectly
> acceptable. OTOH speed is important: it should be able to 
> sustain at least 50 reads per second.
> 
> (Nope, I'm not designing a machine gun target. No weapons
> involved, although in a broad sense we're somewhat close:*)
> 
> It doesnt' seem that hard (I thought), just read all sensors
> in a tight loop, find the first pulse for each sensor to
> discriminate against reflections and calculate the distance
> based on delay/intensity differences from other sensors
> taking into account the different speed of sound in the 
> given material, then repeat.
> That would be trivial if only I wasn't a total math illiterate.
> After some searches the magic words I stumbled upon were
> "multilateration" and "TDOA", so I looked for examples,
> source code or anything that could be made into a small
> microcontroller but no cigar. One matlab example aside, I
> couldn't find anything practical, except for some long math
> papers not even my cat (way better at math than I) could
> understand:)
> 
> So the question is: could such a beast be implemented using
> low cost microcontrollers? Any pointers on similar projects
> with portable source code (hopefully C) to be studied? 
> Thanks!
> 

you might be able to do the signal conditioning with all analog parts and comparators 
until you get a binary value as output. 
Then use timer capture functions of a uC for getting the time difference. I think that's all you need....

On 5/6/2016 3:57 PM, asdf wrote:
> Scenario: a small solid plate of a material yet to decide
> with equally spaced vibration sensors along its outer sides.
> An user knocks (or throws a small object) on a random point
> on the surface and the logic finds the point by only reading
> the sensors, ie time and intensity of the events.

> So the question is: could such a beast be implemented using
> low cost microcontrollers? Any pointers on similar projects
> with portable source code (hopefully C) to be studied?
> Thanks!

How often do you expect to encounter "knocks"?

Must the plate be immobile?

On Fri, 06 May 2016 18:24:31 -0500, Tim Wescott wrote:

> Hire me to do the math!  I'm available.

I wish I had the money, really.

Some of you nailed the idea: it's for a drum controller.
I'm an amateur musician, I recenlty started taking lessons
as a drummer too and am experiencing the same problem every
drummer encounters one day: no way to practice at home due
to space and loudness. Electronic drumkits with pads can help
to partially solve the problem but they sound terrible once
you're used to real drum pieces expressive capabilities, not
taking into account latency which can be a problem in cheaper
sets.
A drum controller that can trigger multiple sound based not
only to the intensity but the area being hit, once paired with 
appropriate sample kits, could sound very very close to the
original and offer huge expressiveness to the player, still
being lighter, smaller and controllable volume-wise.

The firmware would be a bitch though: it should correctly 
detect notes and not being fooled by for example a flam or
multiple bounces, or a double hit on different zones.
The more I think of what it needs the more I believe it
requires hardware only big music equipment companies could
design around to make a working one.

On 5/7/2016 4:56 PM, asdf wrote:
> On Fri, 06 May 2016 18:24:31 -0500, Tim Wescott wrote:
>
>> Hire me to do the math!  I'm available.
>
> I wish I had the money, really.
>
> Some of you nailed the idea: it's for a drum controller.
> I'm an amateur musician, I recenlty started taking lessons
> as a drummer too and am experiencing the same problem every
> drummer encounters one day: no way to practice at home due
> to space and loudness. Electronic drumkits with pads can help
> to partially solve the problem but they sound terrible once
> you're used to real drum pieces expressive capabilities, not
> taking into account latency which can be a problem in cheaper
> sets.
> A drum controller that can trigger multiple sound based not
> only to the intensity but the area being hit, once paired with
> appropriate sample kits, could sound very very close to the
> original and offer huge expressiveness to the player, still
> being lighter, smaller and controllable volume-wise.
>
> The firmware would be a bitch though: it should correctly
> detect notes and not being fooled by for example a flam or
> multiple bounces, or a double hit on different zones.
> The more I think of what it needs the more I believe it
> requires hardware only big music equipment companies could
> design around to make a working one.

I don't know exactly what is required to do this job, but I can assure 
you it doesn't require "big hardware".  CM4 CPUs are very fast compared 
to similar devices from just a decade ago and there are larger, faster 
devices available at not too much higher prices.  Take a look at the 
Raspberry Pi 3.  It's not even at the top of the heap but has a lot more 
performance than a CM4.

I suggest you start with a PC then estimate the MIPS/MFLOPS required and 
figure out your hardware needs from that.

-- 

Rick C

On Sat, 07 May 2016 20:56:02 +0000, asdf wrote:

> On Fri, 06 May 2016 18:24:31 -0500, Tim Wescott wrote:
> 
>> Hire me to do the math!  I'm available.
> 
> I wish I had the money, really.

Whoops -- I thought it was a matter of going to your boss and saying 
"hey! hire this guy!"

> Some of you nailed the idea: it's for a drum controller.
> I'm an amateur musician, I recenlty started taking lessons as a drummer
> too and am experiencing the same problem every drummer encounters one
> day: no way to practice at home due to space and loudness. Electronic
> drumkits with pads can help to partially solve the problem but they
> sound terrible once you're used to real drum pieces expressive
> capabilities, not taking into account latency which can be a problem in
> cheaper sets.
> A drum controller that can trigger multiple sound based not only to the
> intensity but the area being hit, once paired with appropriate sample
> kits, could sound very very close to the original and offer huge
> expressiveness to the player, still being lighter, smaller and
> controllable volume-wise.
> 
> The firmware would be a bitch though: it should correctly detect notes
> and not being fooled by for example a flam or multiple bounces, or a
> double hit on different zones.

A bitch of a job is just a hugely interesting challenge, if you look at 
it from the right angle.

Before you give up you might want to glue some accelerometers to a plate 
and whack it with a stick, while monitoring their outputs.  You'd want an 
oscilloscope, but those can be had for less than $500, and less than $200 
if you're able to live with really basic stuff.

You'll probably want to be creative with what you get -- lab grade piezo 
accelerometers are spendy, but inside of every el-cheapo electret mic is 
an el-cheapo accelerometer just waiting to have a chance to shine.  You 
probably don't want an accelerometer chip -- most of those don't have the 
necessary bandwidth.  But go looking, just in case I'm wrong.

> The more I think of what it needs the more I believe it requires
> hardware only big music equipment companies could design around to make
> a working one.

I work out of my garage, and I can think of half a dozen chips that are 
candidates, and that I could build with, without even hitting the 
Internet.  So I think you're being a bit pessimistic, there.

* Just about every ST chip with a Cortex M3 or higher core.

* Ditto TI

* Ditto NXP

* Just about any of the TI 320F28xxx line (make sure that Code Composter 
is free, though).

* If ADI makes a DSP chip with built in ADC, look there.

And on and on.

-- 
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work!  See my website if you're interested
http://www.wescottdesign.com