SUPPORT SUBSPACES METHOD FOR FRACTAL IMAGES RECOGNITION

Abstract

This paper presents the recognition method of fractal images. The approach is considered based on using support subspaces. Support subspaces are constructed with vectors of source data using a conjunction index. The proposed new computing algorithm for the conjugation index reduces requirements for computing capacities and memory. It is shown that the proposed method of construction, supporting subspaces without vectors with stand-out conjunction index, improves recognition rate with dimension reduction of the source data.

Keywords

• digital image processing
• pattern recognition fractal images
• conjunction index
• binary and multiple classification

Introduction

In images analysis and pattern recognition, images are often represented as a vector whose components are the values of the pixels’ brightness. This approach is widely used in computer vision; in particular, for fractal image recognition [ 1 ]. Going from an ordinary image to the fractal representation is usually possible to significantly reduce the memory requirements for storing the original data, while preserving the quality of recognition [ 2 ]. For example, fractal representation of a 128 × 128 initial image has a size of 16 × 16, so the feature vector is reduced 64 times. However, the dimension of the vector that represents the fractal image remains sufficiently high at exactly 256 × 1.

However, in order to ensure the high quality of recognition, there are commonly-used methods in which recognition procedure is based on the source or even an extended feature space; for example, a support vector machine (SVM) [ 3 ]. The SVM method is now recognised by most researchers as the most effective in linear separability of classes. The kernel functions method can also be used for classification in the absence of the properties of linear separability. However, there are no regular methods of selecting the most appropriate kernel functions. Another problem of the method is that the support vectors are determined at the stage of its configuration, as a result of solving an optimisation problem, which often requires a large number of iterations and significant computational resources. Perhaps this is why the SVM method is not widely used in the recognition of fractal images. There are only [ 4 ], [ 5 ], dedicated to the recognition of fractals in the framework of the SVM approach.

The most widely recognised fractal images use the approach described in [ 6, 7 ], based on the properties of iterated function systems. There are different implementations of this approach; in particular, in [ 6 ], the classifier built on the nearest neighbour algorithm in [ 7 ] used the rate of convergence of the formation of fractals. In [ 8 ] the fractal images are formed of the features obtained by a Gabor wavelet transform. In [ 9 ] for comparison of fractal images, a statistical method based on kernel density estimation was used. [ 10 ] used a set of statistical fractal signatures that combine fractal transformation parameters and error histogram, characterising the difference between individual iterations of the formation of a fractal image. In [ 11 ] for the classification of fractal images calculated absolute values of the Pearson correlation coefficient. In [ 12 ] to improve the recognition quality in the construction of fractal images based on the method of quadtree.

In this paper, we propose an approach in which we develop the basic ideas of fractal recognition method on iterated function systems and SVM. We propose in [ 13 ] the method of support subspaces, which is adjacent to the SVM approach. The proposed approach builds on the previous work of the authors. In particular, [ 13 ] proposed a method of supporting planes, which then in [ 14 ] was generalised to multidimensional support subspaces.

In this case, we are developing in these papers [ 13-14 ], the method of forming support subspaces. In particular, we use a feature of fractal images forming technology to form a training set. Here we investigate recognition quality depending on the method for generating a support subspace and on the number of vectors included in it. Xk  x1 k , x2 k , ..., x j k ,..., xM k  , k  1, K and computed N  N -matrix k - class: Qk  Xk XTk Xk  1 T

Xk , k  1, K ,

Description of the algorithm

Each fractal image is represented as a vector N 1: x   x1, x2 ,..., xN T , where components are numerical values of luminance for N  W  H pixels, where W , H – size of image. Assuming that there are M different fractal images for each K object. The vectors corresponding to the fractal images of one object constitute a class. The set of vectors representing the fractal images of known classes forms the training set.

To construct the classifier we will use the approach described in the [ 4 ]. We assume that the M training vectors are given for each class, i.e. for each x j k , j  1, M , k  1, K composed – N  M -matrix: (1) (2) (3) which we, hereafter, call decision matrix.

