CEB/NT-96/04
2 April 1996

 
 
 
 
 
 
 
 

FUZZY TECHNIQUES FOR PULSE DISCRIMINATION AND

TRACK RECONSTRUCTION
 
 

I.D’Antone
 
 

Istituto Nazionale di Fisica Nucleare

Via Irnerio 46, 40126 Bologna, Italy



 
 
 
 
 
 

ABSTRACT



As requested by the collaboration of the INFN experiment named FUZZY, some applications related to the particle physics experiments have been studied to apply in realistic situations a home made VLSI digital fuzzy processor. To evaluate the fuzzy logic potentiality in the pattern recognition problems, two cases are considered. In the first the fuzzy logic is applied to discriminate two particles following the classical pulse shape discrimination (PSD) technique. In the second case a simple tracking of a trajectory of a particle released in several planes of a detector has been considered. The fuzzy logic has been used to extrapolate the track parameters from different planes. It has been compared with a classical extrapolation method, the Kalman filter. The paper describes a "toy model" but it has been introduced to stimulate ulterior studies in this topic. The described approaches could be useful in trigger systems for the selection of interesting events; however, some considerations about realistic multiplicity, handling of ambiguities and so on, must be considered for a more thorough study.
 
 


 Charts


CENTRO DI ELETTRONICA

ISTITUTO NAZIONALE DI FISICA NUCLEARE

Sezione di Bologna

1. INTRODUCTION
 
 

Fuzzy logic is a superset of conventional Boolean logic that has been extended to deal with such a kind of uncertainty and imprecision.

It is a formal instrument that partially closes the gap between human reasoning and the computer world because the reasoning in a processor is performed by rules expressed in a linguistic way (IF...THEN...rules).

Fuzzy logic is extensively applied to solve control problems and in pattern recognition. It has been applied to deal with uncertainty and imprecision due to measure errors and noise [1][2].

In the first case we suppose to specify a linguistic measure of two features of pulses released in a spectrometer and we discriminate some particles with the well-known PSD (Pulse Shape Discrimination) technique.

In the second case a simple tracking of a trajectory of a particle released in several planes of a detector has been considered. One method used for track reconstruction in future experiments is based on the extrapolation of track segments from one detector layer to another [3][4]. The particle candidate initiates a track search in tracking chambers. In one of the chambers the candidate defines a search region RoI (Region of Interest). If a hit is found, that is if the difference between measured and extrapolated values of position and angle is below a specific threshold, a refined RoI is found for the next tracking chamber. The process is repeated until a search is unsuccessful, or a valid candidate is established. Adopting the fuzzy approach to solve the problem, the fuzziness of the rules accounts for the uncertainty in the tracking process. To compare the fuzzy tracking to classical recursive technique we chose the Kalman filter [5] as a benchmark because of its many optimal linear-system properties.
 
 
 
 

2. PULSE DISCRIMINATION WITH FUZZY LOGIC
 
 

Supposed to specify a linguistic measure of two features of pulses released in a spectrometer, some particles could be discriminated with a fuzzy version of the well-known PSD (Pulse Shape Discrimination) technique.

We assume the pulses released by two particles can be represented with the following model:
 
 

P = (A/ tm) * t * exp(-t / tm) (eq.1)
 
 

where the time constant tm and the amplitude A are different for the two particles (fig1a). With a suitable gate we can evaluate for each pulse the area of the pulse, related to the energy E, and the tail T of the pulse, related to the time constant of the detection process. These two features E and T can be used to discriminate the particles because a two-dimensional plot E-T shows two distributions in separate regions, one for each particle (fig.1b).

Supposed to specify linguistically the measures of energy and tail, we define some fuzzy sets, for example low, medium, high for the first variable and some fuzzy sets, for example short, medium, long for the second variable. If we decide that a high energy is E1, as indicated in the fig.2, the closer a certain energy is to E1, the higher is its membership degree to the high energy. All the Membership Degrees associated to a fuzzy set generate a shape called "Membership function" MF. Usually the MF are triangular, trapezoidal, gaussian and so on. The membership degree evaluation of an input variable to the input fuzzy sets is called "fuzzification process".

After the fuzzification phase, fuzzy reasoning is performed to infer a fuzzy value for each output variable. For example in the neutron-gamma ray discrimination the output can be the variable P with two fuzzy sets defined neutron and gamma.

The inference is performed following the production rules representing the knowledge of the fuzzy system mapping the inputs to its output, for example:
 
 

IF (E is medium AND T is long)

THEN (P is neutron)

etc.
 
 

where E, T are the input variables and P is the output variable. Each rule covers one region in the two-dimensional plot E-T.

