# A Fingerprint-Based Verification Framework Using Harris and SURF Feature Detection Algorithms
## 3 Proposed Methodology
### Speeded Up Robust Feature (SURF) Algorithm  
The key idea of the SURF detection algorithm is to detect points of interest (i.e., keypoints) such as corners or blob-like structures from an image in the places where the determinant of the Hessian matrix has a maximum value [26]. While the detector locates the keypoints, the descriptor describes the features of these keypoints and constructs the feature vectors of the detected keypoints [27]. The steps of the SURF algorithm contain three tasks, namely, keypoint detecting, keypoint describing, and keypoint matching. In the first step, given a fingerprint image, the keypoints can be detected based on the determinant of the Hessian matrix. Formally speaking, in a given image I, the Hessian matrix \(H(x,\sigma)\) can be defined at a point \(x\) and scale \(\sigma\), as follows:  
\[H(x,\sigma)= \begin{bmatrix}L_{xx}(x,\sigma)&L_{yy}(x,\sigma)\\ L_{yy}(x,\sigma)&L_{yy}(x,\sigma)\end{bmatrix}  \tag{15}\]  
where,  
\[L_{xx}(x,\sigma)=I(x)*\frac{\partial^{2}}{\partial x^{2}}g(\sigma),L_{xy}(x, \sigma)=I(x)*\frac{\partial^{2}}{\partial xy}g(\sigma),L_{yy}(x,\sigma)=I(x)* \frac{\partial^{2}}{\partial y^{2}}g(\sigma)\]  
where \(L_{xx}(x,\sigma)\) is the convolution of the image with the second derivative of the Gaussian, \(g(\sigma)\) at scale \(\sigma\). Figure 7 shows the weighted box filter approximations of discretized second order Gaussian derivatives in the y and xy-directions. Using integral images in the calculation of Hessian approximation can greatly reduce the computation time of key points detection. The SURF algorithm can effectively use scale-space analysis of an image to identify the scale-invariant keypoints by using box filters in pyramid mode instead of measuring the approximations for second-order Gaussian derivatives of integral images at different scale values (\(\sigma\)). The box filter begins as an initial scale layer with a (\(9\times 9\)) size filter and the scale value is s = 1.2, which corresponds to the estimated Gaussian derivative with scale value \(\sigma\) = 1.2, and so forth for the remaining filter sizes. When the determinant of Hessian approximation is obtained at each layer, in a \(3\times 3\) neighborhood, the non-maxima suppression (NMS) technique can be used to locate the keypoints over an image scale. For achieving a good approximation, the determinant is weighted to exclude keypoints having low contrast or points lying on edges or being near to edges:  
\[det(H_{approx})=D_{xx}D_{yy}-(\omega D_{xy})^{2} \tag{16}\]  
where \(D_{yy}\) and \(D_{xy}\) are the approximated and discrete kernels for \(L_{yy}\) and \(L_{xy}\), respectively. The \(\omega\) term is theoretically sensitive to scale, but it can be assumed almost constant at 0.9. The extraction stage, also called the feature descriptor, aims to build a descriptor for every detected pixel in the image from the neighborhood information using vector space representation. In feature description, for generating SURF descriptors, two steps are typically required. The first is to determine the orientation for every detected feature by convolving the feature pixel into its neighborhood with the vertical and horizontal Haar wavelet filters. To make the detected points invariant to rotation, Haar wavelet responses are measured in both x and y orientation in the circular neighborhood of radius \(6\sigma\) around the interesting point, where \(\sigma\) is the scale at which the point is detected. The orientation of the dominant is then determined by measuring all responses summation in the sliding orientation window and the longest vector is chosen as the dominant orientation. The second step involves constructing a keypoint descriptor. For extracting a descriptor for every selected point, a square region of size \(20\sigma\) centered around the keypoint and oriented along with the orientation selected in the previous step.