MicLoc

Since I publish this blog post, a lot of folks contacted me for more information, source code and overall encouragement to improve on the project. So I started to work on a better prototype and will document my findings as I go along.

(this is work in progress, check back regularly for newest developments)

What is MicLoc anyway?

MicLoc is an effort to develop a device capable of passively identifying a sound based event position on a given map, therefor pinpointing its location. The whole idea is to achieve this goal with everyday electronics and reduced development costs.

With the event of small, affordable, powerful microprocessors and electronics in general, this technology now seems accessible to potential commercial applications and general public use.

The main goals of this project are:

• Develop a low cost, compact device capable of identifying a source source location on a map with sub-meter precision.
  
• Develop, detail and open-source the hardware and plans used so anyone can build this device.
  
• Develop, detail and open-source the software needed to interface the device with a computer.
  

How it works

 

To understand how a source source can be located, we must first understand sound itself.

“Sound is a vibration that propagates as a mechanical wave of pressure and displacement, through some medium (such as air or water). Sometimes sound refers to only those vibrations with frequencies that are within the range of hearing for humans or for a particular animal.”

As with any wave, sound travels at a given velocity. If we can measure the time, in different points in space, at which the sound wave arrives we can deduct the origin of where that sound was first generated.

Lets assume sound travels at 340 meters per second (the actual speed of sound depend on several factors). When a sound is generated, it propagates in a spherical motion and after one second, it arrives at the border of an imaginary sphere with 340 meters of radius. For simplicity, lets think about 2D maps.

In this example we illustrate the previous proposed scenario. If we have one sensor and the originating time when the source was generated (T0) we know that the sound has to have an origin at the edge of the green circle with radius 340x(T-T0) with the center at our sensor.

With one sensor we only know what distance the sound source is from the sensor. When we add multiple sensors we can figure out exactly where the sound source is, it will be where all circles intercept with each other.

Take the following picture:

The only intercepting point common to all sensors is 3.

This is called acoustic location via trilateration.

There are other methods for locating sound sources, which involve other properties of a sound wave, sensors or the math used to infer the emitters position.

This is one way to explain how one can locate a signal with several sensors. 

The method proposed in this project is slightly different.

The reason is simple: we don't know when the signal was generated in order to start measuring time. We just know a signal was originated when it first arrives at a sensor. This is T0 for us.

So we have to work with the time differences between each sensor receiving the signal, which is usually called multilateration. The setup will be essentially a mini sound ranging device.

Considerations, limitations and challenges

There are several aspects to be considered when developing this project.

a) The device has to know its location and its sensors locations.

This means either a manual configuration (fewer costs) or gps-awareness (greater costs) or both.

b) The device must be able to have a very high sampling rate of its sensors.

c) The device must be able to communicate with the outside, ideally via wireless.

Wifi, Xbee, Bluetooth or others can be considered here.

d) The device should be able to have a decent battery autonomy. (need to define decent)

e) Sensors location and configuration are of major importance and have to be carefully considered.

f) The number of sensors affect the precision. The more sensors, more precision. But usually we cannot sample all sensors at the same time, so the more sensors, less sample rate so less precision. An optimal configuration must be studied for the device.

Phase 1

Given all factors here, I figured that there were just too many variables to just blindly decide on a configuration for the device. How many mics should it have? What's the minimum sample rate acceptable? How far apart should the mics be?

In order to get a more precise idea and answers for these questions I developed a small simulator where it is possible to test several of the previous factors.

In the simulator one can visually see what happens when the mic configuration changes, the sample rate changes or the sound speed changes. The red dots represent the mic locations, the purple dot the sound event position and the blue pixels is where the DTOA (diference of time of arrival) starts to get close to the real solution. The bluer it is, the closer it is to the solution.

The white pixels near the real location are marked as 'possible' solutions. This basically means that for the sample rate used, there is not enough precision to measure accurately and differentiate between the real solution and a proposed one.

This represents the very best case scenario. Real world introduces another set of problems like sound sample quality, measurement errors and so forth, but the simulator aims to provide a basis for the project. In particular, figuring out the minimum sample rate which should be used as well as the distance between mics and their configuration.

You can get the eclipse source code and runnable jar at GitHub. As always, suggestions/corrections/comments are most welcome.