For each rule the antecedent matching grade is evaluated: a value. The AND of two terms in the antecedent is performed taking the minimum (MIN) of the two membership degrees. The result of the fuzzy inference is obtained by truncating the membership function for the consequent (max-min method) or scaling the membership function (max-dot method) using the a value. As a result, the final global fuzzy set is obtained by ORing individual results of a fuzzy inference taking the maximum (MAX) value.

Finally a result of a fuzzy inference is obtained as a deterministic value by calculating the centre of gravity of the final global fuzzy set (defuzzification process). In our example we have an output value showing with which certainty degree P is a neutron or a gamma ray.

In conclusion, the fuzzy inference is possible with a processor having building blocks performing operations like MIN, MAX and centre of gravity calculations. Actually, efficient architectures are studied to realize hardware fuzzy processors[6].
 
 
 
 

3. Tracking with fuzzy processors
 
 

In the following the fuzzy logic is applied to perform a simple tracking of a trajectory of a particle released in several planes of a detector. The fuzzy logic is used to extrapolate the track parameters from different planes.

If the tracking is used for triggering in the first or second level of the data acquisition system, it is implemented in multiple processors, each responsible for a certain section of a tracking chamber.

The most used prediction algorithm is based on the Kalman filtering[5] that has been considered because it is the optimal recursive estimator in the sense that it minimizes the mean square estimate error. If the tracking is submitted to a gaussian random disturbance and the measurement operation is affected by a gaussian noise, the Kalman filter is the optimal estimator; no nonlinear filter can do better. In other cases it is simply the optimal linear filter.

In the Kalman filter the uncertainty due to noise effects are modelled with random variables having a certain variance.

It is possible to apply filtering techniques to track fitting regarding the track in space as a dynamic system.

The basic idea of the Kalman Filter is very simple. If there is an estimate of the state vector at plane zk, it is extrapolated to plane zk+1 by means of a extrapolation equation (eq.3 appendix). The estimate at plane zk+1 is then computed as the weighted mean of the predicted state vector and of the measurement at plane zk+1, according to the measurement equation.

If the state vector, which is the vector of track parameters, is known on surface k, the trajectory can be extrapolated to surface k+1 with an uncertainty defining the Region of Interest RoI (fig.3).

We show on a simple example the principal features of track fitting with the Kalman filter and with a Fuzzy Estimator. Assume the one-dimensional model with Fk = f, Hk =1, for all k, i.e. assume the following state and measurement equations:

xk+1 = f xk+ wk (1)

m k = xk + v k. (2)

This could be the model of the position evolution of a track in a detector, in which the f parameter is the slope of the line. The measurement mk is affected by the noise vk depending by the resolution of the detector.

In this simple model the state and variance will be propagated with:

xk+1 = xk+1|k + Kk+1[mk+1 - xk+1|k] (3)

pk+1 = [1- Kk+1] pk+1|k (4)
 
 

where Kk+1 = pk+1|k [pk+1|k + sv2]-1 (5)

with pk+1|k = f2 pk + sw2 (6)

and x k+1|k= f xk (7).
 
 

In fig.4 is shown the block diagram of the described algorithm. At the beginning the initial x0 and p0 parameters must be assigned. These are approximated values estimated or derived with other information.

The performance of the filter can be evaluated heuristically by comparison of the actual state with the contaminated measurements and the state estimate.

In fig.5a the actual state xk+1(the values could represent the track position with a high noise), a measurement mk+1 and the estimate xk+1|k are shown. This data is satisfying in that the estimator essentially takes the middle ground between the measurements and the actual state. The variance defines the width of the RoI in the layer k+1.

Starting with large values for the initial variance, with a few cycles pk+1 decreases (fig.5b) because, with new measures, decreases the uncertainty. Then the RoI for the next estimate is smaller.

Furthermore we observe that, when the trajectory has abrupt changes, the error (xk+1-xk+1|k) increases (fig.5c) but it in a few steps is reduced again. Control systems, based on these prediction techniques, are diffuse in real-time target-tracking systems.

We have realized a fuzzy estimate considering the same problem. A fuzzy system can be used to evaluate the state xk+1 and the pk+1, i.e. the RoI, in the next layer k+1.

To compare the KF with the fuzzy approach, a block representing a Fuzzy RoI Estimation Processor has been realized. It contains two inputs: VAR_X_PRE (equivalent to pk+1|k), VAR_NOISE (equivalent to sv2) and one output: VAR_X_POST (equivalent to pk+1).

Each input variable has been mapped into three sets of gaussian membership functions as shown in the fig.6a. The output has been mapped into five triangular membership functions (fig.6b).

