# An Efficient System for Automatic Blood Type Determination Based on Image Matching Techniques
## 3 Overview of Image Matching Techniques
### Suf  
The speed-up robust feature (SURF) algorithm has mostly the same principles and steps of operation used in SIFT algorithm. The SURF has a faster convergence time and better performance results compared with the SIFT algorithm. The principle of the SURF algorithm operation is best illustrated by the flow chart shown in Figure 9. Its operation can be summarized by the following steps:  
**Step 1: Integral image generation**. SURF uses an integral image instead of the image itself for faster calculation of box type convolution filters and Haar wavelet features' responses. The integral image (also called the summed area table) at position \(X=(x,y)\) is the sum of all the values of the original image above and to the left of the pixel at location \(X\). \[I_{\Sigma}(X)=\sum_{j=1}^{j<=x}\sum_{j=1}^{j<=y}I(i,j) \tag{11}\]  
where \(I(i,j)\) is the original image and \(I_{\Sigma}(X)\) is the integral image [24]. Figure 8: Flow chart for the SIFT algorithm. Figure 9: Flow chart for the SURF algorithm. **Step 2: Keypoint detection using a fast-Hessian detector. ** A SURF detector differs from a SIFT detector; SURF uses fast Hessian instead of DoG. The Hessian matrix \(H(X,\sigma)\) of a given point \(X=(x,y)\) in the image \(I\) at scale \(\sigma\) is defined as follows:  
\[H(X,\sigma)= \begin{bmatrix}L_{xx}(X,\sigma)&L_{xy}(X,\sigma)\\ L_{yx}(X,\sigma)&L_{yy}(X,\sigma)\end{bmatrix}  \tag{12}\]  
where \(L_{xx}(X,\sigma)\) is the convolution of the Guassian second order derivative \(\frac{\partial^{2}}{\partial X^{2}}g(\sigma)\) with image \(I\) in point \(X\), and similarly, \(L_{xy}(X,\sigma)\),\(L_{yy}(X,\sigma)\). SURF approximates the second order derivatives using box filters and evaluates the image using integral images to speed calculations up [30]. The approximation of convolution results is denoted by \(D_{xx}\), \(D_{xy}\), and \(D_{xy}\). The determinant of the approximated Hessian matrix is calculated as  
\[Det(H_{approx})=D_{xx}D_{yy}-(0.9D_{xy})^{2} \tag{13}\]  
where the factor 0.9 is needed for energy conservation between the Gaussian kernels and the approximated Gaussian kernels [31]. SURF generates a scale-space image pyramid by convolving the image with an increasing size of the box filter. Each octave contains the convolution results with four upscaling box filters. Table 2 shows the parameters of the first three octaves. Note that the new parameter scale is \(s=\frac{size}{9}\times 1.2\). **Step 3: Keypoints localization. ** To localize the keypoints in the image with the accurate scale, the nonmaximum suppression method with a \(3\times 3\times 3\) neighborhood is applied [26]. If the point has maxima determinant of the Hessian matrix, then it is selected to be a keypoint. **Step 4: Keypoints orientation assignment using Haar wavelet. ** To get rotation invarience keypoints, SURF calculates Haar wavelet responses within a circular neighborhood of radius \(6s\) around the keypoint, where \(s\) is the determined scale of the keypoint. The responses in both the \(x\) direction (\(dx\)) and the \(y\) direction (\(dy\)) are calculated. Hence, integral images are used for fast filtering. The sum of \(x\) responses and \(y\) responses within every window of \(60^{\circ}\) is calculated to construct the orientation vector. The dominant orientation of the keypoint is assigned by the longest vector. **Step 5: Keypoints descriptors. ** SURF creates the keypoint descriptor again using Haar wavelets--this time, by creating a square region of size \(20s\) around the keypoint toward the assigned orientation. This region is then divided to \(4\times 4\) sectors. For each sector, Haar wavelet responses in both directions are calculated. Each sector will be presented by a vector \(v\) of length \(4\) that contains the sum of Haar wavelet responses in both the \(x\) and \(y\) directions, the sum of the absolute responses in both the \(x\) and \(y\) directions (\(v=\sum dx,\sum dy,\sum\mid dx\mid,\sum\mid dy\mid\)) [32]. The resulting SURF keypoint descriptor has a length of \(4\times 4\times 4=64\).