At the stage of recognition, decision about vector x j belonging to the m - class is accepted, if Rm  x j   max Rk  x j  , k 1,K

1 where Rk  x j   xTj Qk x j  xTj x j  ,

k  1, K . – conjunction index of vector x j with each of the classes.

It is easy to notice that, in this method, the information on the classes contained in the matrices Qk k  1, K , is computed from matrices Xk  M  . In [ 4 ] for the formation of these matrices it is proposed to use a small number of training vectors, forming the so-called support subspace classes. In this paper, these vectors are selected from the training set by examining all possible options on the criterion of recognition quality. In fractal image recognition, a particular feature of the problem is that the fractal images have variations depending on the number of iterations in which they are received. Therefore, there is a problem of formation of support subspaces considering the feature of variance training vectors. In this paper, we investigate a scheme for constructing support subspaces, using this feature.

In contrast to the SVM method [ 13 ] and the algorithm described in [ 14 ], the support vectors and the support subspace fixed once at the initial phase of training, thus avoiding a large number of iterations to refine them, as occurs when setting up the support vector.

In this approach, we consider the problems of binary and multiple classification, the comparative results of experiments on the MSTAR data set. In this paper, we also deal with the reduction of the computational complexity of the algorithm for calculating conjunction index on the stage of recognition.

As noted above, in this case the main problem is the existence of almost identical vectors. The first issue to be discussed: what is the sequence of removing these "disturbing" vectors from the initial set? The following algorithm is implemented for the removal of linearly dependent vectors. At each step, the vector x r is removed from the initial set of k class, if Rk xr   min Rk x j , j j  1, M ,

1 where, as (2) Rk  x j   xTj Qk x j  xTj x j  .

Experimental procedure

The experimental evaluations make use of the Moving and Stationary Target Acquisition and Recognition (MSTAR) database. For our experiments, we used five target types (BMP2, BTR70, T72, ZIL131, ZSU234). For each type we used 100 images for the training set, and 100 images for testing recognition algorithms. For each image from training and testing sets, we get fractal pattern [ 1 ]. For fractal pattern computing, (5) (6) iterated function systems (IFS) based algorithm is used. The main idea of the IFS shape analysis algorithm is the following: input image is divided into square nonoverlapping parts, named range blocks, and into larger square parts, named domain blocks. There are two main approaches to shape analysis using IFS. They are compression and recognition algorithms. The compression IFS algorithm searches the best affine transformation from domain to range block for every range block. As a result, several affine transformations is coding input image. Using high precision dividing and a large set of affine transformations, we can obtain a decompressed image equal to the input image. The recognition algorithm does not need a high quality of decompression and it is better to use rough regular dividing and a small set of transformations. This approach allows fast compression of different-sized images into a definite set of transformations coefficients.

The aim of the compression stage is to find the best transformation and domain block for the range block. Therefore, we try to use each of these transformations to each domain block for each range block and compare the result with the input image block. So, we can find self-similar parts of the image. As a result, each input image is mapped to a fractal attractor obtained by iterating affine transformations. Fig. 1 shows examples of original MSTAR images (128×128) and their fractal patterns (16×16) . For evaluation of the proposed methods, two experiments were conducted. The first experiment tested the two-class recognition method (BMP2, T72). Support subspace was constructed for each class, excluding vectors from the original data by condition (6). The purpose of the experiment was to determine the dependence of the recognition rate by the exclusion of vectors. In this experiment, fractal patterns of original images were random noised with different amplitude. It was ascertained that the exclusion of the vectors from the support subspace can increase recognition rate. Recognition rates obtained by constructed support subspaces within this condition were compared with recognition rates obtained by support subspaces without excluding vectors.

