Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://acat02.sinp.msu.ru/presentations/fruehwirth/talk.pdf Äàòà èçìåíåíèÿ: Mon Jun 24 13:47:28 2002 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 20:14:04 2012 Êîäèðîâêà:

A review of fast circle and helix fitting
R. Fruhwirth (HEPHY, Vienna, Austria) ¨ A. Strandlie (CERN, Geneva, Switzerland) W. Waltenberger (HEPHY, Vienna, Austria) J. Wroldsen (GjÜvik University College, Norway)

ACAT 2002, Moscow, 26.6.2002


Outline Introduction and background Circle fitting Helix fitting Conclusion

R. Fruhwirth ¨

ACAT 2002, Moscow

2


Introduction and background
In a detector emb edded in a homogeneous magnetic field, the particle tra jectories are helices. Examples: Inner trackers in CMS and ATLAS. LHC track reconstruction methods have to be precise and fast The metho d of choice will very likely depend on the requirements of the actual physics analysis.

R. Fruhwirth ¨

ACAT 2002, Moscow

3


Introduction and background
Track fitting metho ds can roughly be divided into two separate categories: Precise and slow Approximate and fast Those of the latter category mainly work for 2D data -- i.e. data either coming from a 2D detector or pro jected data from a 3D detector

R. Fruhwirth ¨

ACAT 2002, Moscow

4


Introduction and background
The global least-squares metho d: Used for many decades in HEP exp eriments. Prop er treatment of elastic, multiple Coulomb scattering included in the method during the 70's. Close to optimal in precision, but may be computationally quite exp ensive with a large numb er of measurements and/or a large numb er of scattering devices.
R. Fruhwirth ¨ ACAT 2002, Moscow 5


Introduction and background
The Kalman filter: Recursive least-squares estimation. Therefore suitable for combined track finding and fitting Equivalent to global least-squares metho d including all correlations b etween measurements due to multiple scattering. Probably the most widely used metho d to day.
R. Fruhwirth ¨ ACAT 2002, Moscow 6


Introduction and background
Both the global LS fit and the Kalman filter may need previous knowledge of the track: as an expansion point (reference track) of the linearization procedure, for the computation of the multiple scattering covariance matrix. This is particularly imp ortant for tracks with large curvature (low momentum). Therefore fast preliminary fits are required.
R. Fruhwirth ¨ ACAT 2002, Moscow 7


Circle fitting
Some specialized methods for circle fitting: Conformal mapping -- maps circles through the origin onto straight lines Karim¨ metho d -- based on an approximate, aki explicit solution to the non-linear problem of circle fitting Riemann fit -- maps circles onto planes in space, results in exact linear fit in 3D

R. Fruhwirth ¨

ACAT 2002, Moscow

8


Circle fitting
Conformal mapping [1] Inversion in the complex plane: x y u= 2 , v= 2 2 x +y x +y
2

A circle through the origin is mapped on a straight line. the impact parameter of the line is inversely proportional to the radius of the circle.
R. Fruhwirth ¨ ACAT 2002, Moscow 9


Circle fitting
A circle with small impact parameter is mapped on a circle with small curvature (proportional to the impact parameter to first order). The latter circle can be approximated by a parab ola. Fast, linear fit of the coefficients of the parabola.

R. Fruhwirth ¨

ACAT 2002, Moscow

10


Circle fitting
2

1.8

1.6

1.4

1.2

1

0.8

0.6

0.4

0.2

Original circle Transformed circle Approx. parabola
-0.5 0 0.5 1 1.5 2

0 -1

R. Fruhwirth ¨

ACAT 2002, Moscow

11


Circle fitting
Karim¨ metho d [2] aki Under the assumption that the impact parameter is small compared to the radius: ||

an explicit solution to the non-linear problem can be found. An additional correction procedure gives very good final precision.

R. Fruhwirth ¨

ACAT 2002, Moscow

12


Circle fitting
The Riemann fit I [3] Based on a conformal mapping (stereographic pro jection) of 2D-measurements to 3D-points on the Riemann sphere:
2 xi = Ri cos i /(1 + Ri )

yi = Ri sin i /(1 + R )
2 2 zi = Ri /(1 + Ri )

2 i

R. Fruhwirth ¨

ACAT 2002, Moscow

13


Circle fitting

1 0.8 0.6 0.4 0.2 0 1 0.5 0 -0.5 -1 -1.5 -2 -1 -0.5 0 0.5 1

