TDOA, multilateration etc. on small uC

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!

This seems to be another example of choosing an approach to solve a
problem, and having the problems encountered implementing that
approach replace the original one, while obscuring it as well as other
potential solutions.

What's the original problem description? 

Frequency of the impacts?
Size/shape/mass of the objects thrown?
Are they identical?
Speed/momentum? (both linear and angular.)
Are the objects removed after impact?  How?
Continuous operation?  Bursts?
Any environmental requirements?

Possible approaches, depending on the answers to those and other
questions:

* TDOA (1st only because you mention it.)
* Of the shelf touch sensor.
* High speed flash photography.
* High speed video.
* Ultrasound ranging.
* Kistler force plate? (Or a DIY equivalent.)
* Microphones behind the plate?
* Others?

R.W.

On 07.05.2016 2:24, Tim Wescott wrote:
> On Fri, 06 May 2016 22:57:18 +0000, asdf wrote:
>

(snip)

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

Math is an abstraction. But there are things that are just way too 
important to be lost in an abstraction. And cats are among such things.

So: what is your cat's name? :)

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

That's kinda similar to a GPS receiver after you get the pseudoranges. A 
GPS receiver also calculates your position in space (and time) after 
receiving (pseudo)ranges to (basically) four satellites.

They are called pseudo-ranges because there's ambiguity related to the 
time of arrival: you have only one time (not a pair of times) per each 
sensor, so you cannot calculate distance based on only that information. 
You need to solve a system of equations involving information from 
several sensors to determine the position (and time) of the event of 
interest (a drum stroke).

Perhaps an easy option for the OP to get started with the math could be 
to get some open-source software for a GPS receiver and rip the relevant 
piece of code out of it (replacing speed of light with speed of sound). 
Also with some caution about whether a 3D position (requires 4 
pseudoranges) or 2D position (requires 3 pseudoranges) is determined.

Also, the best book about GPS is "Understanding GPS" by Kaplan. I'm 
pretty sure it contains details about resolving position and time of an 
event from a set of pseudoranges.

Evgeny

On 08.05.2016 2:02, Evgeny Filatov wrote:
> On 07.05.2016 2:24, Tim Wescott wrote:
>> On Fri, 06 May 2016 22:57:18 +0000, asdf wrote:
>>
>
> (snip)
>
>>> 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:)
>>>
>
> Math is an abstraction. But there are things that are just way too
> important to be lost in an abstraction. And cats are among such things.
>
> So: what is your cat's name? :)
>

Ok, I digress a bit. Sometimes a cat's name can say a lot about its 
owner. For example, a married couple (who are friends of mine) owns a 
cat named Laplace. Now if I told you their names you would learn nothing 
about their personalities. But what if I tell you instead they are 
totally like the folks who own a cat named Laplace?

Gene

asdf wrote:

>...
>Some of you nailed the idea: it's for a drum controller.

Oops ...

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

