index

Status of the Implementation of Hough Tranformation on Phat

The goal of this study is the revival of the original PHOBOS tracking algorithm, Hough PR, which worked with 85% of efficiency (# of tracks found / # of findables) with few % level of ghost tracks (mis-identified tracks).

Simplified Geometry

The current geometry has missing layers. Rather complicate Hough algorithm will be needed to deal with this geometry correctly. To reach fast to our goal, I decided to simplify our geometry to be as close as to the old geometry ( around 1994 or 1995, when the last Hough PR was being studied).

Here is the current geometry.

The idea of simplication is :

Do not consider

GH having missing sensors
L, N, P having missing sensors

and consider only

AB, CD             for straight line track fit
EF                       for extrapolation of straight line
IJ, K, M, O        5 layers for curved part.

Here is our simplified geometry

What do you think? Looks like very similar to our old geometry, isn't it?

General idea of Hough PR

The track reconstruction is done by three steps:

1) Track seed finding: Using the layers, AB, CD, we apply a hit clustering algorithm (TPhMulguisin) on eta-phi space. A hit cluster that has minimum 3 hits is defined as a track seed. This step is done by TPhTrackSeedFinding.

-> Done (has never been a problem)

2) Curved track finding (track in the magnetic filed): To the 5 outer layers I, J, K, M, O, we apply the Hough PR. We have 4 pairs of layers, IJ, JK, KM, MO, just as we had in the original Hough study. For each pair of layers, we produce so called Hough match-sticks (lines connecting two hits between layers). A curve is then defined by 4 connecting Hough match-sticks which give consistent momenta and theta angles. More details in below.

-> Done (but I got stuck here)

3) Matching straight track seeds and curves: We extrapolate a straigh line track seed to the layers EF and associate hits. We extrapolate a curved track to the EF layers and associate hits. A seed and curve have same hits on EF are regarded as matched. This matching produces a track candidate.

-> Not yet done.

Definition of Hough Transformation & Hough table

For a given MC track we first take two hits (hit i, hit j) from a pair of layers. Hit i and hit j define a match-stick. For a given match-stick we can calculate "alpha" and "gamma" angles as defined in the above figure. "alpha" is highly correlated to the track polar angle "theta". And "gamma" is correlated with particle's momemtum "p". Hough transformation means that obtaining "theta" and "p" values for a given match-stick from "alpha" and "gamma".

Hough table then means a 2-dimensional array of "alpha" (200bins) and "gamma" (400bins) containing momentum "p" values. Another hough table is necessary for "theta". And we need these two tables for each pair of layers (finally 2x4 tables).

Implementation on Phat

I've created 3 classes for this study and modified TPhTrackFinder in order to steer these 3 classes.

1) TPhHough : new class actually for creation of Houble Table and manipulation.
2) TPhHoughHit : inherited from TPhHit, having additional data member for Match-stick information.
3) TPhHoughRoad : new class for Match-stick, having (1/p, theta) values and two hits on each end.

(I named the class TPhHoughRoad just because TPhHoughMatchSticks is too long. But I will call always "Match-stick" since this name is familar.)

TPhTrackFinder has a member function, FindCurve, which actually does the following procedure. Every HoughHits on the layer "I" are considered as curved track seeds. From these seeds, FindCurve generated all combination of HoughHit(I) - HoughRoad(IJ) - HoughHit(J) - HoughRoad(JK) - HoughHit(K) - HoughRoad(KM) - HoughHit(M) - HoughRoad(MO) - HoughHit(O). The sequence can be changed so that one can start from the layer O and go down to the layer I. By default I use "go-down" method.

4 Match-stick combination with compatible momenta (3%) and thetas (0.6 degree) gives a curve track candidate. We have to tune these parameter later. More detail later....

Event Sample

I use here 10 realistic central events which were generated by Krzysztof (cv0_full_10.aou). As my first try, Hough tables were generated by using of MC tracks of the events. The MC tracks used in the generation of the Hough table is

Momentum : 100MeV < P < 1GeV
Theta angle : 25 < theta < 70 (in degree)

to be consistent with the real Hough table.

Here are the hough tables for "p" and "theta" and for each pair of layers. X axis is "alpha" and Y axis is "gamma". They look like.....

For a given "alpha" and "gamma" bin, height of the bin is "p" or "theta". These hough tables are saved into a ROOT file format.

Curved track reconstruction by using the above hough table

For a given event, we first generate all combination of hits (match-sticks) for each pair of layers. Only a few match-sticks can survive because our Hough table has only small number of allowed "alpha" "gamma" values came from MC tracks.

Here is what I get,

Green lines are MC findable tracks and Dotted red lines are the tracks reconstructed by Hough PR! What a beautifule result!!!!!!!!!!!!!!!!

Here MC finadable means:

100MeV< P < 1GeV
25< theta < 70

and

have hits on I,J,K,M,O ( 100% efficiency assumed as in the original Hough study)

Event #2 : lucky case

