There is a sort of scientific “sweet spot,” a window of discovery. It occurs when science turns a question into a potential solution to practical problems, even to problems that had been long dismissed as a “bridge too far.” If you can identify this sweet spot, you can trace the scientific roots of an emerging positioning technology, especially one in the midst of its early development stages.
A BBC news broadcast last summer about sonic measurement piqued my interest, and happenstance would find me passing by the academic institution in Lausanne, Switzerland where the research was being conducted. The school had recently been barraged by inquiries from non-scientific media; it was fortunate that the team had some genuine interest in surveying and invited me in. The story they had to tell was more interesting than I imagined.
“Is it feasible, from echoes, to find shapes?” pondered professor Martin Vetterli, School of Computer and Communication Sciences at Ecole Polytechnique Fédérale de Lausanne (EPFL). “This is a fundamental, basic mathematical problem,” he added. “There is a related problem, which is: Can you hear the shape of the room?”
On the surface, the answer might seem simple to the layman thinking, “Well, we have sonar underwater, and bats can navigate by sound.” But these are fundamentally different solutions, explained Professor Vetterli. Sonar benefits from beam-forming, with sound focused and analyzed by phased arrays that work much like the directional ranging of scanners. And bats navigate by creating rough mental maps with sound, but can we do better? Could the feedback (echoes) from a single sound source be analyzed to define the shape of a room? What Vetterli and his team discovered, seemingly at the sound of a finger snap and with off-the-shelf gear, is indeed yes, and with precisions (in certain conditions) as tight as 5mm.
Can You Hear the Shape of a Drum?
Martin Vetterli’s office at EPFL is lined on one wall, ceiling-to-floor, with a diverse collection of scientific books, revealing an interest in subjects beyond even his substantial body of work in electrical engineering, computer sciences, applied mathematics, wavelet theory and applications, image and video compression, communications systems, sensor networks, and more. His career has included prestigious postings at Columbia University in New York and UC Berkeley; he is well published.
In addition to his official research, semi-related scientific questions have been on his mind for many years, like this one: “There was a mathematical question posed by some physicists, which is: Can you hear the shape of a drum?”
To explain, he cited the source of his interest in the question. “We have drums of different shapes. You hit them, and then you listen to resonant frequencies. Can you tell the shape of the drum? The answer is no; in this case all you know is the resonant frequencies. [You] might have some success in [guessing] the type of drum; it is just like a human … saying, ‘Oh, it has this kind of timbre’ [but nothing scientifically quantifiable].”
Vetterli provided some history behind the drum question. “The question came from astrophysics, people who were looking at rotating pairs of stars. Marc Kac in 1966 posed the question [in American Mathematical Monthly], ‘Can you hear the shape of a drum?’, a kind of sexy paper title.”
But, he noted, “No answer, just posing the question. As it turns out 25 years later, in 1992, [research] showed that different shapes can sound the same. [The answer to the original question is] no, but you can infer a lot from the sound.”
The new question is quite different, and so are the conditions and the fundamentals of how we listen when we’re inside an object we are seeking to define. Vetterli explained, “We do something different, we listen to room impulse responses [the echoes] in the room … listening to many, many echoes, up to infinity.”
Going deeper into the scenario he adds, “[At the] time of arrival, we have phase information. A different problem, related in spirit, but different. The question was open—asked [of] many people—mathematicians working on related questions. No one knew the answer.”
As to Vetterli’s interest in the question, everything changed when a remarkable young student appeared right at the door of his office.
An Answer
“Along comes this fellow, Ivan [Dokmanic,] … An exceptional fellow; he came to start his Ph.D. [about three years ago]. I had interviewed him [previously], but [that day] I asked, ‘How was your flight from Croatia?” He said, no, he had biked the 1000 km,” recalls Vetterli.
He urged Dokmanic to take a few days to recover, then make an appointment, and then they would discuss research ideas. But the young fellow wanted to start right away—“Give me a problem.” Noting the enthusiasm and energy of his new student, Vetterli thought about the question of hearing the shape of a room.
Vetterli smiled widely as he recalled what happened next. “He comes back a day later and says, ‘It works.’ We have this burst of activity, trying this and that, developing tests, testing. I have been in the game a long time, and I can kind of smell if there is a good result, and this I sensed is a good result.”
That day was six weeks before the deadline for a major international conference on signal processing. Rapid work was done with cursory experiments, and the deadline was met; Ivan Dokmanic received the best student paper award for the paper, co-authored by Yue M. Lu and Martin Vetterli, entitled, “Can You Hear the Shape of a Room: The 2D Polygonal Case.”
It was, in Vetterli’s words, a mathematical exercise, not all of the solution, but enough of the solution to help formulate the answer (it addressed only polygons on a plane). Vetterli characterizes the paper as “cute, but [we] could see some practical applications.”
This was three years ago. In the intervening years, when time would permit, the team continued to design and execute experiments and began to address 3D and real-world examples, to truly step into Pasteur’s quadrant: scientific research inspired by applications.
Vetterli said he felt they reached a plateau, until about a year ago. That’s when another burst of activity began (and rooms were measured), culminating in the peer-paper that generated the media buzz, “Acoustic Echoes Reveal Room Shape” by Ivan Dokmanic, Reza Parhizkar, Andreas Walther, Yue M. Lu, and Martin Vetterli.
“I said, ‘Ivan, we can look at ‘Euclidian distance matrices.’ You know, this is something also very important for surveyors, I have an intuition about this,” said Vetterli. “[We] sketch something and we had a plane and [a] matrix of distances, like in the old roadmaps” with the lists of place-names on the two axes and the distances in the grid between. “This matrix for a plane has a very low rank: four, which means there are only really four columns of this [millions by millions] matrix that are truly independent. Solve these four and you have the whole matrix. For our problem we have this intuition that a higher rank of five might work”—as in solving five independent columns of the matrix will inform the entire matrix.
Research Details
I wanted to meet this Ivan and ask him about the experiments and his ideas on practical applications. Vetterli said that, ironically, Ivan was in Seattle at that time on a summer internship with Microsoft. A week later, over a burger the size of a GNSS rover (“These would be very popular in Croatia,” noted Ivan) at a 1950s-themed restaurant near Seattle, Dokmanic recounted the experiments.
“At first we wanted to do this with a single microphone. But to do 3D, it is simple trilateration [that requires] four microphones.” He explained that these were off-the-shelf components; only the omnidirectional sound emitter (speaker) was a more specialized item. “But even the omnidirectional speaker was a bit [imperfect]” because it is really many small speakers pointing in all directions.
He noted, “For the emitted sound we did a simple sine sweep of all audible frequencies. A bat [does] a sine sweep, but of a [narrower] range that we cannot hear.”
When I asked about using the snap of a finger to produce the echoes (one aspect of the original news story that the mainstream media emphasized), he responded, “You could, of course, use a snap of a finger, or pop a balloon which will produce a sine sweep, but for [a controlled experiment] we used the sound card of a laptop.”
He added that some desired improvements in the solution would be truly omnidirectional speakers and microphones, but that even with off-the-shelf gear the results were rather remarkable.
He said that, during his undergraduate studies in electrical engineering, he touched on the world of audio—playing in a band, working on digital audio effects—but his collaboration with Professor Vetterli was his first foray into the deeper elements of acoustics science.
For the initial experiments, they used a room with four perpendicular walls. Later they tipped tables on their sides and stacked them to form an irregular wall. Hand measurements with a tape were compared, and the results surprised everyone.
Later tests in a nearby cathedral in Lausanne added a lot of complexity. It was decided that the full interior would be far too complex at the time, so an alcove was chosen. There were good solid surfaces, and, while it was not possible to define the intricate details, and convex and curved surfaces were much harder to define, the overall dimensions were matched within centimeters. As both he and Vetterli stated, this is only the beginning.
Surveying Applications
There is a renewed interest in acoustics in general for spatial definition, and real-world applications are being implemented. Construction surveyors might be familiar with those little sonic tracers, attached to the end of heavy equipment blades for grade control systems, which bounce sound off a physical reference like a curb or gutter, string line, or an existing or previous pass as an elevation reference. But those are limited to just one focused distance to resolve.
I heard talk years ago of using sound to help navigate little copters for indoor inventory photography; I pictured swarms of what I call “e-Bats” being launched by surveyors. Recent news reveals unrelated research being jointly undertaken by the University of Washington and Microsoft on using the speaker and microphone of a laptop (or smart phone) to measure motion. Microsoft would not comment when I inquired; I can only speculate that this might be related to gaming, situational awareness, or new ways to operate the device by hand motion.
Vetterli spoke of more practical and contemporary needs of the signals: audio and communications industries need to solve the echo problems that befall devices as they are operated in rooms of different shapes and sizes. If you can hear the shape of a room, you can model the echoes or create realistic virtual environments. Your kid could play the piano or violin and then hear how it might sound at Carnegie Hall or Westminster Cathedral.
Those home sound system companies that purport to optimize a stereo for the shape of a room “are not really doing this,” according to Vetterli, at least in terms of actually measuring the room. He says, though, there is a lot of interest from telecommunications companies in solving the echo problems, and maybe someday Skype and speakerphones would not sound so annoying.
What utility would this solution have for surveying, or, say, measuring a room for BIM purposes? Vetterli says, “You [surveyors] are interested in very high precisions.” Both he and Dokmanic are optimistic that there will be refinements and a lot of potential applications.
Dokmanic proposed, “Think also of a solution that is the reverse. You have the dimensions of rooms already, and you can use the sound to verify or validate which room it is or to navigate [known spaces].” I could see this as being of benefit to the blind, but also perhaps as a quick way to validate as-built floor plans. As Dokmanic and Vetterli pointed out, this is an opportunity to evaluate the shape of an interior space rapidly and very inexpensively.
Perhaps the potential application of this solution to affect the high-precision world of surveying soonest might be as a complementary system, providing the initial orientation, dimensions, and spatial validation to inform other measurement instrumentation and metrological robotics. Integrated systems are a wave of innovation that is now just establishing a toehold in our profession.
This article originally appeared in Professional Surveyor Magazine.