06/27/2013 08:55 am ET | Updated Aug 27, 2013

Hearing the Shape of a Room


Our senses work by turning features of the outside world into signals, which are processed by the nervous system and brain to build a mental model of reality. Humans rely heavily on vision. Dogs have a fantastic sense of smell. Cats use their whiskers -- touch. Sharks pick up electrical signals. Birds navigate using the Earth's magnetic field. And bats echolocate: they emit high-pitched sound waves and use the echoes to detect prey when hunting in pitch darkness.

Nearly 50 years ago, mathematician Marc Kac asked 'can you hear the shape of a drum?' More precisely: given a list of the natural frequencies at which something vibrates, can you deduce its exact shape? Eventually it turned out that the answer is 'no'. Different shapes can generate exactly the same list of sounds.

Now Ivan Dokmanić and colleagues at the École Polytechnique, Lausanne, have tackled a similar question: can you hear the shape of a room? This time it's echoes that matter, not vibrations. An echo arises when a pulse of sound hits something and bounces back. Sound travels quite fast, but it's not instantaneous, so the geometry of the room creates delays in the timing. Shout your name and the echo shouts it back a split second later.

Given the shape of a room, it's straightforward to predict how it echoes. But can you work backwards from the echoes to deduce the shape of the room? This time the answer is 'yes'. Dokmanić's team have implemented their solution on a computer, and carried out experiments using randomly placed microphones to pick up the echoes. The method works beautifully -- in fact, better than expected.

Most reports described their method as 'an algorithm', presumably to avoid contaminating the story with any reference to mathematics. Agreed, the public doesn't need to be told all the technical details, but it's unfair to mathematicians to eliminate their role entirely. Their research is in effect being attributed to a clever computer, which miraculously solves the problem of its own accord. How can anyone appreciate that math is useful, if no one mentions it when it's being used?

The algorithm uses the timing of the echoes from a given wall to decide where the wall is. That would be an easy calculation, but the signals from that wall are mixed up with those from all the other walls. Which bits of the recording bounced off which wall? That's a difficult bit. It lies at the heart of the method, and it's achieved using 'Euclidean distance matrices' or EDMs.

An EDM is a table (matrix) listing the distances between specific points in space: in this case, the microphones. It tells us the geometry of what's listening to the echoes. From this, we have to work out the geometry of what's producing them. The big problem is that the microphones 'hear' a jumbled mixture of multiple echoes bouncing off many walls. The algorithm has to un-jumble the echoes, working out which bits of sound are coming from the same wall.

The algorithm starts by making a plausible guess. The question is: is that guess correct? That's the clever bit. Suppose that the chosen parts of the signal have all bounced off the same wall. Sound bounces off a wall just like light bounces off a mirror, so the timing of these echoes will be exactly the same as the sound that would have been emitted by a fictitious source located on the far side of the wall -- the mirror image of the true source.

Throw that fictitious source into the mix and use the speed of sound to calculate how far it is from each microphone. Add those distances to your original table for the microphones . If you've made the right choice of partial echoes, your new table will be an EDM -- and that can be tested. The overall geometry has to be consistent, so the distances are related to each other in subtle ways. If the test confirms that you've got an EDM, then you've located a wall. One down, the rest to go: repeat. If you haven't got an EDM, you've still learned something: you chose the wrong partial echoes. Make a new choice and try again. If you're systematic, then eventually you'll find a wall. As more and more parts of the echoes fit consistently into the evolving picture, it gets easier to deal with the rest, until all walls have been located.

The team proves that this procedure leads to a unique correct answer, provided you use at least four microphones and the room is convex. An experiment in Lausanne Cathedral shows that the technique is useful for non-convex rooms too: the algorithm still detects the main flat surfaces.

What's all this good for? It might help to design concert halls with good acoustics, or to modify existing ones to improve their sound qualities. By playing the same trick with radio waves, you could get omnidirectional radar. It could even have forensic applications -- for instance, to work out where the fatal bullet was fired from by analyzing a sound recording.

It's a beautiful example of how a mathematical idea can be applied to a variety of real-world problems. Naturally, we need the help of a computer to do the grunt work: that's what they're for. But algorithms don't write themselves, and you can't write an algorithm to solve a problem unless someone has sorted out what it should do.