Speeded-Up Robust Feature Matching Algorithm Based on Image Improvement Technology

Sharofiddin Allaberdiev^1*, Shokhrukh Yakhyoev², Rakhmatilla Fatkhullayev³, Jia Chen¹

¹Department of Mathematics and Computer Science, Wuhan Textile University, Wuhan, China.
²Department of Machine Science and Service, Tashkent Institute of Textile and Light Industry, Tashkent, Uzbekistan.
³Department of Information & Communication Engineering, Huazhong University of Science and Technology, Wuhan, China.

DOI: 10.4236/jcc.2019.712001                

Abstract

Due to requirements and necessities in digital image research, image matching is considered as a key, essential and complicating point especially for machine learning. According to its convenience and facility, the most applied algorithm for image feature point extraction and matching is Speeded-Up Robust Feature (SURF). The enhancement for scale invariant feature transform (SIFT) algorithm promotes the effectiveness of the algorithm as well as facilitates the possibility, while the application of the algorithm is being applied in a present time computer vision system. In this research work, the aim of SURF algorithm is to extract image features, and we have incorporated RANSAC algorithm to filter matching points. The images were juxtaposed and asserted experiments utilizing pertinent image improvement methods. The idea based on merging improvement technology through SURF algorithm is put forward to get better quality of feature points matching the efficiency and appropriate image improvement methods are adopted for different feature images which are compared and verified by experiments. Some results have been explained there which are the effects of lighting on the underexposed and overexposed images.

Keywords

Image Matching, SURF Algorithm, Features of an Image, RANSAC Algorithm

1. Introduction

Image matching is an important technology in image processing. Its purpose is to analyze and match the features, textures, contents and other factors of two or more images. Point feature matching is a basic method in image matching. Among them, the SIFT algorithm is a landmark algorithm in the field of feature point matching but the construction of 128-dimensional feature vectors by SIFT algorithm reduces the operation speed [1] [2] [3] [4].

The SURF algorithm is an improved SIFT algorithm which improves the matching rate and provides the possibility for the application of the algorithm in real-time of computer vision system [5].

Due to the problems of being photographed or the environment, there may be uneven brightness, low contrast, more noise and other situations which will bring inconvenience to the follow-up research. SURF feature matching works well when the light is good but it doesn’t match well when the light is insufficient or overexposed [6] [7]. Image improvement technology is used to preprocess the image so that the contrast between the object and the background in the image is stronger, highlighting a part of the image, making the details of this part more clear which is conducive to further observation and analysis [8] [9] [10]. Above this paper proposes the idea of combining image improvement technology with SURF algorithm by using different image improvement methods for processing in advance and through experimental verification, the SURF algorithm combined with image improvement technology improves feature extraction and matching [11] [12].

2. SURF Algorithm Principle

Compared with the SIFT algorithm, SURF algorithm is faster and more robust. Because the algorithm makes the corresponding simplification under the premise of ensuring the correct matching and uses the integral image many times at the same time because its calculation is simple and according to the integral image. It is easy to get the grey value of any rectangular region of the image which greatly improves the efficiency. Moreover, the Haar wavelet transform is used to increase robustness.

2.1. Extraction of Local Feature Points

2.1.1 Building Hessian Matrix

The Hessian matrix is constructed to generate stable edge points, which is the basis of feature extraction. An image f(x, y), whose Hessian matrix can be expressed as follows:

$H\left(f\left(x,y\right)\right)=\left[\begin{array}{cc}\frac{{\partial }^{2}f}{\partial x^2}& \frac{{\partial }^{2}f}{\partial x\partial y}\\ \frac{{\partial }^{2}f}{\partial y\partial x}& \frac{{\partial }^{2}f}{\partial y^2}\end{array}\right]$ (1)

The determinant of the Hessian matrix is also referred. Before constructing the matrix the image needs to be filtered by Gauss. The filtered Hessian matrix is

$H\left(x,\sigma \right)=\left[\begin{array}{cc}{L}_{xx}\left(x,\sigma \right)& L_{xy}\left(x,\sigma \right)\\ L_{xy}\left(x,\sigma \right)& L_{yy}\left(x,\sigma \right)\end{array}\right]$ (2)

