# Robust Fingerprint Minutiae Extraction and Matching Based on Improved SIFT Features
## 3 Proposed Methodology
### Minutiae Feature Extraction  
After finishing all the aforementioned preprocessing operations, the enhanced fingerprint image is obtained, in which the minutiae feature points can be easily located [1]. In this work, the robust minutiae feature points of the enhanced fingerprint image are determined by using an adaptive version of the SIFT detector [30] to obtain a sparse set of frames (or local keypoints) from the fingerprint image. The keypoints are viewed as oriented disks attached to blob-like structures of the fingerprint image under consideration [31]. As the image scales, rotates, and/or translates, these keypoints could help track image objects and thus the deformation. The effect of such deformation on the feature appearance is excluded by canonization, i.e., by mapping the keypoints to a canonical disk [32; 33; 34]. In order to search for fingerprint blobs on a multiple scale, the SIFT based detector constructs a scale space defined as a function \(F(x,\sigma)\) of spatial and scale variables, where \(x\in\mathbb{R}^{2}\) and \(\sigma\in\mathbb{R}_{+}\) are the spatial and scale coordinates, respectively. The domain of the scale-space variable \(\sigma\) is sampled at discretized steps in logarithmic values:  
\[\sigma(s,o)=\sigma_{0}2^{o+s/S},\;o\in\mathbb{Z},\;s=0,\ldots,S-1 \tag{2}\]  
where \(o\), \(s\), \(S\in\mathbb{N}\) and \(\sigma_{0}\in\mathbb{R}_{+}\) are the octave index, scale index, scale resolution and base scale offset, respectively. Notice that octaves of negative index are likely to be obtained. Then, a resolution defined as a function of the octave can be used for sampling the spatial coordinate \(x\) on a lattice, as follows:  
\[x=2^{o}x_{o},\qquad o\in\mathbb{Z},\quad x_{o}\in[0,\ldots,N_{o}-1]\times[0, \ldots,M_{o}-1] \tag{3}\]  
where \(x_{o}\) and \((N_{o},M_{o})\) denote the spatial index and spatial resolution of octave \(o\), respectively. The resolution of the octaves can be obtained from the resolution \((M_{0},N_{0})\) of the base octave \(o=0\), as follows:  
\[N_{o}=\lfloor\frac{N_{0}}{2^{o}}\rfloor,\qquad M_{o}=\lfloor\frac{M_{0}}{2^{o }}\rfloor \tag{4}\]  
However, some scale levels can be usefully stored twice across different octaves, by allowing the parameter \(s\) to be negative or larger than \(S\). More formally, let \([s_{\text{min}},s_{\text{max}}]\) and \([o_{\text{min}},o_{\text{min}}+O-1]\) be the ranges of \(s\) and \(o\), respectively, where \(O\) denotes the number of octaves. The SIFT detector and descriptor make use of two scale spaces, namely a Gaussian space and a Difference of Gaussian (DoG) space. The _Gaussian scale-space_ of an image \(I(x)\) can be obtained from the 'zero-scale' image by a Gaussian convolution:  
\[G(x,\sigma)\triangleq(g_{\sigma}*I)(x) \tag{5}\]  
where the scale \(\sigma\) is typically sampled a particular way to reduce redundancy. In practice, it is assumed that the fingerprint image is nominally pre-smoothed \(\sigma_{n}\), accordingly \(G(x,\sigma)=(g_{\sqrt{\sigma^{2}-\sigma_{n}^{2}}}*I)(x)\). As pointed out in [30], successive convolutions need to be performed by small Gaussian kernels to allow the pyramid to be incrementally computed. Another scale space that the detection algorithm makes use of is the _difference of Gaussians_ which is progressively calculated from the scale derivative of \(G(x,\sigma)\) along the scale coordinate \(\sigma\):  
\[D(x,\sigma(s,o))\triangleq G(x,\sigma(s+1,o))-G(x,\sigma(s,o)) \tag{6}\]  
For computing the octave \(o=-1\), the fingerprint image is enlarged by a factor of, e.g., 2 through bilinear interpolation (applied to the enlarged image \(\sigma_{n}=1\)). For scale space extrema detection at all scales, the DoG space possesses \(s\in[-1,S]\). As the DoG space is derived from the differentiation of the Gaussian scale space, the latter has a scale index in the range of \(s\in[-1,S+1]\). With regard to the parameter \(O\), it should be set as high as possible to cover all octaves.