Muon Segment Algorithm

Linked List Algorithm

(click here (Word, PDF, PS) for the latest printable version of this document)

 

July 16th, 2001: Latest results (Word, PDF, PS)

July 25th, 2001: Talk about LL reconstruction status (Powerpoint, PDF)

Introduction

Segment reconstruction is the part of the muon reconstruction code in which the pattern recognition is done. Hits in the muon wire chambers are combined, and a straight line, called a segment, is fitted through the hits. After this, the found segment is fitted with scintillators for timing information on the segment.

Input to the segment reconstruction is a collection of reconstructed hits; the output is a collection of segments. Originally, the segment reconstruction was based on a combinatorial segment reconstruction algorithm, written by Alexander Kozelov et al. However, multiple algorithms were desired, and a linked list algorithm was consequently developed.

 

Algorithm

For the segment reconstruction algorithm, the muon detector is split in two parts, each of which is again split in two parts:

This division is based on the difference in geometry between these parts. Both in the WAMUS and FAMUS, the wires are oriented along the y-axis (octants 0, 3, 4 and 7) or along the x-axis (octants 1, 2, 5 and 6). However, in the WAMUS, the wire plane is in the x-z or y-z plane, while in the FAMUS this is the x-y plane. To overcome this division, and still be able to have a common algorithm for all different parts, the pattern recognition is not done in the global system but in a local system. This requires a transformation of the reconstructed hits into the local system.

Another problem arises from the fact that the wire hits in the central system (PDT hits) and the wire hits in the forward system (MDT hits) behave differently. The PDT hits need to be updated with the angle to calculate the correct drift distance from the drift time, while the MDT hits need to be updated with a pixel hit for the axial position (and better drift time) information. This is reflected in the algorithm.

The algorithm is divided in 6 steps:

  1. Transformation of ‘global’ hits to ‘local’ hits
  2. Creation of links between hits
  3. Matching of links into local segments
  4. Fitting of local segments
  5. Filtering of local segments
  6. Fitting of local segments in one layer to local segments in other layers; transformation back to global system

Step 1: In the first step, we move the hits from their global coordinate system to a local coordinate system. This is done so we can work in a coordinate space where the drift ‘circles’ are in the x-y plane, and the wire direction is in the z direction. The plane in which the wires are located (the wire plane) is transformed such that it is parallel to the y-axis. The hits in the local system are called PDTSegmentHits for the PDT system, and MDTSegmentHits for the MDT system. Also, because of the left-right ambiguity of the wire hits, two local hits, one on each side of the wire, are created for each wire hit.

 

This is shown in the picture at the left. Here, the black lines are the wire planes (the wires themselves are running perpendicular to the plane of the picture), and the wires are depicted by the black crosses. The MC track is represented by the blue line, and the red circles are the drift circles. In reality, the equi-drifttime lines of the PDT's are not circles but look more like ovals. Each segment hit is placed on top or on the bottom of each of these circles.

The segment reconstruction is not done with all the hits at the same time. Instead, the wire hits are divided by MuoSectionIndex, where each MuoSectionIndex represents one wire chamber, or one octant of scintillators. Then, the segment reconstruction is done on all the wire hits with the same MuoSectionIndex, and all the scintillator hits. One might think of also dividing up the scintillator hits by MuoSectionIndex, however it seems to me that it would take more time dividing the scintillator hits than would be gained later.

Step 2: Now the links between the segment hits are made. These links are called LocalSegments, and consist of one or more segment hits. Each LocalSegment is created with two segment hits, taking all possible combinations of segment hits which satisfy the following conditions:

  1. Both segment hits are not coming from the same underlying wire hit (i.e. they are not positioned on the same drift circle);
  2. The separation between both hits along the y-direction is smaller than 20 centimeters; (currently, this 20 cm is hardcoded which is not good - it should be an rcp parameter). This might not be the best condition; a better test could be to take the direction from the origin to the hit, and compare the direction of the link with that. If it is not within certain parameters, the link can be rejected.
  3. Both hits are not on the same plane, except if they are coming from two neighboring hits, and one is on the top of a drift circle, while the other is on the bottom;

The last condition is made to make sure that segments are still found when less then 3 planes are hit. However, this still does not work when there are only two hits, one on one plane, the other on another plane. This is some work to do.

When a LocalSegment is made from two segment hits, a simple fit is done to calculate the position and direction of the segment. This is needed for the matching in step 3, but is also needed to get an estimate of the direction of the segment, which is needed for an accurate calculation of the drift distance for the LocalSegments in the central system. The created LocalSegment is assigned to the segment hit, which is at the utmost left of the LocalSegment.