Q, P, theta, phi, # of hits, # of hits after merging, # of hits per layer

        findable 0: 1 0.984 49.395 -0.015 15 13 1111121021101110
        findable 1: -1 0.814 34.601 0.015 17 14 2121111121101110
        findable 2: 1 0.321 67.987 0.047 15 11 1110100011222210
        findable 3: -1 0.682 34.595 0.095 16 14 1111111221101110
        findable 4: -1 0.477 51.085 -0.023 14 14 1111111011101111
        findable 5: -1 0.397 34.641 -0.033 17 14 2111121112101110
        findable 6: 1 0.485 43.705 0.057 17 15 1111121111101121
        findable 7: 1 0.235 58.803 -0.054 17 14 2111111012102111
        findable 8: -1 0.385 31.639 -0.100 19 13 2111210131201210
        findable 9: 1 0.263 54.580 0.034 15 14 1111211011101111
        findable 10: -1 0.356 62.590 0.003 18 14 2111211011212011
        findable 11: 1 0.554 48.816 -0.008 16 13 2111111011101220
        findable 12: 1 0.341 42.382 0.028 19 14 1121121112102021

We have 13 finadables, and by eyes, we found 12 good reconstruction.

Efficiency : 92%
Ghost level : 0%

Event #5: bad luck case

        findable 0: 1 0.157 54.247 0.064 13 13 1111111011101011
        findable 1: 1 0.351 63.444 0.032 15 13 1111111011101220
        findable 2: -1 0.438 30.963 0.025 15 13 1111120111101210
        findable 3: -1 0.496 54.076 0.013 14 13 1111121011101011
        findable 4: -1 0.255 56.792 0.035 17 14 1112111011122011
        findable 5: -1 0.643 30.052 0.091 15 13 1111210112101110
        findable 6: 1 0.246 48.730 -0.038 15 13 1111111011102021
        findable 7: 1 0.464 28.803 -0.029 18 14 1111110111212022
        findable 8: 1 0.281 58.407 0.020 15 13 1111111021101120
        findable 9: -1 0.214 64.544 0.042 16 14 1111111011122011
        findable 10: 1 0.675 62.470 -0.018 13 13 1111111011101110
        findable 11: 1 0.358 63.879 0.005 13 13 1111111011101110
        findable 12: 1 0.152 25.754 0.076 18 15 1121110211111121
        findable 13: -1 0.713 25.961 -0.044 20 13 2122110112222010
        findable 14: 1 0.238 45.808 -0.047 15 13 1112111011101021
        findable 15: -1 0.927 29.118 -0.057 16 13 1212120111101110
        findable 16: 1 0.733 60.917 0.057 15 13 1111121011101120

Here again we have 17 MC findables, and we found 9 well reconstructed.

Efficiency: 53%
Ghost : 0 %

These two figures show that my machinary works fine and also the Hough transform works.

Generation of Hough Tables by PhatPMC

Now, we need to generate the real Hough transformation tables. I use PhatPMC to do this job. Tracks are generated with theta range of 25 degree to 70 degree with 0.2 degree step, and momentum range 100MeV to 1GeV with 1% relative error. Pion + - are used and Energy loss are switched on (as in the default RHDATA file).

% MS is switched off... This must give the best Hough table in principle.

How beautiful these tables are!

The horizontal white bands are the momemtum cut on 1GeV.
The vertical white bands come from the cracks on detector which give no corresponding "alpha" value.
There are also other white bands coming from also cracks but depending on track's momentum and theta.

I see also many white bands in the histograms for IJ pair which comes from pixelization (??? am I right ???)

Understandable?

(I appreciate George's comments and helps to make this nice plot)

Technical remarks:
------------
A set of houble table (for a given vertex) is about 8Mbyte size. We have 4 pairs of layers, 400 bins for "gamma" and 200 bins for "alpha" and for momentum, theta, and multiplicity of the bin.

4 x 400 x 200 x 3 x 8bytes (double) = 7.5Mbyte...

I was trying to generate the Hough table with MS switch on (with few tens of same particle) but failed because of memory problems. But I realized that in the end the option "MS switched On" will give the same table from the option "Switch off" because of normalization......

Curved track reconstruction by using of the Hough table generated by PhatPMC

Then, now I run my Hough PR with the Hough Table generated by PhatPMC. I am scarred after looking the following figures...........

Event #2:

Event #5:

Oh! What happens? We are generating only ghosts..........................

Is my hough table not enoughly binned? Or some bugs in my implemetation.................

In fact I found a bug (I have to change the"alpha" range) after reading the Gunter's e-mail (he commented that there must be a bug). I would like to know whether I am going to the right direction (Gunter may answer) and whether he got the same behavior in his beginning stage of his work. If yes, so far so good......

Remark & ideas:

Whole skeleton for Hough PR is completed.

I got stuck at this level...........

Assuming that I resolve the above problem, I have

Some ideas :

- I got a new idea yesterday night just after a small discussion with Don about a possiblity of 1-D Hough transformation (Some of you remember...). The idea is that we only accept Match-sticks (1/p, theta) which are allowed by theta acceptance from the track seeds found by TPhTrackSeedFinder. I hope I can remove many match-sticks....... What do you think?

- George just added a idea: Instead of using 400x200 "alpha" "gamma" 2-D table, he proposed to use #pixels x #pixels table. I think this is more correct way. Are you agree? George may add something.

Next Plan:

- The most urgent thing is understing the problem.

- I would like to spend a day or so to test the idea of Removing Match-sticks using track seeds.

- I've asked to Adam to help me for my next step for ghost rejection by using of PID information. Adam already gave me the code.