Abstract: In order to reduce the time of the process of feature description in SURF algorithm and improve the speed of SURF algorithm, an improved SURF algorithm based on image entropy is proposed. It uses image blocks in the overlap region of original images. Then the image entropy of each block is calculated to select reliable area. The reliable area is only used to detect feature points. The two methods (Uniform sampling and the distance constraint between feature points) are used to control the feature points number. The speed of SURF algorithm is increased by about 65% and the performance is also improved.
INTRODUCTION
Image mosaic technology is an important branch of computer vision areas and widely used in remote sensing image processing, the virtual reality technology, objects of 3D reconstruction technique (Liu et al., 2010; Brunet et al., 2011; Zhao et al., 2007; Zheng and Zhou, 2009). At present, methods based on the area (Zhang et al., 2004), based on the frequency domain (Kuglin and Hines, 1975; Zhang et al., 2011) and based on the features are the common registration methods which are often used. SIFT (Scale Invariant Feature Transformation) algorithm is a representative algorithm of feature detection. (Wang et al., 2011). The SIFT algorithm is adaptable, when the scale, rotation, projection of image changes, SIFT can well detect feature points. PCA-SIFT reduces the dimension of feature vector but the amount of calculation increases (Ke and Sukthankar, 2004). SURF (Speeded Up Robust Features) algorithm based on integral image was put forward by Bay et al. (2006), Simard et al. (1999) and Porikli (2005) which approximated Laplacian-Gaussian operator by square filters based on integral image and constructed a Fast-Hessian matrix. The SURF algorithm improved the detection speed but its performance was equal to SIFT algorithm.
According to the comparison and analysis above, in order to reduce the running time of the SURF algorithm, an improved SURF algorithm is proposed as follows:
| • | Limiting the area of feature point extraction. As shown by Fig. 1 |
| • | Use image entropy to estimate the spatial distribution of feature points |
| • | Use uniform sampling and the distance constraint between the feature points to select more reliable feature points |
By doing these above, the speed of SURF algorithm is accelerated and the performance is improved.
IMPROVED SURF ALGORITHM
Because the computation time of feature points description is proportional to the number of feature points. It need to find the more representative feature points. The direct algorithm complexity is O(n2). That means if there are too many feature points, feature points description and matching will consume a large amount of time.
| Fig. 1: | The overlap region of original images for feature point detection |
Projective transform-ation of image matching between two images can be expressed as:
| (1) |
In the formula: (x, y) and (x’, y’) are the coordinates of matching point in the two images. The 6 parameters can be determined by 3 non collinear image points. So, for image matching, too much matching points are without value. The important problem is the high quality of the matching points.
Get reliable area: Feature points are detected in the gray scale changing area, the edge and corner regions. In these areas, the gradient amplitude is bigger and the gray changes markedly. For the SURF algorithm, the descriptors are on the basis of the statistics of gradient information of pixel on a certain range of feature points around. Significance of descriptor vector determines the matching repeatability. When the range of value is large in each component, the distance between the descriptor vector is large. So, in order to get more significant feature descriptor, it need evaluate whether the gradient characteristics around the detected feature points is significant or not. Then it can decide feature points which can be further descripted.
For the gradient change sharply region, the texture will be very significant. Correlations are consistent between the two. So, the position of salient feature points can be estimated in the image through the measured texture. Here it use image entropy to roughly estimate the gradient change of image.
Entropy is a concept of the degree of disorder information in the information theory. Information is more disordered, entropy is greater. For gray level images, the image gray value changes larger, the entropy is greater. This also means that the image gradient information is abundant. Image entropy is defined as follows:
| (2) |
where, N is the total number of different gray value in the image pi. is the probability of pixel which the gray value is i. It can be approximated as the proportion of the number of pixels with same gray values in the total number of pixels:
| (3) |
where, fi is the number of pixel which the gray value is i . In order to get the entropy of the different regions, the image is divided into a plurality of the box with side length L. Image entropy of each block is calculated, thus the whole image entropy is represented in matrix form which is composed of the image entropy of each block. At the Gauss scale space, with the image scale becomes larger, the image will become more and more smooth and gradual and lose of its details, so that the entropy decreases as the scale becomes large.
Therefore, the area that the image entropy is lower, the possibility of producing candidate feature point is much lower. At the same time, feature descriptor vector which the area of lower entropy generated is lower significance than the region of greater entropy, because the value range of each component is small. Based on this conclusion, it can use a specific threshold to remove the region with its image entropy below it. It will reduce unnecessary calculation.
Classification of image entropy: The threshold is an important parameter. In order to determine its value, it uses the method of cluster to analyse the image entropy matrix. The image will be divided into 3 parts: the region with abundant texture, the region with common texture and the region with generally poor texture. Then the region with poor texture can be removed directly.
K-means clustering method is used to sort the image entropy matrix. The calculation steps are as follows:
| • | k initial sample are random selected for the original centroid of k class |
| • | According to the principle of Euclidean distance, the sample which is not the centroid is divided to the nearest class |
| • | Calculate the sample mean of new class as the centroid of the new class |
| • | Repeat second and third step until the centroid of k clusters have no change |
Here the value of k is 3, the maximal clustering entropy represents the area known as the A class. And the region of B class and C class represent the region with medium value of entropy and small value of entropy. The class C region has less amount of information, so it can be removed directly.
Limit the number of feature points: Too many feature points will consume more time to match. In order to get the high quality of the matching points and reduce the consumption of feature points description, two methods are used to control the number of feature points before describing them. They are uniform sampling and the distance constraint between the feature points.
Uniform sampling: Before describing the feature points, the SURF algorithm has got N feature points. Suppose that it only need M feature points, apparently, the sampling interval can be expressed as N/M . After all the initial feature point are sampled, it obtained the required M feature points, then the M feature points are only described.
The distance constraint between the feature points: First, randomly select a feature point Q from the set of feature points. Then set a circle with this point Q as the centre of the circle and the radius is R. If it detected other feature points A1, A2, A3, An in the circle region, it would remove these points (Fig. 2).
FEATURE POINTS MATCHING
Take one of the key points in images (a) and find two feature points in image (b) which were nearest in continental distance. In these two feature points, if the proportion of the nearest distance divided by the second nearest distance was less than a threshold (0.5-0.8), then this pair of match points was accepted.
| Fig. 2: | Schematic diagram of feature points distance constraint |
If this ratio threshold is reduced, the SURF matched number would be cut down but it would be more stable. To reduce the feature points detecting error, it often uses RANSAC (Fischler and Bolles, 1981) to filter the match results.
EXPERIMENT RESULTS
In order to test the performance of the improved SURF algorithm, It has been developed a MATLAB7.0 implementation on AMD Athlon(tm) || X2 220 Processor 2.79GHz CPU, 1.75GB RAM computer. To verify the perfor-mance of the algorithm. Three group of pictures were downloaded from internet as shown in Fig. 3a. Their size are all 400x300.
First, limit the area of the three group of images for detecting feature points. Second, divide feature detection area into blocks. After many repeated experiments, each r egion can be divided into 25 blocks and the size of each block is 80x60. Then calculate the entropy of each block and perform cluster analysis on the entropy. The feature detection region is divided into class A, B, C three area as said above. In the experiment, it chooses the class A to detect feature points. The results are shown in Fig. 3b. As you can see from Fig. 3b, the region with rich texture is preserved, other regions has been removed. So the more representative feature points are detected. But the number of feature points is still too much. So it need to limit the number of feature points. Two methods which described above are used to select feature points. And the results is shown in Fig. 3d. From Fig. 3d, it shows that the distribution of feature points become more uniform. And the number of feature points is greatly reduced. The comparison of the number is shown in Table 1. Figure 4 shows matching and mosaic results. It shows that the number of matching pairs is reduction in bulk. But the matching result is accurate.
| Fig. 3(a-d): | The results of feature point detection and the number of feature points control of each group, (a) Original onage, (b) Reliable area, (c) Detected feature points and (d) No. Control results |
| Fig. 4(a-b): | The results of feature points matching and image mosaic of three groups images, (a)Matching results and (b) The results of image mosaic |
| Table 1: | Comparison of the number of feature points before and after screening of each group |
| Table 2: | Comparison of feature points matching time of each group based on different conditions |
A: Feature points of the original image, B: Feature points after limit feature detection area, C: Feature points after image entropy cluster analysis, D: Feature points after uniform sampling, E: Feature points after limiting the distance between them |
|
So, it can save much time to calculate the image affine transformation matrix for the next step. And image mosaic effect is also better. At the same time, the matching time comparison is also given under different conditions as shown in Table 2. It can be seen from Table 2 that the improved SURF algorithm is faster than before. The speed of group 2 of images is increased nearly 80%. Other speed is increased by about 65%.
CONCLUSION
In order to further improve the speed of feature point detection. An improved SURF algorithm is proposed. A method based on image entropy that is used to choose the area for feature point detection is proposed. Improved SURF algorithm first limits the feature point detection region of the original images. On this basis, it get 25 blocks of the region and calculate image entropy of each block. Then it use K-means Cluster to analyse the entropy matrix. Get class A region of rich texture and use two methods to screen the feature points. Finally match these feature points. From the experimental results, the proposed method is simple and effective. The speed and performance of SURF algorithm is greatly improved. But there is a problem, if the image entropy of every block is similar, the effect of improved algorithm will be not very obvious. There are some uncertain-ties that the radius R is man-made by limiting the distance between the feature points. So, it need to use the improved SURF algorithm according to the actual situation of the image.
ACKNOWLEDGMENT
This work is supported by the national natural science funds under Grant No. 61272043, Chongqing fundamental and advanced research projects (cstc2013jj B40009) and the open subject of Chongqing Key Laboratory of Emergency Communication under Grant 2012.