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.

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 z_{k}, it is
extrapolated to plane z_{k+1} by means of
a extrapolation equation (eq.3 appendix). The estimate at plane z_{k+1}
is then computed as the weighted mean of the predicted state vector and
of the measurement at plane z_{k+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 **F**_{k} = f, **H**_{k}
=1, for all k, i.e. assume the following state and measurement equations:

x_{k+1 }= f x_{k}+
w_{k }(1)

m_{ k} = x_{k}
+ 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 m_{k}
is affected by the noise v_{k} depending by
the resolution of the detector.

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

x_{k+1 }=
x_{k+1|k
+ }K_{k+1}[m_{k+1}
- x_{k+1|k}] (3)

p_{k+1} = [1- K_{k+1}]
p_{k+1|k }(4)

where K_{k+1} = p_{k+1|k}
[p_{k+1|k} + s_{v}^{2}]^{-1}
(5)

with p_{k+1|k }= f^{2}
p_{k }+ s_{w}^{2}
(6)

and x_{ k+1|k}= f
x_{k }(7).

In fig.4 is shown the block diagram of the described algorithm. At the
beginning the initial x_{0} and p_{0} 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 x_{k+1}(the
values could represent the track position with a high noise), a measurement
m_{k+1} and the estimate x_{k+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
p_{k+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 (x_{k+1}-x_{k+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 x_{k+1}
and the p_{k+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 p_{k+1|k}), VAR_NOISE (equivalent
to s_{v}^{2})
and one output: VAR_X_POST (equivalent to p_{k+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 x_{k+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**(z_{k}) = **x**_{k+1}
= **f**_{k}(**x**_{k})
+ **w**_{k} (1)

where:

- **f**_{k} is the track propagator
from detector k to detector k+1;

- **w**_{k} is a random variable that
incorporates a random disturbance of the track between z_{k}
and z_{k+1}.

Often the state vector **x**_{k} is
not observed directly. In general the observable are a function of the
state vector, corrupted by measurement noise:

**m**_{k} = **H**_{k}**x**_{k}
+ **v**_{k} (2)

where:

- **m**_{k} is the vector of the observations
at z_{k};

- **v**_{k} is a random variable that
incorporates a random disturbance of the measure.

It will be assumed in the following that all **w**_{k}
and **v**_{k} are independent random vectors
having mean 0 and a finite covariance matrix: cov(**w**_{k})=**W**_{k},
cov(**v**_{k})=**V**_{k}.

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:

**x**_{k+1|k}
= **F**_{k} **x**_{k}
(3)

**P**_{k+1|k}
= **F**_{k }**P**_{k}**F'**_{k}
+ **W**_{k} (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;

- **W**_{k} is the covariance matrix
cov(**w**_{k}).

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:

**x**_{k+1} = **x**_{k+1|k}
+ **K**_{k+1} [**m**_{k+1}
- **H**_{k+1} **x**_{k}]
(5)

**P**_{k+1} = **P**_{k+1|k}-
**K**_{k+1} **H**_{k+1}**P**_{k+1|k
}(6)

where

**K**_{k+1} = **P**_{k+1|k}**H'**_{k+1}
[**V**_{k+1} + **H**_{k+1}
**P**_{k+1|k}**H'**_{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*