## 3 Fast Hyperbolic Hough Transform
### Hyperbolic Hough Transform  
To provide location estimates from TDOA measurements, an HHT was proposed in [31]. Now a simpler, and physically more interpretable, version is introduced. Figure 1: (**a**) Measurement scenario with emitter \(E\) and sensors \(S_{i}\); (**b**) estimation process. Let us define a grid where the emitter location is searched for. Using (4), the likelihood of the emitter being at grid position \((x,y)\), given a measurement \(\widetilde{d}_{i,1}\), is the following:  
\[\mathcal{L}(x,y|\widetilde{d}_{i,1})=\frac{1}{\sqrt{2\pi}\sigma_{i,1}}e^{-2 \left(\frac{\widetilde{d}_{i,1}-d_{i,1}(x,y)}{\sigma_{i,1}}\right)^{2}}, \tag{7}\]  
where \(\widetilde{d}_{i,1}\) is the measured distance difference between sensors \(S_{i}\) and \(S_{1}\), according to (6), and \(d_{i,1}(x,y)\) is the exact distance difference at point \((x,y)\), as follows:  
\[d_{i,1}(x,y)=d_{i}(x,y)-d_{1}(x,y) \tag{8}\]  
and  
\[d_{i}(x,y)=\sqrt{\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}+z_{i}^{2}}. \tag{9}\]  
The HHT uses a voting system, where a pair of sensors casts a vote to each of the grid points: a high/low vote represents a high/low likelihood of the emitter being at the given grid point. In the voting process, the normalized version \(\mathcal{L}_{n}\) of likelihood function (7) is utilized, where the maximum value of each vote is \(\frac{1}{N-1}\):  
\[\mathcal{L}_{n}\left(x,y\left|\widetilde{d}_{i,1}\right)=\frac{1}{N-1}e^{- \left(\frac{\widetilde{d}_{i,1}-d_{i,1}(x,y)}{\sigma_{i,1}}\right)^{2}}. \tag{10}\]  
Thus, the HHT value at grid position \((x,y)\) is the following:  
\[A(x,y)=\sum_{i=2}^{N}\mathcal{L}_{n}\left(x,y\left|\widetilde{d}_{i,1}\right. \right). \tag{11}\]  
The highest attainable value of \(A(x,y)\) is 1; this occurs when all the sensor pairs vote with their maximum possible value. If the measurement error is zero, i.e., \(n_{i}=0,\ i=1,\ 2,\ \dots,\ N\), then at the true source position \(A(x_{0},y_{0})=1\). In practical scenarios, where measurement noise is present, \(A(x_{0},y_{0})\) is lower than, but close to 1. The position estimate is at the maximum of \(A(x,y)\) :  
\[\left(\widetilde{x}_{0},\widetilde{y}_{0}\right)=\underset{(x,y)}{\mathrm{ argmax}}A(x,y). \tag{12}\]  
The HHT is illustrated in Figure 2, where four sensors are used, with \(S_{1}\) serving as the reference. The sensors in the example are placed on the plane of the source. The sensor positions are the same, but the source is placed in different positions in Figure 2a,b. In this scenario, 3 pairs of sensors vote: darker points indicate higher votes (white corresponds to zero and black corresponds to one). The result of votes of sensor pair \((S_{i},\ S_{1})\) is denoted by \(H_{i,1}\), forming a hyperbola in Figure 2. The image corresponds well to the well-known two-dimensional geometric interpretation: \(\mathcal{L}_{n}\) is maximal when \(\widetilde{d}_{i,1}=d_{i,1}(x,y)\), where \(d_{i,1}(x,y)\) is the difference of distances \(d_{i}\) and \(d_{1}\), as shown in (8). Thus, the set of points where \(\mathcal{L}_{n}\) is maximal forms a hyperbola with focal points at \(S_{i}\) and \(S_{1}\) and a major axis of \(\widetilde{d}_{i,1}\). The sum of all votes is maximal where the hyperbolas intersect, providing the location estimate (the darkest point). Note that the width of the hyperbola depends on both the accuracy of measurements, i.e., \(\sigma_{i,1}\), and the geometric dilution of precision (GDOP) [46]. The higher \(\sigma_{i,1}\), the wider the likelihood function, and thus the hyperbola, as follows from (10). High GDOP makes the hyperbola even wider, particularly noticeable for \(H_{2,1}\) in Figure 2b: \(H_{2,1}\) is narrow in proximity to \(S_{2}\) and becomes wider at the top of the figure. The GDOP naturally effects the accumulated HHT and, consequently, the position estimate: in Figure 2a, the small dark area around the location estimate indicates good GDOP, resulting in high confidence in the location estimate. In Figure 2b, however, the dark area is significantly larger, forming an ellipsoid-like pattern.