The knowledge base has been written considering some heuristic rules like these:
 
 

-VAR_X_POST is lower than VAR_X_PRE or VAR_NOISE,

-VAR_X_POST is near to the lowest value between VAR_X_PRE and VAR_NOISE

-and so on.
 
 

Then, some rules have been written in the language of the fuzzy processor as follows:
 
 

-IF VAR_X_PRE IS low and VAR_NOISE IS high THEN VAR_X_POST IS low

-and so on.
 
 

The inputs to output mapping generates a three-dimensional surface. It maps VAR_NOISE and VAR_X_PRE to VAR_X_POST and is represented in fig.7a, where it is compared with the surface realized with a KF, given by the eqq.4, 5, 6 (fig.7b).

Moreover, the Fuzzy State Estimation Processor running the xk+1 estimate has been realized. It has three input variables: K, M, X_PRE and one output: X_POST. The input K has been mapped into two triangular membership functions (fig.8a), while the inputs M and X_PRE and the output X_POST have been mapped into three gaussian membership functions (fig.8b).

The knowledge base has been written considering that:
 
 

-if K is high then X_POST is closed to M

-if K is low then X_POST is closed to X_PRE.
 
 

Here the surface mapping inputs to output is four-dimensional, which we cannot plot. We plot a family of three-dimensional surfaces indexed by constant values of the fourth variables. In fig.8c is shown the surface K, M to X_POST, with X_PRE constant. It is equivalent to the surface realized with a KF and given by the eqq.3, 5, 6.
 
 

To evaluate the performance of the Fuzzy RoI Estimation Processor we have substituted the eq.4, 5, 6 in the KF with the fuzzy processor. The results are shown in fig.9 where the actual states, the measurements and the state estimate are represented. We note that with the Fuzzy RoI Estimator Processor the middle ground between the measurements and the actual state is taken, as performed by the classical Kalman filtering.

The parameters of the membership functions, i.e. the shape, the width or the overlap, have been calibrated to achieve good performance. By using some modern "rule generators" it is possible to modify these parameters, independently for each membership function, to reach better performance.

Furthermore we have substituted the eq.3, 5, 6 in the KF with the Fuzzy State Estimation Processor. In fig.10 are shown the actual states, the measurements and the state estimate. We observe that this fuzzy application gives a higher filtering effect in comparison with the optimal filtering. By a learning process the membership function parameters can be also modified to have better performance.

The K value depends only by VAR_X_PRE and VAR_NOISE, then can be obtained from the Fuzzy RoI Estimation Processor. Then the Fuzzy State Estimation Processor could have the input K coming from the previous described Fuzzy RoI Estimation Processor. Then, with these two fuzzy processors is possible to carry out the complete estimate; see fig.4 for comparison.
 
 
 
 

CONCLUSION
 
 

The fuzzy logic has been applied to discriminate two particles following the classical pulse shape discrimination (PSD) technique. Some "rule generators", using neural nets[7][8] and genetic algorithms[9], are under development to obtain the best compromise between the rules and the position and shape of the membership functions. With learning, in this particle discrimination problem, the membership functions move to cover in the best way the two scissors regions concerning the two particles and to find the best discrimination line. More MFs for each variable allow a fine adaptation to the separation line.

We have seen furthermore that the estimate performed with fuzzy processors is feasible, with performance near to the optimal classical methods. The advantage of this approach is that, with a hardware fuzzy processor having a few rules, it is possible to have a fast estimate. Applications in trigger system are suggested, because the fast tracking, based on the extrapolation of track segments from one detector layer to another, is always more used; the fuzziness of the fuzzy rules accounts for the uncertainty in the tracking process. The paper describes a "toy model" but it is introduced to stimulate ulterior studies in this topic; some considerations about realistic multiplicity, handling of ambiguities and so on, must be considered for a more complete study.

A VLSI digital full programmable fuzzy processor has been realized at the INFN Bologna[6] to apply the described methodology and to obtain an experimental verification.
 
 
 
 
 
 

References
 
 

[1] Lofti A. Zadeh, "Outline of a new approach to the analysis of complex systems and decision processes, IEEE Trans. on Systems, Man and Cybernetics, Vol.3, pp.28-44, 1973.
 
 

[2] R. Yager, "Fuzzy Sets and Approximate Reasoning in Decision and Control", IEEE Transaction on Fuzzy Systems, 1992
 
 

[3] HERA-B Proposal, DESY_PRC 94/02, May 1994.
 
 

[4] CMS Technical Proposal, CERN/LHCC 94-38, 15 December 1994.
 
 

