Matching Pursuit: A greedy Algorithm for Hearing the Shape of a Room

Speaker: Khaoula Chahdi

Date and place: September 23, 2021, at 10:30 – Videoconference

Abstract: Hearing the shape of a room, or recovering the 3D geometry of a room, is an innate ability in some species, such as bats, dolphins and other animals. For human beings, it is not that instinctive so we need more specific tools to do this task. This topic is a search field at the crossroads of several disciplines such as signal processing, mathematics and architectural acoustics. Mathematically we solve a non-convex, difficult and combinatorial inverse problem that requires the use of a greedy and sparse algorithm. Mark Kac was the first to explore this question and tried to estimate the shape of the outline of a drum from the sound it produces in his famous 1966 article ”Can One Hear the Shape of a Drum ?” which is a 2D problem, followed by many works that have tried to recover the 3D geometry of a room from the sound. The methods used recently to answer this question are based on the room impulse response RIR and the image source method, we can summarize them in three steps, peak extraction from the RIRs or the peak picking. Then, the right association between peaks and walls must be found, also known as echo labelling. Finally, triangulation to infer the wall positions. An example of this methods is studied in the article ”Acoustic echoes reveal room shape” The authors Using 5 microphones in their experiments, they tried to analyse the peaks of the RIRs measurement with the three steps already mentioned. They obtained satisfying results when testing this approach to hear the shape of the Lausanne cathedral. However, it is still not fully automated and requires three independent steps that may be suboptimal, each error in a step leading to subsequent errors in the next ones. In addition, this approach strongly relies on the availability of broadband, high frequency signals in order to extract sharp peaks. For our experiments, we use room impulse responses obtained from a single point source and a compact spherical microphone array containing 32 microphones distributed on the sphere. Our method is based on the image source model. Hence we will use the early reflections of the sound wave because they can be easily separated. The algorithm we use is an extension of Matching Pursuit, a greedy algorithm well known in the signal processing literature. The parameters involved in our experiments are the frequency of sampling, the angular and the radial resolution ,and finally, the microphone size. We tried to explore the impact of four parameters on the accuracy of our method by setting the default values of the parameters and varying the values attributed to each parameter separately.