\section{Improved localization using the Hough Transform}
\label{sec:line_seg_extraction}
In a noise-free scenario, and neglecting the effects of machine precision, the global minimum of~\eqref{opt_solution} will also be the true solution, so that all ellipses are perfectly aligned and yield a single solution that is the common tangent to all ellipses considered. However, due to errors in the TOA information, the ellipses are prone to mismatch and~\eqref{opt_solution} is not guaranteed to converge to the global minimum. In the following we will present a methodology that improves the accuracy and robustness of the reflector estimate by considering repeated measurements of TOA information.
\subsection{Geometrical relation between line estimates and ellipses}\label{geometrical_interpretation}
Having obtained an estimate of the reflector line from~\eqref{opt_solution} we proceed to calculate points on the ellipses that are geometrically related to this line.
Generally speaking, given $M$ ellipses and $O$ measurement repetitions, our aim is to establish a collection of points
\begin{equation}
\mathbf{p}_{j}\triangleq [x_{j}\;y_{j}]^{T},\;\;\;\; j=0,\dots,P,
\end{equation}
where $M\,O-1\leq P \leq 2\,M\,O-1$, that are related to both the
ellipse $\mathbf{C}$ and the line $\mathbf{l}$ in the following
way:
\begin{itemize}
\item If $\mathbf{l}$ goes through $\mathbf{C}$ then we obtain two points of intersection.
\item If $\mathbf{l}$ touches $\mathbf{C}$ at one point, or in other words if $\mathbf{l}$ is tangent to $\mathbf{C}$, then we obtain one point of tangency.
\item If $\mathbf{l}$ does not go through $\mathbf{C}$ then we need to calculate the closest point on the line with respect to the conic.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Analytical framework}\label{analytic_framework}
Consider for the moment, two lines that are parallel to $\mathbf{l}$ and tangential to the ellipse at points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$. We can construct a line $\mathbf{l}_{\textrm{T}}$ that goes through both points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$, and consequently compute the points of intersection with the ellipse. For this we note that the slope of $\mathbf{l}$ is given by $m = -\frac{l_{1}}{l_{2}}$. Therefore the problem is constrained to finding the points on the ellipse for which the tangents have slope $m$. This can be achieved by implicit differentiation of the ellipse given in~\eqref{eq:conic_eq}
\begin{equation}
\label{eq:ellipse_diff}
\frac{d}{dx}\left( \mathcal{C} \right) = 2\,a\,x + 2\,b\,x \frac{dy}{dx} + c\,2\,y \frac{dy}{dx} + 2\,d \frac{dy}{dx} + 2\,b\,y = 0\,.
\end{equation}
After setting $\frac{dy}{dx}=m$ the line that goes through both tangential points can be expressed as
\begin{equation}
\label{eq:tangent_line}
\mathbf{l}_{\textrm{T}} = [(a + b\,m)\,(b + c\,m)\,(d + e\,m)]^{T}.
\end{equation}
%\begin{figure}[!t]
% \centering
% \includegraphics[scale=0.4]{analytical_constraint}
% \small
% \caption{The line $\mathbf{l}$ (solid) intersects the ellipse at points $\mathbf{p}_{\alpha}$ and $\mathbf{p}_{\beta}$. The two parallel lines of $\mathbf{l}$ that are tangential to the ellipse at points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$ are represented by $\mathbf{l}_{\textrm{T}}$ (dotted) that intersects the ellipse at the two tangential points.}
% \label{fig:analytical_constraint}
%\end{figure}
Given a line $\mathbf{l}$ that goes through the ellipse $\mathbf{C}$, the points of intersection $\mathbf{p}_{\alpha} \triangleq [x_{\alpha}\;y_{\alpha}]^{T}$ and $\mathbf{p}_{\beta} \triangleq [x_{\beta}\;y_{\beta}]^{T}$ are given by
\begin{eqnarray}
\label{eq:intsect1}
x_{\alpha} = & \frac{l_{2}\sqrt{(A+B+C)}+D}{E}\;,\;&y_{\alpha} = -\frac{-l_{3}+l_{1}\,x_{\alpha}}{l_{2}}\,;\\
\label{eq:intsect2}
x_{\beta} = & -\frac{l_{2}\sqrt{(A+B+C)}-D}{E}\;,\;&y_{\beta} = -\frac{-l_{3}+l_{1}\,x_{\beta}}{l_{2}}\,;
\end{eqnarray}
with
\begin{eqnarray*}
A &=& b\, \left(b\, l_{3}^2 - 2\, d\, l_{2}\, l_{3} - 2\, e\, l_{1}\, l_{3} + 2\, f\, l_{1}\, l_{2}\right)\,,\\
B &=& d\, \left(d\, l_{2}^2 - 2\, e\, l_{1}\, l_{2} + 2\, c\, l_{1}\, l_{3}\right)\,,\\
C &=& e^2\, l_{1}^2 + 2\, a\, e\, l_{2}\, l_{3} - c\, f\, l_{1}^2 - a\, f\, l_{2}^2 - a\, c\, l_{3}^2\,,\\
D &=& b\, l_{2}\, l_{3} - d\, l_{2}^2 - c\, l_{1}\, l_{3} + e\, l_{1}\, l_{2}\,,\\
E &=& c\, l_{1}^2 - 2\, b\, l_{1}\, l_{2} + a\, l_{2}^2\,.
\end{eqnarray*}
Instead of using $\mathbf{l}$ in~\eqref{eq:intsect1}
and~\eqref{eq:intsect2} to find the points of intersection
$\mathbf{p}_{\alpha}$ and $\mathbf{p}_{\beta}$, we can replace $[l_{1} \; l_{2}
\; l_{3}]^{T}$ with $[l_{\textrm{T}_{1}}\,l_{\textrm{T}_{2}}\,l_{\textrm{T}_{3}}]^{T}$, as
given by~\eqref{eq:tangent_line}, such that
%\begin{eqnarray*}
%l_{1} &=& (a + b\,m)\,,\\
%l_{2} &=& (b + c\,m)\,,\\
%l_{2} &=& (d + e\,m)\,,\\
%\end{eqnarray*}
%\begin{equation}
%l_{1} = (a + b\,m)\;;\;l_{2} = (b + c\,m)\;;\;l_{2} = (d + e\,m)\,,
%\end{equation}
\begin{equation}
\label{eq:tangent_line_def}
\mathbf{l} \triangleq [(a + b\,m)\,(b + c\,m)\,(d + e\,m)]^{T},
\end{equation}
in order to find $\mathbf{p}_{T_{\alpha}}$ and
$\mathbf{p}_{T_{\beta}}$. Since any line $\mathbf{l}$ will have
two parallel lines that are tangential to the
ellipse,~\eqref{eq:intsect1},~\eqref{eq:intsect2}
and~\eqref{eq:tangent_line_def} can be used to check whether
$\mathbf{l}$ goes through the ellipse, is tangential to the
ellipse or does not go through the ellipse.
\begin{itemize}
\item If $\mathbf{l}$ cuts
through the ellipse, then the parallel line touching the ellipse
at point $\mathbf{p}_{\alpha}$ will be either to the left or
right, above or below $\mathbf{l}$. In other words
$\mathcal{L}(x_{\alpha},y_{\alpha})$ will either be positive or
negative. Therefore if $\mathcal{L}(x_{\alpha},y_{\alpha})$ is
positive and $\mathbf{l}$ does indeed go through the ellipse, then
by definition $\mathcal{L}(x_{\beta},y_{\beta})$ must be negative.
Consequently if $\mathcal{L}(x_{\alpha},y_{\alpha}) < 0$ then
$\mathcal{L}(x_{\beta},y_{\beta}) > 0$.
\item If $\mathbf{l}$ is
tangential to the ellipse, then
$\mathcal{L}(x_{\alpha},y_{\alpha})$ is either equal to zero, or
not equal to zero. Therefore if
$\mathcal{L}(x_{\alpha},y_{\alpha}) = 0$, then
$\mathcal{L}(x_{\beta},y_{\beta}) \neq 0$. A similar argument
holds for the case when $\mathcal{L}(x_{\beta},y_{\beta}) = 0$.
\item If $\mathbf{l}$ neither intersects or is tangential to the ellipse,
then the two parallel lines touching the ellipse at points
$\mathbf{p}_{\alpha}$ and $\mathbf{p}_{\beta}$ are either both
below, above, left or right of $\mathbf{l}$. In other words if
$\mathcal{L}(x_{\alpha},y_{\alpha}) > 0$ then
$\mathcal{L}(x_{\beta},y_{\beta}) > 0$. If
$\mathcal{L}(x_{\alpha},y_{\alpha}) < 0$ then
$\mathcal{L}(x_{\beta},y_{\beta}) < 0$.
\end{itemize}
Consequently in order to
determine the relationship between $\mathbf{l}$ and the ellipse,
it is sufficient to compute
\begin{equation}
\label{eq:check}
\Phi = \left | \text{sgn} \big\{ \mathcal{L}(x_{\alpha},y_{\alpha}) \big\} + \text{sgn}\left \{ \mathcal{L}(x_{\beta},y_{\beta}) \right \} \right |,
\end{equation}
where $\text{sgn}\left \{ \;\cdot\; \right \}$ is defined as
\begin{equation*}
\text{sgn}(x) = \left\{
\begin{array}{l l l}
-1 &\quad \text{if $x < 0$}\,,\\
0 & \quad \text{if $x = 0$}\,,\\
1 &\quad \text{if $x > 0$}\,.\\
\end{array} \right.
\end{equation*}
\begin{itemize}
\item If $\Phi=0$ then $\mathbf{l}$ goes through the ellipse.
\item If $\Phi=1$ then $\mathbf{l}$ is tangential to the ellipse.
\item If $\Phi=2$ then $\mathbf{l}$ does not intersect the ellipse.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Obtaining candidate points}\label{candidate_points}
%Given the analytical framework outlined in Section~\ref{analytic_framework} it is possible to estimate a number of points $\mathbf{p}_{i}$ that are related to each ellipse in~\eqref{eqncot} and the candidate lines given by~\eqref{candidate_solutions}. Instead of estimating $\mathbf{p}_{i}$ exhaustively for each ellipse and candidate lines, it is more efficient to group candidate points on a per-reflector basis, denoted $\mathbf{p}_{j,k}$. We define
%\begin{equation}
%\mathbf{p}_{j,k},\;\;\;\;\,j=0,\dots,P^{\dag}\,;\;k\in\left \{1, \cdots , N \right \},
%\end{equation}
%where $M-1 \leq P^{\dag}\leq 2\,M-1$, as the $j$th candidate point for every $k$th reflector. Consequently for every $k$th reflector there will be $M$ related ellipses.
%For each of the $M$ ellipses $\left (\mathbf{C}_{i,k}\right )$ and each candidate solution $\left (\hat{\mathbf{l}}_{k}\right)$, related to the $k$th reflector, we first use~\eqref{eq:check} to check whether the estimated line either intersects the ellipse, is tangential to the ellipse or does not intersect the ellipse. In the first case, when $\hat{\mathbf{l}}_{k}$ goes through the ellipse, it is sufficient to use~\eqref{eq:intsect1} and~\eqref{eq:intsect2} to obtain the two points of intersection. In the second case, when $\hat{\mathbf{l}}_{k}$ is tangential to the ellipse, we simply use either~\eqref{eq:intsect1} or~\eqref{eq:intsect2}, since the solutions will be equivalent, to obtain one point of tangency. In the final case, where $\hat{\mathbf{l}}_{k}$ does not intersect the ellipse, we use~\eqref{eq:intsect1},~\eqref{eq:intsect2} and~\eqref{eq:tangent_line_def} to obtain the two points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$: the tangential points of the two parallels of $\hat{\mathbf{l}}_{k}$ on the ellipse. The reason why we compute these two points is because one of them will be the closest point on the ellipse and the other the furthest point on the ellipse, with respect to the line. In order to then choose the closest point it is sufficient to compute the distance of points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$ and the line, by projecting them both onto the line and selecting the shortest distance such that
%\begin{equation}
%\min \left \{ \frac{\Big| l_1\,x_{T_{\alpha}} + l_2\,y_{T_{\alpha}} + l_3 \Big|}{\sqrt{l_1^{2}+l_2^{2}}},\frac{\left | l_1\,x_{T_{\beta}} + l_2\,y_{T_{\beta}} + l_3 \right |}{\sqrt{l_1^{2}+l_2^{2}}} \right \}.
%\end{equation}
New candidate points are appended to the intially empty matrix $\mathbf{p}_{j}$ in the following way. First~\eqref{eq:check} is used to check whether the estimated line either intersects the ellipse, is tangential to the ellipse or does not intersect the ellipse. In the first case, when $\hat{\mathbf{l}}$ goes through the ellipse, it is sufficient to use~\eqref{eq:intsect1} and~\eqref{eq:intsect2} to obtain the two points of intersection. In the second case, when $\hat{\mathbf{l}}$ is tangential to the ellipse, we simply use either~\eqref{eq:intsect1} or~\eqref{eq:intsect2}, since the solutions will be equivalent, to obtain one point of tangency. In the final case, where $\hat{\mathbf{l}}$ does not intersect the ellipse, we use~\eqref{eq:intsect1},~\eqref{eq:intsect2} and~\eqref{eq:tangent_line_def} to obtain the two points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$, i.e. the tangential points of the two parallels of $\hat{\mathbf{l}}$ on the ellipse. The reason why we compute these two points is because one of them will be the closest point on the ellipse and the other the furthest point on the ellipse, with respect to the line. Since we are only interested in the closest point, it is sufficient to compute the distance of points $\mathbf{p}_{T_{\alpha}}$ and $\mathbf{p}_{T_{\beta}}$ and the line, by projecting them both onto the line and selecting the shortest distance from
\begin{equation}
\min \left \{ \frac{\Big| l_1\,x_{T_{\alpha}} + l_2\,y_{T_{\alpha}} + l_3 \Big|}{\sqrt{l_1^{2}+l_2^{2}}},\frac{\left | l_1\,x_{T_{\beta}} + l_2\,y_{T_{\beta}} + l_3 \right |}{\sqrt{l_1^{2}+l_2^{2}}} \right \}.
\end{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Reflector localization using the Hough transform}\label{improved_mre}
The Hough transform is a method for estimating the parameters of a shape from its boundary points \cite{Duda1972}. It considers the following normal parametrization
\begin{equation}
\label{hough_trans_eq}
\rho = x\,\cos \theta + y\, \sin \theta,
\end{equation}
which specifies a straight line by the angle $\theta$ of its
normal and its algebraic distance $\rho$ from the origin. A point
in the cartesian space corresponds in the Hough parameter space to
all the lines passing through it, i.e. a sinusoid. Conversely,
points in the parameter space are transformed into lines in the
cartesian coordinate space. Given two points lying on a line with
parameters $\rho,\theta$, in the Hough parameter space the
sinusoids corresponding to these two points intersect at
$\rho,\theta$. Therefore, given a collection of points
$\mathbf{p}_{j}$ in the coordinate space, it is possible to
estimate the line parameters of a line which is seen as a best-fit
to that collection of points. If the points $\mathbf{p}_{j}$ lie
on a straight or quasi-straight line, then by computing the
intersection of the sinusoids in the Hough space it is possible to
obtain values for $\theta$ and $\rho$ from~\eqref{hough_trans_eq}
that can be used to estimate the line parameters of the best-fit.
Let $\rho \in\mathbb{R}$ and $\theta \in[0, \pi]$.
For each point $[x_{j}\;y_{j}]^{T}$ we calculate
\begin{equation}
\label{hough_trans_eq_es}
\hat{\rho} = x_{j}\,\cos \hat{\theta} + y_{j}\, \sin \hat{\theta}.
\end{equation}
The results are stored in an accumulator $\mathcal{A}$, initially set to zero, which is incremented at every step such that:
\begin{equation}
\mathcal{A} \left ( \hat{\rho},\hat{\theta} \right ) = \mathcal{A} \left ( \hat{\rho},\hat{\theta} \right ) + 1.
\end{equation}
The largest maximum of the accumulator given by
\begin{equation}
\left [ \hat{\theta}_{\text{max}},\hat{\rho}_{\text{max}} \right ] = \max \left \{ \mathcal{A} \left ( \hat{\rho},\hat{\theta} \right ) \right \},
\end{equation}
is then picked, which finally leads to the line parameters of the best-fit:
\begin{equation}
\hat{\mathbf{l}}_{\textrm{H}} = [\cos (\hat{\theta}_{\text{max}})\,\sin (\hat{\theta}_{\text{max}})\,(-\hat{\rho}_{\text{max}})]^{T}.
\end{equation}
By taking repeated measurements of TOAs, particularly using spatially varying source positions, it is possible to append the matrix $\mathbf{p}_{j}$ with additional data points for a single reflector. True solutions will cluster around the same point in the Hough space, while outliers will receive less votes in the accumulator space. There are many robust evaluators available that dynamically remove contributions of backgrounds and analyze voting patterns around peaks in the accumulator space [furukawa]. However, when considering a single reflector in the Hough space, it is often sufficient in practice to estimate the single most voted bin to obtain $\hat{\mathbf{l}}_{\textrm{H}}$.