Iterative Echo Labeling Algorithm With Convex Hull Expansion for Room Geometry Estimation

Estimating room geometry is an important problem in audio signal processing, with various applications such as dereverberation and spatial audio. Several methods have been proposed to localize the positions of the walls given the times of arrival (TOAs) from acoustic room impulse responses (RIRs). To localize a reflector, reflections from the same wall should be identified first. When multiple microphones are widely installed inside a room, however, it is hard to identify the reflections generated by the same walls, which leads to the echo labeling problem. In this paper, we propose an iterative echo labeling algorithm to solve the echo labeling problem. We construct a convex hull of ellipses with first-arriving reflections at the initial iteration and expand the convex hull by utilizing later reflections at subsequent iterations. While expanding the convex hull, we sequentially localize the walls by inspecting tangents of the convex hull. Finally, the iteration is terminated when the expanded convex hull of ellipses becomes a superset of a room. As a result, the proposed algorithm can solve the echo labeling problem without prior knowledge of the number of walls and high computational complexity.