=Paper=
{{Paper
|id=Vol-1814/paper-10
|storemode=property
|title=Optimal Scanning of Gaussian and Fractal Brownian Images with an Estimation of Correlation Dimension
|pdfUrl=https://ceur-ws.org/Vol-1814/paper-10.pdf
|volume=Vol-1814
|authors=Alexander Yu. Parshin,Yuri N. Parshin
}}
==Optimal Scanning of Gaussian and Fractal Brownian Images with an Estimation of Correlation Dimension==
<pdf width="1500px">https://ceur-ws.org/Vol-1814/paper-10.pdf</pdf>
<pre>
     Optimal Scanning of Gaussian and Fractal
      Brownian Images with an Estimation of
              Correlation Dimension

                   Alexander Yu. Parshin1 and Yuri N. Parshin1
           1
               Ryazan State Radio Engineering University, Ryazan, Russia
                              parshin.y.n@rsreu.ru



      Abstract. The paper considers the influence of the image pixels position
      in a one-dimensional sequence on the result of correlation dimension eval-
      uation. The sequence formed as a result of reading of the two-dimensional
      pixel image. Dimension evaluation is performed by maximum likelihood
      method, using image elements ordering and creating vectors in pseu-
      dophase space by Takens theorem, and is used as a texture feature if
      texture processing and detection of objects. The two different scanning
      methods are considered. There is a problem of optimization of the scan
      path in order to maintain correlations between pixels in sequence. The
      first method is to scan on the criterion of maximum correlation between
      the adjacent sets of pixels. The second method deals with choice of scan
      direction by criterion of scalar product maximum of chosen vector and
      previous one. An estimator of correlation dimension is evaluated.

      Keywords: optimal scanning, correlation dimension, maximum likeli-
      hood estimator, fractal analysis, Gaussian and Fractal Brownian images.


1   Introduction

Problem of detection of objects and its edges, as well as the separation of areas
at images is one of the most actual in modern thematic image processing. The
distinction between areas and objects from each other is carried out by means
of evaluation of certain parameters — textural features. We can make a decision
about difference of objects on the basis of the difference of characteristic values.
One of textural attributes are statistical features, which are determined by taking
into account the statistical properties of a sequence of pixels. Among them there
is a correlation dimension, which is formally defined as the probability that
the distance between the vectors formed from samples in the time series in
pseudophase space is less than a predetermined constant value.
    One of the problems of dimension estimation of the image is a violation of cor-
relations between pixels during ordering them into a one-dimensional sequence
after reading. Radar images usually have a complex structure, which means that
the relationship of pixels is in different directions. Conventional methods per-
form scanning reading pixels horizontally, vertically or diagonally. In addition,
                                                                                85

there are space-filling curves, which allow to read all of the pixels in a selected
area once, sequentially selecting only adjacent pixels. Such a curve is, for ex-
ample, the Peano-Hilbert curve [1], which has a fractal structure and allows
to completely read the pixels in a square area. This curve is good for scan an
image with fractal properties of objects. Fractal properties and parameters, rep-
resenting it, are promising among different textural features. Such properties
are quantitatively estimated by value of fractal dimension [2, 3]. Hilbert curve
has predetermined trajectory; therefore, it does not change depending on pixels
correlation. Moreover, all of the proposed methods do not have the property of
adaptability, that is, are universal for all the images and do not consider their
statistical properties. The sequence of pixels is weakly correlated, that makes
identification of relationships more difficult. Thus, there is the task of finding
the optimal scanning method that is able to perform the adaptation of the image
with respect to the properties.
    The aim of investigation is to develop a method of scanning an image, provid-
ing more efficient textural processing and evaluation of the correlation dimension
by usage of fractal properties of the analysable image fragment as well as algo-
rithms of the fractal dimension estimation that are optimal by the maximum
likelihood criterion. An improvement of methods and algorithms is performed
by taking into account statistical and geometric dependency of data. An algo-
rithm for data scan within image frame is proposed as well.

