# CUDA and OpenMp Implementation of Boolean Matrix Product with Applications in Visual SLAM
## 5 Ultrametric-PAM and Ultrametric-FABMAP
To build a Chow-Liu tree in the training phase, we use the clustering centeroids and BoW representation of training images. Then, for each image in the test dataset, we select the corresponding BoW representation and calculate the new place likelihood. Using a motion model, we can either insert a new location or declare a loop closure detection. The confusion matrix is returned by this algorithm. Each (i,j) element in this matrix represents a binary value indicating whether or not images i and j are similar. We define several thresholds and calculate the accuracy and recall of the loop closure as follows:

\[accuracy=\frac{\sum\limits_{i}\sum\limits_{j}\left(\left(Confusion\ Matrix[i][j] \ >\ threshold\right)\ \wedge\ ground\ truth[i][j]==1\right)}{\sum\limits_{i}\sum\limits_{j}\left( Confusion\ Matrix[i][j]==1\ >\ threshold\right)} \tag{12}\]

\[recall=\frac{\sum\limits_{i}\sum\limits_{j}\left(\left( Confusion\ Matrix[i][j]\ >\ threshold\right)\ \wedge\ ground\ truth[i][j]==1\right)}{\sum\limits_{i}\sum\limits_{j} ground\ truth[i][j]==1} \tag{13}\]

Figure 11's rows and columns both represent images, and the value of the heatmap for parts (a) and (b) is the cosine similarity between the image's TF-IDF representations. For parts (c) and (d), it is a binary confusion matrix value returned by the FABMAP algorithm, where 1 indicates that two images are similar and zero indicates that they are not. The brighter the points in the confusion matrix, the more similar the corresponding images are. \begin{table}
\begin{tabular}{c c c c c} \hline \multirow{2}{*}{**Dataset**} & \multicolumn{2}{c}{**No,**} & \multirow{2}{*}{**Method**} & \multirow{2}{*}{**Acc**} & \multirow{2}{*}{**Recall**} \\  & **Extracted** & & & \\  & **Features** & & & \\ \hline
**Train/Test** & **Train/Test** & — & — & — \\ \hline Newer & 11,208 & Ultrametric & \%57 & \%93 \\ College & & FABMAP & \%62 & \%84 \\ One Loop & & & \%66.1 & \%81.66 \\ (Train) & & Ultrametric & Ground & Ground \\ Newer & & BoW & Truth & Truth \\ College & 6736 & FABMAP2 & \%51 & \%92.9 \\ Three loops & & & \%61 & \%83 \\ (Test) & & BoW & \%63 & \%100 \\ \hline \end{tabular}
\end{table} 
Table 7: Comparison of FABMAP2, Ultrametric-FABMAP and BOW considering Ultrametric-BoW as our ground truth (Training and testing data are swapped according to Table 5). To determine whether we needed to use OpenMP/AVX-256 or a GPU implementation with the following specifications, we compared the speeds of Algorithms 2 and 3. Table 8 shows that using the CUDA C implementation as our base method, OpenMP/AVX-56 improves transformation speed by 50% over CUDA implementation. Experiments are carried out on a Lenovo ThinkCenter i5, 8500, which has a total of six 3.00 GHz cores and six threads. To achieve the greatest possible speedup, we chose 20 OpenMp threads. In contrast, we used a Geforce 710 GT GPU with 192 CUDA cores and a total of 2 GB of memory. It is also worth noting that this is the cost of one iteration of the algorithm, and we have set the algorithm to not exceed 500 multiplications. We compared the speed of clustering in both cases to demonstrate that Ultrametric-PAM is superior for clustering, not only in terms of clustering compactness, NMI, SSE, and Donn index, but also in terms of speed. Table 9 shows that if we use a comparatively hierarchical distance matrix, we can speed up the PAM clustering algorithm up to 1254 times faster. Figure 11: (**a**) Newer College dataset (three loops), (**b**) Portion of New College dataset (one loop) (Ultrametric-BoW), (**c**) Newer College dataset (three loops), (**d**) Portion of New College dataset) (one loop (Ultrametric-FABMAP). \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset-Size** & **Method** & **Time** & **Speedup** \\ \hline
6736 \(\times\) 6736 & AVX-256 & 1 min 6 s & 1.51 \\
6736 \(\times\) 6736 & GPU & 1 min 39 s & 1. \\ \hline \hline \end{tabular}
\end{table} 
Table 8: OpenMP/AVX-256 Implementation vs. GPU speed up.