=Paper=
{{Paper
|id=Vol-1638/Paper46
|storemode=property
|title=Support subspaces method for fractal images recognition
|pdfUrl=https://ceur-ws.org/Vol-1638/Paper46.pdf
|volume=Vol-1638
|authors=Evgeny Yu. Minaev,Vladimir A. Fursov
}}
==Support subspaces method for fractal images recognition ==
https://ceur-ws.org/Vol-1638/Paper46.pdf
Image Processing, Geoinformatics and Information Security
SUPPORT SUBSPACES METHOD FOR FRACTAL
IMAGES RECOGNITION
E. Minaev, V. Fursov
Samara National Research University, Samara, Russia
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 pro-
posed 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, con-
junction index, binary and multiple classification.
Citation: Minaev E, Fursov V. Support subspaces method for fractal images
recognition. CEUR Workshop Proceedings, 2016; 1638: 379-385. DOI:
10.18287/1613-0073-2016-1638-379-385
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 se-
lecting 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 solv-
ing an optimisation problem, which often requires a large number of iterations and
Information Technology and Nanotechnology (ITNT-2016) 379
Image Processing, Geoinformatics and Information Security Minaev E, Fursov V…
significant computational resources. Perhaps this is why the SVM method is not wide-
ly 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 algo-
rithm 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 transfor-
mation parameters and error histogram, characterising the difference between indi-
vidual 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.
Description of the algorithm
Each fractal image is represented as a vector N 1 :
x x1 , x2 ,..., xN ,
T
(1)
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:
Xk x1 k , x2 k , ..., x j k ,..., xM k , k 1, K
(2)
and computed N N -matrix k - class:
1
Qk Xk XTk Xk XTk , k 1, K , (3)
Information Technology and Nanotechnology (ITNT-2016) 380
Image Processing, Geoinformatics and Information Security Minaev E, Fursov V…
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 , (4)
k 1, K
where Rk x j xTj Qk x j xTj x j ,
1
k 1, K . (5)
– 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 im-
ages have variations depending on the number of iterations in which they are re-
ceived. 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 avoid-
ing 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 calculat-
ing 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 "dis-
turbing" vectors from the initial set?
The following algorithm is implemented for the removal of linearly dependent vec-
tors. At each step, the vector x r is removed from the initial set of k class, if
j
j 1, M ,
Rk xr min Rk x j , (6)
where, as (2) R x x Q x x x .
1
T T
k j j k j j j
Experimental procedure
The experimental evaluations make use of the Moving and Stationary Target Acquisi-
tion 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,
Information Technology and Nanotechnology (ITNT-2016) 381
Image Processing, Geoinformatics and Information Security Minaev E, Fursov V…
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 non-
overlapping parts, named range blocks, and into larger square parts, named domain
blocks. There are two main approaches to shape analysis using IFS. They are com-
pression 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 decom-
pression and it is better to use rough regular dividing and a small set of transfor-
mations. This approach allows fast compression of different-sized images into a defi-
nite 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 pat-
terns (16×16) .
a) b) c)
d) e) f)
Fig. 1. Examples of original MSTAR images (a,b,c); corresponding fractal patterns (d,e,f)
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 recogni-
tion 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 ex-
clusion of the vectors from the support subspace can increase recognition rate.
Recognition rates obtained by constructed support subspaces within this condition
Information Technology and Nanotechnology (ITNT-2016) 382
Image Processing, Geoinformatics and Information Security Minaev E, Fursov V…
were compared with recognition rates obtained by support subspaces without exclud-
ing 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 exclud-
ing 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 subspac-
es method provides a significantly higher recognition rate for undistorted images. For
noised image support, the subspaces method provides a better recognition rate by 1-
3% than SVM.
Table 1. Recognition rate for two-class classification
PSNR pSVM p0 pоп nоп
Without 0,755 0,845 0,85 92
noise
28 dB 0,751 0,771 0,776 91
22 dB 0,714 0,72 0,737 93
18 dB 0,673 0,668 0,683 85
16 dB 0,651 0,634 0,648 87
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 with-
out excluding vectors.
Table 2. Recognition rate of support subspaces method without excluding vectors
BMP2 BTR70 T72 ZIL131 ZSU234
BMP2 0,741 0,152 0,091 0 0,016
BTR70 0,162 0,813 0,025 0 0
T72 0,097 0,035 0,757 0,057 0,054
ZIL131 0 0 0,034 0,829 0,137
ZSU234 0 0 0,093 0,114 0,793
Table 3 shows the recognition rate of the support subspaces method with excluding
vectors.
Thus, it is shown that the proposed method of construction support subspaces im-
proves the recognition rate with dimension reduction of the source data.
Information Technology and Nanotechnology (ITNT-2016) 383
Image Processing, Geoinformatics and Information Security Minaev E, Fursov V…
Table 3. Recognition rate of support subspaces method with excluding vectors
BMP2 BTR70 T72 ZIL131 ZSU234
BMP2 0,744 0,154 0,102 0 0
BTR70 0,16 0,82 0,02 0 0
T72 0,096 0,026 0,761 0,05 0,067
ZIL131 0 0 0,033 0,829 0,138
ZSU234 0 0 0,084 0,121 0,795
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, im-
proving the speed of the classification process. A proposed new computing algorithm
for the conjugation index allows for a reduction in requirements for computing capac-
ities 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 sys-
tem based on the fractal analysis. Computer Optics, 2012; 36(1): 124-130.
2. Minaev EY, Nikonorov AV. High accuracy pose reconstruction of passive colored mark-
er. Computer Optics, 2012; 36(4): 611-616.
3. Lisitsin SO, Baida OA. Road sign recognition using support vector machines and histo-
gram 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 Aero-
sols: 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 Diagno-
sis 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 Se-
curity (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 Recogni-
tion, 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 frac-
tal coding characters. Journal of Visual Communication and Image Representation, 2013;
24(1): 42-47.
Information Technology and Nanotechnology (ITNT-2016) 384
Image Processing, Geoinformatics and Information Security Minaev E, Fursov V…
10. Pi M, Li H. Fractal indexing with the joint statistical properties and its application in tex-
ture 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 conju-
gation indices and support subspaces. Computer Optics, 2015; 39(2): 255-264. DOI:
10.18287/0134-2452-2015-39-2-255-264.
Information Technology and Nanotechnology (ITNT-2016) 385