next up previous contents
Next: Simulation Results Up: On-board tracks reconstruction Previous: Event reconstruction in pair   Contents

The ''Kalmaex Algorithm''

In order of find and fit tracks a Kalman filter-smoother algorithm [Kalman, 1960], [Frühwirth, 1987] has been developed. Unlike traditional pattern recognition algorithms, this technique always progressively updates the track-candidate information during the track-finding process, predicts as precisely as possible the next hit to be found along the trajectory. This capability is used to merge into an unique recursive algorithm the track-finding procedure and the fitting of track parameters.
This technique satisfies two crucial requirements for an on-board reconstruction: it provides good results and it don't need much CPU time, it is in fact able to perform a tracks finding and fitting with a little number of basic operations.
In the Kalman filter formalism the electron trajectory is handled as a evolving system, the planes are the instants of this evolution in which it is acquired information on the system. The coordinates of the vector ($ p_{k} $), which describe the system at the plane k, are the position ( $ x_{k} $ ) and the tangent of track direction ( $ \tan\theta_{k} $ ) . The Kalman filter is a process parted in two step, called Filtering and Smoothing. SmoothingI^2B^2BܱB>ð. ¥2 0x(1 ì±Bs*$)?>H`!  Õ1  Ô ø- HÀ+ _def^2B$1qÞ!emÞl 11`:utf8:utf81/Y#åtex2html_wrap_inline The evolution law of the state vector is :

$\displaystyle p_{k}= F p_{k-1} + w_{k}$ (4.1)

where F is the matrix that operate the geometrical projection from a plane to next, and $ w_{k}$ is the deviation due to multiple scattering. This effect is described by matrix the $ Q$

$\displaystyle Q = cov (w_{k}) %%= \left(\begin{array}{cc} $ (4.2)

The errors associate to $ p_k$ are described by the covariance matrix :

$\displaystyle C_{k}= cov (p_{k}-p_{k}^{true})$ (4.3)

where $ p_{k}^{true}$ contain the true values of system at plane k .
At every plane we have a measure of particle passage ( $ m_{k} $ ), the measurement is described by the following relation:

$\displaystyle m_{k} = H p_{k} + \mu$ (4.4)

where H is the transformation from vector $ p_{k} $ to the measure. $ \mu $ is the measurement error described by matrix:

$\displaystyle V = cov( \mu ) = \left( \begin{array}{c} \sigma^{2} \\ \end{array} \right)$ (4.5)

The estimate of system vector is articulated in three steps called Prediction, Filtering and Smoothing.
Former make a projection of the vector from plane k-1 to plane k . This correspond to a prediction of more probable state of the system at plane k made from the states on previous planes.

$\displaystyle p_{k}^{proj} = F p_{k-1}$ (4.6)

the error on $ p_{k}^{proj}$ is a combination of the errors on $ p_{k-1}$ (projected at plane k) and the multiple scattering effects

$\displaystyle C_{k}^{proj} = F C_{k-1} F^{T} + Q$ (4.7)

A measure on plane k is an independent information of the state vector on plane k,which can be combined with $ p_{k}^{proj}$ with a weight inversely proportional to the respective errors:
$\displaystyle p_{k} = \frac{(C_{k}^{proj})^{-1} p_{k}^{proj} + H^{T} V^{-1} m_{k}}{(C_{k}^{proj})^{-1} + H^{T} V^{-1} H} =$      
$\displaystyle = C_{k} [ (C_{k}^{proj})^{-1} p_{k}^{proj} + H^{T} V^{-1} m_{k} ]$     (4.8)

where:

$\displaystyle C_{k} = [ (C_{k}^{proj})^{-1} + H^{T} V^{-1} H ]^{-1}$ (4.9)

These operations constitute the filtering. In this way is possible to insert the measures on the next planes to create a track.
The smoothing process carry backward the information. This processing, analogous at the prediction and filtering process, is performed thought a gain matrix on the k-th plane:

$\displaystyle A_{k} = C_{k} F^{T} (C_{k+1}^{proj})^{-1}$ (4.10)

The state vector become:

$\displaystyle p_{k}^{smooth} = p_{k} + A_{k} (p_{k+1}^{smooth} - p_{k+1}^{proj} )$ (4.11)

that have an incertitude described by the matrix :

$\displaystyle C_{k}^{smooth} = C_{k} + A_{k} (C_{k+1}^{smooth} - C_{k+1}^{proj} )A_{k}^{T}$ (4.12)

Also these operation have to be performed iteratively, proceeding from the last plane to the first. The vector $ p_{k}^{smooth}$ on the generic plane k will contain the informations coming from all the available measurements. In the Kalman filter computation is also possible define a $ \chi ^2$ that gives a estimate of the fit goodness. The residuals on each plane are defined as:

$\displaystyle r_{k} = m_{k} - H p_{k}^{smooth}$ (4.13)

The matrix with which the residuals are weighted is:

$\displaystyle R_{k} = V - H C_{k}^{smooth} H^{T}$ (4.14)

It is then possible to calculate the $ \chi^{2}$ parameter:

$\displaystyle \chi _{k}^{2} = r_{k}^{T} R_{k}^{-1} r_{k}$ (4.15)

It is therefore possible to associate at every fitted track a total chi square ($ \chi^{2}$), given by the sum of the $ \chi _{k}^{2}$ on each plane. If the combination of the tracker hits gives rise to more than two possible tracks, the $ \chi^{2}$ can be used to choose the best pair of tracks In this way the Kalman filter is used not only as fitting technique, but also as tracks finder. Also the association between X and Y track projection can be performed on the basis of the $ \chi^{2}$.
next up previous contents
Next: Simulation Results Up: On-board tracks reconstruction Previous: Event reconstruction in pair   Contents
Andrea Giuliani 2005-01-21