Recognition rates are shown in Table 1. PSNR - peak signal-to-noise ratio(dB), pSVM p0 , pоп - recognition rates by SVM method, by support subspaces without excluding vectors and by support subspaces with excluding vectors, respectively, nоп number of vectors in support subspace. It was discovered that reducing the number of vectors in in support subspace (by 7- 15% depending on the noise), improved the recognition rate by 0.5-1 %. In comparison with the SVM method, a support subspaces method provides a significantly higher recognition rate for undistorted images. For noised image support, the subspaces method provides a better recognition rate by 13% than SVM. The second experiment tested multiclass recognition with five types of targets (BMP2, BTR70, T72, ZIL131, ZSU234). Original fractal patterns were noised with PSNR=28 dB. Table 2 shows the recognition rate of support subspaces method without excluding vectors.

Conclusion

It was discovered that support subspaces constructed without vectors, with stand-out conjunction index, improved the ecognition rate. Thus, support subspaces should include vector with an average conjunction index.

The proposed recognition method can reduce the dimension of the source data, improving the speed of the classification process. A proposed new computing algorithm for the conjugation index allows for a reduction in requirements for computing capacities and memory.

This work was supported by the Ministry of Education and Science of the Russian Federation.

References

1. Minaev EY , Nikonorov AV . Object detection and recognition in the driver assistance system based on the fractal analysis . Computer Optics , 2012 ; 36 ( 1 ): 124 - 130 .

2. Minaev EY , Nikonorov AV . High accuracy pose reconstruction of passive colored marker . Computer Optics , 2012 ; 36 ( 4 ): 611 - 616 .

3. Lisitsin SO , Baida OA . Road sign recognition using support vector machines and histogram of oriented gradients . Computer Optics , 2012 ; 36 ( 2 ): 289 - 295 .

4. Xi J , Zhao W , Yuan JE , Kim J , Si X , Xu X . Detecting Lung Diseases from Exhaled Aerosols: Non-Invasive Lung Diagnosis Using Fractal Analysis and SVM Classification . PLoS ONE , 2015 ; 10 ( 9 ): e0139511. doi: 10 .1371/journal.pone. 0139511 .

5. Tafraouti A , El Hassouni M , Toumi H , Lespessailles E , Jennane R . Osteoporosis Diagnosis Using Fractal Analysis and Support Vector Machine . In Signal-Image Technology and Internet-Based Systems (SITIS) . Tenth International Conference on IEEE , 2014 : 73 - 77 .

6. Liu Y , Sun JG . Face recognition method based on FLPP . In Electronic Commerce and Security (ISECS) . Third International Symposium on IEEE , 2010 : 298 - 301 .

7. Lasfar A , Mouline S , Aboutajdine D , Cherifi H . Content based retrieval in fractal coded image database , in: Proceedings of the 15th International Conference on Pattern Recognition , 2000 ; 1 : 1031 - 1034 .

8. Yang Y , Sun JG . Face recognition based on gabor feature extraction and fractal coding . In Electronic Commerce and Security (ISECS) . Third International Symposium on IEEE , 2010 : 302 - 306 .

9. Xiaoqing H , Qin Z , Wenbo L . A new method for image retrieval based on analyzing fractal coding characters . Journal of Visual Communication and Image Representation , 2013 ; 24 ( 1 ): 42 - 47 .

10. Pi M , Li H . Fractal indexing with the joint statistical properties and its application in texture image retrieval . Image Processing , IET , 2008 ; 2 ( 4 ): 218 - 230 .

11. Wang J , Lan X , Liu Y , Zheng N. Fractal image encoding with flexible classification sets . Chinese science bulletin , 2014 ; 59 ( 14 ): 1597 - 1606 .

12. Li H , Lu J , Yu J. An image retrieval method based on fractal image coding . In Systems and Informatics (ICSAI) . International Conference on IEEE, 2012 : 1866 - 1869 .

13. Zherdev DA , Kazanskiy NL , Fursov VA . Object recognition by the radar signatures of electromagnetic field scattering on base of support subspaces method . Computer Optics , 2014 ; 38 ( 3 ): 503 - 510 .

14. Fursov VA , Zherdev DA , Kazanskiy NL . Object recognition in radar images using conjugation indices and support subspaces . Computer Optics , 2015 ; 39 ( 2 ): 255 - 264 . DOI: 10 .18287/ 0134 -2452-2015-39-2- 255 -264.