# Robust Fingerprint Minutiae Extraction and Matching Based on Improved SIFT Features
## 3 Proposed Methodology
### Minutiae Feature Matching  
From the above description of the feature extraction module, it is evident that the SIFT algorithm can generally be seen as a local image operator that takes a given image and transforms it into a large collection of local feature vectors. Hence, the feature matching procedure between feature descriptors of two fingerprint images essentially involves computing the Euclidean distance between each descriptor of the first image and each descriptor of the second image in Euclidean space [35]. To use this local operator for fingerprint recognition purposes, it is applied on two fingerprint images, i.e., a test and template image. To find corresponding features between the two images, which could lead to fingerprint recognition, several feature matching approaches can be applied. Based on the Nearest Neighborhood (NN) procedure, for each feature \(a_{i}\) in the feature set of the query fingerprint image, the entire reference database is queried to find the most similar stored feature \(b_{i}\) with the smallest Euclidean distance to the feature \(a_{i}\). A pair of corresponding features \((a_{i},b_{i})\) is typically termed a match \(M(a_{i},b_{i})\)[36]. To check if this match is positive or negative, a certain predefined threshold is considered. For matching, when the ratio of the Euclidean distance of the nearest-neighbor to the Euclidean distance of the next nearest-neighbor exceeds the predefined threshold, the matched feature is rejected. On the other hand, if the Euclidean distance between two feature vectors \(a_{i}\) and \(b_{i}\) does not exceed the value of the threshold, the match \(M(a_{i},b_{i})\) is labelled as positive and stored as a valid match. As shown in [30], Euclidean distance refers to the distance of keypoints in the feature space. The keypoints (i.e., features) in image space are transformed into a multi-dimensional space based on their characteristics such as gradients, orientations, magnitude, locations and brightness, where each feature is represented by a feature vector. Then, the Euclidean distance between the two feature vectors \(\mathbf{a}\) and \(\mathbf{b}\) is defined as:  
\[D(\mathbf{a},\mathbf{b})=\sqrt{(a_{1}-b_{1})^{2}+(a_{2}-b_{2})^{2}+\ldots+(a_{ n}-b_{n})^{2}}=\sqrt{\sum_{i=1}^{n}(a_{i}-b_{i})^{2}} \tag{9}\]  
where \(n\) denotes the number of features in the feature set. The value of \(D(\mathbf{a},\mathbf{b})\) is then compared with a predefined threshold. If it is greater than the threshold, the matched keypoint will be discarded. However, the computation of the pairwise Euclidean distances between all feature points can be prohibitively expensive. As a result, it is very useful, especially for computational purposes, to find inner products of vectors in the feature spaces [37]. This will greatly reduce the computational burden and, in the meantime, retain the feature robustness. As the distance between feature vectors is probably going to be similar, mismatch might take place, but the angle is constantly different [38]. On the other hand, cosine similarity that measures the similarity between two vectors in the feature space can be obtained by the cosine of the angle between the two vectors. Formally, having computed the inner product of a pair of feature vectors, then it is straightforward to compute the inverse cosine between each pair of feature vectors as follows:  
\[\mathbf{a}\cdot\mathbf{b} = \sum_{i=1}^{n}a_{i}b_{i}=a_{1}b_{1}+a_{2}b_{2}+\ldots+a_{n}b_{n}\] \[\theta = \arccos\bigg{(}\frac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{a}\| \|\mathbf{b}\|}\bigg{)} \tag{10}\]  
Then, the nearest neighbor is checked to see if it has an angle below the predefined threshold ratio, i.e., \(\theta<\tau_{\theta}\). It is worth mentioning that, in the original SIFT matching algorithm, only the nearest neighbor distance is compared against other distances and the smallest distance value is selected, whereas, in this improved SIFT matching algorithm, angles between feature vectors are compared.