2   A maximum likelihood estimation of correlation
    dimension
The most precise estimates of correlation dimension are obtained by maxi-
mum likelihood algorithm [4, 5]. Basic iterations for the dimension evaluation
are presented in reference [6]. When distances normalization rm = lm /lmax ,
m = 1, .., M , and correlation dimension equals D a probability distribution
law for distances between vectors V = {V1 , .., VN E } in pseudophase space is
set by power law F (r) = rD and probability density function is as follows:
          dF (r)
w(r) =           = D × rD−1 , 0 < r < 1 [4].
            dr
     In paper [4] it is discussed the problem when all M distances r = {rm , m =
1, .., M } between vectors V are independent, a correlation dimension equals to
D. Then a combined probability density function of distances is as follows:
                                    
                                       M
                                          DrD−1 , r ∈ [0, 1),
                                     Q
                         w(r/D) = m=1 m                                       (1)
                                      0, r ∈
                                           / [0, 1).
                                    

    Dependent distances are formed in accordance with the following rule [6]:
    1) N − 1 independent random numbers are generated with the power law
distribution of probabilities within the range of values (0; 1); these numbers set
distances from the first vector to all other N − 1 vectors. A combined probability
density function of these N −1 independent distances between vectors is obtained
from (1) by substitution N instead of M :
86

                                     
                                        −1
                                      NQ        D−1
                                               Dr1m  , r1 ∈ [0, 1),
                      w1 (r1 /D) =       m=1                                        (2)
                                         0, r1 ∈
                                               / [0, 1).
                                     

    2) N − 2 independent random numbers are generated with the power law dis-
tribution of probabilities within the range of values (rmax k ; rmin k ), k = 3, .., N ;
these numbers set conditionally independent distances from the second vector
to other N − 2 vectors except the 1st vector. Minimum and maximum values are
defined by the triangle rule:

                rmin k = |r12 − r1k | , rmax k = r12 + r1k , k = 3, .., N.

   Combined probability density function of these N − 2 independent distances
between vectors is as follows:
                           
                             2NQ−3       D
                                                   (r      − rmin k )D−1 ,
                           
                            m=N rmax k − rmin k max k
                           
                           
                           
         w2 (r2 /r1 , D) = rm ∈ [rmin k , rmax k ), k = 3, .., N,          (3)
                             0, r  ∈
                                   / [r     , r     ), k = 3,  .., N,
                           
                           
                           
                                m     min k max k
                             m = N + k − 3.
                           

As minimum and maximum values rmin k , rmax k depend on distances with num-
bers 1, .., N − 1, then distances r1 , r2 are also statistically dependent and their
combined probability density function is derived subject to (2), (3) :

                     w12 (r1 , r2 /D) = w1 (r1 /D)w2 (r2 /r1 , D).                  (4)
    3) Coordinates of the first and second vectors in space of embeddings DE = 2
are x1 = 0, y1 = 0, x2 = r12 , y2 = 0. Coordinates of other i = 3, .., N vectors are
defined by geometry of their position using the cosine theorem and distances from
                                                   r2 + r1i2     2
                                                              − r2i
i-th vector to the first and second vectors: xi = 12
                                                                             p
                                                                               2 − x2 .
                                                                    , yi = ± r1i     i
                                                         2r12
For convenience, sign of coordinates yi is chosen positive.
    4) As a result of coordinates evaluationof all vectors     we can calculate other
N2
                                                      p
        5N                                      rij = (xi − xj )2 + (yi − yj )2
     −      − 3 dependent distances r3 =                                          . As
  2      2                                      i = 3, .., N, j = i + 1, .., N
distances r3 are absolutely defined by distances r1 , r2 , than they do not contain
additional information for the correlation dimension estimation.
    Optimal estimates of the correlation dimension should take into account sta-