R. Fruhwirth ¨

ACAT 2002, Moscow

14


Circle fitting
Circles and lines in the plane map uniquely onto circles on the Riemann sphere. Since a circle on the Riemann sphere uniquely defines a plane in space, there is a one-to-one corresp ondence between circles and lines in the plane and planes in space.

R. Fruhwirth ¨

ACAT 2002, Moscow

15


Circle fitting
The Riemann fit I I [5] Non-conformal mapping of 2D-measurements to 3D-points on a cylindrical parab oloid:

xi = Ri cos i yi = Ri sin i zi = R
2 i

This mapping is even simpler.
R. Fruhwirth ¨ ACAT 2002, Moscow 16


Circle fitting
Again, p oints on a circle are mapped on p oints lying on a plane (but not on a circle). Thus, the task of fitting circular arcs in the plane is transformed into the task of fitting planes in space. This can be done in a fast and non-iterative manner. Moreover, there is no need for any track parameter initialization.

R. Fruhwirth ¨

ACAT 2002, Moscow

17


Circle fitting
A plane can be defined by a unit length normal vector nT = (n1 ,n2 ,n3 ) and a signed distance c from the origin. Fitting a plane to N measurements on the sphere or paraboloid requires finding the minimum of
N

S=

i=1

(c + n1 xi + n2 yi + n3 zi ) =

2

N i=1

d2 i

with respect to {c, n1 ,n2 ,n3 }.
R. Fruhwirth ¨ ACAT 2002, Moscow 18


Circle fitting
The minimum of S is found by choosing n to be the eigenvector to the smallest eigenvalue of the sample covariance matrix of the measurements. The distance c is given by the fact that the fitted plane passes through the mean vector of the measurements. The fitted parameters can then be transformed back to the circle parameters in the plane.
R. Fruhwirth ¨ ACAT 2002, Moscow 19


Circle fitting
The precision and the speed of the Riemann fit (RF) has been assessed by a comparison with a non-linear least-squares fit (NLS), a global linearized least-squares fit (GLS), the Kalman filter (KF), and the conformal mapping (CM). We show results from a simulation exp eriment in the ATLAS Transition radiation Tracker, with about 35 observations per track.
R. Fruhwirth ¨ ACAT 2002, Moscow 20


Circle fitting
Method NLS w/o initialization NLS with initialization GLS w/o initialization GLS with initialization KF w/o initialization KF with initialization CM (parabola fit) RF (circle fit) V
rel

trel 36.3 41.4 15.9 21.1 28.2 33.3 1.03 1.00

1.000 1.000 1.001 1.001 1.001 1.001 1.582 1.003

Red=Baseline
R. Fruhwirth ¨ ACAT 2002, Moscow 21


Circle fitting
The RF can be corrected for the non-orthogonal intersection of the track with the detectors. This is important for low-momentum tracks, but requires an iteration. Formulas for the covariance matrix of the fitted parameters have been derived [4].

R. Fruhwirth ¨

ACAT 2002, Moscow

22


Circle fitting
The RF can also deal with multiple scattering [5]: The cost function is generalized: S = dT V
-1

d

d is the vector containing the distances from the measurements to the plane. V is an approximate covariance matrix of these distances including correlations from multiple scattering.
R. Fruhwirth ¨ ACAT 2002, Moscow 23


Circle fitting
Again, the minimum of S with respect to the plane parameters defines the fitted plane. The normal vector of the plane is found in a similar manner as b efore -- only the building-up of the sample covariance matrix of the measurements is slightly mo dified. It is not straightforward to generalize any of the other circle estimators (conformal mapping, Karim¨ ) in this way. aki
R. Fruhwirth ¨ ACAT 2002, Moscow 24


Circle fitting
We have performed a simulation exp eriment in the ATLAS Inner Detector TRT. Four metho ds have been compared: The generalized Riemann fit The Kalman filter The Karim¨ metho d including the diagonal terms aki of the covariance matrix The global least-squares fit without contributions from multiple scattering in the covariance matrix
R. Fruhwirth ¨ ACAT 2002, Moscow 25


Circle fitting
5

4.5

4

Kalman filter Riemann fit Karimaki Global least-squares

Relative generalized variance

3.5

3

2.5

2

1.5

1

0.5

0

0

1

2

3

4 5 6 Transversal momentum (GeV/c)

