Fast Aerial UAV Detection Based on Image Segmentation and HOG-FLD Feature Fusion

Image segmentation is a way to separate the image into regions with different characteristics and separate the interested objects from the background in the segmented blocks. Let interest objects and backgrounds in segmented regions show a clear sense of contrast based on human visual effects. Image segmentation method plays an important role in further analysis of image such as image compression and image recognition.

The image segmentation method based on graph theory (Graph-Based Image Segmentation) and the region merging method are selected to segment the image in this paper. The image segmentation method based on graph theory takes the image as the object transforming the image into the right undirected graph, and uses the connected branch method of graph [6] to segment the image, and then it could obtain the region block. The region merging method is to merge the segmented region blocks according to the specific merging rules. Because of great different characteristics of the UAV and the background in texture, color, size and degree of agreement, regional block of great different characteristics need to be decomposed and regional block of small different features need to be merged [11], which follows the principle of [10] the optimal segmentation.

The image contains information such as shape, size, color, texture and so on. Image will be segmented after the whole image is traversed by the search algorithm of graph theory. In the graph theory, the definition of the image - to - graph [12] is described as follows:

G = (V, E) is an undirected graph with V as its vertex and E as its edge set. Any edge (v_i, v_j) ∈ E is defined as a weight function W(v_i, v_j) greater than zero. Any vertex v_i, v_j, represents the pixel point of the graph to be processed in graph theory, and the weight of any edge represents the gray difference, the distance or some other features between the adjacent pixels of v_i, v_j and (v_i, v_j) in an image. Using Graph Cuts algorithm [7], the graph G is divided into several disjoint independent regions, and the region is defined as G′ = (V, E′), E′ is a subset of E. The regions of the picture is segmented by the algorithm of Minimun Spanning Tree(MST) [14] that the difference of the pixels in the same region is measured through the maximum weight edge, of which the largest weight edge of segmentation region values are defined as follows:(1)Int(C)=maxe∈MST(C,E)ω(e)(2)C∈V

Where C is the generated partition region, and MST(C, E) represents the set of partitioned regions or the Minimun Spanning Tree [17] that C generates in E.

The resulting dissimilarity between pixels within the segmented region could also be understood as the weight of the minimum edge that connects the vertices of two segmented regions, as defined below:(3)Dif(C1,C2)=minvi∈C1,vj∈C2,(vi,vj)∈EW((vi,vj))

When there is no edge connection between the two partitioned regions, there is Dif(C₁, C₂) = ∞. The condition for the appearance of its partition boundary is defined as follows:(4)D(C,C)={trueif,Dif(C1,C2)>MInt(C1,C2)falseotherwise

If true in the expression is satisfied, then the boundary is represented, then the region is segmented. otherwise, it is merged.

Where the smallest internal difference of division is defined as follows:(5)MInt(C1,C2)=min(Int(C1)+τ(C1),Int(C2)+τ(C2))

τ() is a threshold function, which is used to control the merging degree of the image segmentation region, which is defined as τ(C) = k/|C|, where C is the number of the segmentation region or the vertex, and k is a constant parameter that is used to control the coarse granularity of its image segmentation area. The segmentation effect is shown in Figure 1 (b). That small regions will be merged means detecting whether the segmented region meets the regional boundary conditions, if not, then they will be merged. The regional boundary conditions could be measured by the following four types of similarity in the image:

Figure 1.

Because the edge contour feature of UAV has strong stability and extensibility, the HOG feature with strong ability to describe contour is extracted from data set. However, because of the large dimension of HOG feature vector, it is unfavorable to the training of classifier. In order to train the classifier with good classification ability, it is necessary to reduce the dimension of extracted HOG feature by FLD [18] feature fusion and finally obtain the feature vector with small dimension. To sum up, the feature extraction based on HOG-FLD feature fusion is adopted in this article.

The basis of feature extraction in this article is to extract feature of gradient histogram of oriented gradient (HOG). The thought of algorithm is as follows: calculating the gradient of selected image; The whole image is divided into rectangular cells of fixed size and equal size, each cell has pixel including m × m the cell is divided into 9 undirected channels) or 18 directed channels, and the gradient histogram of each direction is voted on. The voting weight is the gradient value that has been calculated earlier. The divided cell units above are composed of fixed blocks of the same size. Each block contains n × n cell elements, which the local eigenvector corresponding to each block is normalized in order to reduce the effect of illumination on the results. The feature vectors of these blocks are combined to form the HOG feature vectors of the image.

