SIAM News Blog

Drones Can Determine the Shape of a Room by Listening

By Karthika Swamy Cohen

Imagine a loudspeaker is placed in a room with a few microphones. When the loudspeaker emits a sound impulse, the microphones receive several delayed responses as the sound reverberates from each wall in the room. These first-order echoes—heard after sound impulses have bounced only once on a wall—then bounce back from each wall to create second-order echoes and so on. 

In a paper that published today in the SIAM Journal on Applied Algebra and Geometry, Mireille Boutin and Gregor Kemper attempt to reconstruct the shape of a room using first-order echoes received by four microphones attached to a drone. The microphones are aligned in a rigid configuration and do not lie in a common plane. Placing microphones on a drone—rather than independently throughout the room—reveals new areas of application.

“The microphones listen to a short sound impulse bouncing on finite planar surfaces — or the ‘walls,’” Boutin, a professor of mathematics and electrical and computer engineering at Purdue University, explains. “When a microphone hears a sound that has bounced on a wall, the time difference between the emission and reception of the sound is recorded. This time difference corresponds to the distance traveled by the sound during that time.”

Algebraic geometry principles can help determine the shape of a room from first-order echoes received by four microphones attached to a drone.
The time delay of each first-order echo provides the authors with a set of distances from every microphone to mirror images of the source reflected across each wall. Identifying the corresponding wall from which each echo originates is impossible; a microphone may not even receive an echo from a given wall based on its configuration and room geometry. 

The authors use a known modeling technique to focus on first-order echoes. This method interprets bounced sound as coming from a virtual source behind the wall instead of from the source, thus allowing a virtual source point to represent each wall. 

“The time differences between emission and reception provide the distance between the microphone and virtual source point,” Boutin says. “If we know the distance from one of these virtual source points to each of the four microphones, we can recover the coordinates of the virtual source and subsequently reconstruct four points on the wall — and hence the plane that contains the wall.”

However, the microphones cannot determine the distance that corresponds to each virtual source point, i.e., each wall. In response, Boutin and her colleagues designed a method to label the distances that correlate with each wall, a process they call “echo sorting.” 

The echo sorting technique uses a polynomial as a screening test and discovers whether the four distances lie on the zero set of a certain polynomial in four variables. A nonzero value reveals that the distances cannot bounce from the same wall. Alternatively, if the polynomial is equal to zero, the distances could possibly come from the same wall. 

This study demonstrates that reconstructing a room from first-order echoes acquired by four microphones is a theoretical problem that is well-posed under generic conditions. “This is a first step towards solving the corresponding real-world problem,” Boutin observes. “If the problem was not well-posed, then a practical solution would require more information. But since we know that it is well-posed, we can move on to the next step: finding a way to reconstruct the room when the echo measurements are noisy.”

This task is by no means straightforward. Certain drone placements give rise to problems that are not well-posed, suggesting that the noisy version of the problem will be susceptible to ill conditioning. More work is necessary to properly solve the problem of reconstructing a room from echoes. 

While the mathematical framework simply requires a rigid configuration of non-coplanar microphones, the research has a range of other potential applications. “These microphones can be placed inside a room or on any vehicle, such as a car, an underwater vehicle, or a person’s helmet,” Gregor Kemper, a professor in the Department of Mathematics at Technische Universität München, explains. The authors’ journal paper poses examples with stationary, indoor sound sources as well as sources placed on vehicles that may get rotated and translated due to movement; these latter sources present significantly more complicated situations.

“A moving car is different from a drone or an underwater vehicle in an interesting way,” Kemper adds. “Its positions have only three degrees of freedom—x-axes, y-axes, and orientation—whereas a drone has six degrees of freedom. Our work indicates that these six degrees of freedom are sufficient to almost always detect the walls, but this does not necessarily mean that three degrees will also suffice. The case of a car or any surface-based vehicle is the subject of ongoing research by our group.”

Achieving computational economy for such problems is an important goal for Boutin and Kemper. Their method requires a computer algebra system to perform symbolic computations, which can become more computationally complex for other variations of the problem, thus limiting its expansion to similar problems. “Finding a less computationally expensive technique to prove the same results would be desirable, especially if this method turned out to be applicable to other cases,” Kemper says. “Our mathematical framework is suitable for surface-based vehicles, but the actual computations necessary for the proof present challenges. We hope other teams will explore this issue.”

Karthika Swamy Cohen is the managing editor of SIAM News.
blog comments powered by Disqus