Optimal Signal and Image Processing in Presence of Additive Fractal Interference Alexander Yu. Parshin1 1 Ryazan State Radio Engineering University, Ryazan, Russia parshin.a.y@rsreu.ru Abstract. The article deals with algorithms for signal and image pro- cessing in presence of interference from the underlying surface, flicker noise, and other types of interference with fractal properties. Models of fractal interference are considered on the basis of the statistical ap- proach. Application of the fractal Brownian motion model with fractional dimension is proved for the statistical description of low-frequency flicker noise is proved, and, also, for describing the reflection coefficient of the sensing signal from the background of natural origin under obtaining the radar images. A maximum likelihood algorithm for detecting signals and extended objects, as well at the background of additive fractal noise are developed. The characteristics of detection of extended objects at the background of fractal noise, as well as a low-frequency signal at the background of flicker noise are calculated. The statistical modeling of the object detection algorithm on raster and complex images of the earth’s surface was carried out and its efficiency was evaluated. It is established that usage of the fractal models allows improving the efficiency of signal and image processing at the background of noise in cases where there are no other differences between them. Keywords: Fractal analysis, signal processing, image processing, max- imum likelihood method, detection algorithm 1 Introduction Contemporary studies have made it possible to establish the self-similarity and fractional measure properties of signals and images obtained by receiving signals reflected from various objects [1, 2]. The investigated processes are not consid- ered as a simple set of individual elements with certain characteristics, but as some structure that has internal topological connections between the elements and characterizes the complex object as a whole. A distinctive property of such processes is the non-integer nature of their dimension. Despite existence of dif- ferent definitions and the magnitude of dimension for a given signal or image [3], each of them characterizes the general property of self-similarity. This allows us to use the dimension value as an indicator in solving problems of detection, classification, and estimation of parameters [1, 2]. At the same time, the theory of optimal processing of signals and images based on fractal representations has not been developed sufficiently. 84 Methods and algorithms for optimal processing of signals and images based on probabilistic models and the theory of optimal statistical solutions are well- known and widely applied. The most general formulation of the problem and the model of signals and interference are implemented in the estimation-correlation- compensation approach [4–6]. The statistical approach is also used in processing the signals and images with fractal properties, for example, fractal Brownian motion [7]. Another example of effective application of the statistical methods is interpretation of the correlation integral as the probability of non-exceeding the distance between vectors of a given value [8–12]. The aim of the research is to develop and improve the statistical approach in problems of detecting signals and objects against a background of fractal noise and increasing the efficiency of processing algorithms. 2 Correlation dimension of signals and interferences The most complete statistical approach is applied to processing the fractal signals and images. For description of signals and images properties, one of the defini- tions of the fractal measure is used, i.e. the correlation dimension. In [2,13], the mathematical description uses the notion of a correlation integral, which deter- mines the probability that two independent observable vectors are at a distance less than r: Cw (r) = P (kx − y kE < r) , where x , y , E dimensional vectors with the same distribution, w probability measure. When observing samples of E-dimensional vectors (x 1 , x 2 , . . . , x n ), correlation dimension is determined [14] as the double limit log Cn (r) D = lim lim , (1) r→0 n→∞ log r where Cn (r) is the correlation integral n X n 2 X Cn (r) = H(r − kx − y kE ), (2) n(n − 1) m=1 j 0 tion dimension of the proposition in [8,9] is based on the assumption that the cor- relation integral is calculated for independent random distances rm = kx − y kE , i = 1, . . . , n, j = 1, . . . , n, m = 1, . . . , M = n(n − 1)/2, distributed by the power law. For given value of correlation dimension the correlation integral (2) is C(r) ≈ rD that allows one to represent distances between vectors as random value with the power law of distribution. In the case of distance norming rm /rmax , the distribution law is F (r) = rD , and multidimension probability density function is [9] YM M Y D−1 w(r , D) = w(rm ) = Drm . (3) m=1 m=1 85 Since the resulting multidimensional density (3) is also a function of unknown dimension, it can be considered as a likelihood function. The maximum likelihood estimation of the correlation dimension is obtained as a result of solving the following extremal problem: D̂ = arg max w(r , D). n D Using logarithm of the likelihood function and extremum condition ln w(r , D) = dD 0, it is possible to calculate the maximum likelihood estimate [10] M D=− M . (4) P ln rm m=1 The above estimate is effective and asymptotically unbiased. Analysis of the dis- placement and variance of the estimation error was carried out in [15]. Presence of the fractal noise alters the properties of the observed signals and images, that is reflected in their correlation dimension. Consider the situation when a fractal signal with the dimension DS is observed against the background of additive fractal noise with the dimension DJ . Since in the general case this analysis is extremely complicated, let us consider the case when the intensity of the inter- ference is much greater than the intensity of the useful signal. Considering the signal and interference in the pseudo-phase space and using the Taken’s tower, it can be assumed that the presence of a weak signal slightly changes the distances between the vectors of the observed process by a value δrm << rm . Under these assumptions, the asymptotic expression for estimating the correlation dimension of the sum of the signal and the interference has the form   M M ! M  M X δrm  D̂ J X δrm D̂1 = − M 1 − M  = D̂J 1 + , P  P m=1 rm  M m=1 rm ln rm ln rm m=1 m=1 M 1 X δrm where the second term describes the signal presence. The factor δD = M m=1 rm is a random variable with the asymptotically Gaussian probability distribution when M >> 1. The signal optimal processing against a noise background reduces calculation of a sufficient statistics to calculation the logarithm of the likelihood ratio. 3 Fractal Brownian motion as a model of fractal signals and interferences Fractal Brownian motion is used as a model of fractal interference. Samples of FBM are formed by one of famous methods [7] and characterized by intensity 86 σ 2 and Hurst exponent H. Dimension of FBM is determined by D = 2 − H for one-dimensional FBM and D = 3 − H for two-dimensional FBM. If determined signals are observed at the background of additive fractal interference in the form of FBM, then detection and identification are complicated. Therefore, one of the actual problem is synthesis of optimal detection algorithms for signals at the background of additive fractal interference in the form of FBM. Let the signal sn is observed at the background of FBM interference xn yn = sn + xn , n = 1, . . . , N, where N is the amount of samples of observed process, xn are the independent samples of FBM interference. The fractal Brownian motion is a Gaussian ran- dom process; therefore, its properties are completely determined by correlation matrices for one-dimensional signal [7] M {(X(t2 ) − X(t1 )) (X(t4 ) − X(t3 ))} = 2 −(t2 − t1 )2H + (t2 − t3 )2H + (t1 − t4 )2H − (t1 − t3 )2H ,   = 0.5σ (5) and for two-dimensional image 1 2 σ (i − j − 1)2H − 2(i − j)2H + (i − j − 1)2H .  Rij = M {xi xj } = 2 Therefore, the matrix R, which contains correlations of all possible increments M = = 0.5 × N (N − 1), has the size of M × M and is formed by given N samples: ∆xm = x(ti ) − x(tj ), i = 1, . . . , N, j = 1, . . . , i, m = 1, . . . , M. Vector of T increments ∆X = {∆X1 , . . . , ∆XM } , given by this way, has multidimensional probability density function:   1 1 w(∆X ) = √ exp − ∆X T R−1 ∆X , (6) (2π)M/2 detR 2 where correlation matrix R depends on Hurst exponent H, and probability den- sity function can be considered as likelihood function   1 1 T −1 w(∆X /H) = p exp − ∆X R (H)∆X . (7) (2π)M/2 detR(H) 2 Likelihood ratio of increments of FBM interference and observing determined signal at the background of interference is s detR(H) Λ(H) = × det(R(H) + Ry )   1 T −1 1 T −1 × exp − ∆X (R(H) + Ry ) ∆X + ∆X R (H)∆X . (8) 2 2 Evaluation of determinant and conversion of matrix of increments R are very difficult computational problem in case of randomly given moments of 87 time. Therefore, in several cases, it is useful to consider only non-correlated increments within non-crossing time intervals. In such cases the correlation equals M {∆Xi , ∆Xj } = δij DX ∆t2H i , where δij is the Kronecker delta, i = 1, . . . , N − 1.QIn this case, the matrix R is diagonal and its determinant equals N N −1 2H detR = DX n=1 ∆tn . Multidimensional probability density function (PDF) of the FBM increments is N −1 " # 1 1 X ∆Xn2 w(∆X ) = exp − 2 , (9) 2σ n=1 ∆t2H s −1 NQ n (2π)(N −1)/2 σ 2H 2H ∆tn n=1 where we can obtain the likelihood ratio of Gaussian signal at the background of fBm interference s −1 NQ σ 2N ∆t2H n " N −1  # ∆x2n  n=1 1 X 1 2 Λ= exp − − 2 2H ∆xn . (2Dv )(N −1)/2 2 n=1 2Dv σ ∆tn This algorithm is quasioptimal, because it does not consider the increments correlation at the overlapping intervals. But it has significant computational advantages, since of absence of matrix inversion operations of high computational cost. Getting the non-correlated samples of FBM is possible as a result of tran- sition in the spectral field. It is well-known [7], that the spectral power density 1 of signal in the form of FBM equals G(f ) = f 2H+1 . Fractional Brownian sur- face (FBS) model may also be given in the spectral area as assembly of har- monics S = {S(k, n)} , k = 1, . . . , Nx , n = 1, . . . , Ny , represented by discrete Fourier transform of FBS samples {s1 , . . . , sN }. All harmonics are independent complex Gaussian values, variances of which equal M |S m |2 = mG  2H+1 , m = X 1, . . . , NG , where NG is the number of harmonics. If the white Gaussian noise is observed with fractal interference, then spectrum of additive interference is G0 |X m |2 = m2H+1 + N0 , m = 1, . . . , M = N/2. Multidimensional probability density function of the FBM spectral compo- nents is " M # 1 X 2 1 w(X ) = M exp − |X m | G0 , (10) G0 2H+1 + N0 Q  π M + N0 m=1 m m2H+1 m=1 . Using spectral representation of the observing data Y m and determined signal S m , logarithm of the likelihood ratio is M X SH Ym H H m + Y mSm − SmSm Λ= G0 , (11) m=1 m2H+1 + N0 88 . Thus, in spectral area, the algorithm of likelihood ratio evaluation turnouts simpler because an operation of matrix inversion is excluded. The FBM detec- tion in spectral area against the background of Gaussian noise is made as a result of calculation of statistic (9) and comparing it with a threshold. If a spec- G0 trum of signal is of low frequency with harmonics |Sm |2 = 2 , then asymptotic m interference immunity of signal processing exists against the background of frac- tal interference and depends on the Hurst factor: if H < 1/2, then interference immunity is nondecreasing function on signal frequency; if H > 1/2, then the interference decreases with decreasing the signal frequency. 4 Conclusion It is shown that methods of the theory of optimal statistical solutions can be successfully applied also to processing of the fractal signals and images against the background of additive fractal noise. The basis for the effectiveness of sta- tistical methods is the irregular character, as well as the relatively large amount of observable data. Under these conditions, the statistical description of fractal signals and images is produced by various methods: the use of a one-dimensional and two-dimensional fractal Brownian motion model, and a statistical descrip- tion of distances between vectors in a pseudo-phase space. This approach allows us to obtain processing algorithms based on the theory of optimal statistical solutions for solving various problems: detection, discrimination, delineation of boundaries, estimation of parameters, and analysis of the processing efficiency. At the same time, the statistical description is not obtained for all fractal signals and images and their characteristics, and this makes it important to continue research in this direction. 5 Acknowledgment The research is supported by the project of the Ministry of education and science of the Russian Federation 8.2810.2017 in the Ryazan State Radio Engineering University. References 1. Potapov A.A.: Fractals in Radio Physics and Radiolocation: Selection Topology. oscow: Universitetskaya kniga, (2005). 2. Culter C.D.: A review of the theory and estimation of fractal dimension. Nonlinear time series and chaos, vol.1. Dimension estimation and models, 1–107, (1993). 3. Parker T. S., Chua L. O.: Practical Numerical Algorithms for Chaotic Systems. New York: Springer. (1989). 4. Sosulin Yu.N.: The theory of detection and estimation of stochastic signals. Sovetckoe radio, Moscow, (1978). 89 5. Sosulin Yu.G., Parshin Yu.N.: Estimation-correlation-compensation processing of multi dimension signals. Padiotechnika i electronica, Moscow. 26, 1635–1643. (1981). 6. Sosulin Yu.G., Kostrov V.V., Parshin Yu.N.: Estimation-correlation signal process- ing and interferences compensation. Radiotechnika, Moscow. (2014). 7. Crownover R.M.: Introduction to Fractals and Chaos. Jones and Bartlett, (1995). 8. Pisarenko D. V., Pisarenko V.F.: Statistical estimation of the correlation dimen- sion. Physics Letters, A(197), 31–39, (1995). 9. Luca L., Lasocki S., Luzio D., Vitale M.: Fractal dimension confidence interval estimation of epicentral distribution. Annali di Geofisica. 42(5), 911–925, (1999). 10. Luciana De Luca, Dario Luzio, Massimo Vitale.: A ML Estimator of the Correlation Di-mension for Left-Hand Truncated Data Samples. Pure and applied geophysics. 159(11-12), 2789–2803. (2002). 11. Parshin A., Parshin Yu.: Usage of non-Gaussian statistics for RF signals detection by complex energy and fractal detector. International radar symposium - IRS 2013, Proceeding, volume I, II, Drezden, Germany. German institute of navigation, 779– 784, (2013). 12. Parshin A.Yu., Parshin Yu.N.: An application maximum likelihood estimations of fractal dimension in nongaussian problems of radio signal detection. Digital signal processing, Radiotechnika, Moscow. 1, 42–46, (2013). 13. Pesin Ya. B.: On rigorous mathematical definitions of correlation dimension and generalized spectrum for dimensions. Journal of Statistical Physics. 71, 529–547, (1993). 14. Grassberger P., Procaccia I.: Characterization of strange attractors. Physical Re- view Letters. 50, 346–349 (1983).