tistical and geometrical dependences of vectors, which are represented in the
likelihood function. A maximum likelihood estimate is obtained as a result of
solving of the optimization problem:

                         Dest = arg      max      w12 (r1 , r1 |D).                 (5)
                                      0<D<DE

   The solving of equation (5) is realized by setting equal to zero of first order
derivative of w12 (r1 r2 |D) with respect to D. A maximum likelihood estimate of
                                                                                                 87

correlation dimension is obtained:
                              "N −1          2N −3
                                                                   #
                               X              X
              D̂ = −(3N − 3)        ln r1m +       ln(rm − rmin k ) .                           (6)
                                      m=1              m=N




3    Optimal scanning by maximum correlation coefficient
It is necessary to choose an approximating model for processing of signals and
images as well. The main principle of model choosing is to provide a maximum
conformance of model and real signal parameters. A 2D Fractional Brownian
motion is widely used as a model of a chaotic fractal image. Samples of 2D
fBm are formed X(k, m), k, m = 1, .., N , by one of famous methods [7, 8] and
characterized by intensity σ 2 and Hurst exponent H. Variance of fBm increments
                                                   H
in the space interval ∆x, ∆y equals σ 2 ∆x2 + ∆y 2 , and its correlation within
disjoint intervals of space equals [7]:

    M = {(X(k1 , m1 ) − X(k3 , m3 )) × (X(k2 , m2 ) − X(k4 , m4 ))} =
      σ2 2         H   σ2 2           H   σ2                            H
    =      k1 + m21 +       k2 + m22 −         (k1 − k2 )2 + (m1 − m2 )2 −
       22               22                 22
      σ            H   σ             H   σ                              H
    −     k12 + m21 −      k42 + m24 +        (k1 − k4 )2 + (m1 − m4 )2 −                       (7)
      2                2                  2
      σ2 2         H   σ2 2          H   σ2                             H
    −     k3 + m23 −       k2 + m22 +         (k3 − k2 )2 + (m3 − m2 )2 +
      22               22                 22
      σ            H   σ             H   σ                              H
    −     k 2 + m23 +      k 2 + m24 −        (k3 − k4 )2 + (m3 − m4 )2 .
      2 3              2 4                2
Two-dimensional Gaussian process X(k, m) is used for representing of image
with zero mathematical expectation, dispersion Dx and correlation matrix

R = {R(i1 , j1 , i2 , j2 ) = Dx exp [−(αx |i1 − i2 | + αy |j1 − j2 |)] , i1 , i2 , j1 , j2 = 1, .., N } .
                                                                                                (8)
Figures 1-2 represent image samples according to above-mentioned models.




         a) H = 0.1                        b) H = 0.5                         c) H = 0.9

                       Fig. 1. Image of 2D Fractal Brownian motion.
88




    a) αx = 0.01, αy = 0.1       b) αx = 0.1, αy = 0.1       c) αx = 0.1, αy = 0.01

                         Fig. 2. Image of 2D Gaussian process.



    In a review paper [1] various methods of the scan path optimization are
considered, based on the correlation property of pixels. It is supposed that the
construction of the scan path, taking into account the correlation property of
pixels, allows to most fully represent dynamic properties of the image and im-
prove the accuracy of correlation dimension estimation
    In this paper two method of image scanning is discussed. The first method
deals with choice of scan direction by criterion of correlation coefficient maxi-
mum (7), (8) of each subsequent pixel. This method uses image characteristics,
averaged by significant ensemble of samples, but it doesnt consider properties
of particular image. The second method deals with choice of scan direction by
criterion of scalar product maximum of chosen vector X and previous one Y.
This method doesnt require a priori information about statistical properties of
image. Data of particular image are most fully used for construction of optimal
scan path. The optimal scanning algorithm consists of a following steps:
    - first vector consists of M image pixels from first line of current frame;
    - one of Q predefined directions from last pixel to end of next vector is
considered;
    - standard scalar product is evaluated for pair of vectors previous X and each
