## 3 Fast Hyperbolic Hough Transform
### Fast HHT  
The basic idea behind the F-HHT is similar to that of the fast HT [45]: instead of calculating the transform on a dense grid, a hierarchical approach is utilized. First, a search with a large grid size is performed. In the next round, the search is focused on \"promising\" areas, now with smaller grid size. The process is iteratively repeated until the required accuracy (i.e., grid size) is achieved. The main novelty is the utilization of two metrics: the exact value of the HHT at a given point and the upper bound of the HHT in the vicinity of this point. This approach allows fast and provable convergence to the global maximum of the HHT. The search space is divided into rectangular tiles with grid points at the centers of the tiles, as shown in Figure 3. In the first round, the tile size is \(D_{1}\); in the second round, \"promising\" tiles are divided into four smaller tiles of size \(D_{2}=D_{1}/2\). In general, in the \(n\)-th round, the tile size is reduced to  
\[D_{n}=\frac{D_{1}}{2^{n-1}}. \tag{13}\]  
To ensure that the global optimum is found, the F-HHT utilizes two metrics at each grid point \((x,y)\). The first is the exact value \(A(x,y)\), according to (11), while the second is the upper bound \(\overline{A}(x,y)\) of the HHT in the actual tile surrounding \((x,y)\). Consider a tile of size \(D_{n}\) with center \(P=(x,y)\), as shown in Figure 4. The difference of distances \(PS_{i}=d_{i}\) and \(PS_{1}=d_{1}\) is \(d_{i,1}\), according to (8). Let \(P^{\prime}\) be an arbitrary point inside the tile, where \(P^{\prime}S_{1}=d^{\prime}_{1}\), \(P^{\prime}S_{i}=d^{\prime}_{i^{\prime}}\) and \(d^{\prime}_{i,1}=d^{\prime}_{i}-d^{\prime}_{1}\). \[ \begin{split} d^{\prime}_{i,1}-d_{i,1}=\\ \left(d^{\prime}_{i}-d^{\prime}_{1}\right)-\left(d_{i}-d_{1} \right)=\left(d^{\prime}_{i}-d_{i}\right)-\left(d^{\prime}_{1}-d_{1}\right) \end{split}  \tag{14}\]  
Figure 4: The derivation of the upper bound in a tile of center \(P\) and size \(D_{n}\). Figure 3: Hierarchical calculation of the HHT. Red and grey circles indicate centers of promising and unpromising tiles, respectively. Grey squares are the tiles. (**a**) Start of iteration step \(n\), (**b**) after the pruning in iteration step \(n\), (**c**) start of iteration step \(n+1\). From the triangle inequality applied to \(S_{i}PP^{\prime}\), it follows that \(-PP^{\prime}\leq d_{i}^{\prime}-d_{i}\leq PP^{\prime}\). Since \(PP^{\prime}\leq\frac{D_{n}}{\sqrt{2}}\), the following inequity holds, for all \(i\):  
\[-\frac{D_{n}}{\sqrt{2}}\leq d_{i}^{\prime}-d_{i}\leq\frac{D_{n}}{\sqrt{2}}. \tag{15}\]  
From (14) and (15), the following inequality follows:  
\[-\sqrt{2}D_{n}\leq d_{i,1}^{\prime}-d_{i,1}\leq\sqrt{2}D_{n}. \tag{16}\]  
The likelihood function at any point \(P^{\prime}\) in the tile is  
\[\mathcal{L}_{n}\left(P^{\prime}\middle|\widetilde{d}_{i,1}\right)=\frac{1}{N -1}e^{-\frac{1}{2}\left(\frac{d_{i,1}-d_{i,1}^{\prime}}{\sigma_{i,1}^{2}} \right)^{2}}. \tag{17}\]  
Since  
\[\left|\widetilde{d}_{i,1}-d_{i,1}^{\prime}\right|=\left|\left(\widetilde{d}_ {i,1}-d_{i,1}\right)-\left(d_{i,1}^{\prime}-d_{i,1}\right)\right|, \tag{18}\]  
using the reverse triangle theorem, it follows that  
\[\left|\widetilde{d}_{i,1}-d_{i,1}^{\prime}\right|\geq\left|\left|\widetilde{ d}_{i,1}-d_{i,1}\right|-\left|d_{i,1}^{\prime}-d_{i,1}\right|\right|. \tag{19}\]  
Let us denote  
\[\Delta d_{i,1}=\left|\widetilde{d}_{i,1}-d_{i,1}\right|. \tag{20}\]  
If \(\Delta d_{i,1}>\sqrt{2}D_{n}\) then, using (16), the inequity (19) can be rewritten as  
\[\left|\widetilde{d}_{i,1}-d_{i,1}^{\prime}\right|\geq\Delta d_{i,1}-\sqrt{2 }D_{n}, \tag{21}\]  
otherwise it is certainly true that  
\[\left|\widetilde{d}_{i,1}-d_{i,1}^{\prime}\right|\geq 0. \tag{22}\]  
Notice that \(\mathcal{L}_{n}\left(P^{\prime}\middle|\widetilde{d}_{i,1}\right)\) in (17) increases if \(\left|\widetilde{d}_{i,1}-d_{i,1}^{\prime}\right|\) decreases.