7

8

9

10

R. Fruhwirth ¨

ACAT 2002, Moscow

26


Helix fitting
The circle fit can be extended to a helix fit by using the linear relation between the arc length s and z [6]. After the circle fit, the arc length between successive observations is computed. A regression of z on s (barrel) or of s on z (forward) gives the polar angle plus an additional coordinate. In disk type detectors the radial positions of the hits are predicted from the line fit, and the entire procedure is repeated.
R. Fruhwirth ¨ ACAT 2002, Moscow 27


Helix fitting
We have done a simulation exp eriment in a simplified model of the CMS Tracker. Three metho ds have been compared: Riemann Helix fit based on Riemann circle fit (RHF) Kalman filter (KF) Global least-squares fit (GLS)

R. Fruhwirth ¨

ACAT 2002, Moscow

28


Helix fitting
Multiple Scattering has been treated on different levels:
Level 0 1 2 3 Covariance matrix of multiple scattering None Approximate Exact, but no correlations between pro jections Exact, including all correlations Applies to All methods GLS, RHF GLS, RHF GLS, KF

When required (KF or level>0), a reference track has been computed by a preliminary RHF.
R. Fruhwirth ¨ ACAT 2002, Moscow 29


Helix fitting
10
3

Cylindrical detectors
Kalman 0 Global 0 Riemann 0

Relative genvar

10

2

10

1

10 0 10

0

10 p [GeV/c]

1

10

2

Generalized variance on level 0, relative to the KF on level 3
R. Fruhwirth ¨ ACAT 2002, Moscow 30


Helix fitting
Method Kalman filter Global fit Riemann fit Level 0 0 0 trel 0.98 0.97 0.70

Timing on level 0, relative to the KF on level 3

R. Fruhwirth ¨

ACAT 2002, Moscow

31


Helix fitting
Cylindrical detectors 1.5
Kalman3 Global 1 Global 2 Global 3 Riemann 1 Riemann 2

1.4

Relative genvar

1.3

1.2

1.1

1

0.9 0 10

10 p [GeV/c]

1

10

2

Generalized variance on level>0, relative to the KF on level 3
R. Fruhwirth ¨ ACAT 2002, Moscow 32


Helix fitting
Method Kalman filter Global fit Global fit Global fit Riemann fit Riemann fit Level 3 1 2 3 1 2 trel 1.00 1.08 1.38 1.38 0.84 1.16

Timing on level>0, relative to the KF on level 3

R. Fruhwirth ¨

ACAT 2002, Moscow

33


Helix fitting
These results have been obtained from the C++ implementation. The program is available from the authors on request. For disk detectors the Riemann helix fit is not comp etitive as an exact fit, because of the need to iterate, but still highly suitable as a preliminary fit for the KF or the GLS.

R. Fruhwirth ¨

ACAT 2002, Moscow

34


Conclusions
In the absence of multiple scattering, the Riemann circle fit is virtually as precise as either non-linear or linear least-squares estimators and much faster In the presence of multiple scattering, the Riemann circle fit is as precise as the Kalman filter over a large range of momentum and sup erior in precision to similar metho ds (Karm¨ aki, Conformal Mapping)
R. Fruhwirth ¨ ACAT 2002, Moscow 35


Conclusions
The Riemann helix fit is a viable alternative to conventional least-squares fits, esp ecially if multiple scattering can b e neglected. It is highly suitable as a fast approximate fit for generating a reference track for the Kalman filter or the global least-squares fit.

R. Fruhwirth ¨

ACAT 2002, Moscow

36


References
[1] V. Karim¨ Nucl. Instr. Meth. A 305 (1991) 187 aki, [2] M. Hansroul, H. Jeremie and D. Savard, NIM A 270 (1988) 498 [3] A. Strandlie, J. Wroldsen, R. Fruhwirth and B. Lillekjendlie, ¨ Comp. Phys. Comm. 131 (2000) 95 [4] A. Strandlie and R. Fruhwirth, ¨ Nucl. Instr. Meth. A 480 (2002) 734 [5] A. Strandlie, J. Wroldsen and R. Fruhwirth, ¨ Nucl. Instr. Meth. (in press) [6] R. Fruhwirth, A. Strandlie and W. Waltenberger, ¨ Nucl. Instr. Meth. (in press)

R. Fruhwirth ¨

ACAT 2002, Moscow

37