As expected, sample rate plays a major role in the project, as well as the distance between mics. The higher the sample rate, the higher the precision is. Same for mic distance. The relationship is not linear either, as one might expect.

Using the simulator, we can test a setup with 4 mic, placed in a square of 200x200 millimetres. By varying the sample rate we get an estimate of possible locations per benchmark run (lower is better). Doing another analysis and maintaining the sample rate at 300kHz, it also possible to test how increasing the distance between mics affects the precision.

When the sample rate doubles, the precision seems to roughly quadruple.
The distance between mics has even more impressive impact on performance.
This is great news if you want to build a big device, by increasing the distance between the sensors, you can greatly increase precision. Unfortunately for me, at least for now, I want to build a compact device, so I must juggle with the sample rate and number of mics.



Phase 2

The first prototype was built on top of the Arduino Nano. This Arduino version is compact and generally something I like to use, but it doesn't seem ideal for the new version of MicLoc. One of the reasons has to do with the maximum sample rate I could get out of it. After messing around with the prescaler factor I was able to get around 77kHz out of the ADC. There is a report that someone achieved 360kHz.

Still, after using the simulator it became clear that is it really not enough for a compact device.

So I search around for an hardware platform that was compatible with the proposed goals and found Teensy 3.1.

Teensy 3.1

Teensy is a great platform. The new version 3.1 features some interesting characteristics that got my attention. One of them is that it has 2 internal ADC converters. This means taking 2 samples at the same time. Major bonus! It's fast (Cortex-M4 CPU can run at 98Mhz), almost 100% arduino compatible, inexpensive, full of a wide range of features and has a pretty active forum. I seriously recommend checking all its features, it's really nice! I think of Teensy a bit like “arduino on steroids”.

It seems like a good platform for developing MicLocV2, especially since I'm already familiar with programming arduinos. Of course, I will continue to search for other platforms for this project, I'm almost sure there are better ones that I don't know (suggestions are welcome).

I order a couple to start experimenting and figuring out how can I squeeze every kHz out of the ADCs.

MicLoc V2 - Prototype 1

My aim here is to understand exactly the Teensy 3.1 limitations on this project. The focus will be almost exclusively on sampling rates. That's because I consider the other goals, like comms (via WiFi, BT,...), position awareness (GPS,...), etc, details that can be 'easily' solved, given enough time and code.

The ability to properly sample fast enough can be a real limitation for using this platform tough.

Hence, I'll start here.

Sampling rate on Teensy 3.1

To find out how fast can I sample on Teensy, I developed the following simple test:

