# Robust Fingerprint Minutiae Extraction and Matching Based on Improved SIFT Features
## 3 Proposed Methodology
### Minutiae Feature Extraction
Thus, keypoints are extracted by picking local-extremum points in3D neighborhoods of \(D(x,\sigma)\), where the extrema are efficiently selected by looking at \(9\times 9\times 9\) neighborhoods of samples. Since the octave is represented by a 3D array, the index \(k\) is mapped to scale space indexes \((x_{1},x_{2},s)\), as follows:  
\[k-1=x_{2}+x_{1}M_{o}+(s-s_{\text{min}})M_{o}N_{o} \tag{7}\]  
The index \(k\) can alternatively be mapped to a subscript \((i,j,l)\) by using:  
\[x_{1}=j-1,\qquad x_{2}=i-1,\qquad s=l-1+s_{\text{min}} \tag{8}\]  
The actual size of a spatial bin is \(m\sigma\), where \(\sigma\) is the scale of the keypoint, and \(m=3.0\) is a nominal factor (see Figure 6). Due to the way such extrema are detected, the following inequality constraints are strictly satisfied: \(1\leq x_{2}\leq M_{o}-2\), \(1\leq x_{1}\leq N_{o}-2\) and \(s_{\text{min}}+1\leq s\leq s_{\text{max}}-1\). As the interest is in both local maxima and minima, the process is then repeated for \(-G(x,\sigma)\). For sub-pixel refinement, a test with a threshold on the intensity \(D(x,\sigma)\) is simultaneously applied on the peakedness of the extremum to exclude weak points and/or edge points (see Figure 7). Figure 6: SIFT descriptor layout for \(4\times 4\) sub-regions. Figure 7: SIFT minutiae detection for various threshold values: (**a**) source image and detected frames at threshold values of (**b**) 5.0, (**c**) 7.5, and (**d**) 10.0. The orientation \(\theta\) of a detected keypoint \((x,\sigma)\) is obtained as a predominant orientation of the gradient around the keypoint calculated as a quadratically interpolated maximum of the histogram of gradient orientations \(\angle\
abla G(x_{1},x_{2},\sigma)\) around the keypoint. The histogram is then weighted by the magnitude of the gradient \(|\
abla G(x_{1},x_{2},\sigma)|\), using a Gaussian window of standard deviation \(1.5\sigma\) centered on the keypoint. After arranging data in bins, a moving average filter is applied to smooth the constructed histogram before computing the maximum. Besides the global maximum, there is also a need to retain all the local maximum of a value over 0.8% of the maximum. Hence, multiple SIFT frames would be obtained for each location and scale. Two examples of SIFT keypoint detection are shown in Figure 8 below. The SIFT descriptor of a detected keypoint \((x,\sigma)\) is a local statistic of gradient orientations of \(G(\cdot,\sigma)\), which is computed from a weighted 3D histogram of gradient orientations. More formally, the SIFT descriptor is expressed as a weighted and interpolated histogram of the gradient orientations and locations within a patch around the keypoint, where the histogram domain is represented in tuples: \((x,\theta)\in\mathbb{R}^{2}\times\mathbb{R}/\mathbb{Z}\). Moreover, the bins constitute a 3D lattice with \(N_{p}=4\) spatial bins along each spatial direction, \(N_{o}=8\) bins for the gradient orientation and a total of \(N_{p}^{2}N_{o}=128\) components. The window \(H(x)\) is a Gaussian with a deviation of \(N_{p}/2\), i.e., half of the spatial bin range. For invariance purposes, the histogram is then projected on the image domain, based on the local reference frame around the keypoint. The spatial dimensions are then multiplied by a factor of \(m\sigma\), where \(m\) and \(\sigma\) are a nominal factor (set to 3.0 by default) and the scale of the keypoint, respectively. The layout is rotated as well to ensure that \(x_{1}\) is aligned to the keypoint orientation \(\theta\). The resultant histograms are further weighted by the gradient modulus, and the contributions of their gradient orientations are smoothly distributed using a trilinear interpolation into adjacent histogram bins to avoid boundary effects in which the descriptor changes abruptly as a sample orientation shifts smoothly from one bin to another. Figure 8: SIFT minutiae feature detection (**a**) original image, (**b**) binary image, (**c**) thinned image, and (**d**) detected SIFT minutiae keypoints (pixels shown in green color).