From Roland's Drums FAQ:
( http://www.roland.co.uk/blog/electronic-drums-faq/ )

What is dual and three-way triggering?

Acoustic drums and cymbals sound very different depending on where you
hit them. Likewise, V-Pads and V-Cymbals that feature dual and
three-way triggering are able to detect and relay exactly where you�ve
made contact, making for faithful response and more expressive play.
You can also apply different sounds to parts of a dual or three-way
pad independently, e.g. a hand clap on a pad rim, a snare shot on the
drum head.

R.W.

asdf <asdf@nospam.com> writes:

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

I don't want to discourage you, but the companies which make such
drumkits probably put a lot of thought and effort into them. Do you
really think you can do better? I've got to believe they do change their
sound based on location.
-- 
Randy Yates, DSP/Embedded Firmware Developer
Digital Signal Labs
http://www.digitalsignallabs.com

On 08/05/16 07:37, Tim Wescott wrote:
> On Sat, 07 May 2016 20:56:02 +0000, asdf wrote:
>> 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 maximum stroke frequency is under 20Hz, but the stick oscillations
cause multiple tip strikes per stroke, if you know what I mean. That's
why you hold the sticks differently during a roll. For realistic drum
feel, you need to detect those, perhaps above 50Hz? I didn't attempt
this for my vibraphone, just not necessary. But it means you need a
total cycle time (arm on the attack edge, detect the peak, handle the
decay, and be ready to re-arm) all in 10ms.

You also need the logic to detect which pad (or part) was hit, and
discard the delayed pulse from adjacent pads. In my vibe, one stroke
could trigger six or seven adjacent pads. That was where my CPU speed
let me down; I could sample fast enough but not process duplicates.
But that was on an 8MHz 8-bitter; a 72MHz STM32F3 or 266MHz STM32F4
would have no difficulty.

> Before you give up you might want to glue some accelerometers to a plate
> and whack it with a stick, while monitoring their outputs.
> ... 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.

The commercial drum pads I've looked at use the same piezo wafers
that are used inside musical birthday cards. Bought for like 5/$.

Just make sure you load them well enough; they act like charge pumps
and with a high impedance load, even through layers of rubber and
plywood, it's easy to get 1500V pulses. In my test setup, the
half-cycle was about 1.5ms, so I stretched the pulses with a 5ms
time constant and scanned every 1ms - not perfect but that was as
fast as my CPU would go. You can't just trigger on a leading edge,
and even if you wait to see the level drop, it can still rise again.
Basically after "arming" on a leading edge, trigger on the highest
level you see in the next 4ms; then de-duplicate adjacent pads.

It was definitely possible to tell which end of a 120mm pad was hit
first; I just couldn't do it for 25 pads. A faster CPU would have no
real difficulty as long as you get the analog part right. (hint: a
pulse stretcher can suffer wind-up because of the high impedance of
the piezo wafer).

Clifford Heath.

On 5/7/2016 11:30 PM, Clifford Heath wrote:
> On 08/05/16 07:37, Tim Wescott wrote:
>> On Sat, 07 May 2016 20:56:02 +0000, asdf wrote:
>>> 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 maximum stroke frequency is under 20Hz, but the stick oscillations
> cause multiple tip strikes per stroke, if you know what I mean. That's
> why you hold the sticks differently during a roll. For realistic drum
> feel, you need to detect those, perhaps above 50Hz? I didn't attempt
> this for my vibraphone, just not necessary. But it means you need a
> total cycle time (arm on the attack edge, detect the peak, handle the
> decay, and be ready to re-arm) all in 10ms.
>
> You also need the logic to detect which pad (or part) was hit, and
> discard the delayed pulse from adjacent pads. In my vibe, one stroke
> could trigger six or seven adjacent pads. That was where my CPU speed
> let me down; I could sample fast enough but not process duplicates.
> But that was on an 8MHz 8-bitter; a 72MHz STM32F3 or 266MHz STM32F4
> would have no difficulty.
>
>> Before you give up you might want to glue some accelerometers to a plate
>> and whack it with a stick, while monitoring their outputs.
>> ... 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.
>
> The commercial drum pads I've looked at use the same piezo wafers
> that are used inside musical birthday cards. Bought for like 5/$.
>
> Just make sure you load them well enough; they act like charge pumps
> and with a high impedance load, even through layers of rubber and
> plywood, it's easy to get 1500V pulses. In my test setup, the
> half-cycle was about 1.5ms, so I stretched the pulses with a 5ms
> time constant and scanned every 1ms - not perfect but that was as
> fast as my CPU would go. You can't just trigger on a leading edge,
> and even if you wait to see the level drop, it can still rise again.
> Basically after "arming" on a leading edge, trigger on the highest
> level you see in the next 4ms; then de-duplicate adjacent pads.
>
> It was definitely possible to tell which end of a 120mm pad was hit
> first; I just couldn't do it for 25 pads. A faster CPU would have no
> real difficulty as long as you get the analog part right. (hint: a
> pulse stretcher can suffer wind-up because of the high impedance of
> the piezo wafer).

Or maybe a CPU is not the right tool for the job.  An FPGA would have 
virtually no speed limitations as it can dedicate hardware to just that 
job.  FPGAs can be as small as MCUs and nearly as low priced.  ADCs and 
DACs can be built in them easily for the sample rates needed.

-- 

Rick C

rickman <gnuarm@gmail.com> writes:
>> A faster CPU would have no real difficulty 
> Or maybe a CPU is not the right tool for the job.  An FPGA would have
> virtually no speed limitations

Before we talk about how much speed is needed, it would help to know
what calculations have to be done.  I was hoping Tim might have
something to say about the math, but I can understand how since he's not
getting paid, he may have better things to do ;-).

