\section{Extension to multiple reflectors}
\label{sec:mult_ref_extension}
There are two big challenges when considering multiple reflectors. The first is how to accurately obtain TOA estimates for all the reflectors present in the acoustic environment. The second is how match the TOAs to the correct reflectors. When simulating a 3-D enclosure, or when measuring a real room, reflections from the ceiling and floor will be included in the RIRs. Although the extension to 3-D of our method is relatively straightforward [-], for simplification we only consider the 2-D case in this paper. In order to address room geometry inference in simulation, we therefore only simulate reflections which are due to the walls. Unfortunately, when estimating RIRs in a real room, it is impossible to simply ignore unwanted reflections. In both cases, disambiguation of TOA information remains a problem. For this reason we adopt two approaches. Given a complete RIR, that contains information about all reflectors that we can localize in 2-D, we propose the iterative common tangent algorithm (ICOTA). Given an incomplete RIR, we propose the clustering of multiple single reflector estimates using the Hough transform.
\subsection{Disambiguation of TOA Information for Multiple Reflectors}
\label{sec:disambiguation_toa}
The biggest challenge when analyzing RIRs is how to distinguish between direct-path and echo-path peaks and between peaks related to different reflectors (virtual sources). Furthermore, there is a question on how to find the set of matching TOAs for different sensor groups. Recently, [-] presented an approach for disambiguation of TDOA estimates for multiple sources. This approach is based on graph theory, making use of an efficient algorithm suitable for real-time implementation. The authors observed that by exploiting two TDOA constraints they could match peaks correctly to different sources. Although not mentioned in the paper, this also holds for reflections, which can be seen as virtual sources.
Generally speaking, disambiguation of TOA information can be performed at pre-processing stage or using the geometric constraint presented in this paper at a post-processing stage. In the following we outline two approaches that match TOA information to the correct reflectors in a simple acoustic scene.
\subsection{Iterative COTA}
\label{sec:icota}
Consider $N$ reflectorsi and a single sound source. By estimating the TOAs of the first order reflections, we can construct a set of $M \cdot N$
ellipse representations. If we group together $M$ ellipses,
extracted from every channel estimate and associated with a
particular reflector, then the line parameters of that particular
reflector can be estimated using a cost function similar to
(\ref{eq:cost_function_COTA}). Consequently for every $k\in\left
\{1, \cdots , N \right \}$ reflectors we can define the following
cost function,
\begin{equation}
\label{eqncot}
J_{\textrm{e}} \left (\mathbf{l},\left \{\mathbf{C}^{*}_{i,k} \right \}_{i=0}^{M-1} \right )= \sum_{i=0}^{M-1}{\begin{Vmatrix}\mathbf{l}^{T}\;\mathbf{C}^{*}_{i,k}\;\mathbf{l}
\end{Vmatrix}}^{2},
\end{equation}
where $M\geq 3$ and $\mathbf{C}^{*}_{i,k} = \det{(\Cb_{i,k})}\Cb_{i,k}^{-1}$.
The three unknown line parameters can be estimated by minimizing the cost function in~\eqref{eqncot},
\begin{equation}
\label{eqnmin}
\mathbf{\hat{l}}_{k} = \arg \min_{\mathbf{l}} J_{\textrm{e}} \left (\mathbf{l},\left \{\mathbf{C}^{*}_{i,k} \right \}_{i=0}^{M-1} \right ).
\end{equation}
Generally speaking, there will be a unique set of $M$ ellipses for
every $k$th reflector. However, prior knowledge is needed to
correctly group together related ellipses from the $\frac{(N \cdot
M)!}{M!(N \cdot M-M)!}$combinations of possible ellipses that can
be used in (\ref{eqncot}). Assuming that the channel estimates
only provide TOAs due to first-order reflections, then for a
rectangular room in 2-D we can expect $N=4$ distinct TOAs in each
channel. If the channel estimates contain information about the
direct-path propagation or if we have knowledge of the microphone
to source range and directivity (so that the source location
relative to the microphone can be determined), then we can
construct a total of $4M$ ellipses. The problem then lies in
finding the correct $M$ ellipses corresponding to every $k$th
reflector. Exhaustive computation of all combinations of groups of
$M$ to find the $N$ optimal line parameters using (\ref{eqncot})
is impractical when $M$ is large. Additionally, if measurement
errors are introduced in the system, suboptimal solutions may give
unsatisfactory inference results. Under noisy conditions a group
of $M$ randomly selected ellipses from the set of $\frac{(N \cdot
M)!}{M!(N \cdot M-M)!}$ combinations might produce a better
minimum in (\ref{eqncot}) than the designated group associated
with any $k$ reflector. For these reasons, we propose an iterative
approach that groups the set of ellipses on a per-reflector basis
\cite{Filos2010}. We start with the geometrically closest
reflector to the reference microphone, gradually minimizing the
total search space by discarding ellipses associated with already
localized reflectors.
The TOA associated with the closest reflector to the reference microphone ($\mathbf{r}_{0}$) is described by $\tau_{0,1}$. The ellipse constructed on basis of this TOA needs to be grouped together with all combinations of ellipses due to other source-microphone pairings and their associated TOAs, i.e.
\begin{equation*}
\tau_{i,k},\;i \in\left \{0, \cdots , M-1 \right \};\;k\in\left \{1, \cdots , 4 \right \}.
\end{equation*}
This results in $\frac{(4M)!}{M!(4M-M)!}$ possible combinations. In Algorithm~\ref{algo} we use (\ref{eqncot}) for each combination. The combination with the smallest value for $J_{\textrm{e}}$ is obtained when all ellipses belong to the same reflector (i.e. with reference to Algorithm~\ref{algo}, for the first reflector ($r=1$) considered, we set $r \equiv \tau_{i,1}$. All ellipses associated with that particular reflector can henceforth be discarded from the search space for subsequent iterations. This means that the reflector associated with $\tau_{0,2}$ ($r=2$), can be estimated by employing (\ref{eqncot}) for the reduced set of $\frac{(3M)!}{M!(3M-M)!}$ different combinations. Consequently the search space for the third reflector, associated with $\tau_{0,3}$ ($r=3$), is reduced to $\frac{(2M)!}{M!(2M-M)!}$ combinations while the final reflector, associated with $\tau_{0,4}$ ($r=4$), is localized using the last $M$ ellipses.
%\begin{table}[b]
%\small
%\caption{Algorithm table for estimating reflectors in a rectangular room.}
%\centering
%\scriptsize{
%\begin{tabular}{c c}
%\hline\hline
%Reflector & Total combinations evaluated \\
%\hline
%$1^{st}$ & $\frac{(4M)!}{M!(4M-M)!}$ \\
%$2^{nd}$ & $\frac{(3M)!}{M!(3M-M)!}$ \\
%$3^{rd}$ & $\frac{(2M)!}{M!(2M-M)!}$ \\
%$4^{th}$ & $M$ \\
%\end{tabular}}
%\label{table:pseudo}
%\end{table}
In this way we can iteratively localize all common reflective lines.
%Table \ref{table:pseudo} shows how the number of total combinations considered decreases for each subsequent reflector.
\begin{algorithm}
\small{
\KwIn{Array of $M \cdot N$ ellipses related to $M$
microphones and $N$ reflectors}
\KwOut{Array of $3 \cdot N$ line
parameters of $N$ reflectors}
%\SetLine \KwIn{Array of $M \cdot N$ ellipses related to $M$
%microphones and $N$ reflectors} \KwOut{Array of $3 \cdot N$ line
%parameters of $N$ reflectors}
\ForEach{Reflector $r$}{
Set $\mathbf{C}^{*}_{0,r}$\;
\ForEach{Microphone $i$}{
\ForEach{Reflective path TOA $k$}{
\If{Any $\mathbf{C}^{*}_{i,k},\;i \in\left \{0, \cdots , M-1 \right \};\;k\in\left \{1, \cdots , N \right \}$ ellipses not discarded}{
Return minimum $\mathbf{l}$ for $J_{\textrm{e}} \left(\mathbf{l}, \left \{\mathbf{C}^{*}_{i,k} \right \}_{i=0}^{M-1}\right)$
\;
}
%\arg \min_{\mathbf{l}}
Discard any $\mathbf{C}^{*}_{i,k},\;i \in\left \{0, \cdots , M-1 \right \};\;k\in\left \{1, \cdots , N \right \}$ ellipses used\;
}
}
Return optimal line parameter $\mathbf{l}$ associated with $r$-th reflector\;
}}
\caption{Iterative COTA estimation for multiple reflectors.}
\label{algo}
\end{algorithm}
\subsection{Clustering Multiple Single Reflector Estimates Using the Hough Transform}
The ICOTA operates optimally under two conditions. The RIRs contain a sparse but complete set of TOA estimates (ideally of only first-order reflection). $M$ and $N$ are small. Although the algorithm can operate when TOA estimates of higher-order reflections are included in the RIRs, it quickly becomes apparent that because of the way the algorithm scales, it is impractical already for $M \geq 6$ and $N \geq 5$.
\cite{Filos2011}