This thesis proposes a methodology to estimate room geometry from times of arrival of early reflections in room impulse responses measured at multiple microphones. Room shape can be inferred by estimating the wall positions constituting a room, and several methods have been proposed for estimating the wall positions. The conventional methods to estimate wall positions require the times of arrival of the first-order reflections from the same wall. However, when microphones are widely distributed in space, the times of arrival from the same wall arrive at each microphone in a different order, which induces the echo labeling problem. Thus, in order to estimate wall positions, the echo labeling problem, which can be solved by associating the times of arrival with each wall, is the most critical problem for room geometry inference.
In this thesis, the echo labeling problem is tackled by proposing the iterative echo labeling algorithm. The iterative echo labeling algorithm constructs ellipses using the first-arriving reflections between all loudspeakers and microphones in the first iteration and estimates the walls tangent to the convex hull calculated by the ellipses. In the next iteration, the convex hull is expanded by utilizing subsequent times of arrival. The tangents of the intersection between the expanded convex hull and the estimated room in the previous iteration are investigated to estimate other walls. As this iteration is repeated, the convex hull is continuously expanded in space, and walls tangent to the convex hull are estimated in each iteration. In some iteration, the convex hull contains the estimated room in the previous iteration. In this iteration, the estimated room becomes the real room, and the iterative echo labeling algorithm is terminated. As a result, the iterative echo labeling algorithm can efficiently solve the echo labeling problem within a reasonable time, compared to previous research. Besides, the search space is greatly reduced by the geometrical constraints induced by the proposed method, which results in improved echo labeling performance.
However, there is a limitation that the iterative echo labeling algorithm cannot solve the echo labeling problem if all microphones do not acquire all times of arrival of the first-order reflections from each wall. The reason for this is that the iterative echo labeling algorithm always expands the convex hull. To address the problem induced by undetected times of arrival of the first-order reflections, the inner convex hull search algorithm is proposed. The inner convex hull search algorithm contracts the convex hull constructed by the iterative echo labeling algorithm from the outermost convex hull to the inner convex hull to estimate walls possibly missed by the iterative echo labeling algorithm in subiterations. The simulation and experiment results show that room geometry can be estimated even when some undetected times of arrival exist.
본 학위 논문은 다수의 마이크로폰에 측정된 음향 에코의 시간 지연으로부터 방의 구조를 추정하는 방법론을 제안한다. 방의 형상 추정 문제는 방을 구성하는 벽의 위치를 추정하여 해결될 수 있고 벽의 위치를 추정하기 위한 여러 방법이 제안되었다. 기존 제안된 벽 위치 추정 방법들은 같은 벽에서 반사된 다수의 일차 반사의 시간 지연을 요구한다. 하지만 마이크로폰이 공간상 넓게 분포된 경우 같은 벽에서 반사된 반사파의 시간 지연이 각 마이크로폰에 상이한 순서로 취득되는 에코의 모호성 문제가 발생한다. 따라서 벽의 위치를 추정하기 위해서는 반사파의 시간 지연을 각 벽에 할당하는 에코 라벨링 문제를 먼저 해결해야 하며, 이 에코 라벨링 문제는 방의 형상 추정 문제에 있어 가장 핵심적인 문제가 된다.
본 학위 논문은 에코 라벨링 문제를 해결하기 위한 반복적 에코 라벨링 알고리즘을 제안한다. 반복적 에코 라벨링 알고리즘은 첫 번째 반복에서 모든 마이크로폰에서 시간상 가장 빠르게 도달하는 시간 지연으로부터 반사파를 기하적으로 나타내는 타원을 구성하고, 이 타원들의 컨벡스 헐에 접한 접선을 탐색하여 컨벡스 헐에 접한 벽을 추정한다. 다음 반복에서는 각 마이크로폰에 측정된 다음 시간 지연을 사용하여 컨벡스 헐을 공간상 확장하고, 이전 반복까지 추정된 방과 현재 컨벡스 헐의 교차 영역에 접한 접선만을 탐색하여 새로운 벽을 찾는다. 이러한 일련의 과정이 반복되면서 컨벡스 헐은 공간상 확장되며 지속해서 컨벡스 헐에 접한 벽을 찾는다. 반복 과정이 진행될수록 컨벡스 헐은 확장되며 이 확장된 컨벡스 헐이 이전 반복까지 추정된 방을 공간상 포함하면, 추정된 방의 형상은 실제 방이 되며 알고리즘은 종료된다. 그 결과로 반복적 에코 라벨링 알고리즘은 효과적으로 에코 라벨링 문제를 무차별 검색에 의존하는 기존 알고리즘들보다 매우 적은 탐색 공간을 탐색하여 더 적은 가짜 벽 추정률 및 연산량에서 큰 성능 향상이 있음을 시뮬레이션을 통해 확인하였다. 또한 실제 방에서 측정된 시간 지연으로부터 방의 형상을 매우 적은 오차로 추정할 수 있음을 보였다.
하지만 반복적 에코 라벨링 알고리즘은 벽에서 반사된 일차 반사의 시간 지연이 모든 마이크로폰에 취득되지 않으면 문제를 해결할 수 없다는 한계가 존재한다. 그 이유는 반복적 에코 라벨링 알고리즘은 항상 컨벡스 헐을 확장하기 때문이며, 이를 해결하기 위해 내부 컨벡스 헐 탐색 알고리즘을 제안한다. 내부 컨벡스 헐 탐색 알고리즘은 반복적 에코 라벨링 알고리즘에서 구성된 컨벡스 헐을 부분 반복에서 축소해 최외곽 컨벡스 헐부터 내부 컨벡스 헐을 탐색한다. 그 결과 소수의 피크 누락이 존재하는 경우에도 방의 구조를 추정할 수 있음을 시뮬레이션 및 실제 실험 결과로 보였다.
