One drone, four microphones and a loudspeaker: nothing more is needed to determine the position of walls and other flat surfaces within a room. This has been mathematically proved by Prof. Gregor Kemper of the Technical University of Munich and Prof. Mireille Boutin of Purdue University in Indiana, USA.
Can walls and flat surfaces be recognized using sound waves? Mathematicians have been studying this question from a theoretical standpoint for quite some time.
"The basic scenario is a room with flat walls, and maybe a ceiling and a floor," explains Prof. Gregor Kemper of the Chair of Algorithmic Algebra at TUM. The room is not assumed to be rectangular. It is also possible to measure the slope of the walls. Several microphones and a loudspeaker are contained in the room.
Speaker and microphones are placed on a drone
Previous studies have already mathematically proven that four microphones and a loudspeaker are sufficient to pinpoint the walls and also calculate their inclination. To prepare for this, the microphones have to be brought into the room at random positions, which will take quite some time and in some situations will be altogether impossible.
That is why Kemper and Boutin took the idea one step further. In their theoretical approach, they mounted the loudspeaker and four microphones on a drone - making measurement much more practical, because the equipment does not have to be installed in the room.
The algorithm can match echoes to a wall
The basic principle remains unchanged in the current approach: When the loudspeaker sends out a sound impulse, the waves bounce back from the walls. These direct reflections of the impulse are referred to as first order echoes. The biggest problem arising in the mathematical feasibility study: "Every microphone detects a large number of echoes. We need to be able to decide with certainty which echoes are coming from which wall," says Kemper.
The transit time - the time delay between emitting the sound pulse and receiving its echo - can be determined very precisely using the microphones. All transit times from a given wall have a specific relationship with one another. Kemper and Boutin developed a new algorithm that uses this relationship to assign individual echoes to a particular wall.
Once the echoes have been assigned to the right walls, the position and inclination of the walls are calculated using a geometric approach similar to that used by GPS when determining location data.
Ghost walls can be created by chance
The calculation can go wrong, however. That is because some echoes might satisfy the conditions of the mathematical relationship by chance. This leads to the identification of walls that are actually not there, so-called ghost walls.
"Naively, the probability of ghost walls would be expected to be higher when the microphones are mounted on a drone," explains Kemper. "This is because, in contrast to microphones mounted freely in space, they have less freedom of movement due to their rigid mounting on the drone. Instead of twelve, they have only six degrees of freedom."
Drone in ideal position for measurements
The question of how likely it is for such ghost walls to arise in the measurement process leads to the core statement of the paper: Kemper and Boutin have proved that the drone's freedom of motion is sufficient for the probability of placing it in a "good" position - meaning a position where no ghost walls are detected - to be equal to 1. In other words, such a placement is a near certainty.
"The six degrees of freedom of the drone are sufficient for the microphones to be almost certainly in an optimal position for the measurement," says Kemper. The only prerequisite is that the microphones are not arranged in a common plane on the drone.
A first step towards practical applications
In a next step, the researchers' scenario will become more realistic: They hope to find a mathematical solution for when errors or inaccuracies occur during measurement. They also intend to study configurations with the loudspeaker and microphones mounted on ground-based vehicles.
Mireille Boutin and Gregor Kemper: A Drone Can Hear the Shape of a Room, SIAM J. APPL. ALGEBRA GEOMETRY; Vol. 4, No. 1, pp. 123-140
Prof. Gregor Kemper
Technical University of Munich
Chair of Algorithmic Algebra
Tel: +49 (0)89 289 174 54
SIAM Journal on Applied Algebra and Geometry