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!

Reply to
asdf
Loading thread data ...

formatting link
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.
Reply to
Rob Gaddi

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 
 Click to see the full signature
Reply to
Tim Wescott

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
Reply to
rickman

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.

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.

Reply to
Clifford Heath

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

Reply to
Johann Klammer

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.

Reply to
asdf

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
Reply to
rickman

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

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.

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 
 Click to see the full signature
Reply to
Tim Wescott

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.

Reply to
Roberto Waltman

(snip)

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

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

Reply to
Evgeny Filatov

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

Reply to
Evgeny Filatov

Oops ...

From Roland's Drums FAQ: (

formatting link
)

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

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.

Reply to
Roberto Waltman

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 
 Click to see the full signature
Reply to
Randy Yates

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.

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.

Reply to
Clifford Heath

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.

Reply to
Clifford Heath

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
Reply to
rickman

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.

Reply to
Paul Rubin

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 
 Click to see the full signature
Reply to
Tim Wescott

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

--
Tim Wescott 
Wescott Design Services 
 Click to see the full signature
Reply to
Tim Wescott

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.