The steps of extracting HOG feature are as follows: graying the positive sample image of UAV, filtering the input image with Gamma correction method so that the image could achieve the standard contrast of color space and reduce the effects of local shadows and light changes on the image; dividing the image into a certain number of cells, and forming a fixed number of cells into a certain number of blocks of equal size as in the preceding paragraph, classifying the gradient range according to the above mentioned rules, we could calculate the cell features in these blocks and finally connect all the blocks together to obtain the feature vector containing the whole target UAV image. Formula (11) is a formula for normalizing the image, formula (12) and formula (13) could calculate the gradient component of each pixel, formula (14) and formula (15) could calculate the size and direction of the gradient.

Where vg* is the result of histogram normalization, and v_g is the extracted vector histogram; pi_(x+1,y), pi_(x−1,y), pi_(x,y+1) and pi_(x,y−1) respectively denote the location of 4 pixel points; Gx(x,y) and Gy(x,y) respectively denote the coordinate position in the horizontal and vertical directions of the two pixels. And S(x,y), θ(x,y) respectively denote the length of the gradient direction vector and the angle of the gradient direction vector.

In this article, a window including 64 * 128 pixel is used to scan the sample image and the image to be detected using a window including 64 × 128 pixel. The scanning step size is 8 pixels (scanning is in horizontal and vertical direction). The window is divided into cells including 8 * 8 pixel and forms 8 * 16 = 128 units. Then setting up four adjacent units up and down to the left and right as a block of pixels, a window contains 105 blocks of pixels. A 3780 dimensional feature vector named HOG feature description value is generated in a window containing 105 pixel blocks according to the calculation steps of HOG. Its specific HOG algorithm is shown in Figure 2:

Figure 2.

On the basis of HOG feature, the linear subspace is constructed by using Fisher Linear Discriminant Analysis (FLD) [18]. By calculating the optimal projection matrix, the projection matrix for feature extraction of the training set is obtained, and the similarity of its projection vector is taken as the similarity degree S_cos of cosine similarity, which purpose is to reduce the intra-class dispersion S_W as much as possible and to increase the inter-class dispersion S_B as much as possible (or that is in the training concentration, to make the sample data of the same UAV as close as possible, and the sample data of different UAV to be far away). In this way, the features with classification ability are extracted. When dealing with a problem that type is c, the mathematical formulas of inter-class dispersion S_B and intra-class dispersion S_W should be defined as follows:(16)SB=∑i=1Ni(μi−μ)(μi−μ)T(17)SW=∑i=1c∑xk∈Ωi(xk−μi)(xk−μi)T

Where μ_i denotes the mean value of class Ω_i; μ means the mean value of total sample; N_i means the number of samples of class Ω_i. The optimal projection matrix W_opt could be obtained by solving the optimization problem such as formula (18), where S_W must be a nonsingular matrix (or that is the total number of training samples N is greater than the characteristic dimension of UAV image):(18)Wopt=argmaxW|WTSBW||WTSWW|

W_opt could also be obtained by solving the generalized eigenvalue problem such as the formula (19):(19)SBW=SWWΛ

In order to solve the problem that the intra-class dispersion matrix S_W is singular, PCA principal component analysis (PCA) is used to reduce the dimension of the feature space (dimensionality reduction to N-cu), and then Fisher linear discriminant analysis (FLD) is used to deal with it. The projection vector y of test sample x is obtained according to formula (20):(20)y=WoptTx

