Segmentation With Predictive Error And Recursive Likelihood Ratio Deviation Methods In Material Characterization

SEGMENTATION WITH PREDICTIVE ERROR AND RECURSIVE LIKELIHOOD RATIO DEVIATION METHODS IN MATERIAL CHARACTERIZATION S. Femmam and N. K. M'Sirdi L.R.P.- U.V.S.Q. 10-12 Avenue de l'Europe V¶elizy 78140 France e-mail : ffemmam, msirdig@robot.uvsq.fr ABSTRACT In this paper, abrupt changes detection techniques are used for segmentation of ultrasound signals in order to characterize materials. We describe the main motivations for the investigation of change detection problems. We show that the use of the Recursive Likelihood Ratio Deviation (RLRD) algorithm provides better results than the Linear Prediction Error (LPE) algorithm. The choice of the ultrasound signal length problem is used in the spectral ratio technique for determining the quality factor of a material. Keywords: Spectral ratio, quality factor, LPE, RLRD, segmentation, faults diagnosis. 1 INTRODUCTION Many practical problems arising in quality control and non-destructive evaluation, can be processed parametric models in which the parameters are subject to abrupt changes at unknown time instants. Because a large part of the information lies in the nonstationarities, and because most of the adaptive estimation algorithms basically can follow slow changes[2]. In this paper we implement and compare two di®erent algorithms (LPE and RLRD) for automatic segmentation of ultrasound signal. The mostly applied technique for determining the quality factor is the spectral ratio technique. The latter uses the entire ultrasound signals. But the main information is localized in a piece of the signal, so we need segmentation. After segmentation we apply the SR method to the desired segments, the results are better comparing the case when we use all the signal. Figure 1. a, b and c show respectively the ultrasound signal for the aluminum, the granite and the limestone. In ¯gure 1. a [T 1; T 2] represents the main interval of information and [T 2; T 3] is the reverberation signal. 2 PROBLEM FORMULATION The spectral ratio method deals with the analysis of the signals energy distribution. The method consists of determining the spectral ratio magnitude of a reference signal and the signal of the material whose quality factor is unknown. Afterward we calculate the slope (¯gure 3. a and b) of the segment of the straight line at the frequency of the excitation signal. The viscoelas2 2 tic model used in [1] is given by: r @@tU2 = M (!) @@xU2 where M(!) is the complex magnitude. A general solution for a °at wave is: U = U0 exp(¡®x) exp(i!(t ¡ xc )) where c is a real constant, exp(¡®x) gives the wave attenuation, and ® is the attenuation factor. The quality ¼ factor Q is given by the relation: ® = QV f: where f and V are respectively the frequency and the velocity of the ultrasound wave. The equation that gives the spectral amplitude of a °at wave is given by: U(f) = G(f; x) exp(¡®(f )x exp(i(2¼f t ¡ kx)) where G(f; x) is the function which takes into account the geometrical shape of the sample and the reference, x, is the length of the material to be characterized, ®(f ), is the attenuation coe±cient. The spectral ratio can be written as: · ¸ U(t) 1 1 ¡ Log( ) = ¡¼ xf + cte (1) Ur (t) QV Qr Vr The Aluminum is well known and considered as a reference material. Its quality factor Qr is very large ( Qr1Vr ¼ can be neglected), and (1) gives the slope a = ¡ QV x which allows us to determine Q. 2.1 Classical spectral analysis and Parametric spectral estimation By using the classical spectral estimation technique (Fourier) the spectral ratio method does not give a good spectrum and hence the determined slope is not smooth so resulting on wrong Q's . The resulting curve is shown in ¯gure 3 [3]. For this estimation the signal is supposed to be stationary. However if the characteristics of the process vary with time, the results are not able to follow these variations. Due to these problems the parametric models to characterize these processes have been chosen to be used. We have shown [3] that the adaptive parametric spectral estimation methods, for instance the Least Mean Square, the Recursive Least Square, the Burg algorithm, and the Marple algorithm in AR modeling provide a very smooth spectrums and hence the spectral ratio. This implies a constant slope estimation over the resonant frequency range and an e±cient quality factor. In ¯gure 3 the parametric spectral ratio estimation is shown. 2.2 Segmentation An other practical motivation for change detection. In signal processing the segmentation of signals refers to the automatic decomposition of a given signal into segments, the length of which is adapted to the local characteristics of the analyzed signal [2]. The homogeneity of a segment can be in terms of the mean level or in terms of the spectral characteristics. Due to the problem of the estimation of the desired portion (portion containing the largest energy) of the ultrasound signal used in the estimation of the Q's. For this task we have developed two algorithms which are the LPE and the RLRD for automatic segmentation of the ultrasound P waves. These results are validated by use of time-frequency and time scale (wavelet) energy distribution, for more information see [4]. The use of time-frequency and wavelets energy distribution can be a tool for faults discrimination in nondestructive evaluation, for more details refer to [8]. 3 CHANGE DETECTION ALGORITHMS 3.1 Linear Predictive Error algorithm The objective of this algorithm is to detect parameters changes of an AR model driven by a gaussian white noise. The method consists of supervising the innovations (LPE) calculated from an AR model. The parameters are estimated by the algorithm of Morf [2]. The model is constructed over a piece of the signal, after we compare the LPE of variance ¾ b2 to a threshold value ¾ , ¸ is real. A change exists when "n exceeds S" ; S" = ¸b Nd times. Where Nd is called the alarm number. After detection we update the model and in this case the new window must be delayed by few samples after the last detection. A discrete signal can be represented by (2): p X xn = ak xn¡k + En (2) k=1 and where En is a white noise of zero mean and a varip P ance ¾2 : Let x bn = b ak xn¡k is the estimated of xn k=1 constructed from the last p samples of the signal xn¡p ; xn¡p+1; ... xn¡1 ; and the EPL can be written as in (3): "(n) = xn ¡ x bn = xn ¡ p X k=1 b ak xn¡k (3) to En with a varithe estimation¡ is good ¢when£ "n tends ¤ ance ¾ b2 ' ¾2 ¾ b2 < ¾x2 :E "2 (n) , ¾"2 : . We introduce a pointer variable as stated in (4). P (n) = 1, f or j"(n)j  t and P (n) = 0, f or j"(n)j Á t (4) where t is a threshold value which is chosen as follows: ¯rst we de¯ne El , El = (P (n ¡ l + 1); :::; P (n)) where l is an innovation sliding window.¤ Under the hypothesis H0 (the probability of a ¯xed alarm PF A = ®), the "threshold" value is given by: ½ µ ¶¾l t P [j"(n ¡ l + 1)j  t; :::; j"(n)j  t=H0 ] = ERF ¾" (5) ¤ Under the hypothesis H1 , the probability of detection PD is maximized by the parameter l. 3.2 Recursive Likelihood Ratio Deviation algorithm 3.2.1 Hypothesis test and Con¯dence interval The hypothesis test can be stated by a con¯dence interb and for a value of ® which val de¯ned for an estimator Á its signi¯cant level is taken by its probability density function[6]. We can consider: * An accepted hypothesis region given by (H0 ): Á® Pr ob[Á1¡ ®2 < Áb < Á ®2 ] = Z2 Á1¡ ® 2 b p(Á)dÁ =1¡® (6) * A critical region de¯ned by (H1 ) : Pr ob[Áb > Á ®2 ] = +1 Z ® b p(Á)dÁ = 2 (7) Á® 2 Â2 law, variance estimation and Likelihood ratio For a gaussian random variables xi we can de¯ned a nb ¾2 variance ¾2x = Â2n (xi ²N (0; 1); n = N ¡ 1)) as a new x variable Â2 with n degrees of freedom (number of lags in processing) [5]. For an (1 ¡ ®)% required con¯dence level. The estimated variance is compared to the accep2 ¾x nb ¾2 tance region Ânb · ¾x2 (t) < Â2 x ® ; if this equation 2 ® n; 2 n;1¡ 2 is satis¯ed The information signal is chosen to be the innovation sequence "(t) then, there is no change (the innovation is white x(t) = "(t)); else, there is a change (the innovation is not white). As we have stated before the likelihood ratio method is based on the statistical test of the probability density function P (xi (k)) of the gaussian random variables xi (k). The PDF is maximum when xi (k) is a value of change. The PDF of x(k) under H0 and H1 is: L[x(k)] = k p(x(t)=x(t ¡ 1); H1 ) p [x(k)=H1 ] = ¦ (8) p [x(k)=H0 ] t=k0 p(x(t)=x(t ¡ 1); H0 ) The likelihood ratio can be written in recursive form (9): (x(k)) + LnL[x(k)] = LLkk¡1 0 [p(x(t)=x(t ¡ 1); H1 )] (9) [p(x(t)=x(t ¡ 1); H0 )] Dk = Dk¡1 + dlk ? » (10) The decision test becomes the Likelihood Ratio Deviation dlk ? ±: 3.2.2 Detection of abrupt changes of variance by RLRD The RLRD is an e®ective algorithm for abrupt changes detection. Consider an independent random variables x(k) with mean m0 and variance ¾02 for the hypothesis H0 and with mean m1 and variance ¾12 for the hypothesis H1 : We assume that it follows the normal distribution. µIts distribution¶ is given by: p(x(t)=Hi ) = ´2 ³ 1 x(t)¡m 1 p exp ¡ , i=0,1, and ¾ b12 are b02 and ¾ 2 ¾ bi ¾ b 2¼ i where a is a reel constant. If we derive (11) with respect to µb and assuming that x(t) and ¾x (t) are independent T b of µ(t): So, F (t) = E '(t)'(t) : F (t) gives us information 2 (t) ¾x about the parameters in its direction. For an e®ective information we estimate F (t) on a sliding window with tc P '(t)'(t)T size nf ; F (tc ¡ nf + 1; tc ) = in recur¾ b 2 (t) sive form, F (tc ) = F (tc ¡ nf + 1; tc ¡ 1) + To avoid the cision test is dl(k) = complexity of the threshold choice we rearrange dl(k): 2 ¡th (x(k)¡m)2 where A¡1 = ¾b 1th is a constant. dl(k) = ¡ A 2 ¾ b 12 A is the minimum and relative uncertainty of the estimated variance to be accepted. So we can consider now the variable dl(k) as a Â2 variable with one degree of freedom, normalized by the constant A of a mean m and a variance ¾ b12 and the test becomes there a change if the conditions jdl(k)j > Â21; ® and jdl(k)j < Â21;1¡ ® 2 2 are satis¯ed, and no change else where. Or we can say 2 ¢b ¾ that there is a change of variance if ¾b 21 > A% and no 0 change else where. 3.2.3 Change compensation Compensation by Fisher information matrix The use of compensation technique provides a good estimation and allows an e®ective tracking performances of parameters estimation. We use the compensation technique by computing the compensation term at the instant of change -0 (tc ) as a function of the Fisher information matrix F (t): From Cramer Rao inequality e µ(t) e T ) > F ¡1 where µ is the paramewe have E(µ(t) ters vector and F is given by the expected value of the probability function logarithm deviation with respect 2 b If we conto the parameters. F = ¡E @@µb2 Lnp(x=µ): sider the signal x(t) is normally distributed the PFD µ ³ ´2 ¶ x(t)¡m 1 1 x (t) b is : p(x(t)=µ(t))) = ¾ (t)p2¼ exp ¡ 2 ¾x (t) x If we assume that between two instants of changes b So, that mx (t) may be replaced by the x b(t=µ(t)). Tb b mx (t) = x b(t=µ(t)) = '(t) µ(t) substituting mx (t) in b p(x(t)=µ(t))) and rearranging, we can write that: b Lnp(x(t)=µ(t)) = a ¡ Ln¾x (t) ¡ pi (tc ) = b 2 (x(t) ¡ '(t)T µ(t)) 2 ¾x (t) (11) '(t)'(t)T ¾ bx2 (t) fi F (tc ; tc ¡ nf + 1)fiT p P fi F (tc ; tc ¡ nf + 1)fiT (12) (13) i=1 1 2 . ¡ 12 ¾bth2 (x(k)¡m) ¾ b 12 ¡th 1 x The change probability and the compensation term are given by (13) and (14) respectively the estimates of ¾02 and ¾12 : The minimum deviation of the variance is ¾ ¾02 > th > 0 b12 -b where th is the threshold value for the minimum variance deviation to be accepted. Dk becomes Dk = 2 and the deLLk1 (x(k)) = LL1k¡1 (x(k)) ¡ 12 ¾bth2 (x(k)¡m) ¾ b 2 ¡th 1 i=tc ¡nf +1 2 -0 (tc ) = s0 s (tc ) p X pi (tc )fi fiT (14) i=1 and ¯nally the compensated gain becomes: P ((t = tc ) + 1) = P (t = tc ) + -0 (tc ) (15) where fi is the change direction vector, s0 is a constant for the compensation level, s2 (tc ) this function is chosen as the information signal covariance and p is the number of parameters to be estimated[7]. 4 RESULTS Fig. 1. a, b and c show respectively the ultrasound signal for the aluminum, the granite and the limestone with the instant of segmentation by use of RLRD algorithm. In ¯g.1. d the limestone with its instant of detection by LPE algorithm is represented. Fig. 2. a, b, and c show respectively the piece of the segment containing the main information of the aluminum, the granite and the limestone signals with segmentation by LPE algorithm. We can remark that the delay of the instant of detection is considerable, this means a loss of information at the beginning of the signals. This is due to the non implementation of the failure compensation technique in the LPE algorithm. Fig. 2. d, e and f show respectively the desired segments by use of the RLRD algorithm of the aluminum, the granite and the limestone signals. The use of RLRD algorithm is much better and more sensitive to the instant of detection, to make clear the failure compensation technique the implementation of the RLRD algorithm without the failure compensation technique is shown by ¯g. 2. f. Fig. 3. a and b show respectively the estimated and the original (Fourier) SR of the desired segments by LPE algorithm of the aluminum (reference signal) over the granite signal and the aluminum over the limestone signal. In ¯g. 3. c and d we represent respectively the estimated and the original SR of the desired segments by RLRD algorithm of the aluminum over the granite signal and the aluminum over the limestone signal. The estimated SR give a very smooth negative slope compared to the original SR where nonparametric method is used. this slope is used for characterizing the materials. (a) 15 10 10 (b) Signals + Abrupt changes 2 Esti. & Orig. Spectral Ratio Original 5 5 0 Estimated 0 Ampl dB Estimated -5 Ampl dB -5 -10 Original -10 -15 -15 -20 -25 0 0.5 (c) (a) (b) Esti. & Orig. Spectral Ratio 15 1 1.5 frequency (Hz) 2 2.5 x 10 -20 0 0.5 1 1.5 frequency (Hz) 6 (d) Esti. & Orig. Spectral Ratio 15 2 2.5 x 10 6 Esti. & Orig. Spectral Ratio 15 Signals + Abrupt changes 1 10 Original 10 5 1.5 1 0.5 Ampl mvolt Ampl mvolt Estimated 0 5 Ampl dB -5 Ampl dB 0 Original -10 0.5 Estimated -15 -5 0 -20 0 T1 T2 -1 0 200 400 (c) 1 -10 T3 -0.5 600 Samples 800 1000 1200 -0.5 0 200 400 (d) Signals + Abrupt changes 1 600 Samples 800 1000 1200 0 0.5 1 1.5 frequency (Hz) 2 2.5 3 x 10 6 -25 0 0.5 1 1.5 frequency (Hz) 2 2.5 3 x 10 6 Figure 3. Estimated & original SR of segments Signals + Abrupt changes References 0.5 0.5 [1] A. Kavetsky et al, A model of acoustic pulse propagation Ampl mvolt Ampl mvolt 0 -0.5 0 0 200 400 600 Samples 800 1000 1200 -0.5 0 200 400 600 Samples 800 1000 1200 Figure 1. Signals with detection of abrupt changes (a) 2 Desired segment (LPE) (d) 2 1.5 1 Ampl mvolt Ampl mvolt 0.5 0.5 0 [3] S. Femmam, N.K. M'Sirdi, S. Guillaume, AR process- 0 -0.5 -0.5 -1 0 50 100 150 Samples 200 250 300 -1 350 (b)Desired segment (LPE) 0.8 0 50 100 150 Samples 200 250 300 200 250 300 (e)Desired segment (RLRD) 0.8 0.6 0.6 0.4 0.4 0.2 0.2 Ampl mvolt Ampl mvolt 0 0 -0.2 -0.2 -0.4 -0.4 -0.6 0 50 (c) 0.7 100 150 Samples 200 250 -0.6 300 0 50 Desired segment (LPE) 100 150 Samples 0.6 0.5 0.4 0.4 0.3 Ampl mvolt 0.2 0.2 Ampl mvolt 0.1 0 0 -0.1 -0.2 -0.2 -0.3 ing of ultrasonic signals and its application to determine characteristics for a given material, Submitted 27 07 96 at Material Evaluation journal, 1711 Arlingate Lane, POB 28518, OH, USA. [4] S. Femmam, N.K. M'sirdi, Application of change de- (f)Desired segment (RLRD) 0.8 0.6 0 50 100 150 200 Samples 250 300 350 400 -0.4 0 50 100 150 Samples 200 250 300 Figure 2. Desired segments used in SR method 5 [2] M. Basseville, P. Flandrin, N. Martin, Signal segmentation, Traitement du signal, 9, Suppl¶ement au N 1, pp., 115-147, 1992. Desired segment (RLRD) 1.5 1 and its application to determine Q for rock mass. Int. J. Rock. Mech. Min. Sci. & Geomech. Abstr. Vol. 27, N± 1, pp. 33-41, 1990. CONCLUSION The detection, with diagnosis, of abrupt changes in ultrasound signal characteristics requires, a ¯ne study of the signal of the changes, and consists of the study of the system using a convenient de¯nition and tools, which allow to build the adequate "residuals" for testing the presence of a precise type of change. This paper describes the performances of the segmentation by use of the nonstationarity detection based on the threshold analysis of the LPE and the RLRD algorithms, for the ultrasound signals. The latter are used for characterization (determination of the quality factor in nondestructive evaluation), perception, and diagnosis of materials. Furthermore the RLRD method gives better results compared to the LPE one, since the delay is less for the same applied ultrasound signal and hence a precise segmentation. The RLRD is very sensitive either for the positive or negative jumps because of the estimation of the jump characteristics (amplitude and position), the detection depends essentially on the instantaneous value of the signal at the instant jump. tection technique to ultrasound signal processing. Use of spectral parametric estimation, time-frequency and wavelets, 30th IEEE SSST, March 8-10, 1998, West Virginia Univ. Morgantown, USA. [5] R. Ramdani, N.K. M'sirdi, Change detection statistical tests in non stationary signal, European Journal of Diagnosis and Safety in Automation, Volume 4, N± 2, pp. 229-271, 1994. [6] H. Tjokronegoro, Estimation adaptative des paramµetres de systemes variant dans le temps et detection de ruptures, Thµese de doctorat de INPG 90. [7] S. Femmam and N.K. M'sirdi, Application of signal segmentation and parametric estimation to determine material characteristics. IEEE, CESA98, IMACS Hammamet, Tunisia, April 1-4 1998 . [8] Femmam, N.K. M'sirdi, Comparison of the performances of spectral parametric estimation, time frequency, time scale, and segmentation with detection of abrupt changes methods in non-destructive evaluation, 3rd IFAC workshop On Line fault detection and supervision in the chemical process industries. 15-16 June 1998, Lyon, France (Accepted).