There's a famous math paper called "Can you hear the shape of a drum?"
(answer: no) but I don't think it applies here.

On Sun, 08 May 2016 14:16:54 -0700, Paul Rubin wrote:

> rickman <gnuarm@gmail.com> writes:
>>> A faster CPU would have no real difficulty
>> Or maybe a CPU is not the right tool for the job.  An FPGA would have
>> virtually no speed limitations
> 
> Before we talk about how much speed is needed, it would help to know
> what calculations have to be done.  I was hoping Tim might have
> something to say about the math, but I can understand how since he's not
> getting paid, he may have better things to do ;-).
> 
> There's a famous math paper called "Can you hear the shape of a drum?"
> (answer: no) but I don't think it applies here.

Blorping this out as I think of it:

You'd be solving for (essentially) the intersection of three spheres in 3-
D space (x, y and time * speed).

So, given t_1, t_2, and t_3, arriving at sensors located at (x_1, y_1), 
etc:

        (x_n - x)^2   (y_2 - y)^2
t_n^2 = ----------- + ----------- + time^2
          speed^2       speed^2

This gives you three equations in three unknowns, which will have no 
solutions, one solution, or two solutions.  I'm pretty sure that if the 
hardware isn't broken, and you haven't done something dumb like locating 
all of the sensors in a straight line, then you'll get exactly two 
solutions and one will be clearly nonsensical.

What I don't know is if there's a formulaic solution, or if you have to 
solve by root-finding or some such each time.  I _do_ know that Maxima 
chokes on the system of equations -- at least, Maxima's been chewing on 
it for the last five minutes and it still hasn't coughed up an answer.  
That usually means that (a) there isn't an answer, and (b) Maxima isn't 
smart enough to figure that out.  Sometimes, though, it means that 
there's an answer, but it's your job to do the math.

(That's one of the interesting things about symbolic solvers: they make 
it easy to do the moderately hard stuff, but when you throw something 
REALLY hard at it, then you're faced needing to do it yourself -- and 
you're out of practice, because the solver's been doing your work for you 
on the easy stuff.)

Solved problems should be available in the literature -- the math to do 
this has been around since LORAN or even OMEGA.  They used to do it with 
grease pencils on charts, back before microprocessors started eating 
people's brains.

-- 

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

On Sun, 08 May 2016 13:34:39 +1000, Clifford Heath wrote:

> On 07/05/16 08:57, asdf wrote:
>> Scenario: a small solid plate of a material yet to decide with equally
>> spaced vibration sensors along its outer sides.
>> The plate is small, 1 meter or less, and can be made of wood, acrylic
>> etc.
> 
> The stiffer the material, the higher the speed of a surface wave, and
> the faster your multi-lateration must be. Rubber over 1/8" plywood is
> good; quiet enough, dense enough, and sufficiently lacking in stiffness
> that the speed of surface waves is minimized.
> Wood without rubber would be bad, and acrylic worse.

How about rubber on acrylic?  Wouldn't wood change it's characteristics 
with moisture?

-- 

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