Step 3: To explain the linking algorithm, I will use two terms: left and right. By left I mean everything with lower x (in the local system), and consequently, by right I mean everything with bigger x. Each LocalSegment is assigned to the segment hit that it contains that is at the utmost left position, I call that the left hit of the LocalSegment. The hit on the other side of the segment, on the end, is called the right hit of the segment. Now, to link all LocalSegments which have been made in the previous step, a loop is done over all the segment hits with the goal of creating a 'tree' of linked LocalSegments for each segment hit. A segment hit is called to have a tree if either it does not contain any LocalSegments, or each LocalSegment that the hit contains has already been tried to match with LocalSegments to the right. Starting with one, a loop is made over all the LocalSegments that are assigned to that hit. Each of these LocalSegments holds a segment hit at the end (the right hit). If this right hit already has a tree, the LocalSegment is matched with the LocalSegment assigned to that right hit, creating the tree for the left hit. If this right hit does not have a tree yet, the tree is recursively created for this hit before proceeding.

 

To test whether two LocalSegments are matching, one is extrapolated to the x-position of the second, and when the difference in y is smaller than s *(the sum of the error's on y of both segments), where s is a RCP tunable parameter, the LocalSegments are said to be matching. If this is the case, a new LocalSegment, which contains all hits of the two other LocalSegments, is created and fitted.

Step 4: After matching all the local segments, each of them is fitted again, this time also calculating the errors. The fit is done in two dimensions (x and y), z (the direction along the wire) is not taken into account. This is reflected in the c2. The c2 contained in the segment is the fitted c2 divided by the number of wire hits on the segment. Then, each segment is fitted with the scintillator hits, to determine the time of the segment, and in case of the forward system, better position. This matching is done by extrapolating the segment to the x position of the scintillator hit, and determining whether the difference in the y position of the segment and the scintillator is smaller than s *(sum of the errors in the y position of the segment and the y position of the hit). The first scintillator found this way is matched to the segment. Thus, there is no matching with the closest scintillator, just the first. If a match with a scintillator is found, the segment is refitted. In the refit, the position of the scintillator itself is not taken into account, it is only used to update the MDT hits on the segment and to give time information.

Step 5; After fitting all local segments, a filter is applied which keeps only those filters which fulfill certain requirements. These requirements are set by an RCP parameter, and include the following options:

The default value is to keep only the one best local segment. However, it often happens that there is a left-right ambiguity, which causes two segments to be found with the same c2. One of those is the correct one, while the other is incorrect. If only the 'best' segment is taken, the wrong one might be selected. Keeping the best two segments solves some of this ambiguity, but the track reconstruction has to be able to cope with this (it could make tracks for all segments, and not take the best).

Step 6: With the remaining segments a more global fit is done. Because of the lack of a magnetic field between the B and C layers, it is possible to match the local segments in the B layer with the local segments in the C layer and do a better fit with a bigger lever arm. In theory, it should also be possible to match segments in the same layer, but in a different system (e.g. PDT-A segments with MDT-A segments). However, because of the transformation step in Step 1, it is not directly possible to extrapolate a local segment in one subsystem to a local segment in another subsystem. Also, matching segments between octant could be done here, but is not implemented. Only B-C matching in the same region is done. This is implemented by looping over all segments in the B layer in one region, and match it with any other segment in the same region in the C layer. A match is found when the difference in the extrapolated y-position and the position of the C layer segment is smaller than s *(error on extrapolated y-position + error on C layer segments y-position). If this is the case, a new local segment is created, and refitted (with errors). The segments used to make this BC segment are still matched with other segments, but are discarded after that. Local segments which could not be matched with a partner in the other layer are kept. The remaining and the new segments are then transformed back to the global system by extracting the final Segment object.

 

 

Software implementation

This algorithm is also intended to run in the L3 framework, and therefor it has to adhere to a couple of restraints:

  1. The algorithm has to be fast - the total time budget for the muon reconstruction is 50 ms maximum. The segment reconstruction should not take more than 10 ms;
  2. No dynamic memory allocation.

Both these restraints were taken into account while writing the code. No dynamic memory allocation takes place (i.e. no new and delete calls), and copying of objects is tried to be kept at a minimum. However, the code in the current state is not fully optimized. For example, there is no reuse of objects. Current timing information can be found here (web page to be made).

To make the code as comprehensible as possible, it was tried to use a modular design, which reflects the steps as outlined in the algorithm above. There is one main segment builder, called LinkedListSegmentBuilder. This is the object that is given the hitcollections and returns the collection of found segments. It inherits from the SegmentBuilder interface, as it is defined in the package muo_segment, for easy compatibility with other segment reconstruction algorithms. When the LinkedListSegmentBuilder is called with the collections of hits, it first builds the segment hits for the local system (step 1). The segment hits are held in maps from MuoSectionIndices to segment hit collections, one map for the PDT segment hits, one map for the MDT segment hits. The MSC segment hits are just stored in a list. Note, that these maps (and the list) are the places where the segment hits are stored; in the rest of the algorithm, only pointers to these segment hits are used. This is done to avoid copying of these objects. After the coordinate transform to the local system, a loop is made over these maps. For the PDT segment hits, the PDTLinkedListSegmentBuilder is called which creates segments in the central region, for the MDT segment hits the MDTSegmentBuilder is called, which creates segments in the forward region (step 2 through 4). After the segments are found in each chamber (or MuoSectionIndex), these found segments are filtered by the object SegmentFilter, which removes those segments which do not fulfill the requirements as set in the RCP file (step 5). After filtering, the remaining local segments are stored in a collection. After the loop over the maps has finished, the SegmentMatcher is called with this collection to match the B and C segments and transform the local segments to the global system (step 6). The global segments are then returned by the LinkedListSegmentBuilder.

Both the PDT- and the MDTLinkedListSegmentBuilder hold two lists of LocalSegments, which are used in the segment reconstruction process. When the builders are called with the wire segment hits, scintillator segment hits and an empty list of LocalSegments, they execute the algorithm as outlined above. First they loop over all the wire segment hits, to make LocalSegments of two hits, and store them in the _segment list. After this, a loop is made over all the wire segment hits, to make the trees for each hit, and to create new LocalSegments from two other LocalSegments which are stored in the _matchedsegment list. All the segments in this list are then refitted, matched with scintillators, and returned.

Each LocalSegment holds lists of pointers to each different type of segment hit which are lying on the segment. LocalSegments can be created in four different ways: from two PDTSegmentHits, two MDTSegmentHits, two other LocalSegments or by using the copy constructor. When they are created from two hits, a simple fit without errors is done to get a first estimate of the angle of the segment. For these two constructors, it is possible to also pass an angle of the segment, to make this initial fit better by using the updated positions of the segment hits (and make the first estimate a 'second' estimate). When the LocalSegments are matched in the PDT- and MDTLinkedListSegmentBuilder, new LocalSegments are created by calling the constructor with the two LocalSegments which are being matched. This constructor takes all the hits from both LocalSegments, inserts them in the correct lists, makes sure there no hits are listed double, and sorts the lists on ascending x-position of the hits. Then, it does a simple fit, taking the angle of one of the LocalSegments as an initial angle, to get better positions of the segment hits. The LocalSegment offers two methods to fit using the hits lying on the segment, one simple fit (method fit() ) which does not calculate the errors and the c 2, and one fit (method fiterror() ) which updates the MDT segment hits with the possible scintillator position, and calculates the error and the c 2. The last method of interest in this class is the method getSegment(), which makes the transformation from a LocalSegment to a Segment.

Each of the SegmentHits holds a list of pointers to LocalSegments which are to the right of the hit and start from that particular hit. These segment hits are created from a hit pointer, and internally use a GeometryHit (see package muo_hit) to access positions, drift distances and axial distances of the hit. They are in a sense just a wrapper around the global hit so it can be used in the local system.

 

How to run the Linked List algorithm

As from t01.32.00, the Linked List algorithm is the default algorithm for the segment reconstruction. Therefor, no RCP variables have to be changed to run the software. To change the parameters which steer the reconstruction, the file muo_segmentlinkedlist/rcp/MuoSegmentLLReco.rcp has to be modified. In here, the following parameters are found:

The following are variables used when matching two local segments into one new local segment:

double pdt_max_angle_diff = 0.2; // Maximum angle between local segments, in radians

double pdt_max_y_diff = 1; // Maximum difference in position on matching plane, in cm

double mdt_max_angle_diff = 0.1; // Maximum angle between local segments, in radians

double mdt_max_y_diff = 1; // Maximum difference in position on matching plane, in cm

These are the variables determining which segments are kept, based on some filter. There are three filters possible:

All these options are possible for both the pdt and the mdt system.

Parameters for matching B and C segments into BC segments:

double match_max_angle_diff = 0.05; // Maximum angle between B&C segment, in radians

double match_max_r_diff = 1; // Maximum difference in position on matching plane, in cm

double nsigma_segmatch = 5; // Max number of sigma's when matching BC segments

double nsigma_scintmatch = 5; // Max number of sigma's when matching segments with scintillators

 

Parameters to bail out when the reconstruction cannot be done:

int max_pdt_hits = 30; // Maximum number of PDT hits per module before ignoring all hits in the module (and not doing reconstruction in that module)

int max_mdt_hits = 30; // Maximum number of MDT hits per module before ignoring all hits in the module (and not doing reconstruction in that module)