# Dog Identification Method Based on Muzzle Pattern Image
## Materials and Methods
### Proposed Method
#### 3.2.3 Feature Extraction Algorithm  
The general-purpose feature extraction algorithms such as SIFT, SURF, BRISK, and ORB have been proven to be a suitable solution for object recognition. They each have their own strength. In order to find which algorithm is better for dog muzzle pattern recognition, SIFT, SURF, BRISK, and ORB were applied to the propose method to extract unique features from muzzle pattern images. The feature extraction algorithms consist of a keypoint detector and descriptor. The detector finds keypoints in an image and the descriptor makes information to describe corresponding keypoints. In the implementation of algorithms, the default values of OpenCV3.3 was used for all the parameters of the algorithms.  
SIFT is an algorithm that solves the problem of Harris corner technique, which is sensitive to scale change of image. SIFT creates different image scale spaces and finds the maximum corners as keypoints in the space with a Difference of Gaussian (DoG) detector (Figure 7). Equation (3) shows the convolution of DoG with image \"I(x,y)\". For each keypoint, a descriptor is calculated from the gradient magnitude and the relative orientation in the local neighborhood of pixels [22]. SIFT is robust to the scale change of the image, but it requires high computational cost [23].  
\[\mathrm{D(x,\ y,\ \sigma)}\ =\ (G(x,\ y,\ k\sigma)-G(x,\ y,\ \sigma))*I(x,\ y) \tag{3}\]  
where \"G\" represents the Gaussian function.  
Figure 6: Muzzle pattern image and histogram; (**a**) Original image; (**b**) CLAHE; (**c**) Proposed CLAHE.  
SURF is an algorithm that uses an integral image in the process of detecting key points and generating descriptors in order to reduce the number of computations [24]. SURF is similar to SIFT in that the angle for the dominant orientation is extracted from the detected keypoints and the gradient information is used as an expression vector in the subarea. SURF uses the Hessian matrix to find keypoints. Equation (4) represents the Hessian Matrix in point \"x = (x, y)\" at scale \"\(\sigma\)\".  
\[\mathrm{H}(\mathrm{x},\sigma)=\left[\begin{array}{cc}L_{xx}(x,\ \sigma)&L_{xy}(x,\ \sigma)\\ L_{yx}(x,\ \sigma)&L_{yy}(x,\ \sigma)\end{array}\right] \tag{4}\]  
where \"\(L_{xx}(x,\ \sigma)\)\" is the convolution of Gaussian second order derivative with the image \"\(1\)\" in point \"x\", and similarly for \"\(L_{xy}(x,\ \sigma)\)\" and \"\(L_{yy}(x,\ \sigma)\)\".  
ORB is an algorithm that combines the Features from Accelerated Segment Test (FAST) and Binary Robust Independent Elementary Features (BRIEF) algorithms [25]. FAST detects a key point by comparing the brightness value with the neighboring pixels within a certain radius (Figure 8a). BRIEF is binary descriptor that compares the intensity of two pixels at a statistical stochastic distance based on the central pixel. ORB is robust to the rotation of an image by adding the main direction angle of the keypoint to the binary descriptor.  
BRISK is another binary descriptor and it improves the concept of BRIEF. BRISK takes four concentric regions around a keypoint and divides them into arbitrary circular sampling zones according to Gaussian smoothing (Figure 8b). Then, the binary descriptor is constructed according to the brightness in all the divided circular zones [26]. FAST was used as the keypoint detector. BRISK with FAST is robust to the rotation and the scale change of an image.