## 4 The Proposed Method
### Fast Descriptor Matching  
Feature matching aims to measure the similarity between the two feature descriptors. The float-type descriptors, such as SIFT, SURF et al. usually use Euclidean distance (L2 distance) to measure the similarity of two feature descriptors [11]. For binary descriptors such as BRISK [37] and LGHD [72], the Hamming distance is used [43]. Because our descriptor is hybrid type that not only includes float-type elements, but also contains binary-type ones. Thus, we use two metrics to measure the similarity of the proposed feature descriptors, namely Hamming distance and Euclidean distance as shown in Figure 5.  
The former is utilized to measure similarity of superpixel-based feature descriptors, then the latter is exploited to handle float-type feature descriptors. For the given two binary-type descriptors,  
Figure 4: Flowchart of joint keypoint computing. Figure 5: Flowchart of descriptor matching. \(DB_{r}=\left\{d_{r}^{1},\cdots,d_{r}^{m}\right\}\), \(D_{Bq}=\left\{d_{q}^{1},\cdots,d_{q}^{m}\right\}\), then the similarity between \(DB_{r}\) and \(DB_{q}\) can be calculated by the simple bitwise operation. \[\text{MS}_{q,r}=DB_{r}\;xor\;DB_{q} \tag{17}\]  
where \(xor\) denotes XOR operation which returns the number of different elements between \(DB_{r}\) and \(DB_{q}\). However, for float-type feature descriptor, \(DF_{q}=\left\{q_{1},\cdots,q_{m}\right\}\) and \(DF_{r}=\left\{r_{1},\cdots,r_{m}\right\}\), we use the Euclidean distance (L2 normal) to estimate the similarity of them, the matching confidence can be calculated as  
\[C_{qr}=\left\|\text{p}(q_{i})-\text{p}(r_{i})\right\|\text{, }i\in[1,m] \tag{18}\]  
where \(\text{p}(q_{i})\) and \(\text{p}(r_{i})\) denote the descriptor for keypoint \(q_{i}\) and keypoint \(r_{i}\) respectively. Once, the metrics are defined, we can simply loop the above procedure until the feature descriptors in the feature database is processed over, then every feature descriptor in query feature database has two potentially corresponding candidates. Let \(\text{p}(r_{i})\) and \(\text{p}\big{(}r_{j}\big{)}\) denote the candidates with respect to the query descriptor \(\text{p}(q_{i})\), then we can judge whether the matching is successful by the following formula. \[C_{f}=\frac{\left\|\text{p}(q_{i})-\text{p}(r_{i})\right\|}{\left\|\text{p}( q_{i})-\text{p}\big{(}r_{j})\right\|} \tag{19}\]  
If \(\text{c}<0.7\), the \(\left\langle q_{i},r_{j}\right\rangle\) is a correct match. Base on the hybrid matching approach, we can use the Brute-Force-Match (BFM) [73] to find a candidate for each query keypoint. However, BFM-based KNN approach is a greedy algorithm and has an expensive computational cost. If the matching method is utilized in large-scale 3D reconstruction, then the process of recovering 3D model is very slow. Thus, we must improve the computation efficiency of BFM-based KNN to accelerate the feature tracking method. After a deep investigation in descriptor matching methods [74; 75], we found that local sensitive hash (LSH) [51; 76] is an efficient approach to achieve descriptor matching. Thus, the LSH is utilized to match feature descriptors. The core of LSH algorithm is an approximate approach to compute k-nearest neighbors, which use \(N\) hash functions \(h_{1}(\cdot),\cdots,h_{N}(\cdot)\) to transform the D-dimensional space \(R^{D}\) into a lattice space \(L^{D}\), and the original each data is distributed into one lattice cell:  
\[H(v)=\left\{h_{1}(v),\cdots,(v)\right\} \tag{20}\]  
where \(v\) denotes a vector of query descriptor. To this end, the LSH-based KNN can use the L2 distance to measure the similarity between the query descriptor and the reference descriptor. ``` input: image sequences, \(I=\left\{l_{1},I_{2},\cdots,I_{N}\right\}\). Output: a set of matching pairs, \(S=\left\{\left\langle k_{ij},k_{hc}\right\rangle\right|_{i}^{\prime},h\in[1,N]\right\}\). Step1: Compute keypoints for each image in \(\left\{l_{1},I_{2},\cdots,I_{N}\right\}\), then resulting in a set of keypoints, \(\left\{k_{1},k_{2},\cdots,k_{m}\right\}\).