Methods of Track Recognition

In general, all track recognition methods can be divided into three classes: local, global and semi-global.

Local methods, also referred to as track following methods, need a starting initial set of track parameters for a track candidate called a ``seed''. These methods usually employ the Kalman filter with its advantages already at the track recognition stage. Given a seed, the algorithm follows the track by trying to find the next hit and improves the track parameters recursively with each new hit added. The method splits the track whenever more than one hit is observed in the neighborhood of the predicted hit location. In order to keep the number of simultaneously propagated track branches at a reasonable level, the algorithm must discard some of them relying upon a quality index of the track. Usually such an index is simply a weighted sum of the $\chi^2$ of the track and a penalty on the number of ``faults'', i.e. cases when the algorithm could not find a hit in a detector plane.

The reconstruction package RANGER employs so-called concurrent track evolution approach which can serve as a good example of local track recognition methods. As was pointed out in [#!ranger!#], this algorithm is quite sensitive to detector efficiency and hit resolution. Above $\epsilon_{HIT} = 95$%, the hit inefficiency is well compensated by the algorithm, while smaller hit efficiencies lead to sizeable losses in the fraction of detected particles. In the course of the track following procedure, RANGER decides to discard some track candidates using a $\chi^2$-based quality index. Therefore the detector resolution becomes a crucial point for the ability of RANGER to separate real tracks from ghost tracks. At bad detector resolution and large track density RANGER can provide a reasonable track reconstruction efficiency and ghost rate only by allowing a higher number of simultaneously explored track branches. This property of RANGER makes the computing time in case of bad detector resolutions grow excessively due to the dramatic increase of hit cobinations to be evaluated.

Global methods of track recognition use a parametric description of a track by a set of its parameters like slopes and offsets. Once the track model and detector measurement model are given, all hits in the detector can be projected into the track parameter space creating a complex density distribution with many local maxima. In this case the track recognition becomes a search for the local maxima corresponding to tracks. For a numerical implementation the density distribution is approximated using a multidimensional grid introduced in the track parameter space. The global methods are essentially maximum likelihood algorithms of parameter estimation. This property makes them, in principle, the most robust techniques for pattern recognition for simple geometries which allow parameterization, for instance, straight lines and circles.

One of the well-known global methods is Hough transform which was implemented in the reconstruction package TEMA [#!tema!#].

A clear disadvantage of global methods is that they require an explicit track model, which makes them quite sensitive to random perturbations of the track caused, for example, by multiple scattering. Another problem arises from the grid approximation, since the separation of tracks with similar parameters depends on the cell size of the grid. Due to this fact any attempt to improve such separation leads to an increase in the number of grid nodes which, in turn, moves memory and CPU consumption beyond feasibility.

The drawbacks of the global approach for track recognition are improved in semi-global methods which try to enhance the efficiency of global methods by local formation of space-points or short track segments in neighbored detector planes. The algorithm employed in the package OTR/ITR-CATS described in this chapter belongs to the semi-global methods combining features of cellular automata for track recognition with the advantages of the Kalman filter for track fitting. In the next section we describe the basic principles and some details of track reconstruction techniques implemented in the CATS package.