The key points are located by the discriminant of Hessian matrix when the local maximum is obtained, it is determined that the current point is brighter or darker than other points in the surrounding neighbourhood.

2.1.2. Building Scale Space

To build image scale-space means to detect image features from different scales. At present, a better method is to build an image pyramid to describe an image in multiple scales. The traditional method uses the same group of upper images in the generated Gaussian pyramid to reduce the next layer, to obtain the Gaussian difference image. Depending on the upper results, the Gaussian template remains unchanged but changes the size of the image reducing the operation efficiency. In SURF we rely on the box filter instead of the Gaussian template, so we can only change the template size of the box filter without changing the size of the image.

Scale invariance improves the speed and accuracy of the algorithm. As shown in Figure 1.

2.1.3. Feature Point Positioning

This process is divided into three steps: selecting threshold, non-maximum suppression and interpolation. Firstly, the threshold value is selected to retain the strongest response value. If there is a larger threshold value, there would be more feature points. In the non-maximum suppression of formula, each pixel processed by Hessian matrix is compared with 8 neighbourhood pixels in the scale space and 9 neighbourhood pixels in the adjacent scale space with a total of 26 pixels are excluding the first and last layer images, as shown in Figure 2. Finally, through the Taylor series interpolation calculation, the key points are initially located. The key points of positioning error or energy difference are filtered out and then the stable feature points are screened out [6].

2.1.4. Main Direction Distribution of Feature Points

Haar wavelet features in the neighbourhood of feature points are used in SURF algorithm. We take the feature point as the centre, calculate the response of the circular area with a radius of 6s, and calculate the sum of the horizontal and vertical feature responses of all points in the 60˚ sector form a new vector traverse the entire circular area. Then, finally, take the longest new vector direction as the main direction of the feature point [7] as the process diagram is shown in Figure 3.

2.2. Generate Feature Point Descriptor

In SURF algorithm, 4 × 4 rectangular blocks are used near the feature points along the main direction. The Haar wavelet features of 25 pixels in each sub-region are calculated. These four values are the feature vectors of each sub-block area.

Figure 1. Pyramid structure.

Figure 2. Feature point positioning.

Figure 3. Main direction feature points.

So the SURF feature descriptor has a total of 64 dimension vectors which is 2 times smaller than the SIFT feature descriptor [8].

2.3. Feature Point Matching

The matching degree is determined by calculating the Euclidean distance between two feature points. According to the judgment of Hessian matrix trace, the shorter Euclidean distance is the better matching degree. If the matrix trace signs of the two feature points are the same, it means that the two features have a contrast change in the same direction. If they are different, it means that the contrast change direction of the two feature points is opposite even if the Euclidean distance is 0, they are directly excluded [9].

3. RANSAC Algorithm for Fine Matching

RANSAC algorithm points out that the effective data is called “internal” that is the distribution of the effective data can be explained by certain model parameters while the invalid data that cannot fit the model is called “external point”. Internal point data is used to estimate parameters to delete the inaccurate data. In this process, parameters need to be estimated iteratively. To improve the matching accuracy between SURF feature points, selecting the RANSAC algorithm is used to filter the matching points when the number of interior points is the most corresponding. Changing matrix is the best estimation, transformation matrix when corresponding interior points are matched point pairs after purification [10].

3.1. Image Improvement Algorithm

Image improvement refers to purposefully enhancing useful information, improving image quality and enhancing the effect. The processed image is more suitable than the original image. In this paper, gamma change histogram equalization and image sharpening are used to enhance the image and the case of underexposure or overexposure is used to verify the applicability of various methods.

3.2. Gamma Transform

Gamma transform can correct the image [11], which is suitable for underexposure or overexposure pictures and can enhance the contrast of the image. The formula of gamma transformation is as follows:

$s=c{r}^{\gamma }r\in \left[0,1\right]$ (3)

In general, the gamma transform is to expand the highlighted part of the dark part by changing the gamma value, to enhance the details of these parts. The gamma transformed graph is shown in Figure 4. When gamma > 1, the light grey stretch, the dark grey compression and the whole image darken.

When gamma is less than 1, the light grey compresses, the dark grey stretches and the whole image becomes bright.