...
void loop() {
startTime = millis();

for(i=0;i
val = analogRead(AIN);
}
stopTime = millis();

totalTime = stopTime-startTime;
samplesPerSec = samples*1000/totalTime;
...

This yields an impressive result of 112599 samples/sec, or around 112kHz. Looks promising, even without any code modification or specific resolution setup, just using the analogRead function it is already much faster than arduino.

Despite Teensy having 16bit resolution (13 usable), I'm happy with 8bit resolution for the MicLoc. After searching around in forums, reading the specs, overall dwelling into the code I hacked away a solution for having a much higher sample rate.

I used the excellent ADC library from Pedvide, even if I ended up writing my own analog reading functions and macros. If you have a Teensy 3.1 (only works on 3.1) and want to give it a spin, you can find the ADC benchmark code at GitHub.

In short, I ended up with a promising 1230012 samples/sec, that's an impressive 1230kHz sampling rate. And the great thing is that it's possible to sample 2 channels at once with negligible loss of sampling rate. Of course, I can't assume the precision will be great, but it seems to me that this is not a big issue for the scope of the project.

Moving towards a prototype

Given that I need at least 3 mic sources to make this project work and I can sample with 2 ADCs at the same time, it makes sense that the V2 prototype has (at least) 4 mics. There's nothing to lose since sampling 3 or 4 analog ports take the same amount of time.

This is the simplest design I came with for a first approach:

Prototype and mics numbered. (bonus: my reflected self...)

Or on a more readable fashion:

Schematic using Fritzing

Besides the 4 microphones there is also a temperature/humidity sensor to calculate the speed of sound. The base is a square of 25cmX25cm, and the mics are 24cm apart.

The code is not very complicated. The idea is to sample and record the mics output to a buffer and, if the sound is above a certain threshold, pipe the data to the serial port for analysis. It also supports commands to check the current sample rate and make ajustments to the threshold level and read the current mic buffers.

You will need the Arduino IDE with the Teensyduino add-on, the Pedvide ADC library and the DTH11 library for the temperature sensor (or use your own) to compile and run the code in the Teensy3.1 (find it here: GitHub).

To get a feeling on what's going on on the mics, I made a Java program that connects to the serial interface, receives the sound events and plots them to a PNG file. Below is the output of the 4 mics.

T: 4511 Samples: 2048 Samples/mSec: 454.0013301 Temp: 18.00 Hum: 37.00 Threshold: 180

The buffer is 2048 bytes sampled at ~454kHz, the grey line shows when the threshold was crossed. Given the Teensy sampling at around 454kHz, the greatest diference between mics srqt(25*25+25*25)=35.355cm, minimum sound speed lets say 320 m/s, the maximum distance in samples from the start of the sound in one mic to the most distant one is given by 353.55/320*454 ~= 500 samples. So my choice was around 4 times that, or 2048 bytes.
General formula for the minimum samples is Dm/SS*SR, where Dm is the greatest distance between mics in millimetres, SS is the speed of sound in m/s (which is the same as mm/ms) and SR is the sample rate in kHz (which is the same for samples/ms).
This is something to consider when recording samples, the bigger the distance between mics the more memory you need in your hardware platform. Same for sampling rate.

Aligning the samples

In order to locate the origin of that sound, we first need to calculate the TDOAs  (Time Difference of Arrival) between each signal. In an ideal world, that would be trivial. Just slide the samples of each mic, subtract one from the other until all points are 0. Even better, if there was no noise, just find the first sample with sound <> 0.
Correctly calculate TDOAs is, of course, of paramount importance for the precision of the device. 
If you look at the image above, you can see the sound waves are similiar, but not equal in format or amplitude. And this is a sample with low noise. I tried several approaches to TDOA calculation, and the one that yielded the best results so far is using Cross-Correlation with time-delay analysis.

Aligning samples with Cross-Correlation and time-delay analysis

The distances between each vertical line gives us the TDOA. We can just assume the first line (in RED) to be T=0 and calculate from there the time differences to the others.
If you notice, the green line does not look good at all. The problem is that the samples where not filtered for noise nor normalized. For that I programmed a filter that normalizes the samples, reduces the noise and weights the sample values in relation to the distance of the probable start of sound. The output will then look like:

After normalization and filtering

The sound waves now seem properly aligned.

Another, more noisy, example:

Before normalization and filtering

After normalization and filtering

In this example we can clearly see the weighting of the sample values in relation to the start of the sound.
I think cross-correlation is a good way to attack the problem of differentiating the TOAs. Simple approaches like finding the first spike in the samples sometimes work, but are not flexible enough.
The weighting in the normalization function seems to also work well, despite it is probably driving the cross-correlation applied after in a very biased way. In general it makes not much sense to do this weighting if you are using a cross-correlation function, but in practice and for this specific problem of TDOA detection it appears to yield good results. I have no reference if this is being used in other similar systems.

From TDOAs to position

With a method developed for TDOAs detection, it's now time to move on and try to pinpoint the origin of the sound event. I suggest reading the Wikipedia article on Sound Ranging and Multilateration. Also check out the references, there are a lot of interesting readings which I did not know off when I developed the first prototype.

My approach for rapidly test the prototype was adapted from the simulator and basically consists in generating a grid and search for the point which as the least time differences to the measured TDOAs. Essentially this is brute-forcing the solution, so you are probably thinking it is not very elegant. You're right. At the same time, it as still some advantages, like a good degree of flexibility when it comes for errors in the measurements.

You can find the code AS IS here (eclipse project). Keep in mind this is test code, you will have to modify it in order to suit your needs. It is mostly not commented and not optimized. Refactoring is needed, etc...

For now, you will need to connect the Teensy to your PC via USB cable to interface the program with the prototype.

The test setup had the following layout:

Grid table, prototype with Mic #1 at 0,0

The grid table is great for the tests, since you can generate different sound events at different known locations and immediately see the output on your PC. You can snap your fingers or use, for example, a cloth clipper to make sounds.

Bellow is the sample output of the test program for a sound generated at grid position [-600,0], the reference origin is microphone #1.

|tempData|: T: 6755 Samples: 3072 Samples/mSec: 454.7742413 Temp: 20.00 Hum: 36.00 Threshold: 180 SoundSpeed: 343.8112863772779
|bufferData:| BUFFSIZE: 2048 Event: 1093
Read 2048
Read 2048
Read 2048
Read 2048

Post normalization (MIC1 basis is sample 0)
CC21@ 60
CC31@ 360
CC41@ 312

Best probable location: [-610,0]

And the respective generated images:

Raw mic output from cloth clipper

Post normalization and cross correlation

Generated heat map with mics in red, best solution plotted in yellow

This is a good result, with 1cm difference from the real event. 

Of course, this is not usually the case. There are a lot of issues with the setup, hardware and software that need to be improved/changed/fixed.

With such a compact setup, the prototype starts to suffer when the distances increase. I'm working on it.

Environmental noise is also an issue for a simple noise detection technique as a threshold level.

Undeniably, there are several factors that need to be addressed...

(update#1)

Phase 3

The world is not flat.

Arranging the microphones in a 2D plane is quick for tests and probably good enough for some applications where the sound source is located far away from the receivers or precision is not that important.

If we want to improve precision we must take into account that the world is not flat...

Lets look at the following setup example:

The microphones coordinates are in a 2D plane (assume z = 0).

Mic1: [0.0,0.0], Mic2: [340.0,0.0], Mic3: [340.0,340.0], Mic4: [0.0,340.0]

There are 3 sound events generated at fixed X,Y coordinates (-3,4m X, 0m Y) and different heights (Z) to help visualize what happens.

A: [-3400.0,0.0,0.0]
Distance to: 1:3400.0 2:3740.0 3:3755.422 4:3416.957
Time to: 1:10.0 2:11.0 3:11.0453 4:10.0498
DTime: 2-1:1.0 3-1:1.0453 4-1:0.0498 3-2:0.0453 4-2:-0.9501 4-3:-0.9954

B: [-3400.0,0.0,500.0]
Distance to: 1:3436.568 2:3773.274 3:3788.561 4:3453.346
Time to: 1:10.1075 2:11.0978 3:11.1428 4:10.1569
DTime: 2-1:0.9903 3-1:1.0352 4-1:0.0493 3-2:0.0449 4-2:-0.9409 4-3:-0.9859

C: [-3400.0,0.0,1500.0]
Distance to: 1:3716.180 2:4029.590 3:4043.908 4:3731.702
Time to: 1:10.9299 2:11.8517 3:11.8938 4:10.9755
Dtime: 2-1:0.9217 3-1:0.9639 4-1:0.0456 3-2:0.0421 4-2:-0.8761 4-3:-0.9182

We can see that by varying height, the times and delta times between mics start to be affected. This will, as expected, reduce accuracy and introduce location errors.

Hence the need for a 3D MicLoc prototype.

MicLoc 3D

The construction of a MicLoc 3D able prototype starts with its microphone array disposition. In 2D, my choice was the square form, where each mic is placed in each vertex.

Since I want to use only 4 mics, the natural arrangement in 3D space seems to be a regular tetrahedron (or a triangular pyramid).

The main idea behind this disposition is that I want to maximize the difference between all mics in the array for a given space. I choose the tetrahedron since all the vertices of a regular tetrahedron are equidistant from each other (they are the only possible arrangement of four equidistant points in 3-dimensional space).

The 3D prototype now resembles this:

You can seem the 3 mics at the base of the pyramid, and 1 on top. In the middle, there is also the temperature/humidity sensor and a nRF24L01 wireless based module for communications (more on this later).

The distance between each mic is ~50 cm

New Algorithm

The brute-forcing used in the latest algorithm is neither elegant nor processor/memory friendly. When I moved on to do 3D location, it quickly proves that is not practical either, as one should expect.

I already knew that, but was postponing writing up a new algorithm since I was busy with the hardware. Some quick and dirty math says I must change approach.

Lets say we divide the space into 10cm squares (our minimum precision) and deploy a grid of 100 meters.

In 2D, the old algorithm have to search a grid of (100/0.1)^2 points = 1 000 000 points.

In 3D, it would have to search (100/0.1)^3 points = 1 000 000 000 points.

Simple put it, if it took 0.1 seconds in this approach to brute force and search this grid in 2D, if we use the same approach for 3D it would took 100 seconds.

Of course, this can be fine tuned if, for example, one would only need to consider 20 meters on the Z axis.

All in all, it doesn't seem right.

A Monte-Carlo based approach.

The new algorithm developed is based on the Monte-Carlo method.

Basically it relies on two things:

a) Given a point in space we can calculate the precise TDOAs that a sample originating from that point should have.

b) The bigger the difference between the sum of all TDOAs from two points the farther away two points are from each other (erm... citation needed?)

