Room Geometry Estimation from Acoustic Echoes using Graph-Based Echo Labeling

A computer being able to estimate the geometry of a room could benefit applications such as auralization, robot navigation, virtual reality and teleconferencing. When estimating the geometry of a room using multiple microphones, the main challenge is to identify which reflections, or echoes, originate from the same wall and can, therefore, be modeled by a virtual source outside the room using the mirror image source model. In this paper we present a new and efficient method to disambiguate the echoes using a graph theoretical approach where echo combinations are modeled as nodes in a graph and the problem is stated as a maximum independent set problem. Once the echoes are correctly labelled, we know the locations of the virtual sources from which we can infer the room geometry. Experiments for shoe-box shaped rooms show that we can reliably estimate the room geometry within seconds on contemporary hardware and achieve centimeter precision on finding the vertices of the room.Winner Best Student Paper Award track audio and acoustic signal processingCircuits and System