3.3. Histogram Equalization

When the distribution of image grey value is too centralizes, histogram equalization

Figure 4. Input and output grey value relationship.

can make the probability distribution of image grey level uniform and make the histogram of the image as stable as possible. The transformation is as follows:

$s=T\left(r\right)$ (4)

The relation between the transformation function T(r) and the original probability density function is

$s=T\left(r\right)={\displaystyle \underset{0}{\overset{r}{\int }}{p}_r\left(r\right)\text{d}r}$ (5)

the discrete form is as follows:

$s_k=T\left(r_k\right){\displaystyle \underset{i=0}{\overset{k}{\sum }}\frac{n_j}{N}}={\displaystyle \underset{i=0}{\overset{k}{\sum }}{p}_r\left(r_j\right)}\left(0\le r\le 1,k=0,1,2,\cdots ,L-1\right)$ (6)

The equalization image is obtained by multiple transformations.

Image point noise refers to unnecessary or redundant interference information in the image which is represented by a series of isolated pixel areas that form a sudden change effect in the image, interfering with the observable information of the image. From the perspective of signal processing, image smoothing is to remove the high-frequency information and retain the low-frequency information to reduce the noise in the image.

3.4. Laplace Operator Method

The Laplacian operator is also called the second-order differential linear operator.

${\nabla }^{2}f=\frac{{\partial }^{2}f}{\partial x^2}+\frac{{\partial }^{2}f}{\partial y^2}$ (7)

The Laplace operator for image sharpening can be obtained by using the second-order partial differential approximation.

${\nabla }^{2}f=f\left(x+1,y\right)+f\left(x-1,y\right)+f\left(x,y+1\right)+f\left(x,y-1\right)-4f\left(x,y\right)$ (8)

The final sharpening formula is

$g\left(x,y\right)=f\left(x,y\right)+c\left[{\nabla }^{2}f\left(x,y\right)\right]$ (9)

3.5. Homomorphic Filtering

Homomorphic filtering adjusts the grey range in an image that enhances the image details of the dark area by eliminating the problem of uneven illumination on the image without losing image details of the bright area [12].

We use an image for its incident and reflected light components

$f\left(x,y\right)=i\left(x,y\right)r\left(x,y\right)$ (10)

This method uses the same filter to achieve the ideal control of the incident component and reflected component. The key is to select the appropriate H(x, y), which has different effects on the low-frequency and high-frequency components of the image. So, it is called homomorphic filtering as shown in Figure 5.

Figure 5. Filter function profile of homomorphic.

4. Experimental Results and Analysis

Under natural conditions, the light has a great influence on the collected image. Different light conditions may lead to insufficient or overexposure of the image which may affect the quality and bring inconvenience to subsequent matching research. Image improvement technology processes the image to improve the quality of the image. Therefore, different image improvement methods are used to improve the quality of the image. Image processing uses the improved SURF algorithm for feature matching and uses the number of feature points, matching points, running time to measure the advantages and disadvantages.

Firstly two underexposed images are selected for an experiment as shown in Figure 6, Figure 7 and Table 1.

Select 2 is overexposed images for the experiment as shown in Figure 8 and Table 2.

Through the above two groups, due to the influence of light, exposure quality was deficient. The following conclusions can be drawn from the image matching experiment of the notch:

1) Image preprocessing uses multiple image improvement methods. After that, the number of matching points and feature points in each group increased. Relatively, the matching effect of the original image is better than others.

2) For the first group of underexposed images effect of Laplacian, the processing is the most significant, an increase of matching points in histogram equalization feature points is less than other improvement effects, the effect of gamma transformation is worse than other methods and the parameters need to be adjusted appropriate brightness.

3) For the second group of overexposed images, Laplacian and homomorphic filtering do not affect. So, we choose two more appropriate methods for comparison among which gamma transform matching effect is better than histogram equalization.

4) Using various image improvement methods for preprocessing increases time consumption. How to improve the number of matching points and reduce the time consumption needs further study.

Figure 6. Original picture of light shortage.

(a) (b) (c) (d)

Figure 7. Image matching results of the light shortage. (a) Original image matching; (b) Gamma transform matching; (c) Laplacian operator matching; (d) Histogram equalization matching.