The statement in b) will act as an heuristic so that the algorithm can converge into a solution. Actually, my chosen heuristic is the sum of the squares of all differences in TDOAs, which I call alpha.

Basically we choose a limit where the algorithm should run, a sphere (or cube) representing the maximum location range. After a sample has been gathered, the TDOA been aligned and calculated, a fixed set of random points are then calculated for their TDOA (a).

Using b) we choose the best point, i.e., the point closer to the actual location of the sound event, i.e., the point with lowest alpha.

Reduce the size of the cube, repeat. Terminate when happy enough.

The algorithm converges to the best solution dealing at the same time with the uncertainty and errors of the readings. When the algorithm stops, we have the best probable location and also the final difference between TDOAs, which can be used to decide either to accept the solution or discard it if it's considered to be too 'noisy'.

Consider the sound event at A [-3400.0,0.0,0.0]

The TDOAs expected to be read are: 
DTime: 2-1:1.0 3-1:1.0453 4-1:0.0498 3-2:0.0453 4-2:-0.9501 4-3:-0.9954

(don't forget MicLoc can only output the TDOAs.)

Lets imagine our setup introduced some errors in the readings, and MicLoc detects the following TDOAs:

DTime: 2-1:1.001 3-1:1.0452 4-1:0.0498 3-2:0.0453 4-2:-0.9501 4-3:-0.9954

This will output an alpha value of 1.738758339262613E-7

Which can be considered small enough for us to be sure about the location.

Let's imagine something went wrong while aligning the samples and TDOAs are messed up:

DTime: 2-1:1.1 3-1:1.05 4-1:0.06 3-2:0.05 4-2:-0.94 4-3:-0.97

alpha is now: 0.0018162586385181902

So the software might decide this is no good. Although a solution is found (since the algorithm has to stop on some condition, either iterations or time) something is wrong with it.

The exact alpha value for which a probable location should be discarded is still under research.

There is always the possibility of incorrect readings resulting in a small or acceptable alpha value, leading to incorrect results.

I have not found, empirically, that this happens very often.

Communications

Amongst other objectives in this project, remote communications is one.

For this, I considered several communications modules and protocols. I finally settle with nRF24L01 2.4GHz Radio/Wireless Transceivers.

Here's my reasons:

- High data rate: 2Mbps / 1Mbps

- Decent range, ~30m without antenna, ~1km with external antenna

- SPI interface, Arduino support, easy integrates with other hardware

- Output power channel selection and protocol settings can be set extremely low current consumption

- 125 channels, multi-point communication and frequency hopping

- Low cost

The current implementation is very simple, suitable for the tests I'm making. It simply uses the module to send out what was sent via serial before.

There is lots of space for improvement such as implementing data structures, data compression, proper protocols, etc.

My idea is to test the technology and find out more of this really interesting modules which I think are a nice addition to MicLoc3D.

You can find more information about using this modules here and here.

Code&Results

Soon...

----

Hack on!

My main idea for this prototype of MicLocV2 is to create the basis for a working prototype and share the experience and source code so others can start playing around and improving on this design or create something completely different.

If you're building this or something similar, I would really like to hear your experience. Feel free to drop a comment or contact me directly via umbelino[at]crazydog.pt 

Meanwhile, I will also be working on the next prototype and keep posting the results here, so keep tuned for upgrades.

kripthor