of Q considered directions Y — as follows:

                                            (X, Y)
                                RX,Y =                                            (9)
                                         ||X|| × ||Y||

    - maximum value of scalar product defines a pair of vectors and thereby the
direction of scan trajectory;
    - scan trajectory moves to new pixel, which is last for chosen vector;
    - the algorithm is repeated until majority pixels are covered.
    Figures 3-6 represent optimal scan paths for Gaussian and Fractal Brownian
images, obtained by two proposed methods.

4     Correlation dimension evaluation
Dimension evaluation is performed by maximum likelihood method [4], with
image elements ordering and vectors formation in pseudophase space by Takens
                                                                                  89




Fig. 3. Optimal scanning trajectory by
1-st method, image of figure 1c.              Fig. 4. Optimal scanning trajectory by
                                              2-st method, image of figure 1c.




Fig. 5. Optimal scanning trajectory by
1-st method, image of figure 2a.              Fig. 6. Optimal scanning trajectory by
                                              2-st method, image of figure 2a.




theorem [9]. An estimator of correlation dimension of Gaussian random image is
investigated. Then we change value of αy and estimate a correlation dimension
in two case: scan trajectory is vertical (figure 7) and scan trajectory is horizontal
(figure 8). The evaluated estimates are averaged by 20 samples, the vector size
is equal NE = 3.


5   Conclusions
Results of analysis of proposed algorithm show, that appliance of maximum
likelihood algorithm demands provision of maximum correlations between im-
age pixels in one-dimension sequence. Scanning by maximum correlation coeffi-
cient criterion provides bigger difference between values of correlation dimension
estimates and therefore simplifies solution of object detection problem.
90




Fig. 7. Dependency of correlation di-          Fig. 8. Dependency of correlation di-
mension on αy , αx = 0.7, vertical scan.       mension on αy , αx = 0.7, horizontal
                                               scan.



Acknowledgments. Investigation was carried out with the Russian Science
Foundation support, project number 14-19-01263.

References
 1. T. Ouni, M. Abid, Scan Methods and their Application in Image Compression,
    International Journal of Signal Processing, Image Processing and Pattern Recog-
    nition, vol. 5, No. 3, 2012, pp. 49-63.
 2. Yu.G. Sosulin, A.B. Russkin, Fractal Detection of Extensive Low in Contrast Ob-
    jects in Images, Radiotechnika, 2009, 12, pp. 48-57.
 3. A.A. Potapov, Fractals in Radio Physics and Radiolocation: Selection Topology.
    oscow: Universitetskaya kniga, 2005.
 4. Luciana De Luca, Dario Luzio, Massimo Vitale, A ML Estimator of the Correlation
    Dimension for Left-hand Truncated Data Samples,, Pure and Applied Geophysics,
    vol.159, pp. 2789-2803, 2002.
 5. A. Yu. Parshin, Yu. N. Parshin, Usage of non-Gaussian statistics for RF Signals
    Detection by Complex Energy and Fractal Detector, International Radar Sympo-
    sium, IRS 2013, Proceeding, vol. I, II, pp. 779-784, Drezden, Germany, German
    institute of navigation, 2013.
 6. A. Yu. Parshin, Yu. N. Parshin, Analysis of Maximum Likelihood Estimation of
    Fractal Dimension by Independent and Dependent Data, 5th Mediterranean Con-
    ference on Embedded Computing (MECO), 2016, pp: 172 175.
 7. R.M. Crownover, Introduction to Fractals and Chaos. Jones and Bartlett, 1995.
 8. Wood A. and Chan G., Simulation of stationary Gaussian processes in [0, 1]d,
    Journal of computational and graphical statistics, 1994, vol. 3, No.4, p. 409-432.
 9. F. Takens, Detecting Strange Attractors in Turbulence, Lecture Notes in athemat-
    ics, vol. 898, 1981, pp. 366-381.

</pre>