(a)(b)(c)

Figure 8. Overexposed image matching results. (a) Original matching; (b) Gamma Transform matching; (c) Histogram equalization matching.

Table 1. Underexposed image matching data.

Table 2. Overexposed image matching data.

5. Conclusion

With the development of society, image matching will be more and more widely used in various fields. SURF algorithm is an improvement of the SIFT algorithm. As a common image matching algorithm, it will still be the focus of research. When the image quality is affected by the light, the SURF matching effect would not be good. By combining the SURF algorithm with existing image improvement algorithm greatly improve the quantity and quality of feature point extraction. This paper introduced the basic theory of SURF algorithm and used the RANSAC algorithm. It filtered matching points and improves the matching accuracy by combining the SURF algorithm with existing image improvement algorithm. We wanted to improve the image quality; for that we first extracted and matched the feature points. The image matching effect has become better after proper method processing.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Chen, S.J., Zheng, S.Z., Xu, Z.G., Guo, C.C. and Ma, X.L. (2018) An Improved Image Matching Method Based on Surf Algorithm. International Archives of the Photogrammetry, Remote Sensing & Spatial Information Sciences, 42, 179-184. https://doi.org/10.5194/isprs-archives-XLII-3-179-2018
[2]	Zhu, L.L., Guo, Z., Teng, G.W., et al. (2019) CDVS Matching Algorithm Based on Image Improvement Processing Method (CN). Electronic Measurement Technology.
[3]	Hore, S., Chatterjee, S. and Chakraborty, S. (2017) Analysis of Different Feature Description Algorithm in Object Recognition. In: Information Resources Management Association, Ed., Analysis of Different Feature Description Algorithm in object Recognition, IGI Global, Hershey, 601-635. https://doi.org/10.4018/978-1-5225-5204-8.ch023
[4]	Nugraha, A.P., Wibowo, S.A. and Andini, N. (2018) Performance Analysis of Metric Threshold in SURF for Object Tracking. 2nd Symposium of Future Telecommunication and Technologies.
[5]	Deak, R. and Sterca, A. (2017) Improving SIFT for Image Feature Extraction. Studia Universitatis Babes-Bolyai, Informatica.
[6]	Ruan, J.X., Xie, L.Y., Ruan, Y.Y., Liu, L.D., Chen, Q. and Zhang, Q. (2018) Image Stitching Algorithm Based on SURF and Wavelet Transform. 7th International Conference on Digital Home, Guilin, 30 November-1 December 2018. https://doi.org/10.1109/ICDH.2018.00009
[7]	Liu, Y.L. and Ma, S.H. (2014) Research on Image Based on Improved SURF Feature Matching. 7th International Symposium on Computational Intelligence and Design.
[8]	Du, G., Su, F. and Cai, A.N. (2009) Face Recognition Using SURF Features. 6th International Symposium on Multispectral Image Processing and Pattern Recognition.
[9]	Yue, W. (2019) Research on Feature Point Extraction and Matching Machine Learning Method Based on Light Field Imaging. Neural Computing and Applications, 31, 8157-8169. https://doi.org/10.1007/s00521-018-3962-7
[10]	Feng, Y.P. and Li, S.G. (2018) Research on an Image Mosaic Algorithm Based on Improved ORB Feature Combined with SURF. Chinese Control and Decision Conference (CCDC), Shenyang, 9-11 June 2018. https://doi.org/10.1109/CCDC.2018.8407963
[11]	Sharma, N. and Verma, O.P. (2014) Gamma Correction Based Satellite Image Enhancement Using Singular Value Decomposition and Discrete Wavelet Transform. IEEE International Conference on Advanced Communications, Control and Computing Technologies, Ramanathapuram, 8-10 May 2014. https://doi.org/10.1109/ICACCCT.2014.7019306
[12]	Agarwal, T.K., Tiwari, M. and Lamba, S.S. (2014) Modified Histogram Based Contrast Enhancement Using Homomorphic Filtering for Medical Images. IEEE International Advance Computing Conference (IACC), Gurgaon, 21-22 February 2014. https://doi.org/10.1109/IAdCC.2014.6779453