[5] R.Fruhwirth, "Application of Kalman filtering to track and vertex fitting", Nuclear Instruments and Methods in Physics Research A262 (1987) 444-450.
 
 

[6] I.D'antone et al., "Architecture of a 50 MFIPS Fuzzy Processor and the related 1mm VLSI CMOS Digital Circuits", Fourth International Conference on Microelectronics for Neural Networks and Fuzzy Systems, September 26-28, 1994, Turin, Italy.
 
 

[7] INFORM GmbH, "Fuzzy TECH - NeuroFuzzy Module", Aachen, Germany, 1992.
 
 

[8] B.Kosko, "Neural Networks and Fuzzy Systems", Prentice-Hall, USA, 1992.
 
 

[9] D.E.Goldberg, "Genetic Algorithm in Search, Optimization and Machine Learning", Addison-Wesley, 1989.

APPENDIX: KALMAN FILTERING
 
 

The state vector of the dynamic system describing a track is identified with a vector x of 5 parameters identifying the track in each point of its trajectory as follows

x = [r, f, dr/dz, df/dz, 1/p]

where: r, f, z are the cylindrical coordinate with the z axis oriented along the beam in the detector and p is the absolute value of the momentum of the particle. A track in the vacuum is represented by five initial values on a fixed reference surface, the so-called track parameters: two spatial coordinates (r, f), two direction angles (dr/dz, df/dz), and a curvature (or 1/p with the proper sign).
 
 

The dynamic system can be described as:

x(zk) = xk+1 = fk(xk) + wk (1)
 
 

where:

- fk is the track propagator from detector k to detector k+1;

- wk is a random variable that incorporates a random disturbance of the track between zk and zk+1.
 
 

Often the state vector xk is not observed directly. In general the observable are a function of the state vector, corrupted by measurement noise:

mk = Hkxk + vk (2)
 
 

where:

- mk is the vector of the observations at zk;

- vk is a random variable that incorporates a random disturbance of the measure.
 
 

It will be assumed in the following that all wk and vk are independent random vectors having mean 0 and a finite covariance matrix: cov(wk)=Wk, cov(vk)=Vk.
 
 

In the presence of a magnetic field the track propagator is non-linear (eq. 1). Such a system can be linearized so that the state vector and its covariance matrix are propagated towards the next measurement layer:

xk+1|k = Fk xk (3)

Pk+1|k = Fk PkF'k + Wk (4)
 
 

where

- x k+1|k is the predicted parameter vector at layer k+1;

- F k is the extrapolation matrix from layer k to k+1;
 
 

- P k+1|k is the predicted covariance matrix at layer k+1;

- Wk is the covariance matrix cov(wk).
 
 

The formalism k+1|k denotes the one-step prediction estimate. A new estimate in plane k is computed, adding a correction term to the prediction, with the following equations:

xk+1 = xk+1|k + Kk+1 [mk+1 - Hk+1 xk] (5)

Pk+1 = Pk+1|k- Kk+1 Hk+1Pk+1|k (6)
 
 

where

Kk+1 = Pk+1|kH'k+1 [Vk+1 + Hk+1 Pk+1|kH'k+1]-1 (7)
 
 

is the Kalman gain matrix.

FIGURE CAPTIONS
 
 

Fig.1. Pulses released by the two particles to discriminate: a) amplitude versus time, b) simulation of 100 values tail-energy for each particle.
 
 

Fig.2. Membership functions mapping the two variables T and E. In the T-E plane is indicated the discrimination line obtained with the fuzzy rules developed.
 
 

Fig.3 Tracking concept used by the extrapolation method.
 
 

Fig.4 Block diagram of one-step of the extrapolation algorithm.
 
 

Fig.5 Various sequences in the optimal filter: a) state, measurement and state estimate, b) transient variance and gain in the first 10 steps, c) actual state -estimate state error.
 
 

Fig.6 Membership functions used for the inputs and the output of the Fuzzy RoI Estimation Processor.
 
 

Fig.7 Surface mapping the inputs to the output: a) in the Fuzzy RoI Estimation Processor b) in the optimal filter.
 
 

Fig.8 Membership functions used for the inputs and the output of the Fuzzy State Estimation Processor and the surface mapping two inputs to the output.
 
 

Fig.9 Various sequences in the Fuzzy RoI Estimation Processor: a) state, measurement and state estimate, b) transient variance and gain in the first 10 steps.
 
 

Fig.10 Various sequences in the Fuzzy State Estimation Processor: a) state, measurement and state estimate, b) transient variance and gain in the first 10 steps.
 
 







Page edited by Bisi Fabio