# An Efficient System for Automatic Blood Type Determination Based on Image Matching Techniques
## 3 Overview of Image Matching Techniques
### Sift  
The scale invariant feature transform (SIFT) algorithm takes an image and transforms it into a large collection of local features' vectors. Each of these features' vectors is invariant to any scaling or rotation of the image. The SIFT algorithm is distinctive where individual features can be matched for a large database of objects. SIFT provides many features for even small objects. The principle of operation of the SIFT algorithm is illustrated by the flow chart shown in Figure 8. The principle of operation of the algorithm is summarized by the following steps:  
**Step 1: Scale space extrema detection using DoG. ** The first step to extract image keypoints is to identify candidate key points and the locations at different space scales using variable-scale Gaussian kernel \(G(x,y,\sigma)\), which is convoluted with the input image \(I(x,y)\) to produce the scale space of an image \(L(x,y,\sigma)\), as in Equation (1)  
\[L(x,y,\sigma)=G(x,y,\sigma)*I(x,y) \tag{1}\]  
where \(*\) is the convolution operation. All scales must be examined to identify the scale invariant feature. SIFT uses a difference of Gaussian method (DoG) function, which is  
Figure 7: Samples with different agglutination patterns. defined as \(D(x,y,\sigma)\), to detect efficient key points' locations by computing the difference of two nearby scales separated by a constant multiplicative factor \(k\)[23], as in Equation (2),  
\[D(x,y,\sigma)=(G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)=L(x,y,k\sigma)-L(x,y,\sigma) \tag{2}\]  
A group of scaled images is called an octave. To ensure that the same numbers of DoG images are generated per octave, each octave corresponds to doubling the value of \(\sigma\), and the value of \(K\) is selected. Each pixel in a DoG image is compared to its eight neighbors at the same scale, and the nine corresponding neighbors at neighboring scales. The pixel will be selected as a keypoint if it is a local maximum or minimum among the (26) pixels surrounded. **Step 2: Keypoints localization. ** Too many keypoints will be generated by extrema detection; some of those keypoints are unstable. The next step aims to eliminate low contrast candidates and poorly localized candidates along edges. This is accomplished using a Taylor series expansion of DoG, \(D\)[26]:  
\[D(X)=D+\frac{\partial D^{T}}{\partial X}+\frac{1}{2}X^{T}\frac{\partial^{2}D }{\partial X^{2}} \tag{3}\]  
where  
\[X=(x,y,\sigma) \tag{4}\]  
The maxima or minima location is determined by Equation (5),  
\[\hat{X}=-\frac{\partial^{2}D^{-1}}{\partial X^{2}}\frac{\partial D}{\partial X} \tag{5}\]  
The keypoint is acceptable if \(|D(\hat{X})|\) is above a threshold value. To ignore candidates along edges, Hessian matrix \(H\) is computed at the location and the keypoints are scaled. \(H\) is given by Equation (6),  
\[H= \begin{bmatrix}D_{xx}&D_{xy}\\ D_{yx}&D_{yy}\end{bmatrix}  \tag{6}\]  
The eigenvalues \(\lambda_{1},\lambda_{2}\) of \(H\) are computed and used to detect corners and reject keypoints edges. However, eigenvalues are not explicitly computed; instead, trace and determinants of \(H\) are used [27]:  
\[T_{r}(H)=D_{xx}+D_{yy}=\lambda_{1}+\lambda_{2} \tag{7}\]  
\[Det(H)=D_{xx}D_{yy}-D_{xy}{}^{2}=\lambda_{1}\lambda_{2} \tag{8}\]  
where keypoints for which the ratio between \(T_{r}(H)^{2}/Det(H)\) is greater than a threshold are neglected. **Step 3: Keypoints orientation assignment. ** This step is important to get rotation invariant keypoints. To assign rotation or more for each candidate, the magnitude and direction of \(L\) (smoothed image) at each scale of keypoint \((x,y,\sigma)\) is calculated [28] using Equations (9) and (10),  
\[m(x,y)=\sqrt{L_{1}^{2}+L_{2}^{2}} \tag{9}\]  
\[\theta(x,y)=\arctan L_{2}/L_{1} \tag{10}\]  
where, \(L_{1}=L(x+1,y,\sigma)-L(x-1,y,\sigma)\) and \(L_{2}=L(x,y+1,\sigma)-L(x,y-1,\sigma)\). A weighted direction histogram for the neighborhood pixels of the keypoint is then created using 36 bins to cover 360\({}^{\circ}\) (10\({}^{\circ}\) for each bin).