=Paper=
{{Paper
|id=Vol-1901/paper3
|storemode=property
|title=Anomalies detection on spatially inhomogeneous polyzonal images
|pdfUrl=https://ceur-ws.org/Vol-1901/paper3.pdf
|volume=Vol-1901
|authors=Nikita A. Andriyanov,Konstantin K. Vasiliev,Vitaliy E. Dementiev
}}
==Anomalies detection on spatially inhomogeneous polyzonal images ==
https://ceur-ws.org/Vol-1901/paper3.pdf
Anomalies detection on spatially inhomogeneous polyzonal images
N.A. Andriyanov1, K.K. Vasiliev1, V.E. Dementiev1
1
Ulyanovsk State Technical University, Severniy Venets street, 32, 432027, Ulyanovsk, Russia
Abstract
The text deals with the problem of detecting anomalies on a background of multi-dimensional images. We synthesized a detection algorithm
based on the use of doubly stochastic models of random fields and which requires pre-filtering the image. We propose to use the modified
Kalman filter. We also investigated an efficiency of extended signals detection on real images. It is shown that the resulting algorithm has a
higher efficiency than the known algorithms which based on the traditional autoregressive image description. The gain is explained by more
adequate description of the real inhomogeneous material using doubly stochastic models.
Keywords: doubly stochastic models; random fields; anomalies detection; image filtering; Kalman filter
1. Introduction
The tasks of detecting and estimating the parameters of anomalies in images are of interest for a number of applications.
Among them, we can distinguish radio and sonar systems with spatial antenna arrays, aerospace systems for global Earth
monitoring, systems of technical vision, etc. For these systems [1-3] the description of signals and interference is realized by
means of random functions of several variables, i.e., by multidimensional random fields (RF). Typical examples of the use of
such RF are the tasks of describing and processing the results of multispectral (up to 10 spectral ranges) and hyperspectral (up to
300 ranges) surveys of earth surface areas. It is necessary, on the one hand, to consider aerospace observations as a single
multidimensional aggregate, and on the other hand, to take into account a number of characteristic features of satellite images,
for example, a pronounced spatial heterogeneity. Among the tasks of such images processing, the problem of detecting
anomalies occupies a special place [4-7]. The examples of such anomalies can be foci of fires, the flare of the starting rocket,
polynyas on the ice, shoals of fish in the ocean, etc. At the same time, the background for detection are sequences of polyzonal
images, i.e. images of the territory at different times in different spectral ranges. In this paper, the results of synthesis and
analysis of algorithms for detecting anomalies on polyzonal satellite images are presented.
2. A brief overview of detecting anomalies algorithms
Typically, statistical algorithms for detecting signals (Bayes, Neumann-Pearson) are often used in detection problems, but
they require a sufficient amount of a priori information. Nevertheless, the development of statistical algorithms is an actual task.
First, for such algorithms, it is possible to use various mathematical models of images. Secondly, the analysis of the
effectiveness of such algorithms can be studied both theoretically and experimentally. The algorithms [7] differing in their
approaches to the detection of "anomalies" and algorithms based on various image models have been proposed relatively
recently. There are following algorithms: the algorithm of spatial-spectral mismatch, in which the image is described by the
stationary RF model, the adaptive spectral mismatch algorithm, where the "anomaly" value is determined by the authors, as an
error in the representation of the pixel through its neighborhood, and the probabilistic algorithm for detecting anomalies using
images signatures quantization. It should be noted that the comparison of the work of algorithms in the work was carried out
only with the standard RXD-algorithm.
Another option in anomalies detection task is the detection of anomalies on multidimensional grids using wavelet transform
[5]. This method refers to methods with pre-processing, so with its use it is possible to increase the performance of anomaly
detection. However, it is difficult to use an algorithm with preliminary discrete wavelet transform when solving real-time
anomaly detection problems.
Recently, topological tools have been used to process hyperspectral images, along with ideas from network theory. A
standard RX (I. S. Reed, X. Yu) algorithm was proposed. It is based on the calculation of standard deviations of pixels from the
mean value in the multidimensional sense. However, it works well only on simple images, such as a large forest, but not on
complex urban scenes. Usually algorithms with transition to abbreviated description, local algorithms or algorithms with
preliminary segmentation [4] are used for complex images processing.
In our investigation, we will consider an anomaly as an a priori defined and observed object on a polyzonal image. We note
that within the framework of this work the signal parameters (its values and location) will be considered known. Otherwise, it
would be necessary to conduct a preliminary classification of the anomalies to determine the possible signal levels, and also to
search for such anomalies not in a specific region, but throughout the entire image.
3rd International conference “Information Technology and Nanotechnology 2017” 10
Image Processing, Geoinformation Technology and Information Security / N.A. Andriyanov, K.K. Vasiliev, V.E. Dementiev
3. Algorithms for filtering and detecting anomalies against a background of doubly stochastic random fields
Let's imagine a polyzonal image as a collection of data sets. Then we have a polyzonal image consisting of N components,
z , k 1...N , i 1...M , j 1...M , which are obtained as a result of spatial discretization of signals received from various sensor
ijk 1 2
systems. When the useful signal is absent (hypothesis H0) the model of observations can be represented by an additive mixture:
zijk xijk ijk , (i, j ) G k , k 1...N ,
of RF xijk with zero mean and given correlation function (CF) B( ml ) M xij , xi m, j l and spatial white noise ijk with zero
kt k t
mathematical expectation and variance in an area G, where the appearance of a signal is considered impossible for all
2
components of the image.
If there is a useful signal (hypothesis Н1) the model of observation s is written in the form:
zijk xijk sijk ijk , (i, j ) G0k , k 1...N ,
zijk xijk ijk , (i, j ) G0k , k 1...N ,
k
where G0 is the area at the k-th component of the image, in which we can wait the appearance of a useful signal with known
levels sijk , (i, j ) G0 . To simplify the calculations, we assume that on each of the components this area has the same form:
k
G0k G0 . And also we shall assume that the region G0 is known in advance.
The general solution of the detection problem is based on the construction of the modified likelihood ratio [3]:
wzijk H 1 ,
L
wzijk H 0
and comparison to the threshold value. A decision is made in favor of the hypothesis of the existence of a useful signal or a
hypothesis about its absence. And the decision is based on the results of the comparison.
Proceeding from the central limit theorem, let us approximate the conditional probability distribution densities wzijk H 1
and wzijk H 0 by Gaussian [2,3,8-10]:
z m z1 2 , z m z 0 2 ,
wz H 1 wz H 0
1 1
exp exp
2 z1 2 z1
2
2 z 0 2 z20
where mz1 and mz 0 are mathematical expectations of observations {z ijk } in the presence of a useful signal and in its absence,
respectively; z1 and z 0 are variations of observations {zijk} in the presence of a useful signal and in its absence, respectively.
2 2
So the optimal signal detection rule can be written in the form [3]:
T L signal presence,
L s V1 z xˆ 0
L0 signal absence,
where V is a diagonal matrix with values , s is extended signal with known characteristics, L0 is a threshold that can be
2
found based on a given false alarm probability.
For the case of the absence of a useful signal, estimates x̂ are optimal linear estimates in the usual sense of the minimum of
variance of errors, based on all available observations {zijk } . If there is a signal, the x̂ values obtained aren’t optimal estimates.
It should be considered as a pseudo-evaluation containing in its composition a transformed input signal s .
Thus, the best detection procedure involves the optimal filtration of the RF, the calculation of the covariance matrix of the
filtering errors, and the execution of the weighted summation in accordance with the indicated formulas. The most complex of
these steps is the filtration of the RF. This is due to the fact that real satellite imagery has a pronounced spatial heterogeneity.
Using standard optimal linear filters for such images leads to significant errors. The solution to this problem is possible due to
the use of special filters that take into account the complex nature of the images. Consider the synthesis of such filters for the
case where correlation between individual components of a polyzonal image can be ignored. In this case, the processing of the
image component can be carried out independently of one another. The conducted studies [11-13] show that to form such filters
it is possible to use doubly stochastic image models, which allow describing inhomogeneous signals [14]. As an example,
consider the following model [8]:
3rd International conference “Information Technology and Nanotechnology 2017” 11
Image Processing, Geoinformation Technology and Information Security / N.A. Andriyanov, K.K. Vasiliev, V.E. Dementiev
xijk 2 xij xi 1, j ,k 2 yij xi , j 1,k 4 xij yij xi 1, j 1,k xij
2
xi 2, j ,k yij
2
xi , j 2,k
2 xij
2
yij xi 2, j 1,k 2 yij
2
xij xi 1, j 2,k xij
2
yij
2
xi 2, j 2,k bij ijk
(1)
where xijk is simulated RF with normal distribution M {xijk } 0 , M {x } ; ijk is RF of independent standard Gaussian
2 2
ijk x
random values M {ijk} 0 , M { ijk } 1 ; xij and yij are correlation coefficients of the model with multiple roots of the
2 2
characteristic equations of multiplicity (2,2) [3]; bij is a scale factor of the modeled RF.
Random values xij and yij with a Gaussian probability distribution density can be described by the following autoregressive
equations:
~xij r1x ~x ( i 1) j r2 x ~xi ( j 1) r1x r2 x ~x ( i 1)( j 1) x
(1 r12x )(1 r22x ) ij ,
x
~yij r1 y ~y ( i 1) j r2 y ~yi ( j 1) r1 y r2 y ~y ( i 1)( j 1) y
(1 r )(1 r ) ij ,
2
1y
2
2y y
(2)
xij ~xij m , x
yij ~ yij m , y
~
where r1x M {~xij ~x ( i 1) j } , r2 x M {~xij ~xi ( j 1) } are correlation coefficients of a random parameter xij ; r1 y M {~yij ~y ( i 1) j } ,
r2 y M {~yij ~yi ( j 1) } are correlation coefficients of a random parameter ~yij ; ij and ij are Gaussian random values with
x y
M { ij } M { ij } 0 , M { 2 ij } M { 2 ij } 2 1.
x y x y
Note that model (1) with parameters (2) imitates inhomogeneous images [14], which allows us to recommend it for
describing real satellite images. In this case, we can use vector (row by row) nonlinear Kalman filter to reduce the noise [11,
12]. To do this, we combine the elements of the image line into a vector xi xi1 , xi 2 , , xiN . Then the model of a individual
T
component of the image can be written in the form:
xi diag( xi ) xi1 xi , yi i , xi r1x x (i1) x xi , yi r1 y y (i 1) y yi ,
where diag xi is diagonal matrix with elements xi on the main diagonal; lower-triangular matrix is the matrix, which is
determined by the decomposition of the covariance matrix: Vx .
T
The process of row by row estimation is described by a nonlinear Kalman filter:
xi
1
Vn zi xˆэpi , x pi xi ( x ( i 1) xi 1 ) ( x ( i 1) , y ( i 1) ) i ,
T
xˆ pi xˆэpi Pi
x pi
( , x) yi
where xэpi x p ( i 1) , ( x i , P is covariance filter error matrix.
p ( i 1) ) r1 x x ( i 1)
,
p
i
r i xi
1 y y ( i 1) yi
The use of this algorithm is possible under the condition of precisely known characteristics of the information RF. So we
need to know coefficients r1x , r2 x , r1 y , r2 y , and also parameters 0 x , 0 y and x , y , x . Otherwise, a preliminary evaluation of
2 2 2
these parameters is necessary. For this, pseudo-gradient procedures [13,15] can be used, as well as expressions for CF of doubly
stochastic RF models [14].
4. Results of the investigation of the efficiency of detection of signals on real images
Let's compare two detectors of anomalies constructed on the basis of a doubly stochastic model (Algorithm 1) and on the
basis of the usual autoregressive model [2] (Algorithm 2). In this case, the detection will be performed on real images obtained
from the LandSat-8 satellite. Studies are conducted for three images. We choose 4 areas for each image, where an anomaly may
occur. It should be noted that the areas are selected based on the structure of the images to be examined, taking into account the
greater and smaller heterogeneity, and the detection procedures are performed not for the entire image, but only for these areas.
Fig. 1a-1c show examples of images with signals located in different parts of the images, and also reflect the probabilities of
correct detection obtained using two algorithms. The sizes of all images are 250x250. The images are distorted by white
Gaussian noise with a single dispersion. The size of the square is 4x4, the radius of the circle is 2. The signal-to-noise ratio is 1.
The statistics are removed 150 times.
Table 1 shows the gain of Algorithm 1 in relation to Algorithm 2 for the magnitude of the threshold signal when the
probability of correct detection is 0.5 and the probability of false alarm is 0.001. It corresponds to the threshold L0 3,1 z21 .
3rd International conference “Information Technology and Nanotechnology 2017” 12
Image Processing, Geoinformation Technology and Information Security / N.A. Andriyanov, K.K. Vasiliev, V.E. Dementiev
Table 1. Gain (in percent) of the proposed detection algorithm based on a doubly stochastic model in comparison with the detection algorithm based on the
AR model
Shape/Image Location 1 Location 2 Location 3 Location 4
Square in Image 1 0 0 0 0
Circle on Image 1 5 2 0 2
Square in Image 2 68 3 13 4
Circle on Image 2 60 4 3 5
Square in Image 3 21 4 4 5
Circle on Image 3 70 5 7 7
Analysis of the results shows that the algorithm based on the doubly stochastic model works better than the algorithm based
on the autoregressive model and provides reliable detection of the signal in 90-95% of cases. The small values of the gains in
Table 1 are explained by the fact that the signals have small dimensions, and their neighborhoods are on a comparable scale to
homogeneous ones. If the signal is "at the junction" of homogeneous regions, an algorithm based on a doubly stochastic model
provides a significant (up to 70%) gain in the signal level term. The gains presented in Table 1 are calculated for each case from
expression
Pdds Pdar
Gain ,
Pdar
where Pd ds and Pd ar are percentages of correctly detected signals based on doubly stochastic and autoregressive models,
respectively.
a) b)
c)
Fig. 1. The noisy image (left) and the source images (right) with the probabilities of correct detection of a square signal: on the left the probabilities for
Algorithm 1 are presented, on the top the probabilities for Algorithm 2 are presented.
Analyzing the Fig. 1, we can conclude that we also have gains in correct detection probability terms on equal signal-to-noise
ratios. Furthermore the probability of correct detection depends not only on the shape and sizes of the signal itself, but also on
the brightness values in its immediate neighborhood. In this sense, a more universal algorithm is an algorithm based on doubly
stochastic RF models.
5. Increase of accuracy of object recognition due to its preliminary detection
Consider the task of recognizing objects in images. Usually, to solve this problem, binarization of the processed image is
used. However, the preliminary detection of the anomaly allows us to abandon the complicated segmentation and binarization
procedures.
As an example, consider a discrete doubly stochastic model:
3rd International conference “Information Technology and Nanotechnology 2017” 13
Image Processing, Geoinformation Technology and Information Security / N.A. Andriyanov, K.K. Vasiliev, V.E. Dementiev
xij xij xi 1 j yij xij1 xij yij xi 1 j 1 ij , i 1,..., M ; j 1,..., N , (3)
where { ij } is the field of Gaussian random variables with constant mathematical expectation M { ij } 0 and variation
M { ij2 } 2 x2 (1 xij2 )(1 yij
2
) , changing at every point of image, MxN are the image sizes.
It should be noted that the correlation coefficients in the row and column in the model (3) represent the realization of a
discrete RF of the following form:
x1 , (i, j ) I1 , y1 , (i, j ) J 1 .
xij yij (4)
x 2 , (i, j ) I 2 y 2 , (i, j ) J 2
Thus, the correlation parameters in expression (4) are a binary RF. Indeed, the elements of each of the fields in (4) can take
only two values, so their binarization by converting some values to a minimum value of brightness (Y = 0) and others to a
maximum value (Y = 255) does not cause any special difficulties.
If the anomaly is characterized by a sufficiently high level of brightness, then for its detection and subsequent identification,
known methods using brightness characteristics of the image can be used. An example of such methods can be statistical
analysis of image histograms. However, the processing results will be unsatisfactory at signal levels comparable to the
background level and less than it. To improve the efficiency of processing, it is proposed to perform preliminary detection of
objects of interest. Tables 2 and 3 show the results of binarization of the image by brightness and by the selection of the signal
area. All the results are obtained against a background of doubly stochastic images. There were cases when one signal was
present on the image: square (Table 2) or circle (Table 3). The ratio of the side of the square signal and the diameter of the
circular signal to the image length is 10%. For detection, the probability of false alarm was set as PF 0.01 .
Table 2. Binarization of an image containing a square signal
Signal-to-noise ratio 0.1 1 3 5 6
Binarization based on detection, % 34 58 94 100 100
Binarization based on brightness, % 0 12 33 78 100
Table 3. Binarization of an image containing a circular signal
Signal-to-noise ratio 0.1 1 3 5 6
Binarization based on detection, % 29 52 92 100 100
Binarization based on brightness, % 0 8 26 39 80
According to Tables 2 and 3, we can conclude that the binarization algorithm, using the results of detection, significantly
exceeds the brightness binarization. So at small signal-to-noise ratios, the first algorithm achieves a gain of 60-70%. This gain is
observed for both signal forms (square and circle). Note that the effectiveness of algorithms falls with the use of a circle-shaped
signal. This is explained by the smaller area of this signal compared to the square one.
Let the anomaly in the image be either circular or square. Then you need to find the area of the object and its center, and then
by comparing the fill factor (it is d = 1 for square signal, it is d = / 4 for circular signal) with the threshold to assign it to a
particular class.
Figure 2 shows the result of the operation of algorithms for images with a high level of brightness of the anomaly. In both
cases, the binarization was correct.
a) b) c)
Fig. 2. Recognition of objects on the image: a - the original image, b - binarization, в - the recognition result.
Thus, the proposed algorithm for detecting signals can improve the quality of binarization of images and recognition of
anomalies of the simplest geometric shape on them.
6. Conclusion
Synthesis was carried out and the efficiency of correct detection based on algorithms using doubly stochastic RF models was
studied in the text. Statistical modeling showed that the algorithm using vector Kalman filtering for models with variable
3rd International conference “Information Technology and Nanotechnology 2017” 14
Image Processing, Geoinformation Technology and Information Security / N.A. Andriyanov, K.K. Vasiliev, V.E. Dementiev
parameters allows to achieve significant gains in comparison with the algorithm based on filtering for models with constant
parameters in conditions of imitation of images based on a doubly stochastic model of RF. The main advantage of vector
filtering for doubly stochastic images lies in the possibility of estimating the change in image parameters. The developed
algorithm is also applicable to the detection of extended signals in images. In this case, the use of detection results allows to
significantly improve the detection quality of detectable low-contrast objects.
Acknowledgements
This work was supported by RFBR grant 16-41-732-027 "Construction of stochastic models and algorithms for processing
sequences of inhomogeneous polyzonal images for regional environmental monitoring systems".
References
[1] Kazarinov YuM. Radio engineering systems: a textbook for students of universities. Moscow: Publishing Center "Academy", 2008; 592 p.
[2] Perov AI. Statistical theory of radio engineering systems: a textbook for high schools. Moscow: Radio Engineering, 2003; 400 p.
[3] Vasiliev KK, Krasheninnikov VR. Statistical analysis of images. Ulyanovsk: UlSTU, 2014; 214 p.
[4] Borghys D, Achard V, Rotman SR, Gorelik N, Perneel C, Schweicher E. Hyperspectral anomaly detection: A comparative evaluation of methods. General
Assembly and Scientific Symposium, XXXth URSI 2011: 1–4.
[5] Baghbidi MZ, Jamshidi K, Nilchi AR, Homayouni S. Improvement of Anomaly Detection Algorithms in Hyperspectral Images Using Discrete Wavelet
Transform . Signal & Image Processing: An International Journal (SIPIJ) 2011; 2(4): 13–25.
[6] Soofbaf SR, Valadan Zoej MJ, Fahimnejad H, Ashoori H. Efficient detection of anomalies in hyperspectral images. The International Archives of the
Photogrammetry, Remote Sensing and Spatial Information Sciences 2008; XXXVII(B7): 303–308.
[7] Denisova AYu, Myasnikov VV. Detection of anomalies on hyperspectral images. Computer Optics 2014; 38(2): 287–296.
[8] Vasil’evKK, Dement’ev VE, Andriyanov NA. Doubly stochastic models of images. Pattern Recognition and Image Analysis 2015; 25(1): 105–110. DOI:
10.1134/S1054661815010204.
[9] Vasiliev KK, Tashlinsky AG, Krasheninnikov VR. Statistical Analysis of Multidimensional Image Sequences. High technology 2013; 5: 5–11.
[10] Vasiliev KK, Dementiev VE, Andriyanov NA. Estimation of the parameters of doubly stochastic random fields. Radiotekhnika 2014; 7: 103–106.
[11] Vasiliev KK, Dementiev VE, Andriyanov NA. Analysis of the effectiveness of estimating the changing parameters of a doubly stochastic model.
Radiotekhnika 2015; 6: 12–15.
[12] Vasiliev KK, Dementiev VE, Andriyanov NA. Detection of extended signals against a background of doubly stochastic images. Radiotekhnika 2016; 9:
23–27.
[13] Vasiliev KK, Dementiev VE, Andriyanov NA. Application of mixed models for solving the problem on restoring and estimating image parameters. Pattern
Recognition and Image Analysis 2016; 26(1): 240–247. DOI: 10.1134/S1054661816010284.
[14] Andriyanov NA. A method for fitting images based on models of random fields with varying parameters. Uspekhi sovremennoi nauki 2016; 5(9): 98–100.
[15] Andriyanov NA. Pseudo-gradient procedures in estimation problems of image model parameters. 26th International Crimean Conference "Microwave
Engineering and Telecommunication Technologies" (Crimea, Russia). Sevastopol, September 4-10, 2016; 1: 2705–2710.
3rd International conference “Information Technology and Nanotechnology 2017” 15