Cosine similarity S_cos is used as the similarity measure of projection vector y. Where the cosine similarity S_cos of vector A = {a₁,a₂,…,a_n} and B = {b₁,b₂,…,b_n} is defined as follows:(21)Scos=〈A,B〉‖A‖2‖B‖2=∑i=1naibi‖A‖2‖B‖2

Because the support vector machine (SVM) proposed by Vapnik has the advantages of simple system structure, global optimization, good generalization, and short training and prediction time [9], this paper uses SVM as a machine learning tool to calculate the rule of samples in order to achieve fast and efficient learning sample features and accurate classification purposes. The main idea of SVM is to deal with the linear inseparability of the original space by selecting the kernel function of Polynomial Kernel to correspond the data to the high-dimensional space. When the algorithm is used to realize the two-classification, the sample features such as HOG must be extracted from the original space first, and then the sample features in the original space are represented as a vector in the high-dimensional space. In order to minimize the error rate of the two class classification problems, we need to find a hyperplane that is used to divide the two classes in the high dimensional space.

Let the sample set be x_i, y_i, where i=1,2,...,N, x_i ∈ R^e, y_i ∈ {0,1} is the class identifier. Then in e dimensional space, its linear discriminant function is as follows:(22)g(x)=w⋅x+b

The formula of the classification surface equation is as follows:(23)w⋅x+b=0

After normalization of the discriminant function, the following conditions must be satisfied for the two types of samples:(24)g(x)≥1

The classification interval could be 2‖w‖, where the maximum requirement ||w|| for the classification interval is kept to a minimum, all samples must be correctly classified, and the following conditions must be met:(25)yi[(w⋅xi)+b]−1≥0

An SVM whose inner product function is maximum requirement k(x_i, x_j) is constructed with the following formulas (which can be understood as the formula for calculating the extreme value of a quadratic function with conditional constraints):(26)Q(a)=∑i=1Naiajyiyjk(xi,xj)

Its constraints are expressed as: 0≤ai≤C,∑i=1Naiyi=0

The formulas of the support vector machine that could be calculated are as follows:(27)f(x)=sgn(∑i=1Nai*yik(x,xi)+b*)

Among them, b* is a constant parameter, indicating the size of the threshold that needs to be classified.

In this article, 900 positive sample images and 900 negative sample images are selected, and 500 original images of positive samples are selected to calculate the aspect ratio of UAV. An image that aspect ratio is 1:2 is obtained, and the pixels are normalized to 256 * 512 to avoid the effect of image size on the recognition effect. As described in the HOG feature section above, each image could produce 105 pixel blocks, and each pixel block could obtain a 36-dimensional feature vector, so a image will finally produce a 3780 dimensional HOG feature vector. The extracted HOG vector is used as the input vector of Fisher linear discriminant analysis algorithm to reduce the dimension of the whole vector. The dimension of the vector is adjustable and its parameter is determined according to the recognition efficiency of the experiment. Sending the vector reduced dimension to the SVM model, the SVM classifier is obtained to detect whether the UAV is included in the image under test.

In the process of extracting feature vector, the dimension that needs to be reduced by Fisher linear discriminant analysis algorithm is the parameter k of FLD algorithm, which changes with the change of this parameter. The contrast graph of recognition time is shown in Figure 3. It can be seen from the graph that when k is 50, the whole algorithm has the least recognition time.

Figure 3.

Experiments show that in the whole algorithm, when the number of pixels in the divided blocks is 8*8, SVM kernel function type is 2, when the threshold of segmentation is k=90 and sigma=10, The algorithm has the best overall recognition effect on accuracy rate and time, and the recognition result is shown in Figure 4:

Figure 4.

In order to verify the efficiency of the proposed method, the experimental results of the proposed method are compared with the experimental results of the HOG and SVM method based on image segmentation, and the experimental results are obtained by statistics. As shown in TABLE I, and the average recognition time of this method is faster than that of the latter method.

TABLE I.